[C] zoeken naar string in file

[SWfreak]

Hoe kan ik in C in een file naar een string zoeken?
Ik probeer het nu te doen door:

code:

FILE *fp;
char *tempString;
...
while(!feof(fp))
{
  fgets(tempString, strlen(searchString), fp);
  if(strcmp(tempString, searchString) == 0)
  //dan yippie
  fseek(fp, -(strlen(searchString) - 1), SEEK_CUR);
}

Dit gaat alleen *enorm* traag door die fseek. Iemand een idee hoe ik dit kan doen zonder die fseek?

[D2k]

files==traag
helaas

[SWfreak]

Op maandag 22 oktober 2001 22:53 schreef D2k het volgende:
files==traag
helaas

Zonder fseek gaat het wel snel, dus het moet snel kunnen...

[marcusk]

erm.... excuse my ignorance, maar waar is die fseek hier voor dan?

[it0]

Ik persoonlijk zou doen

code:

while(fgets(buf,l,fp))
{
if(t=strstr(buf,S))fseek(fp,t,SEEK_CUR));
}

ik weet niet wat die fseek moet doen?

[Jrz]

Die idioot gaat filesize keer een seek doen.

Paar oplossingen:
Haal elke keer een regel op, zoek in die string, niet gevonden? volgende regel.

Memorymapped files. Is een stuk sneller.

[SWfreak]

Op maandag 22 oktober 2001 22:56 schreef marcusk het volgende:
erm.... excuse my ignorance, maar waar is die fseek hier voor dan?

Om de boel enorm op te houden. Ik kan wel iets verzinnen door heel ingewikkeld met geheugen te gaan rommelen (de laatste strlen(searchString) bytes overkopieren naar het begin van de nieuwe tempString, maar ik vroeg me af of het ook nog makkelijker (en sneller) kon.

[SWfreak]

Op maandag 22 oktober 2001 23:03 schreef Jrz het volgende:
Die idioot gaat filesize keer een seek doen.

Paar oplossingen:
Haal elke keer een regel op, zoek in die string, niet gevonden? volgende regel.

Memorymapped files. Is een stuk sneller.

Idioot

Misschien was het handig geweest als ik had gezegd had dat ik een binary read doe, dus regels ophalen kan ik vergeten. Memory mapped files kunnen volgens mij niet in oude C?

[marcusk]

Misschien was het handig geweest als ik had gezegd had dat ik een binary read doe, dus regels ophalen kan ik vergeten.

in plaats van een regel kun je dan een aantal bytes (stuk of 1024) in een buffer inlezen.

[SWfreak]

Op maandag 22 oktober 2001 23:08 schreef marcusk het volgende:

[..]

in plaats van een regel kun je dan een aantal bytes (stuk of 1024) in een buffer inlezen.

En dan dus met geheugen rommelen zodat ik niets oversla?

[marcusk]

Op maandag 22 oktober 2001 23:10 schreef SWfreak het volgende:
En dan dus met geheugen rommelen zodat ik niets oversla?

Hoezo dat dan?

[marcusk]

code:

#define BUFSIZE 1024
char buffer[BUFSIZE];
char * offset;
FILE * fp;
...
while(! feof(fp))
{
    fgets(buffer, BUFSIZE, fp);

    if (offset = strstr(buffer, searchString))
      // gevonden op positie (offset - buffer)
}

http://www.cplusplus.com/ref/cstring/strstr.html

simpel toch?

[farlane]

En als de gezochte reekst begint bij byte 1022 en doorloopt tot byte 1030? En wat als er \0 karakters in staan?
Volgens mij gaat dit niet (helemaal) werken zo.

[edit]

Die \0 opmerking van mij is onzin. Had ff gelezen dat er een binary search moest worden gedaan. Is kennelijk niet zo.

[marcusk]

Op dinsdag 23 oktober 2001 09:22 schreef farlane het volgende:
En als de gezochte reekst begint bij byte 1022 en doorloopt tot byte 1030?

je hebt gelijk. nu snap ik ook waarvoor die fseek was

simpel toch?

je kunt dit oplossen door de buffer groot genoeg te maken dat de bestanden er helemaal inpassen (maar een buffer van 1 MB bv. is IMO een beetje overdreven ). of...

code:

#define BUFSIZE 1024
char   buffer[BUFSIZE];
char * offset;
FILE * fp;
int    length = strlen(searchString);
...
while(! feof(fp))
{
    fgets(buffer, BUFSIZE, fp);
    if (offset = strstr(buffer, searchString))
      // gevonden op positie (offset - buffer)

    fseek(fp, -length, SEEK_CUR);
}

(hmmm... dit lijkt best veel op wat SWfreak al had )

[Rukapul]

Ik hoop dat niemand die in deze thread gereageerd heeft een aan informatica gerelateerde studie doet. In dat geval had degene namelijk moeten weten dat je het probleem zonder SEEK op kan lossen en dat je elk karakter maar 1 maal hoeft te bekijken als je een eindige automaat maakt (kan geautomatiseerd) van je zoekstring. Dit staat in direct verband met reguliere expressies.

Een zoektocht in de boeken of google op pattern matching etc levert misschien ook nog wel wat op.

[marcusk]

Op dinsdag 23 oktober 2001 14:57 schreef Rukapul het volgende:
Ik hoop dat niemand die in deze thread gereageerd heeft een aan informatica gerelateerde studie doet.

Technische Informatica (1e jaar)

In dat geval had degene namelijk moeten weten dat je het probleem zonder SEEK op kan lossen en dat je elk karakter maar 1 maal hoeft te bekijken als je een eindige automaat maakt (kan geautomatiseerd) van je zoekstring. Dit staat in direct verband met reguliere expressies.

Een zoektocht in de boeken of google op pattern matching etc levert misschien ook nog wel wat op.

dat kan idd, maar ik betwijfel heel erg of dat sneller is. Het kost ook nog veel meer code.

[Rukapul]

Op dinsdag 23 oktober 2001 15:07 schreef marcusk het volgende:

[..]

dat kan idd, maar ik betwijfel heel erg of dat sneller is. Het kost ook nog veel meer code.

Het kost wellicht meer code, maar van alle system functies die je nu gebruikt weet je ook niet precies hoeveel code er achter schuilt. Voor de functies die je hier nodig hebt zijn ook kant en klare oplossingen te vinden.

Random file access is traag en dus kun je er op deze manier voor zorgen dat je helemaal sequentieel door het bestand kan gaan.

Ter info:
-als m de lengte van het bestand is
-en als n de lengte van de string is
dan bekijk je in de oude situatie in worst case: n.m

Met een reguliere expressie is dat n . De complexiteit van het algoritme is dus veel lager.

[.oisyn]

Op dinsdag 23 oktober 2001 14:57 schreef Rukapul het volgende:
Ik hoop dat niemand die in deze thread gereageerd heeft een aan informatica gerelateerde studie doet. In dat geval had degene namelijk moeten weten dat je het probleem zonder SEEK op kan lossen en dat je elk karakter maar 1 maal hoeft te bekijken als je een eindige automaat maakt (kan geautomatiseerd) van je zoekstring. Dit staat in direct verband met reguliere expressies.

Een zoektocht in de boeken of google op pattern matching etc levert misschien ook nog wel wat op.

Een eindige automaat maken van een simpele zoekstring is echt bullshit... dat is alleen handig als je echt reguliere expressies gaat gebruiken.

Een handig zoek algoritme waarbij je niet eens alle tekens bekijkt is als je steeds achteraan de zoekstring begint.
Even kijken, hoe kan ik dat het beste uitleggen...

Stel je zoekt op "abcdefg" in de string "qwertyuiopabcdefghjk"
Je kunt natuurlijk bij de 'q' beginnen, en dan kijken of ie gelijk is aan de 'a', en als ze gelijk zijn het volgende teken vergelijken met het volgende teken in de zoekstring, en anders moet je het volgende teken vergelijken met het eerste teken van de zoekstring.
Wat handiger is, is als je bij het 7e teken begint in de string (de 'u') en die vergelijken met het laatste teken van de zoekstring (de 'g'). Als die gelijk zijn moet je 6 tekens terug om te kijken of ie klopt, maar als ze NIET gelijk zijn dan kun je gelijk 7 tekens verder schuiven, aangezien de 'u' nergens in 'abcdefg' voorkomt. Komt ie er wel in voor dan moet je een x aantal tekens terug gaan, waarbij x het hoeveelste teken is dat 'u' in de zoekstring voorkomt.

Ja ik weet het, mijn uitleg suckt, maar misschien is het toch wel duidelijk wat ik bedoel

[.oisyn]

Op dinsdag 23 oktober 2001 15:11 schreef Rukapul het volgende:
Met een reguliere expressie is dat n . De complexiteit van het algoritme is dus veel lager.

Uhm nee de worst case bij eindige automaten is dat m (de lengte van het bestand), in het geval dat de string niet in het bestand voorkomt

[farlane]

Op dinsdag 23 oktober 2001 17:15 schreef OiSyN iets over een zoek algoritme:

Is het niet zo, dat als de lengte van de te zoeken string erg klein is ten opzichte van de string waar je in zoekt (zoals in dit geval het geval is verwacht ik) , dat het niet veel zin heeft om zo'n algoritme te gebruiken?

Een (goede?) oplossing zou hier zijn om met de c++ streams te gaan werken. Die zijn al redelijk goed gebufferd verwacht ik, dus hoef je niet te memory-mappen. Is dat wat?

[marcusk]

Op dinsdag 23 oktober 2001 17:15 schreef OiSyN het volgende:
Een eindige automaat maken van een simpele zoekstring is echt bullshit... dat is alleen handig als je echt reguliere expressies gaat gebruiken.

Ik weet niet wat de definitie van een eindige automaat precies is, maar wat je wel kunt doen is de zoekfunctie zo aanpassen dat ie aangeeft hoeveel characters van de zoekstring hij heeft gematched als ie aan het eind van de string is aangekomen, en dat je daar bij een volgende aanroep verder kunt gaan. Is dat niet wat Rukapul bedoelt?

ff een voorbeeldje voor de duidelijkheid:

buffersize: 10
zoekstring: opabc
string: qwertyuiopabcdefghjk

bij de eerste aanroep zit er "qwertyuiop" in de buffer, dan zegt de functie dat ie 2 tekens gevonden heeft. bij de volgende aanroep "abcdefghjk", dan begint ie bij de 3e letter van de zoekstring.

[Infinitive]

Een handig zoek algoritme waarbij je niet eens alle tekens bekijkt is als je steeds achteraan de zoekstring begint.

Wat als je nu eens een geheugenruimte neemt ten groote van je zoekstringsize-1 en een buffer-size neemt die minstens zo groot is als je zoekstring? Als je dan van achter naar voren aan het inlezen bent, en je vind een byte die matched, maar je bent in je huidige buffer op de eerste byte aangeland, kan je nog verder zoeken in het laatste deel van de vorige buffer. Dat kleine stukje geheugenruimte vul je dan bij elke keer dat je de buffer ververst met een memcpy() vanaf het einde van de buffer - (zoekstringsize-1) tot/met het einde van de buffer.

Als je zoekstring relatief groot is ten opzichte van je buffer zou je zelfs twee buffers kunnen nemen (en via een pointer switchen), dan heb je de overhead van memcpy() niet, het kost alleen wat extra bytes geheugen.

Ehm, eens even kijken of ik het in een stukje code kan zetten, ik heb zelf straks zoiets ook nog nodig:

code:

#include <memory.h>
#include <stdio.h>
#include <string.h>

#define MAX_SEARCH_STR_SIZE 1024

/* 0: match gevonden, 1: geen match, 2: fout */
unsigned char findstr(FILE *fp, const char *const search_str, const size_t buffer_size)
{
    size_t  search_str_size;
    char    *read_buf;
    char    *backup_buf;
    size_t  n_read;
    size_t  i;
    char    *read_ptr;
    const char *backup_ptr;
    char    last_search_str_char;
    size_t  base_pos; /* het aantal bytes wat we tot nu toe hebben ingelezen */
    size_t  left; /* aantal bytes dat er in de buffer gekeken moet worden ("over") */
    size_t  match; /* hebben we een match? */

    if (!fp || ferror(fp))
      return 2u; /* ongeldige fp */
    
    if (!search_str)
      return 2u; /* null ptr */
    
    search_str_size = strlen(search_str);
    if (!search_str_size || search_str_size > MAX_SEARCH_STR_SIZE)
      return 2u; /* ongeldige zoekstring */
    
    if (buffer_size < search_str_size)
      return 2u; /* buffer size te kort */
    
    read_buf = (char *) malloc(sizeof(char) * buffer_size);
    if (!read_buf)
      return 2u; /* malloc gefaalt :? */
    
    /* verknoei 1 byte, maar anders werkt het niet voor een zoekstring van 1 karakter */
    backup_buf = (char *) malloc(sizeof(char) * (search_str_size));
    if (!backup_buf)
    {
        free(read_buf);
      return 2u; /* malloc gefaalt :? */
    }
    
    backup_ptr = backup_buf+(search_str_size-2); /* pointer naar laatste element van backup ptr) */
                                 /* dit kan dus ook het -1 element zijn... maar dat wordt geen probleem */
    
    /* laatste char van search_str */
    last_search_str_char = search_str[search_str_size-1];
    
    /* nog geen match */
    match = 0;
    
    base_pos = 0;
    for(;;)
    {
      /* read_buf vullen */
      n_read   = fread(&read_buf, sizeof(char), buffer_size, fp);
      if (!n_read)
      {
        if (ferror(fp))
            match = 2; /* leesfout */
        
        break; /* einde van bestand */
      }
      
      /* alle karakters van read_buf afgaan (achter naar voren) */
      read_ptr = read_buf + n_read;
      while(read_ptr != read_buf)
      {
        read_ptr --; /* we begonnen 1 element te hoog (zie: + n_read), maar op deze manier is het mooi voor de while loop */
        
        /* in de huidige buffer zit een char die gelijk is aan de laatste char van de zoekstring */
        if (*read_ptr == last_search_str_char)
        {
            /* hoeveel bytes moeten we nog in de leesbuffer checken? */
            if ((left = read_ptr-read_buf +1) >= search_str_size)
              left = search_str_size;
            
            /* hebben we een match in de leesbuffer? */
            if (!memcmp(read_ptr-left, search_str+(search_str_size-left)))
            {
              /* nu nog de backup buffer */
              if (left == search_str_size)
              {
                /* de match bevond zich al in de lees buffer */
                match = 1;
                goto findstr_finished; /* spring uit beide loops */
              }
              else
              {
                if (!base_pos)
                    break; /* backup buffer nog niet gevult */
                         /* (het heeft nu ook geen zin meer om nog verder in deze read_buffer te zoeken) */
                
                /* nu nog search_str_size-left bytes checken */
                if (!memcmp(backup_ptr-(search_str_size-left), search_str+left))
                {
                    /* de rest van de match zit in de backup buffer */
                    match = 1;
                    goto findstr_finished; /* spring uit beide loops */
                }
              }
            }
        }
      }
      
      /* vul de backup buffer met het laatste gedeelte van de read buffer */
      memcpy(backup_buf, read_buf+(n_read-search_str_size), search_str_size-1);
      base_pos += n_read;
    }

findstr_finished:
    free(read_buf);
    free(backup_buf);
    return match;
}

Of het werkt: ik niet weten (op papier lijkt het te kloppen)

Alleen jammer van de malloc()s.

[marcusk]

volgens mij heb je iets dubbel (nu niet meer )

je kunt ook de twee buffers om-en-om als 'backup' gebruiken zodat je niet steeds hoeft te memcpy'en

[edit]oeps, dat schreef je zelf al

[Rukapul]

Op dinsdag 23 oktober 2001 17:15 schreef OiSyN het volgende:
Een handig zoek algoritme waarbij je niet eens alle tekens bekijkt is als je steeds achteraan de zoekstring begint.
Even kijken, hoe kan ik dat het beste uitleggen...

<knip>

Je beschrijving rammelt van alle kanten. Bovendien werkt je optimalisatie nauwelijks op het moment dat de zoekstring een redelijke omvang heeft. Tevens ontbreekt een generiek oplossingmodel, want je houdt de laatste letter bij, maar de andere letters van de zoekstring bijvoorbeeld niet.

Ook je zogenaamde sprongen van de complete lengte van de zoekstring zijn geen sprongen, omdat je alle letters langsloopt om de laatste letter van je zoekstring bij te houden, waarna je daarna terugspringt. Je oplossing is vrijwel gelijk aan die van de originele poster alleen presenteer je het ingewikkelder.

[Infinitive]

volgens mij heb je iets dubbel (nu niet meer )

Ik had 'm ff off-line getikt en via copy&paste hiernaar toe. Toen ging ik de post edditen en ik wilde ctrl+z indrukken, maar had blijkbaar ctrl+v ingedrukt en aangezien dat bij het invoeren voor het gezicht hetzelfde was

je kunt ook de twee buffers om-en-om als 'backup' gebruiken zodat je niet steeds hoeft te memcpy'en

De twee malloc's zou je ook ineen kunnen nemen. Of beter, een buffer opgeven aan de functie.

[marcusk]

ik heb dit in elkaar geknutseld:

code:

// zoekt naar p_str2 in p_str1
// return waarden:
//   0: niet gevonden
//   1: gevonden, offset zit in p_result
//   2: gedeeltelijk gevonden: tot p_result

int strstr_chunk(char * p_str1, char * p_str2, char ** p_result)
{
    char *  l_pos1 = p_str1;
    char *  l_pos2 = p_str2;
    int l_len = strlen(p_str2);

    while (true)
    {
        if (*l_pos1 == *l_pos2)
            l_pos2++;
        else
            l_pos2 = p_str2;

        l_pos1++;

        if (*l_pos2 == 0)
        {
            // eind van str2 -> gevonden
            *p_result = l_pos1 - l_len;
            return 1;
        }

        if (*l_pos1 == 0)
        {
            // eind van str1 -> niet- of gedeeltelijk gevonden
            *p_result = l_pos2;
            return (l_pos2 == p_str2 ? 0 : 2);
        }
    }
}

en om het te gebruiken:

code:

#define BUFSIZE 1024
...
char   buffer[BUFSIZE];
char * offset;
FILE * fp;
int    r = 0;
...
while(! feof(fp))
{
    fgets(buffer, BUFSIZE, fp);
    if (r == 2)
    {
        int len = strlen(offset);
        if (strncmp(buffer, offset, len) == 0)
        // gevonden!!!
    }
    else
      r = strstr_chunk(buffer, search, &offset);

    if (r == 1) // gevonden!!!
}

[.oisyn]

Op dinsdag 23 oktober 2001 21:47 schreef Rukapul het volgende:

[..]

Je beschrijving rammelt van alle kanten. Bovendien werkt je optimalisatie nauwelijks op het moment dat de zoekstring een redelijke omvang heeft. Tevens ontbreekt een generiek oplossingmodel, want je houdt de laatste letter bij, maar de andere letters van de zoekstring bijvoorbeeld niet.

Ook je zogenaamde sprongen van de complete lengte van de zoekstring zijn geen sprongen, omdat je alle letters langsloopt om de laatste letter van je zoekstring bij te houden, waarna je daarna terugspringt. Je oplossing is vrijwel gelijk aan die van de originele poster alleen presenteer je het ingewikkelder.

wat loop je mij nou af te zeiken? Ten eerste zei ik al dat mijn beschrijving zoog, ten tweede is het algoritme niet bedacht door mij, en is het bewezen dat het sneller is. Die sprongen waar ik het over heb zijn sprongen tijdens het CONTROLEREN, niet tijdens het INLEZEN, 2 hele verschillende dingen

[SWfreak]

Op dinsdag 23 oktober 2001 21:35 schreef Infinitive het volgende:

[berg code :)]

