内容简介:最近看到一篇有关 Perfect Hash 生成算法的文章,感觉很有必要写篇文章推荐下:先解释下什么是 Perfect Hash:Perfect Hash 是这样一种算法,可以映射给定 N 个 keys 到 N 个不同的的数字
最近看到一篇有关 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,比如 apple
, boy
, cat
, dog
。
- 给每个 keys 分配一个从零开始递增的 ID,比如
apple 0 boy 1 cat 2 dog 3
- 选择一个稍微比 K 大一点的数 N。比如 N = 6。
- 随机选择两个 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 不一样,好找到一个最小的。
-
以 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 -
-
判断图 G 是否无环。我们可以随机选择一个节点进行涂色,然后遍历其相邻节点。如果某个节点被涂过色,说
明当前的图是有环的。显然上图就是有环的。 - 如果有环,增加 N,回到步骤 3。比如增加 N 为 7。
-
如果无环,则对每个节点赋值,确保同一条的两个节点的值的和为该边的 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,有两点需要解释下:
-
如果步骤 3 中随机选取的 f1(x),f2(x) 不同,则最终生成的 G 亦不同。实践表明,最终生成的 G 大小为 K
的 1.5 ~ 2 倍。你应该多次运行这个最小 Perfect Hash 生成算法,取其中生成的 G 最小的一次。 -
由于 G 是无环的,所以其用到的节点数至少为 K + 1 个。而 G 里面用到的节点数最多为 1.5K 到 2K。所以
有一半以上的节点是有值的。这也是为什么可以用一个 G 数组来表示图 G 里面每个点对应的值。
这个算法背后的数学原理并不深奥。
P(key)
,令 P(key)
的结果恰好等于 key
在 keys
里面的 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),所以这么改应该没有
问题。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 【solitidy编程】-生成随机数算法
- Petuum提出序列生成学习算法通用框架
- QQ安全中心 - 动态口令的生成算法
- Git是怎样生成diff的:Myers算法
- Snowflake —— 分布式全局唯一 id 生成算法
- Snowflake算法生成分布式系统唯一ID
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Linux Programming Interface
Michael Kerrisk / No Starch Press / 2010-11-6 / GBP 79.99
The Linux Programming Interface describes the Linux API (application programming interface)-the system calls, library functions, and other low-level interfaces that are used, directly or indirectly, b......一起来看看 《The Linux Programming Interface》 这本书的介绍吧!