Wyszukiwarka, która wybacza literówki: jak naprawdę działa tolerancja błędów

Problem, sformułowany precyzyjnie

Klient, który wpisuje „kolibre”, prawie na pewno ma na myśli „koliber”. Pole wyszukiwania, które nie zwraca żadnego wyniku dla tego zapytania, nie jest rygorystyczne z dobrego powodu: zawodzi w jedynej sprawie, dla której istnieje, czyli w znalezieniu tego, co ktoś miał na myśli, a nie tylko tego, co wpisał. Tolerancja literówek to ogólna nazwa mechanizmów, które wypełniają tę lukę. Wygląda to na jedną funkcję. W rzeczywistości są to co najmniej dwa różne mechanizmy, o różnych kosztach i różnych sposobach zawodzenia, a mylenie ich sprawia, że większość naiwnych wdrożeń się myli.

Podstawowy element: odległość edycyjna

Prawie wszystkie mechanizmy tolerancji literówek, niezależnie od silnika, opierają się na tej samej podstawowej idei: odległości edycyjnej między dwoma ciągami znaków, najczęściej odległości Levenshteina, która liczy minimalną liczbę wstawień, usunięć lub podstawień pojedynczego znaku potrzebnych do przekształcenia jednego ciągu w drugi. „Koszuta” jest o jedno podstawienie od „koszula”. „Kosuzla” zamiast „koszula”, z zamienionymi dwiema sąsiednimi literami, to jedna transpozycja: dwie edycje według klasycznej definicji Levenshteina, tylko jedna w wariancie Damerau-Levenshteina, który liczy zamianę jako jedną edycję. Sama liczba o niczym nie przesądza; liczy się to, co system z nią robi.

Szczegół do ustalenia od początku: odległość jednej lub dwóch edycji jest hojna dla długiego słowa i niebezpieczna dla krótkiego. Dwie edycje w słowie o dziesięciu literach ledwo je zmieniają. Dwie edycje w słowie o trzech literach mogą zmienić je w zupełnie inne słowo: „kot” i „kod” dzieli jedna edycja, ale „kot” i „kit” również, tak samo jak „kot” i „kat”. System tolerancji literówek, który stosuje ten sam próg odległości niezależnie od długości słowa, skończy na beztroskim „poprawianiu” krótkich, odrębnych słów na inne. Uczciwa korekta to próg proporcjonalny do długości: żadnej korekty dla bardzo krótkich słów, jedna edycja dozwolona od kilku liter, dwie edycje tylko wtedy, gdy słowo jest na tyle długie, że po dwóch zmianach pozostaje rozpoznawalne.

Dwa różne mechanizmy, często mylone w jedną funkcję

„Tolerancja literówek” oznacza zazwyczaj jedną z dwóch rzeczywiście różnych rzeczy, a to, którą oferuje dany system, zmienia to, co potrafi i czego nie potrafi.

1. Dopasowanie fuzzy w momencie zapytania

Elasticsearch, OpenSearch i podobne silniki potrafią wykonać zapytanie fuzzy (lub użyć parametru fuzziness zapytania match), które porównuje szukany termin z terminami zindeksowanymi, używając odległości edycyjnej w momencie zapytania, bez konieczności wcześniejszej wiedzy, jakie błędy istnieją. Działa to dlatego, że silnik ma już indeks odwrócony wszystkich terminów obecnych w katalogu; zapytanie fuzzy sprowadza się mniej więcej do „znajdź terminy w indeksie odległe o najwyżej N edycji od tego i uszereguj wyniki według bliskości”. Nie wymaga osobnego etapu utrzymania i degraduje się łagodnie: nieco błędne zapytanie nadal stawia na szczycie najbliższe zindeksowane terminy. Jego prawdziwy koszt ujawnia się w polu o wysokiej kardynalności lub bardzo dużym słownictwie, gdzie obliczanie odległości edycyjnej na dużym zbiorze terminów kandydujących jest cięższe niż wyszukiwanie dokładnego terminu; dlatego dopasowanie fuzzy stosuje się zwykle selektywnie (główne pole tekstu swobodnego, a nie każde pole słowa kluczowego), a nie wszędzie domyślnie.

