2

Googleで単語のセグメンテーションを検索しても、それについての適切な説明は実際にはありません.動的プログラミングアルゴリズムが文字列のセグメンテーションを個々の単語に見つけるために必要なプロセスを完全に理解しようとしています. 単語のセグメンテーションの問題について適切に説明されている場所を知っている人はいますか、または説明できる人はいますか?

単語のセグメンテーションは、基本的に文字列を取得し、知らなかった場合に単語に分割する場所を決定するだけであり、動的プログラミングを使用すると、ある程度の副問題が考慮されます。これは再帰を使用して行うのは非常に簡単ですが、このオンラインの反復アルゴリズムの説明だけでもオンラインで見つけることができなかったので、誰かが例を持っているか、素晴らしいアルゴリズムを提供できれば.

助けてくれてありがとう。

4

3 に答える 3

2

Python の wordsegment モジュールには、そのようなアルゴリズムがあります。再帰とメモ化を使用して動的プログラミングを実装します。

ソースはGithubで入手できます。関連するスニペットは次のとおりです。

def segment(text):
    "Return a list of words that is the best segmenation of `text`."

    memo = dict()

    def search(text, prev='<s>'):
        if text == '':
            return 0.0, []

        def candidates():
            for prefix, suffix in divide(text):
                prefix_score = log10(score(prefix, prev))

                pair = (suffix, prefix)
                if pair not in memo:
                    memo[pair] = search(suffix, prefix)
                suffix_score, suffix_words = memo[pair]

                yield (prefix_score + suffix_score, [prefix] + suffix_words)

        return max(candidates())

    result_score, result_words = search(clean(text))

    return result_words

memoキャッシュがどのように呼び出しをキャッシュsearchし、次に から最大値を選択するかに注意してくださいcandidates。

于 2015-09-07T17:37:12.513 に答える
2

ここでは些細なケースについて話しているのではないと仮定します (つまり、スペースの周りで文字列を分割するだけではありません。これは、基本的なトークナイザーの問題にすぎないためです)。は明確な単語区切り文字ではないため、string->words の最適な一致を「推測」する必要があります。これ：

lotsofwordstogether

これに：

lots, of, words, together

この場合、動的プログラミングのアプローチはおそらく、1 つの次元Mがシーケンスの th 番目の単語に対応し、もう 1 つの次元Nが入力文字列の各 th 文字に対応するテーブルを計算することになります。次に、表の各正方形に入力する値は、「M位置 で th 番目の単語を終了 (または代わりに開始) した場合に取得できる最高の一致スコアNです。

于 2009-11-23T07:52:55.550 に答える
0

これが反復スタイルの次の解決策です（主なアイデアは、問題を次のように分割することです：入力の特定の範囲内で正確に1,2,3..n個のセグメント化された単語を持つセグメンテーションを見つけることです。インデックス作成の小さな間違いがあればすみません。最近、頭がぼんやりしています. しかし、これはあなたのための反復的な解決策です.):

static List<String> connectIter(List<String> tokens) {

    // use instead of array, the key is of the from 'int int'
    Map<String, List<String>> data = new HashMap<String, List<String>>();

    int n = tokens.size();

    for(int i = 0; i < n; i++) {
        String str = concat(tokens, i, n);
        if (dictContains(str)) {
            data.put(1 + " " + i, Collections.singletonList(str));
        }
    }

    for (int i = 2; i <= n; i++) {
        for (int start = 0; i < n; start++) {
            List<String> solutions = new ArrayList<String>();
            for (int end = start + 1; end <= n - i + 1; end++) {
                String firstPart = concat(tokens, start, end);

                if (dictContains(firstPart)) {
                    List<String> partialSolutions = data.get((i - 1) + " " + end);
                    if (partialSolutions != null) {
                        List<String> newSolutions = new ArrayList<>();
                        for (String onePartialSolution : partialSolutions) {
                            newSolutions.add(firstPart + " "
                                    + onePartialSolution);
                        }
                        solutions.addAll(newSolutions);
                    }
                }
            }

            if (solutions.size() != 0) {
                data.put(i + " " + start, solutions);
            }
        }
    }

    List<String> ret = new ArrayList<String>();
    for(int i = 1; i <= n; i++) { // can be optimized to run with less iterations
        List<String> solutions = data.get(i + " " + 0);
        if (solutions != null) {
            ret.addAll(solutions);
        }
    }

    return ret;
}


static private String concat(List<String> tokens, int low, int hi) {
    StringBuilder sb = new StringBuilder();
    for(int i = low; i < hi; i++) {
        sb.append(tokens.get(i));
    }
    return sb.toString();
}
于 2015-02-17T17:10:04.043 に答える