Częściowe dopasowanie nazw w milionach rekordów

Opracowaliśmy aplikację internetową do dopasowywania nazw. Działa poprzez dzielenie nazw na części, a wartość Soundex każdej części jest przechowywana w bazie danych. Wskaźnik odległości Levenshteina służy do zastosowania procentowego dopasowania dźwięku, a także pisowni w odniesieniu do danego imienia.

W czasie wykonywania ładujemy wszystkie rekordy do pamięci i stosujemy odległość Levenshteina do wszystkich wartości Soundex i pisowni wszystkich części wszystkich nazw.

Na początku działało to dobrze, ponieważ było ich maksymalnie 20 tysięcy, ale teraz jeden z naszych klientów ma 30 milionów nazwisk. Ładowanie tej ogromnej listy do pamięci dla każdego żądania i stosowanie tego rodzaju dopasowywania to żałosne podejście, wymagające dużej ilości pamięci i czasu wykonania.

Szukamy sugestii, aby w najbliższej przyszłości przeszukać bazę danych 30 milionów lub więcej rekordów z procentowym dopasowaniem dźwięku i pisowni.

Podstawowa funkcjonalność

Użytkownik końcowy wprowadza nazwę do dopasowania i minimalny procent. Powinniśmy pokazywać wszystkie te nazwy w bazie danych, dla których dowolna część nazwy pasuje do dowolnej części podanej nazwy, aż do podanego procentu. Pełna nazwa nie musi być dopasowana, każda część, jeśli pasuje do procentu, jest sukcesem. Na przykład.

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Obie części obu nazw nie pasują dokładnie, ale do pewnego stopnia, załóżmy, że 80%, więc jeśli użytkownik wprowadzi 80%, nazwa w DB musi być pokazana jako pasująca nazwa.

Nie znając pełnych szczegółów tego, czego potrzebujesz, prawdopodobnie chcesz wykonać jedną z następujących czynności:

• Użyj istniejącego narzędzia wyszukiwania, takiego jak Sfinks lub Lucene
• Wykonaj przybliżone dopasowanie n-gram

Nie do końca wiem, co obejmuje instalacja i konfiguracja sfinksa; ale mam wrażenie, że możesz wskazać bazę danych, wskazać pola, które mają zostać zindeksowane, jak zważyć wyniki, a otrzymasz z powrotem uporządkowaną listę pasujących rekordów.

W przypadku rzeczy istotnych dla użytkownika lub kluczowych zadań skorzystaj z istniejącego narzędzia wyszukiwania.

Jeśli czujesz się akademicki ... Zagraj w ngrams:

Tabela przeglądowa ngrams może służyć jako początkowy zestaw potencjalnych dopasowań, a odległości Levenshteina można używać do przycinania i sortowania wyników.

Zakładając, że chcesz wyszukiwać people, możesz zrobić coś takiego:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Możesz okresowo odbudowywać swoje ngramy lub budować je w locie. Tak czy inaczej prosty, naiwny algorytm wyszukiwania może wyglądać następująco:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Korzystając z czegoś bardzo podobnego do tego (ale z nieco większym strojeniem „popularności” ngram, czarnymi listami, białymi listami itp.), Widziałem tego rodzaju algorytm w sposób burzliwy łączący rekordy między zbiorami danych, a także ułatwiający niestandardowe wyszukiwanie rozmyte narzędzia i bieżące wysiłki w zakresie usuwania duplikatów.

Teraz, w moim przypadku, nie pasowałem do milionów rekordów, chciałem wybrać najlepsze możliwe połączenia dwóch zestawów danych w kolejności setek tysięcy rekordów. Chcieliśmy, aby działał dość szybko - w ciągu kilku minut. (Szybko, co to jest 100 000 * 100 000?) I odnieśliśmy sukces.

Tak więc, przy odpowiednim strojeniu, tego rodzaju rzeczy mogą być szybkie i skuteczne. Ostatecznie byliśmy w stanie wyprodukować scalony zestaw na skromnej, opatrzonej datą dwurdzeniowej maszynie w ciągu kilku minut, a „wątpliwe” scalenia są automatycznie oznaczane do ręcznej oceny. Ale zajęło dużo czasu znalezienie optymalnego miejsca na popularność / trafność ngram oraz odpowiednich progów odległości łańcuchów, czarnych list i białych list ...

TO POWIEDZIAŁO , naprawdę możesz zostać wciągnięty w dziurę pracującą nad tymi rzeczami. Do wszelkich rzeczy na poziomie produkcji w świecie rzeczywistym powinieneś na ogół korzystać z dobrze ugruntowanego narzędzia, które zostało już stworzone i zoptymalizowane do tego rodzaju wyszukiwania.

Jak Sfinks lub Lucene .