Semantic WebAnalyzer
wyszukiwarka semantycznych słów kluczowych

Zasada działania systemu indeksowania Google, cz.1 - Identyfikacja fraz

System indeksowania Google jest skomplikowanym mechanizmem służącym do efektywnego przetwarzania, organizacji i wyszukiwania informacji w dużych zbiorach dokumentów (stron internetowych). Jego działanie składa się z kilku części, które umożliwiają indeksowanie treści w sposób zoptymalizowany do precyzyjnego i błyskawicznego odpowiadania na zapytania użytkowników.

Na wstępie system musi wypełnić się danymi, które w procesie wyszukiwania będą służyły do określania w jakim stopniu dokumenty pasują do zapytań i intencji użytkowników.

Tymi danymi są najbardziej istotne frazy oraz ich wzajemne relacje, tworzące charakterystyczne powiązania semantyczne. Dzięki nim system będzie mógł określać tematykę dokumentu, jego zgodność z zapytaniem, a nawet jakość treści, a także rozpoznawać podobieństwa i różnice między dokumentami. Zebrane też zostaną dane, które będzie można użyć jako podpowiedzi do wyszukiwania.

Część 1. - Identyfikacja fraz

Proces identyfikacji fraz służy do określania, które frazy są przydatne do indeksowania oraz wyszukiwania dokumentów, a które nie. Składa się z trzech głównych etapów:

Etap 1: Zbieranie potencjalnych i dobrych fraz oraz ich statystyk występowania

Etap ten służy do identyfikacji fraz w korpusie dokumentów i określenia, które z nich są "dobre".

Dobre frazy to takie, które są użyteczne dla indeksowania i wyszukiwania: semantycznie znaczące, często występują w dokumentach i są predykcyjne wobec innych fraz.

• Przeglądanie dokumentów: System przegląda duże ilości dokumentów podzielone na partie (np. po 1 000 000 dokumentów). Dla każdego dokumentu przesuwa okno frazy o długości od 1 do n słów (np. 5), generując potencjalne frazy.

• Generowanie potencjalnych fraz: Z każdego okna tworzone są wszystkie możliwe frazy zaczynające się od pierwszego słowa i zawierające od 1 do n słów.

• Uzupełnianie list fraz: Jeśli potencjalna fraza jest już obecna w systemie na liście dobrych fraz, wówczas do jej wpisu w indeksie dodawany jest identyfikator bieżącego dokumentu (np. jego URL). Jeśli nie ma jej na liście dobrych fraz, ale jest na liście potencjalnych fraz, aktualizowane są jej statystyki. Jeśli nie ma jej na liście potencjalnych fraz, jest do niej dodawana.

• Zbieranie statystyk: Dla każdej potencjalnej frazy zbierane są trzy kluczowe statystyki dotyczące częstości jej występowania oraz wyróżnienia w tekście:

  • Liczba dokumentów zawierających frazę.
  • Łączna liczba wystąpień frazy.
  • Liczba "interesujących" wystąpień frazy (np. wyróżnionych przez formatowanie html, hiperlink, cudzysłów itp.).

• Macierz współwystępowania: Dla wszystkich dobrych fraz system utrzymuje macierz kwadratową, gdzie dla każdej pary fraz przechowywane są dodatkowo:

  • Surowa liczba współwystąpień fraz w bliskim sąsiedztwie (np. w oddaleniu o kilkadziesiąt słów, w tym samym akapicie, części dokumentu itp.).
  • Liczba tych współwystąpień, gdzie przynajmniej jedna z fraz jest "interesująca".
  • Liczba współwystąpień, gdzie frazy zostały wyróżnone łącznie. Ta informacja może być szczególnie przydatna, aby uniknąć sytuacji, w której fraza (np. informacja o prawach autorskich) pojawia się często w paskach bocznych, stopkach lub nagłówkach i w związku z tym nie jest specjalnie użyteczna do szukania związków z resztą tekstu.

Etap 1 jest wykonywany dla każdego dokumentu w korpusie. Kiedy proces ten zostawnie zakończony, system przechodzi do kolejnego etapu:

Etap 2: Klasyfikacja fraz na dobre i złe

W tym etapie, na podstawie zebranych dla potencjalnych fraz statystyk, następuje ich klasyfikacja na "dobre" i "złe".

Złe frazy są nieprzydatne lub nieprzewidywalne dla systemu: nie mają powiązań semantycznych i nie przewidują innych fraz.

• Przenoszenie na listę dobrych fraz: Potencjalna fraza jest przenoszona na listę dobrych fraz, jeśli liczba jej wystąpień i ilość dokumentów, w których się pojawia, przekracza ustalone progi, np:

  • występuje w ponad 10 dokumentach i ma ponad 20 wystąpień
  lub
  • ma więcej niż 5 "interesujących" wystąpień.