2. Korekta ze słownika, stosowana tylko wtedy, gdy trzeba

System bez silnika wyszukiwania, który natywnie punktuje dopasowania fuzzy, na przykład zwykła wyszukiwarka oparta na SQL, musi zbudować ten mechanizm sam: słownik prawidłowych terminów, zbudowany z nazw produktów i marek w katalogu, z którym porównuje się szukany termin, który nic nie dał, aby znaleźć najbliższe prawdziwe słowo. Słownik jest powszechnie indeksowany trigramami znaków (fragmentami po trzy litery), zamiast być porównywany litera po literze z każdym słowem, zarówno dlatego, że indeks trigramów zawęża listę kandydatów do słów prawdopodobnie bliskich, zanim dokładna odległość edycyjna zostanie obliczona na znacznie mniejszym zbiorze, jak i dlatego, że nie wymaga żadnego zewnętrznego silnika.

Szczegół, który w praktyce czyni to podejście ekonomicznym, zamiast pułapką wydajnościową, to moment, w którym uruchamia się wyszukiwanie w słowniku. Gdyby każde wyszukiwanie płaciło koszt zajrzenia do słownika, tolerancja literówek spowalniałaby wszystkie zapytania, także te wpisane poprawnie, które i tak znajdowały wyniki. Zajrzenie do słownika ma sens dopiero wtedy, gdy wyszukiwanie dokładne zwróciło pusty wynik: poprawne zapytanie nigdy go nie dotyka, a nadmiarowy koszt ponosi tylko przypadek zerowej liczby wyników. Zmierzone na prawdziwym katalogu, poprawnie napisane zapytanie i zapytanie z błędem, które uruchamia zajrzenie do słownika, zajęły ten sam, niewielki czas w obu przypadkach (oba między 0,16 a 0,19 sekundy w tej konkretnej instalacji): ścieżka słownika dodaje koszt tylko wyszukiwaniom, które w przeciwnym razie nie zwróciłyby niczego.

Słownik wymaga też utrzymania, którego zapytanie fuzzy nie potrzebuje: musi uczyć się nowych słów w miarę rozrastania się katalogu i zapominać słowa produktów, które już nie istnieją, inaczej powoli się starzeje i zaczyna sugerować korekty do porzuconych produktów. Słownik odbudowywany według harmonogramu (na przykład co tydzień, plus uzupełnienie na żądanie, gdy wyszukiwanie z zerową liczbą wyników po raz pierwszy potrzebuje słowa, którego jeszcze nie zna) pozostaje zgodny z katalogiem bez odbudowy przy każdym zapytaniu.

Gdzie łatwa wersja zawodzi

