kontakt    mapa strony  
    polski   english

Algorytmy tekstowe

Zespół:


Aktualności:


Algorytmy tekstowe opracowane w KIS / IIS:


Kompresja grafu webowego

Technologie webowe stanowią ważną i dynamicznie rozwijaną dziedzinę informatyki, w której coraz większe zastosowanie mają technologie bazodanowe związane ze sztuczną inteligencją i drążeniem danych (Web 3.0).
Przykładowe zastosowania:

  • detekcja spamu webowego;
  • nowe interfejsy użytkownika;
  • zbieranie danych do e-commerce.

Wiele z tych zagadnień sprowadza się do analizy pajęczyny połączeń pomiędzy stronami WWW, a zatem hierarchia globalnej pajęczyny może być w bezpośredni sposób reprezentowana w postaci grafu skierowanego, gdzie wierzchołkami są poszczególne dokumenty (zbiór różnych treści: tekst, multimedia), a gałęziami są odsyłacze prowadzące z jednej strony do innych.
Już w roku 2005 wyszukiwarka Yahoo! indeksowała ponad 19 mld stron webowych, zaś liczba połączeń pomiędzy nimi znacznie przekraczała 100 mld. Bez wątpienia obecnie graf webowy jest jeszcze większy.
Przy naiwnej reprezentacji grafu (listy incydencji) taki graf zajmuje co najmniej kilkaset GB, co wielokrotnie przekracza zasoby pamięci operacyjnej (RAM) dzisiejszych komputerów klasy PC. Przechowywanie grafu na dysku wiąże się z bardzo wolnym dostępem, co w nieakceptowalnym stopniu spowalnia proces przeszukiwania.
Rozwiązaniem eliminującym tę wadę może być przechowywanie w pamięci grafu w postaci skompresowanej w taki sposób, aby możliwy był swobodny dostęp do list incydencji poszczególnych wierzchołków.
Zagadnienie to jest intensywnie badane w ostatnich latach i w literaturze można znaleźć kilka algorytmów osiągających stopień kompresji ok. 15:1 w stosunku do reprezentacji naiwnej. Jest możliwe osiągnięcie jeszcze wyższego stopnia kompresji kosztem spowolnienia dostępu do list incydencji, a zatem można mówić o istnieniu kompromisu pomiędzy jednym a drugim parametrem użytkowym.

Uruchamianie klasycznych algorytmów grafowych na ogromnych grafach (takich jak graf webowy) nastręcza problemy związane z nielokalnym dostępem do danych. Innymi słowy, przechowywanie ogromnych grafów na dysku wiąże się z permanentnym niesekwencyjnym dostępem do danych, co jest niezwykle kosztowne. W końcu lat 90. XX wieku pojawiły się pierwsze próby kompresji grafów z możliwością szybkiej nawigacji bez potrzeby globalnej dekompresji grafu. Do tych pionierskich prac można zaliczyć m.in. publikacje (Kleinberg i in., 1999), (Broder i in., 2000), (Adler i Mitzenmacher, 2001), (Suel i Yuan, 2001). Nieco wcześniej powstały prace teoretyczne dotyczące kompresji grafów planarnych, bez uwzględnienia jednak szybkiego (lokalnego) dostępu do danych (Turan, 1984; He i in., 2000).

Ważnym osiągnięciem w tych badaniach był algorytm Boldiego i Vigny (2004), który wykorzystuje m.in. takie "zjawiska" w grafie webowym, jak lokalność referencji i podobieństwo podzbioru odsyłaczy wychodzących między bliskimi w sensie położenia (przypisanego im indeksu) listami sąsiedztwa. Wspomniany algorytm osiągnął stopień kompresji ok. 3-4 bitów na odsyłacz na typowych grafach (benchmarkach). Celem algorytmu B-V, podobnie jak większości innych znanych, była efektywna obsługa zapytań typu neighbor(x) (odsyłacze wychodzące). Aby równie efektywnie obsłużyć zapytania typu reverse_neighbor(x), należy utworzyć analogiczną strukturę dla grafu transponowanego, co praktycznie podwaja wymogi pamięciowe.

Obsługa zapytań typu reverse_neighbor(y) jest kluczowa w ocenie relewantności stron, np. w algorytmie PageRank. Podejściem, które umożliwia bardziej efektywną obsługę obu tych zapytań jest umiejętne wykorzystanie algorytmu kompresji Re-Pair (Larsson i Moffat, 2000), co zostało dokonane przez Claude i Navarro (Claude i Navarro, 2007; Claude, 2008). Wadą ich podejścia jest wysoki koszt pamięciowo-czasowy budowy struktury skompresowanej.

