如果您在谷歌搜索分词,确实没有很好的描述,我只是想完全理解动态编程算法将字符串分割成单个单词的过程。有谁知道一个可以很好地描述分词问题的地方,或者任何人都可以描述它吗?
分词基本上只是获取一串字符并决定在哪里将其拆分为单词,如果您不知道并使用动态编程它会考虑到一些子问题。使用递归这很简单,但我无法在网上找到任何地方,甚至只是在网上找到一个迭代算法的描述,所以如果有人有任何例子或者可以给出一个很棒的算法。
谢谢你的帮助。
如果您在谷歌搜索分词,确实没有很好的描述,我只是想完全理解动态编程算法将字符串分割成单个单词的过程。有谁知道一个可以很好地描述分词问题的地方,或者任何人都可以描述它吗?
分词基本上只是获取一串字符并决定在哪里将其拆分为单词,如果您不知道并使用动态编程它会考虑到一些子问题。使用递归这很简单,但我无法在网上找到任何地方,甚至只是在网上找到一个迭代算法的描述,所以如果有人有任何例子或者可以给出一个很棒的算法。
谢谢你的帮助。
我将假设我们在这里讨论的不是微不足道的情况(即不只是在空格周围分割字符串,因为那只是一个基本的标记器问题)——相反,我们谈论的是那里的东西不是一个明确的单词分隔符,因此我们不得不“猜测”字符串->单词的最佳匹配是什么 - 例如,一组不带空格的连接单词的情况,例如转换这个:
lotsofwordstogether
进入这个:
lots, of, words, together
在这种情况下,动态编程方法可能是计算出一个表格,其中一个维度对应M
于序列中的第 th 个单词,而另一个维度对应N
于输入字符串中的每个字符。M
然后,您为表格的每个方格填写的值是“如果我们在 position 处结束(或者相反,开始)第 th 个单词,我们可以获得的最佳匹配分数N
。
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
.
这是迭代风格的以下解决方案(主要思想是将问题分解为:在输入的一定范围内找到恰好具有 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();
}