الخلايا المملوءة
مسافة التحرير
الحروف المُبقاة

  • قيد الملء
  • يُقرأ منها
  • الإجابة

مزيد عن مسافة التحرير

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

كم تغييرًا لحرف واحد يحوّل kitten إلى sitting؟ ثلاثة: استبدل k بـ s، واستبدل e بـ i، وأضف g. هذا العدد هو مسافة التحرير، وبه ترتّب المدققات الإملائية اقتراحاتها ويقارن علماء الأحياء الجينات. اكتب كلمتين وشاهد جدولًا يجده. اضغط «تشغيل» لمشاهدة الجدول وهو يمتلئ، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. اكتب كلمتين: الأولى تمتد نزولًا على جانب الجدول، والثانية على امتداد أعلاه. تحمل كل خلية أقل عدد من التعديلات يحوّل الحروف حتى صفها إلى الحروف حتى عمودها. وفي النهاية تُقرأ التعديلات رجوعًا من الخلية السفلية اليمنى. يختار «مثال جديد» زوجًا آخر من الكلمات. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

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

كيف يعمل الجدول

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

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

الخلية السفلية اليمنى هي مسافة التحرير. يبدأ التطبيق منها، فيجد الجار الذي جاءت منه قيمة الخلية وينتقل إليه: قطريًا للحرف المُبقى أو المستبدل، وإلى الأعلى للحرف المحذوف، وإلى اليسار للحرف المُدرج. وعند القراءة من أعلى اليسار، تكوّن هذه الخطوات أقصر قائمة تعديلات، وتظهر أسفل الجدول: الحرف العادي مُبقى، و k→s استبدال، و −e حذف، و +g إدراج.

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

ما مسافة ليفنشتاين؟

اسم آخر لمسافة التحرير هذه: أقل عدد من عمليات إدراج حرف واحد وحذفه واستبداله يحوّل سلسلة نصية إلى أخرى. وقد سُمّيت باسم فلاديمير ليفنشتاين الذي وصفها عام 1965.

ما مسافة التحرير بين kitten وsitting؟

3: استبدل k بـ s، واستبدل e بـ i، وأدرج g في النهاية. ويبيّن الجدول أنه لا توجد قائمة تعديلات أقصر.

ما سرعة خوارزمية مسافة التحرير؟

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

ما مسافات التحرير الأخرى؟

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

هل يُرسَل أي شيء إلى أي مكان؟

لا. يُحسب كل شيء في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

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

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

الانتقال إلى المحرر