שימוש באינדקס אוף כדי למצוא את כל המופעים של מילה במחרוזת
1. סקירה כללית
המטלה של חיפוש דפוס תווים, או מילה, במחרוזת טקסט גדולה יותר נעשית בתחומים שונים. בביואינפורמטיקה, למשל, ייתכן שנצטרך למצוא קטע DNA בכרומוזום.
בתקשורת עורכים מאתרים ביטוי מסוים בטקסט רב. מעקב אחר נתונים מגלה הונאות או דואר זבל על ידי חיפוש מילים חשודות המוטמעות בנתונים.
בכל קונטקסט, החיפוש כה ידוע ומרתיע מטלה שהוא מכונה בפי העם "המחט בבעיית ערמת שחת". במדריך זה נדגים אלגוריתם פשוט המשתמש ב- indexOf (מחרוזת str, int fromIndex) שיטת Java חוּט בכיתה כדי למצוא את כל המופעים של מילה בתוך מחרוזת.
2. אלגוריתם פשוט
במקום פשוט לספור את המופעים של מילה בטקסט גדול יותר, האלגוריתם שלנו ימצא ויזהה כל מיקום בו קיימת מילה ספציפית בטקסט. הגישה שלנו לבעיה קצרה ופשוטה כך:
- החיפוש ימצא את המילה אפילו בתוך מילים בטקסט. לכן, אם אנו מחפשים את המילה "מסוגל", אנו נמצא אותה ב"נוח "וב"טאבלט".
- החיפוש יהיה חסר רישיות.
- האלגוריתם מבוסס על הגישה לחיפוש מחרוזות נאיבי. המשמעות היא שמכיוון שאנו נאיביים לגבי אופי הדמויות במילה ומחרוזת הטקסט, נשתמש בכוח גס כדי לבדוק בכל מיקום הטקסט מופע של מילת החיפוש.
2.1. יישום
כעת, לאחר שהגדרנו את הפרמטרים לחיפושנו, בואו נכתוב פתרון פשוט:
מחלקה ציבורית WordIndexer {public list findWord (String textString, String word) {List indexes = new ArrayList (); מחרוזת lowerCaseTextString = textString.toLowerCase (); מחרוזת lowerCaseWord = word.toLowerCase (); אינדקס int = 0; ואילו (index! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index); אם (אינדקס! = -1) {indexes.add (index); אינדקס ++; }} מחזירים אינדקסים; }}2.2. בודקים את הפתרון
כדי לבדוק את האלגוריתם שלנו, נשתמש בקטע מקטע מפורסם מהמלט של שייקספיר ונחפש את המילה "או", המופיעה חמש פעמים:
@Test הציבור בטל givenWord_whenSearching_thenFindAllIndexedLocations () {String theString; WordIndexer wordIndexer = WordIndexer חדש (); theString = "להיות, או לא להיות: זו השאלה:" + "האם זה יותר אציל במוח לסבול" + "מתלים וחצים של הון מקומם," + "או לקחת נשק נגד ים של צרות, "+" ועל ידי התנגדות לשים קץ להן? למות: לישון; "+" לא יותר; ועל ידי שינה לומר שאנחנו מסיימות "+" כאב הלב ואלף הזעזועים הטבעיים "+" הבשר הזה הוא היורש ל, 'זו השלמה "+" באדיקות להיות רצויה. למות, לישון; "+" לישון: הכניסה לחלום: כן, יש את השפשוף: "+" כי בשנת השינה של המוות מה החלומות עשויים לבוא,"; רשימה expectResult = Arrays.asList (7, 122, 130, 221, 438); רשימת actualResult = wordIndexer.findWord (המחרוזת, "או"); assertEquals (expectResult, actualResult); }כאשר אנו עורכים את הבדיקה שלנו, אנו מקבלים את התוצאה הצפויה. חיפוש "או" מניב חמישה מופעים המוטבעים בדרכים שונות במחרוזת הטקסט:
מדד 7, במדד "או" במדד 122, במדד "הון" של 130, במדד "או במאד 221, במדד" עוד "של 438, ב"עבור"במונחים מתמטיים, לאלגוריתם יש סימון ביג-או של O (m * (n-m)), איפה M הוא אורך המילה ו נ הוא אורך מחרוזת הטקסט. גישה זו עשויה להתאים למחרוזות טקסט בערימת שחת של כמה אלפי תווים, אך תהיה איטית באופן בלתי נסבל אם יש מיליארדי תווים.
3. אלגוריתם משופר
הדוגמה הפשוטה שלעיל מדגימה גישה נאיבית, כוח אנושי לחיפוש מילה נתונה במחרוזת טקסט. ככזה, זה יעבוד עבור כל מילת חיפוש וכל טקסט.
אם נדע מראש שמילת החיפוש אינה מכילה דפוס חוזר של תווים, כמו "aaa", אז נוכל לכתוב אלגוריתם מעט יעיל יותר.
במקרה זה, אנו יכולים להימנע בבטחה מביצוע הגיבוי כדי לבדוק מחדש כל מיקום במחרוזת הטקסט כמיקום התחל פוטנציאלי. אחרי שאנחנו מבצעים את השיחה אל אינדקס של( ) בשיטה, פשוט נעבור למיקום רק לאחר סיום ההתרחשות האחרונה שנמצאה. הצבוט הפשוט הזה מניב תרחיש הטוב ביותר של עַל).
בואו נסתכל על הגרסה המשופרת הזו של הקודמת findWord () שיטה.
רשימה ציבורית findWordUpgrade (String textString, String word) {List indexes = new ArrayList (); פלט StringBuilder = StringBuilder חדש (); מחרוזת lowerCaseTextString = textString.toLowerCase (); מחרוזת lowerCaseWord = word.toLowerCase (); int wordLength = 0; אינדקס int = 0; ואילו (אינדקס! = -1) {index = lowerCaseTextString.indexOf (lowerCaseWord, index + wordLength); // שיפור קל אם (index! = -1) {indexes.add (index); } wordLength = word.length (); } אינדקסים להחזיר; }4. מסקנה
במדריך זה הצגנו אלגוריתם חיפוש שאינם רגישים לאותיות רישיות כדי למצוא את כל הווריאציות של מילה במחרוזת טקסט גדולה יותר. אבל אל תיתן לזה להסתיר את העובדה שג'אווה חוּט מעמד' אינדקס של() השיטה מטבעה תלויה באותיות רישיות והיא יכולה להבחין בין "בוב" ל"בוב ", למשל.
לְגַמרֵי, אינדקס של() היא שיטה נוחה למציאת רצף תווים קבור במחרוזת טקסט מבלי לבצע קידוד למניפולציות של תת-משנה.
כרגיל, בסיס הקוד השלם של דוגמה זו הסתיים ב- GitHub.
