Реализация хеширования с учетом локальных особенностей?
Существуют ли относительно простые для понимания (и простые в реализации) примеры хеш-зависимых от локальности хеш-функций в C/C++/Java/C#?
Я хотел бы узнать больше о концепции и поэтому хочу попробовать реализацию на нескольких текстовых файлах, просто чтобы посмотреть, как она работает, поэтому мне не нужно ничего высокопроизводительного или чего-либо... просто пример хэша функция, которая возвращает похожие хеши для похожих входов. Я могу узнать больше на этом примере позже.:)
4 ответа
Для строк вы можете использовать алгоритм приближенного соответствия.
- Генерация случайной строки
- Для всех строк вычислите их расстояние от этой случайной общей строки, используя алгоритм, подобный http://www.dotnetperls.com/levenshtein
Если строки равноудалены от ссылочной строки, то есть вероятность, что они похожи друг на друга. И вот, у вас есть локальная реализация хеш-строк для строк.
Вы можете создавать различные области хеша для диапазона расстояний.
РЕДАКТИРОВАТЬ: Вы можете попробовать другие варианты расстояния строки. Более простой алгоритм просто вернул бы no. общих символов между двумя строками.
Ну, есть отличная статья в блогах MSDN здесь: http://blogs.msdn.com/b/spt/archive/2008/06/11/locality-sensitive-hashing-lsh-and-min-hash.aspx
Также есть хотя бы одна библиотека C++, которую вы можете просмотреть здесь: http://sourceforge.net/projects/lshkit/
Я понимаю, что вы явно просили C/C++/C#, но есть порт Python для хэша nilsimsa, который может быть проще получить, чем другие, более крупные библиотеки.
Существует также реализация Java на Hadoop. он делает хорошую работу с документами.
это называется LikeLike
В настоящее время Likelike поддерживает только независимые перестановки Min-Wise. Min-Wise независимые перестановки применяются к рекомендации новостей Google