כיצד לחשב מרחק לוונשטיין בג'אווה?

1. הקדמה

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

אנו מספקים יישום איטרטיבי ויישומי ג'אווה של האלגוריתם הזה.

2. מה המרחק של לבנשטיין?

המרחק של לבנשטיין הוא מדד לא שונה בין שניים מיתרים. מתמטית, נתון שניים מיתריםאיקס ו y, המרחק מודד את המספר המינימלי של עריכות תווים הדרושות לשינוי איקס לְתוֹך y.

בדרך כלל מותרות שלוש סוגי עריכות:

  1. הכנסת דמות ג
  2. מחיקת דמות ג
  3. החלפת דמות ג עם ג

דוגמא: אם x = 'ירייה' ו y = 'נקודה', מרחק העריכה בין השניים הוא 1 כי 'בְּעִיטָה' ניתן להמיר ל 'לְזַהוֹת' על ידי החלפת 'ח' ל 'עמ '‘.

בקטגוריות משנה מסוימות של הבעיה, העלות הכרוכה בכל סוג עריכה עשויה להיות שונה.

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

חלק מהיישומים של מרחק העריכה הם:

  1. בודקי איות - איתור שגיאות כתיב בטקסט ומציאת האיות הנכון ביותר במילון
  2. איתור פלגיאט (עיין - נייר IEEE)
  3. ניתוח DNA - מציאת דמיון בין שני רצפים
  4. זיהוי דיבור (עיין - Microsoft Research)

3. ניסוח אלגוריתם

