为连续范围创建 'perfect hash function'

Question

我正在寻找一种方法将 'project' 一系列 'ranges' 转换为一系列值。应用程序将是具有不均匀 bin 的直方图或创建查找 tables.

一个例子：

0 到 14 => 0

15 到 234 => 1

235 => 2

236 到 255 => 3

右侧 'result' 值 (0, 1, 2, 3) 的实际顺序并不重要，只要它们在 0 和 3 之间，这样我就可以使用小型查找table 之后。如果我可以在浮点值（左侧）上进行这项工作，那就更好了。

我知道我可以在这里使用 8 位查找 table 并重复值，但我想找到一种方法来 'perfect hash' 这个：通过一系列系统操作（如小尽可能没有分支）从左值计算右值，以获得尽可能小的结果 space.

我似乎无法为这种算法找到正确的魔法 Google 咒语系列。

此'hash'或'projection'函数的计算持续时间如有必要可以以天为单位。

Answer 1

如果您有 n 个没有重叠或间隙的范围，您可以使用 O(log2(n)) 指令生成一些简单的代码来进行此查找。我将用一些 Python 代码进行演示。

# Must be a power of two, extend with zeros on the right if needed.
lookup = [0, 15, 235, 236]

def index(x):
    i = 0
    # ceil(log2(len(lookup))) iterations in the following pattern.
    # We only need 2 iterations here.
    # ...
    # i += (x >= lookup[i+8]) << 4
    # i += (x >= lookup[i+4]) << 3
    i += (x >= lookup[i+2]) << 2
    i += (x >= lookup[i+1]) << 1
    return i

这称为无分支二分搜索。例如。即使您有 2¹⁶ 个范围，也只需要 32 次加法和 16 次 table 查找、比较和位移来计算确切的索引。

为连续范围创建 'perfect hash function'

Create a 'perfect hash function' for contiguous ranges

algorithm

range

lookup-tables

perfect-hash