Minimum edit distance: alignments and searchمسافة التحرير الدنيا: المحاذاة والبحث

A speech recognizer hears "turn on the kitchen light" and writes "turn on a kitchen light please". A spell checker sees "acress". An OCR engine reads the two letters "rn" as an "m". In each case there is a string we have and a string we want, and the question is the same: how much editing separates them?

يسمع نظام التعرّف على الكلام «turn on the kitchen light» فيكتب «turn on a kitchen light please». ويرى مدقق الإملاء «acress». ويقرأ محرك OCR الحرفين «rn» على أنهما «m». في كل حالة لدينا سلسلة نملكها وسلسلة نريدها، والسؤال واحد: كم من التحرير يفصل بينهما؟

The answer is the Minimum edit distance: the minimum total cost of the editing operations that turn a source string into a target string. Three operations are allowed. An insertion adds one symbol, a deletion removes one, and a substitution replaces one with another. Each operation has a cost, most often 1, and the distance is the cheapest way of getting from source to target, not the first way you happen to find. With every operation at cost 1 (and a substitution of a letter by itself at cost 0) this quantity is the Levenshtein distance, after the 1966 paper that introduced it for error correcting codes. Nothing in the definition says the symbols must be letters. Take words as the symbols and the same definition measures how far a recognized sentence is from its transcript, which is exactly how speech recognition uses it.

الإجابة هي minimum edit distance (مسافة التحرير الدنيا): أقل تكلفة إجمالية لعمليات التحرير التي تحوّل سلسلة مصدر (source) إلى سلسلة هدف (target). يُسمح بثلاث عمليات. الإدراج (insertion) يضيف رمزًا واحدًا، والحذف (deletion) يزيل رمزًا واحدًا، والاستبدال (substitution) يضع رمزًا مكان آخر. لكل عملية تكلفة، غالبًا 1، والمسافة هي أرخص طريقة للوصول من المصدر إلى الهدف، لا أول طريقة تصادفها. وعندما تكون تكلفة كل عملية 1 (وتكلفة استبدال الحرف بنفسه 0) تُسمّى هذه الكمية Levenshtein distance، نسبةً إلى بحث عام 1966 الذي قدّمها لرموز تصحيح الأخطاء. ولا يوجد في التعريف ما يشترط أن تكون الرموز حروفًا. اجعل الكلمات هي الرموز، فيقيس التعريف نفسه مدى بُعد جملة متعرَّف عليها عن نصها المرجعي، وهذا بالضبط ما يفعله التعرّف على الكلام.

The spelling application is older than most of NLP. Damerau found in 1964 that a single wrong, missing, extra or transposed letter accounts for about 80 percent of spelling errors, which is why candidate generation by a single transformation works so well: Kernighan, Church and Gale's spelling corrector lists exactly the six single-transformation candidates for "acress" shown in the table, one of them (caress) reached by reversing the first two letters rather than by a Levenshtein substitution, and then picks among them with a probabilistic model. Approximate matching generalizes the search direction: instead of comparing two whole strings, you look for places in a long text that a pattern would match after at most k edits.

تطبيق الإملاء أقدم من معظم NLP. وجد Damerau عام 1964 أن حرفًا واحدًا خاطئًا أو ناقصًا أو زائدًا أو مبدَّل الموضع يفسّر نحو 80 بالمئة من أخطاء الإملاء، ولهذا ينجح توليد المرشحين بتحويل واحد نجاحًا كبيرًا: مصحح الإملاء الذي بناه Kernighan وChurch وGale يسرد بالضبط المرشحين الستة ذوي التحويل الواحد لكلمة «acress» المبيّنين في الجدول، وأحدهم (caress) يُوصل إليه بعكس ترتيب الحرفين الأولين لا باستبدال من نوع Levenshtein، ثم يختار بينهم بنموذج احتمالي. أما المطابقة التقريبية (approximate matching) فتعمّم اتجاه البحث: بدلًا من مقارنة سلسلتين كاملتين، تبحث عن مواضع في نص طويل يطابقها النمط بعد k تعديلات على الأكثر.

