תוכן עניינים
- הגדרות
- מציאת מרחק עריכה
- האלגוריתם
- זמן ריצה
הגדרות
מחרוזת S היא סדרה של n תווים. התווים יסומנו באופן הבא:
S[1],S[2],...,S[n]
הרישא בגודל k של מחרוזת S היא המחרוזת שמורכבת מ- k התווים הראשונים של המחרוזת.
נסמן אותה ב- Sk.
לדוגמא, בהינתן המחרוזת abcdef הרישא באורך 3 של המחרוזת הנתונה
היא המחרוזת abc. הרישא באורך 0 של כל מחרוזת היא המחרוזת הריקה.
מציאת מרחק עריכה
לפעמים ברצוננו לבחון "דמיון" בין שתי מחרוזות. אפשר להגדיר מדדים רבים לדמיון
בין שתי מחרוזות. אחד מהם הוא "מרחק עריכה".
נגדיר 3 פעולות בסיסיות על מחרוזת:
1. הוספת תו למחרוזת - הוספת התו יכולה להתבצע בכל מקום במחרוזת. כל התווים שאחרי
המיקום בו הוספנו את התו זזים מקום אחד קדימה.
לדוגמא, בהינתן המחרוזת abcde, אם
נוסיף את התו z במקום השני במחרוזת נקבל את המחרוזת azbcde.
2. מחיקת תו מהמחרוזת - מחיקת התו ממקום מסוים גורמת להזזה של כל התווים שבאו אחריו
מקום אחד אחורה.
לדוגמא, בהינתן המחרוזת abcde אם נמחק את התו במקום השלישי
במחרוזת נקבל את המחרוזת abde.
3. החלפת תו קיים בתו אחר - דוגמא: בהנתן המחרוזת abcde אם נחליף את התו השלישי
במחרוזת בתו p נקבל את המחרוזת abpde.
הגדרה: נתונות שתי מחרוזות S באורך n ו- T באורך m. הכמות המינימאלית של פעולות
עריכה בסיסיות שיש לבצע על מנת להפוך את המחרוזת S למחרוזת T נקראת מרחק עריכה של
המחרוזת S מהמחרוזת T.
מכאן אפשר לראות כי ככל שמרחק העריכה בין שתי מחרוזות קטן יותר כך הן דומות יותר
אחת לשניה. אם מרחק העריכה בין שתי מחרוזות הוא 0, אזי שתי המחרוזות זהות.
ברצוננו למצוא אלגוריתם יעיל שבהינתן שתי מחרוזות יחשב את מרחק העריכה ביניהן. יש
לשים לב כי מרחק העריכה של המחרוזת S מהמחרוזת T הוא גם מרחק העריכה של המחרוזת T
מהמחרוזת S מפני שהפעולות הבסיסיות שהגדרנו הפיכות. הפעולה ההפוכה לפעולה 1 היא
פעולה 2 והפעולה ההפוכה לפעולה 3 היא פעולה 3 - המחזירה חזרה את התו שהיה לפני
שהחלפנו אותו בתו אחר.
נגדיר: Di, j הוא מרחק העריכה של המחרוזת Si מהמחרוזת Tj .
אבחנה 1:
מרחק העריכה של המחרוזת הריקה ממחרוזת כלשהי באורך n הוא תמיד n. הדרך היחידה שלנו
להגיע ממחרוזת S כלשהי למחרוזת הריקה היא למחוק את כל n התווים שלה. כלומר,
דרושות לפחות n פעולות מחיקה על מנת להגיע למחרוזת הריקה, ולכן מרחק העריכה הוא n. מכאן נובעת המסקנה כי לכל i, j מתקיים:
Di,0 = i
D0,j = j
אבחנה 2:
נתונות שתי מחרוזות S ו- T. ברצוננו למצוא את מרחק העריכה בין Si לבין Tj, כלומר
לחשב את Di, j. מרחק העריכה יכול להיקבע לפי אחד משלושת המקרים הבאים:
● נבצע Di, j- 1 פעולות על מנת להפוך את המחרוזת Si למחרוזת Tj- 1. לאחר מכן נוסיף
בסופה של Tj- 1 את התו T[j] ונקבל את המחרוזת
Tj.
במקרה זה נובעת המסקנה: Di,j
= Di,j-1 + 1● נבצע Di- 1, j פעולות על מנת להפוך את המחרוזת Tj למחרוזת Si- 1. לאחר מכן נוסיף
בסופה של Si- 1 את התו S[i]ונקבל את המחרוזת Si.
במקרה זה נובעת המסקנה: Di,j = Di-1,j+1
●
נבצע Di- 1, j- 1 פעולות על מנת להפוך את המחרוזת Si- 1 למחרוזת Tj- 1.
-
אם [S[i]
= T[ j אזי על-ידי ביצוע הפעולות הנ"ל כבר הפכנו את Si
ל- Tj.
-
אם [S[i]
≠ T[ j אזי יש לעשות פעולות נוספות של החלפת התו S[i] בתו T[j] על-מנת להפוך את Si
ל- Tj.
מכאן נובעת המסקנה:
if S[i]=T[j] then
p = 0
else
p = 1
Di,j = Di-1,j-1 + p
מרחק העריכה האמיתי בין המחרוזות Si ו- Tj הוא המינימום בין שלושת המקרים.
כעת באמצעות אבחנה 1 ואבחנה 2 אפשר לנסח את האלגוריתם הבא:
edit_distance(S,T)
// איתחול
for i = 0 to n do
Di,0 = i
for j = 0 to m do
D0,j = j
// שימוש באבחנה 2
for i = 1 to n do
for j = 1 to m do
if S[i]=T[j] then
p = 0
else
p = 1
Di,j = minimum(Di-1,j+1, Di,j-1+1, Di-1,j-1+p)
return Dn,m
זמן ריצה:
האלגוריתם מבצע m+ n איטרציות בזמן האתחול. בנוסף הוא מבצע nm איטרציות בעת השימוש
באבחנה 2. לכן זמן הריצה של האלגוריתם הוא (O(nm.
דוגמת הרצה:
נשים לב כי במשבצת הימנית-תחתונה מתקבל המספר 3, לכן מרחק העריכה בין המחרוזת
hello ו- hola הוא 3.
לאלגוריתם הנ"ל יכולים להיות שימושים רבים בתחומים רבים. דוגמא טובה לכך מצוייה
במעבד התמלילים Word כאשר אנו מבצעים שגיאת איות מעבד התמלילים מציע לנו בתור הצעות
לתיקון מילים שדומות למילה השגויה. אחת הדרכים לעשות זאת היא להחזיק מאגר של מילים
נכונות, וכאשר מתגלה מילה שגויה לחפש במאגר מילים שמרחק העריכה שלהן מהמילה השגויה
הוא קטן מערך מסוים קבוע מראש ולהציג אותן בתור הצעות לתיקון (אפשר להיות מתוחכמים
יותר ולקבוע את מרחק העריכה המקסימאלי לפי אורך המילה השגויה).
|
עוד יצירות מאת יוצר זה 
