algorithm - 查找字典单词

Question

我有很多复合字符串，它们是两个或三个英文单词的组合。

    e.g. "Spicejet" is a combination of the words "spice" and "jet"

我需要将这些单独的英文单词与此类复合字符串分开。我的字典将包含大约 100000 个单词。

我可以将单个英语单词与此类复合字符串分开的最有效方法是什么。

Answer 1

我不确定您需要多少时间或频率来执行此操作(是一次性操作吗？每天一次？每周一次？)但您显然需要快速、加权的字典查找。

您还需要一个冲突解决机制，也许是一个辅助队列，用于手动解决具有多种可能含义的元组的冲突。

我会调查 Tries .使用一个您可以有效地找到(并加权)您的前缀，这正是您要查找的内容。

您必须自己从良好的字典来源构建 Tries，并根据完整的单词对节点进行加权，以便为您自己提供优质的引用机制。

这里只是集思广益，但如果您知道您的数据集主要由二元组或三元组组成，您可能可以通过多次 Trie 查找来逃脱，例如查找“Spic”，然后查找“ejet”，然后发现两个结果都有一个低分，放弃进入“Spice”和“Jet”，这两种尝试都会在两者之间产生良好的综合结果。

此外，我会考虑对最常见的前缀进行频率分析，直至达到任意或动态限制，例如过滤“the”或“un”或“in”并相应地加权。

听起来是个有趣的问题，祝你好运!