Локальная чувствительность хеширования?

Есть ли относительно простые для понимания (и простые в реализации) локально-чувствительные хэш-примеры в C/С++/Java/С#?

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

Ответы

Ответ 1

Для строк вы можете использовать алгоритм приближенного соответствия.

  • Создать случайную строку
  • Для всех строк вычисляется их расстояние от этой случайной общей строки с использованием алгоритма, такого как http://www.dotnetperls.com/levenshtein

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

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

РЕДАКТИРОВАТЬ: Вы можете попробовать другие варианты длины строк. Более простой алгоритм просто вернул бы нет. общих символов между двумя строками.

Ответ 3

Существует также реализация Java на Hadoop. он хорошо документирует документы.

он называется LikeLike

В настоящее время Likelike поддерживает только Минимальные независимые перестановки. Минимальные независимые перестановки применительно к рекомендации Новости Google

Ответ 4

Я понимаю, что вы явно просили C/С++/С#, но есть порт Python nilsimsa hash, который может быть проще получить, чем другие, более крупные библиотеки.