如何改进这种猜测算法？

Question

我试图做一个程序，猜测用户所想的词，但现在的程序只是基于消除。有没有人对如何让它变得更好有想法？你知道吗

下面简要介绍一下它现在的工作原理：

我有一个单词列表存储在“palavras.txt文件，则这些单词将被转换为常规列表。你知道吗

第一个问题是：“你的单词有多少个字母？”。在此基础上，该程序继续消除所有其他单词谁没有同样数量的字母。之后，它创建一个列表，其中包含按字母在给定位置出现的次数组织的所有字母。你知道吗

然后我们有第二个问题：“x”是你单词的第一个字母吗。如果回答为“not”，则删除该位置包含该字母的所有单词，然后转到该位置最常用的第二个字母，依此类推。如果是的话，它会删除所有在特定位置不包含该字母的单词，并转到该单词的下一个字母。以此类推，直到单词写完。你知道吗

它一直有效，但有时需要相当多的时间。有更好的方法吗？人工智能？也许是机器学习？你知道吗

代码并不重要，因为我只是在寻找想法，但如果有人好奇，我是如何做到的：

import os
from unicodedata import normalize
import random
import string

# Define a função que retira os acentos das palavras
def remover_pont(txt):
    import string
    return txt.translate(str.maketrans('', '', string.punctuation))

def remover_acentos(txt):
    return normalize('NFKD', txt).encode('ASCII', 'ignore').decode('ASCII')

# Retorna uma lista com as letras mais usadas naquela posição, em ordem
def letramusada(lista, pletra):
    pletraordem = []
    pletraordem2 = []
    pl = []

    for n in lista:
        try:
            pl.append(n[pletra - 1])
        except:
            pass

    dict = {}
    for k in pl:
        if k in dict:
            dict[k] += 1
        else:
            dict[k] = 1
    pletraordem2 = (sorted(dict.items(), key=lambda t: t[1], reverse=True))

    for c in pletraordem2:
        pletraordem.append(c[0])

    return pletraordem

# Lê o "banco de dados" que contém as palavras e as armazena na variável "palavras", sem acentos
file = open('palavras.txt')
palavras = file.read().split("\n")

# Armazena a quantidade de letras que a palavra pensada tem
nletras = int(input('Digite o número de letras da palavra (considerando hífen, caso haja) que você pensou, com máximo de 8: '))

# Declara listas que serão usadas em seguida
npalavras = []
palavras2 = []
palavras3 = []
# Armazena todas as palavras que contém a quantidade de letras escolhida anteriormente em uma nova lista chamada "nletras", desconsiderando pontos

for n in palavras:
    if nletras == len(n):
        npalavras.append(remover_acentos(n).lower())

c = 0
n = 0

for k in range(1, nletras + 1):
    ordem = letramusada(npalavras, k)
    cond = 0
    try:
        while cond == 0:
            if  len(npalavras) < 20 and c == 0:
                print("\nHmmm, estou chegando perto!\n")
                c += 1
            if len(npalavras) < 3:
                break
            for c in ordem:
                if c != 0:
                    r = str(input("A {} letra da sua palavra é a letra \"{}\"? [S/N] ".format(k, c))).lower()
                    r = r[0]
                    if r == "s":
                        for n in npalavras:
                            if n[k-1] == c:
                                palavras2.append(n)
                        npalavras.clear()
                        npalavras = palavras2[:]
                        palavras2.clear()
                        ordem.clear()
                        cond += 1
                        break
                    else:
                        for n in npalavras:
                            if n[k-1] != c:
                                palavras2.append(n)
                        npalavras.clear()
                        npalavras = palavras2[:]
                        palavras2.clear()
                        r = 0
                        pass
    except:
        n = 1
        print("\nDesculpe, não achei nenhuma palavra :(")

escolha = random.choice(npalavras)

if n != 0:
    print("\nA palavra que você pensou é: \"{}\"".format(escolha))

Answer 1

还有一篇文章提到了单词暗示算法，甚至还有python代码。 这是链接What algorithm gives suggestions in a spell checker?

Answer 2

暴力是你的朋友

人们可能认为“机器学习”是一颗银弹，但是，学什么呢？尤其是在信息不多的情况下。你能优化什么？你的描述听起来像是一种纯粹的暴力dictionary based password cracking，而生活在今天的黑客正是utilizing the power of GPU。你知道吗

这可能有点离题，但即使有一个GPU的搜索可能很难。如果您不受特定语言/平台的限制，那么上面的hashcat链接很有用。著名的133 MB dictionary可以在MacBookPro上5分钟内枚举，这比Python中的猜测功能强大得多。你知道吗

搜索空间和字型

另外，average length for English words大约是8，这种情况与典型的密码非常相似。i、 你的搜索空间很大-上界是26^8=208827064576个单词！-除了玩家在游戏中只能使用有限的单词列表。你知道吗

实际的搜索空间可能会小一点，因为在英语单词中有一些模式（比如s是最常见的字母表，ae，as可能比az事物出现得更频繁），但是您使用的是词典，所以我认为这没有帮助。你知道吗

非字典方法

另一个想法是，这个过程可以非常接近于恢复一个DNA序列，它也有一些模式，但给出的信息可能会有所不同。把它当作一个word suggestion。生物信息学利用DNA序列中的概率模式来计算imputation。你知道吗

当您可以逐步猜单词/顺序时，此方法会有所帮助。否则，您只能使用暴力方法（当您的单词只能从哈希中恢复时）。你知道吗

用于搜索引擎、输入法和DNA插补的经典方法是hidden markov model。它根据您以前的输入猜测下一个字符，概率是使用实际单词预先计算的统计值。你知道吗

这可以与字典相结合，对你的建议（猜测）进行排序，并提供更准确的猜测。你知道吗

Answer 3

您可以存储已经使用过的单词，比如说第一个用户使用了单词“carro”，然后您可以将其添加到一个文件中，在几个字母之后，程序可以检查已经说过的单词的列表，查看该单词是否与给定的描述相匹配，例如：“has a c as first letter”，并询问下一个用户“carro”是否是他们的单词，您可以通过为每个单词添加一个计数器来进一步改进这一点，以便使用较多的单词出现在使用较少的单词的顶部。你知道吗