分享一种最小 Perfect Hash 生成算法

wuxiaosi0 2019-06-30

最近看到一篇有关 Perfect Hash 生成算法的文章,感觉很有必要写篇文章推荐下:
http://ilan.schnell-web.net/p...

先解释下什么是 Perfect Hash:Perfect Hash 是这样一种算法,可以映射给定 N 个 keys 到 N 个不同的的数字
里。由于没有 hash collision,这种 Hash 在查找时时间复杂度是真正的 O(1)。外加一个“最小”前缀,则是要
求生成的 Perfect Hash 映射结果的上界尽可能小。举个例子,假设我有 100 个字符串,如果存在这样的最小
Perfect Hash 算法,可以把 100 个字符串一一映射到 0 ~99 个数里,我就能用一个数组存储全部的字符串,然
后在查找时先 hash 一下,取 hash 结果作为下标便可知道给定字符串是否在这 100 个字符串里。总时间复杂度
O(n) 的 hash 过程 + O(1) 的查找,而所占用的空间只是一个数组(外加一个图 G,后面会讲到)。

听到前面的描述,你可能想到 trie (前缀树)和类似的 AC 自动机算法。不过讨论它们之间的优劣和应用场景不
是本文的主题(也许以后我有机会可以写一下)。本文的主题在于介绍一种生成最小 Perfect Hash 算法。

这种算法出自于一篇 1992 年的论文《An optimal algorithm for generating minimal perfect hash functions》。
算法的关键在于把判断某个 hash 算法是否为 perfect hash 算法的问题变成一个判断图是否无环的问题。
注意该算法最终生成的图 G 在不同的运行次数里大小可能不一样,你可能需要多跑几次结果生成多个 G,取其中最小者

以下就是算法的步骤:

假设你有 K 个 keys,比如 appleboycatdog

  1. 给每个 keys 分配一个从零开始递增的 ID,比如
apple 0
boy 1
cat 2
dog 3
  1. 选择一个稍微比 K 大一点的数 N。比如 N = 6。
  2. 随机选择两个 hash 函数 f1(x) 和 f2(x)。这两个函数接收 key,返回 0 ~ N-1 中的一个数。比如
f1(x) = (x[0] + x[1] + x[2] + ...) % N
f2(x) = (x[0] * x[1] * x[2] * ...) % N

之所以随机选择 hash 函数,是为了让每次生成的图 G 不一样,好找到一个最小的。

  1. 以 f1(x) 和 f2(x) 的结果作为节点,连接每个 f1(key) 和 f2(key) 节点,我们可以得到一个图 G。这个图最
    多有 N 个节点,有 K 条边。

比如前面我们挑的函数里,f1(x) 和 f2(x) 的结果如下表:

key    f1(x) f2(x)
apple     2    0
boy       0    0
cat       0    0
dog       2    0

生成的图是这样的:

2 --- apple ------
|                |
--- dog ---------0 -- boy -
                 |        |
                 --- cat -
  1. 判断图 G 是否无环。我们可以随机选择一个节点进行涂色,然后遍历其相邻节点。如果某个节点被涂过色,说
    明当前的图是有环的。显然上图就是有环的。
  2. 如果有环,增加 N,回到步骤 3。比如增加 N 为 7。
  3. 如果无环,则对每个节点赋值,确保同一条的两个节点的值的和为该边的 ID。
    (别忘了有多少个 key 就有多少条边,而每个 key 都在步骤 1 里面分配了个 ID)

沿用前面的例子,当 N 为 7 时,f1(x) 和 f2(x) 的结果如下表:

key    f1(x) f2(x)
apple     5    0
boy       1    0
cat       4    3
dog       6    4

生成的图是这样的:

0 --- apple --- 5
|
---- boy --- 1

4 --- cat --- 3
|
---- dog --- 6

显然上图是无环的。接下来的工作,就是给各个节点赋值,确保同一条边两个节点的值的和为该边的 ID。
即 0 号节点的值 + 5 号节点的值为 apple 的 ID 0。

