Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
 
<< vorige    volgende >>
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 8 van 9 gevonden artikelen
 
 
  Simple Random Access Compression
 
 
Titel: Simple Random Access Compression
Auteur: Fredriksson, Kimmo
Nikitin, Fedor
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 92 (2009) nr. 1-2 pagina's 63-81
Jaar: 2009-06-01
Inhoud: Given a sequence S of n symbols over some alphabet Σ of size σ, we develop new compression methods that are (i) very simple to implement; (ii) provide O(1) time random access to any symbol (or short substring) of the original sequence. Our simplest solution uses at most 2h+o(h) bits of space, where h = n(H_{0}(S)+1), and H_{0}(S) is the zeroth-order empirical entropy of S. We discuss a number of improvements and trade-offs over the basic method. For example, we can achieve n(H_{k}(S)+1)+o(n(H_{k}(S)+1)) bits of space, for k = o(log_{σ}(n)). Several applications are discussed, including text compression, (compressed) full-text indexing and string matching.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften
 
 

                             Details van artikel 8 van 9 gevonden artikelen
 
<< vorige    volgende >>
 
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland
Toegankelijkheidsverklaring