Dit was idd wat ik zocht. Ik hoopte alleen dat het korter/eenvoudiger zou kunnen zonder al die bufferboel, maar helaas pindakaas dus. Many thanx!

[it0]

code:

char b[2048]="\0";
char b2[1024]="\0";
char *l;
FILE *fp;

fp=fopen("bla.txt","r");
while(fgets(b+strlen(b2),bl,fp))
{
if(fgets(b2,bl,fp))
{
strcat(b,b2);
}
l=strstr(b,searchstring);
if(l)printf("found at %e\n",l);
strcpy(b,b2);
}
fclose(fp);

Is dit niet wat eenvoudiger?

[marcusk]

dat kan idd, maar je doorzoekt alles 2x, en strcat is traaaaaaaaag!

(je bent trouwens int bl = 1024 vergeten, en tabs gebruiken is ook wel handig)

[it0]

Op woensdag 24 oktober 2001 23:32 schreef marcusk het volgende:
dat kan idd, maar je doorzoekt alles 2x, en strcat is traaaaaaaaag!

(je bent trouwens int bl = 1024 vergeten, en tabs gebruiken is ook wel handig)

Tabs will niet lukken springt dan uit het textarea venster.
Idd bl vergeten, sorry.

maar als je het beter wil doen dan verander je de strcpy in
strcpy(b,b2+(strlen(b2)-strlen(searchstring)+1));

