我在 Go 中实现了一个简约的非循环有限状态自动机（MA-FSA；一种特定类型的 DAG），并希望将一些额外的数据与指示 EOW（词尾）的节点相关联。使用 MA-FSA，传统方法是不可能的，因为有多个单词可能以该节点结尾。所以我正在寻找最小的完美散列函数作为替代方案。
在他博客文章顶部的“更正”框中，Steve Hanov说他使用了Lucchesi 和 Kowaltowski 在这篇论文中描述的方法。在查看图 12（第 19 页）时，它描述了散列函数。
在第 8 行，它指的是FirstLetterand Predecessor()，但它没有描述它们是什么。或者我没看到。这些是什么？
我所能弄清楚的是它只是遍历树，Number从每个节点开始累加，但这不可能是正确的。它产生的数字太大而且不是一对一的，就像论文说的那样。我误读了什么吗？
论文说：
让我们假设我们的自动机的表示包括，对于每个状态，一个整数，它给出了自动机将从该状态开始接受的单词数。
所以我相信这一点：for C <- FirstLetter to Predecessor(Word[I ]) do
方法：for (c = 'a'; c < word[i]; c++)
（他们只是想独立于字母表。）
可以这样想：枚举所有接受的单词。对它们进行排序。在列表中找到您的单词。它的索引是单词的哈希值。
他们的算法通过跟踪从给定节点可以到达的单词数量来避免存储完整列表。因此，您到达一个节点，并在下一个字母之前检查到其他节点的所有传出边，这些边缘涉及字母表中的一个字母。从这些节点可到达的所有单词都必须在您的单词之前的列表中，因此您可以计算您的单词必须在列表中占据什么位置。
我更新了我的 DAWG 示例，以显示将其用作从键到值的映射。每个节点存储可以从它（包括它自己）到达的最终节点的数量。然后，当遍历 trie 时，我们将跳过的任何计数相加。这样，trie 中的每个单词都有一个唯一的编号。然后，您可以在数组中查找数字以获取与该单词关联的数据。