algorithm - 高效的拼词算法

Question

我正在寻找一种有效的算法来将一组字母打乱为包含最大单词数的排列。

例如，假设我得到了字母列表:{e, e, h, r, s, t}。我需要以包含最大字数的方式对它们进行排序。如果我将这些字母排序为“theres”，它包含单词“the”、“there”、“her”、“here”和“ere”。所以这个例子可能有 5 分，因为它包含 5 个单词。我想以得分最高(包含最多的单词)的方式对字母进行排序。

一个朴素的算法是尝试对每个排列进行评分。我相信这是 O(n!)，因此仅对上面的 6 个字母将尝试 720 种不同的排列(包括一些重复项，因为示例中有两次 e)。当然，对于更多的字母，天真的解决方案很快就变得不可能了。

该算法不必真正产生最佳解决方案，但它应该在合理的时间内找到一个好的解决方案。对于我的应用程序，简单地猜测 (Monte Carlo) 几百万个排列的效果很差，所以这是目前要超越的标准。

我目前正在使用 Aho-Corasick对排列进行评分的算法。它只需一次遍历文本即可搜索字典中的每个单词，因此我相信它非常高效。这也意味着我将所有单词存储在 trie 中。 ，但如果另一种算法需要不同的存储空间，那也没关系。我不担心设置字典，只担心实际排序和搜索的运行时间。如果需要，甚至可以使用模糊词典，例如 Bloom Filter。 .

对于我的应用程序，给定的字母列表大约有 100 个，字典包含超过 100,000 个条目。字典永远不会改变，但需要对几个不同的字母列表进行排序。

我正在考虑尝试 path finding algorithm .我相信我可以从列表中的随机字母开始。然后每个剩余的字母将被用来创建一个“路径”。我认为这将与 Aho-Corasick 评分算法一起使用，因为分数可以一次建立一个字母。不过，我还没有尝试过寻路；也许这不是一个好主意？我不知道哪种寻路算法可能是最好的。

我想到的另一种算法也是以随机字母开头。然后将在字典特里搜索包含剩余字母的“丰富”分支。包含不可用字母的词典分支将被修剪。我对这将如何工作的细节有点模糊，但它可以完全消除得分排列。

Answer 1

这是一个灵感来自 Markov Chains 的想法:

1. 预先计算字典中的字母转换概率。根据字典中的单词，针对所有字母对创建一个表，其中包含某个字母 X 后跟另一个字母 Y 的概率。
2. 根据前一个字母和概率表，通过从剩余字母池中随机选择每个下一个字母来生成排列，直到用完所有字母。运行多次。
3. 您可以通过增加转换表的“内存力”来进行试验 - 不要只回头看一个字母，而是说 2 个或 3 个。这会增加概率表，但会为您提供更多创建有效单词的机会。