Why anyone cares, slide 78

لماذا يهتم أحد بهذا، الشريحة 78

You constantly need to ask "how similar are these two strings?" and get a number, not a yes/no. Edit distance is that number: the smallest number of single-character changes that turn one string into the other.

تحتاج دائماً أن تسأل "ما مدى تشابه هاتين السلسلتين؟" وأن تحصل على رقم لا على نعم أو لا. وedit distance هو ذلك الرقم: أصغر عدد من التغييرات بحرف واحد التي تحوّل سلسلة إلى الأخرى.

Slide 78's application list:

قائمة التطبيقات في الشريحة 78:

• spell checking and correction: the user typed graffe, and giraffe is one edit away while grace is three, so you suggest giraffe

  spell checking and correction: المستخدم كتب graffe، وgiraffe تبعد تعديلاً واحداً بينما grace تبعد ثلاثة، فتقترح giraffe

• OCR post-processing: the scanner read rnodern, which is one edit from modern (rn and m look alike)

  OCR post-processing: الماسح قرأ rnodern، وهي تعديل واحد عن modern (rn وm متشابهتان بصرياً)

• ASR word error rate (WER): WER is edit distance, computed over words rather than characters, between the reference transcript and the system output

  ASR word error rate (WER): الـ WER هو edit distance نفسه، محسوباً على الكلمات بدل الحروف، بين النص المرجعي وناتج النظام

• approximate matching: find records that nearly match a query

  approximate matching: إيجاد السجلات التي تطابق الاستعلام تقريباً

• alignment: say which piece of string A corresponds to which piece of string B

  alignment: تحديد أي جزء من السلسلة A يقابل أي جزء من السلسلة B

That last one is a bonus the algorithm gives you if you keep a little extra bookkeeping, and it is what slide 89 is about.

الأخير مكافأة تمنحها الخوارزمية إذا حفظت قليلاً من البيانات الإضافية، وهو موضوع الشريحة 89.

The three operations, slide 79

العمليات الثلاث، الشريحة 79

You are allowed exactly three moves, each acting on one character:

مسموح لك بثلاث حركات فقط، كل واحدة تعمل على حرف واحد:

يلخّص الجدول العمليات الثلاث: الـ Insertion تضيف حرفاً موجوداً في الهدف وغائباً عن المصدر فتطول السلسلة بحرف، والـ Deletion تحذف حرفاً في المصدر غير موجود في الهدف فتقصر بحرف، والـ Substitution تبدّل حرفاً بآخر فيبقى الطول نفسه ويتغير المحتوى.

Each operation has a cost. Slide 79 says costs are "often 1", and that substitutions can be weighted. The goal is then stated precisely: find the minimum-cost sequence of edits transforming source into target.

لكل عملية cost. تقول الشريحة 79 إن التكاليف "often 1" أي غالباً 1، وإن الـ substitutions يمكن أن تكون موزونة. ثم يُصاغ الهدف بدقة: إيجاد أرخص تسلسل تعديلات يحوّل source إلى target.

Two words there are load-bearing. Minimum, because there are infinitely many edit sequences that work (you could delete everything and then type the target from scratch) and we want the cheapest. And source into target, because the problem has a direction, which is what makes insertion and deletion different operations rather than the same one.

كلمتان هنا تحملان المعنى كله. Minimum، لأن هناك عدداً لا نهائياً من تسلسلات التعديل التي تؤدي الغرض (يمكنك حذف كل شيء ثم كتابة الهدف من الصفر) ونحن نريد الأرخص. وsource into target، لأن للمسألة اتجاهاً، وهذا الاتجاه هو ما يجعل الـ insertion والـ deletion عمليتين مختلفتين لا عملية واحدة.

The alignment view, slides 80 and 81

منظور المحاذاة (alignment)، الشريحتان 80 و81

Here is the mental picture that makes everything else click. An edit sequence is the same thing as lining up the two strings vertically and reading off what happens in each column.

هذه هي الصورة الذهنية التي تجعل كل ما بعدها واضحاً. تسلسل التعديلات هو نفسه رصف السلسلتين عمودياً ثم قراءة ما يحدث في كل عمود.

Write the source on top, the target underneath, and insert a gap symbol * wherever one string has nothing to offer. Slide 81 shows exactly this for our running pair:

اكتب الـ source في الأعلى والـ target تحته، وأدخل رمز الفراغ * في كل موضع لا تقدّم فيه إحدى السلسلتين شيئاً. والشريحة 81 تعرض هذا بالضبط على زوجنا المعتاد:

يرسم المخطط رصف intention في الأعلى فوق execution في الأسفل، مع فراغ * في كل منهما. وتحت كل عمود حرف عمليته: d حذف، وs إبدال، وi إدخال، والنقطة تطابق مجاني. وتحتها تكلفة العمود: الحذف 1، والإدخال 1، والإبدال 2، والتطابق 0. والمجموع 1 + 2 + 2 + 0 + 1 + 2 = 8.

