Хеширование с учетом местоположения в Java с использованием Java-LSH

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, поэтому его должно быть легко импортировать и запускать как есть.