動的プログラミングを使用して文字列を有効な単語の文字列に分割します

Question

この問題を解決するには、動的プログラミングアルゴリズムを見つける必要があります。私は試しましたが、それを理解できませんでした。

あなたはn文字の文字列s [1 ... n]が与えられます。これは、句読点がすべて消えている破損したテキスト文書と思われます（itwasthebestoftimesのように見えるようになります）。 ... "）。任意の文字列wに対してdict（w）が有効な単語であれば値1を持ち、値が0であるようなブール関数dict（*）の形で利用可能な辞書を使って文書を再構築したいさもないと。

1. 文字列s [*]を一連の有効な単語として再構成できるかどうかを決定する動的プログラミングアルゴリズムを提供します。 dictへの各呼び出しに単位時間がかかると仮定して、実行時間は最大でもO（n^2）にする必要があります。
2. 文字列が有効な場合は、アルゴリズムが対応する単語列を出力するようにします。

Answer 1

文字列s []は複数の方法に分割される可能性があります。以下の方法は、s []を分割できる単語の最大数を見つけます。以下のアルゴリズム

bestScore [I]のスケッチ/擬似コードである - >最初のi文字を分割することができる単語の最大数（それ以外MINUS_INFINITYあろう）

for (i = 1 to n){ 
    bestScore[i] = MINUS_INFINITY 
    for (k = 1 to i-1){ 
     bestScore[i] = Max(bestSCore[i], bestScore[i-k]+ f(i,k)) 
    } 
} 

Fを格納し

f(i,k) = 1 : if s[i-k+1 to i] is in dictionary 
     = MINUS_INFINITY : otherwise 

bestScore [n]は[]に分割することができる。■た単語の最大数（値がMINUS_INFINIYである場合、S []に分割することができない）

を格納することになる：（I、K）は次のように定義され

明らかに実行時間はO（n^2）です

これは教科書のように見えますが、実際の分割位置を再構成するコードは書きません。

Answer 2

あなたのコンパクト化文書ことN.

レッツのB（n個）の長さは、ブールとする：真の文書が位置からn個の文書で始まる単語に分割することができます。

b（N）が真（空文字列は0ワードに分割できるので）です。 文字N-k-1から始まるすべての単語を考慮してb（N-k-1）を構成すると、b（N）、b（N-1）、... bそのような単語wがb（N - k - 1 + len（w））に設定されている場合、b（N - k - 1）をtrueに設定します。そのような単語がない場合は、b（N - k - 1）をfalseに設定します。

最後に、文書全体を単語に分割できるかどうかを示すb（0）を計算します。

擬似コードで

：あなたので、

def try_to_split(doc): 
    N = len(doc) 
    b = [False] * (N + 1) 
    b[N] = True 
    for i in range(N - 1, -1, -1): 
    for word starting at position i: 
     if b[i + len(word)]: 
     b[i] = True 
     break 
    return b 

はあなたが効率的「位置私はで始まる単語」を得るために行うことができますいくつかのトリックがありますが、あなたはO（N^2）のアルゴリズムを求めています辞書からiで始まるすべての文字列を検索できます。

ワードを生成するために、あなたは良い言葉を保存するために、上記のアルゴリズムを変更したり、ちょうどこのようにそれを生成することができ、次のいずれか

def generate_words(doc, b, idx=0): 
    length = 1 
    while true: 
    assert b(idx) 
    if idx == len(doc): return 
    word = doc[idx: idx + length] 
    if word in dictionary and b(idx + length): 
     output(word) 
     idx += length 
     length = 1 

ここでBは、アルゴリズムの最初の部分から生成されたboolean型の配列であります。

Answer 3

O(N^2) Dpは明らかですが、辞書の言葉が分かっていれば、O(N)でそれをもっと早く得るためにいくつかの事前計算を使うことができると思います。 Aho-Corasick

Answer 4

のC++でのDPソリューション：

int main() 
{ 
    set<string> dict; 
    dict.insert("12"); 
    dict.insert("123"); 
    dict.insert("234"); 
    dict.insert("12345"); 
    dict.insert("456"); 
    dict.insert("1234"); 
    dict.insert("567"); 
    dict.insert("123342"); 
    dict.insert("42"); 
    dict.insert("245436564"); 
    dict.insert("12334"); 

    string str = "123456712334245436564"; 

    int size = str.size(); 
    vector<int> dp(size+1, -1); 
    dp[0] = 0; 
    vector<string > res(size+1); 
    for(int i = 0; i < size; ++i) 
    { 
     if(dp[i] != -1) 
     { 
      for(int j = i+1; j <= size; ++j) 
      { 
       const int len = j-i; 
       string substr = str.substr(i, len); 
       if(dict.find(substr) != dict.end()) 
       { 
        string space = i?" ":""; 
        res[i+len] = res[i] + space + substr; 
        dp[i+len] = dp[i]+1; 
       } 
      } 
     } 
    } 
    cout << *dp.rbegin() << endl; 
    cout << *res.rbegin() << endl; 

    return 0; 
} 

Answer 5

を@MinhPhamが提案どのような形式化。

これはダイナミックプログラミングソリューションです。文字列strを考える

、聞かせて

B [i]は=真のサブストリングのstr [0 ... i]は（包括的）に有効な単語に分割することができます。

空白の単語を表すために、いくつかの開始文字をstrに前置します（例：！）。 str = "！" + STR

ベース場合は、空の文字列、そう

B [0] =真です。反復場合について

：

B [j]はB場合はtrue = [I] == trueおよびSTR [i..j]は全てのi < J

ための単語であります

Answer 6

以下はこの問題のO（n^2）解決策です。

void findstringvalid() { 
string s = "itwasthebestoftimes"; 
set<string> dict; 
dict.insert("it"); 
dict.insert("was"); 
dict.insert("the"); 
dict.insert("best"); 
dict.insert("of"); 
dict.insert("times"); 

vector<bool> b(s.size() + 1, false); 
vector<int> spacepos(s.size(), -1); 
//Initialization phase 
b[0] = true; //String of size 0 is always a valid string 
for (int i = 1; i <= s.size(); i++) { 
    for (int j = 0; j <i; j++) { 
     //string of size s[ j... i] 
     if (!b[i]) { 
      if (b[j]) { 
       //check if string "j to i" is in dictionary 
       string temp = s.substr(j, i - j); 
       set<string>::iterator it = dict.find(temp); 
       if (it != dict.end()) { 
        b[i] = true; 
        spacepos[i-1] = j; 
       } 
      } 
     } 
    } 
} 
if(b[s.size()]) 
    for (int i = 1; i < spacepos.size(); i++) { 
     if (spacepos[i] != -1) { 
      string temp = s.substr(spacepos[i], i - spacepos[i] + 1); 
      cout << temp << " "; 
    } 
    } 
}