BotonMenu
BotonIndice

Visita : http://www.conoce3000.com
Paypal : https://www.paypal.me/conoce3000/1

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.7. BÚSQUEDA DE CADENAS DE CARACTERES BOYER & MORE.
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.7. BÚSQUEDA DE CADENAS DE CARACTERES BOYER & MORE.
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.7. BÚSQUEDA DE CADENAS DE CARACTERES BOYER & MORE.

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Búsquedas de cadenas de caracteres Boyer & More.

Para encontrar un texto dentro de una cadena de caracteres el algoritmo más usado es el de Boyer Moore. Usualmente se conoce como patrón al texto que se busca dentro de una cadena de caracteres. El algoritmo Boyer & Moore tiene muchas variantes, explicare sólo él método simple que consiste en construir un arreglo al que se le llamará abecedario, que contendrá las posiciones o saltos a desplazar la búsqueda, cada vez que se encuentre una discrepancia entre el patrón y un carácter de la cadena de caracteres en donde se realiza la búsqueda. El abecedario debe tener todos los caracteres de la codificación que esté usando la cadena de caracteres en donde se realiza la búsqueda. Es decir si estamos usando unicodestring, entonces el abecedario debe ser de 65536 elementos (0.. 65535), pero si se usa ansistring entonces sólo debe ser de 256 elementos (0..255).

Para determinar los saltos o posiciones de búsqueda en el abecedario, se debe pre calcular el abecedario, primero colocando en todos los elementos la longitud del patrón. Tal como se muestra:

for i:= 0 to 65535 do abecedario[i]:=length(patron);

Y luego asignamos para un carácter del abecedario que coincida con un carácter del patrón, la longitud del patrón menos la posición del carácter dentro del patrón, del siguiente modo:

for i:=1 to length(patron)-1 do abe[ord(patron[i])]:=length(patron)-i;

Si un carácter del patrón no se encuentra en el abecedario entonces este tomará la longitud del patrón.

El algoritmo consiste en comparar de derecha a izquierda el patrón con la cadena de caracteres, empezando desde el inicio de la cadena de caracteres. Es decir se compara el último carácter del patrón con el correspondiente carácter en la cadena de caracteres en donde se busca el patrón; si los caracteres no coinciden, la búsqueda se desplaza hacia la derecha o adelante con el valor indicado por el abecedario correspondiente al carácter de la cadena de caracteres que no coincide con el patrón. A continuación el programa de ejemplo:


Descargar
{$codepage utf8}
Function BusquedaCadena(patron,cad:unicodestring; var pos:longword):boolean;
Var
  abecedario:array [0..65535] of word; //Todo el BMP UTF16
  i,j,k:longword; 
  c:Widechar;      
Begin 
   pos:=0;

   for i:= 0 to 65535 do abecedario[i]:=length(patron);
   for i:=1 to length(patron)-1 do abecedario[ord(patron[i])]:=length(patron)-i; 
   
   BusquedaCadena:=false;   
   i:=length(patron);    
   j:=i;
   k:=i;
   c:=cad[k];

   while (j>0) and (k<=length(cad)) do
     begin
       if patron[j] <> cad[i]
          then begin
                 //si hay discrepancia saltar segun abecedario 
                 k:=k+abecedario[ord(c)];        
                 i:=k;   
                 c:=cad[k];
                 j:=length(patron)
                end    
          else  begin  
                 //caso contrario comparar hacia atras.  
                  i:=i-1;j:=j-1
                end              
     End;

   if j=0 then begin
                pos:=i+1; BusquedaCadena:=true
           end;                       
End;       

Var cad,patron:unicodestring;
    pos:longword;
Begin
   cad:='Hola en japones se escribe asi: こんにちは '; 
   patron:='こんにちは';
   if BusquedaCadena(patron,cad,pos)
      then Writeln('Se encontro en : ',pos)
      else Writeln('no se encontro')       
End.
Código fuente 17: Primer algortimo Boyer & Moore.
Descargar

La función BusquedaCadena devuelve verdadero cuando encuentra lo que se buscaba, y la posición lo devuelve en el parámetro pos, cuando no encuentra nada devuelve el valor falso y en pos se devuelve 0 como un valor arbitrario.

La función BusquedaCadena tiene tres variables i,j y k que son las que realizan la búsqueda, la variable k es la que hace el recorrido y saltos por la cadena de caracteres y la variable j es la que hace el recorrido por el patrón. La variable i se usa para recorrer la cadena de caracteres cuando se hace la comparación sólo si el último carácter coincide con lo que se busca, y la variable i+1 contendrá la posición si el patrón es encontrado en la cadena de caracteres, y por último la variable c que es de tipo widechar, nos servirá para almacenar el carácter del siguiente salto, en caso este coincida con el último carácter del patrón.

