Semantic WebAnalyzer
wyszukiwarka semantycznych słów kluczowych

Zasada działania systemu indeksowania Google, cz.3 - Indeksowanie dokumentów z użyciem fraz i fraz powiązanych

Po zidentyfikowaniu dobrych fraz oraz informacji o frazach powiązanych i klastrach, system przechodzi do indeksowania dokumentów. W trakcie tego procesu aktualizowana też będzie na bieżąco lista dobrych fraz oraz klastry tematyczne fraz powiązanych. Dokumenty trafią w zależności od ich istotności do indeksu podstawowego lub wtórnego.

Część 3. - Indeksowanie dokumentów z użyciem fraz i fraz powiązanych

Proces ten obejmuje następujące etapy:

Etap 1: Dodawanie dokumentu do list pozycyjnych na podstawie znalezionych w nim dobrych fraz

• Przeszukiwanie dokumentu: Dokument jest analizowany słowo po słowie z użyciem okna frazy o długości n w sposób podobny, jak podczas zbierania potencjalnych i dobrych fraz w korpusie dokumentów.

• Identyfikacja fraz: W każdym oknie frazy identyfikowane są wszystkie dobre frazy.

• Aktualizacja indeksu: Dla każdej dobrej frazy wykonuje się następujące kroki:

  • do jej indeksu dodawany jest identyfikator dokumentu (np. URL),
  • znajdowane są dla niej wszystkie powiązane frazy.

Ponieważ każda dobra fraza w dokumencie przechodzi ten sam proces, uzyskuje się cały obraz hierarchii powiązań (pierwszy stopień, drugi itd.)

Informacje o tych powiązaniach przechowuje sie osobno w wektorach bitowych dla każdej znalezionej frazy. Wektor taki zawiera dwie pozycje: powiązania pierwszego stopnia i powiązania drugiego stopnia.

Warto zauważyć, że długości wektorów dla tej samej frazy są te same dla wszystkich dokumentów w indeksie, pozycje odpowiadają wszystkim zidentyfikowanym przez system powiązanym frazom i są uszeregowane zgodnie z wartością przyrostu informacji, a bity informują tylko o obecności w bieżącym dokumencie jakiejś frazy (1) lub jej braku (0). Dzięki temu można z łatwością porównywać wektory bitowe dla danej frazy pomiędzy wszystkimi dokumentami w indeksie, co jest bardzo przydatne w procesie wyszukiwania dokumentów w odpowiedzi na zapytanie.

Etap 2: Partycjonowanie indeksu

Aby zarządzać dużymi zbiorami danych i zwiększyć wydajność, system wprowadza mechanizm partycjonowania:

• Sortowanie fraz: Frazy w indeksie są ułożone na podstawie częstości ich występowania. Im częściej są znajdowane w dokumentach, tym wyżej znajdują się na przechowywanej liście fraz.

• Sortowanie dokumentów: Przy każdej frazie przechowuje się listę dokumentów, w których ją znaleziono. Dodatkowo każdemu dokumentowi na liście przypisywana jest ocena. Niezależnie od sposobu jej obliczania, dokumenty na liście zostają posortowane w porządku malejącym według tego wyniku, dzięki czemu najwyżej ocenione dokumenty są na początku listy.

  Takie wstępne uporządkowanie dokumentów jest szczególnie korzystne dla poprawy wydajności podczas wyszukiwania, ponieważ dla prostych zapytań nie trzeba będzie poddawać ostatecznej, szczegółowej analizie wykonywanej przez zasadniczy algorytm rankingowy wszystkich dokumentów w indeksie (a tych mogą być setki milionów), a jedynie te, które są najwyżej w pre-rankingu dla frazy związanej z zapytaniem.

  Algorytm pre-rankingu dokumentów opiera się na wykorzystaniu różnych parametrów i atrybutów, które ich dotyczączą, takich jak: PageRank, liczba odnośników przychodzących, wychodzących, długość dokumentu itp.

