Кіріспе
Компьютерлік ғылымдағы метрика. Ақпарат теориясы мен компьютерлік ғылымда Дамерау–Левенштейн қашықтығы (Фредерик Ж. Дамерау мен Владимир И. Левенштейннің есімдерімен аталады) – екі тізбек арасындағы өңдеу қашықтығын өлшеуге арналған жол метрикасы. Шартты түрде, екі сөз арасындағы Дамерау–Левенштейн қашықтығы – бір сөзді екінші сөзге өзгерту үшін қажетті ең аз операциялар саны (бір символді қосу, жою немесе алмастыру, немесе екі іргелес символді орнынан жылжытудан тұрады). Дамерау–Левенштейн қашықтығы классикалық Левенштейн қашықтығынан өзгешелігі – рұқсат етілген операциялардың қатарында үш классикалық символ бойынша өңдеу операцияларынан (қосу, жою және алмастыру) өзгеше, символдарды орнынан жылжыту да бар. Дамерау ақпаратты іздеу жүйесі үшін әріптес қателерді зерттеу кезінде, 80%-дан астам қателердің төрт түрдің біріне жататын бір ғана қатеден туындағанын мәлімдеді. Дамераудың мақаласында тек бір өңдеу операциясымен түзетуге болатын әріптес қателер қарастырылған. Алғашқы мақсат – адамдардың жасаған қателерін өлшеу арқылы әріптес тексерушілер сияқты қолданбаларды жақсарту болған, бірақ Дамерау–Левенштейн қашықтығы биологияда белок тізбектері арасындағы айырмашылықты өлшеу үшін де қолданылады.
In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Levenshtein distance between two words is the minimum number of operations (consisting of insertions, deletions or substitutions of a single character, or transposition of two adjacent characters) required to change one word into the other. The Damerau–Levenshtein distance differs from the classical Levenshtein distance by including transpositions among its allowable operations in addition to the three classical single character edit operations (insertions, deletions and substitutions). Damerau stated that in an investigation of spelling errors for an information retrieval system, more than 80% were a result of a single error of one of the four types. Damerau's paper considered only misspellings that could be corrected with at most one edit operation. While the original motivation was to measure distance between human misspellings to improve applications such as spell checkers, Damerau–Levenshtein distance has also seen uses in biology to measure the variation between protein sequences.
Анықтама
Екі тізбек пен арасындағы Дамерау–Левенштейн қашықтығын көрсету үшін функция анықталады, оның мәні – тізбек пен тізбегінің символдық префиксі (бастапқы кішкентай тізбесі) арасындағы қашықтық. Шектелген қашықтық функциясы рекурсивті түрде былай анықталады: біреуі қарапайым, оптималды тізбектерді сәйкестендіру қашықтығы немесе шектелген өңдеу қашықтығы деп аталатынды есептейді, ал екіншісі – жанындағы ауыстырулармен Дамерау–Левенштейн қашықтығын есептейді. Ауыстыруларды қосу күрделілікті арттырады. Екі алгоритмнің арасындағы айырмашылық – оптималды тізбектерді сәйкестендіру алгоритмі тізбектерді тең ету үшін қажетті өңдеу операцияларының санын есептейді, ал екіншісі мұндай шектеуді ұсынбайды. Мысалы, CA мен ABC арасындағы өңдеу қашықтығын қарастырайық. Дамерау–Левенштейн қашықтығы LD(CA, ABC) = 2, себебі CA → AC → ABC, бірақ оптималды тізбектерді сәйкестендіру қашықтығы OSA(CA, ABC) = 3, себебі егер CA → AC операциясы қолданылса, AC → ABC қолдану мүмкін емес, өйткені бұл кішкентай тізбеге бірнеше рет өңдеу жасауды талап етеді, ал OSA-да мұндайға рұқсат жоқ, сондықтан операциялардың ең қысқа тізбегі CA → A → AB → ABC. Назар аударыңыз, оптималды тізбектерді сәйкестендіру қашықтығы үшін үшбұрыш теңсіздігі OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC) орындалмайды, сондықтан ол нағыз метрика емес.
The restricted distance function is defined recursively as: simpler one, computes what is known as the optimal string alignment distance or restricted edit distance, while the second one computes the Damerau–Levenshtein distance with adjacent transpositions. Adding transpositions adds significant complexity. The difference between the two algorithms consists in that the optimal string alignment algorithm computes the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once, whereas the second one presents no such restriction. Take for example the edit distance between CA and ABC. The Damerau–Levenshtein distance LD(CA, ABC) = 2 because CA → AC → ABC, but the optimal string alignment distance OSA(CA, ABC) = 3 because if the operation CA → AC is used, it is not possible to use AC → ABC because that would require the substring to be edited more than once, which is not allowed in OSA, and therefore the shortest sequence of operations is CA → A → AB → ABC. Note that for the optimal string alignment distance, the triangle inequality does not hold: OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC), and so it is not a true metric.