单调最小完美哈希函数的理论与实践

122 浏览量更新于2024-07-14 收藏 312KB PDF 举报

"Theory and Practice of Monotone Minimal Perfect Hashing" 在计算机科学中，最小完美哈希函数（Minimal Perfect Hash Functions, MPHF）是一种特殊的数据结构，它能够将任何给定集合的元素映射到一个固定大小的无冲突的哈希表中，且每个元素都有唯一的哈希值。这种哈希函数的重要性在于它能有效地压缩数据，特别是在数据管理任务中。当处理的数据具有特定顺序，例如按字典序排序时，单调最小完美哈希函数（Monotone Minimal Perfect Hash Functions, MMPHF）则更为实用。描述中提到的"order-preserving minimal perfect hash functions"是指不仅能够保持元素间原有顺序的哈希函数。这种哈希函数在数据检索时非常有用，可以快速定位到给定键在键列表中的位置。然而，为了保持任意顺序，至少需要 n log n / l bits 的空间来存储函数，这构成了一个下界。最近的研究发现，在许多实际应用中，如搜索引擎的词典、网页图的URL列表等，键往往按照它们的内在（字典）顺序排列。这就引出了单调最小完美哈希问题，它的限制是哈希的键必须保持其原有的顺序关系。论文中分析了之前提出的用于处理单调最小完美哈希的数据结构，并提出了一些新的方法。虽然这些新方法在理论上可能与原有方法等效或稍逊一筹，但在实际性能上可能会有所改进。作者们通过实验评估了这些结构，旨在优化存储效率和查询速度，以适应那些键有序的数据集。在设计单调最小完美哈希函数时，关键挑战是如何在满足单调性的同时，尽可能减少存储需求并提高查找效率。一种常见的策略是利用二分搜索或其他高效的数据组织方法来减少查找时间。此外，动态构建和更新哈希函数以适应插入和删除操作也是研究的重点。 "Theory and Practice of Monotone Minimal Perfect Hashing"探讨了如何在特定有序数据集上有效地应用最小完美哈希，以实现高效的存储和检索。该领域的研究对于优化数据库、搜索引擎和网络爬虫等数据密集型应用至关重要。通过不断改进哈希函数的设计，可以进一步提升数据处理的速度和空间效率。

bits: .s C /n bits for the frequent-output MWHC function, .2

 1/r bits for the array of most

frequent values, and .r C  / bits for each of the .1  p/

n inputs with less frequent output.

Ignoring the array of frequent values, the store space above is minimised by

s D log W



.r C  /.p  1/ ln 2



 log ln.1  p/;

where W./ is Lambert’s W function, which in this case can be approximated by W .x/  ln.1=x/

ln ln.1=x/.

A large-scale approach. MWHC functions and minimal perfect hashes require a large amount of

memory to be built, as they require random access to the 3-hypergraph to perform a visit. To make

their construction suitable for large-size key sets we reuse some techniques from [5]: we divide keys

into chunks using a hash function, and build a separate MWHC function for each chunk. We must

now store for each chunk the offset in the array a where the data relative to the chunk is written, but

using a chunk size !.log n/ (say, log n log log n) the space is negligible. The careful analysis in [5]

shows that this approach can be made to work even at a theoretical level by carefully reusing the

random bits when building the MWHC functions of each chunk.

3.3 Elias–Fano representation of monotone functions.

We will frequently need to store either a list of arbitrary integers, or a list of nondecreasing natural

numbers. In both cases, we would like to consume as little space as possible. To this purpose, we

will use the Elias–Fano representation of monotone functions [10, 11]. Such a data structure stores

a monotone function f W n ! 2

, that is, a list of nondecreasing natural numbers 0  x

 x



  x

n1

< 2

, provides constant-time access

to each x

, and uses 2 C s  log n bits per element

when n < 2

, and 1 C 2

=n bits when 2

 n.

Here, for completeness we brieﬂy recall from [10] the representation: we store explicitly the

s  log n lower bits of each x

in a bit array. The value v of the upper log n bits of x

are written in a

bit array b of 2n bits by setting the bit of position i Cv. It is easy to see that now v can be recovered

as select

.i/ i. Since the lower bits use s log n bits per element, and the bit array requires 2n bits,

we obtain the stated space bounds (in the case 2

 n, the ﬁrst array is empty, and the second array

requires just n C 2

bits). Selection in b can be performed with one of the many selection structures

in the literature (see, e.g., [8, 17, 18, 25, 31]; we note that if n  2

, the impact of the selection

structure on the space usage is irrelevant).

Finally, if we have to store a list of natural numbers x

, x

, : : : , x

n1

, we can just juxtapose the

binary representation of x

C 1, x

C 1, : : : , x

n1

C 1 (without the most signiﬁcant bit) and use an

Elias–Fano monotone sequence to store the starting point of each binary representation. The resulting

structure provides signiﬁcant gains if the distribution is skewed towards small values, as the overall

space usage is 2n Cn log.

blog.x

C1/c=n/ C

blog.x

C1/c. We will speak in this case of an

Elias–Fano compressed list. Note that if a is average of blog.x

C1/c (i.e., the average length in bits

of the x

increased by one), then the space usage is bounded by .2 C a C log a/n.

3.4 Bucketing.

We now discuss here brieﬂy a general approach to minimal perfect monotone hashes that we will

use in this paper and that will be referred to as bucketing. The same idea has been widely used for

non-monotone perfect hashing, and its extension to the monotone case proves to be fruitful.

Suppose you want to build a minimal perfect monotone hash function for a set S; you start with:

Actually, in the original Elias’ paper access is not constant, as it relies on a selection structure that is not constant-

time. Replacing the selection structure with a modern, constant-time structure provides constant-time access to the x

s; note,

however, that our implementations use the original Elias’ inventory-based linear scan, as it turns out to be faster.

剩余26页未读，继续阅读

weixin_38623919

粉丝: 5
资源: 929

单调最小完美哈希函数的理论与实践

Monotone Minimal Perfect Hashing - Searching a Sorted Table with O(1) Accesses - 2014 (MonotoneMinimalPerfectHashing)-计算机科学

Monotone Minimal Perfect Hashing - Searching a Sorted Table with O(1) Accesses (1496770.1496856)-计算机科学

最小多边形拟合python代码

单调样条求导数的R函数

MUSCL slope limiter是啥

用matlab求f(x)=2-(x-1)^(2/3)的单调区间

要求用单调链法连接交点时，要避开岛屿！！重新一个matlab参考代码，重点写用单调链法连接平行线与岛屿轮廓和型腔轮廓交点，并且如何避开岛屿的

Mono8转换成QImage

给定一个字符串判断这个字符串是否由同一个字符重复多次组成

最新资源