Word error rate, computedحساب معدل خطأ الكلمات

The Word error rate (WER) is edit distance applied to words. Align the recognizer's hypothesis to the human reference at the word level, count the insertions, substitutions and deletions on that alignment, and divide by the number of words in the reference. The denominator is the reference, never the hypothesis, and because insertions are counted the rate can exceed 100 percent.

Word error rate (معدل خطأ الكلمات) هو مسافة التحرير مطبّقة على الكلمات. حاذِ فرضية نظام التعرّف (hypothesis) مع المرجع البشري (reference) على مستوى الكلمات، واحسب الإدراجات والاستبدالات والحذوفات في تلك alignment، ثم اقسم على عدد كلمات المرجع. المقام هو المرجع وليس الفرضية أبدًا، ولأن الإدراجات تُحسب فقد يتجاوز المعدل 100 بالمئة.

SLP3's own CallHome example has 6 substitutions, 3 insertions and 1 deletion over 13 reference words, a WER of 76.9 percent. The standard scorer is NIST's sclite in the SCTK toolkit, which does the alignment and the arithmetic for you but reports exactly these counts.

مثال CallHome في SLP3 نفسه فيه 6 استبدالات و3 إدراجات وحذف واحد (1) على 13 كلمة مرجعية، أي WER قدره 76.9 بالمئة. والمقيّم القياسي هو أداة sclite من NIST ضمن حزمة SCTK، التي تنفّذ المحاذاة والحساب نيابةً عنك لكنها تُبلغ عن هذه الأعداد نفسها بالضبط.

Lay the two words on top of each other as on slide 82, with a star for a gap, and read the ten columns from left to right: I over a star, N over E, T over X, E over E, a star over C, N over U, and then T I O N over T I O N. The row underneath, d s s _ i s, names the columns that cost something: delete I, substitute N by E, substitute T by X, insert C, substitute N by U. Five operations, and five is the minimum edit distance.

ضع الكلمتين إحداهما فوق الأخرى كما في الشريحة 82، مع نجمة للفجوة (gap)، واقرأ الأعمدة العشرة من اليسار إلى اليمين: I فوق نجمة، N فوق E، T فوق X، E فوق E، نجمة فوق C، N فوق U، ثم T I O N فوق T I O N. والصف الذي تحتها، d s s _ i s، يسمّي الأعمدة التي لها تكلفة: احذف I، استبدل N بـE، استبدل T بـX، أدرج C، استبدل N بـU. خمس عمليات، والخمسة هي مسافة التحرير الدنيا.

What you just read is an Alignment: a correspondence between the two strings that says, for every symbol, what it lines up with. A column with the same letter top and bottom is a match and costs nothing. A column with two different letters is a substitution. A letter over a gap is a deletion (the source letter is consumed without producing anything), and a gap over a letter is an insertion. The cost of an alignment is the sum of its column costs, and the minimum edit distance is simply the cost of the cheapest alignment. The practical half of the story is that the dynamic programming table does not just give the number, it stores a Backpointer in each cell, and following those pointers back from the last cell recovers one cheapest alignment. Part 11 does that recovery by hand.

ما قرأته للتو هو alignment (محاذاة): تقابل بين السلسلتين يحدد لكل رمز ما يقابله. العمود الذي فيه الحرف نفسه أعلى وأسفل هو تطابق (match) ولا يكلّف شيئًا. والعمود الذي فيه حرفان مختلفان هو استبدال. والحرف فوق فجوة هو حذف (يُستهلك حرف المصدر دون أن ينتج شيئًا)، والفجوة فوق حرف هي إدراج. تكلفة المحاذاة هي مجموع تكاليف أعمدتها، ومسافة التحرير الدنيا ببساطة هي تكلفة أرخص محاذاة. والنصف العملي من القصة أن جدول dynamic programming لا يعطي الرقم فقط، بل يخزّن backpointer (مؤشرًا خلفيًا) في كل خلية، وتتبّع هذه المؤشرات رجوعًا من الخلية الأخيرة يسترجع إحدى المحاذاات الأرخص. الجزء 11 يقوم بهذا الاسترجاع يدويًا.