Slide 80 makes three claims about this picture, and all three are worth holding on to:

تطرح الشريحة 80 ثلاث دعاوى عن هذه الصورة، وكلها تستحق التثبيت:

• edit distance corresponds to an alignment (they are two names for one object)

  الـ edit distance يقابل الـ alignment (اسمان لشيء واحد)

• an alignment makes explicit which characters match, substitute, insert, delete

  الـ alignment يُظهر صريحاً أي الحروف تطابقت، وأيها أُبدل أو أُدخل أو حُذف

• you recover an alignment with backpointers (the distance alone does not hand it to you)

  أنت تستعيد الـ alignment بالـ backpointers، فالمسافة وحدها لا تعطيك إياه

Edit distance as a search, slides 82 and 83

مسافة التحرير بوصفها بحثاً، الشريحتان 82 و83

Now turn the alignment on its side. Slide 82: picture a grid where you start at the corner (0, 0) and must reach the opposite corner (m, n). Position (i, j) means "I have dealt with the first i characters of the source and produced the first j characters of the target."

الآن أدِر الـ alignment على جنبه. الشريحة 82: تصوّر شبكة تبدأ من الزاوية (0, 0) وعليك الوصول إلى الزاوية المقابلة (m, n). والموضع (i, j) يعني "تعاملت مع أول i حرفاً من المصدر وأنتجت أول j حرفاً من الهدف".

Every legal move from a cell is one edit:

كل حركة مشروعة من خلية هي تعديل واحد:

• move down one row: you consumed a source character and produced nothing, which is a deletion

  النزول لأسفل صفاً واحداً: استهلكت حرفاً من المصدر ولم تنتج شيئاً، وهذا deletion

• move right one column: you produced a target character out of nothing, which is an insertion

  التحرك يميناً عموداً واحداً: أنتجت حرفاً من الهدف من لا شيء، وهذا insertion

• move diagonally: you consumed one source character and produced one target character, which is a substitution, or a free match when the two characters are the same

  التحرك قُطرياً: استهلكت حرفاً من المصدر وأنتجت حرفاً من الهدف، وهذا substitution، أو match مجاني إذا كان الحرفان متماثلين

So the question "what is the minimum edit distance" becomes "what is the cheapest path from the top-left corner to the bottom-right corner". That is a shortest-path problem, and brute-force search over all paths is astronomically expensive. Slide 82's punchline: dynamic programming computes the best path efficiently, by solving every subproblem once and reusing it.

فيصبح سؤال "ما أقل edit distance" هو سؤال "ما أرخص مسار من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى". وهذه مسألة أقصر مسار، والبحث الشامل في كل المسارات مكلف بصورة فلكية. وخلاصة الشريحة 82: الـ dynamic programming يحسب أفضل مسار بكفاءة، بحل كل مسألة فرعية مرة واحدة وإعادة استخدامها.

The table, slide 84

الجدول، الشريحة 84

Slide 84 sets up the notation. Memorize these three lines before you try to fill anything.

تُرسي الشريحة 84 الرموز. احفظ هذه السطور قبل أن تحاول ملء أي خلية.

يعرّف المربع الرموز: طول المصدر x هو m، وطول الهدف y هو n، والخلية D[i, j] هي أقل edit distance بين x[1..i] وy[1..j]، أي بين بدايتي السلسلتين لا بينهما كاملتين.

So D[i, j] is the answer to a smaller version of the same question: the distance between the first i letters of the source and the first j letters of the target. The final answer sits in the bottom-right corner, D[m, n].

إذن D[i, j] هو جواب نسخة أصغر من السؤال نفسه: المسافة بين أول i حرفاً من المصدر وأول j حرفاً من الهدف. والجواب النهائي يقع في الزاوية السفلية اليمنى، D[m, n].

Orientation, which you must fix in your head first

الاتجاه، وهو ما يجب أن تثبّته في ذهنك أولاً

On slide 88's filled table the header literally reads Src \ Tar. So:

في جدول الشريحة 88 المكتمل، تقول ترويسة الزاوية حرفياً Src \ Tar. إذن:

يثبّت المربع الاتجاه: الصفوف هي المصدر ومؤشرها i، والأعمدة هي الهدف ومؤشرها j.

Everything else follows from that one choice. Getting it backwards does not merely transpose your table, it swaps which operation each arrow means.

كل شيء آخر ينبني على هذا الاختيار وحده. وعكسه لا يقلب جدولك فقط، بل يبدّل معنى كل سهم فيه.

Initialization, the step people skip

التهيئة، الخطوة التي يتخطاها الناس

يعطي المربع التهيئة: D[0, 0] = 0، وكل خلية في العمود صفر تساوي رقم صفها i، وكل خلية في الصف صفر تساوي رقم عمودها j.

These are not placeholders and they are not zeros. They have a meaning:

هذه ليست خلايا حشو ولا أصفاراً، بل لها معنى:

• D[i, 0] is the distance from the first i source characters to the empty target. The only way to get to nothing is to delete everything, which costs i at one per deletion.

  D[i, 0] هي المسافة من أول i حرفاً من المصدر إلى هدف فارغ. والطريق الوحيد إلى لا شيء هو حذف كل شيء، وتكلفته i بحساب 1 لكل حذف.

• D[0, j] is the distance from the empty source to the first j target characters. You must insert all j of them, which costs j.

  D[0, j] هي المسافة من مصدر فارغ إلى أول j حرفاً من الهدف. يجب إدخالها كلها، وتكلفتها j.

Hence the top row and left column are always 0, 1, 2, 3, ... counting outward from the corner. The algorithm on slide 87 spells this out in a comment: "the zeroth row and column is the distance from the empty string."

لذلك الصف الأعلى والعمود الأيسر دائماً 0, 1, 2, 3, ... تصاعدياً من الزاوية. وخوارزمية الشريحة 87 تنص على هذا في تعليق: "the zeroth row and column is the distance from the empty string".

The recurrence

العلاقة التكرارية (recurrence)

Every interior cell looks at exactly three neighbours and takes the cheapest option.

كل خلية داخلية تنظر إلى ثلاث جارات فقط وتأخذ الأرخص.

هذه معادلة التكرار: قيمة D[i, j] هي الأصغر بين ثلاثة مرشحين لا أكثر. الأول من الأعلى D[i−1, j] + del وهو حذف (السهم ↑)، والثاني من اليسار D[i, j−1] + ins وهو إدخال (السهم ←)، والثالث من القُطر D[i−1, j−1] + sub وهو إبدال (السهم ↖). والـ backpointer يشير دائماً رجوعاً إلى الجارة الفائزة، أي نحو الزاوية العلوية اليسرى.

Read it as a question: "to reach this cell, which of the three neighbours is cheapest to arrive from, once I add the price of the move?"

اقرأها كسؤال: "للوصول إلى هذه الخلية، أي الجارات الثلاث أرخص قدوماً منها بعد إضافة ثمن الحركة؟"

يعرض المخطط أربع خلايا وثلاثة أسهم تتجه إلى الخلية التي تملأها D[i, j]: سهم من الأعلى D[i−1, j] وهو DELETE بتكلفة + 1، وسهم من اليسار D[i, j−1] وهو INSERT بتكلفة + 1، وسهم من القُطر D[i−1, j−1] وهو SUBSTITUTE بتكلفة + 0 إذا تطابق الحرفان و+ 2 إذا اختلفا في جدول هذا المقرر. والخلية تأخذ أصغر القيم الثلاث الواردة، والصفوف هي المصدر والأعمدة هي الهدف.

The cost model, slide 85 and the conflict you must know about

نموذج الكلفة، الشريحة 85 والتعارض الذي يجب أن تعرفه

This is the part that decides whether you get the question right, so read it slowly.

هذا هو الجزء الذي يحدد صواب جوابك، فاقرأه ببطء.

Slide 85 states the cost function in words:

تذكر الشريحة 85 دالة التكلفة بالكلمات:

ينص المربع على تكلفة الإبدال الواحدية: sub(a, b) تساوي 0 إذا كان a = b، وتساوي 1 فيما عدا ذلك. أي أن نص الشريحة 85 يجعل تكلفة الإبدال 1.

But slide 88, the worked table the instructor shows for intention to execution, ends on 8. A unit substitution cost cannot produce 8. It produces 5. The number 8 only comes out if a substitution costs 2, which is the classical Levenshtein variant used in the course textbook (Jurafsky and Martin), where a substitution is priced as a deletion plus an insertion.

لكن الشريحة 88، وهي الجدول المحلول الذي يعرضه المحاضر لتحويل intention إلى execution، تنتهي عند 8. وتكلفة إبدال تساوي 1 لا تستطيع أن تُنتج 8، بل تُنتج 5. والرقم 8 لا يظهر إلا إذا كانت تكلفة الإبدال 2، وهي صيغة Levenshtein الكلاسيكية المستخدمة في كتاب المقرر (Jurafsky and Martin)، حيث يُسعَّر الإبدال كحذف مع إدخال.

The slides are internally inconsistent here. Both conventions appear in the deck. You should know both, and you should know which number goes with which.

الشرائح متناقضة داخلياً هنا، فالاتفاقيتان كلتاهما موجودتان في الملف. اعرفهما كلتيهما، واعرف أي رقم يرافق أيّهما.

يقارن الجدول الاتفاقيتين. في اتفاقية Jurafsky and Martin: الحذف 1، والإدخال 1، والإبدال عند الاختلاف 2، وعند التطابق 0، فتكون المسافة بين intention وexecution هي 8، وهي اتفاقية جدول الشريحة 88 وجدول الـ backpointers في الشريحة 90. وفي اتفاقية Plain Levenshtein: الحذف 1، والإدخال 1، والإبدال عند الاختلاف 1، وعند التطابق 0، فتكون المسافة 5، وهي ما يوافق نص الشريحة 85.

