Encontrando palavras de letras de entrada aleatórias em Python. Qual algoritmo para usar/código já aí?

Question

Estou tentando codificar uma palavra descrabador como esta aqui e estava se perguntando quais algoritmos eu deveria usar para implementar isso. Além disso, se alguém puder encontrar o código existente para isso, também seria ótimo. Basicamente, a funcionalidade será como um solucionador de boggle, mas sem ser uma matriz, apenas pesquisando todas as possibilidades de palavras de uma série de caracteres. Eu já tenho dicionários adequados.

Eu estava planejando fazer isso em Python ou Ruby. Agradecemos antecipadamente por sua ajuda pessoal!

Answer 1

Eu usaria um Trie. Aqui está uma implementação no Python: http://jtauber.com/2005/02/trie.py (Crédito para James Tauber)

Answer 2

Eu posso estar perdendo um entendimento do jogo, mas impedindo algumas complicações nas regras, como com a introdução de cartas "Joker" (curinga), cartas ausentes ou adicionais, várias palavras etc. Eu acho que as seguintes idéias ajudariam a mudar O problema em uma coisa um tanto relativamente desinteressante. :-(

Ideia principal palavras de índice pelo ordenado Sequência de suas cartas.
Por exemplo, "Computer" é digitado como "cemoprtu". O que quer que os desenhos aleatórios forneçam é classificada em espécie e usada como chave para encontrar possíveis correspondências. Usando Trie Estruturas conforme sugerido por perimosocordiae, como o armazenamento subjacente para essas chaves classificadas e palavras associadas (s)/wordids nos nós "folhas", palavra A pesquisa pode ser feita no tempo O (n), onde n é o número de letras (ou melhor, em média devido a palavras inexistentes).

Para ajudar ainda mais com a indexação, podemos ter várias tabelas/dicionários, um por número de letras. Também dependendo das estatísticas, as vogais e as consoantes podem ser tratadas separadamente. Outro truque seria ter uma ordem de classificação personalizada, colocando as letras mais seletivas primeiro.

Reviravoltas adicionais para o jogo (como encontrar palavras feitas de um subconjunto das letras) é principalmente uma questão de iterando o conjunto de força Destas cartas e verificando o dicionário para cada combinação.

Algumas heurísticas podem ser introduzidas Para ajudar a podar algumas das combinações (por exemplo, combinações sem vogais [e de um determinado comprimento] não são soluções possíveis etc. Deve -se gerenciar essas heurísticas cuidadosamente para o custo de pesquisa é relativamente pequeno.

Answer 3

Para o seu índice de dicionário, construa um mapa (mapa [saco [char], list [string]]). Deve ser um mapa de hash para que você possa obter uma pesquisa de palavras o (1). Uma bolsa [char] é um identificador para uma palavra que é única até a ordem dos personagens. É basicamente um mapa de hash de char para int. O char é um determinado personagem na palavra e o int é o número de vezes que esse personagem aparece na palavra.

Exemplo:

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

Para encontrar palavras, pegue todas as combinações de caracteres da string de entrada e procure -a neste mapa. A complexidade desse algoritmo é O (2^n) no comprimento da sequência de entrada. Notavelmente, a complexidade não depende do comprimento do dicionário.

Answer 4

Isso parece Pesquisa de string de Rabin-Karp Seria uma boa escolha. Se você usar uma função de hash rolling, em cada posição, precisará de uma atualização de valor de hash e uma pesquisa de dicionário. Você também precisa criar uma boa maneira de lidar com diferentes comprimentos de palavras, como truncando todas as palavras para a palavra mais curta no conjunto e a recodificação de possíveis correspondências. A divisão da palavra definida em faixas de comprimento separadas reduzirá a quantidade de falsos positivos à custa de aumentar o trabalho de hash.

Answer 5

Existem duas maneiras de fazer isso. Uma é verificar todo o candidato permutação de letras na palavra para ver se o candidato está no seu dicionário de palavras. Essa é uma operação O (N!), Dependendo do comprimento da palavra.

A outra maneira é verificar cada palavra candidata em seu dicionário para ver se está contida na palavra. Isso pode ser acelerado agregando o dicionário; Em vez de cada palavra candidata, você verifica todas as palavras que são anagramas uma da outra de uma vez, pois se qualquer uma delas estiver contida em sua palavra, todas elas são.

Então comece construindo um dicionário cuja chave é uma sequência de letras classificadas e cujo valor é uma lista das palavras que são anagramas da chave:

>>> 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)

Agora precisamos de uma função para ver se uma palavra contém um candidato. Essa função pressupõe que a palavra e o candidato sejam classificados, para que ela possa passar por letra por carta e desistir rapidamente quando descobrir que eles não correspondem.

>>> 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

Agora encontre todas as chaves do candidato no dicionário que estão contidas pela palavra e agregue todos os seus valores em uma única lista:

>>> 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']

Esse último passo leva cerca de um quarto de segundo no meu laptop; Existem 195K Keys no meu dicionário (estou usando o arquivo de palavras do BSD Unix).