Kompresję znacznie wyższą niż oferowaną przez algorytmy wcześniejsze przedstawiono w pracy (Asamo i in., 2008), jednak osiągnięcie japońskich naukowców, ok. 2 bitów na odsyłacz, okupione zostało znacznie wydłużonym czasem dostępu, gdyż ich algorytm wymaga dekompresji pełnej domeny (serwisu WWW) w celu dostępu do sąsiadów pojedynczej strony. Algorytm ten obsługuje tylko zapytania typu neighbor(x).

Bardzo ciekawą koncepcję przedstawili niedawno Brisaboa i in. (2009). Ich algorytm bazuje na nowatorskiej idei tzw. drzew k2, spokrewnionych z drzewami czwórkowymi. Algorytm ten w naturalny sposób obsługuje zarówno zapytania typu neighbor(x), jak i reverse_neighbor(x). Osiągnięty stopień kompresji należy do najwyższych wśród znanych rozwiązań z obsługą obu typów zapytań, przy dość wysokiej szybkości dostępu do danych.

Prace nad kompresją grafu webowego stanowią wycinek szerszej dziedziny algorytmiki, jaką są skompresowane (lecz w pełni funkcjonalne) struktury danych. Do intensywnie badanych struktur tego typu należą tekstowe indeksy skompresowane (Ferragina i Manzini, 2000; Grossi i Vitter, 2000; Navarro i Mäkinen, 2007), drzewa (Jacobson, 1989; Munro i Raman, 1997; Jansson i in., 2007), sekwencje nad ograniczonym alfabetem (Jacobson, 1989; Raman i in., 2002; Ferragina i in., 2007) oraz permutacje (Barbay i Navarro, 2009). Zagadnienia te są ze sobą w ścisłym związku, np. struktura do obsługi zapytań typu rank (zwrócenie i-tego symbolu s w prefiksie zadanej sekwencji), którą zwykle przechowuje się z pamięciowo oszczędny sposób (Jacobson, 1989), jest jednym z kluczowych komponentów algorytmu kompresji grafu webowego z pracy (Brisaboa i in., 2009).

 

We wszystkich znanych nam publikacjach wykorzystuje się kilka standardowych grafów webowych (wycinków pełnego grafu), np. grafu ograniczonego do domeny jednego państwa

 

Oznaczenie zbioru
Data pozyskania
Liczba wierzch.
Liczba krawędzi
Bitów/link*)
arabic-2005
2005
22 744 080
639 999 458
1.99
cnr-2000
2000
325 557
3 216 152
2.838
eu-2005
2005
862 664
19 235 140
4.376
in-2004
2004
1 382 908
16 917 053
2.171
indochina-2004
2004
7 414 866
194 109 311
1.472
it-2004
2004
41 291 594
1 150 725 436
1.999
sk-2005
2005
50 636 154
1 949 412 601
2.86
uk-2002
2002
18 520 486
298 113 762
2.224
uk-2006-06
cze-06
80 644 902
2 481 281 617
2.242
uk-2006-12
gru-06
103 098 631
3 768 836 665
2.079
uk-2007-05
maj-07
105 896 555
3 738 733 648
1.95
uk-union-2006-06-2007-05
maj-07
133 633 040
5 507 679 822
2.644
webbase-2001
2001
118 142 155
1 019 903 190
3.078

 

Zbiory dostępne są na stronie http://law.dsi.unimi.it w postaci plików binarnych. Udostępniono również API dla języka Java pozwalające na ekstrakcję danych z tych zbiorów np. do postaci tekstowej.

W naszych badaniach przyjęliśmy konwencję, iż każdy wiersz pliku tekstowego odpowiada liście sąsiedztwa (incydencji) jednego wierzchołka grafu. Listy sąsiedztwa są przedstawione w postaci ściśle rosnących indeksów dokumentów, do których istnieją odsyłacze ze strony bieżącej. Każdy dokument jest opisany unikalną liczbą (np. dla zbioru uk-2007-05 będzie to liczba z zakresu 1 - 105 896 555). Ilość liczb w każdym pliku oznacza ilość krawędzi (tu: 3 738 733 648).

Jedna z rozważanych koncepcji algorytmu będzie polegać na podziale zbioru na małe bloki obejmujące k wierszy. (gdzie k wynosi np. 8 lub 16). Każdy blok jest kompresowany osobno i przewidziany jest swobodny dostęp do początku każdego bloku.

