למה צריך לבחור לפעמים את האלגוריתם הנכון בעת השוואת מחרוזות

אם אנחנו רוצים להשוואת האם שתי מחרוזות הן תואמות, יש לנו דרך מאוד קלה: להשתמש בפונקציית equal שיש לכל שפה. האלגוריתם פשוט, והוא עובר על כל תו ומוודא שהתווים שווים בכל המקומות. עוד לפני כן האלגוריתם מוודא ששתי המחרוזות שוות אורך כי אחרת לא צריך לבצע בדיקה נוספת.

אבל העניינים מעט מסתבכים כשאנחנו רוצים לעשות fuzzy string search, כלומר להשוואת בין מחרוזות שאינן תואמות במאת האחוזים הן באורך והן בתאימות של התווים. כמו כן לפעמים אנחנו כותבים מילים עם שגיאות, או רוצים לעשות auto complete, או לפתור בעיות ב- NLP ואפילו לזהות התאמה בין רצפים גנטיים.

במקרה בו שני מחרוזות אינן תואמות במדויק, אנחנו רוצים לדעת עד כמה המחרוזות שונות אחת מהשנייה. ככה נוכל לזהות “מועמדים” שראויים להיות דומים ואף להיות המחרוזת “המתקונת” (לדוגמה- cumputer & computer), או סתם לקבל הערכה לעד כמה מחרוזות שונות אחת מהשנייה בספקטרום.

בשביל להעריך עד כמה מחרוזת אחת שונה מהשנייה, אנחנו מחשבים את ה"מרחק" שיש בין המחרוזת הראשונה לשנייה, כלומר כמה אופרציות עלינו לבצע על המחרוזת הראשונה בשביל להפוך אותה למחרוזת השנייה. כל אופרציה של שינוי באחת המחרוזות מוסיפה 1 לערך הכולל של המרחק (נקרא גם edit distance). לדוגמה, במחרוזות ‘נואו’ ו- ‘ניאו’ יש מרחק של אופרציה אחת (החלפת ה-ו’ בי’).

לחישוב המרחק בין שתי מחרוזות יש מספר אלגוריתמים, שלכל אחד הערך של המרחק בין שני המחרוזות ישתנה, בגלל שהוא מאפשר\מונע אופרציות שונות. למשל, האלגוריתם levenshtein distance מאפשר לנו את האופרציות הבאות: לשנות, להוסיף או למחוק תו. על כל תו שאנחנו מסתכלים, אנחנו יכולים או לשנות אותה, או למחוק, או להוסיף לידה.

האלגוריתם hamming distance עובר תו תו ומשווה האם התווים דומים או שונים בכל מיקום. האלגוריתם מאפשר אופרציה אחת בלבד והיא לשנות תו, ולכן הוא יתאים רק למחרוזות בעלי אורך זהה. האלגוריתם של לוונשטיין תמיד יהיה בעל ערך שווה או נמוך מהאמינג, מכיוון שהאופרציות הנוספות שיש ללוונשטיין מאפשרות להפחית את כמות האופרציות הנחוצות.

לדוגמה, המחרוזות “אבגד” ו- “בגדה” הן במרחק של 4 לפי האלגוריתם של האמינג בגלל שבכל מיקום במחרוזת הראשונה, צריך לשנות בתו אחר. אבל המרחק לפי האלגוריתם של לוונשטיין יהיה 2, כי אפשר להוריד את ה-א’ ולהוסיף ה’ ותצא לנו המחרוזת השנייה.

האלגוריתם של לוונשטיין הוא יקר יותר מהאלגוריתם של האמינג, מכיוון שהאלגוריתם פותר את הבעיה בסיבוכיות של nm (האורכים של כל מחרוזת) והאמינג ב- max(n,m). לכן לא תמיד הפתרון האידיאלי יהיה לעבוד לפי האלגוריתם של לוונשטיין. כמובן, שיש עוד אלגוריתמים עם תנאים שונים שמביאים תוצאות שונות בהתאם לצורך של החיפוש\השוואה בין המחרוזות.

לכל אלגוריתם יש את הbest usage משלו, כמו למשל האלגוריתם של לוונשטיין שיעיל בזיהוי שגיאות כתיב, או Levenshtein Damerau שיעיל יותר בשגיאות של החלפת אותיות( copmuter) מכיוון שהוא מאפשר גם אופרציה של החלפת המיקום של התווים (בנוסף לשאר האופרציות של לוונשטיין). לפי levenshtein damerau החלפת מקומי תווים נחשבת לאופרציה אחת, ואילו לפי לוונשטיין אין אפשרות להחליף בין המיקומים תווים, אז נאלץ למחוק ולהוסיף (2 אופרציות).

האלגוריתם של האמינג משומש דווקא למקרים אחרים, והפופולרי מבניהם הוא error detection של מידע שנשלח בתקשורת שונות כמו IP (האלגוריתם עוזר להגדיר “d-error” או כמות הביטים שכנראה השתנו בהודעה שהתקבלה לעומת המקורית).