Эффективная структура данных для поиска слов с подстановочными знаками

Question

Мне нужно сопоставить ряд введенных пользователем слов с большим словарем слов (чтобы убедиться, что введенное значение существует).

Так что, если пользователь ввел:

"orange" it should match an entry "orange' in the dictionary.

Сейчасподвох в том, что пользователь также может вводить символы подстановки или серии символов подстановки, например, скажем

"or__ge" which would also match "orange"

Основные требования:

* this should be as fast as possible.

* use the smallest amount of memory to achieve it.  

Если размер списка слов был малЯ мог бы использовать строку, содержащую все слова и использовать регулярные выражения.

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

Так что, какое-то «дерево» будет подходить дляэто ...?

Любые мысли или предложения по этому поводу будут полностью оценены!

Заранее спасибо, Мэтт

Answer 1

Поместите свой список слов в DAWG (ориентированный ациклический граф слов), как описано в статье Аппеля и Якобсена о самой быстрой в мире программе скрэббл ( бесплатная копия в Колумбии). Для вашего поиска вы пройдете этот график, сохраняя набор указателей: на букве вы делаете детерминированный переход к дочерним элементам с этой буквой; подстановочный знак добавляет всех детей в набор.

Эффективность будет примерно такой же, как в интерпретации NFA Томпсона для grep (это тот же алгоритм). Структура DAWG чрезвычайно экономична - гораздо больше, чем просто хранение самих слов. И это легко реализовать.

Наихудшей стоимостью будет размер алфавита (26?), Возведенный в степень числа подстановочных знаков. Но если ваш запрос начинается с N подстановочных знаков, простой поиск слева направо будет хорошо работать на практике. Я бы предложил запретить запуск запроса со слишком большим количеством символов подстановки или создать несколько разметок, например, разветвление для зеркального отображения, разветвление для повернутых влево трех символов и т. Д.

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

Answer 2

Независимо от того, какой алгоритм вы выберете, у вас есть компромисс между скоростью и потреблением памяти.

Если вы можете позволить себе ~ O (N * L) памяти (где N - размер вашего словаря, а L - средняя длина слова), вы можете попробовать этот очень быстрый алгоритм. Для простоты примем латинский алфавит с 26 буквами и MAX_LEN в качестве максимальной длины слова.

Создать двумерный массив наборов целых чисел, set<int> table[26][MAX_LEN].

Для каждого слова в вашем словаре добавьте индекс слов к наборам в позициях, соответствующих каждой из букв слова. Например, если «оранжевый» является 12345-м словом в словаре, вы добавляете 12345 к наборам, соответствующим [o] [0], [r] [1], [a] [2], [n] [ 3], [г] [4], [е] [5].

Затем, чтобы получить слова, соответствующие "or..ge", вы найдете пересечение множеств в [o] [0], [r] [1], [g] [4], [e] [ 5].

Answer 3

Я бы сначала проверил решение регулярных выражений и посмотрел, достаточно ли оно быстрое - вы можете быть удивлены! : -)

Однако, если бы этого было недостаточно, я бы использовал для этого дерево префиксов.

Базовая структура - это дерево, где:

• Узлы на верхнем уровне - это все возможные первые буквы (т.е., вероятно, 26 узлов из a-z, если вы используете полный словарь ...).
• Следующий уровень вниз содержит все возможные вторые буквы для каждой данной первой буквы
• И так до тех пор, пока вы не достигнете маркера "конца слова" для каждого слова

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

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

Answer 4

Вы можете попробовать строку-матрицу:

0,1: A
1,5: APPLE
2,5: AXELS
3,5: EAGLE
4,5: HELLO
5,5: WORLD
6,6: ORANGE
7,8: LONGWORD
8,13:SUPERLONGWORD

Давайте назовем это рваной индексной матрицей, чтобы сэкономить память. Заказывайте по длине, а затем по алфавиту. Для обозначения символа я использую обозначение x,y:z: x - индекс, y - длина записи, z - позиция. Длина вашей строки f, а g - количество записей в словаре.

• Создать список m, который содержит индексы потенциальных совпадений x.
• Итерация по z от 0 до f.
  • Это подстановочный знак и не последний символ строки поиска?
    • Продолжить цикл (все совпадения).
  • Пусто ли m?
    • Поиск по всем x от 0 до g для y, который соответствует длине. !! !!
      • Соответствует ли символ z строке поиска в этом z? Сохранить x в m.
    • Пусто ли m? Разрыв цикла (без совпадения).
  • Не является ли m пустым?
    • Поиск по всем элементам m. !! B !!
      • Не совпадает ли с поиском? Удалить из m.
    • m пусто? Разрыв цикла (без совпадения).

Подстановочный знак всегда будет пропускать «Соответствовать строке поиска?». И m одинаково упорядочен как матрица.

!! A !!: Двоичный поиск по длине строки поиска. O(log n)
!! B !!: бинарный поиск по алфавиту. O(log n)

Причиной использования строковой матрицы является то, что вы уже сохраняете длину каждой строки (потому что она ускоряет поиск), но она также дает вам длину каждой записи (при условии, что другие постоянные поля), так что вы можно легко найти следующую запись в матрице, для быстрой итерации. Упорядочение матрицы не является проблемой: поскольку это происходит только после обновления словаря, а не во время поиска.

Answer 5

Попробуйте построить обобщенное суффиксное дерево , если словарь будет соответствовать последовательности запросов. Для построения такого дерева можно использовать алгоритм линейного времени ( Ukkonen Suffix Tree Construction ).

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

Answer 6

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

Вы соответствуете только словам, поэтому вы можете разбить словарь на массив строк. Поскольку вы выполняете только точное совпадение с известной длиной, разбейте массив слов на отдельный массив для каждой длины слова. Таким образом, byLength [3] - это массив всех слов длиной 3. Каждый массив слов должен быть отсортирован.

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

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

Если поисковый термин имеет подстановочные знаки после некоторых буквенных символов, то выполните двоичный поиск в отсортированном массиве, чтобы найти верхнюю и нижнюю границы, затем выполните линейный поиск в этой границе. Если все символы подстановки завершаются, то достаточно найти непустой диапазон.

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

Если поисковый термин начинается и заканчивается символами подстановки, то вы застряли с линейным поиском в словах одинаковой длины.

Итак, массив массивов строк. Каждый массив строк сортируется и содержит строки одинаковой длины. При необходимости дублируйте всю структуру с помощью сортировки на основе строк в обратном направлении для случая с подстановочными знаками.

Общий пробел составляет один или два указателя на слово плюс слова. Вы должны иметь возможность хранить все слова в одном буфере, если позволяет ваш язык. Конечно, если ваш язык не позволяет, grep, вероятно, быстрее в любом случае. Для миллиона слов это 4-16 МБ для массивов и аналогичные для реальных слов.

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