Хеширование наборов целых чисел для тестирования включения

Я ищу хэш-функцию над множествами H (.) И отношением R (.,.), Чтобы, если A входит в B, то R (H (A), H (B)). Конечно, R (.,.) Должно легко проверяться (постоянное время), а H (A) должно вычисляться за линейное время.

Одним из примеров H и R является:

$H(A) = \bigvee_{x\in A} 1 << (h(x) \mod k)$ , где k - фиксированное целое число, а h (x) - хеш-функция над целыми числами.
R (H (A), H (B)) = ((H (A) и H (B)) == H (A))

Есть ли другие хорошие примеры? (хорошо трудно определить, но интуитивно, если R (H (A), H (B)), тогда whp A включен в B).

Позже редактировать :

Я ищу семейство хэш-функций. У меня много комплектов; 3 - 8 элементов в каждом наборе; 90% из них имеют 3 или 4 элемента. Пример хэш-функции, который я дал, не очень хорошо распределен для этого случая.
Число битов H (.) (В моем примере k), которое должно быть небольшим (т. Е. H (.), Должно соответствовать целому или длинному).
Одно приятное свойство R состоит в том, что если H (.) Имеет k битов, то R (.,.) Истинно для (3 ^ k - 2 ^ k) / 4 ^ k пар, т.е. для очень немногих пар.
Фильтры Блума особенно хороши для больших наборов. Я пытался использовать BF для этой проблемы, но оптимальные результаты были только с одной функцией.

(кросс-пост из stackoverflow , я не получил достаточно хороший ответ)

ds.algorithms hash-function Александр
источник

что за что? Предполагаете ли вы, что ваши входные данные поступают из определенного распределения?

Юкка Суомела

И вы действительно ищете единственную фиксированную хеш-функцию, а не семейство хеш-функций?

Юкка Суомела

@Jukka: я думаю, что он имеет в виду, что если R (H (A), H (B)), то с большой вероятностью мы заключаем, что A является подмножеством B. Вероятность принимается за случайные выборы A и B, а также внутренние броски монет H и R (если есть).

MS Dousti

Я ищу семейство хэш-функций. Мои наборы имеют тенденцию быть маленькими (3 - 8 элементов каждый; 90% из них имеют 3 или 4 элемента), поэтому приведенная мною хэш-функция не очень хорошо распределена.

Александру

Одно приятное свойство R состоит в том, что если H (.) Имеет n битов, то R (.,.) Истинно для (3 ^ n - 2 ^ n) / 4 ^ n пар, т.е. для очень немногих пар.

Александру

Ответы:

(Этот ответ изначально был в комментариях, но я перевожу его на отдельный ответ по предложению Суреша.)

Для вашего приложения с очень маленькими наборами вы, вероятно, захотите, чтобы число хеш-функций Блума было достаточно большим, чтобы минимизировать количество ложных срабатываний. Чтобы сэкономить время вычислений, я предлагаю следующий вариант фильтра Блума. Предположим, у вас есть три традиционные хеш-функции , , для элементов, каждый из которых генерирует битные строки. Хэш каждого элемента для побитового и этих трех хеш-функций. Полученные хэши элементов будут примерно $k$ $h_1$ $h_2$ $h_3$ $m$ $2^{-3}=1/8^{th}$ из них. Хеш каждого набора битовый или хэши его составляющих элементов. Поскольку в ваших сетах по 3-8 элементов, полученные хэши будут соседствовать с половиной хэшей, что, по-видимому, является тем, что вы хотите наилучшим образом снизить уровень ложных срабатываний.

Разница между приведенной выше схемой традиционного фильтра Блума аналогична разнице между классической моделью случайных графов Erdos и случайными регулярными графами. Приведенная выше схема имеет эффективное число хэшей Блума, немного отличающееся от среднего значения но довольно велико, поэтому эта разница не должна иметь значения. $G_{n,p}$ $d$ $k$ $m/8$ $m/8$

Уоррен Шуди
источник

Это особенно хорошо для больших m (32 или 64), как вы предложили.

Александру

Я бы попробовал использовать фильтр Блума в качестве хэша с отношением, аналогичным вашему предложению. Вычисление наилучшего размера фильтра и количества хеш-функций для вашего приложения не должно быть слишком сложным; см. статью Блум-фильтра Википедии для вдохновения. В зависимости от того, насколько сильно вы хотите избежать ложных срабатываний, может быть достаточно что-то вроде и . $m$ $k$ $m=64$ $k=4$

Уоррен Шуди
источник

Для вашего приложения с очень маленькими наборами вы, вероятно, хотите, чтобы довольно большим. Это может быть довольно медленно с традиционным подходом. Вместо этого я предлагаю следующее.

k

$k$

Уоррен Шуди

(Продолжение предыдущего комментария) По сути, это разновидность фильтров Блума. Предположим, у вас есть три хеш-функции , , для элементов, которые генерируют битные строки. Хэш-элемент для побитового и этих трех. Полученные хэши будут иметь 1 / 8th 1s. Хэш-набор для побитового или хэш-кода его составляющих элементов. Поскольку ваши наборы имеют 3-8 элементов, полученные хеши будут иметь в окрестности половину единиц, что, вероятно, поможет снизить уровень ложных срабатываний.

h_{1}

$h_1$

h_{2}

$h_2$

h_{3}

$h_3$

m

$m$

Уоррен Шуди

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

Уоррен Шуди

Уоррен, ты должен опубликовать это как ответ. Это заслуживает некоторых голосов

Суреш Венкат

@Warren, @Suresh: я думаю, что было бы разумнее объединить эти два тесно связанных ответа, а затем удалить комментарии. Было бы легче следовать, в частности, так как один из ответов относится к параметрам, определенным в другом.

Юкка Суомела