Кіріспе
Компьютерлік лингвистика және компьютерлік ғылымда өңдеу қашықтығы – екі жолдың (мысалы, сөздердің) бір-бірінен қаншалықты өзгеше екенін өлшеудің бір жолы, яғни бір жолды екінші жолға айналдыру үшін қажетті ең аз операциялар санын есептеу арқылы анықталады. Өңдеу қашықтығы табиғи тілді өңдеуде қолданылады, онда автоматты орфографиялық түзету қате сөздерді түзету үшін сөздіктен қашықтығы аз сөздерді таңдап, түзетуге үміткерлерді анықтай алады. Биоинформатикада ДНҚ тізбектерінің ұқсастығын өлшеу үшін де қолданылады, мұнда ДНҚ тізбектері А, С, Г және Т әріптерінің тізбектері ретінде қарастырылады.
In computational linguistics and computer science, edit distance is a string metric, i. e. a way of quantifying how dissimilar two strings (e. g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.
Өңдеу қашықтығының әртүрлі анықтамалары әртүрлі операциялар жиынтығын қолданады. Левенштейн қашықтығы операциялары – жол ішіндегі таңбаны жою, қосу немесе алмастыру. Ең көп қолданылатын өлшем болғандықтан, Левенштейн қашықтығы термині көбінесе өңдеу қашықтығымен бірдей қолданылады.
Өңдеу қашықтығының түрлері
Редакция қашықтығының әртүрлі түрлері әртүрлі жол операцияларын қолдануға мүмкіндік береді. Мысалы:
Левенштейн қашықтығы жоюға, қосуға және алмастыруға рұқсат береді. Ең ұзын ортақ ішкі тізбек (LCS) қашықтығы тек қосу мен жоюға ғана рұқсат етеді, алмастыруға емес. Хамминг қашықтығы тек алмастыруға рұқсат береді, сондықтан ол тек бірдей ұзындықтағы жолдарға қолданылады. Дамерау–Левенштейн қашықтығы екі жақын символдың орнын ауыстыруға (транспозицияға), сондай-ақ қосуға, жоюға және алмастыруға рұқсат береді. Жаро қашықтығы тек транспозицияға ғана рұқсат береді. Кейбір редакция қашықтықтары рұқсат етілген редакция операцияларының белгілі бір жиынтығымен есептелетін параметрленетін метрика ретінде анықталады, және әрбір операцияға құн (мүмкін шексіз) тағайындалады. Бұл Смит–Уотерман алгоритмі сияқты ДНК тізбегін салыстыру алгоритмдерімен одан әрі кеңейтіледі, онда операцияның құны оның қолданылған жеріне байланысты өзгереді.
The Levenshtein distance allows deletion, insertion and substitution. The longest common subsequence (LCS) distance allows only insertion and deletion, not substitution. The Hamming distance allows only substitution, hence, it only applies to strings of the same length. The Damerau–Levenshtein distance allows insertion, deletion, substitution, and the transposition (swapping) of two adjacent characters. The Jaro distance allows only transposition. Some edit distances are defined as a parameterizable metric calculated with a specific set of allowed edit operations, and each operation is assigned a cost (possibly infinite). This is further generalized by DNA sequence alignment algorithms such as the Smith–Waterman algorithm, which make an operation's cost depend on where it is applied.
Ресми анықтама және қасиеттері
Екі a және b жол берілген Σ әліпбиі бойынша (мысалы, ASCII символдары жиынтығы, [0 255] байттар жиынтығы, және т.б.), өңдеу қашықтығы – a жолын b жолына түрлендіретін өңдеу операцияларының ең төмен салмақты тізбегі. Өңдеу операцияларының ең қарапайым жиынтығының бірі 1966 жылы Левенштейнмен анықталды:
Қосымша қарапайым операциялар ұсынылған. Дамеру-Левенштейн қашықтығы екі іргелес символдардың орнын ауыстыруды бір өңдеу ретінде есептейді, бұл операция uxyv-ді uyxv-ке өзгерту арқылы формалды түрде сипатталады. Өңдеу қашықтығының басқа түрлері операциялар жиынтығын шектеу арқылы алынады. Ең ұзын ортақ ішкі тізбек (LCS) қашықтығы – енгізу және жою операцияларын ғана қолданатын өңдеу қашықтығы, олардың екеуі де бірлік құнымен бағаланады. Левенштейн қашықтығы және бірлік құны бар LCS қашықтығы жоғарыда аталған шарттарға, демек метрикалық аксиомаларға сәйкес келеді. Әдебиетте нақты метрика болып табылмайтын өңдеу қашықтығының түрлері де қарастырылған.
Ортақ алгоритм
Левенштейннің бастапқы операцияларын қолдана отырып, (симметриялық емес) өңдеу арақашықтығы , рекурренттік формуламен анықталады, бірақ оның көп рет қайта ашылған тарихы бар. Мұндай рекурренттік формулаларды шешу және кірістің мөлшеріне пропорционал жадта операциялардың оптималды тізбесін тиімді түрде алу үшін, Chowdhury, Le және Ramachandran жалпы рекурсивті «бөліп талқылау» әдісін ұсынады.
Жақсартылған алгоритмдер
Жоғарыда сипатталған Вагнер-Фишер алгоритмін жетілдіре отырып, Укконен бірнеше нұсқаны сипаттайды, олардың бірі екі жол және максималды түзету қашықтығы s қабылдап, нәтиже береді. Ол бұған динамикалық бағдарламалау кестесінің диагоналі маңындағы бөлігін ғана есептеу және сақтау арқылы қол жеткізеді. Бұл алгоритм уақыт алады, мұнда m және n – жолдардың ұзындығы. Жадының күрделілігі немесе , түзету тізбегін оқу қажеттігіне байланысты. Шекті әліпбе және бір-біріне пропорционалды түзету құндары болған жағдайда, ең жылдам белгілі нақты алгоритм – Masek және Paterson алгоритмі, оның ең нашар жағдайдағы жұмыс уақыты O(nm/logn) құрайды.
Қолданбалар
Edit distance есептеу биологиясы және табиғи тілді өңдеуде қолданылады, мысалы, орфографиялық қателерді немесе OCR қателерін түзетуде, сондай-ақ шамамен тізбектерді сәйкестендіруде, мұнда мақсат – көптеген ұзын мәтіндерде қысқа тізбектерге сәйкес келетін нәрсені табу, егер аз ғана айырмашылықтар күтілсе. Екі тізбек арасындағы қашықтықты есептеуден басқа, байланысты мәселелерді шешу үшін әртүрлі алгоритмдер бар. Хиршберг алгоритмі екі тізбенің оңтайлы сәйкестігін есептейді, онда оңтайлылық – edit distance-ты азайту ретінде анықталады. Шамамен тізбектерді сәйкестендіру edit distance тұрғысынан формулировкаланады. Укконеннің 1985 жылғы алгоритмі үлгі деп аталатын p тізбегі мен k тұрақтысын қабылдайды; содан кейін ол кез келген s тізбегінде p-ге edit distance-ы k-дан аспайтын кіші тізбекті табатын детерминистік шекті күй автоматын құрайды (Aho–Corasick алгоритмімен салыстырыңыз, ол ұқсас түрде кез келген үлгілерді іздеу үшін автоматты құрастырады, бірақ edit операцияларына рұқсат бермейді). Шамамен тізбектерді сәйкестендіруге арналған ұқсас алгоритм – bitap алгоритмі, ол да edit distance тұрғысынан анықталған. Левенштейн автоматтары – бұл шекті күйдегі машиналар, олар белгілі бір анықтама тізбегінен шектеулі edit distance-тағы тізбектер жиынтығын таниды, мұндағы edit distance – тізбектер арасындағы қашықтық. Егер L тілі контекстсіз болса, 1972 жылы Ахо мен Петерсон ұсынған тілдік edit distance-ты есептейтін кубикалық уақытты динамикалық бағдарламалау алгоритмі бар. Грамматиканың экспрессивті емес отбасылары үшін, мысалы, регулярлы грамматика үшін, edit distance-ты есептеуге арналған жылдам алгоритмдер бар. Тілдік edit distance РНК бүктеу, қателерді түзету және оптималды стек генерациялау мәселесінің шешімдері сияқты көптеген әртүрлі қолданыстар тапты.