Chapter 3 - Comparison Based on String Metric

Summary

A string metric is any metric distance between entitieswhich can be associated with a string. String metric-based methods have beendeveloped and used for tackling various problems, from plagiarism detectionand DNA/RNA analysis, image analysis and recognition, to data mining andintegration, and incremental search, to name a few. In this chapter, weconsider some simple examples of metric distances and apply them to somereal examples related to language.

Levenshtein Distance

The most widely known string metric for measuring the difference between twosequences is the Levenshtein distance, also known asedit distance, named after Vladimir Levenshtein, whoconsidered this distance in 1965 (Levenshtein, 1966).

The Levenshtein distance L(a,b) between two given strings a andb, each composed of a set of characters, is defined asthe minimum number of edit operations, including characteraddition, removal, and replacement, needed to turn a intob 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 usconsider three different locations in the Basque countries, labeled herewith k = 1, 2, 3, where three correspondingly differentdialects of Basque are spoken, and compare the three variants of the sameword, the Basque word for ‘I am’, in these locations. Thewords are a₁ = naiz,a₂ = nais, anda₃ = nas. Comparing thesethree words with each other, we notice the following relations:

• • a₁ = naiz vs.a₂ = nais:naiz → nais by onereplacement operation z →s; thus, L₁₂ =L(naiz, nais)= 1.

• • a₁ = naiz vs.a₃ = nas:naiz → nais →nas by two edit operations: replacementz → s and deletion ofi; so L₁₃ =L(naiz, nas)= 2.