We present a new variable-length computation-friendly encoding scheme, named SFDC (Succinct Format with Direct aCcessibility), that supports direct and fast accessibility to any element of the compressed sequence and achieves compression ratios often higher than those offered by other solutions existing in the literature. The SFDC scheme provides a flexible and simple representation geared towards either practical efficiency or compression ratios, as required. For a text of length 𝑛 over an alphabet of size 𝜎 and a fixed parameter 𝜆, the access time of our proposed encoding is proportional to the length of the character’s code-word, plus an expected 𝒪((𝐹𝜎−𝜆+3 − 3)/𝐹𝜎+1) overhead, where 𝐹𝑗 is the 𝑗-th Fibonacci number. In the overall, it uses 𝑁 + 𝒪(︀𝑛 · (︀𝜆 − (𝐹𝜎+3 − 3)/𝐹𝜎+1)︀)︀ = 𝑁 + 𝒪(𝑛) bits, where

A New Directly Accessible Compression Scheme

Domenico Cantone;Simone Faro
2024-01-01

Abstract

We present a new variable-length computation-friendly encoding scheme, named SFDC (Succinct Format with Direct aCcessibility), that supports direct and fast accessibility to any element of the compressed sequence and achieves compression ratios often higher than those offered by other solutions existing in the literature. The SFDC scheme provides a flexible and simple representation geared towards either practical efficiency or compression ratios, as required. For a text of length 𝑛 over an alphabet of size 𝜎 and a fixed parameter 𝜆, the access time of our proposed encoding is proportional to the length of the character’s code-word, plus an expected 𝒪((𝐹𝜎−𝜆+3 − 3)/𝐹𝜎+1) overhead, where 𝐹𝑗 is the 𝑗-th Fibonacci number. In the overall, it uses 𝑁 + 𝒪(︀𝑛 · (︀𝜆 − (𝐹𝜎+3 − 3)/𝐹𝜎+1)︀)︀ = 𝑁 + 𝒪(𝑛) bits, where
File in questo prodotto:
File Dimensione Formato  
paper100.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 1.38 MB
Formato Adobe PDF
1.38 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/641833
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact