Skip to content
← Wszystkie wpisy
5 min czytania Dawid Skłodowski

Usługa rozmytego dopasowania pełnotekstowego w Ruby

Użytkownicy robią literówki, a dopasowanie dokładne po cichu ich zawodzi. Praktyczny deep-dive w rozmyte dopasowanie oparte na trigramach w Ruby — jak działa, jak je przyspieszyć i kiedy zamiast tego wepchnąć je do Postgresa.

Oto problem, który wygląda trywialnie, dopóki go nie wdrożysz: użytkownik wpisuje „Manchestr” w pole miasta, twoje WHERE name = ? nie zwraca nic, a on dochodzi do wniosku, że twój produkt jest zepsuty. Dopasowanie dokładne jest binarne i bezlitosne — nie ma pojęcia „blisko”. Prawdziwe dane wejściowe są pełne literówek, przestawień, brakujących liter i alternatywnych pisowni, a wyszukiwanie rozumiejące tylko dokładną równość po cichu zawodzi przy wszystkich.

Chcesz rozmytego dopasowania: dla zapytania zwróć kandydatów, którzy są mu bliscy, uszeregowanych według tego, jak blisko. Budowaliśmy to kilka razy i podejście oparte na trigramach wciąż wygrywa — jest proste, dość szybkie do użytku interaktywnego i łatwe do ogarnięcia. Oto jak działa i jak zbudować je w Ruby.

Dlaczego nie odległość edycyjna?

Podręcznikową odpowiedzią na „jak podobne są dwa łańcuchy” jest odległość Levenshteina: liczba pojedynczych wstawień, usunięć lub podstawień znaków, by zamienić jeden w drugi. „Manchestr” → „Manchester” to odległość 1. Jest intuicyjna i dokładna, i ma jedną fatalną wadę przy skali: jej obliczenie to O(n·m) na parę, a żeby znaleźć najlepsze dopasowanie na liście miliona nazw miast, policzyłbyś ją milion razy na zapytanie. Odległość edycyjna to świetny sposób na uszeregowanie garstki wstępnie przefiltrowanych kandydatów; to fatalny sposób na ich znalezienie w dużym zbiorze.

Potrzebujemy metody, która tanio zredukuje milion kandydatów do kilkudziesięciu, a potem możemy uszeregować tych kilku czymś precyzyjnym. Trigramy są tą metodą.

Trigramy: zamiana rozmycia w nakładanie się zbiorów

Trigram to ciąg trzech kolejnych znaków. Rozłóż łańcuch na zbiór jego trigramów (dopełniając końce, by krótkie łańcuchy i granice słów zachowywały się dobrze):

def trigrams(string)
  s = "  #{string.downcase.gsub(/[^a-z0-9]/, ' ')} "
  (0..s.length - 3).map { |i| s[i, 3] }.uniq
end

trigrams("Manchester")
# => ["  m", " ma", "man", "anc", "nch", "che", "hes", "est", "ste", "ter", "er "]

Sztuczka tkwi w tym, co to ci daje: dwa łańcuchy, które są podobne, dzielą większość swoich trigramów, a literówka zaburza tylko dwa–trzy trigramy wokół zmienionego znaku. „Manchestr” i „Manchester” dzielą niemal każdy trigram, więc ich podobieństwo — rozmiar przecięcia podzielony przez rozmiar sumy (indeks Jaccarda) — jest wysokie:

def similarity(a, b)
  ta, tb = trigrams(a), trigrams(b)
  (ta & tb).size.to_f / (ta | tb).size
end

similarity("Manchestr", "Manchester")  # => ~0.8
similarity("Manchester", "Liverpool")  # => ~0.0

Rozmycie stało się nakładaniem zbiorów, a nakładanie zbiorów to coś, co możemy zindeksować.

Indeks odwrócony: szybkie znajdowanie kandydatów

Kluczowym spostrzeżeniem czyniącym to szybkim jest to, że nigdy nie porównujemy zapytania z każdym rekordem. Zamiast tego budujemy indeks odwrócony z każdego trigramu na listę rekordów go zawierających — dokładnie tak, jak wyszukiwarka mapuje słowa na dokumenty:

# trigram => [record_id, record_id, ...]
index = Hash.new { |h, k| h[k] = [] }

cities.each do |city|
  trigrams(city.name).each { |tri| index[tri] << city.id }
end

Teraz na zapytanie odpowiada się, wyszukując tylko trigramy, które zawiera zapytanie, zbierając rekordy dzielące którykolwiek z nich i licząc, ile każdy dzieli:

def search(query, index, limit: 20)
  counts = Hash.new(0)
  trigrams(query).each do |tri|
    index[tri].each { |id| counts[id] += 1 }
  end
  counts.sort_by { |_id, n| -n }.first(limit)
end

