فاصله‌ی ویرایشی

فاصله‌ی ویرایشی بین دو کلمه، که فاصله‌ی لوانشتین (Levenshtein) نیز نامیده می‌شود، کمترین تعداد حذف، اضافه، یا تغییر حروف است که نیاز داریم تا یکی از این کلمات را به دیگری تبدیل کنیم. برای مثال فرض کنید می‌خواهیم فاصله‌ی کلمه‌ی «اجتماع» و «مجموعه» را محاسبه کنیم. این مقدار حداکثر برابر چهار است:
مجموعه → مجموع → مجماع → مجتماع → اجتماع
می‌توان این روند را با زیر هم نوشتن کلمات نیز نشان داد:

   ا  ج  ت  م  ا  ع     
م  ج     م  و  ع  ه

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

بیایید برای حل سوال از روش برنامه‌ریزی پویا کمک بگیریم. فرض کنید می‌خواهیم فاصله‌ی بین i خانه‌ی اول از کلمه‌ی اول و j خانه‌ی اول از کلمه‌ی دوم را محاسبه کنیم. به این مقدار $d_{i,j}$ می‌گوییم. پس جواب مسئله $d_{n,m}$ است اگر $n$ و $m$ را به ترتیب تعداد حروف کلمه‌ی اول و دوم در نظر بگیریم.
اگر مثلا $i$ برابر صفر باشد، جواب برابر $j$ است، چون باید تمام $j$ حرف را به کلمه‌ی اول اضافه کنیم. همچنین اگر $j$ برابر صفر باشد، جواب برابر $i$ است، چون باید تمام $i$ خانه‌ی کلمه‌ی اول را حذف کنیم تا به کلمه دوم برسیم. در غیر اینصورت، یا می‌توانیم یکی از سه کار زیر را انجام دهیم:

1. حرف i ام کلمه‌ی اول را حذف کنیم، در نتیجه باید علاوه بر این عمل حذف، باید $i-1$ حرف اول کلمه‌ی اول را نیز به $j$ حرف اول کلمه‌ی دوم تبدیل کنیم که این مقدار خودش یکی از خانه‌های جدول ما است، یعنی $d_{i-1,j}$ . پس تعداد تغییرات برابر$ d_{i-1,j} + 1$ می‌شود.
   
2. حرف $j$ ام کلمه‌ی دوم را به کلمه‌ی اول اضافه کنیم، در نتیجه علاوه بر این باید $i$ حرف اول کلمه‌ی اول را به $j-1$ حرف اول کلمه‌ی دوم تبدیل کنیم، یعنی $d_{i,j-1}$ . پس تعداد تغییرات برابر $d_{i,j-1} + 1$ می‌شود.
   
3. حرف $i$ ام کلمه‌ی اول را به حرف $j$ ام کلمه‌ی دوم تغییر دهیم. پس باید بعد از این $i-1$ حرف اول کلمه‌ی اول را به $j-1$ حرف اول کلمه‌ی دوم تبدیل کنیم. در نتیجه تعداد تغییرات برابر $d_{i-1,j-1} + 1$ می‌شود. البته اگر این دو حرف یکسان باشند، نیازی به تغییر نیست و تعداد تغییرات در این حالت برابر $d_{i-1,j-1}$ می‌شود.
   

شبه کد: ($a_i$ را حرف $i$ ام کلمه‌ی اول و $b_j$ را حرف $j$ ام کلمه‌ی دوم در نظر بگیرید.)

for i from 0 to n
	d[i][0] = i
for j from 0 to n
	d[0][j] = j

for i from 1 to n
	for j from 1 to n
		if a[i] == b[j]
			plus = 0
		else
			plus = 1
		d[i][j] = min( d[i-1][j] + 1 , d[i][j-1] + 1 , d[i-1][j-1] + plus )

از آنجایی که هر ستون فقط از روی خودش و ستون قبلش به روز رسانی می‌شود، می‌توان به جای نگه داشتن یک آرایه $n*m$ از یک آرایه‌ی $2*n$ که از $O(n)$ است استفاده کنیم. اما اگر برای ما به جز تعداد تغییرات در بهترین حالت، خود این تغییرات نیز مهم باشد، در هر صورت باید یک آرایه‌ی $n*m$ برای نگه‌داری مسیر برگشت استفاده کنیم که اندازه‌ی حافظه از $O(n*m)$ می‌شود. اما در هر دو صورت باید $n*m$ مقدار را محاسبه کنیم و هر محاسبه هم از $O(1)$ است. پس پیچیدگی زمانی $O(n*m)$ است.

edit_distance.cpp

#include<iostream>
using namespace std;
 
const int MAXN=10*1000;
 
int d[MAXN+10][MAXN+10];
int a[MAXN+10];
int b[MAXN+10];
 
int main(){
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n;
	for(int i=0; i<n; i++)
		cin >> a[i];
	cin >> m;
	for(int j=0; j<m; j++)
		cin >> b[j];
 
	for(int i=0; i<=n; i++)
		d[i][0] = i;
	for(int j=0; j<=m; j++)
		d[0][j] = j;
 
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++){
 
			int plus = 1;
			if( a[i-1] == b[j-1] )  // a and b are 0-base
				plus = 0;
 
			d[i][j] = min( min( d[i-1][j] + 1 , d[i][j-1] + 1 ) ,
					d[i-1][j-1] + plus );
		}
 
	cout << d[n][m] << endl;
 
	return 0;	
}