El bucle While culminará cuando la variable j tenga el valor cero, que nos indica que encontró la posición del patrón en la cadena o cuando la longitud de la cadena de caracteres sea mayor o igual al valor de la variable k. Dentro del bucle while con la instrucción if se condiciona los recorridos, verificando si hay discrepancias. Si hay discrepancias entonces se da saltos hacia adelante con la variable k según el abecedario, y la variable j se inicializa a la longitud del patrón para realizar la búsqueda nuevamente, y cuando no hay discrepancias entonces se disminuyen las variables i y j, pero si no se encuentra una discrepancia entonces la variable j llegará a valer 0 y eso permitirá finalizar el bucle while principal, obteniéndose de ese modo la posición del patrón encontrado en la variable i+1.

Este algoritmo se puede mejorar separando en un procedimiento aparte el cálculo de los saltos o posiciones de búsqueda del abecedario. El algoritmo de Boyer Moore que se ha explicado en este capítulo, es más rápido cuando más grande es el patrón de búsqueda usado, para búsquedas pequeñas es recomendable el uso de la función pos. El siguiente programa de ejemplo muestra una comparación entre ambas funciones de búsqueda:


Descargar
{$codepage utf8}
Uses Sysutils;


Type Tabecedario=array [0..65535] of word;


Procedure IniciarAbecedario(patron:unicodestring;Var abecedario:Tabecedario);


Var i:longword;       
 Begin
   for i:=0 to 65535 do abecedario[i]:=length(patron);
   for i:=1 to length(patron)-1 do abecedario[ord(patron[i])]:=length(patron)-i; 
 End;
 
Function BusquedaCadena(patron,cad:unicodestring; var pos:longword;
                        abecedario:Tabecedario):boolean;
Var

  i,j,k:longword; 
  c:Widechar;     
Begin 

   
   BusquedaCadena:=false;   
   i:=length(patron);
   pos:=0;  
   j:=i;
   k:=i;   
   c:=cad[k];
   while (j>0) and (k<=length(cad)) do
     begin
       if patron[j] <> cad[i]
          then begin
                 //si hay discrepancia saltar segun abecedario 
                 k:=k+abecedario[ord(c)];        
                 i:=k;   
                 c:=cad[k];
                 j:=length(patron)
                end    
          else  begin   
                  //caso contrario comparar hacia atras.  
                  i:=i-1;j:=j-1
                end              
     End;
   if j=0 then begin
                pos:=i+1; BusquedaCadena:=true
           end;                       
End;       

Var cad1,cad2,cad,patron:unicodestring;
    i,n,posicion:longword;
    abecedario:Tabecedario;
    t1,t2:double; 
Begin
   
  setlength(cad1,20000000);  
  setlength(cad2,20000000);  
  randomize;
  for i:=1 to length(cad1) do
    begin
       n:=random(26)+96;    
       if n=96 then cad1[i]:=' '
               else cad1[i]:=Widechar(n)
    end;
  randomize;
  for i:=1 to length(cad2) do
    begin
          n:=random(26)+96;
          if n=96 then cad2[i]:=' '
                  else cad2[i]:=Widechar(n)
    end;

  cad:=cad1+' 1234567890123456789012345 '+cad2;
  patron:='1234567890123456789012345';

  Writeln('BusquedaCadena');
  t1:=time;
  IniciarAbecedario(patron,abecedario);
  if BusquedaCadena(patron,cad,posicion,abecedario)
     then Writeln('Se encontro en : ',posicion)
     else Writeln('no se encontro');       
  t2:=time;
  Writeln(FormatDateTime('hh:nn:ss:zzz',t2-t1));    	 
   
  Writeln('pos');
  t1:=time;   
  posicion:=pos(patron,cad);
  if posicion<>0 
     then Writeln('Se encontro en : ',posicion)
     else Writeln('no se encontro');
  t2:=time;
  Writeln(FormatDateTime('hh:nn:ss:zzz',t2-t1));    	   
End.
Código fuente 18: Comparacion funcion pos y Boyer & Moore.
Descargar

El programa anterior crea inicialmente una cadena de caracteres de 40000000 caracteres al azar, y casi al medio coloca la cadena de caracteres a buscar de 25 caracteres que son los números 1234567890123456789012345, siempre y cuando el patrón sea más grande los resultados de la función BusquedaCadena, serán más rápidos que la función pos, en caso contrario la funcion pos será siempre más rápido.




SIGUIENTE
SIGUIENTE
SIGUIENTE


 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.








PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.