Constructing Perfect Hash Families Using a Greedy Algorithm
Constructing Perfect Hash Families Using a Greedy Algorithm
复制标题
使用贪心算法构造完美哈希族
DOI：
10.1142/9789812832245_0008
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
C. Colbourn
中科院分区：
文献类型：
--
作者：
C. Colbourn
一个完美的哈希家族是一个符号数组，其中每个子数组中至少有一行由不同的符号组成。完美散列族在密码学中有广泛的应用，特别是在数据库管理中的安全防帧代码，并间接用于软件交互测试。提出了一种构造小的完美哈希族的简单的逐行贪婪算法。该算法是确定性的，其最坏情况下的运行时间是多项式的，但在指数;因此，当固定时，该算法在最坏情况下以多项式时间运行。它提供了一个确定性的保证，即产生的行数是O（log k）。除了这些强渐进保证之外，该方法还被证明对于和的“小”值的完美哈希族的计算是实用的。
Aperfect hash familyis anarray onsymbols with, in which in everysubarray, at least one row is comprised of distinct symbols. Perfect hash families have a wide range of applications in cryptography, particularly to secure frameproof codes, in database management, and are indirectly used in software interaction testing. A simple one-row-at-a-time greedy algorithm for constructing small perfect hash families is described. The algorithm is deterministic, and its worst-case runtime is polynomial inandbut exponential in; consequently, whenis fixed, the algorithm runs in polynomial time in the worst case. It provides a deterministic guarantee that the numberof rows produced is O(log k). In addition to these strong asymptotic guarantees, the method is shown to be practical for the computation of perfect hash families for "small" values ofand.