Komprimeret datastruktur - Compressed data structure

Udtrykket komprimeret datastruktur opstår i datalogi- underfelterne af algoritmer , datastrukturer og teoretisk datalogi . Det henviser til en datastruktur, hvis operationer er omtrent lige så hurtige som dem, der er for en konventionel datastruktur for problemet, men hvis størrelse kan være væsentligt mindre. Størrelsen af ​​den komprimerede datastruktur er typisk meget afhængig af entropien af ​​de data, der er repræsenteret.

Vigtige eksempler på komprimerede datastrukturer inkluderer det komprimerede suffiksarray og FM-indekset , som begge kan repræsentere en vilkårlig tekst med tegn T til mønster matching . I betragtning af alle input mønster P , de støtter driften af finde om og hvor P vises i T . Søgetiden er proportional med summen af ​​længden på mønster P , en meget langsomt voksende funktion af længden på teksten T og antallet af rapporterede kampe. Det rum, de optager, er nogenlunde lig med størrelsen på teksten T i entropi-komprimeret form, såsom det, der opnås ved Prediction af Partial Matching eller gzip . Derudover er begge datastrukturer selvindekserende, idet de kan rekonstruere teksten T på en tilfældig adgangsmåde, og dermed kan den underliggende tekst T kasseres. Med andre ord, de samtidig giver en komprimeret og hurtigt søgbare repræsentation af teksten T . De repræsenterer en væsentlig plads forbedring i forhold til konventionelle suffix træ og suffiks-array , der optager mange gange mere plads end størrelsen af T . De understøtter også søgning efter vilkårlige mønstre i modsætning til det inverterede indeks , der kun kan understøtte ordbaserede søgninger. Derudover har inverterede indeks ikke funktionen til selvindeksering.

En vigtig relateret opfattelse er den af ​​en kortfattet datastruktur , der bruger plads, der er nogenlunde lig med det informationsteoretiske minimum, som er en værste sag om det rum, der er nødvendigt for at repræsentere dataene. I modsætning hertil afhænger størrelsen af ​​en komprimeret datastruktur af de bestemte data, der er repræsenteret. Når dataene er komprimerbare, som det ofte er tilfældet i praksis for tekst på naturligt sprog, kan den komprimerede datastruktur besætte plads meget tæt på det informationsteoretiske minimum og betydeligt mindre plads end de fleste komprimeringsordninger.

Referencer