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)

1 Alcatel-Lucent Bell Labs France [Nozay]
2 HIPERCOM - High performance communication
3 LINCS - Laboratory of Information, Network and Communication Sciences
4 X - École polytechnique
5 Department of Computer Science [Purdue]

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.

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⟩