Two cost conventions, and the same words come out as 5 or 8اصطلاحان للتكلفة، والكلمات نفسها تخرج بـ5 أو 8

Here is the trap this lecture sets, and the reason this section exists. Slides 85 and 86 define the Substitution cost as 1 for two different letters. The filled table you will meet in part 11 (slides 89 and 91) is copied from SLP3, and SLP3 fills it with a substitution cost of 2. Levenshtein proposed both: in his second version insertions and deletions cost 1 and substitutions are simply not allowed, and since any substitution can be written as a deletion followed by an insertion, that is the same as allowing it at cost 2. Both are legitimate cost functions. They give different numbers, and they can disagree about which alignment is best.

هذا هو الفخ الذي تنصبه هذه المحاضرة، وهو سبب وجود هذا القسم. الشريحتان 85 و86 تعرّفان substitution cost (تكلفة الاستبدال) بأنها 1 لحرفين مختلفين. أما الجدول المملوء الذي ستقابله في الجزء 11 (الشريحتان 89 و91) فمنسوخ من SLP3، وSLP3 يملؤه بتكلفة استبدال 2. اقترح Levenshtein الاثنين معًا: في نسخته الثانية يكلّف الإدراج والحذف 1 ولا يُسمح بالاستبدال إطلاقًا، وبما أن أي استبدال يمكن كتابته كحذف يليه إدراج، فهذا يكافئ السماح به بتكلفة 2. كلتاهما دالة تكلفة مشروعة. تعطيان أرقامًا مختلفة، وقد تختلفان أيضًا حول أي محاذاة هي الأفضل.

Read the totals again: 1 + 1 + 1 + 0 + 1 + 1 = 5 under unit costs and 1 + 2 + 2 + 0 + 1 + 2 = 8 with substitutions at 2. Both describe the same alignment. If an exam asks for the distance from intention to execution and you answer 8 without saying why, the grader who has the slide 85 recurrence in mind will mark it wrong, and the reverse is also true.

اقرأ المجموعين مرة أخرى: 1 + 1 + 1 + 0 + 1 + 1 = 5 في التكاليف الوحدوية و1 + 2 + 2 + 0 + 1 + 2 = 8 عندما يكلّف الاستبدال 2. كلاهما يصف المحاذاة نفسها. إذا سأل الامتحان عن المسافة من intention إلى execution وأجبت 8 دون أن تقول لماذا، فالمصحح الذي يضع في ذهنه علاقة الشريحة 85 سيعتبرها خطأ، والعكس صحيح أيضًا.

Try it: label the columns yourselfجرّب بنفسك: سمِّ الأعمدة

The editor below shows three alignments of intention and execution, with the four trailing matches already labeled. Label every remaining column, watch the two totals update, and then compare the presets. The third one pairs the letters position by position with no gaps at all: five substitutions. Under unit costs it ties the slide alignment at 5. With substitutions at 2 it costs 10 and loses to 8. The cost function does not only change the total; it changes which alignments are optimal.

يعرض المحرر أدناه ثلاث محاذاات لـintention وexecution، مع تسمية التطابقات الأربعة الأخيرة مسبقًا. سمِّ كل عمود متبقٍّ، وراقب المجموعين وهما يتحدّثان، ثم قارن المحاذاات الجاهزة. الثالثة تقرن الحروف موضعًا بموضع دون أي فجوات: خمسة استبدالات. في التكاليف الوحدوية تتعادل مع محاذاة الشريحة عند 5. وعندما يكلّف الاستبدال 2 تكلّف 10 وتخسر أمام 8. دالة التكلفة لا تغيّر المجموع فقط؛ بل تغيّر أيضًا أي المحاذاات هي المثلى.

