Comparison Based on String Metric
Marco Patriarca, Els Heinsalu, Jean Leó Leonard · 2020
A string metric is any metric distance between entities which can be associated with a string. String metric-based methods have been developed and used for tackling various problems, from plagiarism detection and DNA/RNA analysis, image analysis and recognition, to data mining and integration, and incremental search, to name a few. In this chapter, we consider some simple examples of metric distances and apply them to some real examples related to language. Levenshtein Distance The most widely known string metric for measuring the difference between two sequences is the Levenshtein distance , also known as edit distance , named after Vladimir Levenshtein, who considered this distance in 1965 (Levenshtein, 1966). The Levenshtein distance L ( a , b ) between two given strings a and b , each composed of a set of characters, is defined as the minimum number of edit operations, including character addition, removal, and replacement, needed to turn a into b or vice versa (see e.g. Apostolico and Galil [1997]). Here is an example of how the Levenshtein distance can be used. Example: Levenshtein distances between three given words. Let us consider three different locations in the Basque countries, labeled here with k = 1, 2, 3, where three correspondingly different dialects of Basque are spoken, and compare the three variants of the same word, the Basque word for ‘I am’, in these locations. The words are a 1 = naiz , a 2 = nais , and a 3 = nas . Comparing these three words with each other, we notice the following relations: • a 1 = naiz vs. a 2 = nais : naiz → nais by one replacement operation z → s ; thus, L 12 = L ( naiz , nais ) = 1. • a 1 = naiz vs. a 3 = nas : naiz → nais → nas by two edit operations: replacement z → s and deletion of i ; so L 13 = L ( naiz , nas ) = 2.