Реализация локально чувствительного хэша?

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

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


c java c# hash locality-sensitive-hash
person user541686    schedule 24.04.2011    source источник

Ответы (4)


arrow_upward
9
arrow_downward

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

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

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

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

EDIT: вы можете попробовать другие варианты расстояния между строками. Более простой алгоритм просто вернул бы нет. общих символов между двумя строками.

person Muhammad Hasan Khan    schedule 24.04.2011
comment
+1 кажется, это именно то, что я ищу, я посмотрю еще немного. Большое спасибо! :) - person user541686; 24.04.2011
comment
@Hasan: я немного запутался ... строки "abcd" и "xyzw" обе находятся на расстоянии 4 от случайной строки, такой как "6pGO", но они совершенно разные. Как это работает? (Это 4 для почти любой случайной строки длины 4...) - person user541686; 24.04.2011
comment
@Mehrdad этот алгоритм сообщает вам, сколько изменений вам нужно, чтобы преобразовать вашу входную строку в эталонную (случайную) строку. Вы также можете попробовать более простой алгоритм, в котором расстояние равно нулю. символов, общих между случайной строкой и вашей входной строкой. - person Muhammad Hasan Khan; 24.04.2011
comment
@Hasan: Да, я понял, что делает алгоритм, но проблема в том, что он совсем не работает, как я показал. Вы случайно не знаете какие-нибудь лучшие алгоритмы? (Тот, который вы только что упомянули, кажется отличным, я подумаю об этом.) - person user541686; 25.04.2011
comment
Такое решение для хеширования будет хорошо работать с похожими строками, но для нерелевантных строк оно даст вам бесполезные результаты, но если вы посмотрите на него в этом случае, у вас все равно нет похожих строк, поэтому любой алгоритм не будет работать. В первом случае все нерелевантные подпадают под хэш-код 4, и вы можете поддерживать другой хэш-лист для его дальнейшего разбиения. - person Muhammad Hasan Khan; 25.04.2011
comment
Вы можете получить лучшие результаты, сгенерировав n случайных строк, каждая из которых представляет одно ведро (список). Вы находите расстояние входной строки с каждой головкой ведра (случайная строка) и вставляете строку в ведро с минимальным расстоянием. Это называется кластеризацией. Позже вы можете проверить ведра по отдельности и поменять местами голову с элементом в списке, который представляет большинство строк в этом списке. Чтобы узнать больше об алгоритмах, попробуйте en.wikipedia.org/wiki/String_metric. - person Muhammad Hasan Khan; 25.04.2011
comment
Привет @MuhammadHasanKhan, спасибо за ваши проницательные ответы. Могу ли я использовать тот же подход в этой задаче «оптимизировать совпадающие элементы из двух больших наборов данных, используя расстояние Левенштейна»> stackoverflow.com/questions/54511595/ - person Shahid Manzoor Bhat; 23.11.2019

arrow_upward
6
arrow_downward

Здесь есть отличная статья в блогах 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/

person Teoman Soygul    schedule 24.04.2011
comment
Та же проблема, что и со ссылкой @Mehran, но все равно спасибо, +1. - person user541686; 24.04.2011

arrow_upward
2
arrow_downward

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

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

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

person Mehran    schedule 24.04.2011
comment
Спасибо за ссылку, но она кажется слишком сложной для моего случая... Я стараюсь избегать больших библиотек, пока не разберусь с простой. :-) В любом случае спасибо, +1. - person user541686; 24.04.2011

arrow_upward
2
arrow_downward

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

person Alec Thomas    schedule 27.05.2011
comment
+1 это довольно здорово, я также изучаю Python, так что он убивает двух зайцев одним выстрелом. Спасибо, что поделились этим! :) - person user541686; 28.05.2011