1

私は、スペースを含む単語の文字列が削除された DP 問題に取り組んでおり、文字列を個々の英語の単語に分割するために、ボタンアップとメモ化の両方のバージョンを実装する必要があります。ただし、ボタンアップバージョンを入手しましたが、メモ化は少し複雑なようです。 

 /* Split a string into individual english words
 * @String str the str to be splitted
 * @Return a sequence of words separated by space if successful,
     null otherwise
 */
public static String buttom_up_split(String str){
    int len = str.length();
    int[] S = new int[len+1];
    /*Stores all the valid strings*/
    String[] result = new String[len+1];  
    /*Initialize the array*/
    for(int i=0; i <= len; i++){
        S[i] = -1;
    }
    S[0] =0;
    for(int i=0; i < len; i++){
        if(S[i] != -1){
            for(int j= i+1; j <= len; j++){
                String sub = str.substring(i, j);
                int k = j;      
                if(isValidEnglishWord(sub)){
                    S[k] = 1; //set true indicates a valid split
                    /*Add space between words*/
                    if(result[i] != null){ 
                        /*Add the substring to the existing words*/
                        result[i+ sub.length()] = result[i] + " " + sub;
                    }
                    else{
                        /*The first word*/
                        result[i+ sub.length()] = sub;
                    }
                }

            }
        }
    }
    return result[len];  //return the last element of the array
}

この buttom_up_version をメモ化されたバージョンに変換する方法を本当に混乱させました。誰かが助けてくれることを願っています..

4

2 に答える 2

1

ええと、私はメモ化のエクスポートではありませんが、アイデアは、以前の良い英単語の「記憶」を持つことです. 目的は、計算時間を節約することです。あなたの場合、isValidEnglishWord() の呼び出しです。

したがって、次のようにアルゴリズムを適応させる必要があります。

  1. 「str」文字列をウォークスルーする
  2. そこから部分文字列を抽出する
  3. 部分文字列が記憶の中で有効な単語かどうかを確認してください。
    1. メモリ内にある: スペースと単語を結果に追加します。
    2. メモリ内にありません: isValidEnglishWord を呼び出し、その戻り値を処理します。

次のようなものが得られます（テストもコンパイルもされていません）

// This is our memory
import java.util.*

private static Map<String, Boolean> memory = new HashMap<String, Boolean>()

public static String buttom_up_split(String str){
   int len = str.length();
   int[] S = new int[len+1];

   String[] result = new String[len+1];  
   for(int i=0; i <= len; i++){
      S[i] = -1;
   }
   S[0] =0;
   for(int i=0; i < len; i++){
      if(S[i] != -1){
         for(int j= i+1; j <= len; j++){
            String sub = str.substring(i, j);
            int k = j;    

            // Order is significant: first look into memory !
            Boolean isInMemory = memory.contains(sub);
            if (isInMemory || isValidEnglishWord(sub)){
                S[k] = 1;
                if(result[i] != null){ 

                    // Memoize the result if needed.
                    if (!isInMemory) {
                        memory.put(sub, true);
                    }

                    result[i+ sub.length()] = result[i] + " " + sub;
                } else {
                    result[i+ sub.length()] = sub;
                }
            }

        }
    }
}
return result[len];

}

于 2012-06-02T07:54:11.877 に答える
0

個人的には、アルゴリズムを変更せずに、できるだけ透過的にメモ化を使用することを常に好みます。これは、メモ化とは別にアルゴリズムをテストできるようにしたいためです。また、メモ化が適用可能なメソッドに @Memoize を追加するだけでよいメモ化ライブラリに取り組んでいます。しかし残念ながら、これはあなたにとって遅すぎるでしょう。

最後に memoization を (ライブラリなしで) 使用したときは、プロキシ クラスを使用して実装しました。重要な注意点は、この実装は再帰をサポートしていないということです。ただし、アルゴリズムは再帰的ではないため、これは問題になりません。

その他の参考文献は次のとおりです。

アルゴリズムについてのコメント: 他の単語を含む単語をどのように処理しますか? 「verbose」には「verb」が含まれ、「theory」には「the」が含まれます。

于 2012-06-03T10:45:21.247 に答える