La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Lempel-Ziv Factorization in Linear-Time O(1)-Workspace for Constant Alphabets Factorisation de Lempel-Ziv en temps linéaire O(1) -Espace de travail pour alphabets constants

Weijun LIU

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le calcul de la factorisation Lempel-Ziv (LZ77) d'une chaîne est l'un des problèmes les plus importants en informatique. De nos jours, il est largement utilisé dans de nombreuses applications telles que la compression de données, l'indexation de texte et la découverte de modèles, et est déjà devenu le cœur de nombreux compresseurs de fichiers comme gzip et 7zip. Dans cet article, nous montrons un algorithme de temps linéaire appelé Xone pour calculer le LZ77, qui a le même besoin d'espace que le meilleur besoin d'espace précédent pour la factorisation du temps linéaire LZ77 appelé BGone. Xone améliore considérablement l'efficacité de BGone. Les expériences montrent que les deux versions de Xone : XoneT et XoneSA sont respectivement environ 27 % et 31 % plus rapides que BGoneT et BGoneSA.

Publication
IEICE TRANSACTIONS on Information Vol.E104-D No.12 pp.2145-2153
Date de publication
2021/12/01
Publicisé
2021/08/30
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2021EDP7037
Type de manuscrit
PAPER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

Weijun LIU
  Gannan Normal University

Mots-clés

Table des matières