خوارزمية فاغنر-فيشر

في علوم الحاسوب ، تعتبر خوارزمية Wagner-Fischer خوارزمية برمجة ديناميكية تحسب مسافة التحرير بين سلسلتين من الأحرف.

تاريخ

لخوارزمية فاغنر-فيشر تاريخ من الاختراعات المتعددة . يسرد نافارو المخترعين التاليين لها، مع تاريخ النشر، ويقر بأن القائمة غير مكتملة: ^{[ 1 ]}^{: 43}

فينتسيوك ، 1968
نيدلمان وونش ، 1970
سانكوف ، 1972
سيلرز، 1974
فاغنر وفيشر ، 1974
لورانس وواغنر، 1975

حساب المسافة

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

يُمكن تطبيق دالة Distance ، التي تأخذ سلسلتين نصيتين، s بطول m و t بطول n ، وتعيد مسافة ليفنشتاين بينهما، بشكل مباشر باستخدام الشفرة الزائفة التالية. تكون السلاسل النصية المدخلة مُفهرسة من 1، بينما تكون المصفوفة d مُفهرسة من 0، [i..k]وهي نطاق مغلق.

دالة المسافة ( char s [ 1..m ] , char t [ 1..n ] ) : // لكل i و j ، سيحتوي d [ i , j ] على المسافة بين // أول i حرف من s وأول j حرف من t // لاحظ أن d له قيم ( m + 1 ) * ( n + 1 ) ...d [ i , j ] := minimum ( d [ i - 1 , j ] + 1 , // حذف d [ i , j - 1 ] + 1 , // إضافة d [ i - 1 , j - 1 ] + substitutionCost ) // استبدال return d [ m , n ]

مثالان على المصفوفة الناتجة (يؤدي تحريك المؤشر فوق رقم مسطر إلى إظهار العملية التي تم إجراؤها للحصول على هذا الرقم):

		ك	أنا	ت	ت	هـ	ن
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
أنا	2	2	1	2	3	4	5
ت	3	3	2	1	2	3	4
ت	4	4	3	2	1	2	3
أنا	5	5	4	3	2	2	3
ن	6	6	5	4	3	3	2
ز	7	7	6	5	4	4	3

		S	أ	ت	u	ر	د	أ	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
ن	3	2	2	2	3	3	4	5	6
د	4	3	3	3	3	4	3	4	5
أ	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

الثابت الذي يُحافظ عليه طوال الخوارزمية هو أنه يمكننا تحويل الجزء الأولي s[1..i]باستخدام t[1..j]أقل عدد ممكن من d[i,j]العمليات. في النهاية، يحتوي العنصر السفلي الأيمن من المصفوفة على الإجابة.

إثبات صحة النتائج

كما ذكرنا سابقاً، فإن الثابت هو أنه يمكننا تحويل الجزء الأولي s[1..i]إلى t[1..j]باستخدام أقل عدد ممكن من d[i,j]العمليات. ويتحقق هذا الثابت للأسباب التالية:

يكون هذا صحيحًا مبدئيًا في الصف والعمود 0 لأنه s[1..i]يمكن تحويله إلى سلسلة فارغة t[1..0]ببساطة عن طريق حذف جميع iالأحرف. وبالمثل، يمكننا تحويله s[1..0]إلى سلسلة فارغة t[1..j]ببساطة عن طريق إضافة جميع jالأحرف.
إذا كان s[i] = t[j]بإمكاننا تحويل ، ويمكننا تحويل s[1..i-1]إلى t[1..j-1]في kالعمليات ، فيمكننا فعل الشيء نفسه إلى s[1..i]وترك الحرف الأخير كما هو، مما يعطي kالعمليات.
وإلا، فإن المسافة هي الحد الأدنى من بين الطرق الثلاث الممكنة لإجراء التحويل:
- إذا استطعنا التحويل s[1..i]إلى t[1..j-1]في kالعمليات، فيمكننا ببساطة الإضافة t[j]بعد ذلك للحصول على t[1..j]في k+1العمليات (الإدراج).
- إذا استطعنا التحويل s[1..i-1]إلى t[1..j]عمليات k، فيمكننا إزالة s[i]ثم القيام بنفس التحويل، ليصبح المجموع الكلي k+1للعمليات (الحذف).
- إذا استطعنا التحويل s[1..i-1]إلى t[1..j-1]في kعمليات، فيمكننا أن نفعل الشيء نفسه إلى s[1..i]، ونستبدل الأصل s[i]بـ t[j]بعد ذلك، ليصبح المجموع الكلي من k+1العمليات (الاستبدال).
العمليات المطلوبة للتحويل s[1..n]إلى t[1..m]هي بالطبع العدد المطلوب لتحويل كل sإلى كل t، وبالتالي d[n,m]فإن نتيجتنا صحيحة.

يفشل هذا البرهان في إثبات أن العدد الموضوع d[i,j]هو في الواقع أصغر عدد ممكن؛ وهذا أكثر صعوبة في إثباته، ويتضمن حجة بالتناقض حيث نفترض d[i,j]أن أصغر من الحد الأدنى للثلاثة، ونستخدم هذا لإظهار أن أحد الثلاثة ليس أصغر عدد ممكن.