The obvious algorithm is search. Start at intention and try one edit: delete a letter and you get ntention, insert a letter and you get intecntion, substitute a letter and you get inxention. Those are three of the children. Count all of them for a 26-letter alphabet: 9 possible deletions, 26 × 10 = 260 insertions and 25 × 9 = 225 substitutions, which is 494 children for one step. The rule of thumb 2|Σ|L used below is 2 × 26 × 9 = 468 here, the same order as the exact 494 and convenient for estimating the growth. A blind search that needs five steps to reach execution touches on the order of 494^5, about 3 × 10^13 strings. SLP3 puts it plainly: the space of all possible edits is enormous, so we cannot search naively.

الخوارزمية البديهية هي البحث. ابدأ من intention وجرّب تعديلًا واحدًا: احذف حرفًا فتحصل على ntention، أدرج حرفًا فتحصل على intecntion، استبدل حرفًا فتحصل على inxention. هذه ثلاثة من الأبناء. عُدّها كلها لأبجدية من 26 حرفًا: 9 حذوفات ممكنة، و26 × 10 = 260 إدراجًا، و25 × 9 = 225 استبدالًا، أي 494 ابنًا لخطوة واحدة. والقاعدة التقريبية 2|Σ|L المستخدمة أدناه تساوي هنا 2 × 26 × 9 = 468، وهي من رتبة القيمة الدقيقة 494 نفسها ومريحة لتقدير النمو. والبحث الأعمى الذي يحتاج خمس خطوات للوصول إلى execution يلمس ما رتبته 494^5، أي نحو 3 × 10^13 سلسلة. ويقولها SLP3 صراحةً: فضاء كل التعديلات الممكنة هائل، فلا يمكننا البحث فيه بسذاجة.

The visual shows the observation that rescues the problem. Delete the i of intention and then substitute t by x and you reach nxention. Substitute t by x first and then delete the i and you reach nxention again. Two paths, one state, and once you know the cheapest way to reach a state there is no reason to explore any other route into it. SLP3 states the idea directly: many distinct edit paths end up in the same string, so rather than recomputing all those paths we can remember the shortest path to a state each time we see it. Remembering subproblem answers and combining them is Dynamic programming, Bellman's table-driven method from 1957.

يعرض الشكل الملاحظة التي تنقذ المسألة. احذف i من intention ثم استبدل t بـx فتصل إلى nxention. استبدل t بـx أولًا ثم احذف i فتصل إلى nxention مرة أخرى. مساران وحالة واحدة، وبمجرد أن تعرف أرخص طريقة للوصول إلى حالة فلا داعي لاستكشاف أي طريق آخر إليها. يقول SLP3 الفكرة مباشرة: كثير من مسارات التعديل المختلفة تنتهي إلى السلسلة نفسها، فبدلًا من إعادة حساب كل تلك المسارات يمكننا أن نتذكر أقصر مسار إلى الحالة كلما رأيناها. وتذكّر إجابات المسائل الفرعية والجمع بينها هو dynamic programming (البرمجة الديناميكية)، طريقة Bellman القائمة على الجداول من عام 1957.

Why only prefix pairs matterلماذا لا يهمّ إلا أزواج البادئات

Remembering strings is still too many states. The step that makes the table small is to notice which states can matter at all. Suppose exention lies on an optimal path from intention to execution. Then the part of the path from intention to exention must itself be optimal, because if a shorter way to exention existed we could splice it in and shorten the whole path, a contradiction. This is the Optimal substructure argument in SLP3, and it means the only thing worth remembering about a partial solution is how much of the source it has consumed and how much of the target it has produced: the pair (i, j). For two 9-letter words there are only (m + 1)(n + 1) = 10 × 10 = 100 such pairs. Put as a picture: edits are moves in a grid from (0, 0) to (m, n), each move is one operation, and dynamic programming finds the best path efficiently.

