جدول تحرير البادئات: استعادة خطوات الإدراج والحذف والاستبدال والتحقق منها

البادئتان ومعنى خانة الجدول

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

خانة الجدول عند صف i وعمود j تعني أقل كلفة لتحويل أول i عناصر من المصدر إلى أول j عناصر من الهدف. هذان الرقمان طولان لبادئتين، لا فهرسا حرفين بالضرورة. حين يكون i صفرًا تكون بادئة المصدر فارغة، وحين يبلغ طول المصدر الكامل نكون قد أخذناه كله. هذا التعريف يجعل حدود الجدول قابلة للفهم قبل ملء أي خانة.

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

[1]

ABCD إلى AXCE باستبدالين

نختار المصدر ABCD والهدف AXCE، وكلاهما أربعة أحرف. نبقي A الأولى، ونستبدل B بحرف X، ونبقي C، ثم نستبدل D بحرف E. النتيجة AXCE والتعديلات اثنان. خطوتا الإبقاء لا تغيران حرفًا، ولذلك لا ندخلهما في عدد التعديلات رغم أن قائمة الشاهد ستسجلهما لتوضيح استهلاك المصدر وإنتاج الهدف.

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

الأحرف والرموز هنا مؤلفة للتعليم، وليست أسماء سجلات حقيقية أو نتيجة أداة تصحيح. الرسم الرئيسي سيعرض تكاليف بادئات هذه السلسلتين، والرسم الداخلي سيعرض keep وreplace بجانب ما يستهلكه الشاهد وما يخرجه. هذان الشكلان يصفان بيانات المثال نفسه، ولا ينقلان صورة من المصدر الذي عرفنا منه اسم المسافة.

صف الصفر وعمود الصفر

تحويل بادئة مصدر فارغة إلى أول j أحرف من الهدف يحتاج j إدراجات في عقدنا، لذلك صف البداية هو 0 ثم 1 ثم 2 ثم 3 ثم 4. وبالمثل، تحويل أول i أحرف من المصدر إلى هدف فارغ يحتاج i حذوفات، فيكون عمود البداية بالقيم نفسها. لا نقول إن الخانة 4 حرف قيمته أربعة؛ هي عدد العمليات لبنية بادئة محددة.

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

والجدول في المثال خمسة صفوف وخمسة أعمدة رغم أن النصين أربعة أحرف لكل منهما. أضفنا حالة البادئة الفارغة إلى الأطوال من واحد إلى أربعة. حين ننظر إلى الصف أربعة والعمود أربعة نصل إلى سؤال المصدر والهدف كاملين. الخلط بين أربعة مواضع أحرف وخمس حالات أطوال قد يجعل الرسم أو فهرسة الكود ينقصان حد البداية.

ثلاثة مرشحين للخلية

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

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

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

المطابقة صفر كلفة لا تحرير

عند مقارنة A الأولى بالمقابلة لها في الهدف، تتساويان. ننقل الكلفة من بادئتين فارغتين ونضيف صفرًا، فتصير الخانة صفرًا. وعند C في الموضع الثالث من كلتا السلسلتين، نبقيها ونتابع من القطر السابق الذي كانت كلفته واحدًا. لا تزيد المسافة لمجرد أننا قرأنا حرفًا جديدًا نجح في المطابقة.

في قائمة الشاهد نسجل الإبقاء باسم keep، ونكتب أن take هو الحرف الذي نقرأه من المصدر وput هو الحرف الذي ننتجه. يمكن أن تحتوي القائمة أربعة صفوف في مثالنا، لكن صفين فقط منها تحرير فعلي. لذلك لا نستعمل طول قائمة الخطوات بوصفه المسافة دون فصل الإبقاء من التعديل في عقد المخرج.

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

تتبع جدول خمسة في خمسة