Slide 85 also mentions two extensions you only need to recognize:

تذكر الشريحة 85 أيضاً امتدادين يكفي أن تعرفهما:

• Weighted substitution can encode confusions. Keyboard proximity is the stock example: substituting e for r should be cheaper than substituting e for q, because the first is a likelier typo.

  الـ Weighted substitution يمكنه ترميز الالتباسات. وقرب حروف لوحة المفاتيح هو المثال المعتاد: إبدال e بـ r يجب أن يكون أرخص من إبدالها بـ q، لأن الأول خطأ طباعي أرجح.

• Damerau-Levenshtein adds a fourth operation, transposition, so swapping two adjacent characters (teh to the) costs 1 instead of 2.

  الـ Damerau-Levenshtein يضيف عملية رابعة هي transposition، فيصبح تبديل حرفين متجاورين (teh إلى the) بتكلفة 1 بدل 2.

The algorithm, slide 87

الخوارزمية، الشريحة 87

Slide 87 shows the pseudocode. Here it is with the loop structure made obvious. Note that this figure uses n for the source length and m for the target, the opposite letters from slide 84. The orientation is the same in both (source on rows, target on columns); only the naming differs, so ignore the letters and watch the strings.

تعرض الشريحة 87 الشفرة الوصفية (pseudocode). وهي هنا ببنية حلقات واضحة. لاحظ أن هذا الشكل يستخدم n لطول المصدر وm لطول الهدف، أي عكس حرفي الشريحة 84. والاتجاه واحد في الاثنين (المصدر على الصفوف والهدف على الأعمدة)، والفرق في التسمية فقط، فأهمل الحروف وراقب السلاسل.

function MIN-EDIT-DISTANCE(source, target) returns min-distance

  n <- LENGTH(source)
  m <- LENGTH(target)
  Create a distance matrix D[n+1, m+1]

  # Initialization: the zeroth row and column is the
  # distance from the empty string
  D[0,0] = 0
  for each row i from 1 to n do
      D[i,0] <- D[i-1,0] + del-cost(source[i])
  for each column j from 1 to m do
      D[0,j] <- D[0,j-1] + ins-cost(target[j])

  # Recurrence relation:
  for each row i from 1 to n do
      for each column j from 1 to m do
          D[i,j] <- MIN( D[i-1,j]   + del-cost(source[i]),
                         D[i-1,j-1] + sub-cost(source[i], target[j]),
                         D[i,j-1]   + ins-cost(target[j]) )

  # Termination:
  return D[n,m]

تُقرأ الشفرة هكذا: أنشئ مصفوفة D[n+1, m+1]، ثم هيّئ الصف صفر والعمود صفر بتكلفة الإدخال والحذف المتراكمة، ثم مُرّ على الصفوف من 1 إلى n وداخلها على الأعمدة من 1 إلى m، وضع في كل خلية أصغر ثلاثة: الأعلى مع تكلفة الحذف، والقُطر مع تكلفة الإبدال، واليسار مع تكلفة الإدخال. والناتج النهائي هو D[n,m].

The nesting is the whole trick. Because the outer loop walks rows top to bottom and the inner loop walks columns left to right, every one of the three neighbours a cell needs has already been computed by the time you reach it. That is why a problem with exponentially many paths collapses to one pass over a grid.

التعشيق هو كل الحيلة. فلأن الحلقة الخارجية تمشي على الصفوف من الأعلى إلى الأسفل والداخلية على الأعمدة من اليسار إلى اليمين، فإن كل جارة من الجارات الثلاث التي تحتاجها الخلية تكون محسوبة سلفاً قبل أن تصل إليها. ولهذا تنهار مسألة ذات مسارات أسية إلى مرور واحد على الشبكة.

On paper this means: fill left to right, top to bottom. Finish a whole row before starting the next.

على الورق هذا يعني: املأ من اليسار إلى اليمين ومن الأعلى إلى الأسفل، وأكمل الصف كله قبل أن تبدأ الذي بعده.

Filling the table by hand, step by step

ملء الجدول باليد، خطوة بخطوة

This is the worked example from slide 88. Source intention (m = 9), target execution (n = 9), with del = 1, ins = 1, sub = 2 when the characters differ and 0 when they match.

هذا هو المثال المحلول من الشريحة 88. المصدر intention بطول m = 9، والهدف execution بطول n = 9، مع الحذف = 1، والإدخال = 1، والإبدال = 2 عند اختلاف الحرفين و0 عند تطابقهما.

1. Draw a grid with 10 rows and 10 columns. Label the rows with # then the letters of the source: # i n t e n t i o n. Label the columns with # then the letters of the target: # e x e c u t i o n.

   ارسم شبكة بعشرة صفوف وعشرة أعمدة. سمِّ الصفوف بـ # ثم حروف المصدر: # i n t e n t i o n. وسمِّ الأعمدة بـ # ثم حروف الهدف: # e x e c u t i o n.