• Podział na indeksy: Najwyżej oceniane dokumenty dla danej frazy znajdują się teraz na początku listy wystąpień. Aby oszczędzać zasoby, lista wystąpień zostaje podzielona między indeks główny a indeks wtórny. Wpisy z listy wystąpień dotyczące pierwszych N (np. 32k) dokumentów pozostają przechowywane na serwerze głównym, podczas gdy wpisy dotyczące pozostałych dokumentów są przenoszone do indeksu wtórnego i usuwane z końca listy wystąpień głównego indeksu. Dzięki temu najważniejsze dokumenty są łatwo dostępne, a mniej istotne są przechowywane w sposób oszczędzający zasoby.

  Liczba dokumentów przechowywanych w indeksie głównym może być dodatkowo zwiększona dla fraz bardziej popularnych i zmniejszona dla mniej popularnych, co jest kolejnym zabiegiem optymalizującym efektywność systemu.

• Selektywne przechowywanie atrybutów dokumentów: Wybór atrybutów dokumentów przechowywanych w indeksie głównym dla każdego dokumentu na liście jest optymalizowany i maleje w kierunku końca listy wystąpień. Dokumenty, które są wysoko oceniane, będą miały przechowywane wszystkie lub większość atrybutów. Dokumenty znajdujące się bliżej końca listy będą miały przechowywane jedynie ograniczony zestaw atrybutów.

  Dla każdego z dokumentów z maksymalną ilością przechowywanych atrybutów zapisywane są:

  1. wynik oceny pre-rankingu
  2. całkowita liczba wystąpień frazy w dokumencie
  3. uporządkowana według pre-rankingu lista maksymalnie 10 000 dokumentów linkujących, które również zawierają frazę i wskazują na ten dokument, a dla każdego z nich zapisany jest też wynik jego pre-rankingu oraz tekst zakotwiczenia
  4. pozycja każdego wystąpienia frazy, a dla każdego wystąpienia zestaw flag wskazujących, czy znajduje się w tytule, nagłówku, jest pogrubione, w URL, w treści, na pasku bocznym, w stopce, w reklamie, zapisane wielkimi literami lub w innym rodzaju znacznika HTML

  Dla dokumentów z dalszych pozycji na liście i ograniczoną liczbą atrybutów zapisywane są pozycje 1-3.

  Dla dokumentów z najbardziej ograniczoną liczbą atrybutów zapisywany jest tylko wynik oceny pre-rankingu.

  W przypadku dokumentów najmniej istotnych, a więc przeniesionych do indeksu wtórnego, można bez utraty jakości wyszukiwania zredukować ilość przechowywanych danych do minimum - mogą to być jedynie np. numer dokumentu i jego URL

Aby zachować aktualność danych, kroki sortowania i podziału na indeksy są przeprowadzane podczas każdej iteracji indeksowania.

Rezultat indeksowania dokumentów z podziałem na indeksy główny oraz wtórny i selektywnym przechowywaniem atrybutów

Taki sposób przechowywania danych pozwala na zapisanie znacznie większej liczby wpisów na określonej ilości miejsca na dysku twardym w porównaniu do konwencjonalnych technik.

Po pierwsze, eliminacja informacji o miejscach wystąpień dla każdej frazy w dokumencie zapewnia około 50% redukcji wymaganego miejsca na dane, co w praktyce podwaja liczbę dokumentów, które można przechować.

Po drugie, podział list wystąpień między indeks główny a indeks wtórny oraz przechowywanie informacji o trafności (ocena w pre-rankingu) wyłącznie dla dokumentów znajdujących się w indeksie głównym przynosi dalsze znaczne oszczędności. Wiele fraz ma w swoich listach wystąpień ponad 100 000, a nawet 1 000 000 dokumentów. Przechowywanie informacji o trafności tylko dla wpisów w indeksie głównym eliminuje konieczność przechowywania tych danych dla dokumentów, które prawdopodobnie nie zostaną zwrócone podczas wyszukiwania. Ten aspekt zapewnia około dziesięciokrotne zwiększenie liczby dokumentów, które można przechowywać.

Na koniec, dodatkowe oszczędności (około 25-50% redukcji) uzyskuje się poprzez selektywne przechowywanie mniejszej ilości informacji w indeksie głównym dla mniej istotnych (niżej sklasyfikowanych) dokumentów w każdej liście wystąpień.

© 2024 - 2025 semanticwebanalyzer.pl