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.
Odpowiedzi:
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: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:
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 .
źródło