COMPARISON OF STRINGS BELONGING TO THE SAME FAMILY

The comparison of strings belonging to the same family can be made thr ough the construction of a long(est) Common Subsequence (CS) that refl ects structural similarities that exist between these strings. The lon gest CS problem is NP-complete. In this paper, we present an O(N-2 x L (2)log(2)(L)) algorithm, where N is the number of the strings and L is the maximum length, that constructs a CS, to a family of strings, mad e up by longer words appearing, approximately, in the same positions i n all the strings. During each iteration, our algorithm looks for the longest common words that appear, approximately, in the same positions in all the strings, then, filters the common words found, to keep jus t those that assure the smallest norm between all the strings. The fil tering is based on a new distance called contextual distance. (C) 1998 Elsevier Science Inc. All rights reserved.