Ricerca di parole input casuale di lettere in python.Quale algoritmo utilizzare/codice già lì?

Question

Sto cercando di codice di una parola decodicatore come questo qui e a chiedersi cosa algoritmi dovrei usare per implementare questo.Anche se chiunque può trovare il codice esistente per questo che sarebbe ottimo.Fondamentalmente la funzionalità sta per essere come un boggle risolutore, ma senza essere una matrice, solo cercando di word possibilità di una stringa di caratteri.Ho già dispongono di un'adeguata dizionari.

Avevo intenzione di farlo in python o ruby.Grazie in anticipo per il vostro aiuto ragazzi!!!

Answer 1

mi piacerebbe utilizzare un Trie . Ecco un'implementazione in Python: http://jtauber.com/2005/02/trie.py (credito per James Tauber)

Answer 2

Mi potrebbe mancare una comprensione del gioco, ma salvo qualche complicanze nelle regole, come ad esempio con l'introduzione del "joker" (jolly) lettere mancanti o altre lettere, più parole, ecc...Penso che le idee seguenti vorresti aiutare a trasformare il problema in un modo un po ' relativamente poco interessante la cosa.:-(

Idea principale le parole indice il ordinato sequenza di lettere.
Per esempio "computer" viene digitato come "cemoprtu".Qualunque sia casuale disegni di fornire è di smistamento in genere, e utilizzato come chiave per trovare le corrispondenze possibili.Utilizzando trie strutture come suggerito da perimosocordiae, come l'archiviazione sottostante per queste chiavi ordinate e parole associate(s)/wordIds in nodi "foglia", Parola ricerca può essere fatto in tempo O(n) , dove n è il numero di lettere (o meglio, in media, a causa della non-esistente parole).

Per facilitare ulteriormente l'indicizzazione possiamo avere diversi tavoli/dizionari, uno per ogni numero di lettere.Anche secondo le statistiche, le vocali e le consonanti possono essere esaminati separatamente.Un altro trucco sarebbe quello di avere un ordinamento personalizzato, mettendo il più selettivo lettere prima.

Ulteriori colpi di scena per il gioco (come la ricerca di parole fatto da un sottoinsieme di lettere) è in gran parte una questione di iterando il set di potenza di queste lettere e controllando il dizionario per ogni combinazione.

Qualche euristica può essere introdotto per aiutare a potare alcune delle combinazioni (ad esempio le combinazioni senza vocali [e di lunghezza] non sono possibili soluzioni etc.Si dovrebbe gestire questi euristica con attenzione per la ricerca di costo è relativamente piccolo.

Answer 3

Per l'indice dizionario, costruire una mappa (Map [Bag [Char], List [String]]). Dovrebbe essere una mappa di hash in modo da poter ottenere O (1) Parola di ricerca. Un Sacchetto [Char] è un identificatore di una parola che è unico fino a ordine dei caratteri. E 'fondamentalmente una mappa di hash da Char a Int. Il Char è un dato di carattere nella parola e l'Int è il numero di volte che il carattere appare nella parola.

Esempio:

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

di trovare le parole, prendere ogni combinazione di caratteri dalla stringa di input e guardare in su in questa mappa. La complessità di questo algoritmo è O (2 ^ n) nella lunghezza della stringa di input. In particolare, la complessità non dipende dalla lunghezza del dizionario.

Answer 4

Questo suona come Rabin-Karp stringa di ricerca sarebbe un bella scelta. Se si utilizza un hash-funzione di laminazione poi a ogni posizione è necessario un aggiornamento del valore di hash e uno di ricerca dizionario. È inoltre necessario creare un buon modo per far fronte a diverse lunghezze di parola, come troncando tutte le parole per la parola più breve nel set e ricontrollato possibili corrispondenze. Suddividere la parola impostata in un intervallo compreso separati riduce la quantità di falsi positivi a scapito di aumentare il lavoro hashing.

Answer 5

Ci sono due modi per farlo. Uno è quello di controllare ogni permutazione candidato di lettere nella parola per vedere se il candidato è nel tuo dizionario di parole. Questo è un O operazione (N!), A seconda della lunghezza della parola.

L'altro modo è quello di verificare ogni parola candidato nel vostro dizionario per vedere se è contenuta all'interno della parola. Questo può essere accelerato aggregando il dizionario; invece di ogni parola candidato, di controllare tutte le parole che sono anagrammi di ogni altro in una sola volta, dal momento che se uno di essi è contenuto nella tua parola, tutti sono.

Quindi iniziare con la costruzione di un dizionario la cui chiave è una stringa di lettere e ordinato il cui valore è un elenco di parole che sono anagrammi della chiave:

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

Ora abbiamo bisogno di una funzione per vedere se una parola contiene un candidato. Questa funzione presuppone che la parola e candidato siano entrambi ordinati, in modo che possa passare attraverso di loro sia lettera per lettera e rinunciare rapidamente quando constati che non corrispondono.

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

Ora trovare tutte le chiavi candidate nel dizionario che sono contenute dalla parola, e aggregare tutti i loro valori in un unico elenco:

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

Questo ultimo passaggio richiede circa un quarto di secondo sul mio computer portatile; ci sono 195K chiavi nel mio dizionario (sto usando il file di parole BSD Unix).