W jaki sposób Google „miałeś na myśli?” Algorytm działa?

Tworzę wewnętrzną stronę internetową dla narzędzia do zarządzania portfelem. Istnieje wiele danych tekstowych, nazw firm itp. Byłem pod wielkim wrażeniem zdolności wyszukiwarek do bardzo szybkiego reagowania na zapytania za pomocą „Czy miałeś na myśli: xxxx”.

Muszę być w stanie inteligentnie przyjąć zapytanie użytkownika i odpowiedzieć nie tylko nieprzetworzonymi wynikami wyszukiwania, ale także słowem „Czy miałeś na myśli?” odpowiedź, gdy istnieje wysoce prawdopodobna odpowiedź alternatywna itp

[Rozwijam się w ASP.NET (VB - nie miej mi tego za złe!]]

AKTUALIZACJA: OK, jak mogę to naśladować bez milionów „nieopłaconych użytkowników”?

• Generować literówki dla każdego „znanego” lub „poprawnego” terminu i wyszukiwać?
• Jakaś inna bardziej elegancka metoda?

Oto wyjaśnienie bezpośrednio ze źródła (prawie)

Szukaj 101!

o min 22:03

Warte obejrzenia!

Zasadniczo i według byłego CTO Google'a Douglasa Merrilla wygląda to tak:

1) W Google wpisujesz (błędnie) słowo

2) Nie znajdziesz tego, co chciałeś (nie klikaj żadnych wyników)

3) Zdajesz sobie sprawę, że źle napisałeś słowo, więc przepisujesz je w polu wyszukiwania.

4) Znajdziesz to, co chcesz (klikasz w pierwszych linkach)

Ten wzorzec pomnożony miliony razy pokazuje, jakie są najczęstsze błędy ortograficzne i jakie są najczęstsze poprawki.

W ten sposób Google może niemal natychmiast zaoferować korekcję pisowni w każdym języku.

Oznacza to również, że z dnia na dzień wszyscy zaczną literować noc, ponieważ „nigth” google sugeruje to słowo.

EDYTOWAĆ

@ThomasRutter: Douglas opisuje to jako „statystyczne uczenie maszynowe”.

Wiedzą, kto poprawia zapytanie, ponieważ wiedzą, które zapytanie pochodzi od którego użytkownika (za pomocą plików cookie)

Jeśli użytkownicy wykonają zapytanie, a tylko 10% użytkowników kliknie wynik, a 90% cofa się i wpisuje kolejne zapytanie (z poprawionym słowem), a tym razem 90% kliknie wynik, to wiedzą, że znaleźli korekta.

Mogą również wiedzieć, czy są to „powiązane” zapytania dwóch różnych, ponieważ mają informacje o wszystkich wyświetlanych linkach.

Co więcej, teraz włączają kontekst do sprawdzania pisowni, więc mogą nawet sugerować inne słowa w zależności od kontekstu.

Zobacz prezentację Google Wave (@ 44m 06s), która pokazuje, w jaki sposób uwzględnia się kontekst, aby automatycznie poprawić pisownię.

Tutaj wyjaśniono, jak działa przetwarzanie języka naturalnego.

I wreszcie tutaj jest niesamowite demo tego, co można zrobić, dodając do miksu automatyczne tłumaczenie maszynowe (@ 1h 12m 47s).

_{Dodałem kotwice minut i sekund do filmów, aby przejść bezpośrednio do treści, jeśli nie działają, spróbuj ponownie załadować stronę lub ręcznie przewiń do znaku.}

Znalazłem ten artykuł jakiś czas temu: Jak napisać korektor pisowni , napisany przez Petera Norviga (dyrektor ds. Badań w Google Inc.).

To ciekawa lektura na temat „korekty pisowni”. Przykłady są w języku Python, ale są jasne i łatwe do zrozumienia, i myślę, że algorytm można łatwo przetłumaczyć na inne języki.

Poniżej znajduje się krótki opis algorytmu. Algorytm składa się z dwóch etapów: przygotowania i sprawdzania słów.

Krok 1: Przygotowanie - konfiguracja bazy danych słów

Najlepiej jest, jeśli możesz użyć rzeczywistych wyszukiwanych słów i ich występowania. Jeśli tego nie masz, możesz użyć dużego zestawu tekstu. Policz występowanie (popularność) każdego słowa.

Krok 2. Sprawdzanie słów - znajdowanie słów podobnych do sprawdzanego

Podobne oznacza, że ​​odległość edycji jest niska (zwykle 0-1 lub 0-2). Odległość edycji to minimalna liczba wstawek / usunięć / zmian / zamian potrzebnych do przekształcenia jednego słowa w drugie.

Wybierz najpopularniejsze słowo z poprzedniego kroku i zaproponuj je jako poprawkę (jeśli inne niż samo słowo).

