Edit Distance (מרחק עריכה)

מחרוזת X:

מחרוזת Y:

s(i,j) = מרחק עריכה בין X[1..i] ל-Y[1..j]

s(i,0) = i — הוספת i תווים

s(0,j) = j — הוספת j תווים

for each 1 ≤ i ≤ n, 1 ≤ j ≤ m:

s(i,j) = min{ s(i−1,j)+1, s(i,j−1)+1, s(i−1,j−1)+δ(x_i,y_j) }

δ(x_i,y_j) = 0 אם x_i=y_j, אחרת 1 | s(i−1,j)+1: מחיקה | s(i,j−1)+1: הוספה | s(i−1,j−1)+δ: החלפה/התאמה

אלכסון T[i-1][j-1] (החלפה)

T[i-1][j] (מחיקה)

T[i][j-1] (הוספה)

ערך נוכחי

תוצאה

מסלול אחורה

סדרת פעולות אופטימלית:

לחץ על "הבא" להתחלת הסימולציה