מציאת ההבדל בין שני מיתרים בג'אווה

1. סקירה כללית

מדריך מהיר זה יראה כיצד מצא את ההבדל בין שני מיתרים באמצעות Java.

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

2. הבעיה

בואו ניקח בחשבון את הדרישה הבאה: אנו רוצים למצוא את ההבדל בין המיתרים “ABCDELMN "ו-" ABCFGLMN ".

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

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

האפשרות האחרת היא StringUtils כיתה מאפצ'י קומונס לאנג.

בואו נבדוק את ההבדלים בין שני אלה.

3. תיקון מבדל התאמה

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

ראשית, נצטרך לכלול את התלות שלה בתוכן שלנו pom.xml קוֹבֶץ:

 org.bitbucket.cowwoc תיקון diff-match 1.2

ואז נבחן את הקוד הזה:

טקסט מחרוזת 1 = "ABCDELMN"; מחרוזת text2 = "ABCFGLMN"; DiffMatchPatch dmp = DiffMatchPatch חדש (); LinkedList diff = dmp.diffMain (text1, text2, false);

אם נפעיל את הקוד שלעיל - מה שמייצר את ההבדל בין טקסט 1 ו טקסט 2 - הדפסת המשתנה הבדל יפיק פלט זה:

[Diff (EQUAL, "ABC"), Diff (DELETE, "DE"), Diff (INSERT, "FG"), Diff (EQUAL, "LMN")]

למעשה, התפוקה תהיה a רשימה של Diff חפצים, כל אחד מהם נוצר על ידי סוג פעולה (לְהַכנִיס, לִמְחוֹק אוֹ שווה), ו חלק הטקסט המשויך לפעולה.

כאשר מריצים את ההבדל בין טקסט 2 ו טקסט 1, נקבל את התוצאה הזו:

[Diff (EQUAL, "ABC"), Diff (DELETE, "FG"), Diff (INSERT, "DE"), Diff (EQUAL, "LMN")]

4. StringUtils

הכיתה מ אפאצ'י קומונס יש גישה פשטנית יותר.

ראשית, נוסיף את התלות של אפאצ'י קומונס לאנג שלנו pom.xml קוֹבֶץ:

 org.apache.commons commons-lang3 3.9

ואז, כדי למצוא את ההבדל בין שני טקסטים עם Apache Commons, היינו מתקשרים StringUtils # ההבדל:

StringUtils.difference (text1, text2)

התפוקה שהופקה יהיה מחרוזת פשוטה:

FGLMN

ואילו הפעלת ההבדל בין טקסט 2 ו טקסט 1 יחזור:

DELMN

גישה פשוטה זו ניתן לשפר באמצעותStringUtils.indexOfDifference (), איזה יחזיר אתאינדקס בו שני המיתרים מתחילים להיות שונים (במקרה שלנו, הדמות הרביעית של המחרוזת). ניתן להשתמש באינדקס זה קבל תשתית של המחרוזת המקורית, להציג מה המשותף בין שתי התשומות, בנוסף לשונה.

5. ביצועים

עבור אמות המידה שלנו, אנו מייצרים רשימה של 10,000 מחרוזות עם חלק קבוע של 10 תווים, בא אחריו 20 תווים אלפביתיים אקראיים.

לאחר מכן נעבור ברשימה ונבצע הבדל בין ה- נ ' אלמנט ו n + 1 אלמנט ברשימה:

@Benchmark public int diffMatchPatch () {for (int i = 0; i <inputs.size () - 1; i ++) {diffMatchPatch.diffMain (inputs.get (i), inputs.get (i + 1), false) ; } להחזיר input.size (); }

@Benchmark ציבורי int stringUtils () {for (int i = 0; i <inputs.size () - 1; i ++) {StringUtils.difference (inputs.get (i), inputs.get (i + 1)); } להחזיר input.size (); }

לבסוף, בואו ננהל את המדדים ונשווה בין שתי הספריות:

יחידות מידה שוויון ציון Cnt יחידות StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130.559 ± 1.501 ms / op StringDiffBenchmarkUnitTest.stringUtils avgt 50 0.211 ± 0.003 ms / op

6. מסקנה

במונחים של מהירות ביצוע טהורה, StringUtils ברור שמבצע יותר, למרות שהוא מחזיר רק את המצע שממנו שני המיתרים מתחילים להיות שונים.

באותו הזמן, Diff-Match-Patch מספק תוצאת השוואה יסודית יותר, על חשבון הביצועים.

היישום של דוגמאות וקטעי מידע אלה זמין ב- GitHub.

streamalism.org