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, whereFile | 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.