A new distance metric on strings computable in linear time (Q1102764)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new distance metric on strings computable in linear time |
scientific article |
Statements
A new distance metric on strings computable in linear time (English)
0 references
1988
0 references
We describe a new metric for sequence comparison that emphasizes global similarity over sequential matching at the local level. It has the advantage over the Levenshtein metric that strings of lengths n and m can be compared in time proportional to \(n+m\) instead of nm. Various mathematical properties of the metric are established.
0 references
string matching
0 references
partial match
0 references
distance metric
0 references
clustering
0 references
text processing
0 references
editing
0 references
spelling correction
0 references
sequence comparison
0 references
sequential matching
0 references
