Skompresowana tablica sufiksów

W informatyce skompresowana tablica sufiksów jest skompresowaną strukturą danych służącą do dopasowywania wzorców . Skompresowane tablice sufiksów to ogólna klasa struktur danych , które ulepszają tablicę sufiksów . Te struktury danych umożliwiają szybkie wyszukiwanie dowolnego ciągu o stosunkowo małym indeksie.

Biorąc pod uwagę tekst T złożony z n znaków z alfabetu Σ, skompresowana tablica sufiksów obsługuje wyszukiwanie dowolnych wzorców w T . Dla wzorca wejściowego P złożonego z m znaków, czas wyszukiwania wynosi zwykle O( m ) lub O( m + log( n )). Używana przestrzeń to zazwyczaj ${\ Displaystyle O (nH_ {k} (T)} + o (n)}$ , gdzie ${\ Displaystyle H_ { k}(T)}$ jest entropią empiryczną k-tego rzędu tekstu T . Czas i miejsce na skonstruowanie skompresowanej tablicy sufiksów to zwykle ${\ Displaystyle O (n)}$ .

Oryginalna instancja skompresowanej tablicy sufiksów rozwiązała od dawna otwarty problem, pokazując, że szybkie dopasowywanie wzorców było możliwe przy użyciu tylko struktury danych w przestrzeni liniowej, a mianowicie struktury danych proporcjonalnej do rozmiaru tekstu T , który zajmuje ${\ Displaystyle O (n \ {\ log | \ Sigma |})}$ bitów. Konwencjonalna tablica sufiksów i drzewo $które$ znacznie Podstawą struktury danych jest rekurencyjna dekompozycja z wykorzystaniem „funkcji sąsiada”, która umożliwia reprezentację tablicy sufiksów jako połowy jej długości. Konstrukcja jest powtarzana wiele razy, aż wynikowa tablica sufiksów użyje liniowej liczby bitów. Dalsze prace wykazały, że rzeczywista przestrzeń dyskowa była związana z entropią zerowego rzędu i że indeks obsługuje samoindeksowanie. Ograniczenie przestrzeni zostało jeszcze ulepszone, osiągając ostateczny cel, jakim jest entropia wyższego rzędu; kompresję uzyskuje się przez podział funkcji sąsiada na konteksty wyższego rzędu i kompresję każdego podziału za pomocą drzewa falkowego . Wykorzystanie przestrzeni jest w praktyce niezwykle konkurencyjne w porównaniu z innymi najnowocześniejszymi kompresorami, a także obsługuje szybkie dopasowywanie wzorców.

Dostępy do pamięci wykonywane przez skompresowane tablice sufiksów i inne skompresowane struktury danych do dopasowywania wzorców zazwyczaj nie są zlokalizowane, a zatem te struktury danych były bardzo trudne do efektywnego zaprojektowania do użytku w pamięci zewnętrznej . Niedawne postępy w stosowaniu dualności geometrycznej wykorzystują dostęp do bloków zapewniany przez dyski w celu znacznego przyspieszenia czasu operacji we/wy. Ponadto wykazano potencjalnie praktyczną wydajność wyszukiwania skompresowanej tablicy sufiksów w pamięci zewnętrznej.

Implementacje Open Source

Dostępnych jest kilka implementacji skompresowanych tablic sufiksów typu open source (patrz Linki zewnętrzne poniżej). Bowtie i Bowtie2 to skompresowane implementacje tablicy sufiksów o otwartym kodzie źródłowym służące do wyrównania odczytu do użytku w bioinformatyce . Succinct Data Structure Library (SDSL) to biblioteka zawierająca różne skompresowane struktury danych, w tym skompresowane tablice sufiksów. FEMTO to implementacja skompresowanych tablic sufiksów dla pamięci zewnętrznej. Ponadto różne implementacje, w tym oryginalne FM-index , są dostępne na stronie internetowej Pizza & Chili (zobacz linki zewnętrzne).

Zobacz też

^ ^a ^b ^c R. Grossi i JS Vitter, skompresowane tablice sufiksów i drzewa sufiksów, z aplikacjami do indeksowania tekstu i dopasowywania ciągów, SIAM Journal on Computing, 35 (2), 2005, 378-407. Wcześniejsza wersja ukazała się w Proceedings of the 32nd ACM Symposium on Theory of Computing, maj 2000, 397-406.
^ ^{ab Paolo Ferragina i}^Giovanni Manzini (2000). „Oportunistyczne struktury danych z aplikacjami”. Materiały z 41. dorocznego sympozjum na temat podstaw informatyki. str. 390.
^ ^ab ^Proceedings R. Grossi, A. Gupta i JS Vitter, High-Order Entropy-Compressed Text Indexes, of the 14th Annual SIAM / ACM Symposium on Discrete Algorithms, styczeń 2003, 841-850.
Bibliografia _ _ _ 1969, Springer, grudzień 2000, 410-421.
Bibliografia Linki zewnętrzne _
Bibliografia _ Hon, R. Shah, SV Thankachan i JS Vitter, On Entropy-Compressed Text Indexing in External Memory, Proceedings of the Conference on String Processing and Information Retrieval , sierpień 2009.
^ MP Ferguson, FEMTO: szybkie wyszukiwanie dużych kolekcji sekwencji , Proceedings of the 23. Annual Conference on Combinatorial Pattern Matching , lipiec 2012

Linki zewnętrzne

Wdrożenia:

[GV00-1] R. Grossi i JS Vitter, skompresowane tablice sufiksów i drzewa sufiksów, z aplikacjami do indeksowania tekstu i dopasowywania ciągów, SIAM Journal on Computing, 35 (2), 2005, 378-407. Wcześniejsza wersja ukazała się w Proceedings of the 32nd ACM Symposium on Theory of Computing, maj 2000, 397-406.

[opportunistic_2000-2] {ab Paolo Ferragina i}^Giovanni Manzini (2000). „Oportunistyczne struktury danych z aplikacjami”. Materiały z 41. dorocznego sympozjum na temat podstaw informatyki. str. 390.

[GGV03-3] Proceedings R. Grossi, A. Gupta i JS Vitter, High-Order Entropy-Compressed Text Indexes, of the 14th Annual SIAM / ACM Symposium on Discrete Algorithms, styczeń 2003, 841-850.

[4] Bibliografia _ _ _ 1969, Springer, grudzień 2000, 410-421.

[5] Bibliografia Linki zewnętrzne _

[6] Bibliografia _ Hon, R. Shah, SV Thankachan i JS Vitter, On Entropy-Compressed Text Indexing in External Memory, Proceedings of the Conference on String Processing and Information Retrieval , sierpień 2009.

[7] MP Ferguson, FEMTO: szybkie wyszukiwanie dużych kolekcji sekwencji , Proceedings of the 23. Annual Conference on Combinatorial Pattern Matching , lipiec 2012