Similarity measures for sets of strings^†

Partially supported by the National Science Foundation Grant No. ECS-80-09041.

Abstract

In the companion paper [3], we have presented a common basis for many of the similarity and dissimilarity measures involving a pair of strings. In this paper, we extend the results to capture various numerical and nonnumerical measures involving more than two strings. A measure D(X Y,…Z) has been defined involving the set of strings {X Y,…Z} in terms of two abstract operators ⊕ and ⊛ and a function δ(·, ·) which has as many arguments as there are strings in the set {X Y,…Z}. The quantity D(X Y,…Z) represents various numerical and nonnumerical quantities involving {X Y,…Z} such as Length of their Longest Common Subsequence, (LLCS) the Length of their Shortest Common Supersequence, (LSCS) the set of their common subsequences, the set of their common supersequences and the set of their shuffles. The computational properties of D(X Y,…Z) have also been discussed.

Keywords:

• Similarity measures for sets of strings
• dissimilarity measures for sets of strings
• common basis for properties involving sets of strings
• subsequences
• supersequences and shuffles of sets of strings

C.R. Categories::

• 3.63
• 5.23
• 5.25
• 5.42
• 5.7

Partially supported by the National Science Foundation Grant No. ECS-80-09041.

Partially supported by the National Science Foundation Grant No. ECS-80-09041.

Notes

Partially supported by the National Science Foundation Grant No. ECS-80-09041.