Strängmatchning

Anders Sandberg, efter förlaga av Hasse Haitto

Givet: ett mönster P och en strän S. Mönsterlängden |P| betecknas m, stränglängden |S| med n.

Rakt Fram

Jämför P och S successivt från vänster, vid olikhet flytta fram P ett steg åt höger och börja jämföra från början av P igen.

Om S=which-finally-halt-at-that-point och P=at-that 

which-finally-halt-at-that-point
a                                   
 a                                
  a                                
   a                            
    a                           
     a                          
      a                         
       a                        
        a                       
         at                     
          a                     
           a                    
            a                   
             a                  
              a                 
               at               
                a               
                 a              
                  a             
                   at-that
28 jämförelser.

RF fungerar bra om m är litet (mindre än 4) eller n är ungefär m.

Knuth-Morris-Pratts Algoritm

KMP använder en vektor (eller tabell) kallad next, som räknas ut innan matchningen påbörjas (se proceduren initnext i Sedgewicks artikel). Next[j] säger vilket tecken i mönstret som ska jämföras när ett tecken i strängen inte matchar tecken j i mönstret. Jämförelsen sker från vänster till höger och har fördelen att man aldrig behöver backa, dvs läsa in samma tecken i strängen två gånger. Man går alltså framåt i strängen endast i fallet att hela mönstret mismatchar.

Exempel: Nextvektorn för mönstret abracadabra

Nextvektorn kan tas fram för hand: vid mismatch med p[j] matcha p[1..j-1] mot sig själv och låt
next[j] = 1+längden av matchande delsträng.
Tecknet * visar aktuell mismatch, versaler den matchande delsträngen. 
j   abracadabra   next[j]
1                  0 (per def)
2   a*             1       
3   ab*            1       
4   abr*           1       
5   abrA*          2       
6   abrac*         1       
7   abracA*        2       
8   abracad*       1       
9   abracadA*      2       
10  abracadAB*     3        
11  abracadABR*    4

Matchning

S= "abrada... abracabracadabra" (den förvirrade trollkonstnärens formel) P = abracadabra 
abrada... abracabracadabra
abrac                        next[5]=2
    b                        next[2]=1
     ab                      next[2]=1
      a                      next[1]=0
       a                     next[1]=0
        a                    next[1]=0 
         a                   next[1]=0
          abracad            next[7]=2
                bracadabra   match!

Förbättringar

Vid mismatch så flyttas mönsterpekaren bakåt i mönstret för att utföra nästa jämförelse. Algoritmen är "dum" på så sätt att vid mismatch i fallen j=4,6,8,9, 10 och 11 så råkar det vara samma bokstav i den nya positionen som den som redan mismatchat. Man kan undvika denna onödiga jämföresle genom att direkt hoppa till läget next[next[j]]. Det görs i den modifierade versionen av KMP-algoritmen.

KMP fungerar bäst i texter med alfabetets storlek ungefär lika med n.

Boyer-Moores Algoritm

Man jämför från slutet av mönstret, i riktning från höger till vänster. Vid sökningen använder man sig av två tabeller, d1 och d2, och väljer det resultat som är bäst.

Bruksanvisning

Vid mismatch ger d1-tabellvärdet för tecknet i strängen där mismatch uppstod, medan d2-värdet bestäms av mönsterpekaren j:s läge i mönstret. Tabellerna används så att mönsterpekaren stegas åt höger till slutet av mönstret, och sedan "släpar" mönsterpekaren med sig mönstret tills man gått det antal steg som tabellen anger.

Exempel

P = AT-THAT
S = WHICH-FINALLY-HALT-AT-THAT-POINT
(längd m=7 och n=32 respektive)
AHT-Övr
d112047

AT-THAT
d1111098741

* markerar var mönsterpekaren är när en mismatch detekteras, versaler anger jämförda bokstäver. Varje rad motsvarar en flyttning via tabellerna. 

WHICH-FINALLY-HALT-AT-THAT-POINT
      *
at-thaT      *                       F i d1 ger 7 steg
       at-thaT  *                    - i d1 ger 4 steg
           at-thAT*                  A i d2 ger 4 steg
              at-tHAT                H i d2 ger 7 steg
                   AT-THAT           match
Totalt 14 jämförelser.

Hur man får fram d1

Ta fram uppsättningen av tecken som ingår i mönstret: här har vi A, H, T och -. Ställ upp dessa i en tabellrubrik och lägg till en rubrik Övr. för eventuella andra tecken som kan finnas i den undersökta strängen. Sätt d1 värdet av Över till m.

För varje tecken i d1 sätt tabellvärdet till:

d1[j]=m-läget i mönstret för den "högraste" förekomsten av tecknet. 
1234567
AT-THAT
A, H, T och - förekommer sist i mönstret i lägena 6, 5, 7 resp. 3 vilket ger d1 värden 1, 2, 0 och 4.

Hur man får fram d2

Tabellen d2 anger för varje teckenposition största möjliga flyttning om det bakifrån stämmer ända fram till mismatchläget. Vid mismatch stegas mönsterpekaren åt höger till slutet av mönstret; därefter "släpas" mönstret framåt med kunskap om de matchande tecknen. Man bygger upp tabellen från höger till vänster, från j=m ned till j=1. Man har en allt längre delsträng (av längden m-j när man befinner sig vid tecken j) att matcha.

Versala tecken har blivit jämförda, * anger mönsterpekaren och X ett tecken som mismatchar. Raden ovanför mönstret representerar en tänkt text man arbetar mot. 

      *
   ...X...
at-thaT        j=7. Mismatch vid T: flytta 1 steg, ger:
       *        
 at-that

     *
  ...XT..
at-thAT        j=6. Match för T: flytta 4 steg, ger:
         *        
   at-that

    *
 ...XAT.
at-tHAT        j=5. Match för AT: flytta 7 steg, ger:
           *        
     at-that

   *
...XHAT
at-THAT        j=4. Match för HAT: flytta 8 steg, ger:
           *        
     at-that

  *
..XTHAT
at-THAT        j=3. Match för THAT: flytta 9 steg, ger:
           *        
     at-that

 *
.X-THAT
at-THAT        j=2. Match för -THAT: flytta 10 steg, ger:
           *        
     at-that

*
XT-THAT
at-THAT        j=1. Match för T-THAT: flytta 11 steg, ger:
           *        
     at-that

Förbättringar

d2 är trasslig att räkna ut, man kan nöja sig med d1, och får då Horsepools algoritm. Den går aldrig bakåt (som KMP) och är hyfsat snabb.

Källa

Boyer, Robert S & Moore, J. Strother: "A Fast String Searching Algorithm" Communications of the ACM, Vol 20, Number 10, October 1977

Se också http://www.ctc.dcu.ie/ctcweb/courses/algorithms/course/string.html för en genomgång av flera strängmatchningsalgoritmer.