从连续字符串中提取单词

Question

我有意见：

callme
senditnow
runningcar

我如何提取像给我打电话这样的词，现在发送，运行 car.Is python 中的任何图书馆都可以使用一些字典来做到这一点。

Answer 1

我不知道正确的做法，但有办法作弊！

这是我在大学时解决的一个算法练习题，你有一个没有空格的字符串（例如 thesearethereasons），你试图找回单词。

诀窍是试图将问题转化为图（有向无环图）：您需要一个函数来检查字典中是否存在单词（当时我使用 /usr/share/dict/words 解析为 grep），然后尝试所有单词组合。存储单词和 start/end 索引。

These (0,4)
The (0,2)
Sea (3,5)
[...]

然后您只需要通过在一个词的结尾和另一个词的开头之间建立链接，将它们变成一个图表：

*--+The----Sea-------(no more words there)
   |
   +-These---Are+----The+-------Reason (not end)
                |       +----Reasons [String end]   <== Solution
                |
                +----There---A---Sons [String end]  <== False Positive

现在你有了一个词图，跟着它（DFS）到最后就好了。任何以字符串结尾的路径都代表单词 =)

如您所想，几个单词组合就可以达到目的，返回一系列 "plausible sentences"。那不是一个完美的解决方案

Answer 2

Peter Norvig 在他的书的章节 Beautiful Data（Segaran 和 Hammerbacher，2009 年）中解决了这个问题。

Here 是有问题的章节。

你要做的是找到一个分段，使得每个词的概率乘积给出最高分。这样做可以避免产生非词（其概率应该接近于零），并且您可能会在可能的情况下选择正确的分割。

这是比使用图形方法更安全的方法，因为它会拒绝可能但不太可能的元素。

（如何分割"speedofart"或"expertsexchange"？）

简而言之，方法如下：

定义概率模型
列举可能的候选人
选择最有可能的分词

您定义一次模型，运行为您要分割的每个字符串执行第 2 步和第 3 步。步骤 2 和 3 运行复杂度为 O(n**2)，其中 n 是要分段的字符串的长度。

一切都在我给你的链接中得到了非常详细的解释，而且你还得到了 Python 代码来实现所有这些！

从连续字符串中提取单词

Extract words from continous strings

python

algorithm

text-mining

nltk