Teorię algorytmu „czy miałeś na myśli” można znaleźć w rozdziale 3 wstępu do wyszukiwania informacji. Jest dostępny online za darmo. Punkt 3.3 (strona 52) dokładnie odpowiada na twoje pytanie. Aby konkretnie odpowiedzieć na twoją aktualizację, potrzebujesz tylko słownika słów i nic więcej (w tym milionów użytkowników).

Hmm ... Myślałem, że Google użył ich ogromnego zbioru danych (Internetu), aby wykonać poważne NLP (przetwarzanie języka naturalnego).

Na przykład mają tak dużo danych z całego Internetu, że mogą policzyć, ile razy występuje sekwencja trzech słów (znana jako trigram ). Jeśli więc zobaczą zdanie: „koncert Pink Frugr”, zobaczą, że ma kilka hitów, a następnie znajdą najbardziej prawdopodobny „różowy * koncert” w swoim ciele.

Najwyraźniej po prostu zmieniają to, co mówił Davide Gualano, więc zdecydowanie przeczytaj ten link. Google używa oczywiście wszystkich stron internetowych, które zna, jako korpusu, dzięki czemu jego algorytm jest szczególnie skuteczny.

Domyślam się, że używają kombinacji algorytmu odległości Levenshteina i gromadzonych mas danych dotyczących uruchomionych wyszukiwań. Mogą pobrać zestaw wyszukiwań, które mają najkrótszą odległość Levenshteina od wprowadzonego ciągu wyszukiwania, a następnie wybrać ten, który ma najwięcej wyników.

Zwykle produkcyjny korektor pisowni wykorzystuje kilka metod w celu zapewnienia sugestii pisowni. Niektóre są:

• Wybierz sposób ustalenia, czy wymagana jest korekta pisowni. Mogą one obejmować niewystarczające wyniki, wyniki, które nie są wystarczająco szczegółowe lub dokładne (według niektórych miar), itp. Następnie:

• Użyj dużej części tekstu lub słownika, w których wszystkie lub większość z nich jest poprawnie napisana. Można je łatwo znaleźć w Internecie, w miejscach takich jak LingPipe . Następnie, aby określić najlepszą sugestię, szukasz słowa, które jest najbliższym dopasowaniem na podstawie kilku miar. Najbardziej intuicyjny jest podobny znak. Badania i eksperymenty wykazały, że dopasowanie sekwencji dwóch lub trzech znaków działa lepiej. (bigramy i trygramy). Aby jeszcze bardziej poprawić wyniki, zważ wyższy wynik po meczu na początku lub na końcu słowa. Ze względu na wydajność zindeksuj wszystkie te słowa jako trygramy lub bigramy, aby podczas wykonywania wyszukiwania konwertować na n-gram i wyszukiwać za pomocą tablicy hashtable lub trie.

• Użyj heurystyki związanej z potencjalnymi błędami klawiatury na podstawie lokalizacji postaci. Tak więc „hwllo” powinno być „hello”, ponieważ „w” jest zbliżone do „e”.

• Użyj klawisza fonetycznego (Soundex, Metaphone), aby zindeksować słowa i wyszukać możliwe poprawki. W praktyce zwykle daje to gorsze wyniki niż stosowanie indeksowania n-gram, jak opisano powyżej.

• W każdym przypadku musisz wybrać najlepszą korektę z listy. Może to być metryka odległości, taka jak lewenshtein, metryka klawiatury itp.

• W przypadku wyrażenia składającego się z wielu słów tylko jedno słowo może być błędnie zapisane. W takim przypadku możesz użyć pozostałych słów jako kontekstu przy określaniu najlepszego dopasowania.

Użyj odległości Levenshteina , a następnie utwórz drzewo metryczne (lub wąskie drzewo), aby zindeksować słowa. Następnie uruchom zapytanie 1-Nearest Neighbor, a otrzymasz wynik.

Google najwyraźniej sugeruje zapytania z najlepszymi wynikami, a nie z tymi, które są poprawnie napisane. Ale w tym przypadku prawdopodobnie poprawienie pisowni byłoby bardziej wykonalne. Oczywiście możesz przechowywać pewną wartość dla każdego zapytania, w oparciu o pewną miarę tego, jak dobre wyniki zwraca.

Więc,

1. Potrzebujesz słownika (angielski lub na podstawie danych)

2. Wygeneruj kratę wyrazów i oblicz prawdopodobieństwo za pomocą słownika.

3. Dodaj dekoder, aby obliczyć minimalną odległość błędu za pomocą kratki. Oczywiście powinieneś zadbać o wstawianie i usuwanie przy obliczaniu odległości. Zabawne jest to, że klawiatura QWERTY maksymalizuje odległość, jeśli naciskasz klawisze blisko siebie (cae zmieniałby samochód, cay zmieniałby kota)

