Найти все слова, которые удовлетворяют неизвестных букв (палач)


Я работаю на функцию, которая может использоваться, чтобы решить игра в слова, как виселица или "Колесо Фортуны".

В принципе, я хочу, чтобы поиск из очень большого WORD_LIST (>1 млн. уникальных записей) для любого слова, которое удовлетворяет предоставленные Буквы в слове search.

Примером этого может быть, если search это "а??ЛЕ", то результирующий список будет содержать яблоко, голеностопного, ...

Но это технически, если письмо уже не предоставленные/не выявлено, то он также не может быть одной из заготовок, например; search= "висят???" может вернуться притон, вешалки , но не палач , потому что А/П , уже догадались.

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

def words_like(search, without_letters='', preclude_revealed_letters=True):
    if len(search) < 1:
        return []

    search = search.lower()
    without_letters = without_letters.lower()
    # Find indices of letters and blanks
    letters = [i for i, x in enumerate(list(search)) if x != "?"]
    blanks = [i for i, x in enumerate(list(search)) if x == "?"]

    if preclude_revealed_letters:
        # If a letter has been revealed, it can't also be one of the blanks
        without_letters = set(without_letters+''.join([x for x in search if x != "?"]))

    # Search our word-list for all matching "revealed" letters
    possible_words = []

    for w in WORD_LIST:
        if len(w) != len(search):
            continue
        for i in letters:
            if search[i] != w[i]:
                break
        else:
            possible_words.append(w)
    # Then remove all that use forbidden letters in the blanks
    without_possibles = []

    for w in possible_words:
        for i in blanks:
            if w[i] in without_letters:
                break
        else:
            without_possibles.append(w)
    return without_possibles


Комментарии
5 ответов

Решение действительно будет гораздо проще с помощью регулярных выражений. Хитрость заключается в том, чтобы построить регулярное выражение динамически, используя отрицается класс символов, как [^unwanted] для представления любого символа, кроме u, n, w, a, n, t, eили d.

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

import re

def words_like(search, without_letters='', preclude_revealed_letters=True):
forbidden_letters = set(without_letters)
if preclude_revealed_letters:
forbidden_letters.update(c for c in search if c != '?')
regex = re.compile(
search.replace('?', '[^' + ''.join(forbidden_letters) + ']'),
re.IGNORECASE
)
return filter(regex.fullmatch, WORD_LIST)

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

(Обратите внимание, что regex.fullmatch() был добавлен в Python 3.4. Для более ранних версий Python, использовать regex.matchи добавить $ в регулярное выражение.)

9
ответ дан 16 марта 2018 в 06:03 Источник Поделиться

Если вы пытаетесь ускорить поиск ваша основная цель должна заключаться в устранении цикл for w in WORD_LIST:. Для этого я бы просто построить трие от WORD_LIST. Тогда ваш код должен просто провести специальный поиск по этому Боре. Построить набор without_letters со всеми буквами уже в search. И тогда поиск Боре со следующими правилами:


  • Если search[i] это письмо вы просто съехать на Боре на пути соответствия search[i]т. е. нормального дерева поиска.

  • Если search[i] это ? Вы вниз каждый путь, не соответствующий букве в without_letters.

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

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

4
ответ дан 16 марта 2018 в 06:03 Источник Поделиться

Это довольно много @jesm00 отличное предложение.

Код

Вы создаете три первых:

def create_trie(words):
root = {}
for word in words:
curr_node = root
for letter in word:
curr_node = curr_node.setdefault(letter, {})
curr_node.setdefault('', True)
return root

with open('/usr/share/dict/american-english') as wordbook:
words = [word.strip().upper() for word in wordbook]

TRIE = create_trie(words)

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

def words_like(pattern, trie=TRIE, already_taken=None, temp=''):
pattern = pattern.upper()
if not already_taken:
already_taken = {letter for letter in pattern if letter != '?'}
already_taken.add('')
if pattern:
letter = pattern[0]
if letter == '?':
for node in trie:
if node not in already_taken:
yield from words_like(pattern[1:], trie[node],
already_taken, temp + node)
else:
yield from words_like(pattern[1:], trie.get(letter, {}),
already_taken, temp + letter)
else:
if trie.get(''):
yield temp

