algorithm - 最好的字符串重建算法？ (最好在 'most accurate' 中)

Question

我一直在搜索和测试各种字符串重建算法，即将无空格文本重建为普通文本。

我的结果发布在这里 Solution working partially in Ruby ，正在90% 重建 2 或 3 个单词的句子，并使用完整的字典。但我无法让它运行得比这更好!

我认为我的算法灵感来自 dynamic programming很糟糕并且包含很多补丁工作。

您能否提出另一种算法(以伪代码的形式)，该算法可以万无一失地处理完整的字典？

Answer 1

您需要的不仅仅是字典，因为您可以从同一个无空格字符串中获得多个可能的短语。例如，“themessobig”可以是“the mess so big”或“themes so big”或“the mes so big”等。

这些都是有效的可能性，但有些可能性比其他可能性大得多。因此，您要做的是根据实际使用语言的方式选择最有可能的一种。为此，您需要一个庞大的文本语料库以及一些 NLP 算法。可能最简单的方法是计算一个词在另一个词之后出现的可能性。所以对于“这么大的困惑”，它可能是:

P(the | <START>) * P(mess | the) * P(so | mess) * P(big | so)

对于“主题如此之大”，可能性是:

P(themes | <START>) * P(so | themes) * P(big | so)

然后您可以选择最有可能的可能性。您还可以构造三元组而不是元组(例如 P(so | the + mess))，这需要更大的语料库才能有效。

这并非万无一失，但您可以通过使用更好的语料库或调整算法来做得越来越好。