Поиск слов по случайным введенным буквам в Python.Какой алгоритм использовать/код уже есть?

StackOverflow https://stackoverflow.com/questions/1570242

Вопрос

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

Я планировал сделать это либо на Python, либо на Ruby.Заранее спасибо за вашу помощь, ребята!

Это было полезно?

Решение

я бы использовал Три.Вот реализация на Python: http://jtauber.com/2005/02/trie.py (кредит Джеймсу Тауберу)

Другие советы

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

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

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

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

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

Для индекса словаря создайте карту (Map[Bag[Char], List[String]]).Это должна быть хеш-карта, чтобы вы могли найти слово O (1).Bag[Char] — это идентификатор слова, уникальный с точностью до порядка символов.По сути, это хэш-карта от Char до Int.Char — это заданный символ в слове, а Int — количество раз, которое этот символ встречается в слове.

Пример:

{'a'=>3, 'n'=>1, 'g'=>1, 'r'=>1, 'm'=>1} => ["anagram"]
{'s'=>3, 't'=>1, 'r'=>1, 'e'=>2, 'd'=>1} => ["stressed", "desserts"]

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

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

Есть два способа сделать это.Один из них — проверить каждую кандидатскую перестановку букв в слове, чтобы увидеть, есть ли кандидат в вашем словаре слов.Это операция O(N!), в зависимости от длины слова.

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

Итак, начнем с создания словаря, ключ которого представляет собой отсортированную строку букв, а значение — список слов, которые являются анаграммами ключа:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> with open(r"c:\temp\words.txt", "r") as f:
        for line in f.readlines():
            if line[0].isupper(): continue
            word = line.strip()
            key = "".join(sorted(word.lower()))
            d[key].append(word)

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

>>> def contains(sorted_word, sorted_candidate):
        wchars = (c for c in sorted_word)
        for cc in sorted_candidate:
            while(True):
                try:
                    wc = wchars.next()
                except StopIteration:
                    return False
                if wc < cc: continue
                if wc == cc: break
                return False
        return True

Теперь найдите в словаре все потенциальные ключи, содержащиеся в слове, и объедините все их значения в один список:

>>> w = sorted("mythopoetic")
>>> result = []
>>> for k in d.keys():
        if contains(w, k): result.extend(d[k])
>>> len(result)
429
>>> sorted(result)[:20]
['c', 'ce', 'cep', 'ceti', 'che', 'chetty', 'chi', 'chime', 'chip', 'chit', 'chitty', 'cho', 'chomp', 'choop', 'chop', 'chott', 'chyme', 'cipo', 'cit', 'cite']

На моем ноутбуке этот последний шаг занимает около четверти секунды;В моем словаре 195 тысяч ключей (я использую файл слов BSD Unix).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top