en in fgets wordt dan strlen(b2) strlen(b);
Zo beter?

Als je strcat te langzaam vindt code je daar zo omheen

[Verwijderd]

Hmm, ik zie alleen maar naieve oplossingen die N * M karaktervergelijkingen gebruiken, en dat is lekker traag. Er bestaat al meer dan 25 jaar een algoritme waarmee je in gemiddeld N/M vergelijkingen een string kunt doorzoeken. Dat algoritme en zijn varianten worden Boyer-Moore zoeken genoemd en zijn definitief veel sneller.

Ze berusten op het geniale idee om bij het achterste karakter van de zoekstring te beginnen met vergelijken, en dan meer dan een karakter te overspringen als er een ongelijkheid gevonden wordt.

[Verwijderd]

Als optimalisatie kun je onder Windows ook nog gebruik maken van memory mapped files. In sommige gevallen kan dit enorme snelheids winst geven.

[.oisyn]

Op donderdag 25 oktober 2001 13:45 schreef mietje het volgende:
Hmm, ik zie alleen maar naieve oplossingen die N * M karaktervergelijkingen gebruiken, en dat is lekker traag. Er bestaat al meer dan 25 jaar een algoritme waarmee je in gemiddeld N/M vergelijkingen een string kunt doorzoeken. Dat algoritme en zijn varianten worden Boyer-Moore zoeken genoemd en zijn definitief veel sneller.

