Compression guided by automata and rational kernels - Archive ouverte HAL Access content directly
Theses Year : 2015

Compression guided by automata and rational kernels

Compression guidée par automate et noyaux rationnels

(1)
1
Ahmed Amarni
  • Function : Author
  • PersonId : 766998
  • IdRef : 191226785

Abstract

Due to the expansion of datas, compression algorithms are now crucial algorithms. We address here the problem of finding an optimal compression algorithm with respect to a given Markovian source. To this purpose, we extend the classical Huffman algorithm. The kernels are popular methods to measure the similarity between words for classication and learning. We generalize the definition of rational kernels in order to apply kernels to the comparison of languages. We study this generalization for factor and subsequence kerneland prove that these kernels are defined for parameters chosen in an appropriate interval. We give different methods to build weighted transducers which compute these kernels
En raison de l'expansion des données, les algorithmes de compression sont désormais cruciaux. Nous abordons ici le problème de trouver des algorithmes de compression optimaux par rapport à une source de Markov donnée. A cet effet, nous étendons l'algorithme de Huffman classique. Pour se faire premièrement on applique Huffman localement à chaque état de la source Markovienne, en donnant le résultat de l'efficacité obtenue pour cet algorithme. Mais pour bien approfondir et optimiser quasiment l'efficacité de l'algorithme, on donne un autre algorithme qui est toujours appliqué localement à chaque états de la source Markovienne, mais cette fois ci en codant les facteurs partant de ces états de la source Markovienne de sorte à ce que la probabilité du facteur soit une puissance de 1/2 (sachant que l'algorithme de Huffman est optimal si et seulement si tous les symboles à coder ont une probabilité puissance de 1/2). En perspective de ce chapitre on donne un autre algorithme (restreint à la compression de l'étoile) pour coder une expression à multiplicité, en attendant dans l'avenir à coder une expression complète
Fichier principal
Vignette du fichier
TH2015PEST1002.pdf (664.21 Ko) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

tel-01270750 , version 1 (08-02-2016)

Identifiers

  • HAL Id : tel-01270750 , version 1

Cite

Ahmed Amarni. Compression guidée par automate et noyaux rationnels. Informatique et langage [cs.CL]. Université Paris-Est, 2015. Français. ⟨NNT : 2015PESC1002⟩. ⟨tel-01270750⟩
279 View
185 Download

Share

Gmail Facebook Twitter LinkedIn More