بعد صف الصفر، صف بادئة A هو 1 ثم 0 ثم 1 ثم 2 ثم 3. وصف AB هو 2 ثم 1 ثم 1 ثم 2 ثم 3. ثم يأتي صف ABC بالقيم 3 ثم 2 ثم 2 ثم 1 ثم 2، وأخيرًا صف ABCD بالقيم 4 ثم 3 ثم 3 ثم 2 ثم 2. تحدد كل خانة زوجًا من البادئات، لا تكلفة تحرير حرف واحد منفرد في معزل عن السابق.

عند AB إلى AX تكفي مطابقة A ثم استبدال B، فتكون الخانة واحدًا. وعند ABC إلى AXC تبقى الكلفة واحدًا لأن C متساوية في الطرفين. وعند ABCD إلى AXCE نضيف استبدال D إلى E على هذا القطر، فتكون المسافة اثنين. هذه حالات مختارة يمكن مراجعتها يدويًا بجانب بقية المصفوفة المرسومة.

ولا نستنتج أن كل صف أو عمود يزيد خطوة واحدة دائمًا عند الانتقال فيه. توافق حروف أو اختلاف أفضل طريق قد يجعل تكاليف الخانات المجاورة متساوية أو مختلفة. ما يضبط الرقم هو تعريف البادئتين والعلاقة التي حسبناها، لا نمط بصري نتوقعه من جدول يكثر فيه الصفر أو العدد واحد.

الرجوع إلى أصل الجدول

لاستعادة شاهد، نبدأ من الخانة النهائية عند أربعة وأربعة ونبحث عن انتقال يحقق قيمتها. في مثالنا نرجع قطريًا مع استبدال D بـE، ثم نرجع قطريًا مع إبقاء C، ثم استبدال B بـX، ثم إبقاء A. وصلنا إلى بادئتين فارغتين، لكن الخطوات سجلت من النهاية إلى البداية في هذا الرجوع.

نعكس ترتيب السجل ليصبح صالحًا للقراءة من أول المصدر: keep على A، ثم replace من B إلى X، ثم keep على C، ثم replace من D إلى E. الكلفة المجمعة واحد وواحد للتعديلين، وصفر للقراءتين المطابقتين. لا نخلط ترتيب الرجوع الداخلي بترتيب تنفيذ الشاهد؛ تطبيق سجل معكوس من نهاية النص يحتاج عقد مواضع مختلفًا لم نعطه هنا.

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

خطوات take وput على المصدر الأصلي

نقرأ الشاهد من بدايته مع مؤشر في المصدر الأصلي ومخرج جديد فارغ. كل take غير فارغ يجب أن يوافق الجزء الذي سنستهلكه الآن من المصدر، وكل put يضاف إلى المخرج. في مثالنا نستهلك A وننتج A، ثم نستهلك B وننتج X، ثم نستهلك C وننتج C، ثم نستهلك D وننتج E. صار المخرج AXCE واستهلكنا المصدر كله.

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

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

عرض الرسم بالحجم الكامل

الإدراج والحذف في مثالين منفصلين

لتحويل ABC إلى AXBC، نقرأ A ونبقيها، ثم نضيف X دون استهلاك حرف من المصدر، ثم نبقي B وC. خطوة insert تحمل take فارغًا وput بقيمة X، ولذلك تزيد طول المخرج ولا تتقدم بالمؤشر في المصدر عند هذه الخطوة. كلفتها واحد، بينما قراءات A وB وC المطابقة كلفتها صفر.

ولتحويل ABC إلى AC، نبقي A ثم نحذف B ثم نبقي C. خطوة delete تستهلك B وتحمل put فارغًا، فتتقدم قراءة المصدر دون إضافة حرف إلى المخرج. النتيجة أقصر بحرف واحد وكلفتها واحد. المثالان يوضحان فرق استهلاك المصدر من إنتاج الهدف، وهو ما قد يختلط إذا سمينا كل الخطوات تغييرًا دون تعريف حقولها.

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

التعادل يعطي شاهدًا واحدًا

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

