21

この問題を解決するには、動的計画法のアルゴリズムを見つける必要があります。やってみましたがわかりませんでした。問題は次のとおりです。

n 文字の文字列 s[1...n] が与えられます。これは、すべての句読点が消えた破損したテキスト ドキュメントであると考えられます (そのため、「最高の時代だった...」のように見えます)。ブール関数 dict(*) の形式で利用可能な辞書を使用してドキュメントを再構築したい場合、任意の文字列 w に対して、w が有効な単語の場合は dict(w) の値は 1 になり、値は 0 になります。それ以外は。

  1. 文字列 s[*] を有効な単語のシーケンスとして再構成できるかどうかを決定する動的計画法アルゴリズムを与えてください。dict の各呼び出しに単位時間がかかると仮定すると、実行時間は最大で O(n^2) になります。
  2. 文字列が有効な場合は、アルゴリズムに対応する一連の単語を出力させます。
4

6 に答える 6

9

圧縮されたドキュメントの長さを N とします。

b(n) をブール値とします。ドキュメント内の位置 n から始まる単語にドキュメントを分割できる場合は true です。

b(N) は true です (空の文字列は 0 語に分割できるため)。b(N)、b(N - 1)、... b(N - k) が与えられた場合、文字 N - k - 1 で始まるすべての単語を考慮して、b(N - k - 1) を作成できます。 b(N - k - 1 + len(w)) が設定されたそのような単語 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

「位置 i から始まる単語」を効率的にするためにできるトリックがいくつかありますが、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 はアルゴリズムの最初の部分から生成されたブール配列です。

于 2011-03-15T11:39:37.240 に答える
6

@MinhPhamが提案したことを形式化する。

これは、動的プログラミング ソリューションです。

文字列 str が与えられると、

b[i] = 部分文字列 str[0...i] (両端を含む) を有効な単語に分割できる場合は true。

空の単語を表すために、str の先頭に ! などの開始文字を追加します。str = "!" + 筋

基本ケースは空の文字列なので、

b[0] = 真。

反復の場合:

b[i] == true で、str[i..j] がすべての i < j の単語である場合、b[j] = true

于 2013-07-03T19:12:17.283 に答える
1

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;
}
于 2011-03-15T12:27:22.847 に答える
1

O(N^2)Dp は明確ですが、辞書の単語を知っている場合は、いくつかの事前計算を使用して でさらに高速に取得できると思いますO(N)。 アホ・コラシック

于 2011-03-15T11:56:06.433 に答える
0

文字列 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(i,k) は次のように定義されます。

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

bestScore[n] は、s[] を分割できる単語の最大数を格納します (値が MINUS_INFINIY の場合、s[] は分割できません)。

明らかに実行時間は O(n^2) です

これは教科書的な演習のように見えるので、実際の分割位置を再構築するためのコードは書きません。

于 2011-03-15T11:35:30.290 に答える