Algorytmy tekstowe

Zespół:

dr hab. Szymon Grabowski
dr inż. Wojciech Bieniecki
dr Marcin Raniszewski
dr inż. Tomasz Kowalski
dr inż. Grzegorz Nowak
mgr inż. Robert Susik
mgr inż. Aleksander Cisłak

Aktualności:

I 2017: przyjęta publikacja: Szymon Grabowski and Marcin Raniszewski: Compact and hash based variants of the suffix array, Bulletin Of The Polish Academy Of Sciences Technical Sciences.
XII 2016: przyjęta publikacja: Szymon Grabowski and Marcin Raniszewski: Sampled Sufﬁx Array with Minimizers, Software–Practice and Experience.
Compact and hash based variants of the suffix array, Bulletin Of The Polish Academy Of Sciences Technical Sciences.
VIII 2016: udział (Szymon Grabowski i Aleksander Cisłak) w I szkole letniej nt. bioinformatycznych struktur danych w Helsinkach, wygłoszenie referatu (Sz.G.) nt. Compressed genomic sequences with fast access.
VII 2016: przyjęta publikacja: Szymon Grabowski, Robert Susik i Marcin Raniszewski: A Bloom filter based semi-index on q-grams, Software–Practice and Experience.
I-IV 2016: c.d. prac na indeksami FM (artykuł wysłany do pisma The Computer Journal) oraz strukturami pomocniczymi rank/select.
IX 2015: udział (Szymon Grabowski i Marcin Raniszewski) w konferencji międzynarodowej SPIRE'15 oraz workshopie WCTA (Workshop on Compression, Text and Algorithms), wygłoszenie łącznie 2 referatów.
VI 2015: przyjęta publikacja: Tomasz Kowalski, Szymon Grabowski and Sebastian Deorowicz: Indexing arbitrary-length k-mers in sequencing reads, PLoS ONE.
VI 2015:przyjęty artykuł na konferencję SPIRE'15: Szymon Grabowski and Marcin Raniszewski: Sampling the suffix array with minimizers.
I-VI 2015: prace nad nowymi wariantami indeksu FM (http://arxiv.org/abs/1506.04896);
III 2015: publikacja: Szymon Grabowski: A note on the longest common substring with k-mismatches problem, Information Processing Letters, 115 (2015) 640–642.
I 2015: publikacja: Sebastian Deorowicz, Marek Kokot, Szymon Grabowski and Agnieszka Debudaj-Grabysz: KMC 2: fast and resource-frugal k-mer counting, Bioinformatics, 31(10), 2015, 1569–1576, doi: 10.1093/bioinformatics/btv022.
I 2015: prosty, lecz efektywny algorytm wyszukiwania słów (keywordów) w słowniku z obsługą błędów Hamminga (współpraca z inż. A. Cisłakiem).
XII 2014: publikacja Szymon Grabowski, Sebastian Deorowicz and Łukasz Roguski: Disk-based compression of data from genome sequencing, Bioinformatics, 31(9), 2015, 1389–1395, doi: 10.1093/bioinformatics/btu844.
X 2014: publikacja: Agnieszka Danek, Sebastian Deorowicz and Szymon Grabowski: Indexes of Large Genome Collections on a PC, PLoS ONE, DOI: 10.1371/journal.pone.0109384.
IX 2014: udział w konferencji międzynarodowej Prague Stringology Conference (PSC'14), wygłoszenie 3 referatów (przez mgra R. Susika, dra M. Raniszewskiego i dra hab. Sz. Grabowskiego). Teksty publikacji i slajdy dostępne na stronie http://www.stringology.org/event/ , karta "2014".
VI 2014: nowatorska odmiana samplowanej tablicy sufiksowej o korzystnych relacjach: pamięć-czas wyszukiwania (Sz. Grabowski i M. Raniszewski, http://arxiv.org/abs/1406.2348).
VI 2014: najszybszy istniejący algorytm zliczania k-merów w odczytach sekwencjonowania (Sz. Grabowski we współpracy z Kolegami z Politechniki Śląskiej, http://arxiv.org/abs/1407.1507), I 2015: artykuł przyjęty do "Bioinformatics".
V 2014: efektywny dyskowy algorytm kompresji strumienia DNA w odczytach sekwencjonowania (Sz. Grabowski we spółpracy z Kolegami z Politechniki Śląskiej, http://arxiv.org/abs/1405.6874), XII 2014: artykuł przyjęty do "Bioinformatics".
XI 2013: otrzymany grant NCN (konkurs OPUS 5, panel ST6) pt. Inżynieria algorytmiczna indeksów pełnotekstowych (kierownik: dr hab. Szymon Grabowski; uczestnicy grantu z IIS PŁ oraz Politechniki Śląskiej);
XI 2013: publikacja pracy przeglądowej:
Sebastian Deorowicz and Szymon Grabowski: Data compression for sequencing data, Algorithms for Molecular Biology 2013, 8:25 (http://www.almob.org/content/8/1/25, Open Access);
IX–XI 2013: nowe algorytmy dla problemu LCSk (S. Deorowicz i Sz. Grabowski), raport http://arxiv.org/abs/1311.4552 i submisja do pisma międzynarodowego (2014: artykuł przyjęty w Information Processing Letters, http://www.sciencedirect.com/science/article/pii/S0020019014001045);
IX–XI 2013: prace nad efektywnym algorytmem wyszukiwania wielu wzorców (R. Susik w ramach rozprawy doktorskiej, Sz. Grabowski oraz K. Fredriksson z Univ. of Eastern Finland);
IX–XI 2013: prace nad efektywną reprezentacją tablicy sufiksowej (M. Raniszewski i Sz. Grabowski);
VI–XI 2013: indeksowanie danych bioinformatycznych (T. Kowalski i Sz. Grabowski z IIS PŁ, A. Danek i S. Deorowicz z Politechniki Śląskiej);
IV–XI 2013: efektywna reprezentacja danych Google Ngrams (Sz. Grabowski i M. Raniszewski, we współpracy z mgrem inż. F. Proborszczem);
X 2013: publikacje na konferencji międzynarodowej ICMMI (http://icmmi.polsl.pl/):
Robert Susik, Szymon Grabowski, Sebastian Deorowicz: Fast and Simple Circular Pattern Matching;
Sebastian Deorowicz, Szymon Grabowski: Subcubic Algorithms for the Sequence Excluded LCS Problem.

Algorytmy tekstowe opracowane w KIS / IIS:

opracowanie pełnotekstowego indeksu skompresowanego FM-Huffman (2004), charakteryzującego się bodaj największą prostotą w swej klasie, a przy tym oferującego korzystne relacji szybkości wyszukiwania do stopnia oferowanej kompresji (Sz.Grabowski, we współpracy z kolegami z zagranicy);
opracowanie i analiza wariantów oryginalnej koncepcji FM-Huffman (2005, 2006). W świetle niedawnych badań, odmiana indeksu FM-KZ1 osiąga najwyższy stopień kompresji sekwencji DNA wśród istniejących implementacji indeksów skompresowanych (Sz.Grabowski, we współpracy z kolegami z zagranicy i studentem kierunku informatyka R.Przywarskim);
współautorstwo algorytmu Fast Average Optimal Shift-Or służącego do wyszukiwania wzorca w tekście, należącego do najszybszych algorytmów w praktyce na dzisiejszych platformach sprzętowych (2005) (Sz.Grabowski, we współpracy z Kimmo Fredrikssonem z Finlandii);
współautorstwo kilku nowych algorytmów wyszukiwania przybliżonego w danych muzycznych (MIDI), konkurencyjnych w stosunku do algorytmów istniejących z punktu widzenia teorii i/lub praktyki (2006, 2007) (Sz.Grabowski, we współpracy z Kimmo Fredrikssonem z Finlandii);
współautorstwo algorytmu wstępnego przetwarzania tekstu pod kątem dalszej kompresji (2005). Wyniki eksperymentów świadczą o praktycznej atrakcyjności opracowanego schematu; (Sz.Grabowski, we współpracy z Przemysławem Skibińskim z Uniwersytetu Wrocławskiego i Sebastianem Deorowiczem z Politechniki Śląskiej);
współautorstwo algorytmów kompresji dokumentów XML cechujących się wysokim stopniem kompresji przy dużej szybkości dekompresji (2006, 2007) (Sz.Grabowski, we współpracy z Przemysławem Skibińskim z Uniwersytetu Wrocławskiego i Jakubem Swachą z Uniwersytetu Szczecińskiego);
współautorstwo algorytmu kompresji tekstu opartej na q-gramach, umożliwiającej proste i szybkie wyszukiwanie wzorca bez uprzedniej dekompresji tekstu (2006) (Sz.Grabowski, we współpracy z Kimmo Fredrikssonem);
współautorstwo nowatorskiej techniki efektywniejszego wykorzystywania liczników w algorytmie Shift-Add i pokrewnych algorytmach opartych na tzw. równoległości bitowej (2006, 2007) (Sz.Grabowski, we współpracy z Kimmo Fredrikssonem);
algorytm detekcji plagiatów w kodach źródłowych programów, wykorzystujący pewne miary używane w "stringologii" i information retrieval (2006) (Sz.Grabowski i W.Bieniecki);
dwa algorytmy wyszukiwania permutowanego wzorca dla tekstu binarnego (binary jumbled pattern matching) (2012) (E. Giaquinta i Sz.Grabowski);
algorytm szukania przybliżonego w sensie odległości Hamminga w tekście upakowanym (2012) (E. Giaquinta, Sz. Grabowski i K.Fredriksson).

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 k², 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 k² 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