تذكّر السلاسل ما زال يعني حالات أكثر من اللازم. الخطوة التي تجعل الجدول صغيرًا هي أن نلاحظ أي الحالات يمكن أن تهمّ أصلًا. افترض أن exention تقع على مسار أمثل من intention إلى execution. عندئذ يجب أن يكون جزء المسار من intention إلى exention أمثل هو نفسه، لأنه لو وُجد طريق أقصر إلى exention لأمكننا وصله مكانه وتقصير المسار كله، وهذا تناقض. هذه هي حجة optimal substructure (البنية الجزئية المثلى) في SLP3، وهي تعني أن الشيء الوحيد الذي يستحق التذكر عن حل جزئي هو كم استهلك من المصدر وكم أنتج من الهدف: الزوج (i, j). ولكلمتين من 9 أحرف لا يوجد إلا (m + 1)(n + 1) = 10 × 10 = 100 زوج من هذا النوع. وبالصورة: التعديلات حركات في شبكة من (0, 0) إلى (m, n)، كل حركة عملية واحدة، والبرمجة الديناميكية تجد أفضل مسار بكفاءة.

A path from the top-left corner to the bottom-right corner that uses only these three moves is an alignment: each step is one column. Reading the slide 82 alignment as moves gives down, diagonal, diagonal, diagonal, right, then five diagonals, which is the staircase in the figure. Wagner and Fischer showed in 1974 that filling the grid solves the problem in time proportional to the product of the two lengths, O(mn) time and, with backpointers stored, O(mn) space. Each cell is filled once with three comparisons.

المسار من الزاوية العليا اليسرى إلى الزاوية السفلى اليمنى الذي لا يستخدم إلا هذه الحركات الثلاث هو alignment (محاذاة): كل خطوة عمود واحد. وقراءة محاذاة الشريحة 82 كحركات تعطي: نزول، قُطر، قُطر، قُطر، يمين، ثم خمس حركات قُطرية، وهذا هو الدرج في الشكل. بيّن Wagner وFischer عام 1974 أن ملء الشبكة يحل المسألة في زمن يتناسب مع حاصل ضرب الطولين، أي زمن O(mn)، ومع تخزين backpointers (المؤشرات الخلفية) مساحة O(mn). كل خلية تُملأ مرة واحدة بثلاث مقارنات.

Three small questions give you the whole initialization. What is the distance from int to the empty string? You must delete i, n and t, so 3. From the empty string to ex? Insert e and x, so 2. From empty to empty? Nothing to do, 0. Write those as D[3, 0] = 3, D[0, 2] = 2 and D[0, 0] = 0 and you have the first row and column of every table you will ever fill.

ثلاثة أسئلة صغيرة تعطيك التهيئة كلها. ما المسافة من int إلى السلسلة الفارغة؟ عليك أن تحذف i وn وt، إذن 3. ومن السلسلة الفارغة إلى ex؟ أدرج e وx، إذن 2. ومن الفارغة إلى الفارغة؟ لا شيء يُفعل، 0. اكتبها على صورة D[3, 0] = 3 وD[0, 2] = 2 وD[0, 0] = 0 فيكون لديك الصف الأول والعمود الأول لكل جدول ستملؤه في حياتك.

Slide 85 sets the notation. The source x has length m, the target y has length n, and D[i, j] is the minimum edit distance between the prefix x[1..i] and the prefix y[1..j]. The answer to the whole problem is the last cell, D[m, n]. The Edit distance recurrence says how to fill every other cell from three neighbors.

الشريحة 85 تحدد الرموز. المصدر x طوله m، والهدف y طوله n، وD[i, j] هي minimum edit distance (مسافة التحرير الدنيا) بين البادئة x[1..i] والبادئة y[1..j]. وإجابة المسألة كلها هي الخلية الأخيرة، D[m, n]. وedit distance recurrence (العلاقة التكرارية لمسافة التحرير) تحدد كيف تُملأ كل خلية أخرى من ثلاثة جيران.

