streamalism.org

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

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

2. התאמת תבניות מיתרים

2.1. הַגדָרָה

במחרוזות, התאמת תבניות היא תהליך בדיקת רצף נתון של תווים שנקרא תבנית ברצף תווים הנקרא a טֶקסט.

הציפיות הבסיסיות של התאמת תבנית כאשר התבנית אינה ביטוי קבוע הן:

• ההתאמה צריכה להיות מדויקת - לא חלקית
• התוצאה צריכה להכיל את כל המשחקים - לא רק את המשחק הראשון
• התוצאה צריכה להכיל את המיקום של כל התאמה בטקסט

2.2. מחפש תבנית

בואו נשתמש בדוגמה להבנת בעיית התאמה פשוטה של ​​דפוסים:

תבנית: NA טקסט: HAVANABANANA התאמה 1: ---- לא ------ התאמה 2: -------- לא-- התאמה 3: ---------- לא

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

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

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

2.3. מבנה נתונים Trie לאחסון דפוסים

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

אנו יודעים שמבנה נתוני trie מאחסן את הדמויות של מחרוזת במבנה דמוי עץ. אז, לשני מיתרים {NA, NAB}, נקבל עץ עם שני שבילים:

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

שימו לב שאנחנו משתמשים ב- $ תו כדי לציין את סוף המחרוזת.

2.4. מבנה נתוני הסיומת של סיומת לאחסון טקסט

א סיומת טרי, לעומת זאת, הוא מבנה נתוני trie נבנה באמצעות כל הסיומות האפשריות של מחרוזת אחת.

לדוגמא הקודמת HAVANABANANAנוכל לבנות סיומת של סיומת:

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

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

נבחן גרסה משופרת של טריפ הסיומת בחלק הבא.

3. עץ הסיומת

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

אז נוכל ליצור עץ סיומת לאותו טקסט HAVANABANANA:

כל שביל החל מהשורש ועד העלה מייצג סיומת של המחרוזת HAVANABANANA.

גם עץ סיומת מאחסן את מיקום הסיומת בצומת העלה. לדוגמה, בננה $ היא סיומת המתחילה מהעמדה השביעית. לפיכך, ערכו יהיה שישה תוך שימוש במספור מבוסס אפס. כְּמוֹ כֵן, A-> BANANA $ הוא סיומת נוספת המתחילה ממצב חמש, כפי שאנו רואים בתמונה לעיל.

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

אם הנתיב מסתיים בצומת עלים, נקבל התאמת סיומות. אחרת, אנו מקבלים רק התאמת סובסטרים. לדוגמא, התבנית NA הוא סיומת של HAVANABANA [NA] ומצע של HAVA [NA] BANANA.

בחלק הבא נראה כיצד ליישם את מבנה הנתונים הזה ב- Java.

4. מבנה נתונים

בואו ניצור מבנה נתוני עץ סיומת. נצטרך שתי מחלקות תחום.

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

אז בואו ניצור את שלנו צוֹמֶת מעמד:

