مسافة التحرير (مسافة ليفنشتاين)

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

جدول فيه كلمة تمتد نزولًا على جانبه وأخرى على امتداد أعلاه، وأرقام في خلاياه، ومسار برتقالي من التعديلات من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى
جدول فيه كلمة تمتد نزولًا على جانبه وأخرى على امتداد أعلاه، وأرقام في خلاياه، ومسار برتقالي من التعديلات من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى

المسألة

يغيّر التعديل الكلمة بحرف واحد: إدراج حرف، أو حذف حرف، أو استبدال حرف بآخر. ومسافة التحرير بين كلمتين هي أقل عدد من التعديلات يحوّل إحداهما إلى الأخرى. المسافة بين cat و cut هي 1، وبين cat و cast هي 1، وبين cat و act هي 2. وتُسمّى أيضًا مسافة ليفنشتاين، نسبةً إلى عالم الرياضيات السوفيتي فلاديمير ليفنشتاين الذي درسها عام 1965.

الجدول

لتكن d[i][j] مسافة التحرير بين أول i حروف من كلمة وأول j حروف من الأخرى. تحويل كلمة إلى لا شيء يتطلب حذفًا واحدًا لكل حرف، لذا d[i][0] = i، وبناء كلمة من لا شيء يتطلب إدراجًا واحدًا لكل حرف، لذا d[0][j] = j. إذا كان الحرف i يساوي الحرف j، فإن d[i][j] = d[i − 1][j − 1]. وإلا فإن d[i][j] = 1 + أصغر القيم d[i − 1][j − 1] (استبدال) و d[i − 1][j] (حذف) و d[i][j − 1] (إدراج).

مثال

لكلمتي kitten و sitting يضم الجدول 7 صفوف و8 أعمدة. الخلية السفلية اليمنى تساوي 3، والقراءة رجوعًا منها تعطي: استبدل k بـ s، وأبقِ i و t و t، واستبدل e بـ i، وأبقِ n، وأدرج g. Kitten، sitten، sittin، sitting: ثلاثة تعديلات، والجدول يثبت أنه لا توجد قائمة أقصر.

قراءة التعديلات رجوعًا

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

التاريخ والاستخدامات

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

استكشفها بنفسك

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

الأسئلة المتداولة

هل مسافة التحرير مقياس مسافة (متري)؟

نعم. فهي لا تكون سالبة أبدًا، ولا تساوي 0 إلا للكلمات المتساوية، وهي نفسها في الاتجاهين، والمرور بكلمة ثالثة لا يجعلها أقصر أبدًا: d(a, c) ≤ d(a, b) + d(b, c). وهذا يجعلها مفيدة في البحث عن التطابقات القريبة.

ما مسافة داميراو–ليفنشتاين؟

هي مسافة التحرير مع تعديل إضافي واحد: تبديل حرفين متجاورين. وجد فريدريك داميراو عام 1964 أن الإدراج والحذف والاستبدال والتبديل معًا تغطي أكثر من 80٪ من الأخطاء الإملائية. ومع التبديل تكون المسافة بين recieve و receive هي 1 بدلًا من 2.

هل يمكن حساب مسافة التحرير أسرع من O(m·n)؟

ليس بكثير. ففي عام 2015 بيّن أرتورس باكورس وبيوتر إنديك أن أي طريقة تستغرق زمنًا O(n^(2 − ε)) لقيمة ما ε > 0 ستنقض فرضية الزمن الأسي القوية، التي يؤمن بها معظم الباحثين. لكن للكلمات المتقاربة يكفي شريط ضيق حول قطر الجدول.

كيف تُستخدم مسافة التحرير في مقارنة الحمض النووي؟

يستخدم علماء الأحياء الجدول نفسه بدرجات بدلًا من الأعداد: التطابقات تكسب نقاطًا، والاستبدالات والفجوات تكلّف نقاطًا تعتمد على الحروف. هذه هي خوارزمية نيدلمان–وونش لعام 1970 للتسلسلات الكاملة، وخوارزمية سميث–ووترمان لعام 1981 لأفضل الأجزاء تطابقًا.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب مسافة التحرير