将连续整数映射到非不同整数的哈希函数

Question

我有一个由 1760 个整数组成的序列，范围从 129 到 250，这些整数没有可辨别的模式。我正在开发一个非常小的嵌入式系统，不能在查找上浪费将近 2 KB table。我想提出一个函数，允许我查找给定索引（在 0 到 1759 范围内）的值。

我知道 minimal perfect hashing 允许我将不同的值映射到一组连续的整数，但我希望将一组连续的整数映射到非不同的值。

数百万年的蛮力是唯一的方法吗？是否有某种方法可以实现更小的查找 table（例如，大约 256 字节或更少）？

Answer 1

什么进程生成了您的 1760 个整数？不幸的是，如果不更多地了解您的数据源，将很难（如您所说，"millions of years"）找到这样的函数（如果存在）。克劳德·香农证明了随机噪声的信息熵最大，因此无法压缩。因此，如果您的整数没有可辨别的模式，那确实符合随机噪声的条件。

回到查找 table，您可以将 table 的大小减少 1/8，方法是识别您的整数都在 129-250 范围内，这只需要 7 位代表。在 table 查找中使用一些位操作技巧，您将只需要 1760 * 7/8 = 1540 字节或 12.5% 的节省。数量不多，但这是一个开始；这里有一些示例代码来说明我的意思。

示例代码

#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>

void compress(const std::vector<uint8_t>& raw, std::vector<uint8_t>& comp) {
    // Length must be a multiple of 8 to handle unrolled loop.
    assert(raw.size() % 8 == 0);

    comp.resize(raw.size() * 7 / 8);
    for (size_t rIdx = 0, cIdx = 0; rIdx < raw.size(); rIdx += 8, cIdx += 7) {
        comp[cIdx + 0] = (raw[rIdx + 0] << 1) | ((raw[rIdx + 1] & 0x7f) >> 6);
        comp[cIdx + 1] = (raw[rIdx + 1] << 2) | ((raw[rIdx + 2] & 0x7f) >> 5);
        comp[cIdx + 2] = (raw[rIdx + 2] << 3) | ((raw[rIdx + 3] & 0x7f) >> 4);
        comp[cIdx + 3] = (raw[rIdx + 3] << 4) | ((raw[rIdx + 4] & 0x7f) >> 3);
        comp[cIdx + 4] = (raw[rIdx + 4] << 5) | ((raw[rIdx + 5] & 0x7f) >> 2);
        comp[cIdx + 5] = (raw[rIdx + 5] << 6) | ((raw[rIdx + 6] & 0x7f) >> 1);
        comp[cIdx + 6] = (raw[rIdx + 6] << 7) | ((raw[rIdx + 7] & 0x7f) >> 0);
    }
}

uint8_t lookup(const std::vector<uint8_t>& comp, size_t rIdx) {
    size_t cIdx = rIdx / 8 * 7;
    switch (rIdx % 8) {
    case 0:
        return                                  (comp[cIdx + 0] >> 1) | 0x80;
    case 1:
        return ((comp[cIdx + 0] & 0x01) << 6) | (comp[cIdx + 1] >> 2) | 0x80;
    case 2:
        return ((comp[cIdx + 1] & 0x03) << 5) | (comp[cIdx + 2] >> 3) | 0x80;
    case 3:
        return ((comp[cIdx + 2] & 0x07) << 4) | (comp[cIdx + 3] >> 4) | 0x80;
    case 4:
        return ((comp[cIdx + 3] & 0x0f) << 3) | (comp[cIdx + 4] >> 5) | 0x80;
    case 5:
        return ((comp[cIdx + 4] & 0x1f) << 2) | (comp[cIdx + 5] >> 6) | 0x80;
    case 6:
        return ((comp[cIdx + 5] & 0x3f) << 1) | (comp[cIdx + 6] >> 7) | 0x80;
    case 7:
        return ((comp[cIdx + 6] & 0x7f) << 0) | 0x80;
    }
}

int main() {
    std::vector<uint8_t> raw { 151, 169, 162, 164, 155, 147, 149, 143, };
    std::vector<uint8_t> comp;

    compress(raw, comp);

    for (size_t i = 0; i < raw.size(); ++i) {
        std::cout << i << ": raw " << static_cast<int>(raw[i])
                  << ", lookup " << static_cast<int>(lookup(comp, i))
                  << std::endl;
    }
    return 0;
}

输出

我只是在每个索引处打印出原始数据和 compressed/uncompressed 数据以验证存储和检索。

0: raw 151, lookup 151
1: raw 169, lookup 169
2: raw 162, lookup 162
3: raw 164, lookup 164
4: raw 155, lookup 155
5: raw 147, lookup 147
6: raw 149, lookup 149
7: raw 143, lookup 143

如果您的输入数据长度不再是 8 的倍数，则还有一些工作要做，但这应该让您开始。

将连续整数映射到非不同整数的哈希函数

Hash function to map consecutive integers to non-distinct integers

embedded

hash

lookup-tables

示例代码

输出