Inferring lexical and grammatical structure from sequences

摘要

In a wide variety of sequences from various sources, from musicand text to DNA and computer programs, two different but related kindsof structure can be discerned. First, some segments tend to be repeatedexactly, such as motifs in music, words or phrases in text, identifiersand syntactic idioms in computer programs. Second, these segmentsinteract with each other in variable but constrained ways. For example,in English text only certain syntactic word classes can appear after theword `the' many parts of speech (such as verbs) are necessarilyexcluded. This paper shows how these kinds of structure can be inferredautomatically from sequences. We begin with an example that bothillustrates the utility of inferring the kinds of structure we seek andshows what our techniques can do. Next we present an efficient andnon-obvious algorithm for identifying exact repetitions-including nestedrepetitions-in time which is linear with the length of the sequence.Then we describe a very simple algorithm for identifying interactionsbetween sequence elements. The focus of this paper is on how these twoalgorithms can work together, for their combination is far more powerfulthan either alone. We show how they combine to generate the kind ofstructure sought in the original motivating example. Although the twomethods work well together on many simple examples, the resultsfrequently conflict with intuition in the inference of branchingstructure. The minimum description length principle seems to provide theonly satisfactory general approach