Algoritmo de Boyer-Moore-Horspool

El algoritmo de Boyer-Moore-Horspool se utiliza para encontrar eficientemente patrones en una secuencia. Es fácil de implementar y utiliza un preprocesamiento del texto a buscar, compara de derecha a izquierda y realiza la búsqueda del patrón en un tiempo O(MN). siendo M la longitud del texto. Es considerado el mejor algoritmo de búsqueda de un patrón en un texto en aplicaciones usuales.

En caso de una no ocurrencia o una ocurrencia total del patrón se usa una función preprocesada para saltar:

1. Salto del mal carácter(bad-character shift) (o salto de ocurrencia).

Horspool propuso utilizar solamente el salto del mal carácter para calcular los saltos en el algoritmo de Boyer-Moore.

El salto del mal carácter consiste en:

1. Alinear cada carácter del alfabeto Σ con la ocurrencia más a la derecha en x[0, …, m-2].
2. Si el carácter no ocurre en el patrón x, la no ocurrencia de x puede incluir el carácter, y alinearlo en el lado más izquierdo del patrón.
3. Esta operación (usada en el algoritmo BM) no es muy eficiente para alfabetos pequeños, pero cuando el alfabeto es grande comparado con la longitud del patrón llega a ser muy útil.

Se calcula el preprocesamiento del patrón de la siguiente forma:

1. Se calcula la distancia mínima entre el último carácter y la ocurrencia de cada carácter del alfabeto de la hilera principal.
   

Para la búsqueda:

1. Consiste en la comparación de cada carácter del texto con las posiciones del patrón en el orden m-1, 0, 1, 2, …, y m-2, si se da una ocurrencia del patrón o no.
2. Cuando se encuentra una no ocurrencia, al hacer la primera comparación entre el patrón y el texto, el salto se calcula bmBc[c], donde c es el carácter del texto.
3. Cuando se encuentra una no ocurrencia o una ocurrencia total, al hacer las siguientes comparaciones entre el patrón y el texto, el salto se calcula bmBc[c], donde c es el carácter del patrón.

Ref:

UCR –ECCI
CI-2414 Recuperación de Información
Prof. M.Sc. Kryscia Daviana Ramírez Benavides

Implementación en Delphi:

function search(pat: string; text: string): integer;
var
i, j, k, m, n: integer;
skip: array [0..MAXCHAR] of integer;
found: boolean;
begin
found := FALSE;
search := 0;
m := length(pat);
if m=0 then
begin
search := 1;
found := TRUE;
end;
for k:=0 to MAXCHAR do
skip[k] := m;   {*** Preprocessing ***}
for k:=1 to m-1 do
skip[ord(pat[k])] := m-k;
k := m;
n := length(text);            {*** Search ***}
while not found and (k <= n) do begin i := k; j := m; while (j >= 1) do
begin
if text[i] <> pat[j] then
j := -1
else
begin
j := j-1;
i := i-1;
end;
if j = 0 then
begin
search := i+1;
found := TRUE;
end;
k := k + skip[ord(text[k])];
end;
end;
end;

Si queremos una medida, en millonésimas de segundo, del tiempo consumido por un algoritmo, podemos utilizar lo siguiente:

const   UnMillon = 1000000;
 var    Frecuencia, X, Y: Int64;
 begin
 QueryPerformanceFrequency(Frecuencia);
 QueryPerformanceCounter(X);
 Algoritmo;
 QueryPerformanceCounter(Y);
 ShowMessage(FormatFloat('0,', (Y - X) * UnMillon div Frecuencia));
 end;