Busqueda rápida de una String dentro de un fichero  

Enviado Por: Radikal (Q3 Team)
Web : http://www.q3.nu
Email: radikal@q3.nu
Fecha: 20/01/04

Truco accedido 83 veces

 


Sirva este truco como ejemplo de rastreo rápido de un fichero usando lecturas a través de un Buffer para acelerar.
En concreto, en este ejemplo se trata de buscar la primera vez que una cadena aparece en un fichero (en el caso de que aparezca, claro), indicando su posición desde el principio del fichero.
Seria como hacer una búsqueda mediante un Pos(Subcadena,Cadena), salvo que en lugar de buscar en una cadena, podremos leer en un fichero de varios gigas, pero con la ventaja de no tener que cargarlo de golpe en memoria.
Para lograrlo, iremos cargando el fichero en un Buffer de memoria (que en el ejemplo es de 8 KBytes), trozo por trozo.
El proceso es como sigue:
  • Cargamos un trozo de 8 KBytes y buscamos dentro de el.
  • Si encontramos la cadena en ese trozo de 8 kBytes, acabamos y mostramos donde fué encontrada.
  • Si la cadena no fué encontrada en ese trozo, repetitemos el proceso, es decir, cargaremos un nuevo trozo y volveremos a buscar.
    Todo esto está muy bien, pero nos dejamos un pequeño detalle:
    ¿Que ocurre si la cadena está situada juuusto entre dos trozos de esos de 8 KBytes?... pues pasaria que nuestra búsqueda fallaría miserablemente :)
    Para evitarlo, basta con 'rebobinar' la Stream un trozo hacia atrás justo antes de leer el siguiente.
    En concreto, rebobinaremos tantos bytes como la longitud de la cadena buscada, asi nos aseguramos que la encontraremos aunque pille en medio de dos trozos.
    Fácilmente podría ser adecuada para, por ejemplo, contar las veces que se encuentra esa cadena dentro del fichero, para substituir una cadena por otra, para construirte tu propio comando Grep, etc, etc...
    Aqui está la función y un ejemplo de llamada, todo ello contenido en el OnClick de un TButton cualquiera:

     procedure TForm1.Button1Click(Sender: TObject);
     var
      EncontradaEn : integer;
    
    
      function BuscaStringEnFichero(const Fichero: string ;const Cadena: string):integer;
      { Busca la primera vez que la cadena 'Cadena' aparece dentro del fichero 'Fichero',
        devolviendo la posición (Offset) en la que se encuentra (contando desde el principio
        del fichero) o bien devuelve un -1 si la cadena no fué encontrada.
        It looks for the first time that the string ' Cadena' appears inside the file ' Fichero',
        returning the position (Offset) in the one that is (counting from the beginning
        of the file) or it returns a -1 if the string was not find
        Radikal Q3 para Trucomania}
    
      const
        {Leeremos de 8K en 8K
        We will read of 8K in 8K }
        CUANTOBUFFER = 8192;
      var
        Corriente  : TFileStream;
        Almacen    : String;
        Donde      : integer;
        Parar      : boolean;
        Posicion   : integer;
      begin
        SetLength(Almacen, CUANTOBUFFER);
        Corriente:=TFileStream.Create(Fichero,fmOpenRead OR fmShareDenyWrite);
        Result:=-1;
        try
          Corriente.Seek(0,soFromBeginning);
          Parar:=FALSE;
          repeat
            {Guardamos el inicio de lo leido, antes de leer
            We keep the beginning of that read, before reading }
            Posicion:=Corriente.Position;
    
            {Parar:=TRUE cuando no haya mas que leer o bien hayamos encontrado la cadena
             Parar(stop):=TRUE when there is not but to read or we have found the string }
            Parar:= ( Corriente.Read(Almacen[1],CUANTOBUFFER) < CUANTOBUFFER );
            {Buscamos la cadena en el Almacen leido
           We look for the string in the read Almacen }
            Donde:=Pos(Cadena, Almacen);
    
            If Donde <> 0 then begin
              Result:=Donde+Posicion;
              {Si la hemos encontrado... tambien paramos
              If we have found it... we also stopped }
              Parar:=TRUE;
            end else begin
              {Rebobinamos un poco por si la cadena estuviera en medio de dos
               páginas de CUANTOBUFFER de longitud:
              We rewind a little for if the string was in a middle of two
               pages of CUANTOBUFFER of longitude }
              Corriente.Seek(Length(Cadena),soFromCurrent);
            end;
          until Parar;
        finally
          Corriente.Free;
        end;
      end;
    
     begin
      {Ejemplo de uso
      Use example }
    
      {Ejecutamos la busqueda
      We execute the search }
      EncontradaEn:=BuscaStringEnFichero('c:\Ejemplo.txt','BuscaMe');
      {Si la ladeca fué encontrada, mostramos donde, sino no
        If the string was find, we show where, but not }
      if EncontradaEn <>-1 then begin
        {Aqui si la encontró
        Here we just found it }
         ShowMessage( 'Cadena encontrada en: '+     // string found in:
                      IntToStr( EncontradaEn )
                      );
      end else begin
         ShowMessage( 'Lo siento, cadena no encontrada en el fichero'+#13+
                      'Im sorry, string not found in the file');
      end;
    
     end;
    




    Actualizado el 20/01/2004 Traducción al inglés, gracias a Jorge Fco. Pérez Soto (jperezso@puc.cl)