A new distance metric on strings computable in linear time (Q1102764): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q3214349 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The smallest automaton recognizing the subwords of a text / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A technique for isolating differences between files / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A faster algorithm computing string edit distances / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A Space-Economical Suffix Tree Construction Algorithm / rank | |||
Normal rank | |||
Revision as of 16:16, 18 June 2024
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
