机构名称：
¥ 1.0
最小完美哈希函数 (MPHF) 用于有效访问大型字典 (键值对集) 的值。发现构建 MPHF 的新算法是一个活跃的研究领域，尤其是从存储效率的角度来看。MPHF 的信息论极限为 1 ln 2 ≈ 1.44 位/键。当前最佳实用算法的范围是每个键 2 到 4 位。在本文中，我们提出了两种基于 SAT 的 MPHF 构造。我们的第一个构造产生的 MPHF 接近信息论极限。对于这种构造，当前最先进的 SAT 求解器可以处理字典包含多达 40 个元素的情况，从而优于现有的 (蛮力) 方法。我们的第二个构造使用 XOR-SAT 过滤器来实现一种实用方法，每个键的长期存储量约为 1.83 位。
利用 SAT 技术构造最小完美哈希函数
主要关键词
相关文件推荐