Rekord dzielący dziesięć trigramów z zapytaniem szereguje się wyżej niż ten dzielący dwa. Co kluczowe, rekordy nie dzielące nic z zapytaniem nigdy nie są dotykane — odwiedzamy tylko (zwykle mały) zbiór kandydatów osiągalny przez własne trigramy zapytania. To różnica między skanowaniem miliona wierszy a skanowaniem kilkuset.

Szeregowanie: tani filtr, precyzyjne sortowanie

Dwuetapowy wzorzec jest tym, co czyni całość zarazem szybką i dokładną:

  1. Filtruj indeksem trigramów — tanio, zbiorowo, redukuje milion do kilkudziesięciu.
  2. Szereguj tę krótką listę precyzyjną miarą — indeksem Jaccarda powyżej albo Levenshteinem, jeśli chcesz prawdziwej odległości edycyjnej — na co teraz cię stać, bo lista jest malutka.
def fuzzy_find(query, index, records_by_id, limit: 10)
  candidate_ids = search(query, index, limit: 100).map(&:first)
  candidate_ids
    .map     { |id| records_by_id[id] }
    .sort_by { |rec| -similarity(query, rec.name) }
    .first(limit)
end

To architektura stojąca za bibliotekami jak blurrily i za własnym dopasowaniem trigramowym Postgresa: szybki pre-filtr trigramowy zasilający precyzyjne przeszeregowanie. Gdy raz zobaczysz ten wzorzec, widzisz go wszędzie w wyszukiwaniu.

Doprowadzenie do gotowości produkcyjnej

Zabawkowy hash w pamięci działa dla tysięcy rekordów; prawdziwa usługa potrzebuje kilku rzeczy więcej:

  • Normalizacja liczy się bardziej niż algorytm. Zmniejsz wielkość liter, usuń interpunkcję, zwiń białe znaki, złóż akcenty (café → cafe) i rozważ transliterację do ASCII. Spójny normalizator zastosowany do obu — indeksowanego tekstu i zapytania — usuwa całą klasę błędów „czemu to się nie dopasowało”, zanim trigramy w ogóle wejdą do gry.
  • Próg podobieństwa powstrzymuje cię przed zwracaniem bzdur. Poniżej ~0,3 „dopasowanie” to zwykle szum; zwróć nic i pozwól UI to powiedzieć, zamiast pewnie oferować „Liverpool” dla „xyzzy”.
  • Trwałość i pamięć. Indeks w pamięci jest szybki, ale musi być odbudowany przy starcie i trzymany w synchronizacji przy zapisach. blurrily rozwiązuje to kompaktowym indeksem trigramowym na dysku zbudowanym w C dla szybkości; alternatywą, poniżej, jest pozwolić bazie być jego właścicielem.

Kiedy pozwolić Postgresowi to zrobić: pg_trgm

Zanim zbudujesz i będziesz utrzymywać osobną usługę dopasowania, sprawdź, czy twoja baza już tego nie potrafi — bo w wielu przypadkach potrafi. Rozszerzenie pg_trgm PostgreSQL implementuje dokładnie ten model trigramowy, z indeksem GiST lub GIN dla szybkości:

CREATE EXTENSION pg_trgm;
CREATE INDEX index_cities_on_name_trgm
  ON cities USING gin (name gin_trgm_ops);

-- rozmyte wyszukiwanie szeregowane podobieństwem, zindeksowane:
SELECT name, similarity(name, 'Manchestr') AS sim
FROM cities
WHERE name % 'Manchestr'           -- operator %: „dość podobne”
ORDER BY sim DESC
LIMIT 10;

Operator % filtruje według konfigurowalnego progu podobieństwa, a indeks czyni to szybkim, podczas gdy similarity() daje ci wynik do sortowania. Dla bardzo częstego przypadku — rozmytego dopasowania kolumny, którą już przechowujesz w Postgresie — to właściwa odpowiedź: żadnej dodatkowej usługi do wdrożenia, utrzymania i synchronizacji; dane i indeks żyją razem; a zapisy aktualizują indeks automatycznie. Po dedykowaną usługę Ruby/blurrily sięgamy tylko, gdy zbioru dopasowania nie ma w Postgresie albo gdy potrzebujemy indeksu odpiętego od głównej bazy ze względu na skalę lub opóźnienia.

Wniosek

Rozmyte dopasowanie wydaje się, jakby miało być trudne, a naiwne podejście (porównaj zapytanie ze wszystkim odległością edycyjną) naprawdę jest zbyt wolne, by było użyteczne. Sztuczka trigramowa przekształca problem: zamień łańcuchy w zbiory, użyj indeksu odwróconego, by tanio znaleźć nakładających się kandydatów, i przeszereguj krótką listę precyzyjnie. Zbuduj to w Ruby, gdy musisz, ale sięgnij najpierw po pg_trgm — przez większość czasu baza, którą już uruchamiasz, wykona całą robotę, zindeksowaną i zsynchronizowaną, za cenę jednego CREATE EXTENSION.

#ruby #postgresql #search