«1. Обзор

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

В этой быстрой статье мы воспользуемся библиотекой java-lsh, чтобы продемонстрировать простой вариант использования этого алгоритма.

2. Зависимость от Maven

Для начала нам нужно добавить зависимость Maven к библиотеке java-lsh: 

<dependency>
    <groupId>info.debatty</groupId>
    <artifactId>java-lsh</artifactId>
    <version>0.10</version>
</dependency>

3. Пример использования хеширования с учетом местоположения

У LSH есть много возможных приложений , но мы рассмотрим один конкретный пример.

Предположим, у нас есть база данных документов и мы хотим реализовать поисковую систему, которая сможет идентифицировать похожие документы.

Мы можем использовать LSH как часть этого решения:

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

4. Пример

Мы будем использовать библиотеку java-lsh для вычисления хэшей для наших входных векторов . Мы не будем освещать само преобразование, так как это огромная тема, выходящая за рамки данной статьи.

Однако предположим, что у нас есть три входных вектора, преобразованных из набора из трех документов, представленных в форме, которую можно использовать в качестве входных данных для алгоритма LSH: 

boolean[] vector1 = new boolean[] {true, true, true, true, true};
boolean[] vector2 = new boolean[] {false, false, false, true, false};
boolean[] vector3 = new boolean[] {false, false, true, true, false};

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

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

Давайте создадим экземпляр класса LSHMinHash. Нам нужно передать ему размер входных векторов — все входные векторы должны иметь одинаковый размер. Нам также нужно указать, сколько хеш-багет мы хотим и сколько этапов вычислений (итераций) должен выполнять LSH: 

int sizeOfVectors = 5;
int numberOfBuckets = 10;
int stages = 4;

LSHMinHash lsh = new LSHMinHash(stages, numberOfBuckets, sizeOfVectors);

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

Чтобы вычислить хэш для каждого вектора, мы передаем вектор методу hash(): 

int[] firstHash = lsh.hash(vector1);
int[] secondHash = lsh.hash(vector2);
int[] thirdHash = lsh.hash(vector3);

System.out.println(Arrays.toString(firstHash));
System.out.println(Arrays.toString(secondHash));
System.out.println(Arrays.toString(thirdHash));

Выполнение этого кода приведет к выводу, подобному: 

[0, 0, 1, 0]
[9, 3, 9, 8]
[1, 7, 8, 8]

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

После четырех итераций LSH дал результаты, как мы и ожидали – LSH вычислил одно и то же значение хеш-функции (8) для второго и третьего векторов, которые были похожи друг на друга, и другое значение хеш-функции (0) для вектора. первый вектор, который отличался от второго и третьего векторов.

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

Когда мы имеем дело с массивными наборами данных, LSH может быть удобным алгоритмом.

5. Заключение

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

Реализацию всех этих примеров и фрагментов кода можно найти в проекте GitHub — это проект Maven, поэтому его должно быть легко импортировать и запускать как есть.