2. Write 0 1 2 3 4 5 6 7 8 9 across the top row and the same down the left column. Do this before anything else.

   اكتب 0 1 2 3 4 5 6 7 8 9 في الصف الأعلى ومثلها نازلاً في العمود الأيسر. افعل هذا قبل أي شيء آخر.

3. For each interior cell, compute three candidates: above + 1, left + 1, diagonal + (0 if the row letter equals the column letter, else 2).

   لكل خلية داخلية احسب ثلاثة مرشحين: الأعلى زائد 1، واليسار زائد 1، والقُطر زائد 0 إذا تساوى حرف الصف وحرف العمود أو زائد 2 إذا اختلفا.

4. Write the smallest of the three. If you want the alignment later, also note which neighbour won.

   اكتب أصغر الثلاثة. وإذا أردت الـ alignment لاحقاً، فسجّل أيضاً أي جارة فازت.

5. Work left to right, finish each row, then drop to the next.

   اعمل من اليسار إلى اليمين، وأكمل كل صف، ثم انزل إلى الذي بعده.

6. The answer is the bottom-right cell.

   الجواب هو الخلية السفلية اليمنى.

INITIALIZATION
  row 0:   0  1  2  3  4  5  6  7  8  9      (insert j target chars)
  col 0:   0  1  2  3  4  5  6  7  8  9      (delete i source chars)


ROW 1,  source letter 'i'

 D[1,1]  row 'i'  vs  col 'e'   ->  differ, sub = 2
         above     D[0,1] + 1 = 1 + 1 = 2
         left      D[1,0] + 1 = 1 + 1 = 2
         diagonal  D[0,0] + 2 = 0 + 2 = 2
         min = 2                                   D[1,1] = 2

 D[1,2]  'i' vs 'x'  ->  differ, sub = 2
         above     D[0,2] + 1 = 2 + 1 = 3
         left      D[1,1] + 1 = 2 + 1 = 3
         diagonal  D[0,1] + 2 = 1 + 2 = 3
         min = 3                                   D[1,2] = 3

 D[1,3]  'i' vs 'e'  ->  differ, sub = 2
         above  3+1 = 4    left  3+1 = 4    diag  2+2 = 4     = 4
 D[1,4]  'i' vs 'c'  differ:  4+1=5,  4+1=5,  3+2=5           = 5
 D[1,5]  'i' vs 'u'  differ:  5+1=6,  5+1=6,  4+2=6           = 6
 D[1,6]  'i' vs 't'  differ:  6+1=7,  6+1=7,  5+2=7           = 7

 D[1,7]  row 'i'  vs  col 'i'   ->  MATCH, sub = 0
         above     D[0,7] + 1 = 7 + 1 = 8
         left      D[1,6] + 1 = 7 + 1 = 8
         diagonal  D[0,6] + 0 = 6 + 0 = 6     <-- free, and it wins
         min = 6                                   D[1,7] = 6

 D[1,8]  'i' vs 'o'  differ
         above     D[0,8] + 1 = 8 + 1 = 9
         left      D[1,7] + 1 = 6 + 1 = 7     <-- wins
         diagonal  D[0,7] + 2 = 7 + 2 = 9
         min = 7                                   D[1,8] = 7

 D[1,9]  'i' vs 'n'  differ:  9+1=10,  7+1=8,  8+2=10         = 8

 ROW 1 COMPLETE:   1  2  3  4  5  6  7  6  7  8


ROW 2,  source letter 'n'

 D[2,1]  'n' vs 'e'  ->  differ, sub = 2
         above     D[1,1] + 1 = 2 + 1 = 3
         left      D[2,0] + 1 = 2 + 1 = 3
         diagonal  D[1,0] + 2 = 1 + 2 = 3
         min = 3                                   D[2,1] = 3

 D[2,2]  'n' vs 'x'  differ:  3+1=4,  3+1=4,  2+2=4           = 4
 D[2,3]  'n' vs 'e'  differ:  4+1=5,  4+1=5,  3+2=5           = 5
 D[2,4]  'n' vs 'c'  differ:  5+1=6,  5+1=6,  4+2=6           = 6
 D[2,5]  'n' vs 'u'  differ:  6+1=7,  7,  5+2=7               = 7
 D[2,6]  'n' vs 't'  differ:  7+1=8,  8,  6+2=8               = 8

 D[2,7]  'n' vs 'i'  differ
         above     D[1,7] + 1 = 6 + 1 = 7     <-- wins
         left      D[2,6] + 1 = 8 + 1 = 9
         diagonal  D[1,6] + 2 = 7 + 2 = 9
         min = 7                                   D[2,7] = 7

 D[2,8]  'n' vs 'o'  differ:  7+1=8,  7+1=8,  6+2=8           = 8

 D[2,9]  row 'n'  vs  col 'n'  ->  MATCH, sub = 0
         above     D[1,9] + 1 = 8 + 1 = 9
         left      D[2,8] + 1 = 8 + 1 = 9
         diagonal  D[1,8] + 0 = 7 + 0 = 7     <-- free, and it wins
         min = 7                                   D[2,9] = 7

 ROW 2 COMPLETE:   2  3  4  5  6  7  8  7  8  7