בוא ניקח שניים מיתרים x ו y של אורכים M ו נ בהתאמה. אנחנו יכולים לציין כל אחד מהם חוּט כפי ש x [1: מ '] ו y [1: n].

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

  1. החלפה:
    1. קבע את העלות (D1) של החלפה x [1] עם y [1]. עלות שלב זה תהיה אפס אם שתי התווים זהים. אם לא, העלות תהיה אחת
    2. לאחר שלב 1.1 אנו יודעים ששניהם מיתרים התחל עם אותה דמות. לפיכך העלות הכוללת תהיה כעת סכום העלות של שלב 1.1 ועלות ההפיכה של שאר הוצאות מחרוזת x [2: מ '] לְתוֹך y [2: n]
  2. הַכנָסָה:
    1. הכנס תו ל איקס כדי להתאים את הדמות הראשונה ב yהעלות של צעד זה תהיה אחת
    2. לאחר 2.1, עיבדנו תו אחד מ- y. מכאן שהעלות הכוללת תהיה כעת סכום העלות של שלב 2.1 (כלומר, 1) ועלות שינוי המלא x [1: מ '] להישאר y (y [2: n])
  3. מְחִיקָה:
    1. מחק את התו הראשון מ- איקסהעלות של צעד זה תהיה אחת
    2. לאחר 3.1 עיבדנו תו אחד מ- איקס, אבל המלא y נותר לעבד. העלות הכוללת תהיה סכום העלות של 3.1 (כלומר, 1) ועלות השינוי שנותרה איקס עד תום y

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

4. יישום רקורסיבי נאיבי

אנו יכולים לראות כי השלב השני של כל אפשרות בסעיף 3 הוא לרוב אותה בעיית מרחק עריכה אך על מיתרי משנה של המקור. מיתרים. המשמעות היא שאחרי כל איטרציה נגיע לאותה הבעיה אך עם קטנה יותר מיתרים.

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

D (x [1: m], y [1: n]) = דקה {

D (x [2: m], y [2: n]) + עלות החלפת x [1] ל- y [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}

עלינו להגדיר גם מקרי בסיס לאלגוריתם הרקורסיבי שלנו, שבמקרה שלנו הוא כאשר אחד או שניהם מיתרים להיות ריק:

  1. כאשר שניהם מיתרים ריקים, ואז המרחק ביניהם הוא אפס
  2. כאשר אחד מה מיתרים ריק, ואז מרחק העריכה ביניהם הוא אורך האחר חוּט, כיוון שאנחנו צריכים מספרים רבים של הכנסות / מחיקות כדי להפוך אחד לשני:
    • דוגמה: אם אחד חוּט הוא "כֶּלֶב" ואחר חוּט הוא “” (ריק), אנו זקוקים לשלוש הכנסות בריק חוּט להצליח "כֶּלֶב", או שאנחנו צריכים שלוש מחיקות ב "כֶּלֶב" כדי שיהיה ריק. מכאן שמרחק העריכה ביניהם הוא 3

יישום רקורסיבי נאיבי של אלגוריתם זה:

מחלקה ציבורית EditDistanceRecursive {static int calc (String x, String y) {if (x.isEmpty ()) {return y.length (); } אם (y.isEmpty ()) {להחזיר x.length (); } int החלפה = לחשב (x.substring (1), y.substring (1)) + costOfSubstitution (x.charAt (0), y.charAt (0)); הכנסת int = חישוב (x, y. substring (1)) + 1; מחיקה int = לחשב (x.substringing (1), y) + 1; החזר דקה (החלפה, הכנסה, מחיקה); } עלות ציבורית סטטית ציבוריתOfSubstitution (char a, char b) {return a == b? 0: 1; } ציבורי סטטי int min (int ... numbers) {return Arrays.stream (numbers) .min (). orElse (Integer.MAX_VALUE); }}

לאלגוריתם זה יש את המורכבות האקספוננציאלית. בכל שלב, אנו מסתדרים לשלוש שיחות רקורסיביות, בונים שיחה O (3 ^ n) מוּרכָּבוּת.

בחלק הבא נראה כיצד ניתן לשפר זאת.

5. גישה לתכנות דינמי

בניתוח השיחות הרקורסיביות נצפה כי הטיעונים לבעיות משנה הם סיומות של המקור מיתרים. זה אומר שיכול להיות רק m * n שיחות רקורסיביות ייחודיות (איפה M ו נ הם מספר סיומות של איקס ו y). מכאן שמורכבות הפתרון האופטימלי צריכה להיות ריבועית, O (m * n).

בואו נסתכל על כמה מבעיות המשנה (על פי יחס ההישנות המוגדר בסעיף 4):

  1. בעיות משנה של D (x [1: m], y [1: n]) הם D (x [2: m], y [2: n]), D (x [1: m], y [2: n]) ו D (x [2: m], y [1: n])
  2. בעיות משנה של D (x [1: m], y [2: n]) הם D (x [2: m], y [3: n]), D (x [1: m], y [3: n]) ו D (x [2: m], y [2: n])
  3. בעיות משנה של D (x [2: m], y [1: n]) הם D (x [3: m], y [2: n]), D (x [2: m], y [2: n]) ו D (x [3: m], y [1: n])

בשלושת המקרים אחת מתת-הבעיות היא D (x [2: m], y [2: n]). במקום לחשב את זה שלוש פעמים כמו שאנחנו עושים ביישום הנאיבי, אנחנו יכולים לחשב את זה פעם אחת ולעשות שימוש חוזר בתוצאה בכל פעם שצריך שוב.

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

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

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

חישוב int סטטי (String x, String y) {int [] [] dp = int int [x.length () + 1] [y.length () + 1]; עבור (int i = 0; i <= x.length (); i ++) {for (int j = 0; j <= y.length (); j ++) {if (i == 0) {dp [i] [j] = j; } אחר אם (j == 0) {dp [i] [j] = i; } אחר {dp [i] [j] = min (dp [i - 1] [j - 1] + costOfSubstitution (x.charAt (i - 1), y.charAt (j - 1)), dp [i - 1] [j] + 1, dp [i] [j - 1] + 1); }}} להחזיר dp [x.length ()] [y.length ()]; } 

אלגוריתם זה מבצע ביצועים טובים משמעותית מהיישום הרקורסיבי. עם זאת, זה כרוך בצריכת זיכרון משמעותית.

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

6. מסקנה

במאמר זה תיארנו מהו מרחק Levenshtein וכיצד ניתן לחשב אותו באמצעות גישה רקורסיבית ומבוססת על תכנות דינמי.

מרחק לבנשטיין הוא רק אחד המדדים של דמיון מחרוזות, חלק מהמדדים האחרים הם דמיון קוסינוס (המשתמש בגישה מבוססת אסימון ורואה במיתרים וקטורים), מקדם קוביות וכו '.

כמו תמיד ניתן למצוא את היישום המלא של הדוגמאות ב- GitHub.


$config[zx-auto] not found$config[zx-overlay] not found