我们可以每次选择一个没被赋值的节点,赋值为 0,然后遍历其相邻节点,确保这些节点和随机选择的节点的值的
和为该边的 ID,直到所有节点都被赋值。这里我们假设随机选取了 5 号节点和 3 号节点,赋值后的图是这样的:

0(0) --- apple --- 5(0)
|
---- boy --- 1(1)

4(2) --- cat --- 3(0)
|
---- dog --- 6(1)

现在图 G 可以这么表示:

int G[7] = {
    0, // 0 号节点值为 0
    1,
    0, // 2 号节点没有用到,可以取任意值
    0,
    2,
    0,
    1  // 6 号节点值为 1
}

最终得到的最小 Perfect Hash 算法如下:

P(x) = (G[f1(x)] + G[f2(x)]) % N
# N = 7
key    f1(x) f2(x) G[f1(x)] G[f2(x)] P(x)
apple     5    0    0       0         0
boy       1    0    1       0         1
cat       4    3    2       0         2
dog       6    4    1       2         3

P(x) 返回的值正好是 key 的 ID,所以拿这个 ID 作为 keys 的 offset 就能取出对应的 key 了。

注意,如果输入 x 不一定是 keys 中的一个 key,则 P(x) 的算出来的 offset 取出来的 key 不一定匹配输入
的 x。你需要匹配下x 和 key 两个字符串。

关于图 G,有两点需要解释下:

  1. 如果步骤 3 中随机选取的 f1(x),f2(x) 不同,则最终生成的 G 亦不同。实践表明,最终生成的 G 大小为 K
    的 1.5 ~ 2 倍。你应该多次运行这个最小 Perfect Hash 生成算法,取其中生成的 G 最小的一次。
  2. 由于 G 是无环的,所以其用到的节点数至少为 K + 1 个。而 G 里面用到的节点数最多为 1.5K 到 2K。所以
    有一半以上的节点是有值的。这也是为什么可以用一个 G 数组来表示图 G 里面每个点对应的值。

这个算法背后的数学原理并不深奥。

如果你能找到这样的 P(key),令 P(key) 的结果恰好等于 keykeys 里面的 offset,则 P(key)
必然是最小 Perfect Hash 算法。因为 keys[P(key)] 只能是 key,不可能会有两个结果;而且也找不到比
比 keys 的个数更小的 Perfect Hash 了,再小下去必然会有 hash collision。

如果我们设计出这样的一个图 G,它有 K 条边,每条边对应一个 key,边的两端节点的和为该边(key)的 offset
,则 P(x) 就是先算得两端节点的值,然后求和。两端节点的值可以通过随机选取一个节点为 0,然后给每个相邻
节点赋值的方式决定,前提是这个图必须是无环的,否则一个节点就可能被赋予两个值。所以我们首先要检查生成
出来的图 G 是否是无环的。

你可能会问,为什么生成出来的 P(x) 是 (G[f1(x)] + G[f2(x)]) % N,而不是 G[f1(x)] + G[f2(x)]?我看
了原文里面的代码实现(就在本文开头所给的链接里),他在计算每个节点值时,不允许值为负数。比如节点 A 为 5,
边的 ID 为 3,N 为 7,则另一端的节点 B 为 9(而不是 -2)。之所以这么做,是因为论文里面说 G(x) 是一个映射
x[0,K] 的函数,然后 P(x) 里面需要 % K。而代码里则把 G(x) 实现成映射 x 到 [0,N] 的函数,顺理
成章地后面就要 % N 了。

但其实如果我们允许值为负数,则 G[f1(x)] + G[f2(x)] 就能满足该算法背后的数学原理了。这么改的好处在
于计算时可以省掉一个相对昂贵的取余操作。

我改动了下代码实现,改动后的结果也能通过所有的测试(我另外还添了个 fuzzy test),所以这么改应该没有
问题。

相关推荐