Experiments in Unsupervised Entropy-Based Corpus Segmentation

Experiments in Unsupervised Entropy-Based Corpus Segmentation Andrd Kempe Xerox Research Centre Europe - Grenoble Laboratory 6 chemin de Maupertuis - 38240 Meylan - France andre, kempe@xrce, xerox, corn http://ggla, xrce. xerox, corn/research/mitt Abstract The paper presents an entropy-based approach to segment a corpus into words, when no additional information about the corpus or the language, and no other resources such as a lexicon or grammar are available. To segment the corpus, the algorithm searches for separators, without knowing a priory by which symbols they are constituted. Good results can be obtained with corpora containing "clearly perceptible" separators such as blank or new-line. 1 Introduction The paper presents an approach to segment a cor- pus into words, based on entropy. We assume that the corpus is not annotated with additional informa- tion, and that we have no information whatsoever about the corpus or the language, and no linguistic resources such as a lexicon or grammar. Such a situ- ation may occur e.g. if there is a (sufficiently large) corpus of an unknown or unidentified language and alphabet. 1 Based on entropy, we search for separa- tors, without knowing a priory by which symbols or sequences of symbols they are constituted. Over the last decades, entropy has frequently been used to segment corpora [Wolff, 1977, Alder, 1988, Hutchens and Alder, 1998, among many others]. and it is commonly used with compression tech- niques. Harris [1955] proposed an approach for seg- menting words into morphemes that, although it did not use entropy, was based on an intuitively similar concept: Every symbol of a word is annotated with the count of all possible successor symbols given the .substring that ends with the current symbol, and with the count of all possible predecessor symbols I Such a corpus can be electronically encoded with arbi- trarily defined symbol codes. given the tail of the word that starts with the cur- rent symbol. Maxima in these counts are used to segment the word into morphemes. All steps of the present approach will be described on the example of a German corpus. In addition, we will give results obtained on modified versions of this corpus, and on an English corpus. 2 The Approach 2.1 The Corpus We assume that any corpus C can be described by the expression: c = S. T IS+ T]* 3, (1) There must be at least one token T ("word") which is a string of one or more symbols s : T = s+ (2) Different tokens T must be separated form each other by one or more separators S which are strings of zero or more symbols s : S = s* (3) Separators can consist of blanks, new-line, or "'real" symbols. They can also be empty strings. 2.2 Recoding the Corpus We will describe the approach on the example of a German corpus. First, all symbols s (actually all character codes) of the corpus are recoded by strings of "'visible" ASCII characters. For example: 2 2In this example, \ denotes that …

Content truncated to 500 words