PageRank - serce algorytmu wyszukiwarki Google
niedziela, 26 listopada 2006
PageRank to metoda nadawania indeksowanym stronom internetowym określonej wartości liczbowej, oznaczającej jej jakość. Na podstawie tej wartości ustalany jest ranking znalezionych stron w wyszukiwarce dla każdego zapytania.
Algorytm PageRank został opracowany przez założycieli firmy Google Larry'ego Page'a i Sergeya Brina podczas ich studiów na Uniwersytecie Stanforda w 1998 roku.
PageRank jest rozwinięciem znanej od dawna heurystyki, wedle której jakość tekstu jest proporcjonalna do ilości tekstów, które się na niego powołują. Rozwinięcie zaproponowane przez autorów Google polegało na ważeniu sumy linków wskazujących na rozpatrywany tekst ich własną wartością PageRank. Innymi słowy: jeśli na dany tekst powołuje się artykuł, który sam ma wysoką ocenę, ma to większe znaczenie niż gdy na ten sam tekst powołuje się mało popularna strona.
Wartość PageRank można obliczyć, stosując następujący wzór:
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
Zakładamy, że do pliku A prowadzą odsyłacze ze stron od T1 do Tn, d to współczynnik, który może przyjmować wartości od 0 do 1, zazwyczaj ustawiany jest na 0,85, a C(A) to liczba odnośników prowadzących z dokumentu A. Skąd wziąć wartości PR dla stron składowych? Chcąc je obliczyć, powstanie układ 4,3 mld równań z 4,3 mld niewiadomych. Jego rozwiązanie jest oczywiście niemożliwe. Dlatego nie da się precyzyjnie określić wartości PageRanku dla wszystkich dokumentów. Nie ma jednak takiej potrzeby. Internet bowiem cały czas się zmienia. Problem rozwiązano następująco: na początku wszystkim dokumentom nadano identyczne wartości PR, później na tej podstawie obliczono współczynniki i zaczęto obliczanie od nowa. W ten krokowy sposób można uzyskać współczynniki bliskie rzeczywistości.
Metody zbliżone do algorytmu PageRank są obecnie coraz śmielej wprowadzane do mechanizmów innych wyszukiwarek internetowych. Szczegóły właściwego algorytmu nigdy nie zostały upublicznione i są jednymi ze ściśle strzeżonych tajemnic Google. Do tego są najprawdopodobniej sukcesywnie zmieniane w celu dopracowania mechanizmu. Wszystkie informacje dostępne jawnie przedstawiają jedynie wzorcową wersję algorytmu stosowanego w wyszukiwarce Google. Ponadto PageRank jest tylko jednym z wielu elementów decydujących o ostatecznej pozycji danej strony wśród wyników wyszukiwania.
Autor:Tomasz Dziedzic o 18:23
Architektura systemu Google
wtorek, 14 listopada 2006
Większość systemu została napisana w C lub C++ i działa na komputerach wyposażonych w system Linux. Roboty (crawlers) mają za zadanie pobierać strony WWW, których adres otrzymują od Serwera URL. Następnie skopiowane już pliki zostają skompresowane i wysłane do magazynu dokumentów (StoreServer). Każdy zbiór ma przydzielony unikatowy numer ID. Funkcje indeksowania i sortowania są wykonywane przez Indexer oraz Sorter. Pierwszy moduł pobiera dane z przechowalni, dekompresuje zapisane tam dokumenty i przetwarza je. Każdy plik jest przekształcany w rekordy nazywane trafieniami (hits). Znajdują się w nich: słowo, jego pozycja w dokumencie i rozmiar fontu.
Tak utworzone rekordy Indexer umieszcza w cylindrach. Drugim ważnym zadaniem wykonywanym przez Indexer jest przetwarzanie wszystkich odnośników występujących na pobranych przez Szperacza stronach i zapisywanie ich do Kotwicy. Znajdujące się tam dane zawierają informację, dokąd i skąd prowadzi odsyłacz, oraz opis, który przy nim występuje.
URL Resolver czyta rekordy z Kotwic, zamienia względne adresy URL na absolutne oraz nadaje im ID. Powiązane w ten sposób dane umieszczane są przez Indexera w Cylindrach i tam przechowywane. Dodatkowo URLresolver tworzy bazę odnośników (links), które są parą numerów ID. Służy ona właśnie do generowania rankingu stron (PageRank). Sorter pobiera Cylindry, które są ułożone rosnąco względem ID, i sortuje je ponownie, tworząc w ten sposób indeks odwrotny.
Najbliżej użytkownika jest Szukacz (Searcher), który jest uruchamiany przez serwer WWW, a następnie, korzystając z leksykonu utworzonego przez Indexer, odwrotnego indeksu oraz modułu wyliczającego PageRank odpowiada na zapytania użytkowników.
Potężnym wyzwaniem jest pobieranie stron, a Crawler jest najczulszym punktem w całym systemie Google'a. Jego zadaniem jest odwiedzanie setek tysięcy dokumentów. Szperacze są zazwyczaj uruchamiane po kilka jednocześnie, a każdy utrzymuje około 300 połączeń naraz. Z obsługą takiego ruchu nie radzą sobie serwery DNS. Dlatego każdy Szperacz dysponuje własną pamięcią DNS, dzięki czemu nie musi za każdym razem wysyłać zapytań do serwerów nazw. Pomimo szczegółowego opracowania systemu na etapie projektowania podczas pracy Szperaczy zdarzały się nieprzewidziane sytuacje, jak chociażby próba pobrania trwającej gry online, co generowało dużą ilość niepotrzebnych informacji.
Sprzęt, na którym działa system Google, to nie jeden potężny serwer, a farma złożona z około 15 000 komputerów klasy PC (najprawdopodobniej największy w tej chwili system komputerowy tego typu na świecie). Całość pracuje z systemem Linux. Część tych maszyn zajmuje się pobieraniem stron WWW (aplikacja Crawler). Zwykle wygląda to tak, że na początku połączenie ze skanowanym serwisem nawiązuje jeden lub dwa roboty. Następnego dnia pojawia się ich 8 lub 9, a każdy Szperacz odwiedza około 8 stron na serwerze. Ponownie zjawiają się za około tydzień, później znikają na dłużej. Jednak pobrana strona nie pojawia się od razu w rezultatach wyszukiwania. Z reguły można ją tam znaleźć po około miesiącu od wizyty botów. Taki cykl nazywany jest przez fanów wyszukiwarki "Google Dance" i trwa właśnie około 30 dni - po tym czasie informacje w bazie Google'a zostają odświeżone.
Kluczem do sukcesu jest spowodowanie, żeby wyniki wyszukiwania były jak najbardziej zbliżone do oczekiwań użytkownika, próbującego odnaleźć w Internecie potrzebną mu informację. Jak to osiągnąć? Google najpierw tworzy listę dokumentów, w których słowo kluczowe zostało użyte. Wyraz może wystąpić w tytule, URL-u, treści strony zapisany małą czcionką, wytłuszczony itp. Każde z tych miejsc lub atrybutów ma przyznaną określoną wagę, co w powiązaniu z systemem PageRank daje ostateczny wynik i powoduje umieszczenie strony na odpowiednim miejscu w rezultatach szukania.
http://www.chip.pl/arts/archiwum/n/sub/articlear_106902.html
Autor:Tomasz Dziedzic o 14:20
Etykiety: Google