Generating candidates with edit distanceتوليد المرشحين بمسافة التحرير

Someone types acress. No English dictionary contains it, so this is a Non-word error: detection is a simple lookup. Correction is the hard half. What did they mean? Your mind probably offers actress or across within a second, and maybe acres. You did not search a dictionary alphabetically. You searched the neighbourhood of the typo, words that look like it.

يكتب شخص ما acress. لا يحتوي أي قاموس إنجليزي على هذه الكلمة، لذا فهذا non-word error (خطأ ينتج كلمة غير موجودة): اكتشافه مجرد بحث بسيط في القاموس. التصحيح هو النصف الصعب. ماذا كان يقصد؟ غالبًا يقترح عليك ذهنك actress أو across خلال ثانية، وربما acres. لم تبحث في القاموس أبجديًا. بل بحثت في جوار الخطأ، أي الكلمات التي تشبهه.

From a typo to a list of suspectsمن الخطأ الإملائي إلى قائمة من المشتبه بهم

Candidate generation is that neighbourhood search made explicit. It turns one observed string x into a short list of real words w, and only those words go on to the Noisy channel model, where each is scored by P(x|w)P(w). The argmax in that formula ranges over the candidate list, not over the whole vocabulary. That is the first thing to understand about this step: it decides which answers are even possible. If the right word is not generated, no amount of good scoring can recover it.

Candidate generation (توليد المرشحين) هو هذا البحث في الجوار وقد صار صريحًا. فهو يحوّل سلسلة واحدة مرصودة x إلى قائمة قصيرة من الكلمات الحقيقية w، وهذه الكلمات وحدها تنتقل إلى noisy channel model، حيث تُعطى كل منها درجة بالقيمة P(x|w)P(w). الـ argmax في هذه الصيغة يمتد على قائمة المرشحين، لا على المفردات كلها. هذا أول ما يجب فهمه عن هذه الخطوة: إنها تحدد أي الإجابات ممكنة أصلًا. إذا لم تُولَّد الكلمة الصحيحة، فلن يستطيع أي قدر من حساب الدرجات الجيد استعادتها.

The lecture names two ways a real word can be near a typo.

تذكر المحاضرة طريقتين يمكن أن تكون بهما كلمة حقيقية قريبة من خطأ إملائي.

• Similar spelling. The word has a small Edit distance to the error: a few letters inserted, deleted, replaced or swapped turn one into the other. This catches typographical errors, slips of the fingers such as actress typed as acress.تهجئة متشابهة. للكلمة edit distance (مسافة تعديل) صغيرة إلى الخطأ: بضعة أحرف تُدرج أو تُحذف أو تُستبدل أو تُبدَّل مواضعها فتحوّل إحداهما إلى الأخرى. هذا يلتقط typographical errors (أخطاء الطباعة)، وهي زلّات الأصابع مثل كتابة actress على شكل acress.
• Similar pronunciation. The word sounds like the error. Each string is first mapped to an approximate pronunciation, and candidates are words whose pronunciation is a small edit distance from the pronunciation of the typo. This catches cognitive errors, where the writer spells by sound, which letter edits alone can miss when the spelling is far off but the sound is close.نطق متشابه. الكلمة تبدو في صوتها مثل الخطأ. تُحوَّل كل سلسلة أولًا إلى نطق تقريبي، والمرشحون هم الكلمات التي يبعد نطقها مسافة تعديل صغيرة عن نطق الخطأ. هذا يلتقط cognitive errors (الأخطاء الإدراكية)، حين يتهجّى الكاتب الكلمة بحسب صوتها، وهي أخطاء قد تفوت تعديلات الأحرف وحدها عندما تكون التهجئة بعيدة لكن الصوت قريب.

Both routes use the same tool, edit distance, applied to different strings: letters in one case, pronunciation symbols in the other. GNU aspell, for example, generates candidates by comparing Metaphone keys, and later systems fold this into a Phonetic error model. Part 8 returns to those. For the rest of this part we work with spelling, which is what the acress example and the Kernighan, Church and Gale data use.

يستخدم الطريقان الأداة نفسها، مسافة التعديل، مطبّقة على سلاسل مختلفة: الأحرف في حالة، ورموز النطق في الأخرى. فبرنامج GNU aspell مثلًا يولّد المرشحين بمقارنة مفاتيح Metaphone، والأنظمة اللاحقة تدمج ذلك في phonetic error model (نموذج أخطاء صوتي). يعود الجزء 8 إلى هذه الأنظمة. في بقية هذا الجزء نعمل على التهجئة، وهي ما يستخدمه مثال acress وبيانات Kernighan وChurch وGale.

Take the intended word actress and imagine the typist hurrying. Their finger skips the t, and acress comes out. Now take caress: the typist hits a before c, and acress comes out again. Six different real words can turn into the same typo with a single slip each. The table on slide 15 lists every one of them and names the slip.

