Classification of Markov Sources Through Joint String Complexity: Theory and Experiments

Philippe Jacquet 1, 2, 3 Dimitrios Milioris 1, 2, 3, 4 Wojciech Szpankowski 5
2 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We propose a classification test to discriminate Markov sources based on the joint string complexity. String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define the joint string complexity as the cardinality of the set of words which both strings have in common. In this paper we analyze the average joint complexity when both strings are generated by two Markov sources. We provide fast converging asymptotic expansions and present some experimental results showing usefulness of the joint complexity to text discrimination.
Type de document :
Communication dans un congrès
IEEE International Symposium on Information Theory, Jul 2013, Istanbul, Turkey
Liste complète des métadonnées

https://hal-polytechnique.archives-ouvertes.fr/hal-00904144
Contributeur : Dimitrios Milioris <>
Soumis le : mercredi 13 novembre 2013 - 18:22:00
Dernière modification le : jeudi 22 novembre 2018 - 14:27:41

Identifiants

  • HAL Id : hal-00904144, version 1

Citation

Philippe Jacquet, Dimitrios Milioris, Wojciech Szpankowski. Classification of Markov Sources Through Joint String Complexity: Theory and Experiments. IEEE International Symposium on Information Theory, Jul 2013, Istanbul, Turkey. 〈hal-00904144〉

Partager

Métriques

Consultations de la notice

548