COLUMN 1 (target letter 'e'), computed the same way down the grid

 D[1,1]  'i' vs 'e'  differ:  min(1+1, 1+1, 0+2) = 2
 D[2,1]  'n' vs 'e'  differ:  min(2+1, 2+1, 1+2) = 3
 D[3,1]  't' vs 'e'  differ:  min(3+1, 3+1, 2+2) = 4

 D[4,1]  row 'e'  vs  col 'e'  ->  MATCH, sub = 0
         above     D[3,1] + 1 = 4 + 1 = 5
         left      D[4,0] + 1 = 4 + 1 = 5
         diagonal  D[3,0] + 0 = 3 + 0 = 3     <-- free, and it wins
         min = 3                                   D[4,1] = 3

 D[5,1]  'n' vs 'e'  differ:  above 3+1=4, left 5+1=6, diag 4+2=6   = 4
 D[6,1]  't' vs 'e'  differ:  above 4+1=5, left 6+1=7, diag 5+2=7   = 5
 D[7,1]  'i' vs 'e'  differ:  above 5+1=6, left 7+1=8, diag 6+2=8   = 6
 D[8,1]  'o' vs 'e'  differ:  above 6+1=7, left 8+1=9, diag 7+2=9   = 7
 D[9,1]  'n' vs 'e'  differ:  above 7+1=8, left 9+1=10, diag 8+2=10 = 8

 COLUMN 1 COMPLETE (top to bottom):  1  2  3  4  3  4  5  6  7  8

The completed table, slide 88

الجدول المكتمل، الشريحة 88

This is the artifact. The highlighted cells are the optimal path, which we recover in the next section.

هذا هو الناتج النهائي. والخلايا المظللة هي المسار الأمثل، وسنستعيده في القسم التالي.

هذا جدول الشريحة 88 كاملاً: الصفوف حروف intention، والأعمدة حروف execution، والعلامة # تعني السلسلة الفارغة. وكل خلية D[i, j] هي أقل مسافة بين أول i حرفاً من المصدر وأول j حرفاً من الهدف، وهي أصغر ثلاثة مرشحين: الأعلى زائد 1، واليسار زائد 1، والقُطر زائد 2 عند الاختلاف أو زائد 0 عند التطابق. والصف الأعلى والعمود الأيسر يعدّان من 0 إلى 9، والجواب في الخلية السفلية اليمنى وهو 8. والخلايا المظللة ترسم المسار الأمثل، ويُقرأ رجوعاً من الزاوية السفلية اليمنى إلى الزاوية العلوية اليسرى.

يقول المربع إن المسافة بين intention وexecution هي D[9, 9] وتساوي 8، بشرط أن تكون تكلفة الإبدال 2.

Three things to check whenever you finish a table like this, as a self-audit:

ثلاثة أمور تتحقق منها كلما أكملت جدولاً كهذا، كتدقيق ذاتي:

• Top row and left column count up from 0. If they do not, stop and redo.

  الصف الأعلى والعمود الأيسر يعدّان تصاعدياً من 0. فإن لم يكونا كذلك، فتوقف وأعِد.

• No cell differs from its left or upper neighbour by more than 1. That is structurally guaranteed, since you can always reach a cell from either one for a cost of 1. Look at the table: every horizontal and vertical step is +1 or −1. A jump of 2 means an arithmetic slip.

  لا تختلف أي خلية عن جارتها اليسرى أو العلوية بأكثر من 1. وهذا مضمون بنيوياً، لأنك تستطيع دائماً الوصول إلى الخلية من أي منهما بتكلفة 1. انظر إلى الجدول: كل خطوة أفقية أو عمودية هي +1 أو −1، والفرق بمقدار 2 يعني زلة حسابية.

• The final answer cannot exceed max(m, n) × (cost of the priciest single-character fix). Here m = n = 9, so 8 is comfortably plausible.

  الجواب النهائي لا يمكن أن يتجاوز max(m, n) مضروباً في تكلفة أغلى إصلاح لحرف واحد. وهنا m = n = 9، فالرقم 8 معقول تماماً.

Backtrace: getting the alignment back, slides 89 and 90

التتبع العكسي (Backtrace): استعادة المحاذاة، الشريحتان 89 و90

The table gives you 8. It does not tell you what the eight edits were. Recovering those is a separate step.

يعطيك الجدول الرقم 8، لكنه لا يقول لك ما هي التعديلات الثمانية. واستعادتها خطوة منفصلة.

Slide 89's method: store an argmin pointer in each cell, recording which of the three neighbours produced the minimum. Then walk backwards from D[m, n] to D[0, 0] following the pointers, and read the operations off in reverse.

