文字列を単語に分割する

Question

文字列から可能なすべての単語の組み合わせを形成する最も効率的なアルゴリズムを探しています。たとえば、

Input String: forevercarrot 

Output: 

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

（すべての単語は辞書からのものです）。

私はブルートフォースアプローチを考えることができます。 （可能なすべての部分文字列を見つけて一致させる）が、より良い方法は何でしょうか？

Answer 1

擬似コードの実装では、文字列のすべての部分を単語にする必要があるという事実を利用して、何もスキップすることはできません。文字列の先頭から最初のビットが単語になるまで作業を進め、文字列の残りのすべての可能な組み合わせを生成します。私たちがそれをしたら、最初の言葉のために他の可能性が見つかるまで続けます。 ["for", "ever", allPossibleWords["carrot"]]に一度["forever", allPossibleWords["carrot"]]に一度と - あなたの例では、あなたが二回allPossibleWords("carrot")を計算する必要が終わるだろう -

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  
} 

このコードでの変化は、あなたが、計算を繰り返す羽目になるということです。だからこれをメモすることは何かを考えることです。

Answer 2

知られている単語のリストにはprefix treeを使用してください。おそらくmyspellのようなlibsはすでにそうしています。既製品を使用してみてください。

マッチ（例： 'car'）を見つけたら、計算を分割します.1つのブランチが新しい単語（ '腐敗'）を探し始め、別のブランチは現在の先頭（ 'ニンジン'）のバリエーションを探し続けます。

計算を分割するたびに、文字列にオフセットのペア(start_position, current_position)のキューを効果的に維持します。いくつかのスレッドがこのキューから並行してポップアップし、start_positionから始まり、すでにcurrent_positionまで知られていますが、そこで終わらない単語を続行しようとします。単語が見つかると、それが報告され、別のペアがキューからポップされます。それが不可能な場合、結果は生成されません。分割が発生すると、新しいペアがキューの末尾に追加されます。最初にキューには(0,0)が含まれています。

Answer 3

さらに詳しい回答があるこの質問を参照してください。これは、標準の動的なプログラミングの問題です：

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

Answer 4

入力文字列：これまでの車の腐敗のために、これまでニンジン のための永遠の車の腐敗

永遠ニンジン

プログラム：

出力forevercarrot ：

#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; 
}