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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

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

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

Ответ 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 пустым? Разрыв цикла (нет соответствия).

Подстановочный знак всегда будет передавать "Match with search string?". И m равноупорядочен как матрица.

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

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

Ответ 5

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

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

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

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

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

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

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

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

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

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

Ответ 6

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

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