Ze berusten op het geniale idee om bij het achterste karakter van de zoekstring te beginnen met vergelijken, en dan meer dan een karakter te overspringen als er een ongelijkheid gevonden wordt.

Dat is nou precies het algoritme wat ik probeerde te beschrijven een paar posts terug... Ik zat eigenlijk op een reactie als deze te hopen

[Infinitive]

Op donderdag 25 oktober 2001 13:45 schreef mietje het volgende:
Hmm, ik zie alleen maar naieve oplossingen die N * M karaktervergelijkingen gebruiken, en dat is lekker traag. Er bestaat al meer dan 25 jaar een algoritme waarmee je in gemiddeld N/M vergelijkingen een string kunt doorzoeken. Dat algoritme en zijn varianten worden Boyer-Moore zoeken genoemd en zijn definitief veel sneller.

interessante link, heb je er nog meer?

[Verwijderd]

Op donderdag 25 oktober 2001 20:07 schreef Infinitive het volgende:
interessante link, heb je er nog meer?

Oei Helaas niet nee, gewoon uit m'n oude algoritmiekboek (dat van Wirth onderaan in die link) gehaald, en vervolgens met google een linkje gezocht.

Ik was me wel aan het vervelen, dus heb ik er maar een simpele BM-search uitgestampt

