Хороший алгоритм и структура данных для поиска слов с пропущенными буквами?

Question

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

Например, если у меня есть что-то, я мог бы получить эти, те, темы, там и т. Д.

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

Спасибо!

РЕДАКТИРОВАТЬ: Trie слишком мало места и делает его слишком медленным. Любые другие модификации идей?

ОБНОВЛЕНИЕ: может быть до ДВУХ вопросительных знаков, и когда два вопросительных знака встречаются, они будут появляться последовательно.

В настоящее время я использую 3 хэш-таблицы для точного соответствия, 1 знак вопроса и 2 знака вопроса. Учитывая словарь, я хэширую все возможные слова. Например, если у меня есть слово WORD. Я хэш СЛОВО,? ORD, W? RD, WO? D, WOR ?,? RD, W? D, WO ??. в словарь. Затем я использую список ссылок, чтобы связать коллизии вместе. Так, скажем, hash (W? RD) = hash (STR? NG) = 17. hashtab (17) будет указывать на WORD, а WORD указывает на STRING, потому что это связанный список.

Время поиска в среднем одного слова составляет около 2е-6 с. Я хочу добиться большего успеха, желательно порядка 1e-9.

РЕДАКТИРОВАТЬ: я не смотрел на эту проблему снова, но это заняло 0,5 секунды для вставки записей 3м и 4 секунды для поиска записей 3м.

Спасибо!

Answer 1

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

Answer 2

Рассматривали ли вы использование троичного поиска дерева ? Скорость поиска сопоставима с деревом, но она более компактна.

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

Answer 3

В моем первом посте была ошибка, обнаруженная Джейсоном, она не работала, когда ?? был в начале. Я сейчас позаимствовал циклические сдвиги у Анны ..

Мое решение: Введите символ конца слова (@) и сохраните все циклически сдвинутые слова в отсортированных массивах !! Используйте один отсортированный массив для каждой длины слова. При поиске "th ?? e @" сдвиньте строку, чтобы переместить? -Марки до конца (получение e @ th ??), выберите массив, содержащий слова длиной 5, и выполните двоичный поиск первого встречающегося слова после строки "e @ th". Все оставшиеся слова в массиве совпадают, т.е. мы найдем «e @ thoo (thoose), e @ thes (this) и т. Д.

Решение имеет временную сложность Log (N), где N - размер словаря, и оно увеличивает размер данных примерно в 6 раз (средняя длина слова)

Answer 4

Структура данных, которую вы хотите, называется trie - краткую сводку см. В статье Википедии .

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

Answer 5

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

Вы можете начать с индекса на каждую длину слова, содержащего индекс каждого индекса = наборы слов, соответствующие символам. Для слов длиной 5, например, 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group} и т. Д. Чтобы получить возможные совпадения для исходного запроса, скажем, «? Ro ??», наборы слов будут пересекаться, что в данном случае приведет к {wrote, group}.

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

Answer 6

Резюме: Используйте два компактных индекса с двоичным поиском, одно из слов и одно из перевернутых слов. Стоимость места составляет 2N указателей для индексов; почти все поиски идут очень быстро; в худшем случае, «?? e», все еще приличный. Если вы создадите отдельные таблицы для каждой длины слова, это очень быстро сделает даже худший случай.

Подробности: Стивен С. опубликовал хорошая идея : поиск в упорядоченном словаре, чтобы найти диапазон, в котором может появиться шаблон. Это не помогает, однако, когда шаблон начинается с подстановочного знака. Вы также можете индексировать по длине слова, но вот еще одна идея: добавить упорядоченный индекс по обращенным словарным словам; тогда шаблон всегда дает небольшой диапазон либо в прямом индексе, либо в индексе обратного слова (поскольку нам говорят, что нет таких шаблонов, как «ABCD»). Сами слова должны быть сохранены только один раз, причем записи обеих структур указывают на одни и те же слова, а процедура поиска просматривает их либо вперед, либо назад; но чтобы использовать встроенную в Python функцию бинарного поиска, я вместо этого создал два отдельных массива строк, потратив некоторое пространство. (Я использую отсортированный массив вместо дерева, как предлагали другие, так как он экономит место и работает по крайней мере так же быстро.)

Код

import bisect, re

def forward(string): return string
def reverse(string): return string[::-1]

index_forward = sorted(line.rstrip('\n')
                       for line in open('/usr/share/dict/words'))
index_reverse = sorted(map(reverse, index_forward))

def lookup(pattern):
    "Return a list of the dictionary words that match pattern."
    if reverse(pattern).find('?') <= pattern.find('?'):
        key, index, fixup = pattern, index_forward, forward
    else:
        key, index, fixup = reverse(pattern), index_reverse, reverse
    assert all(c.isalpha() or c == '?' for c in pattern)
    lo = bisect.bisect_left(index, key.replace('?', 'A'))
    hi = bisect.bisect_right(index, key.replace('?', 'z'))
    r = re.compile(pattern.replace('?', '.') + '$')
    return filter(r.match, (fixup(index[i]) for i in range(lo, hi)))