طريقة الشريحة 89: احفظ مؤشر argmin في كل خلية، يسجّل أي الجارات الثلاث أنتجت الأصغر. ثم امشِ رجوعاً من D[m, n] إلى D[0, 0] متبعاً المؤشرات، واقرأ العمليات بالعكس.

The word argmin is doing real work there. The min gives you the winning value, which is what you write in the cell. The argmin gives you the winning argument, which is which neighbour it came from. You need both, and only the first one is stored by default.

كلمة argmin تعمل عملاً حقيقياً هنا. فالـ min تعطيك القيمة الفائزة وهي ما تكتبه في الخلية، والـ argmin تعطيك المُعامل الفائز وهو الجارة التي جاءت منها. أنت تحتاج الاثنين، والأول وحده هو المحفوظ تلقائياً.

Slide 90 shows the same table with arrows drawn in every cell. Many cells have two or three arrows, because the three candidates frequently tie. Slide 89 states the consequence directly: multiple optimal alignments can exist. Any one of them is a correct answer, and they all cost 8.

تعرض الشريحة 90 الجدول نفسه مع أسهم مرسومة في كل خلية. وكثير من الخلايا فيها سهمان أو ثلاثة، لأن المرشحين الثلاثة يتعادلون كثيراً. وتنص الشريحة 89 على النتيجة مباشرة: يمكن أن يوجد أكثر من alignment أمثل. وأي واحد منها جواب صحيح، وكلها تكلّف 8.

at D[9,9]=8   row 'n', col 'n'  MATCH
              diagonal D[8,8]=8, plus 0, gives 8   -> take diagonal
at D[8,8]=8   'o' vs 'o'  MATCH,  D[7,7]=8 + 0 = 8 -> diagonal
at D[7,7]=8   'i' vs 'i'  MATCH,  D[6,6]=8 + 0 = 8 -> diagonal
at D[6,6]=8   't' vs 't'  MATCH,  D[5,5]=8 + 0 = 8 -> diagonal
at D[5,5]=8   'n' vs 'u'  differ. all three tie at 8:
                above D[4,5]=7 +1, left D[5,4]=7 +1, diag D[4,4]=6 +2
              take the diagonal -> SUBSTITUTE n with u
at D[4,4]=6   'e' vs 'c'  differ
                above D[3,4]=7 +1 = 8
                left  D[4,3]=5 +1 = 6   <-- only winner
                diag  D[3,3]=6 +2 = 8
              take left -> INSERT c
at D[4,3]=5   'e' vs 'e'  MATCH,  D[3,2]=5 + 0 = 5 -> diagonal, free
at D[3,2]=5   't' vs 'x'  differ, diag D[2,1]=3 + 2 = 5 -> SUBSTITUTE t with x
at D[2,1]=3   'n' vs 'e'  differ, diag D[1,0]=1 + 2 = 3 -> SUBSTITUTE n with e
at D[1,0]=1   column 0, so the only possible move is up -> DELETE i
at D[0,0]=0   done

READ THE OPERATIONS FORWARD:

  delete      i                 cost 1
  substitute  n -> e            cost 2
  substitute  t -> x            cost 2
  match       e                 cost 0
  insert      c                 cost 1
  substitute  n -> u            cost 2
  match       t                 cost 0
  match       i                 cost 0
  match       o                 cost 0
  match       n                 cost 0
                                -----
                          total = 8     confirms D[9,9]

