PHP字典类？或替代？

Question

基本上，我正在寻找的是在 PHP 中实现字典的某种类或方法。例如，如果我正在构建一个单词解码器——假设我使用了字母“a、e、l、p、p”。排列的可能性是巨大的——我如何只显示那些实际的单词(苹果、苍白等)？

谢谢!

Answer 1

经典的单词查找问题可以使用 Trie 有效地解决.

我会建议从 WordNet 中找到一个单词列表，将其存储在 Trie 中，然后对可能的词执行快速查找。

解决方案的形式是:

1. 加载单词列表
2. 将单词列表存储在一个 trie 中
3. 接受要解读的单词的输入

4. 尝试排列 i=1..N

   一个。查找排列我使用 trie

   如果有阳性结果，将其保存以供展示

   迭代(i++)

5. 从 3 开始重复。

编辑:

这里的旁注是对于任何长度为 N 的字符单词可能有 N!需要查找(对于 7 个字符，即 5040)。您应该考虑对 trie 查找算法进行一些优化。例如，您可以通过尽早排除无效子字符串而不是重复结束排列来获得显着的效率。

例如给定单词 apple，如果您选择“ppl”作为前三个字符的排列，则不会找到任何单词。所以，无论你如何排列最后的 a 和 e，你都无法构造一个单词。提前终止排列可能对您的算法效率很重要。