Understanding Boyer-Moore Algorithm

Question

Understanding Boyer-Moore Algorithm

#1 da (2 voti)

4

Modifica: ho trovato la pubblicazione originale . Mi sembra che l'originale non abbia un l′(i) . Ma potrei sbagliarmi perché la definizione di rpr(i) è così oscura per me. Non sono sicuro di come ci si avvale quando rpr(i) è negativo e cosa accade quando non viene trovata una tale ripetizione.

Sto cercando di implementare l'algoritmo di Boyer-Moore in base a questo . Non sono sicuro se faccia parte di un libro o se siano solo alcune note universitarie. Secondo questo (poco prima Theorem 0.2.4 ):

Definition: Let l′(i) denote the length of the largest suffix of P[i..n] that is also a prefix of P, if one exists. If none exists, then let l′(i) be zero.

E poi continua da qualche altra parte con:

If, during the search stage, a mismatch occurs at position i − 1 of P and L′(i) > 0, then the good suffix rule shifts P by n − L′(i) places to the right, so that the L′(i) - length prefix of the shifted P aligns with the L′(i) - length suffix of the unshifted P. In the case that L′(i) = 0, the good suffix rule shifts P by n − l′(i) places.

Note that the rules work correctly even when l′(i) = 0.

Fai attenzione che gli indici sono basati su 1.

La parte con cui ho problemi è grassetto . Ad esempio se abbiamo il pattern abcde per cui l′(5) = 0 e se testiamo questo contro abcze ; la prima mancata corrispondenza si verifica in d rispetto a z . Ora che l′(5) è 0 , dobbiamo spostarlo n - l′(5) caratteri a destra e quindi abbiamo perso la possibilità di trovare la corrispondenza. Modifica: SBAGLIATO. Dovrebbe davvero spostare n - l′(5) caratteri perché non c'è z o e nel modello prima del carattere che stiamo controllando.

Quindi mi chiedo se mi manca qualcosa o no. Devo ignorare l′(i) quando è zero?

algorithms strings

posta mostruash 02.10.2014 - 19:19

fonte

1 risposta

Leggi altre domande sui tag algorithms strings

Come gestire il codice di programmazione delle coppie per verificare l'identificazione dell'utente? Come definire il percorso di movimento di un oggetto su una superficie dell'altro?

score 2 · Accepted Answer

Quindi, dopo aver lavorato un po 'di più sull'algoritmo, ho funzionato. La risposta alla mia domanda è:

Dovrebbe essere spostato n - l′(i) caratteri a destra anche quando l′(i) = 0 .

Quando l′(i) è zero, ciò significa quanto segue:

L′(i) è zero. Quindi non è stata trovata alcuna sottostringa ricorrente a sinistra che abbia un carattere precedente diverso. Per esempio:
```
mismatch:               v -----
 pattern: a b c Z a b c Z a b c
   index: 1 2 3 4 5 6 7 8 9 0 1
          0                 1
```

Si verifica una mancata corrispondenza su Z . C'è una sottostringa di ripetizione abc a sinistra, ma inizia anche con Z . Quindi non va bene. L′(9) è 0 .

In questo caso, abc corrisponde al prefisso dell'intero modello, abc . l′(9) = 3 che è la lunghezza della corrispondenza del prefisso del substrato più lunga.

n - l′(9) = 11 - 3 = 8 turni, continuiamo a controllare pattern[1..3] rispetto a abc già presente nel testo originale.

Il pattern non ha un prefisso che corrisponde alla sottostringa già abbinata finora.

Quindi è impossibile trovare una corrispondenza a meno che non spostiamo n - l′(i) = n caratteri a destra. Non sono ancora sicuro di come la pubblicazione originale gestisca il caso quando L′(i) è zero però.