التعديلات المحتملة

تشمل التعديلات المحتملة على هذه الخوارزمية ما يلي:

يمكننا تكييف الخوارزمية لاستخدام مساحة أقل، O ( m ) بدلاً من O ( mn )، لأنها تتطلب فقط تخزين العمود السابق والعمود الحالي في أي وقت.
يمكننا تخزين عدد عمليات الإدخال والحذف والاستبدال بشكل منفصل، أو حتى المواضع التي تحدث فيها، وهو أمر ثابت دائمًا j.
يمكننا تطبيع المسافة إلى الفترة [0,1].
إذا كنا مهتمين فقط بالمسافة إذا كانت أصغر من عتبة $k$ ، فإنه يكفي حساب شريط قطري بعرض ⁠ $2k+1$ في المصفوفة. وبهذه الطريقة، يمكن تشغيل الخوارزمية في $زمن قدره O (kl)$ ، حيث $l$ هو طول أقصر سلسلة.^{[ 2 ]}
يمكننا فرض غرامات مختلفة على عمليات الإضافة والحذف والاستبدال. كما يمكننا فرض غرامات تعتمد على الأحرف التي يتم إضافتها أو حذفها أو استبدالها.
لا يُطبَّق هذا الخوارزمية بالتوازي بشكل جيد، نظرًا لكثرة التبعيات بين البيانات . مع ذلك، يمكن حساب جميع costالقيم بالتوازي، ويمكن تعديل الخوارزمية لتنفيذ minimumالوظيفة على مراحل للتخلص من هذه التبعيات.
من خلال فحص الأقطار بدلاً من الصفوف، وباستخدام التقييم الكسول ، يمكننا إيجاد مسافة ليفنشتاين في زمن قدره O ( m (1 + d )) (حيث d هي مسافة ليفنشتاين)، وهو أسرع بكثير من خوارزمية البرمجة الديناميكية العادية إذا كانت المسافة صغيرة. ^{[ 3 ]}

صيغة البائع للبحث عن السلاسل النصية

بتهيئة الصف الأول من المصفوفة بالأصفار، نحصل على صيغة معدلة من خوارزمية فاغنر-فيشر، والتي يمكن استخدامها للبحث التقريبي عن سلسلة نصية ضمن نص. ^{[ 1 ]} يُحدد هذا التعديل موضع نهاية السلاسل الفرعية المطابقة في النص. ولتحديد موضع بداية هذه السلاسل، يمكن تخزين عدد عمليات الإضافة والحذف بشكل منفصل، واستخدامه لحساب موضع البداية انطلاقًا من موضع النهاية. ^{[ 4 ]}

إن الخوارزمية الناتجة ليست فعالة بأي حال من الأحوال، ولكنها كانت في وقت نشرها (1980) واحدة من أوائل الخوارزميات التي أجرت بحثًا تقريبيًا. ^{[ 1 ]}

مراجع

1 2 3 نافارو، غونزالو (2001). "جولة إرشادية لتقريب مطابقة السلاسل" (ملف PDF) . مجلة ACM Computing Surveys . 33 (1): 31-88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .
↑ غوسفيلد، دان (1997). خوارزميات على السلاسل والأشجار والمتتاليات: علوم الحاسوب وعلم الأحياء الحاسوبي . كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج. ISBN 978-0-521-58519-4.
↑ أليسون ل (سبتمبر 1992). "البرمجة الديناميكية الكسولة يمكن أن تكون متلهفة" . رسائل معالجة المعلومات . 43 (4): 207-12 . doi : 10.1016/0020-0190(92)90202-7 .
↑ برونو وولتزنلوغل باليو. معجم تقريبي لـ GATE قائم على مسافة ليفنشتاين. مؤرشف في 8 مايو 2013 على موقع Wayback Machine . قسم الطلاب في المدرسة الصيفية الأوروبية في المنطق واللغة والمعلومات ( ESSLLI )، 2007.

[navarro-1] 1 2 3 نافارو، غونزالو (2001). "جولة إرشادية لتقريب مطابقة السلاسل" (ملف PDF) . مجلة ACM Computing Surveys . 33 (1): 31-88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .

[2] غوسفيلد، دان (1997). خوارزميات على السلاسل والأشجار والمتتاليات: علوم الحاسوب وعلم الأحياء الحاسوبي . كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج. ISBN 978-0-521-58519-4.

[3] أليسون ل (سبتمبر 1992). "البرمجة الديناميكية الكسولة يمكن أن تكون متلهفة" . رسائل معالجة المعلومات . 43 (4): 207-12 . doi : 10.1016/0020-0190(92)90202-7 .

[4] برونو وولتزنلوغل باليو. معجم تقريبي لـ GATE قائم على مسافة ليفنشتاين. مؤرشف في 8 مايو 2013 على موقع Wayback Machine . قسم الطلاب في المدرسة الصيفية الأوروبية في المنطق واللغة والمعلومات ( ESSLLI )، 2007.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]