Algoritmo di scramble delle parole efficiente

Question

Sto cercando un algoritmo efficiente per rimescolare una serie di lettere in una permutazione contenente il numero massimo di parole.

Ad esempio, dire che mi viene fornita la lista di lettere: {e, e, h, r, s, t}. Ho bisogno di ordinarli in modo tale da contenere il numero massimo di parole. Se ordino quelle lettere in "theres", contiene le parole "the", "there", "her", "here" e "ere". Quindi quell'esempio potrebbe avere un punteggio di 5, poiché contiene 5 parole. Voglio ordinare le lettere in modo tale da avere il punteggio più alto (contiene la maggior parte delle parole).

Un algoritmo ingenuo sarebbe quello di provare a segnare ogni permutazione. Credo che questo sia O (n!), Quindi verrebbero tentate 720 diverse permutazioni solo per le 6 lettere sopra (inclusi alcuni duplicati, dato che l'esempio ha due e). Per più lettere, la soluzione ingenua diventa rapidamente impossibile, naturalmente.

L'algoritmo non deve effettivamente produrre la soluzione migliore, ma dovrebbe trovare una buona soluzione in un ragionevole lasso di tempo. Per la mia applicazione, la semplice supposizione (Monte Carlo) a qualche milione di permutazioni funziona in modo piuttosto scadente, quindi è attualmente il punto da battere.

Attualmente sto utilizzando l'algoritmo Aho-Corasick per ottenere le permutazioni. Cerca ogni parola nel dizionario in una sola passata del testo, quindi credo che sia abbastanza efficiente. Ciò significa anche che ho tutte le parole memorizzate in un trie, ma se anche un altro algoritmo richiede una memorizzazione diversa va bene. Non sono preoccupato di impostare il dizionario, solo il tempo di esecuzione degli ordini e delle ricerche effettivi. Potrebbe anche essere usato un dizionario fuzzy, se necessario, come lo Bloom Filter.

Per la mia applicazione, l'elenco di lettere fornite è circa 100 e il dizionario contiene oltre 100.000 voci. Il dizionario non cambia mai, ma è necessario ordinare diversi elenchi di lettere.

Sto considerando di provare un path finding algorithm. Credo che potrei iniziare con una lettera casuale dalla lista come punto di partenza. Quindi ogni lettera rimanente verrebbe utilizzata per creare un "percorso". Penso che questo potrebbe funzionare bene con l'algoritmo di punteggio Aho-Corasick, dal momento che i punteggi potrebbero essere costruiti una lettera alla volta. Tuttavia non ho ancora provato la ricerca di percorsi; forse non è nemmeno una buona idea? Non so quale algoritmo di ricerca del percorso potrebbe essere il migliore.

Un altro algoritmo che ho pensato inizia anche con una lettera casuale. Quindi il dizionario verrà cercato per i rami "ricchi" contenenti le lettere rimanenti. I rami del dizionario contenenti lettere non disponibili sarebbero stati eliminati. Sono un po 'annebbiato sui dettagli di come funzionerebbe esattamente, ma potrebbe eliminare completamente le permutazioni dei punteggi.

Answer 1

Si potrebbe provare simulated annealing, che è stato utilizzato con successo per problemi di ottimizzazione complessi in un certo numero di domini. Fondamentalmente si fa un'escursione in salita casuale mentre si riduce gradualmente la casualità. Dato che hai già il punteggio Aho-Corasick hai già fatto la maggior parte del lavoro. Tutto ciò di cui hai bisogno è un modo per generare permutazioni dei vicini; per questo qualcosa di semplice come scambiare un paio di lettere dovrebbe funzionare bene.

Answer 2

Hai mai pensato di utilizzare un algoritmo genetico? Hai già l'inizio della tua funzione fitness. Potresti sperimentare con gli algoritmi di mutazione e crossover (grazie Nathan) per vedere quale fare il lavoro migliore.

Un'altra opzione potrebbe essere che l'algoritmo generi la parola più piccola possibile dal set di input e quindi aggiunga una lettera alla volta in modo che anche la nuova parola sia o contenga una nuova parola. Inizia con alcune parole di partenza diverse per ogni set di input e guarda dove conduce.

Solo pochi pensieri oziosi.

Answer 3

Potrebbe essere utile per verificare come gli altri hanno risolto questo: http://sourceforge.net/search/?type_of_search=soft&words=anagram

In questa pagina è possibile generare anagrammi on-line. Ci ho giocato per un po 'ed è molto divertente.Non spiega in dettaglio come funziona il suo lavoro, ma i parametri forniscono alcune informazioni. http://wordsmith.org/anagram/advanced.html

Answer 4

Ecco un'idea, ispirato da Markov Chains:

1. Precompute la lettera probabilità di transizione nel dizionario. Crea una tabella con la probabilità che una lettera X sia seguita da un'altra lettera Y, per tutte le coppie di lettere, in base alle parole nel dizionario.
2. Generare permutazioni scegliendo casualmente ogni successiva lettera dal rimanente gruppo di lettere, in base alla lettera precedente e alla tabella delle probabilità, fino a quando tutte le lettere sono esaurite. Esegui questo molte volte.
3. Puoi sperimentare aumentando la "memoria" della tua tabella di transizione, non guardare indietro di una sola lettera, ma dire 2 o 3. Questo aumenta la tabella delle probabilità, ma ti dà più possibilità di creare una parola valida.