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.
Document type :
Conference papers
Complete list of metadatas

https://hal-polytechnique.archives-ouvertes.fr/hal-00904144
Contributor : Dimitrios Milioris <>
Submitted on : Wednesday, November 13, 2013 - 6:22:00 PM
Last modification on : Tuesday, May 14, 2019 - 10:19:37 AM

Identifiers

  • 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⟩

Share

Metrics

Record views

725