code:

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>

#define BUFFERLENGTE    2048

struct ZoekPatroon {
  const char    *string;
  int       lengte,
          afstand[UCHAR_MAX + 1];
};

void ZoekPatroon_init(struct ZoekPatroon*,const char*);
int ZoekPatroon_zoek(const struct ZoekPatroon*,const char*,int);

struct FileZoekBuffer {
  char      *buffer;
  const char    *basis;
  int       capaciteit,
        lengte;
  FILE      *file;
  long      positie;
};

void FileZoekBuffer_init(struct FileZoekBuffer*,char*,int,FILE*,long);
long FileZoekBuffer_zoek(struct FileZoekBuffer*,const struct ZoekPatroon*);

char buffer[BUFFERLENGTE];

int main(int argc, char *argv[]) {
  FILE           *fp;
  long           pos;
  struct ZoekPatroon    zp;
  struct FileZoekBuffer fzb;
  if(argc != 3) {
    fprintf(stderr, "Gebruik: %s <filenaam> <zoekstring>\n", argv[0]);
    return EXIT_FAILURE;
  }
  fp= fopen(argv[1], "rb");
  if(!fp) {
    fprintf(stderr, "Kan file \'%s\' niet openen!\n", argv[1]);
    return EXIT_FAILURE;
  }
  ZoekPatroon_init(&zp, argv[2]);
  FileZoekBuffer_init(&fzb, buffer, BUFFERLENGTE, fp, 0);
  pos= FileZoekBuffer_zoek(&fzb,&zp);
  while(pos >= 0) {
    printf("%li\n",pos);
    pos= FileZoekBuffer_zoek(&fzb,&zp);
  }
  fclose(fp);
  return EXIT_SUCCESS;
}

