الگوریتم واگنر–فیشر کیست؟ توضیح بده.
در علوم رایانه، الگوریتم واگنر-فیشر یک الگوریتم برنامه‌نویسی پویا می‌باشد، بدین معنا که در فرایند انجام محاسبه این فاصله، رشته‌ها به بخش‌های مختلف تقسیم شده و تغییرات به همراه وزن منحصربه‌فرد آن‌ها در آن بخش محاسبه می‌شود. این الگوریتم همانند روش «لونشتاین» دارای تغییرات درج حرف اضافه، حذف حرف اضافه و جایگزینی حرف می‌باشد؛ با این تفاوت که از لحاظ زمانی بهینه شده و برای تشخیص هر تغییر در رشته، هزینه‌های خاصی در نظر گرفته می‌شود و سپس، بهینه‌ترین مسیر برای دستیابی به جواب نهایی انتخاب می‌گردد. در موتورهای جستجو، پردازش کلمات و چک کننده‌های تلفظ از این الگوریتم استفاده می‌شود. این الگوریتم یکی از ساده‌ترین الگوریتم‌های خانواده ماشین الگوریتم حالت می‌باشد.تاریخچه.الگوریتم واگنر-فیشر دارای سابقه چندین اختراع است. لیستی از مخترعین این الگوریتم در زیر آمده‌است. البته این لیست کامل نمی‌باشد.الگوریتم.الگوریتم واگنر-فیشر فاصله ویرایشی را براساس اتخاذ یک ماتریس برای نگه‌داشتن فاصله‌های ویرایشی بین تمام پیشوندهای رشته اول و تمام پیشوندهای رشته دوم، محاسبه می‌کند؛ آنگاه مقادیر موجود در ماتریس را با پرکردن ماتریس محاسبه می‌کند، و در نتیجه فاصله بین دو رشته کامل را به عنوان مقدار نهایی به عنوان خروجی بازمی‌گرداند.یک پیاده‌سازی ساده، به عنوان شبه‌کد برای تابع "LevenshteinDistance" که دو رشته را به عنوان ورودی می‌گیرد "(s به طول m و t به طول n)" و فاصله لوناشتاین (فاصله ویرایشی) بین آنها را محاسبه می‌کند، به صورت زیر است. توجه داشته‌باشید که رشته‌های ورودی تک اندیسی هستند، در حالی که ماتریس "d" دارای نمایه صفر است و codice_1 یک بازه بسته می‌باشد. function LevenshteinDistance(char s[1..m], char t[1..n]): // for all i and j, d[i,j] will hold the Levenshtein distance between // the first i characters of s and the first j characters of t // note that d has (m+1)*(n+1) values declare int d[0..m, 0..n] set each element in d to zero // source prefixes can be transformed into empty string by // dropping all characters for i from 1 to m: d[i, 0] := i // target prefixes can be reached from empty source prefix // by inserting every character for j from 1 to n: d[0, j] := j for j from 1 to n: for i from 1 to m: if s[i] = t[j]: substitutionCost := 0 else: substitutionCost := 1 d[i, j] := minimum(d[i-1, j] + 1, // deletion d[i, j-1] + 1, // insertion d[i-1, j-1] + substitutionCost) // substitution return d[m, n]فضای ناوردا در این الگوریتم این است که ما می‌توانیم بخش اولیه formula_1 را با استفاده از حداقل formula_2 عملیات formula_3 تغییر دهیم. در پایان، عنصر پایین-راست آرایه شامل پاسخ است.پیاده‌سازی با پایتون.def wagner_fischer_O1(s, t): n = len(s) m = len(t) buf = list(range(m + 1)) for i in range(1, n + 1): tmp = buf[0] buf[0] = i for j in range(1, m + 1): if s[i - 1] == t[j - 1]: tmp, buf[j] = buf[j], tmp else: tmp, buf[j] = buf[j], min(buf[j], buf[j - 1], tmp) + 1 return buf[m]اثبات درستی.همان‌طور که قبلاً نیز اشاره شد، ناوردا (نامتغیر) این است که ما می‌توانیم با استفاده از حداقل formula_2 عملیات، بخش اولیه formula_1 به formula_3 تبدیل کنیم.این مورد در ابتدا در سطر و ستون ۰ درست است زیرا formula_7 با انداختن تمام حروف i می‌تواند به یک رشته خالی formula_8 تبدیل شود. به‌طور مشابه، ما می‌توانیم formula_9 را به سادگی با اضافه کردن تمام حروف j، به formula_3 تغییر دهیم.اگر formula_11، آن‌گاه ما می‌توانیم formula_12 را به formula_13 در k عملیات تغییر دهیم، آنگاه می‌توانیم همین کار روی formula_7 را انجام دهیم و فقط آخرین کاراکتر را رها کنیم، و k عملیات را انجام دهیم.در غیر این‌صورت، فاصله، حداقلِ سه‌راه ممکن برای انجام این تغییر است:اگر بتوانیم formula_1 را به formula_13 در k عملیات تبدیل کنیم، آن‌گاه به سادگی می‌توانیم formula_17 را برای بدست‌آوردن formula_3 در k + ۱ عملیات اضافه کنیم (درج).اگر بتوانیم formula_1 را به formula_13 در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم formula_21 را حذف کنیم و سپس همان انتقال را با k + 1 عملیات انجام دهیم (حذف).اگر بتوانیم formula_22 را به formula_13 در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم همان کار را روی formula_1 انجام دهیم و با k + 1 عملیات جای formula_21 را با formula_17 عوض کنیم (جانشینی).عملیات‌های مورد نیاز برای تبدیل formula_1 به formula_3 عددی است که برای تبدیل همه sها به همه tها مورد نیاز است، و بنابراین formula_29 نتیجه نهایی ما می‌باشد.این اثبات نمی‌تواند معتبر باشد چرا که تعداد قرار داده‌شده در formula_2 در واقع کمینه است؛ این کار برای نشان‌دادن دشوارتر است، و شامل یک مشاجره با تناقضی است که در آن فرض می‌کنیم formula_2 کوچک‌تر از حداقل سه است، و استفاده از این برای نشان‌دادن یکی از این سه مقدار، مقدار حداقل نیست.مثال‌هایی از الگوریتم واگنر-فیشر.محاسبه فاصله بین دو رشته MUSE و MUSIC. جواب نهایی در خانه آخر ماتریس (سطر ۷ ام و ستون ۶ ام) قرار دارد.محاسبه فاصله بین دو رشته carnivore و herbivore.یافتن فاصله بین دو رشته Saturday و Sunday.یافتن فاصله بین دو رشته kitten و sitting.اصلاحات ممکن.تغییرات احتمالی در این الگوریتم شامل موارد زیر است:رابطه الگوریتم واگنر-فیشر و برنامه‌سازی پویا.برنامه‌نویسی پویا یک روش برنامه‌نویسی است که عمدتاً در برنامه‌نویسی رقابتی استفاده می‌شود. یکی از ساده‌ترین ترفندهای این متدولوژی، ذخیره‌سازی(Memorization) می‌باشد. ذخیره‌سازی(Memorization) یعنی مقادیری که در هر مرحله بدست می‌آوریم را در داخل یک آرایه ذخیره کرده و درصورت نیاز به چنین مقادیری، دوباره محاسبات مربوط به آن را انجام ندهیم. در این‌صورت سرعت برنامه افزایش می‌یابد. در الگوریتم واگنر-فیشر نیز از این روش استفاده می‌شود تا سرعت برنامه افزایش یابد. می‌توان گفت تفاوت روش واگنر-فیشر و لونشتاین، استفاده از برنامه‌نویسی پویا در الگوریتم واگنر-فیشر می‌باشد.متغیر سِلِرز برای جستجوی رشته.با مقداردهی اولیه ردیف اول ماتریس با صفر، ما یک متغیر از الگوریتم واگنر-فیشر را بدست می‌آوریم که می‌تواند برای جستجوی رشته‌ای فازی در یک رشته در یک متن استفاده شود. این تغییر، موقعیت نهایی انطباق متن را ایجاد می‌کند. برای تعیین موقعیت شروع رشته متناظر، تعداد درج و حذف‌ها را می‌توان به‌طور جداگانه ذخیره کرد و برای محاسبه موقعیت شروع از وضعیت نهایی استفاده کرد.الگوریتم حاصل‌شده به هیچ وجه مؤثر نیست، اما در زمان انتشار آن(۱۹۸۰) یکی از اولین الگوریتم‌هایی بود که جستجوی تقریبی را انجام می‌داد.