streamalism.org

1. הקדמה

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

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

2. אלגוריתמים

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

2.1. שיטות עוזר

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

ציבורי סטטי ציבורי ארוך getBiggerPrime (int m) {BigInteger prime = BigInteger.probablePrime (getNumberOfBits (m) + 1, אקראי חדש ()); החזר prime.longValue (); } פרטי סטטי int getNumberOfBits (int מספר) {return Integer.SIZE - Integer.numberOfLeadingZeros (number); } 

2.2. חיפוש טקסט פשוט

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

ציבורי סטטי ציבורי int simpleTextSearch (char [] תבנית, char [] טקסט) {int patternSize = pattern.length; int textSize = text.length; int i = 0; ואילו ((i + patternSize) = patternSize) מחזיר i; } i + = 1; } להחזיר -1; }

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

אם M הוא מספר האותיות בתבנית, ו נ הוא מספר האותיות בטקסט, מורכבות הזמן של אלגוריתמים אלה היא O (m (n-m + 1)).

התרחיש הגרוע ביותר מתרחש במקרה של חוּט עם הרבה התרחשויות חלקיות:

טקסט: baeldunbaeldunbaeldunbaeldun תבנית: baeldung

2.3. אלגוריתם רבין קארפ

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

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

הדבר החשוב בצעד העיבוד המוקדם הוא שמורכבות הזמן שלו היא O (m) והאיטרציה דרך הטקסט תימשך עַל) מה שנותן מורכבות זמן של אלגוריתם שלם O (m + n).

קוד האלגוריתם:

ציבורי סטטי ציבורי RabinKarpMethod (char [] דפוס, char [] טקסט) {int patternSize = pattern.length; int textSize = text.length; פריים ארוך = getBiggerPrime (patternSize); ארוך r = 1; עבור (int i = 0; i <patternSize - 1; i ++) {r * = 2; r = r% פריים; } ארוך [] t = חדש ארוך [textSize]; t [0] = 0; אצבע ארוכה = 0; עבור (int j = 0; j <patternSize; j ++) {t [0] = (2 * t [0] + text [j])% prime; pfinger = (2 * pfinger + דפוס [j])% ראש; } int i = 0; עבר בוליאני = שקר; int diff = textSize - patternSize; עבור (i = 0; i <= diff; i ++) {if (t [i] == pfinger) {עבר = נכון; עבור (int k = 0; k <patternSize; k ++) {if (טקסט [i + k]! = דפוס [k]) {עבר = שקר; לשבור; }} אם (עבר) {להחזיר i; }} אם (i <diff) {long value = 2 * (t [i] - r * text [i]) + text [i + patternSize]; t [i + 1] = ((ערך% פריים) + פריים)% פריים; }} להחזיר -1; }

בתרחיש הגרוע ביותר, מורכבות הזמן לאלגוריתם זה היא O (m (n-m + 1)). עם זאת, בממוצע יש לאלגוריתם הזה O (n + m) מורכבות זמן.

בנוסף, קיימת גרסת מונטה קרלו של האלגוריתם הזה שהיא מהירה יותר, אך היא עלולה לגרום להתאמות שגויות (תוצאות שגויות).

2.4 אלגוריתם קנוט-מוריס-פראט

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

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

יישום Java של אלגוריתם KMP:

ציבורי סטטי ציבורי KnuthMorrisPrattSearch (char [] דפוס, char [] טקסט) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int [] shift = KnuthMorrisPrattShift (תבנית); ואילו ((i + patternSize) = patternSize) להחזיר i; } אם (j> 0) {i + = shift [j - 1]; j = Math.max (j - shift [j - 1], 0); } אחר {i ++; j = 0; }} להחזיר -1; }

וכאן אנו מחשבים טבלת משמרות:

ציבורי סטטי ציבורי [] KnuthMorrisPrattShift (דפוס char]] {int דפוס גודל = דפוס.אורך; int [] shift = int int [patternSize] חדש; משמרת [0] = 1; int i = 1, j = 0; ואילו ((i + j)  0) {i = i + shift [j - 1]; j = Math.max (j - shift [j - 1], 0); } אחר {i = i + 1; j = 0; }}} משמרת חזרה; }

מורכבות הזמן של אלגוריתם זה היא גם כן O (m + n).

2.5. אלגוריתם פשוט בויר-מור

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

ציבורי סטטי ציבורי BoyerMooreHorspoolSimpleSearch (char [] דפוס, char [] טקסט) {int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; ואילו ((i + patternSize) <= textSize) {j = patternSize - 1; בעוד (טקסט [i + j] == תבנית [j]) {j--; אם (j <0) להחזיר i; } i ++; } להחזיר -1; }

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

2.6. אלגוריתם בויר-מור-הורספול

ישנן וריאציות רבות של יישום היוריסטי של האלגוריתם של בויר-מור, והפשוטה ביותר היא וריאציה של הורספול.

גרסה זו של האלגוריתם נקראת Boyer-Moore-Horspool, וריאציה זו פתרה את בעיית השינויים השליליים (אנו יכולים לקרוא על בעיית משמרת שלילית בתיאור האלגוריתם Boyer-Moore).

בדומה לאלגוריתם של בויר-מור, מורכבות הזמן בתרחיש הגרוע ביותר היא O (m * n) ואילו המורכבות הממוצעת היא O (n). השימוש בחלל אינו תלוי בגודל התבנית, אלא רק בגודל האלף-בית שהוא 256 מכיוון שזה הערך המרבי של תו ASCII באלפבית האנגלי:

int static public BoyerMooreHorspoolSearch (char [] pattern, char [] text) {int shift [] = new int [256]; עבור (int k = 0; k <256; k ++) {shift [k] = pattern.length; } עבור (int k = 0; k <pattern.length - 1; k ++) {shift [pattern [k]] = pattern.length - 1 - k; } int i = 0, j = 0; ואילו ((i + תבנית.אורך) <= טקסט.אורך) {j = תבנית.אורך - 1; ואילו (טקסט [i + j] == תבנית [j]) {j - = 1; אם (j <0) להחזיר i; } i = i + shift [טקסט [i + pattern.length - 1]]; } להחזיר -1; }

4. מסקנה

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

וכמו תמיד, ניתן למצוא את קוד המקור ב- GitHub.