צמת בכיתה ציבורית {טקסט מחרוזת פרטי; ילדים ברשימה פרטית; תפקיד אינטימי פרטי; צומת ציבורי (מחרוזת, מיקום int) {this.text = מילה; this.position = עמדה; this.children = ArrayList חדש (); } // getters, setters, toString ()}

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

כתוצאה מכך, יש לנו SuffixTree מעמד:

סוג ציבורי SuffixTree {מחרוזת סופי סטטי פרטי WORD_TERMINATION = "$"; סופי סטטי פרטי POSITION_UNDEFINED = -1; שורש הצומת הפרטי; מחרוזת פרטית fullText; SuffixTree ציבורי (טקסט מחרוזת) {root = new Node ("", POSITION_UNDEFINED); fullText = טקסט; }}

5. שיטות עוזר להוספת נתונים

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

בואו נשנה את שלנו SuffixTree בכיתה להוסיף כמה שיטות הדרושות לבניית העץ.

5.1. הוספת צומת ילד

ראשית, תהיה לנו שיטה addChildNode ל להוסיף צומת צאצא חדש לכל צומת הורה נתון:

חלל פרטי addChildNode (צומת parentNode, טקסט מחרוזת, אינדקס int) {parentNode.getChildren (). להוסיף (צומת חדש (טקסט, אינדקס)); }

5.2. מציאת הקידומת המשותפת הארוכה ביותר של שני מיתרים

שנית, נכתוב שיטת שימוש פשוטה getLongestCommonPrefix ל מצא את הקידומת הנפוצה הארוכה ביותר של שני מיתרים:

מחרוזת פרטית getLongestCommonPrefix (String str1, String str2) {int CompareLength = Math.min (str1.length (), str2.length ()); עבור (int i = 0; i <CompareLength; i ++) {if (str1.charAt (i)! = str2.charAt (i)) {return str1.substring (0, i); }} להחזיר str1.substring (0, השווה אורך); }

5.3. פיצול צומת

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

אנו יכולים לראות מהתמונה למטה את זה ANA מתפצל ל A-> NA. לאחר מכן, הסיומת החדשה ABANANA $ ניתן להוסיף כ A-> BANANA $:

בקיצור, זו שיטת נוחות שתהיה שימושית בעת הכנסת צומת חדש:

חלל פרטי splitNodeToParentAndChild (צומת parentNode, String parentNewText, String childNewText) {צומת childNode = צומת חדש (childNewText, parentNode.getPosition ()); אם (parentNode.getChildren (). size ()> 0) {while (parentNode.getChildren (). size ()> 0) {childNode.getChildren () .add (parentNode.getChildren (). להסיר (0)); }} parentNode.getChildren (). הוסף (childNode); parentNode.setText (parentNewText); parentNode.setPosition (POSITION_UNDEFINED); }

6. שיטת עוזר למעבר

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

6.1. התאמה חלקית מול התאמה מלאה

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

כדי להוסיף סיומת חדשה ANABANANA $, אנו בודקים אם קיים צומת כלשהו שניתן לשנות או להרחיב כדי להתאים לערך החדש. לשם כך, אנו משווים את הטקסט החדש עם כל הצמתים ומוצאים כי הצומת הקיים [A] VANABANANA $ משחקים בדמות ראשונה. לכן, זהו הצומת שעלינו לשנות, וניתן לקרוא להתאמה זו התאמה חלקית.

מצד שני, בואו ניקח בחשבון שאנחנו מחפשים את הדפוס שַׁבשֶׁבֶת על אותו עץ. אנו יודעים שזה תואם חלקית עם [VAN] ABANANA $ על שלוש הדמויות הראשונות. אם כל ארבע הדמויות היו תואמות, היינו יכולים לקרוא לזה התאמה מלאה. לצורך חיפוש תבניות, יש צורך בהתאמה מלאה.

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

6.2. חוצה את העץ

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

רשימה getAllNodesInTraversePath (דפוס מחרוזת, צומת startNode, בוליאני isAllowPartialMatch) {// ...}

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

ראשית בהשוואה בין התו הראשון של טקסט התבנית לטקסט הצומת:

אם (pattern.charAt (0) == nodeText.charAt (0)) {// לוגיקה לטיפול בתווים הנותרים} 

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

אם (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {nodes.add (currentNode); צמתים להחזיר; } 

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

int CompareLength = Math.min (nodeText.length (), pattern.length ()); עבור (int j = 1; j <CompareLength; j ++) {if (pattern.charAt (j)! = nodeText.charAt (j)) {if (isAllowPartialMatch) {nodes.add (currentNode); } להחזיר צמתים; }} 

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

nodes.add (currentNode);

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

אם (pattern.length ()> CompareLength) {List nodes2 = getAllNodesInTraversePath (pattern.substring (CompareLength), currentNode, isAllowPartialMatch); אם (nodes2.size ()> 0) {nodes.addAll (nodes2); } אחר אם (! isAllowPartialMatch) {nodes.add (null); }} להחזיר צמתים;

מחברים את כל זה, בואו ניצור getAllNodesInTraversePath:

רשימה פרטית getAllNodesInTraversePath (תבנית מחרוזת, צומת startNode, בוליאנית isAllowPartialMatch) {צמתים רשימה = ArrayList חדש (); עבור (int i = 0; i <startNode.getChildren (). size (); i ++) {Node currentNode = startNode.getChildren (). get (i); מחרוזת nodeText = currentNode.getText (); if (pattern.charAt (0) == nodeText.charAt (0)) {if (isAllowPartialMatch && pattern.length () <= nodeText.length ()) {nodes.add (currentNode); צמתים להחזיר; } int CompareLength = Math.min (nodeText.length (), pattern.length ()); עבור (int j = 1; j CompareLength) {List nodes2 = getAllNodesInTraversePath (pattern.substring (CompareLength), currentNode, isAllowPartialMatch); אם (nodes2.size ()> 0) {nodes.addAll (nodes2); } אחר אם (! isAllowPartialMatch) {nodes.add (null); }} להחזיר צמתים; }} להחזיר צמתים; }

7. אלגוריתם

7.1. אחסון נתונים

כעת אנו יכולים לכתוב את ההיגיון שלנו לאחסון נתונים. נתחיל בהגדרת שיטה חדשה addSuffix על SuffixTree מעמד:

ריק ריק addSuffix (סיומת מחרוזת, מיקום int) {// ...}

המתקשר יספק את עמדת הסיומת.

לאחר מכן, בואו נכתוב את ההיגיון לטיפול בסיומת. ראשית, עלינו לבדוק אם קיים נתיב התואם את הסיומת באופן חלקי לפחות על ידי קריאה לשיטת העוזר שלנו getAllNodesInTraversePath עם isAllowPartialMatch נקבע כ נָכוֹן. אם אין נתיב, אנו יכולים להוסיף את הסיומת שלנו כילד לשורש:

צמתים ברשימה = getAllNodesInTraversePath (תבנית, שורש, נכון); אם (nodes.size () == 0) {addChildNode (שורש, סיומת, מיקום); }

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

צומת lastNode = nodes.remove (nodes.size () - 1); מחרוזת newText = סיומת; אם (nodes.size ()> 0) {String existingSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (existingSuffixUptoLastNode.length ()); }

לשינוי הצומת הקיים, בואו ניצור שיטה חדשה extendode, אליו נקרא מהמקום בו הפסקנו addSuffix שיטה. לשיטה זו שתי תחומי מפתח מרכזיים. האחד הוא לפרק צומת קיים להורה ולילד, והשני הוא להוסיף ילד לצומת ההורה החדש שנוצר. אנו מפרקים את צומת האב רק כדי להפוך אותו לצומת משותף לכל צמתי הילד שלו. אז השיטה החדשה שלנו מוכנה:

ריק ריק מאריך (צומת צומת, מחרוזת טקסט חדש, מיקום int) {מחרוזת currentText = node.getText (); מחרוזת commonPrefix = getLongestCommonPrefix (currentText, newText); אם (commonPrefix! = currentText) {String parentText = currentText.substring (0, commonPrefix.length ()); מחרוזת childText = currentText.substring (commonPrefix.length ()); splitNodeToParentAndChild (node, parentText, childText); } מחרוזת leftText = newText.substring (commonPrefix.length ()); addChildNode (צומת, נשאר טקסט, מיקום); }

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

ריק ריק addSuffix (סיומת מחרוזת, מיקום int) {צמתים ברשימה = getAllNodesInTraversePath (סיומת, שורש, נכון); אם (nodes.size () == 0) {addChildNode (שורש, סיומת, מיקום); } אחר {Node lastNode = nodes.remove (nodes.size () - 1); מחרוזת newText = סיומת; אם (nodes.size ()> 0) {String existingSuffixUptoLastNode = nodes.stream () .map (a -> a.getText ()) .reduce ("", String :: concat); newText = newText.substring (existingSuffixUptoLastNode.length ()); } extendNode (lastNode, newText, position); }}

לבסוף, בואו לשנות את שלנו SuffixTree בנאי ליצור את הסיומות ולקרוא לשיטה הקודמת שלנו addSuffix כדי להוסיף אותם באופן איטרטיבי למבנה הנתונים שלנו:

חלל ציבורי SuffixTree (טקסט מחרוזת) {root = new Node ("", POSITION_UNDEFINED); עבור (int i = 0; i <text.length (); i ++) {addSuffix (text.substring (i) + WORD_TERMINATION, i); } טקסט מלא = טקסט; }

7.2. חיפוש נתונים

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

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

רשימת ציבורי searchText (דפוס מחרוזת) {// ...}

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

צמתים ברשימה = getAllNodesInTraversePath (תבנית, שורש, שקר);

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

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

רשימה פרטית getPositions (צומת צומת) {מיקומי רשימה = ArrayList חדש (); אם (node.getText (). endsWith (WORD_TERMINATION)) {positions.add (node.getPosition ()); } עבור (int i = 0; i <node.getChildren (). size (); i ++) {positions.addAll (getPositions (node.getChildren (). get (i))); } עמדות החזרה; }

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

private String markPatternInText (StartPosition Integer, Model String) {String matchingTextLHS = fullText.substring (0, startPosition); מחרוזת matchingText = fullText.substring (startPosition, startPosition + pattern.length ()); מחרוזת matchingTextRHS = fullText.substring (startPosition + pattern.length ()); החזר matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS; }

כעת, יש לנו את שיטות התמיכה שלנו מוכנות. לָכֵן, אנו יכולים להוסיף אותם לשיטת החיפוש שלנו ולהשלים את ההיגיון:

public list searchText (תבנית מחרוזת) {List result = new ArrayList (); צמתים ברשימה = getAllNodesInTraversePath (תבנית, שורש, שקר); אם (nodes.size ()> 0) {Node lastNode = nodes.get (nodes.size () - 1); אם (lastNode! = null) {מיקומי רשימה = getPositions (lastNode); עמדות = positions.stream () .sorted () .collect (Collectors.toList ()); positions.forEach (m -> result.add ((markPatternInText (m, דפוס)))); }} להחזיר תוצאה; }

8. בדיקות

עכשיו שיש לנו את האלגוריתם שלנו, בואו נבדוק אותו.

ראשית, בואו נשמור טקסט ב SuffixTree:

SuffixTree suffixTree = SuffixTree חדש ("האוואנבאנה"); 

לאחר מכן, בואו נחפש דפוס תקף א:

התאמות רשימה = suffixTree.searchText ("a"); matches.stream (). forEach (m -> LOGGER.info (m));

הפעלת הקוד נותנת לנו שישה התאמות כצפוי:

h [a] vanabanana hav [a] nabanana havan [a] banana havanab [a] nana havanaban [a] na havanabanan [a]

הבא, בואו חפש תבנית חוקית אחרת nab:

התאמות רשימה = suffixTree.searchText ("nab"); matches.stream (). forEach (m -> LOGGER.info (m)); 

הפעלת הקוד נותנת לנו התאמה אחת בלבד כצפוי:

hava [nab] anana

לבסוף, בואו חפש תבנית לא חוקית לְנַדְנֵד:

התאמות רשימה = suffixTree.searchText ("לנדנד"); matches.stream (). forEach (m -> LOGGER.info (m));

הפעלת הקוד לא נותנת לנו תוצאות. אנו רואים כי התאמות צריכות להיות מדויקות ולא חלקיות.

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

9. מורכבות זמן

בעת בניית עץ הסיומת לטקסט נתון באורך t, ה מורכבות הזמן היא O (t).

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

10. מסקנה

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

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

כמו תמיד, קוד המקור עם הבדיקות זמין ב- GitHub.