خذ الكلمة المقصودة actress وتخيّل الكاتب مستعجلًا. يتخطى إصبعه الحرف t، فتخرج acress. والآن خذ caress: يضغط الكاتب a قبل c، فتخرج acress مرة أخرى. ست كلمات حقيقية مختلفة يمكن أن تتحول إلى الخطأ نفسه بزلّة واحدة لكل منها. الجدول في الشريحة 15 يسرد كل واحدة منها ويسمّي الزلّة.

Four kinds of single slipأربعة أنواع من الزلّة الواحدة

Spelling correction uses Damerau-Levenshtein distance, which counts four operations, each at cost 1:

يستخدم تصحيح التهجئة Damerau-Levenshtein distance، التي تحتسب أربع عمليات، تكلفة كل منها 1:

• Deletion: a letter of the intended word is left out (actress becomes acress).Deletion (حذف): يُترك حرف من الكلمة المقصودة دون كتابة (actress تصبح acress).
• Insertion: an extra letter is typed (cress becomes acress).Insertion (إدراج): يُكتب حرف زائد (cress تصبح acress).
• Substitution: one letter is typed in place of another (across becomes acress).Substitution (استبدال): يُكتب حرف مكان حرف آخر (across تصبح acress).
• Transposition: two adjacent letters are swapped (caress becomes acress).Transposition (تبديل مواضع): يتبادل حرفان متجاوران موضعيهما (caress تصبح acress).

The convention that decides exam answersالاصطلاح الذي يحسم إجابات الامتحان

The type always names what the typist did to the correct word to produce the error. Read every row as intended word → typo, never the other way. That is why the columns are called correct letter and error letter: the correct letter is what should have been typed, the error letter is what was typed, and a dash means nothing. So actress has correct letter t and error letter dash: a t should have been there and nothing was typed, a deletion. cress has correct letter dash and error letter a: nothing should have been there and an a was typed, an insertion.

يسمّي النوعُ دائمًا ما فعله الكاتب بالكلمة الصحيحة لينتج الخطأ. اقرأ كل صف على أنه intended word → typo (من الكلمة المقصودة إلى الخطأ)، لا العكس أبدًا. لهذا سُمّي العمودان correct letter (الحرف الصحيح) وerror letter (الحرف الخاطئ): الحرف الصحيح هو ما كان يجب أن يُكتب، والحرف الخاطئ هو ما كُتب فعلًا، والشرطة تعني لا شيء. إذن لـ actress حرف صحيح t وحرف خاطئ شرطة: كان يجب أن يوجد t ولم يُكتب شيء، أي حذف. ولـ cress حرف صحيح شرطة وحرف خاطئ a: لم يكن يجب أن يوجد شيء وكُتب a، أي إدراج.

Why transposition gets its own operationلماذا يحصل تبديل المواضع على عملية خاصة به

In lecture 2 you computed minimum edit distance with three operations only, insertion, deletion and substitution. That is Levenshtein distance. Under it, caress and acress are two edits apart: two substitutions, or a deletion plus an insertion. Damerau observed in 1964 that swapping two neighbouring keys is one of the commonest typing mistakes, so he counted it as a single edit. Adding that one operation is the only difference, and it is what makes caress a distance-1 candidate.

في المحاضرة 2 حسبت مسافة التعديل الدنيا (minimum edit distance) بثلاث عمليات فقط: الإدراج والحذف والاستبدال. هذه هي مسافة Levenshtein. وفقها، تبعد caress وacress تعديلين: استبدالين، أو حذفًا مع إدراج. لاحظ Damerau عام 1964 أن تبديل مفتاحين متجاورين من أكثر أخطاء الطباعة شيوعًا، فاحتسبه تعديلًا واحدًا. إضافة هذه العملية الواحدة هي الفرق الوحيد، وهي ما يجعل caress مرشحًا على مسافة 1.

How does a program actually find those six words? It does not compare acress against every dictionary entry. It runs the four operations in reverse on the typo itself, every possible way, and then asks the dictionary which of the results exist. Peter Norvig's well-known corrector does exactly this in a few lines. The number of strings it produces is worth computing once, because it explains the whole design.

كيف يجد البرنامج هذه الكلمات الست فعلًا؟ إنه لا يقارن acress بكل مدخل في القاموس. بل يشغّل العمليات الأربع بالعكس على الخطأ نفسه، بكل طريقة ممكنة، ثم يسأل القاموس أي النتائج موجود. مصحح Peter Norvig المعروف يفعل هذا بالضبط في بضعة أسطر. عدد السلاسل التي ينتجها يستحق أن يُحسب مرة واحدة، لأنه يفسّر التصميم كله.

This is why the dictionary filter, not the edit operations, is the key step. Generating strings is trivial and cheap; almost all of them are nonsense. Intersecting them with the dictionary is what turns a few hundred strings into a handful of real candidates, each with its edit type and position recorded for the channel model. Because the count is linear in n, edit-1 generation is fast for any realistic word.

