Поиск строк с.подстановочные

Question

У меня есть массив с таким количеством строк, и я хочу найти шаблон на нем. Этот шаблон может иметь некоторые "." подстановочный знак, который соответствует (каждому) 1 символу (любому).

Например:

myset = {"bar", "foo", "cya", "test"}

find(myset, "f.o") -> returns true (matches with "foo") 
find(myset, "foo.") -> returns false 
find(myset, ".e.t") -> returns true (matches with "test")
find(myset, "cya") -> returns true (matches with "cya")

Я пытался найти способ быстро реализовать этот алгоритм, поскольку myset на самом деле очень большой массив, но ни одна из моих идей не имеет удовлетворительной сложности (например, O(size_of(myset) * lenght(pattern)))

Edit:

myset - это огромный массив, слова в нем невелики. Я могу сделать медленную предварительную обработку. Но у меня будет так много find() запросов, поэтому find() Я хочу, чтобы find() был максимально быстрым.

Answer 1

Вы могли бы построить дерево суффиксов из всех возможных слов в вашем наборе ( см. Эту ссылку ). Используя эту структуру данных, ваша сложность включала бы единовременную стоимость O (n) для построениядерево, где n - сумма длин всех ваших слов.

После того, как дерево построено, поиск совпадений строк должен занять всего O (n), где n - длина строки.

Answer 2

Сначала разделите корпус на наборы по длине слова.Тогда ваш алгоритм поиска может выполнить поиск по соответствующему набору, поскольку для ввода в find() всегда требуется, чтобы совпадение имело определенную длину, и алгоритм может быть спроектирован так, чтобы хорошо работать со всеми словами одинаковой длины.

Далее (для каждого набора) создайте хэш-карту от хеша символа x до списка подходящих слов.Вполне нормально иметь большое количество хеш-коллизий.Вы можете использовать дельта-кодирование и кодирование длины строки, чтобы уменьшить размер списка совпадающих слов.

Для поиска выберите соответствующую карту хеш-функции для входной длины поиска и для каждого не . символа рассчитайтехэш для этого символа x position и AND вместе списки слов, чтобы получить значительно сокращенный список.

Поиск методом грубой силы по этому гораздо меньшему списку.

Answer 3

Если набор фиксирован, вы можете предварительно рассчитать частоты символа c, находящегося в позиции p (столько значений p, сколько вы считаете стоящими), затем один раз выполнить поиск в массиведля каждого элемента тестирование символов в определенных позициях в таком порядке, что вы, скорее всего, выйдете рано.

Answer 4

У меня был тот же вопрос, и я не был полностью доволен большинством идей / решений, которые я нашел в Интернете. Я думаю, что «правильный» способ сделать это - использовать Направленный ациклический граф слов . Я этого не сделал, но добавил Trie дополнительную логику, чтобы получить аналогичный эффект.

См. Мою реализацию isWord(), аналогичную желаемому интерфейсу find(). Он работает, возвращая Trie, разветвляясь по шаблону, а затем собирая результаты обратно в общий набор. (См. findNodes().)

getMatchingWords() похож по духу, за исключением того, что он возвращает набор совпадающих слов, а не просто логическое значение того, соответствует ли запрос чему-либо.

Answer 5

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

Список слов с первым символом «a», Список слов с первым символом «b», ..

Список слов, имеющих второй символ «a», Список слов, имеющих второй символ «b», ..

и так далее.

Когда вы ищете слово. Вы можете найти список слов, в которых первый символ совпадает с первым символом строки поиска. С этим уточненным списком ищите слова, у которых второй символ совпадает со вторым символом строк поиска и так далее. Вы можете игнорировать "." всякий раз, когда вы сталкиваетесь с ними.

Я понимаю, что создание стола может занять много места, но время, потраченное на это, значительно сократится.

Например, если у вас есть myset = {"bar", "foo", "cya", "test"} и вы ищете 'f.o'

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