找到所有满足未知字母的单词(汉格曼)

Question

我一直在做一个函数，可以用来解决像Hangman或“命运之轮”这样的文字游戏。

基本上，我希望从一个非常大的WORD_LIST (>100万个唯一条目)中搜索满足单词search中提供的字母的任何单词。

这方面的一个例子可能是如果search是"A??LE"，结果列表将包含苹果，脚踝，.

但从技术上讲，如果已经提供/披露了一封信，那么它也不可能是空白之一--例如；search=“挂起？？”可能会回来的，吊架，但不是绞刑架，因为A/N已经被猜测。

我主要想知道字符串搜索速度是否可以提高，还是更优雅(RegEx?)搜索的方法可以给我更快的结果，而不会失去准确性。

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

Answer 1

使用正则表达式解决方案确实要简单得多。诀窍是动态构建正则表达式，使用像[^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元字符(如. )。

(注意，regex.fullmatch()是在Python3.4中添加的。对于早期版本的Python，请使用regex.match，并将$附加到regex。)

Answer 2

有一件事需要考虑的是，到底是什么在运行多少次。这在一定程度上取决于用例。无论如何，每次运行此函数时都要执行len(w) != len(search)检查。相反，您可以先按长度分隔单词；创建一个字典，其中键是整数，值是该长度的单词列表。下一个问题是，您是否设想这个函数会在一个难题中运行一次，还是每次猜到一个新的字母时都会反复运行。如果是后者，@200_success的S回答将重新创建每个字母的正则表达式，这些字母与前一个字母仅略有不同，此时只需要检查新字母。因此，假设您有一个函数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，并查看它是否更快。

如果您想在每个拼图中只运行一次，您只需遍历字母，但这可能不是最优的。

Answer 3

好的,

我不确定这会不会更快，但我有一个基于非正则表达式的解决方案，它倾向于找到所有可能的组合，然后检查它们是否在would列表中。

我认为它可能更快的原因是，WORDLIST上的搜索是作为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??????")

在我的With列表中，这将产生(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'
]

编辑

正如Eric提到的，最初的解决方案内存非常昂贵，对于较大的问题，它可能会成为问题。这是因为它在检查之前存储了所有可能的组合。一个更新的版本是每次只检查几个。由于itertools.product生成迭代器，所以实际上不需要同时检查所有内容。

函数中的变量max_members_memory允许平衡速度与内存使用之间的关系，越大，所需的list.extend和set.intersection就越少。