موضوع مقاله: الگوریتم واگنر–فیشر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم واگنر–فیشر | مقدمه: در علوم رایانه، الگوریتم واگنر-فیشر یک الگوریتم برنامه‌نویسی پویا می‌باشد، بدین معنا که در فرایند انجام محاسبه این فاصله، رشته‌ها به بخش‌های مختلف تقسیم شده و تغییرات به همراه وزن منحصربه‌فرد آن‌ها در آن بخش محاسبه می‌شود. | ## بخش 1: الگوریتم واگنر–فیشر | این الگوریتم همانند روش «لونشتاین» دارای تغییرات درج حرف اضافه، حذف حرف اضافه و جایگزینی حرف می‌باشد؛ با این تفاوت که از لحاظ زمانی بهینه شده و برای تشخیص هر تغییر در رشته، هزینه‌های خاصی در نظر گرفته می‌شود و سپس، بهینه‌ترین مسیر برای دستیابی به جواب نهایی انتخاب می‌گردد. در موتورهای جستجو، پردازش کلمات و چک کننده‌های تلفظ از این الگوریتم استفاده می‌شود. وینتسیوک، ۱۹۶۸ نیدلمن و وانچ، ۱۹۷۰ سنکوف، ۱۹۷۲ سِلِرز، ۱۹۷۴ واگنر و فیشر، ۱۹۷۴ لورنس و واگنر، ۱۹۷۵ الگوریتم الگوریتم واگنر-فیشر فاصله ویرایشی را براساس اتخاذ یک ماتریس برای نگه‌داشتن فاصله‌های ویرایشی بین تمام پیشوندهای رشته اول و تمام پیشوندهای رشته دوم، محاسبه می‌کند؛ آنگاه مقادیر موجود در ماتریس را با پرکردن ماتریس محاسبه می‌کند، و در نتیجه فاصله بین دو رشته کامل را به عنوان مقدار نهایی به عنوان خروجی بازمی‌گرداند. توجه داشته‌باشید که رشته‌های ورودی تک اندیسی هستند، در حالی که ماتریس d دارای نمایه صفر است و [i..k] یک بازه بسته می‌باشد. این مورد در ابتدا در سطر و ستون ۰ درست است زیرا با انداختن تمام حروف i می‌تواند به یک رشته خالی تبدیل شود. به‌طور مشابه، ما می‌توانیم را به سادگی با اضافه کردن تمام حروف j، به تغییر دهیم. اگر ، آن‌گاه ما می‌توانیم را به در k عملیات تغییر دهیم، آنگاه می‌توانیم همین کار روی را انجام دهیم و فقط آخرین کاراکتر را رها کنیم، و k عملیات را انجام دهیم. در غیر این‌صورت، فاصله، حداقلِ سه‌راه ممکن برای انجام این تغییر است: اگر بتوانیم را به در k عملیات تبدیل کنیم، آن‌گاه به سادگی می‌توانیم را برای بدست‌آوردن در k + ۱ عملیات اضافه کنیم (درج). اگر بتوانیم را به در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم را حذف کنیم و سپس همان انتقال را با k + 1 عملیات انجام دهیم (حذف). | ## بخش 2: الگوریتم واگنر–فیشر | اگر بتوانیم را به در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم همان کار را روی انجام دهیم و با k + 1 عملیات جای را با عوض کنیم (جانشینی). عملیات‌های مورد نیاز برای تبدیل به عددی است که برای تبدیل همه sها به همه tها مورد نیاز است، و بنابراین نتیجه نهایی ما می‌باشد. این اثبات نمی‌تواند معتبر باشد چرا که تعداد قرار داده‌شده در در واقع کمینه است؛ این کار برای نشان‌دادن دشوارتر است، و شامل یک مشاجره با تناقضی است که در آن فرض می‌کنیم کوچک‌تر از حداقل سه است، و استفاده از این برای نشان‌دادن یکی از این سه مقدار، مقدار حداقل نیست. اصلاحات ممکن تغییرات احتمالی در این الگوریتم شامل موارد زیر است: ما می‌توانیم الگوریتم را با استفاده از فضای کم‌تر، به جای تطبیق دهیم، زیرا تنها لازم است ردیف قبلی و ردیف فعلی در هر زمان ذخیره شوند. ما می‌توانیم تعداد درج، حذف و جانشینی‌ها را به‌طور جداگانه ذخیره کنیم، یا حتی موقعیت‌هایی که در آن رخ می‌دهند، که همیشه j است. اگر ما تنها به فاصله علاقه‌مند باشیم و آن کوچک‌تر از یک آستانه k باشد، آن‌گاه برای محاسبه یک نوار مورب در عرض در ماتریس کفایت می‌کند. در این روش، الگوریتم می‌تواند در زمان اجرا شود، که در آن l طول کوتاه‌ترین طول رشته‌است. ما همچنین می‌توانیم هزینه‌های جریمه را که به آن کاراکترهایی که درج، حذف یا جانشین شده‌اند، ارائه نماییم. با این‌حال، تمام مقادیر هزینه را می‌توان به صورت موازی محاسبه کرد، و الگوریتم را می‌توان برای اجرای حداقل عملکرد در فازها برای حذف وابستگی‌ها بکار برد. | ## بخش 3: الگوریتم واگنر–فیشر | با بررسی قسمت‌های مورب به جای ردیف، و با استفاده از ارزیابی تنبل، می‌توانیم فاصله Levenshtein را در زمان پیدا کنیم که بسیار سریع‌تر از الگوریتم برنامه‌نویسی پویا است، اگر فاصله کوچک باشد. رابطه الگوریتم واگنر-فیشر و برنامه‌سازی پویا برنامه‌نویسی پویا یک روش برنامه‌نویسی است که عمدتاً در برنامه‌نویسی رقابتی استفاده می‌شود. ذخیره‌سازی(Memorization) یعنی مقادیری که در هر مرحله بدست می‌آوریم را در داخل یک آرایه ذخیره کرده و درصورت نیاز به چنین مقادیری، دوباره محاسبات مربوط به آن را انجام ندهیم. در الگوریتم واگنر-فیشر نیز از این روش استفاده می‌شود تا سرعت برنامه افزایش یابد. می‌توان گفت تفاوت روش واگنر-فیشر و لونشتاین، استفاده از برنامه‌نویسی پویا در الگوریتم واگنر-فیشر می‌باشد. متغیر سِلِرز برای جستجوی رشته با مقداردهی اولیه ردیف اول ماتریس با صفر، ما یک متغیر از الگوریتم واگنر-فیشر را بدست می‌آوریم که می‌تواند برای جستجوی رشته‌ای فازی در یک رشته در یک متن استفاده شود. برای تعیین موقعیت شروع رشته متناظر، تعداد درج و حذف‌ها را می‌توان به‌طور جداگانه ذخیره کرد و برای محاسبه موقعیت شروع از وضعیت نهایی استفاده کرد. | ## جمع‌بندی | الگوریتم حاصل‌شده به هیچ وجه مؤثر نیست، اما در زمان انتشار آن(۱۹۸۰) یکی از اولین الگوریتم‌هایی بود که جستجوی تقریبی را انجام می‌داد.