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

436

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?
Andrew Harry
źródło
1
Oto wersja VB.NET korektora pisowni Norvig. Może się to przydać, jeśli nie jest za późno!
Ralph Wiggum,
7
możliwy duplikat Jak wdrożyć „Czy miałeś na myśli”?
Kurt McKee,
Piszę na klawiaturze innej niż qwerty (Colemak), a funkcja nie jest w połowie tak sprytna. Z pewnością uczy się na podstawie zarejestrowanych par korekcji błędów, a tym samym dostosowuje się do qwerty. Zwykłe sprawdzanie pisowni działa dobrze na mojej klawiaturze, zgodnie z oczekiwaniami - odległość edycji ciągu znaków jest niezmienna.
Pułkownik Panic

Odpowiedzi:

366

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.

OscarRyz
źródło
Jak działa algorytm? W jaki sposób Google przechodzi od „Otrzymujemy miliardy wyszukiwań przy użyciu różnych haseł, a są to wyszukiwania„ na ”, dlatego ten termin musi być często błędną pisownią tego terminu”? Rozwiązali ten problem, ale interesuje mnie jak. Jak oceniają, że dwa wyszukiwania pochodzą od tego samego użytkownika, a które słowo jest „korektą” innego, i jak sumują to ponad miliardy wyszukiwań?
thomasrutter
51
Jeśli wszyscy zaczęli pisać z błędami „noc”… Myślę, że już na to wpadli, gdy ludzie szukali „Flickr”.
Max Lybbert
42
problem ze wszystkimi błędami w pisowni coś już się wydarzyło w znacznie poważniejszym sensie: spróbuj wpisać „fuscia” w Google. Google mówi „Czy chodziło Ci o fuschia?” Prawidłową pisownią jest w rzeczywistości „fuksja”, ale z jakiegoś powodu nikt nie potrafi jej poprawnie przeliterować. Problem jest jeszcze gorszy na Dictionary.com; jeśli wpiszesz „fuschia” w ich wyszukiwaniu, pojawi się komunikat „Brak wyników dla fuschia. Czy chodziło Ci o„ fuschia ”? (tj. czy miałeś na myśli to, co właśnie napisałeś?)
Daisy Sophia Hollman,
8
Nie sądzę, że używają tylko danych z błędami ortograficznymi - na pewno dzieje się pewna odległość Levenshteina lub podobne - szukaj „Plack” (i jednego lub więcej innych słów) i zawsze zmienia się na „czarny”, co jest bardzo mało prawdopodobne z błędem ortograficznym / typo
plusplus
4
@Jakub Myślę, że naprawili problem, odkąd napisałem ten komentarz ponad 4 lata temu. Rzeczywiście, Google również rozwiązał problem. Wyszukiwanie fuschia obejmuje automatycznie wyniki dla fuksji.
Daisy Sophia Hollman
104

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).

Davide Gualano
źródło
6
@Davide: „” „przykłady są w pythonie, ale jest jasne i proste do zrozumienia” „”: Nie rozumiem twojego użycia „ale”… powiedziałbym, biorąc pod uwagę styl pisania Python + Norvig, „jasne i prosty do zrozumienia ”to oczekiwany rezultat.
John Machin,
20
„Ale” było tam, ponieważ Harry w swoim pytaniu powiedział, że jest programistą VB.NET, więc założyłem, że nie był pewien języka Python.
Davide Gualano,
56

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).

Szere Dyeri
źródło
10

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.

Claudiu
źródło
7

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.

Jim Burger
źródło
6
Powiedzmy, że masz w sumie miliardy słów na stronach internetowych. Nie ma łatwego sposobu na indeksowanie odległości Levenshteina w celu szybkiego wyszukiwania bliskich dopasowań bez obliczania odległości Levenshtein kilka miliardów razy dla każdego zapytania. Dystans Levenshteina nie ma zatem większego zastosowania w tej sytuacji, a przynajmniej nie w pierwszym etapie, w którym Google musi zawęzić liczbę miliardów istniejących słów do tylko tych słów, które mogą być błędnie napisane w bieżącym słowie. Z pewnością może zastosować Levenshtein jako późniejszy krok, gdy już pobrał prawdopodobne dopasowania.
thomasrutter
6

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.

eulerfx
źródło
6

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.

Nicolas Dorier
źródło
4

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ń.

Geee
źródło
3

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.

seanb
źródło
3

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 ...

Paul Kapustin
źródło
2

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.

schonarth
źródło
1
Nikt nie wątpił, że Google ma wszystkie niezbędne dane, aby to zrobić, ale pytanie dotyczyło szczegółów, w jaki sposób Google opracował algorytm, aby to zrobić, z tak dużą ilością danych, w rozsądnym czasie. Dziennie mieliby setki wyszukiwań - w jaki sposób łatwo rozpoznają, czy wyszukiwane hasło jest „korektą pisowni” innego, ostatniego? Jakie czynniki powodują, że Google decyduje, że jeden termin jest błędny w pisowni innego? Są to szczegóły implementacji, które mogą być interesujące.
thomasrutter
2

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 :-)

Tomas Petricek
źródło
jak długo, aż google powstrzyma twojego bota od skrobania? - czy Google nawet tego nie zauważy?
Andrew Harry,
Nie sądzę, aby zauważyli, że wymagania / s nie są zbyt wysokie.
Mauricio Scheffer,
2

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.
amarjeetAnand
źródło
1

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

Jimit Patel
źródło
1

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.

Josep Valls
źródło
0

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


źródło
-1

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.

ewakened
źródło