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

A Reconstruction of Circular Binary String Using Substrings and Minimal Absent Words Une reconstruction d'une chaîne binaire circulaire à l'aide de sous-chaînes et de mots absents minimaux

Takahiro OTA, Akiko MANADA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Une chaîne circulaire formée en connectant le premier et le dernier symbole d'une chaîne est l'une des formes de séquence les plus simples et elle a été utilisée pour de nombreuses applications telles que la compression de données et les problèmes d'assemblage de fragments. Une condition suffisante sur les longueurs de sous-chaînes avec des fréquences pour la reconstruction d'une chaîne binaire circulaire d'entrée est présentée. Cependant, il n’existe pas de descriptions détaillées de la preuve de la condition suffisante et de l’algorithme de reconstruction. Dans cet article, nous prouvons une condition nécessaire et suffisante sur les longueurs des sous-chaînes avec des fréquences pour la reconstruction de la corde circulaire. Nous montrons que la longueur est plus courte que celle de l’étude précédente pour certaines cordes circulaires. Pour améliorer la longueur, nous utilisons un minimum de mots absents (MAW) pour des sous-chaînes de longueur donnée. k, et nous proposons un nouvel algorithme de construction de MAW de longueur h(>k) alors qu'un algorithme de construction conventionnel de MAW peut construire des MAW de longueur l(≤k). De plus, nous proposons un algorithme de reconstruction d'une chaîne circulaire d'entrée pour des sous-chaînes données satisfaisant la nouvelle condition.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.3 pp.409-416
Date de publication
2024/03/01
Publicisé
2023/09/05
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2023TAP0015
Type de manuscrit
Special Section PAPER (Special Section on Information Theory and Its Applications)
Catégories
Codage source et compression des données

Auteurs

Takahiro OTA
  Senshu University
Akiko MANADA
  Nagaoka University of Technology

Mots-clés

Table des matières