WRITTEN AS AN ALIGNMENT (this is slide 81's figure):

  I N T E * N T I O N
  | | | | | | | | | |
  * E X E C U T I O N
  d s s   i s

The same table with unit substitution cost

الجدول نفسه بكلفة استبدال تساوي واحداً

If the exam says every operation costs 1, here is the whole table. The answer is 5, and the optimal path is a straight diagonal.

إذا قال الامتحان إن كل عملية تكلّف 1، فهذا هو الجدول كاملاً. الجواب 5، والمسار الأمثل قُطر مستقيم.

هذا هو الجدول نفسه بتكلفة إبدال واحدية. الصفوف حروف intention، والأعمدة حروف execution، وكل خلية D[i, j] هي أصغر ثلاثة مرشحين: الأعلى زائد 1، واليسار زائد 1، والقُطر زائد 1 عند الاختلاف أو زائد 0 عند التطابق. والجواب في الزاوية السفلية اليمنى وهو 5 لا 8، والخلايا المظللة تسير على القُطر مباشرة من الزاوية العلوية اليسرى.

The alignment here is simpler, because with substitution priced at 1 nothing ever beats the diagonal:

الـ alignment هنا أبسط، لأن القُطر لا يُغلَب أبداً عندما تُسعَّر تكلفة الإبدال بـ 1:

I N T E N T I O N
| | | | | | | | |
E X E C U T I O N
s s s s s        

يعرض المربع رصفاً بلا فراغات: INTENTION فوق EXECUTION، وتحت أول خمسة أعمدة الحرف s أي إبدال، وبقية الأعمدة تطابقات مجانية.

Five substitutions, zero insertions, zero deletions, total 5. Both strings have length 9, so no gaps are needed at all.

خمسة إبدالات، وصفر إدخالات، وصفر حذوفات، والمجموع 5. وطول كل من السلسلتين 9، فلا حاجة إلى أي فراغ.

Compare the two tables for a moment. Under sub = 2 the numbers climb much faster along the top-left region, because the cheap diagonal shortcut is gone. Under sub = 1 the values stay low and the optimal path is the straight diagonal. Same algorithm, same strings, one number changed.

قارن الجدولين لحظة. عند الإبدال = 2 تصعد الأرقام أسرع كثيراً في المنطقة العلوية اليسرى، لأن اختصار القُطر الرخيص اختفى. وعند الإبدال = 1 تبقى القيم منخفضة ويكون المسار الأمثل قُطراً مستقيماً. الخوارزمية نفسها، والسلسلتان نفسهما، ورقم واحد تغيّر.

Complexity, slide 91

التعقيد، الشريحة 91

يلخّص الجدول التعقيد: الزمن O(mn) لأن هناك خلية واحدة لكل زوج (i, j) وكل خلية تعمل عملاً ثابتاً (ثلاث جمعيات وmin لثلاث قيم). والمكان بالجدول الكامل O(mn) لأنك تحفظ كل خلية. وإذا أردت المسافة فقط فالمكان O(min(m, n))، لأن الخلية تقرأ الصف السابق والخلية التي على يسارها فقط، فيكفي صف واحد من التاريخ.

The min(m, n) in the space bound is not a typo. If you only need the number, keep one row at a time, and orient the table so the shorter string is the one indexing that row. That gives you a buffer of length min(m, n) + 1.

الـ min(m, n) في حدّ المكان ليست خطأ مطبعياً. فإذا أردت الرقم وحده، احفظ صفاً واحداً في كل مرة، ووجّه الجدول بحيث تكون السلسلة الأقصر هي التي تفهرس ذلك الصف. فتحصل على مخزن طوله min(m, n) + 1.

Slide 91's final bullet is the catch, and it is the trade-off worth being able to state: alignment requires storing backpointers, or recomputing. The moment you want the edit sequence and not just the distance, you lose the space saving, because a single row cannot tell you where the path came from.

النقطة الأخيرة في الشريحة 91 هي المقايضة التي يجدر أن تستطيع صياغتها: الـ alignment يحتاج حفظ backpointers، أو إعادة الحساب. فلحظة أن تريد تسلسل التعديلات لا المسافة فقط، تفقد التوفير في المكان، لأن صفاً واحداً لا يستطيع أن يخبرك من أين جاء المسار.

يقابل المربع بين الحالتين: إذا أردت الرقم فقط فالمكان O(min(m, n))، وإذا أردت الـ alignment أيضاً فالمكان O(mn).

Key takeaways for all of Lecture 02, slide 92

الخلاصات الرئيسية للمحاضرة 02 كلها، الشريحة 92

This is the last page of the lecture, so slide 92 wraps up the whole deck, not just edit distance. Each bullet is a one-line summary of one of the earlier pages.

هذه آخر صفحة في المحاضرة، فالشريحة 92 تلخّص الملف كله لا الـ edit distance وحده. وكل نقطة فيها سطر واحد يلخّص إحدى الصفحات السابقة.

يسرد الجدول خلاصات المحاضرة ومصدر كل منها: "الكلمة" ليست وحدة عالمية والـ tokenization قرار تصميمي، ونمو الـ vocabulary له ذيل ثقيل (Zipf وHeaps) وهو ما يحفّز الـ subwords، والـ morphology تختلف بين اللغات، وUnicode وUTF-8 يجعلان النص متعدد اللغات ممكناً، والـ BPE يتعلم مفردات مدمجة قابلة لإعادة الاستخدام، والـ Regex أداة عملية للتطبيع، وأخيراً أن minimum edit distance خوارزمية DP أساسية لقياس تشابه السلاسل، وهي هذه الصفحة.

Slide 93 is the acknowledgment: the slides are drawn mainly from Jurafsky and Martin, Speech and Language Processing, 3rd edition online manuscript. That is the same textbook whose substitution cost of 2 produces the 8 on slide 88, which is a useful thing to remember about where the convention comes from.

الشريحة 93 هي الإشارة إلى المصدر: الشرائح مأخوذة أساساً من Jurafsky and Martin، Speech and Language Processing، النسخة الثالثة المنشورة إلكترونياً. وهو الكتاب نفسه الذي تُنتج فيه تكلفة الإبدال 2 الرقم 8 في الشريحة 88، وهذه معلومة مفيدة عن مصدر الاتفاقية.

Thirty-second recap

خلاصة في ثلاثين ثانية