Come suddividere un dato testo in parole dal dizionario?

Question

Questa è una domanda di intervista. Supponiamo che tu abbia una stringa text e una dictionary (un insieme di stringhe). Come si suddivide text in sottostringhe in modo tale che ciascuna sottostringa venga trovata in dictionary.

Ad esempio, è possibile suddividere "thisisatext" in ["this", "is", "a", "text"] utilizzando /usr/share/dict/words.

Credo che backtracking può risolvere questo problema (in pseudo-Java):

 
void solve(String s, Set<String> dict, List<String> solution) { 
    if (s.length == 0) 
     return 
    for each prefix of s found in dict 
     solve(s without prefix, dict, solution + prefix) 
} 

List<String> solution = new List<String>() 
solve(text, dict, solution) 

Ha senso? Ottimizzeresti la fase di ricerca dei prefissi nel dizionario? Quali strutture dati consiglieresti?

Answer 1

Questa soluzione presuppone l'esistenza della struttura dati Trie per il dizionario. Inoltre, per ogni nodo in Trie, si presuppone le seguenti funzioni:

1. nodo.IsWord(): restituisce vero se il percorso di quel nodo è una parola
2. node.IsChild (char x): Restituisce true se esiste un bambino con l'etichetta x
3. node.GetChild (char x): Restituisce il bambino nodo con l'etichetta x

Function annotate(String str, int start, int end, int root[], TrieNode node): 
i = start 
while i<=end: 
    if node.IsChild (str[i]): 
     node = node.GetChild(str[i]) 
     if node.IsWord(): 
      root[i+1] = start 
     i+=1 
    else: 
     break; 

end = len(str)-1 
root = [-1 for i in range(len(str)+1)] 
for start= 0:end: 
    if start = 0 or root[start]>=0: 
     annotate(str, start, end, root, trieRoot) 

index 0 1 2 3 4 5 6 7 8 9 10 11 
str: t h i s i s a t e x t 
root: -1 -1 -1 -1 0 -1 4 6 -1 6 -1 7 

mi lascerà la parte per di elencare le parole che compongono la stringa inversa attraversando la radice.

La complessità del tempo è O (nk) dove n è la lunghezza della stringa e k è la lunghezza della parola più lunga nel dizionario.

PS: Sto assumendo le seguenti parole nel dizionario: questo è, a, testo, mangiato.

Answer 2

Approccio 1- Trie sembra essere molto vicino qui. Genera il trie delle parole nel dizionario inglese. Questo trie building costa una volta. Dopo aver creato trie, il tuo string può essere facilmente confrontato lettera per lettera. se in qualsiasi momento incontri una foglia nel trie puoi presupporre di aver trovato una parola, aggiungila a una lista & vai avanti con la tua traversata. Esegui l'attraversamento finché non hai raggiunto la fine del tuo string. L'elenco viene emesso.

Complessità del tempo per la ricerca - O (lunghezza word).

Complessità dello spazio - O (dimensione * lunghezza_le parole * nessuna_ parole). Dimensione del tuo dizionario

Approccio 2 - Ho sentito parlare di Suffix Trees, non li ho mai usati ma potrebbe essere utile qui.

Approccio 3 - è più pedante & un'alternativa pessima. lo hai già suggerito.

Si potrebbe provare il contrario. Corri attraverso il dict è verificare la corrispondenza sub-stringa. Qui presumo che le chiavi in ​​dict siano words del dizionario inglese /usr/share/dict/words. Quindi il codice pseudo simile a questa -

(list) splitIntoWords(String str, dict d) 
{ 
    words = [] 
    for (word in d) 
    { 
     if word in str 
      words.append(word); 
    } 
    return words; 
} 

Complessità - O (n) che attraversa tutta la dict + O (1) per la corrispondenza di sottostringa.

Space - caso peggiore O (n) se len(words) == len(dict)

Come altri hanno fatto notare, questo richiede backtracking.

Answer 3

C'è un interessante resoconto molto accurato per la soluzione a questo problema in questo blog post.

L'idea di base è solo quello di Memoize la funzione che hai scritto e avrete un O (n^2) tempo, O (n) algoritmo spaziale.

Answer 4

È possibile risolvere questo problema utilizzando Dynamic Programming e Hashing.

Calcolare l'hash di ogni parola nel dizionario. Usa la funzione di hash che ti piace di più. Vorrei usare qualcosa come (a1 * B^(n - 1) + a2 * B^(n - 2) + ... + an * B^0)% P, dove a1a2 ... an è una stringa, n è la lunghezza della stringa, B è la base del polinomio e P è un numero primo grande. Se si ha il valore hash di una stringa a1a2 ... a è possibile calcolare il valore hash della stringa a1a2 ... ana (n + 1) in tempo costante: (hashValue (a1a2 ... an) * B + a (n + 1))% P.

La complessità di questa parte è O (N * M), dove N è il numero di parole nel dizionario e M è la lunghezza della parola più lunga nel dizionario.

Poi, utilizzare una funzione DP come questo:

bool vis[LENGHT_OF_STRING]; 
    bool go(char str[], int length, int position) 
    { 
     int i; 

     // You found a set of words that can solve your task. 
     if (position == length) { 
      return true; 
     } 

     // You already have visited this position. You haven't had luck before, and obviously you won't have luck this time. 
     if (vis[position]) { 
     return false; 
     } 
     // Mark this position as visited. 
     vis[position] = true; 

     // A possible improvement is to stop this loop when the length of substring(position, i) is greater than the length of the longest word in the dictionary. 
     for (i = position; position < length; i++) { 
     // Calculate the hash value of the substring str(position, i); 
     if (hashValue is in dict) { 
      // You can partition the substring str(i + 1, length) in a set of words in the dictionary. 
      if (go(i + 1)) { 
       // Use the corresponding word for hashValue in the given position and return true because you found a partition for the substring str(position, length). 
       return true; 
      } 
     } 
     } 

     return false; 
    } 

La complessità di questo algoritmo è O (N * M), dove N è la lunghezza della stringa e M è la lunghezza della parola più lunga nel dizionario o O (N^2), a seconda che tu abbia codificato il miglioramento o meno.

Quindi la complessità totale dell'algoritmo sarà: O (N1 * M) + O (N2 * M) (o O (N2^2)), dove N1 è il numero di parole nel dizionario, M è la lunghezza della parola più lunga nel dizionario e N2 è la lunghezza della stringa).

Se non è possibile pensare ad una bella funzione di hash (dove non ce ne sono di collisione), altra soluzione possibile è quella di utilizzare Tentativi o un trie Patricia (se la dimensione del trie normale è molto grande) (non potevo link per questi argomenti perché la mia reputazione non è abbastanza alta per pubblicare più di 2 link). Ma in questo modo, la complessità del tuo algoritmo sarà O (N * M) * O (tempo necessario per trovare una parola nel trie), dove N è la lunghezza della stringa e M è la lunghezza della parola più lunga nel dizionario

Spero che sia d'aiuto, e mi scuso per il mio povero inglese.