Conteggio di parole inglesi in una stringa casuale

Question

Supponiamo di avere una stringa generata in modo casuale s=t&^%JHGgfdteam*&HGEdfg, qual è l'approccio migliore per contare il numero di parole inglesi in quella stringa? (Parole inglesi come definite in alcuni file di dizionario). Ovviamente la forza bruta non è una buona idea ... un suffisso-tri e funzionerebbe? Ricerca binaria? Si noti che nel caso di s, ci sono due parole: "tè" e "squadra". Qualche idea? Cordiali saluti

Answer 1

Vorrei caricare le parole del dizionario in una struttura Trie, quindi leggere la stringa da sinistra a destra e controllare se le sottostringhe sono nel trie. Se sono e ci sono bambini, continua. Se capita di essere una foglia o una parola valida, aggiungi al conteggio delle occorrenze.

In pseudo-codice:

Trie dict = ... // load dictionary 
Dictionary occurences = {} 

for i in length(string): 
    j = i + 1 
    # think of partial as string.Substring(i, j); 
    while dict.hasChildren(partial): 
     j++ 
     if isWord(partial): 
      dict[partial]++ 

In questo modo sarete garantisco che non perde un incontro, mentre ancora alla ricerca di tutte le possibilità.

è possibile limitare la lunghezza minima delle parole valide, modificando ciò che j viene inizializzato o rifiutando le parole brevi nel metodo isWord() (così a non sarebbe una parola "valido").

Answer 2

Il Aho-Corasick string matching algorithm crea la struttura di corrispondenza in tempo lineare nella dimensione del dizionario e corrisponde a modelli in tempo lineare nella dimensione del testo di input + numero di corrispondenze trovate.