2

如果您在谷歌搜索分词,确实没有很好的描述,我只是想完全理解动态编程算法将字符串分割成单个单词的过程。有谁知道一个可以很好地描述分词问题的地方,或者任何人都可以描述它吗?

分词基本上只是获取一串字符并决定在哪里将其拆分为单词,如果您不知道并使用动态编程它会考虑到一些子问题。使用递归这很简单,但我无法在网上找到任何地方,甚至只是在网上找到一个迭代算法的描述,所以如果有人有任何例子或者可以给出一个很棒的算法。

谢谢你的帮助。

4

3 回答 3

2

我将假设我们在这里讨论的不是微不足道的情况(即不只是在空格周围分割字符串,因为那只是一个基本的标记器问题)——相反,我们谈论的是那里的东西不是一个明确的单词分隔符,因此我们不得不“猜测”字符串->单词的最佳匹配是什么 - 例如,一组不带空格的连接单词的情况,例如转换这个:

lotsofwordstogether

进入这个:

lots, of, words, together

在这种情况下,动态编程方法可能是计算出一个表格,其中一个维度对应M于序列中的第 th 个单词,而另一个维度对应N于输入字符串中的每个字符。M然后,您为表格的每个方格填写的值是“如果我们在 position 处结束(或者相反,开始)第 th 个单词,我们可以获得的最佳匹配分数N

于 2009-11-23T07:52:55.550 回答
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 回答
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 回答