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

Context-Sensitive Grammar Transform: Compression and Pattern Matching Transformation grammaticale contextuelle : compression et correspondance de modèles

Shirou MARUYAMA, Youhei TANAKA, Hiroshi SAKAMOTO, Masayuki TAKEDA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Un cadre de transformation grammaticale sensible au contexte pour accélérer la correspondance de modèles compressés (CPM) est proposé. Un algorithme de compression glouton avec le modèle de transformation est présenté ainsi qu'un algorithme de correspondance de motifs compressé de type Knuth-Morris-Pratt (KMP). Le taux de compression correspond à gzip et Re-Pair, et la vitesse de recherche de notre algorithme CPM est presque deux fois plus rapide que l'algorithme CPM de type KMP sur Byte-Pair-Encoding de Shibata et al., et dans le cas de courts modèles, plus rapide que l'algorithme de Boyer-Moore-Horspool avec le codage stopper de Rautio et al., qui est considéré comme l'une des meilleures combinaisons permettant une recherche pratiquement rapide.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.219-226
Date de publication
2010/02/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E93.D.219
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science)
Catégories

Auteurs

Mots-clés

Table des matières