print(list(words_like('A??LE')))
# ['AISLE', 'AGILE', 'ADDLE', 'AMPLE', 'AMBLE', 'APPLE', 'ANKLE', 'ANGLE']
print(list(words_like('HANG???')))
# ['HANGERS', 'HANGOUT']

Производительности

Первая часть будет медленно (300мс на моем ноутбуке). Это не зависит от шаблона, поэтому можно вычислить его один раз и кэшировать его с pickle или JSON. pickle.loads(dumped_trie) ушло меньше 100 мс.

Вторая часть-это действительно быстро. Для 'HANG???'в боре версия более чем в 1500 раз быстрее, чем @200_success' код (40 мс против 68 МС). Боре код становится немного медленнее с более ? заполнители, это всегда на несколько порядков быстрее, чем другие ответы, хотя.

4
ответ дан 17 марта 2018 в 10:03 Источник Поделиться

Одно дело думать о том, что сколько раз запускали. Что-то зависит от случая использования. Несмотря ни на что, вы выполняете len(w) != len(search) проверяем каждый раз, когда вы запускаете эту функцию. Вместо этого, вы можете просто отдельные слова, длина спереди; создать словарь, в котором ключи являются целыми числами, а значения представляют собой списки слов той же длины. Следующий вопрос заключается в том как Вы себе представляете эту функцию один раз для головоломки, или неоднократно, каждый раз новые письма угадывается. Если последнее, @200_success 'ы ответ будет воссоздавать регулярные выражения для каждого письма, которое лишь немного отличается от предыдущего письма, когда вы только нужно проверить новые письма. Итак, предположим, у вас есть функция get_positions что возвращает список, который является пустым, если головоломка будет закончено, в противном случае первая запись последняя буква угадал, а второй элемент-это те позиции, которые появилось письмо (если буквы не появляются, то список пуст).

while True:
new_positions = get_positions()
if new_positions == []:
break
new_letter = new_positions[0]
positions = new_positions[1]
new_word_list = [word for word in old_word_list if
all([(word[i]==new_letter)==(i in positions)
for i in range(len(word))])
]
old_word_list = new_word_list

Вы также можете попробовать regex для создания new_word_list и посмотреть, будет ли это быстрее.

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

3
ответ дан 16 марта 2018 в 03:03 Источник Поделиться

ОК,

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

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

Вот как это будет происходить:

import itertools
import string
import gzip

WORDLIST = set([x.upper().strip() for x in gzip.open("words.txt.gz").readlines()])

def grouper(iterable, n):
while True:
yield itertools.chain([iterable.next()], itertools.islice(iterable, n-1))

def words_like(search, preclude_revealed_letters=True):
max_members_memory = 100000
search = search.upper()
if preclude_revealed_letters:
options = list(set(string.ascii_uppercase).difference(set(list(search))))
else:
options = string.ascii_uppercase

search = map(lambda x:x if x!= "?" else options, list(search))

real_words = []

for x in grouper(itertools.imap("".join, itertools.product(*search)), max_members_memory):
real_words.extend(list(WORDLIST.intersection(set(x))))

return real_words

print words_like("HA??????")

С моих слов, это производит (1min:56sec):

