Wyszukiwanie Levenshtein

Question

Pracuję na stronie, która sprzedaje, powiedzmy, rzeczy i oferuje "wyszukiwanie dostawców". W tym wyszukiwaniu wpisujesz swoje miasto, kod pocztowy, region i odległość (w km lub milach), a następnie witryna podaje listę dostawców.

Aby to zrobić, mam bazę danych z dostawcami. W formularzu, aby zapisać tych dostawców, podajesz ich pełny adres, a po kliknięciu przycisku Zapisz tworzona jest prośba o mapy google w celu uzyskania ich szerokości i długości geograficznej.

Kiedy ktoś wykonuje wyszukiwanie, patrzę na stół, na którym przechowuję wszystkie wyszukiwane hasła i ich wartości lat/lng. Ta tabela wygląda

+--------+-------+------+ 
| term | lat | lng | 
+--------+-------+------+ 

Więc pierwsze zapytanie jest czymś bardzo prostym

select lat, lng from my_search_table where term = "the term" 

Jeśli znajdę rezultatu, szukaj Następnie z ładnym metody dla wszystkich sprzedawców w zakresie użytkownik chce i wydrukuj wynik na mapie.

Jeśli nie znajdę wyniku, szukam z funkcją levenshtein, ponieważ ludzie piszący bruxelle lub bruxelle zamiast bruxelles są czymś bardzo powszechnym i nie chcę ciągle prosić o mapy google (I również mam kolumnę "ile czasu przeszukano" w moim stoliku, aby uzyskać pewne statystyki)

Tak więc proszę o moje_search_time bez klauzuli where i przechodzę przez wszystkie wyniki, aby uzyskać najmniejszą odległość od levensthein. Jeśli najmniejszy wynik jest większy niż 2, żądam współrzędnych z mapy google.

Oto mój problem. W przypadku niektórych krajów (mamy kilka witryn na całym świecie), my_search_table ma 15-20k + wpisów ... a php nie (naprawdę) lubi zapętlać się na takich danych (co doskonale rozumiem), a moja prośba wchodzi w php timeout . Mogłabym zwiększyć ten limit czasu, ale problem będzie taki sam w ciągu kilku miesięcy.

Próbowałem więc funkcji MySQL z levensthein (znalezionej na stackoverflow btw), ale jest również bardzo powolna.

Moje pytanie brzmi: "czy istnieje sposób na szybkie przeprowadzenie wyszukiwania nawet na bardzo dużych zestawach danych?"

Answer 1

Moja propozycja opiera się na trzech rzeczach:

• Po pierwsze, zestaw danych jest duży. Oznacza to - jest to: wystarczająco duży, aby odrzucić pomysł "wybierz wszystko" + "uruchom w aplikacji PHP"
• Po drugie, masz kontrolę nad swoją bazą danych. W związku z tym można dostosować pewne aspekty związane z architekturą.
• Wreszcie, najważniejsza jest wydajność zapytań SELECT, a wydajność dodawania nowych danych nie ma znaczenia.

Rzecz nie można wykonać szybkiego wyszukiwania Levenshteina ponieważ Levenshteina sobie jest bardzo powolna. Chodzi mi o to, że obliczanie dystansu dzielącego odległość jest powolne. W związku z tym nie można rozwiązać problemu tylko za pomocą "inteligentnego wyszukiwania". Będziesz musiał przygotować trochę danych.

Możliwe rozwiązanie: utwórz indeks grupy i przypisz go podczas dodawania/aktualizacji danych. Oznacza to - będziesz przechowywać dodatkową kolumnę, która będzie przechowywać niektóre hash (np. Numeryczne). Podczas dodawania nowych danych, będziesz:

• Wykonaj wyszukiwanie z odległości Levenshteina (na które mogą wykorzystać aplikację lub funkcję, która to już (już wymienionych) w stosunku do wszystkich rekordów w tabeli przed wstawionych danych
• Ustaw indeks grupy dla nowego wiersza na wartość indeksu, który znalazł wiersze w poprzednim kroku:
• Jeśli nic nie znaleziono, ustaw nową wartość indeksu grupowego (jest to "pierwszy wiersz i nie ma jeszcze podobnych wierszy)", różnić się od wartości indeksu grupy, które są już obecne w tabeli

Aby wyszukać żądane wiersze, musisz po prostu wybrać wiersze z tą samą wartością indeksu grupy. To oznacza, że ​​twoje zapytania będą bardzo szybkie. Ale - tak, spowoduje to ogromne obciążenie podczas dodawania/zmieniania danych. W związku z tym nie ma zastosowania w przypadku, gdy wykonanie aktualizacji/wstawienia ma znaczenie.

Answer 2

można spróbować funkcji MySQL SOUNDS LIKE

SELECT lat, lng FROM my_search_table WHERE term SOUNDS LIKE "the term" 

Answer 3

Można użyć KD-drzewo lub potrójny drzewa, aby przyspieszyć wyszukiwanie. Chodzi o to, aby użyć wyszukiwania binarnego.