Częściowe dopasowanie nazw w milionach rekordów

10

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.

bjan
źródło
1
Czy używasz programu SQL Server? Widzę, że oznaczyłeś to tagiem asp.net. Myślenie o możliwości złożenia CLR, która uniemożliwi ruch w sieci i pozwoli serwerowi SQL zarządzać pamięcią.
RubberChickenLeader
@WindRaven używamy zarówno SQL Server, jak i Oracle
bjan
1
Czy to nie ten sam problem z indeksowaniem sieci, który rozwiązuje Google?
candied_orange
@bjan gdzie są przechowywane nazwiska? czy są przechowywane w SQL Server?
RubberChickenLeader
Czego szukasz? 100 najlepszych nazw, które najlepiej pasują do danego zapytania?
Doc Brown,

Odpowiedzi:

6

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

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 .

svidgen
źródło
Właśnie przeszukałem rozmytą instrukcję obsługi Sphinx 2.2.11 i wygląda na to, że pasuje do dokładnego słowa, podczas gdy muszę częściowo dopasować słowa. Popraw mnie, jeśli się mylę.
bjan
@bjan Tak. Patrząc dalej na dokumentację, nie jestem pewien, czy rozmyte wyszukiwanie Sphinx jest dokładnie tym, czego szukasz. Może używać morfologii soundex . Ale, na podstawie swojej ostatniej edycji, to może chcesz się toczyć własną Ngram + wyszukiwanie string-odległość. I jak powiedziałem powyżej, poprawienie algorytmu i progów może zająć trochę czasu; ale nie jest to niemożliwe. A jeśli potrzebujesz tego poziomu elastyczności ...
svidgen
@bjan Oh, też całkowicie zapomniałem o Lucene . Nie jestem też pewien, czy robi to, czego potrzebujesz; ale jest dość popularny i warto na niego spojrzeć, zanim rzucisz własny. Dokumenty Lucene wspominają o rozmytym wyszukiwaniu i rankingach przy użyciu odległości Levenshteina.
svidgen