Являются ли перекрывающиеся вложенные массивы байтового массива достаточно независимыми, чтобы использовать их в качестве хэш-функций для фильтра Блума?

Question

У меня следующий вопрос в контексте BloomFilter. BloomFilters должен иметь k независимых хеш-функций. Давайте назовем эти функции h1, h2, ... hk. Независимость в этом контексте означает, что их значение будет иметь очень небольшую корреляцию (возможно, нулевую) при применении к одному и тому же набору. См. Описание алгоритма на http://en.wikipedia.org/wiki/Bloom_filter (но, конечно, вы уже знаете эту страницу наизнанку:).

Теперь предположим, что я хочу определить мои хеш-функции, используя некоторые n биты (поступающие из крипто-функции, если вы должны знать, но это не имеет отношения к вопросу), которые сами не зависят друг от друга. Если вы хотите больше контекста, вы можете прочитать http://bitworking.org/news/380/bloom-filter-resources, что делает нечто подобное.

Например, предположим, что я хочу определить каждый h как (простите мой псевдокод):

bytes = MD5(value)
h1 = bytes[0-3] as Integer
h2 = bytes[4-7] as Integer
h3 = bytes[8-11] as Integer
...

Конечно, мы быстро исчерпаем хеш-функции. В этом примере MD5 мы получаем только четыре.

Одна из возможностей - позволить хеш-функциям перекрываться друг с другом и не требовать, чтобы четыре байта были последовательными. Таким образом, у нас есть много хеш-функций, так как перестановки позволяют байтовый массив. Проще говоря, что если мы определили хеш-функции следующим образом:

bytes = MD5(value)
h1 = bytes[0-3] as Integer
h2 = bytes[1-4] as Integer
h3 = bytes[2-5] as Integer
...

Легко видеть, что в случае с MD5 теперь у нас есть 12 хеш-функций вместо четырех.

Наконец, мы переходим к THE вопросу. Являются ли эти функции хеширования независимыми? Спасибо!

ОБНОВЛЕНИЕ : Я решил попытаться ответить на вопрос с практической точки зрения, поэтому я создал небольшую программу, которая проверила бы гипотезу. Смотри ниже.

Answer 1

Запуск программы, приведенной ниже, проверит гипотезу с генераторами случайных чисел.

public static void main(String[] args) {
    int R = 100, N = 10000, W = 8;
    double[] totals = new double[33];
    Random r = new Random();

    for (int k = 0; k < R; k++) {
        // Generate 10,000 random byte arrays
        byte[][] bytes = new byte[N][W];
        for (int i = 0; i < N; i++) r.nextBytes(bytes[i]);

        double[] a1 = new double[N], a2 = new double[N];
        for (int i = 0; i <= 32; i++) {

            // Extract arrays
            for (int j = 0; j < N; j++) {
                a1[j] = readInt(bytes[j], 0, 31);
                a2[j] = readInt(bytes[j], 32 - i, 31);
            }

            double c = (new PearsonsCorrelation()).correlation(a1, a2);
            totals[i] += c;
        }
    }
}

Интересные биты в том, что только когда есть только один перекрывающийся бит, корреляция начинает быть значимой. Ниже приведены коэффициенты корреляции Пирсона для каждого числа перекрывающихся битов. Мы начинаем с очень низкого уровня (т.е. близко к случаю перекрытия 0) и получаем 1, когда они полностью перекрываются.

0   -0.001883705757299319
1   -0.0019261826793995395
2   -0.0018466135577488883
3   -0.001499114477250019
4   -0.0010874727770462341
5   -1.1219111699336884E-5
6   -0.001760700583842139
7   3.6545455908216937E-4
8   0.0014823972050436482
9   0.0014809963180788554
10  0.0015226692114697182
11  0.00199027499920776
12  0.001720451344380218
13  -2.0219121772336676E-4
14  6.880004078769847E-4
15  8.605949344202965E-4
16  -0.0025640320027890645
17  -0.002552269654230886
18  -0.002550425130285998
19  -0.002522446787072504
20  -0.00320337678141518
21  -7.554573868921899E-4
22  -6.463448718890875E-4
23  -3.4709181348336335E-4
24  0.0038077518094915912
25  0.0037865326140343815
26  0.0038728464390708982
27  0.0035091958914765407
28  0.005099109955591643
29  0.016993434043779915
30  0.06120260114179265
31  0.25159073855202346
32  1.0

Итог : кажется, что сдвиг на один байт (то есть значение 24 выше) должен быть совершенно безопасным в отношении генерации хэш-функции.

Answer 2

Как часто бывает с умными вопросами, ответ - да, и нет.

Да, в том смысле, что есть 16 битов, которые не разделены между h1 и h2.Нет, в тех смыслах, которые важны для вас (если только вы на самом деле не используете только восемь битов хэш-функции, а я полагаю, что вы этого не делаете).

Проблема здесь не так велика с зависимостью между двумя применяемыми функциямик одному и тому же элементу, вставляемому и более (в данном случае, на мой взгляд) с функциями, применяемыми к нескольким элементам.

Подумайте об этом так.Предположим, ваш первый пример использует g1-g4, а второй - h1-h4.Два элемента, чья сумма MD5 (или любая другая функция хеширования) перекрываются только в 5 последовательных байтах (маловероятно, но статистически выполнимо, особенно если вы пытаетесь), будут иметь вероятность коллизии, если просто используете h1 и h2, h2 и h3,или h3 и h4.Между тем g1-g4 устойчив к такой возможности.

Теперь коллизии с фильтрами Блума не так важны, как другие приложения хеш-функций, но вы должны иметь в виду, что перекрывающиеся байты отвлекают от использования хеш-функций.Я немного удивлен, что вам нужно более четырех независимых хеш-функций, если честно.

Кроме того, если вы используете только последние 8 бит каждого числа (256-битный фильтр Блума) или последнюю16 бит (2 ^ 16 битный фильтр Блума), или что угодно, тогда вы можете «перекрывать» биты, которые вы не используете, с опрометчивой энергией и без риска.

Отказ от ответственности: Я хорошо знаю криптографию и расцветаюфильтры, потому что они потрясающие, но мое практическое знание фильтров Блума ограничено;то, что вы описываете, может хорошо работать для вашего варианта использования.