Jednym z faktów, które wydały mi się zabawne, jest to, że Google jest w rzeczywistości prowadzony przez bioinformatykę („okej, uważam to za zabawne, ponieważ jestem bioinfekcją… rzecz). Pozwól mi wyjaśnić.
Bioinformatycy wcześnie musieli bardzo szybko przeszukiwać małe teksty w gigantycznych strunach. Dla nas „gigantyczna struna” to oczywiście DNA. Często nie jest to pojedynczy DNA, ale baza danych zawierająca kilka DNA różnych gatunków / osobników. Małe teksty to białka lub ich genetyczny odpowiednik, gen. Większość pierwszych prac biologów obliczeniowych ograniczała się do znalezienia homologii między genami. Odbywa się to w celu ustalenia funkcji nowo odkrytych genów poprzez odnotowanie podobieństw do genów, które są już znane.
Teraz te ciągi DNA stają się rzeczywiście bardzo duże i (stratne!) Wyszukiwanie musi być wykonywane niezwykle wydajnie. Większość współczesnej teorii wyszukiwania ciągów została więc rozwinięta w kontekście biologii obliczeniowej.
Jednak jakiś czas temu konwencjonalne wyszukiwanie tekstu zostało wyczerpane. Potrzebne było nowe podejście, które umożliwi przeszukiwanie dużych ciągów w czasie podliniowym, to znaczy bez patrzenia na każdy pojedynczy znak. Odkryto, że można to rozwiązać, wstępnie przetwarzając duży ciąg i budując na nim specjalną strukturę danych indeksu. Zaproponowano wiele różnych takich struktur danych. Każdy ma swoje mocne i słabe strony, ale jest jeden, który jest szczególnie niezwykły, ponieważ umożliwia wyszukiwanie w ciągłym czasie. Teraz, jeśli chodzi o rzędy wielkości, w których działa Google, nie jest to już do końca prawdą, ponieważ należy wziąć pod uwagę równoważenie obciążenia między serwerami, przetwarzanie wstępne i inne wyrafinowane rzeczy.
Ale w istocie tak zwany indeks q-gramów umożliwia wyszukiwanie w stałym czasie. Jedyna wada: struktura danych robi się śmiesznie duża. Zasadniczo, aby umożliwić wyszukiwanie ciągów zawierających do q znaków (stąd nazwa), wymaga tabeli zawierającej jedno pole dla każdej możliwej kombinacji liter q (to znaczy q S , gdzie S jest rozmiarem alfabetu powiedzmy 36 (= 26 + 10)). Dodatkowo musi istnieć jedno pole dla każdej pozycji litery w indeksowanym ciągu (lub w przypadku Google, dla każdej witryny internetowej).
Aby złagodzić sam rozmiar, Google prawdopodobnie użyje wielu indeksów (w rzeczywistości robi to , aby zaoferować usługi takie jak korekta pisowni). Te najwyższe nie będą działać na poziomie postaci, ale zamiast tego na poziomie słów. Zmniejsza to q, ale sprawia, że S jest nieskończenie większe, więc będą musieli używać tablic mieszania i kolizji, aby poradzić sobie z nieskończoną liczbą różnych słów.
Na następnym poziomie te zaszyfrowane słowa będą wskazywały na inne struktury danych indeksu, które z kolei będą oznaczać znaki skrótu wskazujące strony internetowe.
Krótko mówiąc, te struktury danych indeksu q- gramów są prawdopodobnie najbardziej centralną częścią algorytmu wyszukiwania Google. Niestety, nie ma dobrych artykułów nietechnicznych wyjaśniających, jak działają indeksy q -gram. Jedyna znana mi publikacja zawierająca opis działania takiego indeksu to… niestety moja praca licencjacka .