Newsgroup: it.comp.lang.c
Titolo: Scrivere la miglior funzione di ricerca...

Chi e' disposto ad accettare la sfida ? ;)
Scrivere una funzione di ricerca di un testo in un file binario.
Il prototipo della funzione e' il seguente :
int FindText( FILE *fp, const char *Text, unsigned long *pos ) ;
Il corpo della funzione non deve essere piu' lungo di 40 linee e deve
essere scritto in C standard.
Ci si puo' avvalere di funzioni aggiuntive.
--
Andrea Laforgia (
andrea_...@bigfoot.com
)
---------------------------------------------

Io ho scritto una implementazione dell' algoritomo di Knut Morris Pratt
cosi' come e' descritto da Sedgewich, ma sono due funzioni:
una che compila un automa a stati finiti (deterministico, quindi no
espressioni regolari) e l' altra che, si procura un carattere da
qualsiasi inpute fa scattare l' automa. Non si memorizza mai niente
del testo perche' non si guarda mai indietro, e' velocissima, adatta
ad aspettare parole anche da una linea TD (l' avevo fatta per eliminare
script in Procomm in cui potevo usare waitfor), le due funzioni insieme
occupano un foglio A4, ma ha un costo aggiuntivo nel compilare il
pattern (una sola volta pero') che potrebbe essere, per pattern come
"aaaaaaaaaaa" di costo (N^2) / 2.
Il sorgente non sara facile trovarlo, e comunque nella mia casa nelle
Marche, ma se hai pazienza due settimane....


 Chi e' disposto ad accettare la sfida ? ;)
Quali saranno i criteri per valutare la migliore routine?
Ivan Molella

Quali saranno i criteri per valutare la migliore routine?
Mi sembra ovvio : quella piu' efficiente !


 ---------------------------------------------
Ecco un tentativo, tutto farina del mio sacco, senza andare a cercare
algoritmi gia' fatti :)
Magari nel formattare il testo ci puo' essere qualche 'a capo' da
mettere a posto, le linee sono 2 o 3 piu' delle 40 indicate, ma qualche
commentino ce l'ho voluto mettere, spero vada bene comunque!
Bye all,
 - Andrea
------------------
#include <stdio.h>
#include <string.h>
int FindText( FILE *fp, const char *Text, unsigned long *pos ){
  /* Assumo corretti i parametri in ingresso (niente NULL) */
  char buf[BUFSIZ], *scan=(char*)Text, *scanBuf;
  int numRead=0,buflen=BUFSIZ;
  long actSeek=ftell(fp),endSeek;
  fseek(fp, 0L, SEEK_END);
  endSeek=ftell(fp);
  fseek(fp, actSeek, SEEK_SET);
  if(endSeek-actSeek<(long)BUFSIZ)
    buflen=(int)(endSeek-actSeek);
  while(numRead || (scanBuf=buf,
                    numRead=fread((void *)buf, sizeof(char), buflen,
fp)) > 0){
    if (scan != (char*)Text){
      /* continuo un match lasciato a meta' */
      while ((*scan != '\0') && (*scanBuf++ == *scan++) && --numRead);
      if (*scan == '\0'){
        /* match trovato */
        fseek(fp, actSeek, SEEK_SET); /* posiziono fp al punto in
questione */
        *pos = (unsigned long)actSeek;
        return 1; /* assumo != 0 per 'ricerca ok' */
      }
      if(!numRead)
        continue; /* buffer esaurito, continuo il match con un altra
lettura */
      /* fallito il match, restart dal punto dove avevo iniziato, + 1 */
      fseek(fp, ++actSeek, SEEK_SET);
      numRead=0;
      if(endSeek-actSeek<(long)BUFSIZ)
        buflen=(int)(endSeek-actSeek);
      scan=(char*)Text;
      continue;
    }
    /* cerco il primo carattere di match*/
    while (*scanBuf++ != *scan && --numRead);
    if (numRead){
      /* carattere trovato */
      ++scan;
      actSeek = ftell(fp) - numRead--;
    }
  }
  return 0;
}
-- 
------------------------------------
arimicci @@ aritaly. com  .~~~.  ))
                (\__/)  .'     )  ))
  Andrea        /o o  \/     .~
      Rimicci  {o_,    \    {
                 / ,  , )    \     .
 * Developer *   `~  '-' \    } ))
C C++ cgi miva  _(    (   )_.'
Java           '---..{____}
OS/2 Warp Server for Ebusiness admin
--------- OS/2 V5 "Phoenix" --------

 Mi sembra ovvio : quella piu' efficiente !
Efficiente riguardo a cosa: tempo, spazio, ... ?
--
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it

Riposto la funzione per vari motivi:
- in alcuni casi il precedente algoritmo non funzionava, ho dovuto
mettere l'autoincremento di 'scan' fuori da "while ((*scan != ..."
- chiamavo fseek anche quando il restart era nel buffer gia' in memoria,
con evidente inefficenza
Adesso l'ho testato in vari casi, dovrebbe andare bene, se non funziona,
fatemi sapere!!! ^_^
Ciao a tutti, - Andrea
#include <stdio.h>
#include <string.h>
int FindText( FILE *fp, const char *Text, unsigned long *pos ){
  /* Assumo corretti i parametri in ingresso (niente NULL) */
  char buf[BUFSIZ], *scan=(char*)Text, *scanBuf, *nextScanBuf;
  int numRead=0,buflen=BUFSIZ, nextnumRead, newBuf=0;
  long actSeek=ftell(fp),endSeek;
  fseek(fp, 0L, SEEK_END);
  endSeek=ftell(fp);
  fseek(fp, actSeek, SEEK_SET);
  if(endSeek-actSeek<(long)BUFSIZ)
    buflen=(int)(endSeek-actSeek);
  while(numRead || (scanBuf=buf, ++newBuf,
                    numRead=fread((void *)buf, sizeof(char), buflen,
fp)) > 0){
    if (scan != (char*)Text){
      /* continuo un match lasciato a meta' */
      while ((*scan != '\0') && (*scanBuf++ == *scan) && --numRead)
        ++scan;
      if (*scan == '\0'){
        /* match trovato */
        fseek(fp, actSeek, SEEK_SET); /* posiziono fp al punto in
questione */
        *pos = (unsigned long)actSeek;
        return 1; /* assumo != 0 per 'ricerca ok' */
      }
      if(!numRead)
        continue; /* buffer esaurito, continuo il match con un altra
lettura */
      /* fallito il match, restart dal punto dove avevo iniziato, + 1 */
      if(newBuf){
        /* devo fare una seek perche' il punto di restart non e' nel
buffer */
        fseek(fp, ++actSeek, SEEK_SET);
        numRead=newBuf=0;
        if(endSeek-actSeek<(long)BUFSIZ)
          buflen=(int)(endSeek-actSeek);
      }else{
        /* rimango in questo buffer */
        scanBuf=nextScanBuf;
        numRead=--nextnumRead;
        ++actSeek;
      }
      scan=(char*)Text;
      continue;
    }
    /* cerco il primo carattere di match*/
    newBuf=0;
    while (*scanBuf++ != *scan && --numRead);
    if (numRead){
      /* carattere trovato */
      ++scan;
      nextScanBuf=scanBuf;
      nextnumRead=numRead;


#include<stdio.h>
#include<string.h>
#define	SEEK_STRING		"Ivan"
#define BUFF_SIZE		(32 * (unsigned int)1024)
#define STRING_MATCHED		0
#define STRING_UNMATCHED        -1
int 	FindText( FILE *,const char *,unsigned long * );
int	main(int argc, char **argv)
{
	FILE *fp			= NULL;
	unsigned long Pos		= 0;
	if	( argc < 2 )
		{
		fprintf( stdout,"uso: <nome programma> <nomefile>\n" );
		exit(1);
		}
	if	( !(fp = fopen( argv[1],"rb" )) )
		{
		fprintf( stderr," Errore in open file\n" );
		exit(0);
		}
	while	( !(FindText( fp, SEEK_STRING, &Pos )) )
			printf( "La stringa e' stata trovata alla posizione: %lu\n", Pos );
	return 0;
}
int	FindText ( FILE *fp,const char *String, unsigned long  *Pos )
{
	char *stPos = NULL, Buff[BUFF_SIZE],*apString = (char*)String,*pBuff = NULL,*stBuff = NULL;
	static unsigned long curPos 	= 0;
	int szBuff = 0, stLen = strlen(String), _stLen = stLen-1;
	static void *prevFP = NULL, *prevString = NULL;
	curPos = ( !curPos )?curPos:( (fp != prevFP) || ( strcmp(
String,prevString ) ) )?0:curPos;
	if	( prevString ) free( prevString );
	prevString = (char*)calloc( ( strlen( String ) + 1 ),sizeof( char ));
	prevFP = fp;
	strcpy( prevString, String );
	do{
		fseek( fp, curPos,SEEK_SET );
		memset( Buff,0,BUFF_SIZE );
		szBuff = fread( Buff, sizeof(char), BUFF_SIZE, fp );
		stBuff = Buff+(((szBuff)?szBuff:1)-1);
		pBuff = Buff;
		while	( ( stBuff - pBuff ) >= (_stLen) ){
			while	( (pBuff != stBuff) && (*pBuff != *String) ) pBuff++;
			if	( ( stBuff - pBuff ) >= (_stLen)){
				stPos = pBuff;
				while( (*String) && (*String++ == *pBuff++) );
				if	( !((!*String) && (*(String-1) == *(pBuff-1))) )
					 stPos=NULL;
				else
					break; }
			String = apString;}
		if	( (stPos) ){
			curPos+= ((char*)stPos - (char*)Buff) + stLen;
			*Pos = curPos - stLen;
			return STRING_MATCHED;}
		else
			curPos+= BUFF_SIZE - (_stLen);
	  } while ( szBuff );
	return STRING_UNMATCHED;
}
Non e' propio il massimo delle performance pero' per meno di 40 righe non
credo sia malaccio;
Le prestazioni decadono per Len(String) che tende a BUFF_SIZE;Se trovate
qualche malfunzionamento che mi e' sfuggito fatemelo sapere.
Ivan Molella
--
Posted from 
mta04-acc.tin.it
 [212.216.176.35]
via Mailgate.ORG Server - 
http://www.mailgate.org



Scusate: Roberto Cappellini alias ziofester
ziofester@mypad,com
Il PC Linux nelle marche non e' ancora tutto configurato.

 Il PC Linux nelle marche non e' ancora tutto configurato.
Non dovresti collegarti come root sai?

 --
Salve, visto che mi farebbe piacere ricevere commenti su un mio programma
ho deciso di mandarvi la mia soluzione.
La mia funzione assume che il file sia aperto correttamente e che
sia bufferizzato.
Se lo stile vi sembra insolito, tenete conto che programmo in C++
#include <stdlib.h>
#include <stdio.h>
int match(FILE* fp, const char* Text, char* end, unsigned long* tested);
int FindText(FILE* fp, const char* Text, unsigned long *pos)
{
  char begin = *Text;           /* carattere iniziale */
  int read;                             /* carattere letto dal file */
  unsigned long fpos = 0;   /* posizione corrente nel file */
  char end;                           /* ultimo carattere letto da match()
                                            */
  unsigned long tested = 0;     /* caratteri letti da match() */
  while( (read = getc(fp) ) != EOF)    /* legge fino alla fine del file */
  {
    if( (char)read == begin )
    {
      /* potrebbe essere l'inizio del testo che si sta cercando */
      if( match(fp, Text, &end, &tested) )
      {
        /* ha trovato il testo */
        *pos = fpos;
        return 1;
      }
      else
      {
        /* riposiziona l'ultimo carattere testato da match() nel buffer
           (infatti potrebbe verificarsi :
            Text = "ciao"  file = "ciaciao"; )  */
        if(ungetc(end, fp) != end)
        {
          /* errore non previsto */
          exit(0);
        }
        fpos += tested;   /* si devono aggiungere i caratteri letti da
                                        match() */
      }
    }
    else ++fpos;  /* avanza la posizione corrente del file */
  }
  /* nessun match trovato */
  return 0;
}
int match(FILE* fp, const char* Text, char* end, unsigned long* tested)
{
  int ch;
  /* il primo carattere è già stato confrontato */
  int size = strlen(++Text);
  *tested = 0;   /* azzera il numero di caratteri testati */
  do
  {
    ch = getc(fp);
    ++*tested;
    if( (char)ch != *Text )
    {
      /* il carattere trovato non fa parte nel testo */
      *end = (char)ch;
      return 0;
    }
    ++Text;
  }
  while(ch != EOF && --size > 0);
  return size == 0;
}
Saluti,  Manlio Perillo

Ho scritto un'altra funzione, questa volta molto piccola.
int FileSize(FILE* fp);
int FindText(FILE* fp, const char* Text, unsigned long *pos)
{
  unsigned long size;           /* dimensione del file */
  char* buf;
  const char* find;
  size = FileSize(fp);
  buf = (char*) malloc(sizeof(char) * size);
  if(buf == NULL) exit(0);
  /* memorizza l'intero contenuto del file */
  fread(buf, sizeof(char), size, fp);
  find = strstr(buf, Text);
  if(find == NULL) return 0;  /* no match */
  *pos = find - buf;
  return 1;
}
int FileSize(FILE* fp)
{
  /* calcola la dimensione del file usando solo C standard */
  unsigned long curr;
  unsigned long size;
  curr = ftell(fp);       /* memorizza la posizione corrente */
  fseek(fp, 0, SEEK_END); /* si posiziona alla fine del file */
  size = ftell(fp);
  fseek(fp, curr, SEEK_SET);
  return size;
}

 Chi e' disposto ad accettare la sfida ? ;)
Sbaglio o.............mancano all' appello un paio di versioni.......
?:):)