لهذا السبب فإن فلتر القاموس، لا عمليات التعديل، هو الخطوة الأساسية. توليد السلاسل أمر تافه ورخيص؛ وكلها تقريبًا بلا معنى. تقاطعها مع القاموس هو ما يحوّل بضع مئات من السلاسل إلى حفنة من المرشحين الحقيقيين، مع تسجيل نوع التعديل وموضعه لكل منها لصالح نموذج القناة. ولأن العدد خطي في n، فإن توليد السلاسل على بُعد تعديل واحد سريع لأي كلمة واقعية.

Why stop at one or two editsلماذا نتوقف عند تعديل واحد أو تعديلين

The radius is set by data on real errors. Damerau's 1964 study found that more than 80% of the misspellings he examined were a single insertion, deletion, substitution or transposition, and the slide's rule follows: about 80% of errors are within edit distance 1, almost all within 2. Norvig's experiment agrees on the second half: in his development set only 3 of 270 errors were further than two edits from the correction.

يُحدَّد نصف القطر ببيانات الأخطاء الحقيقية. وجدت دراسة Damerau عام 1964 أن أكثر من 80% من الأخطاء الإملائية التي فحصها كانت إدراجًا واحدًا أو حذفًا أو استبدالًا أو تبديل مواضع، ومنها تأتي قاعدة الشريحة: نحو 80% من الأخطاء ضمن مسافة تعديل 1، وكلها تقريبًا ضمن 2. وتجربة Norvig تتفق مع الشطر الثاني: في مجموعة التطوير لديه كان 3 فقط من 270 خطأ أبعد من تعديلين عن التصحيح.

Going further is expensive and rarely useful. Applying the generator twice squares the work: for acress the edit-2 set has on the order of 335 × 349 ≈ 117,000 raw strings, and the number of real words inside that wider ring grows too, so the channel model has more distractors to separate. Norvig's corrector therefore tries distance 1 first and widens to distance 2 only when distance 1 finds no known word.

الذهاب أبعد مكلف ونادرًا ما يفيد. تطبيق المولّد مرتين يربّع العمل: لكلمة acress تضم مجموعة التعديلين ما يقارب 335 × 349 ≈ 117,000 سلسلة خام، ويزداد أيضًا عدد الكلمات الحقيقية داخل هذه الحلقة الأوسع، فيكون أمام نموذج القناة مشتّتات أكثر عليه التمييز بينها. لذلك يجرّب مصحح Norvig المسافة 1 أولًا، ولا يتوسع إلى المسافة 2 إلا عندما لا تجد المسافة 1 أي كلمة معروفة.

Space and hyphen as extra editsالمسافة والشرطة كتعديلات إضافية

Some errors are not inside a word at all. A typist who misses the space bar produces thisidea for this idea; one who drops a hyphen produces inlaw for in-law. Neither is one letter edit from a single dictionary word, so the plain generator returns nothing. Allowing the generator to insert a space or a hyphen between two letters fixes this, as long as the lookup then checks each piece. It adds only 2(n - 1) strings.

بعض الأخطاء ليست داخل كلمة أصلًا. الكاتب الذي يخطئ مفتاح المسافة ينتج thisidea بدلًا من this idea؛ ومن يُسقط شرطة ينتج inlaw بدلًا من in-law. لا يبعد أي منهما تعديل حرف واحد عن كلمة واحدة في القاموس، لذا لا يعيد المولّد العادي شيئًا. السماح للمولّد بإدراج مسافة أو شرطة بين حرفين يحل المشكلة، بشرط أن يفحص البحث بعد ذلك كل جزء على حدة. وهذا لا يضيف إلا 2(n - 1) سلسلة.

Try the generator below. Start with acress and check that the counts match the worked example and that the survivors match slide 15, both acres rows included. Then try teh, graffe, and the two run-together presets. Notice that the survivor column names the typist's error even though the generator ran the opposite operation. The run-together presets switch the space and hyphen option on; switch it on for acress too and a cress appears as an eighth row, a small reminder that every extra kind of edit also admits extra distractors.

جرّب المولّد أدناه. ابدأ بـ acress وتحقق من أن الأعداد تطابق المثال المحلول وأن الناجين يطابقون الشريحة 15، بما في ذلك صفّا acres كلاهما. ثم جرّب teh وgraffe والإعدادين المسبقين للكلمات الملتصقة. لاحظ أن عمود الناجين يسمّي خطأ الكاتب رغم أن المولّد نفّذ العملية المعاكسة. الإعدادان المسبقان للكلمات الملتصقة يفعّلان خيار المسافة والشرطة؛ فعّله مع acress أيضًا وستظهر a cress صفًا ثامنًا، تذكيرًا صغيرًا بأن كل نوع إضافي من التعديل يُدخل أيضًا مشتّتات إضافية.