A new distance metric on strings computable in linear time (Q1102764): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| 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 | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0166-218x(88)90076-5 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1995552834 / rank | |||
Normal rank | |||
Latest revision as of 08:49, 30 July 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
