الگوریتم واگنر–فیشر

الگوریتم واگنر-فیشر دارای سابقه چندین اختراع است. لیستی از مخترعین این الگوریتم در زیر آمده‌است. البته این لیست کامل نمی‌باشد.

• وینتسیوک، ۱۹۶۸
• نیدلمن و وانچ، ۱۹۷۰
• سنکوف، ۱۹۷۲
• سِلِرز، ۱۹۷۴
• واگنر و فیشر، ۱۹۷۴
• لورنس و واگنر، ۱۹۷۵

الگوریتم واگنر-فیشر فاصله ویرایشی را براساس اتخاذ یک ماتریس برای نگه‌داشتن فاصله‌های ویرایشی بین تمام پیشوندهای رشته اول و تمام پیشوندهای رشته دوم، محاسبه می‌کند؛ آنگاه مقادیر موجود در ماتریس را با پرکردن ماتریس محاسبه می‌کند، و در نتیجه فاصله بین دو رشته کامل را به عنوان مقدار نهایی به عنوان خروجی بازمی‌گرداند.

یک پیاده‌سازی ساده، به عنوان شبه‌کد برای تابع LevenshteinDistance که دو رشته را به عنوان ورودی می‌گیرد (s به طول m و t به طول n) و فاصله لوناشتاین (فاصله ویرایشی) بین آنها را محاسبه می‌کند، به صورت زیر است. توجه داشته‌باشید که رشته‌های ورودی تک اندیسی هستند، در حالی که ماتریس d دارای نمایه صفر است و [i..k] یک بازه بسته می‌باشد.

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]

فضای ناوردا در این الگوریتم این است که ما می‌توانیم بخش اولیه ${\displaystyle s[\mathrm{1..}i]}$

پیاده‌سازی با پایتون

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]

اثبات درستی

همان‌طور که قبلاً نیز اشاره شد، ناوردا (نامتغیر) این است که ما می‌توانیم با استفاده از حداقل ${\displaystyle d[i,j]}$

این مورد در ابتدا در سطر و ستون ۰ درست است زیرا ${\displaystyle s[\mathrm{1..}j]}$

اگر ${\displaystyle s[i]=t[j]}$

در غیر این‌صورت، فاصله، حداقلِ سه‌راه ممکن برای انجام این تغییر است:

اگر بتوانیم ${\displaystyle s[\mathrm{1..}i]}$

اگر بتوانیم ${\displaystyle s[\mathrm{1..}i]}$

اگر بتوانیم ${\displaystyle s[\mathrm{1..}i-1]}$

عملیات‌های مورد نیاز برای تبدیل ${\displaystyle s[\mathrm{1..}i]}$

این اثبات نمی‌تواند معتبر باشد چرا که تعداد قرار داده‌شده در ${\displaystyle d[i,j]}$

محاسبه فاصله بین دو رشته MUSE و MUSIC. جواب نهایی در خانه آخر ماتریس (سطر ۷ ام و ستون ۶ ام) قرار دارد.

محاسبه فاصله بین دو رشته carnivore و herbivore.

یافتن فاصله بین دو رشته Saturday و Sunday.

یافتن فاصله بین دو رشته kitten و sitting.

تغییرات احتمالی در این الگوریتم شامل موارد زیر است:

• ما می‌توانیم الگوریتم را با استفاده از فضای کم‌تر،${\displaystyle O(m)}$
  به جای ${\displaystyle O(mn)}$
  تطبیق دهیم، زیرا تنها لازم است ردیف قبلی و ردیف فعلی در هر زمان ذخیره شوند.
• ما می‌توانیم تعداد درج، حذف و جانشینی‌ها را به‌طور جداگانه ذخیره کنیم، یا حتی موقعیت‌هایی که در آن رخ می‌دهند، که همیشه j است.
• ما می‌توانیم فاصله تا فاصله ${\displaystyle [0,1]}$
  را نرمال کنیم.
• اگر ما تنها به فاصله علاقه‌مند باشیم و آن کوچک‌تر از یک آستانه k باشد، آن‌گاه برای محاسبه یک نوار مورب در عرض ${\displaystyle 2k+1}$
  در ماتریس کفایت می‌کند. در این روش، الگوریتم می‌تواند در زمان ${\displaystyle O(kl)}$
  اجرا شود، که در آن l طول کوتاه‌ترین طول رشته‌است.
• ما می‌توانیم هزینه‌های مختلف جریمه را به درج، حذف و جایگزینی منتسب کنیم. ما همچنین می‌توانیم هزینه‌های جریمه را که به آن کاراکترهایی که درج، حذف یا جانشین شده‌اند، ارائه نماییم.
• این الگوریتم به علت تعداد زیاد وابستگی‌های داده‌ها، ضعیف عمل می‌کند. با این‌حال، تمام مقادیر هزینه را می‌توان به صورت موازی محاسبه کرد، و الگوریتم را می‌توان برای اجرای حداقل عملکرد در فازها برای حذف وابستگی‌ها بکار برد.
• با بررسی قسمت‌های مورب به جای ردیف، و با استفاده از ارزیابی تنبل، می‌توانیم فاصله Levenshtein را در زمان ${\displaystyle O(m(1+d))}$
  پیدا کنیم که بسیار سریع‌تر از الگوریتم برنامه‌نویسی پویا است، اگر فاصله کوچک باشد.

برنامه‌نویسی پویا یک روش برنامه‌نویسی است که عمدتاً در برنامه‌نویسی رقابتی استفاده می‌شود. یکی از ساده‌ترین ترفندهای این متدولوژی، ذخیره‌سازی(Memorization) می‌باشد. ذخیره‌سازی(Memorization) یعنی مقادیری که در هر مرحله بدست می‌آوریم را در داخل یک آرایه ذخیره کرده و درصورت نیاز به چنین مقادیری، دوباره محاسبات مربوط به آن را انجام ندهیم. در این‌صورت سرعت برنامه افزایش می‌یابد. در الگوریتم واگنر-فیشر نیز از این روش استفاده می‌شود تا سرعت برنامه افزایش یابد. می‌توان گفت تفاوت روش واگنر-فیشر و لونشتاین، استفاده از برنامه‌نویسی پویا در الگوریتم واگنر-فیشر می‌باشد.

با مقداردهی اولیه ردیف اول ماتریس با صفر، ما یک متغیر از الگوریتم واگنر-فیشر را بدست می‌آوریم که می‌تواند برای جستجوی رشته‌ای فازی در یک رشته در یک متن استفاده شود. این تغییر، موقعیت نهایی انطباق متن را ایجاد می‌کند. برای تعیین موقعیت شروع رشته متناظر، تعداد درج و حذف‌ها را می‌توان به‌طور جداگانه ذخیره کرد و برای محاسبه موقعیت شروع از وضعیت نهایی استفاده کرد.

الگوریتم حاصل‌شده به هیچ وجه مؤثر نیست، اما در زمان انتشار آن(۱۹۸۰) یکی از اولین الگوریتم‌هایی بود که جستجوی تقریبی را انجام می‌داد.