[
'HACKBUTS', 'HACKBOLT', 'HACKNEYS', 'HACKLIER', 'HACKLING', 'HACKLERS', 'HACKSTER', 'HACKTREE', 'HACKWOOD', 'HACKWORK', 'HABENDUM', 'HABILITY', 'HABITUDE', 'HABITURE', 'HABITING', 'HABITUES', 'HABSBURG', 'HABROWNE', 'HAEMOPOD', 'HAEREDES', 'HADDOCKS', 'HADFIELD', 'HADRONIC', 'HAGBERRY', 'HAGECIUS', 'HAGGERTY', 'HAGGISES', 'HAGGLING', 'HAGGLERS', 'HAGSTROM', 'HAGSTONE', 'HAGRIDER', 'HAGRIDES', 'HAGUETON', 'HAFFLINS', 'HAFNIUMS', 'HAFTOROT', 'HAILWEED', 'HAILWOOD', 'HAIRCUTS', 'HAIRBELL', 'HAIRGRIP', 'HAIRIEST', 'HAIRBIRD', 'HAIRPINS', 'HAIRLINE', 'HAIRLIKE', 'HAIRLOCK',
'HAIRNETS', 'HAIRLESS', 'HAIRWORK', 'HAIRWEED', 'HAIRWORM', 'HAIRWOOD', 'HAMBONED', 'HAMBONES', 'HAMBURGS', 'HAMETUGS', 'HAMFORRD', 'HAMIFORM', 'HAMILTON', 'HAMITISM', 'HAMITOID', 'HAMMERER', 'HAMMERED', 'HAMMIEST', 'HAMMOCKS', 'HAMLETED', 'HAMPERED', 'HAMPERER', 'HAMSTERS', 'HAMULOUS', 'HAMULOSE', 'HALCYONE', 'HALCYONS', 'HALBERTS', 'HALBERDS', 'HALECRET', 'HALENESS', 'HALESOME', 'HALEWEED', 'HALFCOCK', 'HALFLIFE', 'HALFNESS', 'HALFLING', 'HALFMOON', 'HALFUNGS', 'HALFTIME', 'HALFWORD', 'HALFWISE', 'HALFTONE', 'HALIBUTS', 'HALICORE', 'HALIDOMS', 'HALIDOME', 'HALIBIOS', 'HALIMOUS', 'HALIOTIS', 'HALINOUS', 'HALIPLID', 'HALLCIST', 'HALLETTE', 'HALLMOTE', 'HALLMOOT', 'HALLICET', 'HALLOING', 'HALLTOWN', 'HALLOWER', 'HALLOOED', 'HALLROOM', 'HALLOWED', 'HALLUCES', 'HALLOPUS', 'HALOBIOS', 'HALLWOOD', 'HALOGENS', 'HALOSERE', 'HALOLIKE', 'HALOXENE', 'HALUCKET',
'HALUTZIM', 'HALTERED', 'HALTERES', 'HALTLESS', 'HANDBILL', 'HANDBOLT', 'HANDEDLY', 'HANDCUFF', 'HANDBOOK', 'HANDBELL', 'HANDBLOW', 'HANDLOOM', 'HANDLINE', 'HANDGRIP', 'HANDLESS', 'HANDLERS', 'HANDGUNS', 'HANDLIKE', 'HANDIEST', 'HANDLOCK', 'HANDLING', 'HANDIRON', 'HANDLIST', 'HANDFEED', 'HANDFULS', 'HANDOUTS', 'HANDPICK', 'HANDREST', 'HANDSFUL', 'HANDSEWN', 'HANDSLED', 'HANDSPEC', 'HANDPOST', 'HANDSELS', 'HANDSETS', 'HANDOFFS', 'HANDSOME', 'HANDYMEN', 'HANGBIRD', 'HANDWORM', 'HANDWORK', 'HANDWRIT', 'HANGDOGS', 'HANGINGS', 'HANGFIRE', 'HANGMENT', 'HANGOVER', 'HANGNEST', 'HANGOUTS', 'HANGWORM', 'HANFORRD', 'HANIFISM', 'HANIFITE', 'HANKERER', 'HANKERED', 'HANKSITE', 'HANNOVER', 'HANSBORO', 'HANSELED', 'HANSFORD', 'HANSTEEN', 'HANZELIN', 'HAQUEBUT', 'HAQUETON', 'HAPLITIC', 'HAPLITES', 'HAPLOIDY', 'HAPLOSES', 'HAPLONTS', 'HAPLODON', 'HAPLOIDS', 'HAPLOSIS', 'HAPLOMID', 'HAPPENED', 'HAPPIEST', 'HAPSBURG', 'HAPTENIC', 'HAPTENES',
'HAPTERON', 'HASIDISM', 'HASKNESS', 'HASKWORT', 'HASPICOL', 'HASPLING', 'HASSOCKS', 'HASSOCKY', 'HASSLING', 'HASTENER', 'HASTENED', 'HASTIEST', 'HASTIFLY', 'HASTEFUL', 'HASTINGS', 'HARCOURT', 'HARBESON', 'HARBINGE', 'HARBOURS', 'HARBORER', 'HARBISON', 'HARBORED', 'HAREBELL', 'HAREMISM', 'HAREMLIK', 'HAREFOOT', 'HARELIPS', 'HARELIKE', 'HAREWOOD', 'HARDIEST', 'HARDBOOT', 'HARDCOPY', 'HARDESTY', 'HARDENER', 'HARDEDGE', 'HARDENED', 'HARDCORE', 'HARDFERN', 'HARDFIST', 'HARDNOSE', 'HARDLINE', 'HARDNESS', 'HARDWEED', 'HARDWICK', 'HARDTNER', 'HARDWOOD', 'HARDTOPS', 'HARDWIRE', 'HARICOTS', 'HARINGEY', 'HARKENER', 'HARKENED', 'HARKNESS', 'HARMINES', 'HARMINIC', 'HARMLESS', 'HARMONIE', 'HARMONIC', 'HARLETON', 'HARLOTRY',
'HARPISTS', 'HARPLESS', 'HARPINGS', 'HARPLIKE', 'HARPOONS', 'HARPSTER', 'HARPRESS', 'HARPWISE', 'HARSLETS', 'HARRELLS', 'HARRIERS', 'HARRIETT', 'HARROWED', 'HARRIOTT', 'HARRISON', 'HARROWER', 'HARRYING', 'HARUNOBU', 'HARUSPEX', 'HARTFORD', 'HARTNETT', 'HARTNELL', 'HARTLINE', 'HARTMUNN', 'HARTTITE', 'HARTZELL', 'HARTWICK', 'HARTWELL', 'HARTWOOD', 'HARTWORT', 'HARWILLL', 'HARVESTS', 'HARVISON', 'HARVIELL', 'HARYNGES', 'HAUBERKS', 'HAUERITE', 'HAULIERS', 'HAULMIER', 'HAULSTER', 'HAUNTING', 'HAUNTERS', 'HAUSTRUM', 'HAURIENT', 'HAUTBOYS', 'HAUTEURS', 'HAUTESSE', 'HAUTBOIS', 'HAUYNITE', 'HATBOXES', 'HATELESS', 'HATFIELD', 'HAWKEYES', 'HAWKBILL', 'HAWKINGS', 'HAWKLIKE', 'HAWKNOSE', 'HAWKWEED', 'HAWKWISE', 'HAVENING', 'HAVENFUL', 'HAVELOCK', 'HAVELESS', 'HAVENNER', 'HAVERING', 'HAVERELS', 'HAVIORED', 'HAVIOURS', 'HAVOCKER', 'HAVOCKED', 'HAYCOCKS', 'HAYFIELD', 'HAYFORKS', 'HAYLOFTS', 'HAYSEEDS', 'HAYRICKS', 'HAYRIDES', 'HAYWIRES', 'HAZELINE', 'HAZELESS', 'HAZELNUT', 'HAZELTON', 'HAZINESS', 'HAZLETON'
]

Редактировать:

Как Эрик упоминает, исходный раствор был очень дорогим и памяти для больших проблем может стать проблематичным. Это потому, что он был хранить все возможные комбинации, прежде чем проверить. Обновленная версия-это только несколько каждый раз. Что itertools.product создает итератор, никто не действительно нужно, чтобы проверить все одновременно.

Переменная max_members_memory в функции позволяет сбалансировать скорость и памяти, чем ее больше, тем меньше list.extend и set.intersection нужны.

3
ответ дан 16 марта 2018 в 04:03 Источник Поделиться