• Stały próg odległości edycyjnej dla słów każdej długości, jak widać wyżej: hojna korekta krótkich słów zamienia odrębne słowa na inne.
• Poprawianie zapytania, które już ma wyniki. Jeśli wyszukiwanie, które już znalazło produkty, jest także „poprawiane” na inny, popularniejszy termin, klient może zostać oddalony od tego, co faktycznie wpisał, i skierowany do tego, co silnik uzna za bliskie i popularne. Miejsce korekty jest po prawdziwym wyszukiwaniu z zerową liczbą wyników, a nie jako stałe przepisywanie każdego zapytania w tle.
• Korekta, która uruchamia się po cichu, gdy nie powinna. Na stronie wyszukiwania z fasetami wybór filtrów może zasadnie dać zero wyników (klient wybrał kombinację rozmiaru i koloru, której nikt nie ma na stanie). To nie jest problem pisowni, a warstwa tolerancji literówek, która nie potrafi tego rozróżnić, spróbuje „poprawić” słowo napisane zupełnie poprawnie, ponieważ to filtry, a nie słowo, opróżniły stronę.
• Poleganie na dopasowaniu fuzzy, żeby gwarantować także poprawne fasety. Sprawienie, by błędnie napisane zapytanie nadal znajdowało produkty, to inny problem niż poprawne policzenie, ile produktów pasuje do każdej wartości filtra. Silnik tolerujący błędy, który znajduje wyniki dla „kolibre”, bez wahania obliczy liczniki faset dla tego samego dopasowania fuzzy; jeśli element dalej w łańcuchu (na przykład lista autouzupełniania „popularnych wyszukiwań”) zakłada, że „znaleziono co najmniej jeden produkt” oznacza „to był prawdziwy, poprawnie napisany termin”, chętnie opublikuje literówki sklepu każdemu odwiedzającemu. To właśnie dlatego, że silnik tolerujący błędy dobrze wykonuje swoją pracę, ten błąd łatwo popełnić gdzie indziej w tym samym systemie.
• Milczenie zamiast przejrzystości. Wyszukiwanie, które po cichu zastępuje wpisany termin innym, nie wskazując, że doszło do podmiany, zostawia klienta z pytaniem, dlaczego wyniki nie całkiem odpowiadają temu, czego szukał. Widoczna, uczciwa linijka: „Brak wyników dla X. Oto wyniki dla Y”, kosztuje jedno zdanie i całkowicie zapobiega tej dezorientacji.

Krótka lista kontrolna

• Należy dostosować dozwoloną odległość edycyjną do długości słowa; nie wolno stosować tego samego progu do słowa o trzech literach i do słowa o dwunastu.
• Poprawiać należy dopiero po prawdziwym wyszukiwaniu z zerową liczbą wyników, nigdy przez ciche przepisanie zapytania, które już coś znalazło.
• Należy odróżniać „słowo było błędnie napisane” od „filtry opróżniły stronę”: oba przypadki wymagają innego traktowania, a ich pomylenie powoduje próbę korekty tam, gdzie nie było na nią miejsca.
• Jeśli prowadzą Państwo własny słownik zamiast polegać na wbudowanym punktowaniu fuzzy silnika, należy go aktualizować: odbudowywać według harmonogramu i pozwalać mu uczyć się z katalogu w miarę jego zmian, inaczej zacznie sugerować słowa, które już nie istnieją.
• Należy informować klienta, gdy doszło do podmiany. Nie wolno pozwolić, by „udane” dopasowanie fuzzy ukrywało fakt, że to, co wpisał, i to, co otrzymał, nie jest tym samym słowem.

W skrócie

Tolerancja literówek nie jest przełącznikiem włącz/wyłącz: to wybór między dwoma różnymi mechanizmami, natywnym dopasowaniem fuzzy silnika w momencie zapytania albo utrzymywanym słownikiem, do którego zagląda się tylko przy prawdziwym wyszukiwaniu z zerową liczbą wyników, każdym z własnym kosztem i własnym sposobem cichego mylenia się. Dwa błędy, na które trzeba uważać, to poprawianie słów, które wcale nie były błędnie napisane, oraz poleganie na dopasowaniu fuzzy w sprawach, do których nie zostało zaprojektowane, jak dokładne liczenie faset. Zajmujemy się tym w cll_essearch, naszym module wyszukiwania i nawigacji fasetowej dla PrestaShop, zarówno przy natywnym dopasowaniu fuzzy Elasticsearch, jak i z naszym własnym słownikiem trigramów dla sklepów korzystających z natywnego silnika bazy danych, jeśli chcą Państwo zobaczyć to rozróżnienie zastosowane w prawdziwym sklepie internetowym.

Wyszukiwarka Elasticsearch i nawigacja fasetowaBłyskawiczne wyszukiwanie z tolerancją literówek i nowoczesna nawigacja fasetowa we wbudowanym silniku lub w o…99,99 €Zobacz produkt