将域名拆分成单词（如果可能）？

Question

我想将一个域名分解成单词和数字，例如：

iamadomain11.com = ['i', 'am', 'a', 'domain', '11']

我该如何做？我知道可能会有多组可能性，但是目前只需要得到一组可能的结果。

- demos

---

['i','a','ma','do','ma','in','11'] - Ken Bloom

这听起来要么是NP-难问题，要么需要动态规划。我已经编辑了标签，以便让那些比我更擅长这些算法的人注意到它。 - Ken Bloom

谢谢Ken！希望有人回复。 - demos

上周已经有人问过这个问题并且得到了比你更好的答案：https://dev59.com/5nA75IYBdhLWcg3wH1JB - Ken Bloom

Answer 1

这个问题实际上在O'Reilly Media的书籍Beautiful Data中得到了解决。在第14章“自然语言语料库数据”中，作者使用一个巨大且免费可用的标记频率数据集，在Python中创建了一个分割器，可以完全按照您的要求进行操作。

- Thien

---

有一个 Python 模块 (http://www.grantjenks.com/docs/wordsegment/#)，它基于 Peter Norvig 在书籍《美丽的数据》中的章节“自然语言语料库数据”中的代码实现了分词。 - noleto

Answer 2

这是一个有趣的问题！首先，您需要一个字典。出于性能原因，将其存储在哈希集中（可能可以使用Python中的字典类型）。然后，您可以迭代每个可能的字符串（“i”，“ia”，“iam”...“n11”，“1”，“11”，“1”），并在字典中查找匹配项。然后，只需迭代这些匹配项，直到您获得一个没有重叠的连续集。

这将是一种快速而简单的方法。可能有更快的方法来解决这个问题。

- Evil Pigeon

---

这样做会过于不优化，所需时间将会非常长！ - demos

@demos：也许不适用于您试图拆分像典型域名那样小的字符串时。 - Ken Bloom

他的方法依赖于创建使用连续字母的所有可能的n-gram来表示特定单词。您是否了解某个大型英语词典的存在？ - demos

这肯定会有很高的计算成本。最好使用字典，因为启发式地处理这个问题将是一场噩梦。将单词存储在哈希集中可以使查找为O(1)。您也不必计算和存储每个n元组。您的实现可以按顺序匹配单词，然后在找不到解决方案时回滚。该过程可能如下所示："i"->"a"->"mad"->在 "omain11" 中未找到任何单词匹配，回滚。 "i"->"am"->"a"->"do"->"main"->"11" - Evil Pigeon

@demos：大多数UNIX系统都有/usr/share/dict/words（一个每行一个单词的纯文本文件），您可以将其用作字典。 - Ken Bloom

Answer 3

这听起来很像中文分词的问题，因为中文单词之间没有空格。以下段落摘自Manning、Raghavan和Schütze的《信息检索导论》，可在此处在线获取：

“这种现象在东亚主要语言（例如中文、日语、韩语和泰语）中达到了极限情况，其中文本没有任何单词之间的空格。[...]一种方法是进行词分割作为先前的语言处理。词分割的方法因具有大量词汇并采用最长词汇匹配与某些未知词汇的启发式方法相结合而异，也可以使用机器学习序列模型，例如隐马尔可夫模型或条件随机场，对手动分割的单词进行训练。”

我建议首先采用贪婪字典匹配，然后添加启发式方法来处理最常见的失败情况。

- Stompchicken