有人知道使用动态规划进行分词的示例算法吗？

Question

Closed. This question is seeking recommendations for software libraries, tutorials, tools, books, or other off-site resources. It does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

我们不允许提出寻求软件库、教程、工具、书籍或其他场外资源推荐的问题。您可以编辑问题，以便用事实和引文来回答。

5 年前已关闭。

Answer 1

我假设我们在这里讨论的不是微不足道的情况（即不仅仅是在空格周围分割字符串，因为这只是一个基本的分词器问题） - 相反，我们正在讨论那里的一些东西不是一个明确的单词分隔符，因此我们必须“猜测” string->words 的最佳匹配是什么 - 例如，一组没有空格的串联单词的情况，例如将其转换

lotsofwordstogether

为

lots, of, words, together

：在这种情况下，动态编程方法可能会计算出一个表，其中一个维度对应于序列中的第 M 个单词，另一个维度对应于每个 <输入字符串中的第 n 个字符。那么您为表中每个方格填写的值就是“如果我们在位置 NM 个单词，我们可以获得的最佳匹配分数代码>.

Answer 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

注意如何< code>memo 缓存对 search 的调用，而 search 又从 candidates 中选择最大值。

Answer 3

这是迭代风格的以下解决方案（主要思想是将问题分解为：在输入的特定范围内找到恰好具有 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();
}