Skift eller algoritme

Original: http://www-igm.univ-mlv.fr/~lecroq/string/node6.html

Hovedtræk
bruger bitvise teknikker;
effektiv, hvis længde mønster er ikke længere end hukommelsen ord størrelsen af maskinen;
forbehandling fase i O (m + sigma) tid og rum kompleksitet;
søger fase i O (n) tid kompleksitet (uafhængig af alfabetet størrelse og længden mønsteret);
tilpasser nemt til omtrentlige streng matchning.

Beskrivelse
Shift Eller algoritmen bruger bitvise teknikker. Lad R være en smule vifte af størrelse m. Vector Rj er værdien af array R efter teksttegn y [j] er blevet behandlet (se figur 5.1). Den indeholder informationer om alle kampe i præfikser af x, der ender på position j i teksten til 0 <i Leq m-1:

figure 5.1

Vektoren Rj + 1 kan beregnes efter Rj som følger. For hver Rj [i] = 0:

og 

Hvis Rj + 1 [m-1] = 0 derefter en komplet kamp kan rapporteres.
Overgangen fra Rj til Rj + 1 kan beregnes meget hurtigt, som følger: For hvert ci Sigma, lad Sc være lidt vifte af størrelse m således at: til 0 Leq i <m-1, Sc [i] = 0 IFF x [I] = c.
Array Sc betegner positionerne af den karakter ci mønstret på x. Hver Sc kan forbehandles før søgningen. Og beregningen af Rj + 1 reducerer til to operationer, shift og eller: Rj + 1 = SHIFT (RJ) eller Sy [j + 1]
Antages det, at længden mønster er ikke længere end hukommelsen ord møllestørelsen, tid og rum kompleksitet forbehandling fase er O (m + sigma).
Tidskompleksiteten af den søgende fase er O (n), således uafhængige af alfabetet størrelse og længden mønster.

Den C-kode

 int preSo(char *x, int m, unsigned int S[]) { 
    unsigned int j, lim; 
    int i; 
    for (i = 0; i < ASIZE; ++i) 
      S[i] = ~0; 
    for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) { 
      S[x[i]] &= ~j; 
      lim |= j; 
    } 
    lim = ~(lim>>1); 
    return(lim); 
  } 

  void SO(char *x, int m, char *y, int n) { 
    unsigned int lim, state; 
    unsigned int S[ASIZE]; 
    int j; 
    if (m > WORD) 
      error("SO: Use pattern size <= word size"); 

    /* Preprocessing */ 
    lim = preSo(x, m, S); 

    /* Searching */ 
    for (state = ~0, j = 0; j < n; ++j) { 
      state = (state<<1) | S[y[j]]; 
      if (state < lim) 
        OUTPUT(j - m + 1); 
    } 
  } 

Eksemplet
Søgning fase

Shift Or search table
Som R12 [7] = 0 betyder det, at en forekomst af x er fundet ved position 12-8 + 1 = 5.
Beklager den nye eksempel ikke er klar ... Se Java-applet.

referencer
BAEZA-YATES, RA, Gonnet, GH, 1992, En ny tilgang til tekst søgning, Meddelelser fra ACM. 35 (10): 74-82.
BAEZA-YATES R., NAVARRO G., RIBEIRO-NETO B., 1999, indeksering og søgning, i Modern Informationssøgning, kapitel 8,
side 191-228, Addison-Wesley.
CROCHEMORE, M., LECROQ, T., 1996, Mønster matchende og tekst komprimering algoritmer, i CR
 Computer Science and Engineering Handbook,
 A. Tucker ed., Kapitel 8, side 162-202, CRC Press Inc., Boca Raton, FL.
WU, S., Manber, U., 1992, Fast tekst søger tillader fejl, Commun. ACM. 35 (10): 83-91.

Comments are closed.