如何将字符串拆分为单词.例如:"stringintowords" - >"String into Words"？

Question

将字符串拆分成单词的正确方法是什么？(字符串不包含任何空格或标点符号)

例如:"stringintowords" - >"String into Words"

你能告诉我这里应该使用什么算法吗？

!更新:对于那些认为这个问题仅仅是为了好奇的人.该算法可用于动态域名("sportandfishing .com" - >"SportAndFishing .com"),此算法目前由aboutus dot org用于动态执行此转换.

Answer 1

假设您有一个函数isWord(w),它w使用字典检查单词是否为单词.为简单起见,我们现在假设您只想知道是否可以进行某些分词w.这可以通过动态编程轻松完成.

让S[1..length(w)]与布尔条目的表格.S[i]如果单词w[1..i]可以拆分,则为true .然后设置S[1] = isWord(w[1])和for i=2到length(w)计算

S [i] =(isWord [w [1..i]或{2..i}中的任何j:S [j-1]和isWord [j..i]).

如果字典查询是恒定时间,则这需要O(长度(w)^ 2)时间.要实际找到分裂,只需将获胜分割存储在设置为true的每个S [i]中.这也可以适用于通过存储所有这样的分裂来枚举所有解决方案.

Answer 2

正如这里的许多人所提到的,这是一个标准的,简单的动态编程问题:最好的解决方案由FalkHüffner提供.其他信息:

(a)您应该考虑使用trie 实现isWord,如果您正确使用(通过逐步测试单词),这将为您节省大量时间.

(b)输入"分段动态编程"可以从大学级别的讲座中获得更详细的答案,如伪代码算法,例如杜克大学的讲座(甚至可以提供简单的概率方法来处理什么当你有任何字典中不包含的单词时要做的事情.

Answer 3

如果你想确保你做到这一点,你将不得不使用基于字典的方法,这将是极其低效的.您还必须期望从算法中获得多个结果.

例如:windowsteamblog(的http://windowsteamblog.com/名望)

Answer 4

关于这一点，学术文献中应该有很多。您要搜索的关键词是分词。例如，本文看起来很有希望。

通常，您可能需要学习markov模型和viterbi算法。后者是一种动态编程算法，可以使您找到字符串的合理分段，而无需详尽测试每个可能的分段。此处的基本见解是，如果对前m个字符有n个可能的细分，而您只想找到最可能的细分，则无需针对后续字符对每个细分进行评估-您只需要继续评估最可能的一个。