Поиск в массиве похожих / наиболее похожих строк Java

Question

Я работаю над проектом, в котором у меня есть названия книг в файле XML. Затем они анализируются и превращаются в список массивов book объектов. Теперь я хочу их просмотреть. Я уже успешно реализовал Collections.binarySearch(). Проблема сейчас в том, что, поскольку поиск ищет точное совпадение, он только перевернет книгу, если написан точно правильно. Например, если бы я вводил «Гарри Поттр», я бы ничего не получил, так как он написан с ошибкой. Что мне нужно знать, так это пару вещей:

1. Как бы мне создать систему, которая может отображать результаты для входа, достаточно близкого к чему-либо в массиве. Например:

   ArrayList<Book> library = new ArrayList<Book>();
   Для простоты скажем, я добавил несколько книг в массив: "Harry Potter", "The Lord of The Rings", "Wonder"

   Теперь, если бы я искал в массиве "Wnder", я бы хотел, чтобы книга все еще появлялась.

2. Есть ли решение этой проблемы, которое я могу использовать с функцией Collections.binarySearch(), или мне нужно выполнить собственный бинарный поиск, чтобы использовать ее.

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

P.S. Я знаю о расстоянии Левенштейна. Но если бы я понял это, я мог бы использовать это в уже использованной функции поиска Коллекций.

Answer 1

Расстояние Левенштейна - один из лучших способов найти сходство между двумя словами, но это не поможет вам с бинарным поиском, потому что бинарный поиск работает в отсортированной коллекции и эффективно ищет объект, равныйзаданное значение.

С расстоянием Левенштейна вы ищете не то, что соответствует вашему поисковому запросу, вы ищете элемент, который является наиболее похожим (наименьшее расстояние Левенштейна).Вам нужно будет оценить каждый элемент в списке, чтобы выяснить, какой из них наиболее близок.

Другая возможность - Soundex.Алгоритм Soundex пытается уловить, как звучит слово.Он выбрасывает все гласные, а затем кодирует согласные, давая вам число, представляющее звук слова.Используя это, вы можете сохранить список объектов с их значениями soundex, а затем найти в нем значение soundex, близкое к значению вашего поискового запроса.Однако у вас все равно будет проблема отсутствия точного значения для поиска.

Answer 2

В стандартную библиотеку вы попадете только так далеко.

Если список строк (название книги) «маленький», то вы, вероятно, можете использовать https://github.com/xdrop/fuzzywuzzy (см. FuzzySearch.extractTop).

В противном случае, если это слишком медленно, вам нужен алгоритм, основанный на индексах, такой как реализованный в https://lucene.apache.org/core/.

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