4. Zwraca słowo o minimalnej odległości.

5. Następnie możesz porównać to z bazą danych zapytań i sprawdzić, czy istnieją lepsze wyniki dla innych bliskich dopasowań.

Oto najlepsza odpowiedź, jaką znalazłem: korektor pisowni zaimplementowany i opisany przez dyrektora ds. Badań Google Petera Norviga.

Jeśli chcesz przeczytać więcej na temat teorii, możesz przeczytać jego rozdział w książce .

Idea tego algorytmu opiera się na statystycznym uczeniu maszynowym.

Widziałem coś w tym kilka lat temu, więc mogło się to zmienić, ale najwyraźniej zaczęli to od analizy dzienników dla tych samych użytkowników, którzy w bardzo krótkim czasie przesyłali bardzo podobne zapytania, i korzystali z uczenia maszynowego w oparciu o to, jak użytkownicy poprawili sami.

Domyślam się, że tak

1. szukaj słów
2. jeśli nie zostanie znaleziony, użyj jakiegoś algorytmu, aby spróbować „odgadnąć” słowo.

Może to być coś z AI, jak sieć Hopfield lub sieć propagacji wstecznej, lub coś innego „identyfikacja odcisków palców”, przywracanie uszkodzonych danych lub korekty pisowni, jak już wspomniał Davide ...

Prosty. Mają mnóstwo danych. Mają statystyki dla każdego możliwego terminu, na podstawie tego, jak często jest ono wyszukiwane i jakie odmiany zwykle dają wyniki, które klikają użytkownicy ... więc kiedy widzą, że wpisujesz częstą literówkę dla wyszukiwanego terminu, proponują bardziej typowa odpowiedź.

Właściwie, jeśli błąd w pisowni jest najczęściej wyszukiwanym terminem, algorytm weźmie go za właściwy.

odnośnie twojego pytania, jak naśladować zachowanie bez mnóstwa danych - dlaczego nie wykorzystać ton danych zebranych przez Google? Pobierz wyniki wyszukiwania Google dla błędnie napisanego słowa i wyszukaj „Czy miałeś na myśli:” w kodzie HTML.

Chyba w dzisiejszych czasach nazywa się to mashup :-)

Oprócz powyższych odpowiedzi, na wypadek, gdybyś chciał szybko coś zaimplementować, oto sugestia -

Algorytm

Implementację i szczegółową dokumentację tego algorytmu można znaleźć na GitHub .

• Utwórz kolejkę priorytetową za pomocą komparatora.
• Utwórz drzewo wyszukiwania Ternay i wstaw wszystkie angielskie słowa (z postu Norviga ) wraz z ich częstotliwościami.
• Zacznij przemierzać TST i dla każdego słowa napotkanego w TST oblicz jego Levenshtein Distance ( LD ) od input_word
• Jeśli LD ≤ 3, umieść go w kolejce priorytetowej.
• W końcu wyodrębnij 10 słów z kolejki priorytetowej i wyświetl.

Chcesz powiedzieć sprawdzanie pisowni? Jeśli jest to moduł sprawdzania pisowni, a nie cała fraza, mam link o sprawdzaniu pisowni, w którym algorytm jest rozwijany w pythonie. Sprawdź ten link

Tymczasem pracuję również nad projektem obejmującym wyszukiwanie w bazach danych za pomocą tekstu. Myślę, że to rozwiązałoby twój problem

To stare pytanie i jestem zaskoczony, że nikt nie sugerował OP za pomocą Apache Solr.

Apache Solr to wyszukiwarka pełnotekstowa, która oprócz wielu innych funkcji zapewnia także sprawdzanie pisowni i sugestie dotyczące zapytań. Z dokumentacji :

Domyślnie, sprawdzania pisowni Lucene sortują sugestie najpierw według wyniku z obliczenia odległości ciągu, a następnie według częstotliwości (jeśli jest dostępna) sugestii w indeksie.

Istnieje specjalna struktura danych - drzewo wyszukiwania trójskładnikowego - które naturalnie obsługuje dopasowania częściowe i dopasowania bliskie sąsiedztwa.

Najprostszym sposobem, aby to rozgryźć, jest programowanie dynamiczne Google.

Jest to algorytm zapożyczony z Information Retrieval i jest szeroko stosowany we współczesnej bioinformatyce, aby zobaczyć, jak podobne są dwie sekwencje genów.

Optymalne rozwiązanie wykorzystuje dynamiczne programowanie i rekurencję.

Jest to bardzo rozwiązany problem z wieloma rozwiązaniami. Wystarczy google, aż znajdziesz jakiś kod open source.