Приблизительный поиск строк
Приблизительный поиск строк, нечеткий поиск, поиск с ошибками — есть много названий для этой одной проблемы. В этой статье я покажу вам два способа реализации поиска, который принимает во внимание потенциальную опечатку.
Пример проблемы
Пользователь вводит название компании с ошибкой: Tetla, Aptle, Cola Koca, Mikrosoft, и приложение возвращает правильное название компании и похожие компании (если таковые существуют):
| Пользовательский запрос с ошибкой | Ожидаемый результат |
| сетевидная структура | тесла |
| Apptle | яблоко |
| Cocakola | Кока-Кола |
| Mikrosoft | Microsoft |
Алгоритм проверки орфографии, описанный директором по исследованиям Google
Питер Норвиг описал алгоритм, похожий на проверку орфографии поиска Google в этой статье . Я изменил предоставленную реализацию Java в соответствии с требованиями, установленными в этой статье. Вы можете найти полный исходный код здесь .
Я изменил это немного, чтобы соответствовать нашим потребностям. В словарь добавляем наши четыре компании и после тестирования:
Джава
1
public class Spelling {
2
private static final String ABC = "abcdefghijklmnopqrstuvwxyz";
3
private static Map<String, Integer> dictionary = new HashMap<>();
4
private static String DICTIONARY_VALUES = "Tesla,Apple,Microsoft,CocaCola";
5
public static void main(String[] args) {
6
Stream.of(DICTIONARY_VALUES.toLowerCase().split(",")).forEach((word) -> {
7
dictionary.compute(word, (k, v) -> v == null ? 1 : v + 1);
8
});
9
System.out.println("Correction for Tela: " + correct("Tela"));
10
System.out.println("Correction for Apptle: " + correct("Apptle"));
11
System.out.println("Correction for Cocakola: " + correct("Cocakola"));
12
System.out.println("Correction for Mikrosoft: " + correct("Mikrosoft"));
13
}
14
private static Stream<String> getStringStream(String word) {
16
Stream<String> deletes = IntStream.range(0, word.length())
17
.mapToObj((i) -> word.substring(0, i) + word.substring(i + 1));
18
Stream<String> replaces = IntStream.range(0, word.length()).boxed().flatMap((i) -> ABC.chars()
19
.mapToObj((c) -> word.substring(0, i) + (char) c + word.substring(i + 1)));
20
Stream<String> inserts = IntStream.range(0, word.length() + 1).boxed().flatMap((i) -> ABC.chars()
21
.mapToObj((c) -> word.substring(0, i) + (char) c + word.substring(i)));
22
Stream<String> transposes = IntStream.range(0, word.length() - 1)
23
.mapToObj((i) -> word.substring(0, i) + word.substring(i + 1, i + 2) + word.charAt(i) + word.substring(i + 2));
24
return Stream.of(deletes, replaces, inserts, transposes).flatMap((x) -> x);
25
}
26
private static Stream<String> edits1(final String word) {
28
return getStringStream(word);
29
}
30
private static String correct(String word) {
32
Optional<String> e1 = known(edits1(word)).max(Comparator.comparingInt(a -> dictionary.get(a)));
33
if (e1.isPresent()) return dictionary.containsKey(word) ? word : e1.get();
34
Optional<String> e2 = known(edits1(word).map(Spelling::edits1).flatMap((x) -> x))
35
.max(Comparator.comparingInt(a -> dictionary.get(a)));
36
return (e2.orElse(word));
37
}
38
private static Stream<String> known(Stream<String> words) {
40
return words.filter((word) -> dictionary.containsKey(word));
41
}
42
}
Алгоритм работает как положено. Для наших входных данных мы получаем правильную коррекцию: Tetla: Tesla, Aktle: яблоко, CokaCola: кокакола, Mikrosaft: Microsoft.
К сожалению, эта реализация не поддерживает сложные случаи и поэтому не готова к производству. Давайте посмотрим на следующее, гораздо более мощное решение.
Apache Solr
Solr - поисковая платформа для предприятий, основанная на Apache Lucene. Solr имеет встроенный поиск, который поддерживает эту опечатку. Этот проект является частью программного обеспечения Apache с открытым исходным кодом , поэтому вы можете использовать его бесплатно.
Монтаж
- Скачайте и распакуйте apache solr .
- Создать новое ядро:
solr create -c my_new_core - Измените solr \ solr-8.4.1 \ server \ solr \ newcoretest \ conf \ solrconfig.xml. Найдите xml с DirectSolrSpellChecker и измените значение поля с _text_ на name.
XML
xxxxxxxxxx
1
<str name="field">name</str>
2
<str name="classname">solr.DirectSolrSpellChecker</str>
Начало Solr в командной строке с: solr start (execute administration mode). Затем создайте пустой проект Java и http://www.apache.org/ с зависимостью Maven:
XML
xxxxxxxxxx
1
<dependency>
2
<groupId>org.apache.solr</groupId>
3
<artifactId>solr-solrj</artifactId>
4
<version>6.4.0</version>
5
</dependency>
После этого шага конфигурация проверки орфографии по умолчанию будет использовать поле «имя» во всех документах.
Написание приложения поиска с предложениями правописания
Инициализация HttpSolrClient:
Джава
xxxxxxxxxx
1
String urlString = "http://localhost:8983/solr/my_new_core";
2
HttpSolrClient solr = new HttpSolrClient.Builder(urlString).build();
3
solr.setParser(new XMLResponseParser());
Добавление документов в my_new_core
Джава
xxxxxxxxxx
1
Arrays.asList("Tesla", "Apple", "Microsoft", "Coca Cola").forEach(companyName -> {
2
try {
3
SolrInputDocument document = new SolrInputDocument();
4
document.addField("name", companyName);
5
solr.add(document);
6
solr.commit();
7
} catch (Exception ignored) {}
8
});
Запрос запроса правописания для слова "кока":
Джава
xxxxxxxxxx
1
SolrQuery params = new SolrQuery();
2
params.set("qt", "/spell");
3
params.set("q", "coka");
4
params.set("spellcheck", "on");
5
params.set("spellcheck.build", "true");
6
QueryResponse response = solr.query(params);
8
List<SpellCheckResponse.Suggestion> suggestions = response.getSpellCheckResponse().getSuggestions();
9
for (SpellCheckResponse.Suggestion suggestion : suggestions) {
10
for(String alternative: suggestion.getAlternatives()){
11
System.out.println("suggestion for coka:" + alternative);
12
}
13
}
Для запрошенного слова «coka» движок возвращает существующее слово в нашей библиотеке (не документы):
suggestion for coka:coca
suggestion for coka:cola
Наконец, поиск одного из совпавших предложений: "кока"
Джава
xxxxxxxxxx
1
SolrQuery params = new SolrQuery();
2
params.set("qt", "/query");
3
params.set("q", "name:" + "coca");
4
params.set("spellcheck", "on");
5
params.set("spellcheck.build", "true");
6
QueryResponse response = solr.query(params);
8
for (SolrDocument document: response.getResults()){
9
System.out.println("Matched document: " + document.getFieldValue("name"));
10
}
Результат исполнения:
Matched document: Coca Cola
Веб-интерфейс поиска Solr
В целях отладки вы можете использовать веб-интерфейс Solr. Адрес по умолчанию: http: // localhost: 8983 / .
Пример запроса проверки правописания - поиск предложений "coka".
Поиск конкретного названия компании, которое содержит «кока»:
Настройка Solr требует времени для изучения. Это очень больно в самом начале.
Альтернатива Solr: Elasticsearch
Elasticsearch является известной альтернативой Solr. Он более мощный, но полная версия платная, а бесплатная версия имеет некоторые ограничения.