C++ - Come scoprire in modo efficiente se una stringa in un vettore può essere assemblata da una serie di lettere

Question

Sto implementando una versione testuale di Scrabble per un progetto universitario.

Ho un vettore contenente circa 400K stringhe (il mio dizionario) e, ad un certo punto in ogni turno, dovrò controllare lo se nel dizionario c'è ancora una parola che può essere formata con i pezzi nella mano del giocatore. Sto verificando se il giocatore ha qualche mossa a sinistra ... Se no, è game over per il giocatore in questione ...

La mia unica soluzione a questo è iterando attraverso la stringa, uno per uno, e usando una sub-routine Devo controllare se la stringa in questione può essere formata dai pezzi del giocatore. Implementerò un quickfail che verifica se l'utente ha vocali, ma sarà comunque dolorosamente inefficiente.

Il file di testo che contiene il dizionario è già ordinato alfabeticamente, quindi il vettore è ordinato.

Qualche suggerimento?

---

Un problema è stato presentato nei commenti seguenti: Qualche suggerimento su come prendo in considerazione le lettere già presenti sul tabellone?

Answer 1

Senza fornire alcun codice specifico (poiché questo è dopotutto compiti), un approccio generale da considerare è quello di mappa dalle lettere ordinate nella parola alle parole legali effettive.

Vale a dire, se il file dizionario aveva solo le parole ape, gum e mug, la struttura di dati sarà simile:

aep -> ape 
gmu -> gum, mug 

Poi si può semplicemente passare attraverso permutazioni delle lettere del giocatore, e identificare rapidamente se quella chiave esiste nella mappa.

Si paga un po 'di tempo di elaborazione impostando il dizionario all'avvio, ma in tal caso è sufficiente eseguire alcune ricerche rapide anziché scorrere l'elenco intero ogni volta.

Answer 2

È inoltre possibile memorizzare le stringhe con i caratteri ordinati in ordine ASCII in un set std ::, quindi ordinare le lettere del lettore nello stesso ordine e cercare la mappa per ciascuna sottostringa delle lettere del giocatore.

Answer 3

Come su come mantenere le coppie {parola dal dizionario, stringa costituita dalle stesse lettere, ma in ordine crescente (ordinato)}

quindi ordinare il vettore di quelle coppie basate sulla seconda corda e confrontare con ricerca binaria con una stringa composta da lettere ordinate dalla mano dei giocatori.

Answer 4

suona come una variante del problema sottoinsieme somma: http://en.wikipedia.org/wiki/Subset_sum_problem

Forse alcuni degli algoritmi descritti vi aiutano.

Answer 5

Ci sono stati numerosi documenti e domande su Scrabble su questo sito.

Ci sono anche molte strategie disponibili.

La rappresentazione del tuo dizionario è inadeguata, ci sono molti metodi intelligenti disponibili.Ad esempio, controlla che cos'è un Trie su wikipedia.

Utilizzando questo è possibile implementare un algoritmo di backtracking per determinare rapidamente quali parole è possibile formare.

{'as', 'ape', 'gum'} 

Trie: 

void -a-> (n) -p-> (n) -e-> (y) 
       -s-> (y) 
    -g-> (n) -u-> (n) -m-> (y) 

Dove "n" significa che non forma una parola e y significa che lo fa.

Ora, devi solo camminare sul Trie, tenendo presente quali lettere sono disponibili.

Diciamo che si dispone di { 'a', 'p', 'g', 'm', 'u'}:

1. I have a 'a' (but 'a' is not a word) 
2. I have a 'p' (but 'ap' is not a word) 
3. I don't have any 'e' so I can't go further, let's backtrack 
4. I don't have any 's' so... 
5. I have a 'g', but it's not a word 
6. I have a 'u', but 'gu' is not a word 
7. I have a 'm' and 'gum' is a word, I store it somewhere, I can't go further 

Il punto è quello di mantenere un insieme delle lettere a disposizione, quando prendi il ramo -a->, rimuovi 'a' da questo set, quindi quando prendi -a-> al contrario (mentre fai il backtracking) lo aggiungi nuovamente nel set.

• Questa struttura è molto più efficiente dello spazio, in realtà modelli un Finite Automaton che riconoscono la lingua del dizionario invece di salvare ciecamente tutte le parole
• Il runtime dovrebbe essere molto più veloce pure, dal momento che non avrete mai andare in profondità nella struttura ad albero (avete solo 7 lettere disponibili)
• non è certo cosa farei, in quanto non tiene la scheda in considerazione: p

'' lettere significa che si può prendere uno dei rami disponibili. Non è necessario utilizzare uno spazio vuoto se si dispone della lettera richiesta.

Answer 6

Ci sono alcune buone risposte già qui, e penso che un trie è probabilmente il modo giusto per andare, ma questo è un problema interessante quindi mi lancio in pena i miei due centesimi ...

Il l'approccio ingenuo sarebbe quello di generare tutte le permutazioni delle lettere disponibili e di tutti i sottoinsiemi distinti, quindi cercare ogni parola potenziale nel dizionario. Il problema è che, anche se non è difficile farlo, c'è un numero sorprendentemente alto di parole potenziali e la maggior parte di esse non è valida.

Sul lato positivo, la verifica del dizionario può essere velocizzata con una ricerca binaria o qualcosa di simile. Sul lato negativo, lo faresti così tante volte che il programma si fermerebbe per lunghe liste di lettere.

Abbiamo sicuramente bisogno di pre-elaborazione il dizionario per renderlo più utile, e cosa abbiamo veramente bisogno è di avere un modo per escludere rapidamente la maggior parte dei potenziali partner, anche se il metodo ha occasionali falsi positivi.

Un modo per farlo sarebbe quello di rappresentare quali lettere utilizza una parola in una mappa bit. In altre parole, precalcolo di un numero a 32 bit per ogni parola nel dizionario, in cui ogni bit viene impostato se la parola corrispondente dell'alfabeto viene utilizzata nella parola almeno una volta. Questo ti permetterebbe di trovare tutte le potenziali parole facendo una scansione lineare del dizionario e mantenendo solo quelle che usano solo le lettere che hai a disposizione. Sospetto che, con un po 'di intelligenza e indicizzazione, tu possa fare meglio di lineare.

Tra i candidati, alcuni richiedono più istanze di una lettera di quelle disponibili, quindi saranno falsi positivi. Ciò significa che devi eseguire un controllo finale su tutti i candidati che hai generato per eliminare i quasi-hit. Ci sono molti modi per farlo, ma uno dei più semplici è quello di passare attraverso la tua lista di lettere e sostituire la prima occorrenza di quella lettera nella parola potenziale con un trattino.Quando hai finito, se la parola potenziale ha qualcosa a parte i trattini, è un fallimento. Una soluzione più elegante, sebbene non necessariamente più veloce, sarebbe quella di generare una serie di frequenze di lettere e confrontarle.

Ancora una volta, penso che i tentativi siano probabilmente la strada da percorrere, ma spero che queste idee ti siano utili.

modificare

Permettetemi di buttare fuori un esempio di come si potrebbe fare meglio di una ricerca lineare completo sulla ricerca iniziale: usa la radice. Mantieni un semplice indice che ti consente di cercare la prima parola che inizia con una determinata lettera. Quindi, quando fai la ricerca, salta su tutte le parole che iniziano con una lettera che non hai. Questa non è una gigantesca accelerazione, ma è un miglioramento.