אלגוריתמים - pattern matching

[carlos22]

אלגוריתמים - pattern matching

נתונה מחרוזת של ביטים S ותבנית P שאותה צריך לחפש בS כאשר P מורכבת מ 0 1 או * כאשר מופיעה * ב P לא משנה מה מופיע ב S וצריך למצוא את המופעים של P ב S . באלגוריתם הרגיל של מציאת תבנית היו מוגדרות שתי סדרות של -1 ו 1 כאשר במקום המקביל במחרוזת המתאימה לכל סדרה הופיע 0 או 1 בהתאמה .. ובסדרה המתאימה לתבנית בכל מקום שהוא מסמן מקום הגדול מאורך התבנית היה 0. לאחר הפעלת קונבולוציה על שתי הסדרות במקומות שמתאימים למקום ב S בו מתחילה P שלמה היה האורך של P .. חשבתי באלגוריתם לבעיה החדשה להגדיר 0 במקום בו יש * בP ו -1 ו1 כמו בבעיה הקודמת ואז לחפש בקונבולוציה מקומות בהם יש את אורך התבנית פחות מספר ה-*אבל זה יוצר בעיה עם המקומות הגדולים מאורך המחרוזת .. אם יוגדר שם מספר אחר לדוג' 2 אז בקונבולוציה יופיע ערך חסר משמעות מכיוון ש2 יוכפל ב1 או -1 בהתאם למקום המקביל בS .. אני בכלל בכיוון ?

 

[vinney]

אתה לא כל כך ברור

מה בדיוק האלגוריתם שאתה מדבר עליו? מה מחליף הסימן "*"?

 

[carlos22]

* משמש כ dont care

אם P = 10* zz אז בכל מקום ב S שתופיע תת המחרוזת 100 או 101 נחשיב את זה כהתאמה אותו דבר עם * באמצע מילה 0*0 = 010 0*0 = 000

 

[vinney]

ברור

זאת אומרת ש* משמש כתחליף לביט בודד בדיוק (זאת בניגוד למשל ל* בpattern matching של מחרוזות שמשמש כtoken שמחליף מחרוזת מכל אורך או תוכן). אם כך, הפתרון הטריויאלי יהיה להריץ את החיפוש כשבכל איטרציה של הרצה אתה מחליף * ב1 או 0 בהתאמה (מה שייצר לך סיבוכיות של N^2 פעמים הסיבוכיות המקורית, שזה כמובן לא טוב). עכשיו, על איזה אלגוריתם אתה מדבר?

 

[carlos22]

הבנתי את הפתרון בנתיים אני חושב לפחות.. זה מה

שהגעתי אליו.. כאשר אין * אלא גם P היא רק ביטים ניתן להגדיר מעין סדרות מציינות עבור שתי המחרוזות. אם P=P0,P1,P2...Pm ו S=S0,S1,S2...Sn n>m . נגדיר סדרה מציינת לP אשר במקום ה i מקבלת אחד אם Pi הוא 1 ו -1 אם Pi הוא 0 אותו דבר עבור S בכל מקום m<i נגדיר בסדרה המציינת של P את האבר כ 0. עכשיו אם נחשב את הקונבולוציה של שתי הסדרות נקבל שבמקום הi יש את גודל החפיפה בין P למחרוזת שהתחילה באינדקס i ובמקומות שבהם יש ערך השווה בערכו לאורך של P נקבל שיש חפיפה מלאה ואלה המקומות שחיפשנו. (אמנם הקונבולוציה תחפש את המחזרות הפוך אבל אפשר מראש פשוט להפוך את P). בבעיה החדשה יש את תו *. אז חשבתי לסמן אותו ב סדרה המצינת של P כ 0 ואז לחפש אינדקסים בקונבולוציה שבהם יש ערך ששוה לאורך של P פחות מספר ה* שיש בו. בהתחלה חשבתי שאני אצטרך לסמן את המקומות הגדולים מm באיזהשהו מספר אחר כדי להבחין מתי אני מסיים לעבור על P אבל 0 לכל מקום מחוץ לטווח גם עובד..