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

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

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

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

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

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

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

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

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

Можно попробовать матрицу строк:

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, которые совпадают по длине. !!A!!
      • Совпадает ли символ z с поисковой строкой при этом z? Сохраните x в m.
    • Пуст ли m? Прервать цикл (нет совпадений).
  • Не является ли m пустым?
    • Поиск по всем элементам m. !!B!!
      • Совпадает ли not с поиском? Удалить из m.
    • В m пусто? Прервать цикл (нет совпадений).

Подстановочный знак всегда пройдет проверку "Совпадает с поисковой строкой?". А m одинаково упорядочен с матрицей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создайте двумерный массив наборов целых чисел, set 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].