Dividere la stringa in parole

Question

Sto cercando l'algoritmo più efficiente per formare tutte le possibili combinazioni di parole da una stringa. Ad esempio:

Input String: forevercarrot 

Output: 

forever carrot 
forever car rot 
for ever carrot 
for ever car rot 

(Tutte le parole devono provenire da un dizionario).

Posso pensare ad un approccio a forza bruta. (trova tutte le sottostringhe possibili e corrisponde) ma quali sarebbero i modi migliori?

Answer 1

Un'implementazione di psuedocode, sfruttando il fatto che ogni parte della stringa deve essere una parola, non possiamo saltare nulla. Lavoriamo in avanti dall'inizio della stringa fino a quando il primo bit è una parola, e quindi generiamo tutte le possibili combinazioni del resto della stringa. Una volta che lo abbiamo fatto, continuiamo ad andare avanti finché non troviamo altre possibilità per la prima parola, e così via.

allPossibleWords(string s, int startPosition) { 
    list ret 
    for i in startPosition..s'length 
     if isWord(s[startPosition, i]) 
      ret += s[startPostion, i] * allPossibleWords(s, i) 
    return ret  
} 

lo spauracchio in questo codice è che si finirà per ripetere i calcoli - nel tuo esempio, si finirà per dover calcolare allPossibleWords("carrot") due volte - una volta nel ["forever", allPossibleWords["carrot"]] e una volta in ["for", "ever", allPossibleWords["carrot"]]. Quindi ricordare questo è qualcosa da considerare.

Answer 2

Utilizzare un prefix tree per l'elenco di parole conosciute. Probabilmente le librerie come myspell lo fanno già. Prova a usare uno pronto.

Una volta trovata una corrispondenza (ad esempio "auto"), dividi il tuo calcolo: un ramo inizia a cercare una nuova parola ("rot"), un altro continua ad esplorare le varianti dell'inizio corrente ("carota").

Effettivamente si mantiene una coda di coppie (start_position, current_position) di offset nella stringa ogni volta che si divide il calcolo. Diversi thread possono uscire da questa coda in parallelo e provare a continuare una parola che inizia da start_position ed è già nota fino a current_position della coppia, ma non finisce qui. Quando viene trovata una parola, viene segnalata e un'altra coppia viene estratta dalla coda. Quando è impossibile, non viene generato alcun risultato. Quando si verifica una divisione, una nuova coppia viene aggiunta alla fine della coda. Inizialmente la coda contiene (0,0).

Answer 3

Vedere questa domanda che ha risposte ancora migliori. Si tratta di uno standard di problema di programmazione dinamica:

How to split a string into words. Ex: "stringintowords" -> "String Into Words"?

Answer 4

stringa di input: forevercarrot

uscita:

sempre carota sempre auto rot per sempre la carota per sempre rot auto

programma :

#include<iostream> 
#include<string> 
#include<vector> 
#include<string.h> 
void strsplit(std::string str) 
{ 
    int len=0,i,x,y,j,k; 
    len = str.size(); 
    std::string s1,s2,s3,s4,s5,s6,s7; 
    char *c = new char[len+1](); 
    char *b = new char[len+1](); 
    char *d = new char[len+1](); 
    for(i =0 ;i< len-1;i++) 
    { 
     std::cout<<"\n"; 
     for(j=0;j<=i;j++) 
     { 
      c[j] = str[j]; 
      b[j] = str[j]; 
      s3 += c[j]; 
      y = j+1; 
     } 
     for(int h=i+1;h<len;h++){ 
      s5 += str[h]; 
     } 
     s6 = s3+" "+s5; 
     std::cout<<" "<<s6<<"\n"; 
     s5 = ""; 
     for(k = y;k<len-1;k++) 
     { 
      d[k] = str[k]; 
      s1 += d[k]; 
      s1 += " "; 
      for(int l = k+1;l<len;l++){ 
      b[l] = str[l]; 
      s2 += b[l]; 
     } 
     s4 = s3+" "+s1+s2; 
     s7 = s4; 
     std::cout<<" "<<s4<<"\n"; 
     s3 = "";s4 = ""; 
     } 
     s1 = "";s3 = ""; 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    std::string str; 
    if(argc < 2) 
       std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n"; 
    else{ 
       str = argv[1]; 
       strsplit(str); 
    } 

return 0; 
}