9.7 התאמת מחרוזות

מבנה נתונים ואלגוריתמים

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

אם נאמר שהטקסט שבו מחפשים את התבנית הוא מחרוזת תווים המיוצגת על ידי המערך T[1...n], והתבנית שאת מופעיה מחפשים היא מחרוזת תווים המיוצגת על ידי המערך P[1...m], כאשר m ≤ n, אזי נאמר שהתבנית P מופיעה בטקסט T עם היסט בגודל s אם מתקיים T[s+1...s+m] = P[1...m] עבור 0 ≤ s ≤ n.

האלגוריתם הנאיבי

האלגוריתם הנאיבי בודק האם מתקיים התנאי T[s+1...s+m] = P[1...m], עבור כל אחד מערכי s האפשריים. השגרה הבאה מתארת אלגוריתם כזה:

StringMatcher(T,P)
{

n <- length[T]

m <- length[P]

for s <- 0 to n- m

do if T[s+1...s+m]=P[1...m

then print "The pattern occurs with shift" s

}

שגרה זו רצה במקרה הגרוע ביותר בזמן של θ((n-m+1)m). מיד נראה כי זמן זה ניתן לשיפור באופן משמעותי.

אלגוריתם נאיבי זה אינו יעיל מאחר שהוא אינו מנצל את המידע שמתקבל עבור ערך אחד של s, כאשר הוא בודק

את ערכי s הבאים.

אלגוריתם הגישה הדינאמית

כפי שכבר ראינו, השימוש בידע שנרכש בשלבים מוקדמים יותר של האלגוריתם, מאפיין את הגישה הדינאמית. אלגוריתם התאמת מחרוזות של קנות', מוריס ופראט (Knuth, Morris & Pratt) משיג זמן ריצה של O(n+m) בזכות שימוש במערך Π(1...m) המאחסן מידע שכבר נצבר. להלן פסאודו-קוד של אלגוריתם זה:

KMP-Matcher(T,P)

{

n <- length[T]

m <- length[p]

П <- Compute-Function(P)

q <- 0

for i <- 1 to n

do while q>0 and P[q+1]≠T[i]

do q <- П[q]

if P[q+1]=T[i]

then q <- q+1

if q=m

then print "The pattern occurs with shift" i-m

q <- П[q]

}

Compute-Function(P)

{

m <- length[P]

П[1] <- 0

K <- 0

for q <- 2 to m

do while k>0 and P[k+1]≠P[q]

do k <- П[k]

if P[k+1]=P[q]

then k <- k+1

П[q] <- k

return П

}

כפי שניתן לראות, השגרה KMP-Matcher קוראת לשגרת עזר בשם Compute-Function, המחשבת את תוכן המערך Π.

מושגים

אלגוריתם התאמת מחרוזות של קנות', מוריס ופראט

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

המשך ל: גרפים חזור ל: תוכן עניינים