Skompresowana struktura danych

Termin skompresowana struktura danych pojawia się w poddziedzinach informatyki, takich jak algorytmy , struktury danych i informatyka teoretyczna . Odnosi się do struktury danych, której operacje są mniej więcej tak szybkie, jak w przypadku konwencjonalnej struktury danych dla danego problemu, ale której rozmiar może być znacznie mniejszy. Rozmiar skompresowanej struktury danych jest zwykle silnie zależny od entropii reprezentowanych danych.

Ważne przykłady skompresowanych struktur danych obejmują skompresowaną tablicę sufiksów i FM-index , które mogą reprezentować dowolny tekst znaków T do dopasowywania wzorców . Biorąc pod uwagę dowolny wzorzec wejściowy P , obsługują one operację znajdowania, czy i gdzie P pojawia się w T . Czas wyszukiwania jest proporcjonalny do sumy długości wzorca P , bardzo wolno rosnącej funkcji długości tekstu T , oraz liczby zgłoszonych dopasowań. Zajmowane przez nie miejsce jest w przybliżeniu równe rozmiarowi tekstu T w postaci skompresowanej entropijnie, takiej jak uzyskana przez Prediction by Partial Matching lub gzip . Co więcej, obie struktury danych są samoindeksujące, ponieważ mogą zrekonstruować tekst T w sposób o swobodnym dostępie, a tym samym podstawowy tekst T można odrzucić. Innymi słowy, jednocześnie zapewniają skompresowaną i dającą się szybko przeszukiwać reprezentację tekstu T . Stanowią one znaczne ulepszenie przestrzeni w porównaniu z konwencjonalnym drzewem sufiksów i tablicą sufiksów , które zajmują wiele razy więcej miejsca niż rozmiar T. Obsługują również wyszukiwanie dowolnych wzorców, w przeciwieństwie do odwróconego indeksu , który może obsługiwać tylko wyszukiwanie oparte na słowach. Ponadto odwrócone indeksy nie mają funkcji samoindeksowania.

Ważnym pokrewnym pojęciem jest zwięzła struktura danych , która wykorzystuje przestrzeń mniej więcej równą minimum informacyjnemu, co jest najgorszym przypadkiem pojęcia przestrzeni potrzebnej do reprezentacji danych. W przeciwieństwie do tego rozmiar skompresowanej struktury danych zależy od konkretnych reprezentowanych danych. Gdy dane są kompresowalne, jak to często ma miejsce w praktyce w przypadku tekstu w języku naturalnym, skompresowana struktura danych może zajmować miejsce bardzo bliskie minimum teoretycznego i znacznie mniej miejsca niż większość schematów kompresji.