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

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

تاریخچه

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

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

الگوریتم

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

یک پیاده‌سازی ساده، به عنوان شبه‌کد برای تابع 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]

فضای ناوردا در این الگوریتم این است که ما می‌توانیم بخش اولیه $s[1..i]$ را با استفاده از حداقل $d[i,j]$ عملیات $t[1..j]$ تغییر دهیم. در پایان، عنصر پایین-راست آرایه شامل پاسخ است.

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

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]

اثبات درستی

همان‌طور که قبلاً نیز اشاره شد، ناوردا (نامتغیر) این است که ما می‌توانیم با استفاده از حداقل $d[i,j]$ عملیات، بخش اولیه $s[1..i]$ به $t[1..j]$ تبدیل کنیم.

این مورد در ابتدا در سطر و ستون ۰ درست است زیرا $s[1..j]$ با انداختن تمام حروف i می‌تواند به یک رشته خالی $t[1..0]$ تبدیل شود. به‌طور مشابه، ما می‌توانیم $s[1..0]$ را به سادگی با اضافه کردن تمام حروف j، به $t[1..j]$ تغییر دهیم.

اگر $s[i]=t[j]$، آن‌گاه ما می‌توانیم $s[1..j-1]$ را به $t[1..j-1]$ در k عملیات تغییر دهیم، آنگاه می‌توانیم همین کار روی $s[1..j]$ را انجام دهیم و فقط آخرین کاراکتر را رها کنیم، و k عملیات را انجام دهیم.

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

اگر بتوانیم $s[1..i]$ را به $t[1..j-1]$ در k عملیات تبدیل کنیم، آن‌گاه به سادگی می‌توانیم $t[j]$ را برای بدست‌آوردن $t[1..j]$ در k + ۱ عملیات اضافه کنیم (درج).

اگر بتوانیم $s[1..i]$ را به $t[1..j-1]$ در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم $s[i]$ را حذف کنیم و سپس همان انتقال را با k + 1 عملیات انجام دهیم (حذف).

اگر بتوانیم $s[1..i-1]$ را به $t[1..j-1]$ در k عملیات تبدیل کنیم، آن‌گاه می‌توانیم همان کار را روی $s[1..i]$ انجام دهیم و با k + 1 عملیات جای $s[i]$ را با $t[j]$ عوض کنیم (جانشینی).

عملیات‌های مورد نیاز برای تبدیل $s[1..i]$ به $t[1..j]$ عددی است که برای تبدیل همه sها به همه tها مورد نیاز است، و بنابراین $d[n,m]$ نتیجه نهایی ما می‌باشد.

این اثبات نمی‌تواند معتبر باشد چرا که تعداد قرار داده‌شده در $d[i,j]$ در واقع کمینه است؛ این کار برای نشان‌دادن دشوارتر است، و شامل یک مشاجره با تناقضی است که در آن فرض می‌کنیم $d[i,j]$ کوچک‌تر از حداقل سه است، و استفاده از این برای نشان‌دادن یکی از این سه مقدار، مقدار حداقل نیست.

مثال‌هایی از الگوریتم واگنر-فیشر

E	S	U	M
۴	۳	۲	۱	۰
۴	۳	۲	۰	۱	M
۴	۳	۰	۲	۲	U
۴	۰	۳	۳	۳	S
۱	۴	۴	۴	۴	I
۲	۵	۵	۵	۵	C

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

e	r	o	v	i	n	r	a	c
۹	۸	۷	۶	۵	۴	۳	۲	۱	۰
۹	۸	۷	۶	۵	۴	۳	۲	۱	۱	h
۹	۸	۷	۶	۵	۴	۳	۲	۲	۲	e
۹	۷	۷	۶	۵	۴	۲	۳	۳	۳	r
۸	۸	۷	۶	۵	۳	۴	۴	۴	۴	b
۹	۸	۷	۶	۳	۵	۵	۵	۵	۵	i
۹	۸	۷	۳	۶	۶	۶	۶	۶	۶	v
۹	۸	۳	۷	۷	۷	۷	۷	۷	۷	o
۹	۳	۸	۸	۸	۸	۸	۸	۸	۸	r
۳	۹	۹	۹	۹	۸	۹	۹	۹	۹	e

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

y	a	d	r	u	t	a	S
۸	۷	۶	۵	۴	۳	۲	۱	۰
۷	۶	۵	۴	۳	۲	۱	۰	۱	S
۶	۵	۴	۳	۲	۲	۱	۱	۲	u
۶	۵	۴	۳	۳	۲	۲	۲	۳	n
۵	۴	۳	۴	۳	۳	۳	۳	۴	d
۴	۳	۴	۴	۴	۴	۳	۴	۵	a
۳	۴	۵	۵	۵	۴	۴	۵	۶	y

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

n	e	t	t	i	k
۶	۵	۴	۳	۲	۱	۰
۶	۵	۴	۳	۲	۱	۱	s
۵	۴	۳	۲	۱	۲	۲	i
۴	۳	۲	۱	۲	۳	۳	t
۳	۲	۱	۲	۳	۴	۴	t
۳	۲	۲	۳	۴	۵	۵	i
۲	۳	۳	۴	۵	۶	۶	n
۳	۴	۴	۵	۶	۷	۷	g

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

اصلاحات ممکن

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

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

رابطه الگوریتم واگنر-فیشر و برنامه‌سازی پویا

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

متغیر سِلِرز برای جستجوی رشته

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

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