Тесты: (Код также работает для таких шаблонов, как «AB? D», но без гарантии скорости.)

>>> lookup('hello')
['hello']
>>> lookup('??llo')
['callo', 'cello', 'hello', 'uhllo', 'Rollo', 'hollo', 'nullo']
>>> lookup('hel??')
['helio', 'helix', 'hello', 'helly', 'heloe', 'helve']
>>> lookup('he?l')
['heal', 'heel', 'hell', 'heml', 'herl']
>>> lookup('hx?l')
[]

Эффективность: Для этого требуется 2N указателей плюс пространство, необходимое для хранения текста словарного слова (в настроенной версии). Наихудшее время наступает на паттерне '?? e', который просматривает 44062 кандидата в моих 235 тыс. Слов / usr / share / dict / words; но почти все запросы выполняются намного быстрее, например, «h ?? lo», смотрящий на 190, и индексирование сначала по длине слова уменьшит «e» почти до нуля, если потребуется Каждая проверка кандидатов проходит быстрее, чем хэш-таблицы, которые предлагали другие.

Это напоминает решение rotations-index , которое позволяет избежать всех кандидатов на ложное совпадение за счет необходимости указывать около 10N указателей вместо 2N (предполагая, что средняя длина слова составляет около 10, как в my / usr /share/dict/words).

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

Answer 7

Ленивое решение - позволить SQLite или другой СУБД выполнить эту работу за вас.

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

Answer 8

Вот как бы я это сделал:

1. Объединить слова словаря в одну длинную строку, разделенную несловесным символом.
2. Поместите все слова в TreeMap, где ключ - это слово, а значение - смещение начала слова в большой строке.
3. Найти базу строки поиска; то есть самая большая ведущая подстрока, которая не включает '?'.
4. Используйте TreeMap.higherKey(base) и TreeMap.lowerKey(next(base)), чтобы найти диапазон в строке, между которым будут найдены совпадения. (Метод next должен вычислять следующее большее слово в базовой строке с тем же числом или меньшим количеством символов; например, next("aa") равно "ab", next("az") равно "b".)
5. Создайте регулярное выражение для строки поиска и используйте Matcher.find() для поиска подстроки, соответствующей диапазону.

Шаги 1 и 2 выполняются заранее, давая структуру данных, используя O(NlogN) пробел, где N - количество слов.

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

РЕДАКТИРОВАТЬ :

Чтобы повысить производительность в случае, когда '?' является первым символом, создайте вторичную справочную таблицу, в которой записываются начальные / конечные смещения серий слов, вторыми символами которых являются «a», «b» и т. Д. , Это может быть использовано в случае, когда первый не '?' это второй персонаж. Вы можете использовать аналогичный подход для случаев, когда первый не '?' является третьим символом, четвертым символом и т. д., но в конечном итоге вы получаете все большее и меньшее количество прогонов, и в конечном итоге эта «оптимизация» становится неэффективной.

Альтернативный подход, который требует значительно больше места, но в большинстве случаев быстрее, состоит в том, чтобы подготовить структуру данных словаря, как указано выше, для всех поворотов слов в словаре. Например, первый поворот будет состоять из всех слов 2 символа или более, а первый символ слова будет перемещен в конец слова. Вторым поворотом будут слова из 3 или более символов, первые два символа будут перемещены в конец и т. Д. Затем, чтобы выполнить поиск, найдите последовательность longest , отличную от '?' символы в строке поиска. Если индекс первого символа этой подстроки равен N, используйте вращение Nth, чтобы найти диапазоны, и выполните поиск в списке слов N-го вращения.

Answer 9

Если вы серьезно хотите что-то порядка миллиарда поисков в секунду (хотя я не могу мечтать, почему кто-то за пределами кого-то, кто делает следующий гроссмейстерский AI-скраббл или что-то для огромного веб-сервиса, захочет так быстро), Я рекомендую использовать потоки для порождения потоков [количество ядер на вашем компьютере] + мастер-поток, который делегирует работу всем этим потокам. Затем примените лучшее решение, которое вы нашли на данный момент, и надеемся, что вам не хватит памяти.

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

Еще одна мысль, которая у меня возникла, заключалась в том, что вы пытались что-то перебить - возможно, создать БД или список или что-то для скрэббл?

Answer 10

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

Character Index 0:
  'a' -> {"arete", "arite"}
  'd' -> {"drate"}
  'w' -> {"write", "wrote"}
Character Index 1:
  'r' -> {"write", "wrote", "drate", "arete", "arite"}
Character Index 2:
  'a' -> {"drate"}
  'e' -> {"arete"}
  'i' -> {"write", "arite"}
  'o' -> {"wrote"}
...

Если вы хотите посмотреть a?i??, вы бы взяли набор, который соответствует индексу символов 0 => 'a' {"arete", "arite"} и набор, который соответствует индексу символов 2 = 'i' => {"write", "arite"} и возьмите установленное пересечение.