W obrębie bloku zastosujemy następujące techniki algorytmiczne:

  • kodowanie różnicowe (wykorzystuje fakt monotoniczności indeksów);
  • kodowanie podobieństw bliskich sobie wierszy (wykorzystanie zjawiska wspólnej struktury - kolejne wiersze należą zwykle do tego samego serwisu WWW, a tym samym mają podobną strukturę nawigacyjną) - mamy zamiar rozszerzyć ideę flag znaną z pracy Boldiego i Vigny (2004).

Struktura logiczna otrzymanego pliku skompresowanego będzie się składać z kilku strumieni (w fazie projektowania będą to osobne pliki). Każdy strumień zawiera dane jednego z poniższych typów (m. in.):

  • informacja czy dany wiersz jest kodowany niezależnie, czy w sposób referencyjny;
  • odnośnik do pozycji wiersza względem którego dany wiersz jest kodowany;
  • flaga podobieństwa danej krawędzi do jednej z krawędzi wiersza wcześniejszego;
  • długość wiersza liczona w krawędziach (liczba odsyłaczy wychodzących z danego dokumentu).

Przy kompresji pojawiających się tu danych pośrednich (np. indeksów referencji do wcześniejszych wierszy) powinno przydać się doświadczenie kierownika projektu dotyczące tematyki kompresji logów webowych (Grabowski i Deorowicz, 2007; Deorowicz i Grabowski, 2008).

Następnie rozważania przeniesiemy w kierunku osiągnięcia najlepszego stopnia kompresji przy zachowaniu względnie dobrego (krótkiego) czasu wyszukiwania. Obecnie najlepszy algorytm zaproponowano w (Asamo i in., 2008). Uważamy, że jest możliwość uzyskania lepszego stopnia kompresji przy zachowaniu porównywalnej lub wyższej szybkości przetwarzania. Przesłanką do tego twierdzenia jest wnikliwa analiza istniejącego algorytmu. Sądzimy, że dla odpowiednio przygotowanych bloków wierszy jest możliwe zastosowanie algorytmu kompresji ogólnego przeznaczenia charakteryzującego się wysokim stopniem kompresji i szybką dekompresją (np. 7-zip, http://7zip.org/).

Ostatnim etapem badań będzie opracowanie efektywnego algorytmu obsługującego zapytania typu:

  • sprawdź, czy istnieje krawędź z wierzchołka x do wierzchołka y (isEdge(x, y));
  • zwróć listę odnośników wychodzących (neighbor(x));
  • zwróć listę odnośników wchodzących (reverse_neighbor(x)).

Naiwna implementacja wymaga osobnego kodowania grafu prostego oraz grafu transponowanego. Algorytm z pracy (Brisaboa i in., 2009) wykorzystuje nowatorską koncepcję drzewa k2 spokrewnioną z dobrze znanymi drzewami czwórkowymi. Uważamy, że elegancki ten pomysł zawiera jeszcze pewne rezerwy, jeżeli chodzi o wydajną implementację.

Prototypy algorytmów zostały napisane w języku Python ze względu na wygodne mechanizmy przetwarzania plików i tekstu oraz rozbudowane kolekcje wysokiego poziomu. Wersje finalne są w języku Java ze względu na możliwość porównania z implementacjami dostępnymi w literaturze. W pracy magisterskiej p. Filip Proborszcz zaimplementował niektóre z naszych algorytmów w C++, uzyskując przyspieszenie ponad 30%.

Testowanie algorytmów polegało na porównaniu rozmiarów plików wynikowych (mamy do dyspozycji dane literaturowe) oraz czasu wyszukiwania.


Algorytmy bioinformatyczne (Sz.G., we współpracy z drem hab. Sebastianem Deorowiczem z Politechniki Śląskiej):

  • algorytm kompresji odczytów sekwencjonowania w formacie FASTQ, wraz z szybką ekstrakcją dowolnego rekordu. Wyniki (w stopniu kompresji i szybkości (de)kompresji) konkurencyjne względem istniejących (http://bioinformatics.oxfordjournals.org/content/27/6/860),
  • algorytm kompresji różnicowej kompresji genomów GDC. W trybie bez szybkiego dostępu do danych stopień kompresji różnicowej na kolekcji 70 genomów przekroczył nieco 1000:1. (http://bioinformatics.oxfordjournals.org/content/27/21/2979)

powrót do góry


Redakcja:
Szymon Grabowski

Ostatnia modyfikacja:
2017-03-18 18:01:09, Szymon Grabowski