Each line is one possible last column of an optimal alignment of the two prefixes. Either the last column is x_i over a gap, in which case the rest is an optimal alignment of x[1..i-1] with y[1..j] and we pay a deletion; or it is a gap over y_j, the rest aligns x[1..i] with y[1..j-1] and we pay an insertion; or it is x_i over y_j, the rest aligns the two shorter prefixes and we pay the substitution cost, which is zero when the letters agree. There is no fourth shape a column can take, so the minimum over these three is exact. That is the optimal substructure of the previous concept written as an equation.

كل سطر يمثل عمودًا أخيرًا ممكنًا لـalignment (محاذاة) مثلى للبادئتين. إما أن يكون العمود الأخير x_i فوق فجوة، وعندها يكون الباقي محاذاة مثلى لـx[1..i-1] مع y[1..j] وندفع تكلفة حذف؛ أو يكون فجوة فوق y_j، فيحاذي الباقي x[1..i] مع y[1..j-1] وندفع تكلفة إدراج؛ أو يكون x_i فوق y_j، فيحاذي الباقي البادئتين الأقصر وندفع تكلفة الاستبدال، التي تساوي صفرًا عندما يتطابق الحرفان. لا يوجد شكل رابع يمكن أن يتخذه العمود، لذلك فالحد الأدنى على هذه الثلاثة دقيق تمامًا. وهذه هي البنية الجزئية المثلى من المفهوم السابق مكتوبة كمعادلة.

Now the exam favorite: why is D[i, 0] = i? The target prefix is empty, so every one of the i source letters has to disappear, and the only operation that removes a source letter is a deletion. No insertion can help, since it would produce a target letter where none is wanted, and no substitution can help, since it leaves a letter in place. At one unit per deletion the cost is exactly i. The mirror argument gives D[0, j] = j. In the general form of SLP3's pseudocode the border is built incrementally, D[i, 0] = D[i-1, 0] + del(x_i), which reduces to i when deletions cost one.

والآن السؤال المفضل في الامتحانات: لماذا D[i, 0] = i؟ البادئة الهدف فارغة، لذلك يجب أن يختفي كل حرف من حروف المصدر الـi، والعملية الوحيدة التي تزيل حرفًا من المصدر هي الحذف. لا يمكن لأي إدراج أن يساعد، لأنه سينتج حرفًا في الهدف حيث لا يُراد أي حرف، ولا يمكن لأي استبدال أن يساعد، لأنه يُبقي حرفًا في مكانه. وبوحدة واحدة لكل حذف تكون التكلفة i بالضبط. والحجة المعاكسة تعطي D[0, j] = j. وفي الصيغة العامة لشيفرة SLP3 الزائفة (pseudocode) يُبنى الحد تدريجيًا، D[i, 0] = D[i-1, 0] + del(x_i)، وهذا يؤول إلى i عندما تكون تكلفة الحذف واحدًا.

A table you can fill in one minuteجدول يمكنك ملؤه في دقيقة واحدة

Before the 10 × 10 table of part 11, fill a tiny one under unit costs: cat to cats. The first row and column are the initialization. Every other cell is the minimum of the cell above plus one, the cell to the left plus one, and the diagonal cell plus zero or one.

قبل جدول 10 × 10 في الجزء 11، املأ جدولًا صغيرًا في التكاليف الوحدوية: cat إلى cats. الصف الأول والعمود الأول هما التهيئة. وكل خلية أخرى هي أصغر قيمة بين الخلية التي فوقها زائد واحد، والخلية التي على يسارها زائد واحد، والخلية القُطرية زائد صفر أو واحد.

What the cost function can encodeما الذي يمكن أن تُرمّزه دالة التكلفة

