Фильтр Блума на основе символов

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

hash(S)=sum(S[i]*(p^i))_i=0 to n-1.

Вы можете использовать этот хеш 2 раза, чтобы уменьшить вероятность ложных срабатываний. Это даст вам разумное поведение.

Также выбор p должен быть ограничен простым числом, и он должен быть больше, чем количество символов в наборе алфавита.

• Это даст вам лучший результат, чем простое добавление значений ascii.

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

Еще одним критерием является скорость, поэтому стандартные криптографические хеши - не лучший выбор. (как sha1)

Я слышал об одном стандартном методе хеширования murmurhash, который вы можете попробовать использовать и сравнить с ожидаемым результатом.

Чтобы понять, как вы собираетесь его реализовать: -

Вы можете рассмотреть несколько хэш-функций, таких как murmur, fnv1a или даже простую, которую я представил, и тогда вы получите 3 значения из каждого хеша. Поместите их в соответствующие места. И тогда он будет работать как ваш фильтр цветения.

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

Например:

Вы хотите хешировать stackoverflow. Теперь вы используете 3 хэш-функции, которые дают вам числа 11, 45 и 17. Вы бы сохранили карту, где вы поместите это значение.

{
   11: 1,
   45: 1,
   17: 1
}

Снова вы выполняете хеширование таким образом и получаете значения 11, 15 и 97.

Затем вы измените его на

{
  11: 1,
  15: 1,
  17: 1,
  45: 1,
  97: 1
}

Примечание: я упомянул здесь карту ... это может быть что-то вроде массива битов, в котором вы также устанавливаете биты. Например .. в случае stackoverflow 11,17 и 45 биты будут установлены в 1.

Обратите внимание, что эта карта поможет вам ответить на вопрос, есть ли элемент там или нет.

Теперь в случае запроса вы сделаете то же самое, получите хеш-значения и проверите, существуют ли эти значения. Если да, высока вероятность, что он есть (не совсем так, как это может быть ложное срабатывание), если нет, то это не совсем точно.

Предположим, теперь вы проверите, есть ли там строка «abcd». Вы применяете 3 хэш-функции, которые использовались ранее. Результаты 11,99,55. Вы проверите, все ли они существуют. Вы можете видеть, что 55 там нет. Так что строки «abcd» там нет.