• Oznaczanie fraz jako złe: Fraza jest uznawana za złą i usuwana z listy potencjalnych fraz, jeśli nie spełnia odpowiednich wymagań, np.:

  • występuje w mniej niż 2 dokumentach i nie ma żadnych "interesujących" wystąpień.

Wartosci te mogą być oczywiście tak doregulowywane, aby uzyskać pożądaną jakość wyników.

Po zakończeniu tego etapu na liście dobrych fraz będą się znajdować zarówno pojedyncze słowa, jak i dłuższe frazy zaczynające się od tego słowa (czyli przewidujące swoje własne rozszerzenia), a także takie, które przewidują wprawdzie zupełnie inne frazy, jednak w stopniu zbyt małym, aby mogło to być użyteczne dla systemu. Aby tego uniknąć, potrzebny jest jeszcze jeden etap:

Etap 3: Przycinanie listy dobrych fraz na podstawie miary predykcyjnej

Na początku tego etapu system dysponuje kwadratową macierzą współwystępowania wszystkich dobrych fraz. Przypomnijmy, że macierz ta zawiera m.in. informację o liczbie wystąpień każdej frazy, liczbie dokumentów, w jakich została znaleziona oraz liczbie współwystąpień dwóch fraz (można to sobie wyobrazić jako wartość przechowywaną w komórce tabeli znajdującej się na przecięciu wiersza reprezentującego jedną frazę i kolumny reprezentującej drugą frazę).

• Wyliczanie miary predykcyjnej: Dla każdej pary fraz obliczana jest miara predykcyjna, czyli tzw. zysk informacyjny. Jest to stosunek rzeczywistej częstotliwości współwystępowania tych fraz do oczekiwanej częstotliwości współwystępowania przy założeniu niezależności.

  Jeśli np. jedna fraza wystąpiła w 0,02% dokumentów, a druga w 0,03% dokumentów, to prawdopodobieństwo, że trafią na siebie przypadkowo wynosi 0,0006%. Ta wielkość jest porównywana z rzeczywistą wartością przechowywaną w macierzy współwystępowania dla tych fraz. Jeśli wartość rzeczywista przekracza wartość oczekiwaną w wymaganym stopniu (kolejny parametr, którym można regulować czułość systemu) oznacza to, że nie ma mowy o przypadku i między frazami istnieje zależność.

• Przycinanie fraz: Jeśli fraza nie przewiduje w wystarczającym stopniu żadnej innej frazy (tj. nie przekracza ustalonego progu zysku informacyjnego dla żadnej jej pary), jej wiersz jest usuwany z macierzy. Pozostaje w niej jednak jako kolumna, ponieważ nie przewidując żadnej frazy, sama może być tą, która jest przewidywana.

• Usuwanie fraz niekompletnych: Frazy, które przewidują tylko swoje rozszerzenia (dłuższe frazy zaczynające się od nich), są uznawane za niekompletne i usuwane z listy dobrych fraz. Nie są jednak kasowane zupełnie. Trafiają na listę fraz niekompletnych i stanowią bardzo użyteczny zbiór do wykorzystania przez wyszukiwarkę np. jako podpowiedzi sugerowane użytkownikowi podczas wpisywania przez niego zapytania.

Po tym etapie system dysponuje już zoptymalizowaną listą dobrych fraz, które przewidują w wymaganym stopniu przynajmniej jedną inną, a dodatkowo listą fraz niekompletnych, dla których również znajduje się praktyczne zastosowanie.

Rezultat procesu identyfikacji fraz

Po przeprowadzeniu wszystkich trzech etapów, system posiada zoptymalizowaną listę dobrych fraz, które są:

• Semantycznie znaczące: Są często używane i mają istotne znaczenie w kontekście dokumentów.

• Predykcyjne: Pomagają przewidywać występowanie innych fraz, co jest użyteczne na dalszych etapach indeksowania oraz w procesie wyszukiwania.

Proces identyfikacji jest powtarzany cyklicznie, dzięki czemu system jest w stanie na bieżąco dostosowywać się do zmian w treści dokumentów, a nawet zmian trendów językowych, gramatyki itp. Nowe frazy, które stają się popularne, o ile spełniają kryteria, są automatycznie dodawane do listy dobrych fraz, co pozwala na utrzymanie aktualności. Wysoka efektywność systemu jest utrzymywana dzięki temu, że, w odróżnieniu od wielu innych systemów identyfikacji treści, jest w pełni automatyczny i na żadnym z etapów nie wymaga uczestnictwa człowieka.

Po identyfikacji fraz następuje cz.2: tworzenie klastrów fraz powiązanych, dzięki którym m.in. będzie można określać tematy dokumentów oraz sprawdzać, w jakim stopniu pasują one do zapytań i intencji użytkowników.

© 2024 - 2025 semanticwebanalyzer.pl