Name
  • String
  • Substring
  • Search
Edit

Berry and Ravindran designed an algorithm which performs the shifts by considering the bad-character shift (see chapter Boyer-Moore algorithm) for the two consecutive text characters immediately to the right of the window.

The preprocessing phase of the algorithm consists in computing for each pair of characters (ab) with ab in Sigma the rightmost occurrence of ab in axb. For ab in Sigma

The preprocessing phase is in O(m+sigma2) space and time complexity.

After an attempt where the window is positioned on the text factor y[j .. j+m-1] a shift of length brBc[y[j+m],y[j+m+1]] is performed. The text character y[n] is equal to the null character and y[n+1] is set to this null character in order to be able to compute the last shifts of the algorithm.

The searching phase of the Berry-Ravindran algorithm has a O(mn) time complexity.


Main features:

  • hybrid of the Quick Search and Zhu and Takaoka algorithms;
  • preprocessing phase in O(m+2) space and time complexity;
  • searching phase in O(mn) time complexity.

Example:

Preprocessing phase

brBc table
The star (*) represents any character in Sigma \{A, C, G, T}.
brBc table used by Berry-Ravindran algorithm.

Searching phase

First attempt
GCATCGCAGAGAGTATACAGTACG
1234 
GCAGAGAG 

Shift by: 1 (brBc[G][A])

Second attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG 

Shift by: 2 (brBc[A][G])

Third attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG 

Shift by: 2 (brBc[A][G])

Fourth attempt
GCATCGCAGAGAGTATACAGTACG
 12345678 
 GCAGAGAG 

Shift by: 10 (brBc[T][A])

Fifth attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG 

Shift by: 7 (brBc[G][0])

Sixth attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG

Shift by: 10 (brBc[0][0])

The Berry-Ravindran algorithm performs 16 character comparisons on the example.

C