في المثال AA إلى A، يمكن إبقاء الحرف الأول وحذف الثاني، أو حذف الأول وإبقاء الثاني. الكلفة واحد في الاثنين. سياسة الرجوع في دالتنا تفضل إبقاء آخر A عند الخانة النهائية، ثم تحذف الأولى، فتعيد delete ثم keep بعد عكس سجل الرجوع. تطابق الحرفين في الشكل لا يلغي اختلاف ظهورين داخل المصدر الذي نقرأه.

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

الكود الأصلي والتحقق بإعادة التشغيل

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

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

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

def edit_witness(source, target):
    if not isinstance(source, str) or not isinstance(target, str):
        raise TypeError("two text inputs required")
    n, m = len(source), len(target)
    table = [list(range(m + 1))]
    table.extend([[i] + [0] * m for i in range(1, n + 1)])
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = int(source[i - 1] != target[j - 1])
            table[i][j] = min(
                table[i - 1][j] + 1,
                table[i][j - 1] + 1,
                table[i - 1][j - 1] + cost,
            )
    steps = []
    i, j = n, m
    while i or j:
        if i and j:
            cost = int(source[i - 1] != target[j - 1])
            if table[i][j] == table[i - 1][j - 1] + cost:
                steps.append({"op": "replace" if cost else "keep",
                              "take": source[i - 1], "put": target[j - 1]})
                i -= 1
                j -= 1
                continue
        if i and table[i][j] == table[i - 1][j] + 1:
            steps.append({"op": "delete", "take": source[i - 1], "put": ""})
            i -= 1
        else:
            steps.append({"op": "insert", "take": "", "put": target[j - 1]})
            j -= 1
    steps.reverse()
    return {"distance": table[n][m], "steps": tuple(steps),
            "table": tuple(tuple(row) for row in table)}

الفارغ والمطابق وأنواع المدخل

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

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

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

مرجع رسم حالات تحرير مستقل

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

نفذنا فحصًا محدودًا على جميع أزواج النصوص من A وB بأطوال من صفر إلى ثلاثة ضمن رسم الحالات المعلن. نقارن المسافة ونراجع كل شاهد بإعادة تشغيله، ونعد غير keep للتأكد من تطابق كلفته. هذه تجربة صغيرة منتهية، وليست دليلًا أن حدود رسم نصوص صغير تكفي لكل طول أو لكل حرف أو عملية جديدة.

ونضيف المصدر ABCD والهدف AXCE، ومثالي الإدراج والحذف، والتعادل، والمطابق، والمدخلات المرفوضة. نحتفظ بنتائج الفحوص وبالنصين لكل مثال حتى يمكن إعادة المخرج. لا نحول العدد نفسه إلى ثقة في صحة النص أو قدرة على تفسير عربية أو نجاح خدمة بحث لم نستدعها؛ تحققنا من عقد تحرير حرفي محلي.

بطاقة النتيجة والعقد والكلفة

يمكن أن تصف بطاقة الأصل المصدر ABCD والهدف AXCE، والعمليات الثلاث بكلفة واحدة، والإبقاء صفرًا، والمسافة اثنين. نضيف الجدول خمسة في خمسة والشاهد keep A ثم replace B إلى X ثم keep C ثم replace D إلى E. ونكتب أن الحقول تصف استهلاك المصدر وإنتاج الهدف، وأن التعادل يحفظ طريقًا واحدًا.

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

قبل اعتماد سجل تحرير، راجع معنى الخانة والعمليات والتكاليف ووحدة النص، ثم أعد تشغيل الشاهد على المصدر. افصل بين صحة المخرج وكلفة الشاهد وحدها وأمثليتها، واحفظ ما يثبت كل سؤال. ستعرف بذلك ما أنجزناه: جدول ومسار تحويل قابلان للتحقق في العقد المعلن، دون ادعاء تفسير لغوي أو تعديل مقصود لم ندخل معناه في الحساب.