Compression guidée par automate et noyaux rationnels / Ahmed Amarni ; sous la direction de Marie-Pierre Béal

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Données -- Compression (informatique)

Markov, Processus de

Noyaux (analyse fonctionnelle)

Automates

Transducteurs

Béal, Marie-Pierre (1962-....) (Directeur de thèse / thesis advisor)

Carton, Olivier (Président du jury de soutenance / praeses)

Caron, Pascal (1966-.... ; enseignant-chercheur en informatique) (Rapporteur de la thèse / thesis reporter)

Université Paris-Est (2015-....) (Organisme de soutenance / degree-grantor)

École doctorale Mathématiques, Sciences et Technologies de l'Information et de la Communication (Champs-sur-Marne, Seine-et-Marne ; 2015-....) (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire d'informatique de l'Institut Gaspard Monge (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : 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

Résumé / 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