Быстрый алгоритм частичного поиска текста

Question

У меня есть список слов, описывающих действия, например:

New
Open
Save
Save as
Copy
Paste
Cut
Select all

и т. Д.

Я бы хотел, чтобы пользователь мог находить команды, вводя только пару буквв последовательности.Поэтому, если пользователь ввел, например, «ae», он должен получить:

sAvE
sAvE as
pAstE

В общем, когда пользователь вводит «abc», я хочу вернуть все строки, соответствующие регулярному выражению .*a.*b.*c.*.Поскольку проверка совпадения строки в этом выражении является линейной, а алгоритм bruteforce также является линейным, регулярные выражения не сильно помогут в оптимизации поиска.

Важным моментом в этом списке является то, что он известен во время компиляции, поэтомуЯ могу разработать структуру данных, которая будет содержать все эти термины, чтобы ускорить поиск.

Существует ли структура данных или алгоритм, который ускорил бы поиск всех подходящих слов для конкретной записи пользователя, кроме O (m * n) (где m - количество терминов, а n - средняя длина терминов)?

Answer 1

Для меня это звучит как случай преждевременной оптимизации.Смешно преждевременно.Даже если у вас есть 70 команд вместо всего лишь семи, время, необходимое для последовательного поиска всех ваших команд, настолько мало, что ваш пользователь не заметит этого.И это не значит, что эту функцию вы будете вызывать сотни или тысячи раз в секунду.Таким образом, тратя часы на реализацию причудливого поиска, вы сэкономите несколько миллисекунд, а время просто потрачено впустую.Вполне вероятно, что количество времени, которое ваши пользователи сэкономят в течение жизни программы, даже близко не будет соответствовать количеству времени, которое вы потратите на разработку, написание и отладку оптимизированного решения.

У вас естьнебольшое количество очень коротких команд.Компьютеры быстры.Здесь нет проблем для решения.Потратьте свое время на функции, которые действительно принесут пользу пользователю.

Теперь, если у вас есть очень большое количество (десятки тысяч) строк для поиска, вы можете воспользоваться некоторой оптимизацией.В таком случае .,.

Вы могли бы начать с создания словаря с буквенным обозначением, а значением является список всех слов, содержащих эту букву.Таким образом, ваш пример будет выглядеть примерно так:

a, [Save, Save as, Paste]
c, [Copy, Cut, Select all]
e, [New, Open, Save, Save as, Paste, Select all]
n, [New, Open]
... etc.

Затем введите в словаре слова "буква следует за буквой".Это станет большим в спешке.Например, «Вставить» будет содержать записи:

pa ps pt pe как в начале сеанса

Вы можете продолжить создавать эти ключи для более длинных подстрок.Например, вы получаете:

pas pat pae pst pse pse pte

Это может быть очень эффективно, когда строки короткие.Это становится менее эффективным, когда строки становятся длиннее, потому что вероятность строки, содержащей определенную комбинацию букв, увеличивается с увеличением длины строки.

Возможно, вы могли бы сэкономить некоторое пространство, создав trie ,но техника по сути та же самая.

Также потенциально полезно: дерево суффиксов и обобщенный суффикс tre e.

Answer 2

Я не знаю много о его временной сложности, но если мы просто хотим найти слова, которые должны содержать a и e, мы начнем с выражения, подобного следующему, тогда мы оптимизировал бы для времени выполнения:

(?=.*a)(?=.*e).*

Test

using System;
using System.Text.RegularExpressions;

public class Example
{
    public static void Main()
    {
        string pattern = @"(?=.*a)(?=.*e).*";
        string input = @"New
Open
Save
Save as
Copy
Paste
Cut
Select all";
        RegexOptions options = RegexOptions.Multiline;

        foreach (Match m in Regex.Matches(input, pattern, options))
        {
            Console.WriteLine("'{0}' found at index {1}.", m.Value, m.Index);
        }
    }
}

Демо

Answer 3

Как написано в моем комментарии, вероятно, вам не стоит слишком беспокоиться о производительности ...

Однако эта структура данных должна соответствовать вашим потребностям, назовем ее буквой X перед деревом Y. По сути, это дерево, в котором у каждого узла есть дочерние элементы для каждой буквы, если буква появляется после буквы родительских узлов в целевом слове. Для каждого узла вы должны хранить список всех совпадений.

public class Node
{
    public char Letter { get; set; }

    public Node[] Children {get;set;}

    public List<string> CommandNames {get;set;} 
}

Вы можете предварительно заполнить его всеми известными именами, как это

p paste
a paste
s paste
..
p/a paste
p/s paste
p/t paste
..
t/e paste
..
p/a/s paste
..
s/t/e paste

Совпадение с поисковым словом просто означает обход вашего дерева для каждой буквы, введенной пользователем, поэтому оно сводится к O (n)