void ZoekPatroon_init(struct ZoekPatroon *zp, const char *str) {
  int i, stop;
  zp->string= str, zp->lengte= stop= strlen(str);
  for(i= 0; i <= UCHAR_MAX; ++i) zp->afstand[i]= stop;
  for(i= 0, --stop; i < stop; ++i) zp->afstand[(int)str[i]]= stop - i;
}

int ZoekPatroon_zoek(const struct ZoekPatroon *zp,
                    const char *buffer, int lengte) {
  int   i= zp->lengte,
    j, k;
  if(i > lengte) return -1;
  do {
    j= zp->lengte, k= i;
    do {
    if(--j < 0) return k;
    --k;
    } while(zp->string[j] == buffer[k]);
    i+= zp->afstand[(int)buffer[i - 1]];
  } while(i < lengte);
  return zp->lengte - i - 1;
}

void FileZoekBuffer_init(struct FileZoekBuffer *fzb, char *buffer,
                int capaciteit, FILE *file, long positie) {
  fzb->buffer= buffer, fzb->capaciteit= capaciteit, fzb->lengte= 0,
  fzb->file= file, fzb->positie= positie;
}

long FileZoekBuffer_zoek(struct FileZoekBuffer *fzb,
                    const struct ZoekPatroon *zp) {
  long  ret;
  int   ofs= ZoekPatroon_zoek(zp, fzb->basis, fzb->lengte);
  while(ofs < 0) {
    if(feof(fzb->file)) return -1;
    ofs= -1 - ofs;
    fzb->positie+= ofs;
    fzb->lengte-= ofs;
    memmove(fzb->buffer, fzb->basis + ofs, fzb->lengte);
    fzb->lengte+= fread(fzb->buffer + fzb->lengte, sizeof(char),
    fzb->capaciteit - fzb->lengte, fzb->file);
    fzb->basis= fzb->buffer;
    ofs= ZoekPatroon_zoek(zp, fzb->basis, fzb->lengte);
  }
  ret= fzb->positie+= ofs;
  fzb->positie+= zp->lengte;
  ofs+= zp->lengte;
  if(ofs >= fzb->lengte) fzb->lengte= 0;
  else fzb->basis+= ofs, fzb->lengte-= ofs;
  return ret;
}

Je kunt die ZoekPatroon_zoek() ook gebruiken om in strings te zoeken, hij retourneert een index >= 0 in de string, of een negatief getal dat de offset naar de volgende zoekopdracht weergeeft als het patroon niet gevonden is. Die FileZoekBuffer_zoek() is zo ingewikkeld omdat je ervoor moet zorgen dat je ook strings die over een buffergrens heen gaan moet kunnen vinden (dat vergeten nogal wat mensen die oplossingen posten).

[farlane]

Op donderdag 25 oktober 2001 13:45 schreef mietje het volgende:
Hmm, ik zie alleen maar naieve oplossingen ...

Wie weet is werkt strstr(...) intern ook wel op die BM manier. Wat is er op tegen om een reeks met strstr te doorzoeken?

[Verwijderd]

Op donderdag 25 oktober 2001 21:08 schreef farlane het volgende:
Wie weet is werkt strstr(...) intern ook wel op die BM manier. Wat is er op tegen om een reeks met strstr te doorzoeken?