Slide 86 spells out the unit Substitution cost: sub(a, b) = 0 if a = b, else 1. It also says the cost can be weighted, and this is where edit distance stops being a counting exercise and becomes a model. SLP3's caption to its pseudocode notes that costs can be specific to the letter, and its text adds that for spelling correction substitutions are more likely between letters that are next to each other on the keyboard. Kernighan, Church and Gale estimated four confusion matrices (deletion, addition, substitution and reversal counts) from the typos in 44 million words of 1988 AP newswire and used them as the channel probabilities of a noisy-channel spelling corrector; their top candidate agreed with the majority of three human judges in 87 percent of 329 cases. Set a substitution cost to the negative log of such a probability and the cheapest alignment becomes the most probable one.

الشريحة 86 توضح substitution cost (تكلفة الاستبدال) الوحدوية: sub(a, b) = 0 إذا a = b، وإلا 1. وتقول أيضًا إن التكلفة يمكن أن تكون موزونة، وهنا تتوقف مسافة التحرير عن كونها تمرين عدّ وتصبح نموذجًا. يذكر تعليق SLP3 على شيفرته الزائفة أن التكاليف يمكن أن تكون خاصة بكل حرف، ويضيف نصه أن الاستبدالات في تصحيح الإملاء أرجح بين الحروف المتجاورة على لوحة المفاتيح. قدّر Kernighan وChurch وGale أربع مصفوفات التباس (confusion matrices) (أعداد الحذف والإضافة والاستبدال والعكس) من الأخطاء المطبعية في 44 مليون كلمة من أخبار AP لعام 1988، واستخدموها احتمالاتِ القناة في مصحح إملاء قائم على نموذج القناة المشوِّشة (noisy channel)؛ واتفق مرشحهم الأول مع أغلبية ثلاثة محكّمين بشريين في 87 بالمئة من 329 حالة. اجعل تكلفة الاستبدال مساوية للوغاريتم السالب لاحتمال كهذا، فتصبح أرخص محاذاة هي الأكثر احتمالًا.

A cost function can also grow a fourth operation. Damerau's 1964 study listed transposition of two adjacent letters as one of the four single-error types. The simplest extension adds a fourth line to the Wagner-Fischer table, D[i-2, j-2] + cost, that applies when x_{i-1} = y_j and x_i = y_{j-1}; this restricted form is often called optimal string alignment distance, and it can overcount when a transposed pair is edited again. Lowrance and Wagner's 1975 algorithm handles that general case, and both are commonly labelled Damerau-Levenshtein distance. The typo tehcosts 2 with the three classic operations (delete one letter, insert it elsewhere) but only 1 with transposition. The slide recurrence does not include this move; treat it as an optional fourth line you can add when the application calls for it.

ويمكن لدالة التكلفة أيضًا أن تضيف عملية رابعة. دراسة Damerau عام 1964 عدّت تبديل موضع حرفين متجاورين (transposition) أحد أنواع الخطأ المفرد الأربعة. أبسط امتداد يضيف سطرًا رابعًا إلى جدول Wagner-Fischer، هو D[i-2, j-2] + cost، يُطبّق عندما x_{i-1} = y_j وx_i = y_{j-1}؛ وهذه الصيغة المقيّدة تُسمّى غالبًا مسافة المحاذاة المثلى للسلاسل (optimal string alignment distance)، وقد تبالغ في العدّ عندما يُعدَّل زوج مبدَّل مرة أخرى. أما خوارزمية Lowrance وWagner لعام 1975 فتعالج تلك الحالة العامة، وكلتاهما تُسمّى عادةً Damerau-Levenshtein distance. الخطأ المطبعي teh يكلّف 2 بالعمليات الكلاسيكية الثلاث (احذف حرفًا وأدرجه في مكان آخر) لكنه يكلّف 1 فقط مع التبديل. علاقة الشريحة لا تتضمن هذه الحركة؛ فتعامل معها كسطر رابع اختياري يمكنك إضافته عندما يتطلبه التطبيق.