Nee, dat doet hij niet. Bij dit soort searches moet je het zoekpatroon (de te zoeken string) voorvertalen (doe ik in ZoekPatroon_init). Dit voorvertalen is een nadeel als de te doorzoeken strings kort zijn, wat meestal het geval is. Hoe langer de te doorzoeken string en het te vinden zoekpatroon worden, hoe voordeliger een BM-search wordt.

<edit>eumz, ik had me in een naampje vergist, sorry |:(</edit>

[marcusk]

Op donderdag 25 oktober 2001 21:31 schreef mietje het volgende:
Nee, dat doet hij niet.

ik heb ff gekeken bij de implementatie in msvc, en dat is inderdaad een char-voor-char vergelijking

Bij dit soort searches moet je het zoekpatroon (de te zoeken string) voorvertalen (doe ik in ZoekPatroon_init). Dit voorvertalen is een nadeel als de te doorzoeken strings kort zijn, wat meestal het geval is. Hoe langer de te doorzoeken string en het te vinden zoekpatroon worden, hoe voordeliger een BM-search wordt.

je week niet hoe lang de zoekstring in het geval van SWfreak is, dus je opmerking over 'naieve zoekmethoden' vind ik misplaatst (hoewel het uiteraard altijd sneller kan).

Daarnaast houdt ook jouw code geen rekening met buffer overlaps (maar dit heeft niets met strstr te maken). Stel we zoeken de string "ik" met een buffergrootte van 10, dan vindt jouw programma die string niet in de file "123456789ik", omdat die "ik" precies over de buffergrens valt. Je houdt er ook geen rekening mee dat een string meerdere malen in de buffer voorkomt.

waarover heb je het nou? ik zie hier namelijk geen code van farlane.

[Verwijderd]

Op donderdag 25 oktober 2001 21:52 schreef marcusk het volgende:
je week niet hoe lang de zoekstring in het geval van SWfreak is, dus je opmerking over 'naieve zoekmethoden' vind ik misplaatst (hoewel het uiteraard altijd sneller kan).

Het gaat ook om de lengte van de te doorzoeken string. In het geval van een file zal die eerder groot dan klein zijn. Hoe groter je die buffers maakt, hoe sneller de BM-search wordt in verhouding tot strstr. Naief slaat trouwens niet op de personen, het is een algemeen gebruikte uitdrukking in de algoritmiek voor een "brute force" oplossing.

waarover heb je het nou? ik zie hier namelijk geen code van farlane.

Was ik toch te laat met m'n edit Ik dacht ten onrechte dat farlane die strstr code geschreven had.

[farlane]

Op donderdag 25 oktober 2001 21:31 schreef mietje het volgende:

[..]

Bij dit soort searches moet je het zoekpatroon (de te zoeken string) voorvertalen (doe ik in ZoekPatroon_init).

Ok, ik had eerlijk gezegd niet je code doorgekeken. In dat geval zou het misschien wat kunnen opleveren. Toen ik je lap code zag bekroop me het gevoel dat het simpeler (met minder werk) moest kunnen.

Kun je niet het standaard find() algoritme loslaten op die stream?

[SWfreak]

Op donderdag 25 oktober 2001 13:45 schreef mietje het volgende:
Hmm, ik zie alleen maar naieve oplossingen die N * M karaktervergelijkingen gebruiken, en dat is lekker traag. Er bestaat al meer dan 25 jaar een algoritme waarmee je in gemiddeld N/M vergelijkingen een string kunt doorzoeken. Dat algoritme en zijn varianten worden Boyer-Moore zoeken genoemd en zijn definitief veel sneller.

Ze berusten op het geniale idee om bij het achterste karakter van de zoekstring te beginnen met vergelijken, en dan meer dan een karakter te overspringen als er een ongelijkheid gevonden wordt.

Hmm, ik had nog niet aan mijn Algoritmen-boeken gedacht. Was gewoon gaan hakken Brute-force is dan idd O(nm) terwijl Boyer Moore O(n+m) is. Scheelt wel behoorlijk op files van ongeveer 200KB grootte, waarvan ik ook nog eens verwacht dat de te zoeken string achteraan staat.