Šta je novo?
Od:
Filteri

String search u file-u - algoritam

A

alfaunits

Uticajan
Učlanjen(a)
24.06.2006
Poruke
45,668
Poena
1,705
Treba mi sto brzi algoritam za pretragu stringa u fajlu.
Posto moram da implementiram isti u driveru, ne znaci mi postojeci kod, cak ni u C-u, jer file I/O nije isti 🙂

Ono sto je najbitnije je:
- string koji se pretrazuje ce biti ceo u memoriji
- ne sme se ucitavati vise od 4 ili 64KB odjednom i sme se ucitavati iskljucivo toliko (zbog performansi)

Neki osnovni sam skrcao olako, i posto ce u vecini slucajeva biti pretrazivani vrlo mali fajlovi nije neki problem, ali bih voleo da ovo bolje uradim 🙂

Ideas ili link na neki konkretan algoritam?
 
Posto je u pitanju driver.. kakva je situacija sa dinamickom alokacijom memorije?
Npr.. u pretrazi naletis na pocetak stringa koji se trazi pa malo kasnije ponovo naletis na moguci pocetak stringa koji se trazi i sada pratis dva moguca resenja. Kada uleti neki karakter koji nije u stringu koji se trazi jedno od resenja (ili oba) otpada. Moze se desiti da imas mnogo zapocetih pretraga pa je potrebno alocirati memoriju... ne puno.. 2 x int za svaku zapocetu pretragu.
 
Najbrži algortam je Bojer-Mur (Boyer-Moore) algoritam. Ako je dat tekst dužine n i string za pretragu dužine m, vreme pretrage je O(n/m)+O(broj nađenih). Kako funkcioniše:

String za pretragu mora da se procesira i da se od njega napravi jump tabela za svaki jedinstveni karakter u stringu. Zatim kreće pretraga teksta od m-tog karaktera u tekstu. Ako nije jednak nijednom karakteru stringa može se preskočiti sledećih m karaktera teksta i opet krenuti. Ako je jednak poslednjem karakteru stringa algoritam se vraća unazad za po jedan karakter dok ne potvrdi da je našao string, ako negde u vraćanju naiđe na karakter koji nije na tom mestu u stringu konsultuje tabelu koliko može da preskoči.

Ovo je u vrlo kratkim crtama. Ali suština je da ako stringa nema u tekstu, i ako je string relativno dugačak (recimo 20 karaktera) algoritam će proći kroz tekst za O(n/20). Ako ga ima u tekstu, na to se dodaje vreme koje je potrebno da se potvrdi nalaz.

Pogledaj po Internetu (Wikipedia, Google) o Boyer-Moore algoritmu. Može se sigurno naći po kom se tačno principu formira tabela, kolika ona treba da bude i svi ostali detalji.


Nevezano za pretragu:
Pretpostavljam da je ograničenje učitavanja od 4 ili 64kB vezano za veličinu stranice memorije koja je 4kB na x86. Na unix sistemima imaš sistemski poziv mmap() (može da se zove iz C-a ili asamblera), koji će da ti odvoji jednu ili više stranica memorije i mapira je na neki fajl ili deo fajla.

Recimo imaš fajl od 25kB-a teksta. Pozoveš mmap daš mu kao argumente fajl deskriptor (koji možeš dobiti iz imena fajla drugom funkcijom), poziciju u fajlu i dužinu. Ako za poziciju staviš 0, a dužinu staviš 4096, mapiraće ti prva 4 kB fajla na jednu stranicu memorije i vratiće pointer sa adresom početka te stranice. Sadržaj te stranice biće jednak sadržaju prva 4kB fajla. I trebaće to 7 mapiranja za ceo fajl. 25 = 4*6 + 1. Dakle poslednje mapiranje će straćiti 3 kB memorije.

Na Windows-u postoje funkcije CreateFileMapping i MapViewOfFile. Ne znam tačno kako one funkcionišu.
 
Poslednja izmena:
To je ok resenje, ali je nezgodno ako je string koji se trazi duzi od stranice. Onda moze da se desi da mapira razlicite stranice vise puta da bi testirao. E sad, posto je u pitanju driver code, treba da nam javis koliko su pojedine operacije skupe (dinamicka alokacija memorije, ucitavanje stranice sa diska) pa po tome izabrati algoritam.
 
@ivan, problem je kako da se bufferuje file koji se pratrazuje? Recimo da string koji se trazi postoji na lokaciji 4KB-1 do 4KB+10? Procitano je 4KB pa novih 4KB ali da se zasebno pretrazuju string se ne bi nasao.
Taj deo je ono sto treba optimizovati isto kao i samu string pretragu.
Mapiranje fajla u memoriju mi nista ne znaci. Da li cu citati po 4KB ili mapirati po 4KB nema razlike.
Ali moze se desiti da se u isti vreme pretrazuje gomila vecih fajlova ili jedan cak file koji je >256MB - toliko memorije driver ne moze da alocira 🙂 (non-paged) Ili 450MB za paged, i... ne znam koliki bese limit za x64 OS, ali postoji i filesize vrlo lako moze preci taj limit. Znaci nikako ne dolazi u obzir kompletno ucitavanje fajla.

yooyo je napisao(la):
Posto je u pitanju driver.. kakva je situacija sa dinamickom alokacijom memorije?
Kliknite za proširenje...
Unapred poznata kolicina alokacija moze i sigurno ce trebati barem za buffering.
Precizirane su moguci stringovi tako da velicine nece biti velike (1KB recimo nece biti), sto i moj na-brzaka algoritam dosta uproscuje.

Npr.. u pretrazi naletis na pocetak stringa koji se trazi pa malo kasnije ponovo naletis na moguci pocetak stringa koji se trazi i sada pratis dva moguca resenja. Kada uleti neki karakter koji nije u stringu koji se trazi jedno od resenja (ili oba) otpada. Moze se desiti da imas mnogo zapocetih pretraga pa je potrebno alocirati memoriju... ne puno.. 2 x int za svaku zapocetu pretragu.
Kliknite za proširenje...
Uh, alokacija po (int) za ovako nesto bi dovele sistem na kolena ili slomila kicmu vrlo brzo 🙂 Samo za filename smo morali da radimo lookaside alokacije recimo jer se na serverima precesto alocira dinamicka velicina memorije - i vrlo brzo je ponestalo memorije zbog fragmentacije 🙂 (int) alokacije bi bile ubitacne, a bile bi jos cesce.
A i posto ce stringovi koji se traze biti "maleni", nema potrebe da se cuva tabela, "ponovna" pretraga bi bila brza cak.

Ucitavanje stranice sa diska se ne sme ponavljati i mora biti sequential. Ovo je mnogo bitnije nego brzina string pretrage! Diskovi gde ce se ovo koristiti su u najboljem slucaju laptop 7200rpm diskici... a procesori nece biti ispod C2D. Znaci disk je bottleneck.

EDIT: Proveravao sam da li bi smeo da se koristi windows cache ovde - sme. Znaci ponovno ucitavanje iste stranice moze ali je potrebno. Ali mislim da buffering jedne dodatne back-stranice nije problem (posto stringovi koji se pretrazuju nece biti veci od stranice).
 
Poslednja izmena:
strstr() ne sme da se koristi u kernel modu?
 
Sme... ali kako ces to iskoristiti kada nemas ceo buffer koji pretrazujes linearno?
 
Pa iz delova. Pretražuješ 4kb po 4kb. 🙂

Rezervišeš bafer od 4096 + strlen bajtova (ili x2 ako je unicode) i + 1 za 0x00. Prvi put pročitaš 4k iz fajla, svaki sledeći put na početku bafera ostaviš poslednjih strlen bajtova iz prethodne iteracije + novih 4k iz fajla. Samo jednom prolaziš kroz fajl, a strstr() je prilično dobro napisana. Jedino ako ne postoji neka kvaka zbog čega ne radi dobro u kernel modu.
 
Poslednja izmena:
OK, ajde ovako, ako je string za pretragu veći od veličine stranice nije problem, može da se mapira kolko oćeš memorije na kolki oćeš deo fajla (ne mora da se mapira po jedna strana, možeš više). Jedino što treba da se reši je situacija kod prelaza sa nekog dela fajla na sledeći (ako je jedan deo u memoriji pa algoritam diođe do pred kraj, šta onda). Recimo da bi možda moglo da se ubaci sledeći deo fajla u memoriju na strance koje su odma posle te krajnje u trenutnom delu fajla. Samo ne znam da li operativni sistem dozvoljava recimo da ti da memoriju, ali da ti kaže da li iza tememorije ima dovoljno memorijskog prostora (odnosno nemapiranih stranica) u kontinuitetu, da možeš da mapiraš još stranica kad ti treba i da ih nadovežeš na one od ranije. Naravno demapiraćeš onu memoriju koja ti ne treba više, da bi održao ograničenje u memoriji koju koristiš. U suštini treba da se valjaš kroz memoriju kao gusenica tenka 😀.

Pošto radiš u kernelu ne znam tačno šta kernelski api za drajvere pruža. Možda možeš ovo da postigneš.


EDIT: preteče me.

@zeleni_zub: Odlična je ideja. Znači za drugi buffer uzimaju se iz fajla bajtovi od (4k-strlen)-tog do (8k-strlen), pa onda za treći buffer od (8k-2*strlen) do (12k-2*strlen). Vidi se da se ovaj množilac povećava, pa će do kraja pretrage biti straćeno strlen*brojparčića memorije, a i vremena zbog duplog prelaska.
 
Poslednja izmena:
Ne. Ti iz fajla uvek čitaš 4k podataka i ne čitaš dva puta iste podatke. Znači, fajl se sekvencijalno čita u blokovima od 4k. Takođe koristiš uvek isti bafer, tako da se ne troši puno memorije.

Recimo da tražiš string dužine 256 (i da ne radimo sa unicode stringovima).

Rezerviše se bafer u memoriji od 4096 + 256b + 1 (ili 8192 ako memorija mora da se rezerviše u celim stranama).
Iz fajla pročitaš 4k bajtova u prvih 4k bafera, dodaš 0x00 na kraj (na 4096 pozicji).
Pretražiš bafer sa strstr().
Prekopiraš poslednjih 256 (strlen) bajtova iz bafera na početak bafera, od pozicije 256 upišeš sledećih 4k bajtova iz fajla, dodaš 0x00 na kraj.
Pretražiš bafer sa strstr().
Ponavljaš dok ne nađeš traženi string.

U slučaju da je string koji tražiš veći od 4k, iz fajla čitaš veću količinu podataka po iteraciji (n*4k, za najmanju vrednost n gde je n*4k veće ili jednako dužini stringa).


edit: To je najjednostavnije rešenje. Ali pošto je, za neki opšti slučaj, teško napraviti funkciju bržu od strstr(), a da ne pojede puno memorije, ja bih počeo odavde, pa gledao gde je bottleneck.

edit2: Ako su to neki fajlovi koji se ne menjaju tako često, možda bi veće ubrzanje donelo keširanje najčešćih rezultata nego optimizacija same funkcije za pretragu?
 
Poslednja izmena:
Aha ti misliš da se ne ide preko mmap() nego obično sekvencijalno čitanje. Onda znači treba da se kopira strlen bajtova sa kraja na početak buffer-a, a u ostatak da se učita sledeći deo iz fajla.
 
Poslednja izmena:
Odlicno... ovo odgovara na pitanje koje sam hteo gore da postavim - sta da radim sa strstr() ako je deo u jednom, deo u drugom bufferu. Kopiranje SERACH_PATTERN_LENGTH karaktera pre sledece stranice bi se resio taj problem.
E sad kad bi strstr radio pattern matching 🙂 Ali to ce biti manji problem, imam vec vektorizovanu alternativu za to.

Moze sada podpitanje... sta ako pattern moze biti veci od buffera? Buffer ne smem da povecavam jer se lako moze desiti da ima 10.000 provera u isto vreme, pa u tom slucaju ni sa 64KB bufferom necu imati dovoljno memorije.
Recimo da imam PtrMatch (nesto kao strstr samo za patterne) ovako:
PtrMatch(szBuf, dwBuf, szPattern, dwPattern)
szBuf je bafer koji se pretrazuje, szPattern je pattern kojim se szBuf proverava (string pattern, nesto kao regular expressions ali dosta prostije - file name matching je recimo slican dosta)
dw* su duzine pointer - nema NULL pointer.

Ovako nesto vidim kao jedini nacin cak da se radi provera ako pattern moze biti veci od buffera (opisujem proveru kada se vec zna da je pattern veci, tj. ovo je podrutina za taj podslucaj, ne celokupna)
- ucitavanje 4K buffera
- provera PtrMatch(szBuf, dwBuf, szPattern, 4096)
- no match, PtrMatch(szBuf + 1, dwBuf - 1, szPattern, 4095)
...
- match
- ucitavanje sledeceg buffera 4K
- PtrMatch(szBuf (novi), dwBuf, szPattern+PrethodniMatchedChars, Min(4096, dwPattern - PrethodniMatchedChars)

Izgleda dosta komplikovano bez konkretnog koda... ima li neko ideju za optimizovaniji pristup, jer ce ovde u sustini biti FILE_SIZE komparacija 🙁
 
ivan90BG je napisao(la):
Aha ti misliš da se ne ide preko mmap() nego obično sekvencijalno čitanje. Onda znači treba da se kopira strlen bajtova sa kraja na početak buffer-a, a u ostatak da se učita sledeći deo iz fajla.
Kliknite za proširenje...

Ista stvar samo drugi ime poziva u sustini cim ce se jednom samo prelaziti svaka stranica. Jedino se mora imati na umu da ne postoji mogucnost da se mapira ceo file odjednom, znaci sigurno mora iz delova.
 
A kakav ti je to string patern, da nije nešto sa zvezdicama za bilo koji znak ili niz znakova?
 
Yep. Nesto tipa *predmet.doc* (sto bi moglo i mojpredmet.docx da uzme u obzir).

Radim neke testove performansi i imam utisak da ce odustati od ovoga tj. da ce ostati samo case-insensitive string match.
 
A jel to treba da nađe reči bez razmaka ili sa razmacima. Ako se otkuca *nesto*, i ako ga nađe mogao bi da matchuje ceo fajla (jer zvezdica matchuje sve), ili se možda u fajlu nalaze redovi razdvojeni newline oznakom ili nulom (\0). A i kakav to drajver radi ovakve stvari (pretraživanje fajlova većih od 200MB)?
 
Antivirus recimo radi to 🙂 I mnogo kompleksnije stvari.
Ne mora da se brine za newline, whitespace i slicno. Sve se to smatra razmakom i prekida pretragu sem ako search pattern explicitno nema taj znak u sebi.
Pretraga je vise binary search nego ASCII/UNICODE.
 
Pa antivirus nije drajver.

Aj daj neki primer stringa za pretragu, šta može da sadrži, kakav fajl može biti.
 
Antivirus bas jeste driver 🙂 Tj. realtime engine je driver uz minimalnu komunikaciju sa user mode-om. Ovo sto ja radim nije AV niti slicno ali opet je u driveru pretraga.

Primet koji sam dao je stvaran primer:
*predmet.doc*
DaLiMeneIma
 
alfaunits je napisao(la):
ima li neko ideju za optimizovaniji pristup, jer ce ovde u sustini biti FILE_SIZE komparacija 🙁
Kliknite za proširenje...

Ako već imaš samo pattern za uparivanje imena fajla - zbog čega ne možeš da čitaš fajl u segmentima i te segmente prosleđuješ na uparivanje sa paternom. Kraj bloka za uparivanje su ti određeni karakteri (0x00, 0x0A,...), ali ne i kraj bafera. Tako da sledeći bafer nastavlja uparivanje kao da je bio deo prethodnog.

Nešto ovako (na brzinu napisano, sigurno ne radi za neke granične slučajeve):

- Koriste se ?(jedan karakter) i *(jedan ili više karaktera).
- 0x00 označava kraj bloka. Kraj bafera ne označava kraj bloka.


PatternMatcher.h
Kod: 
#include <vector>

#pragma once

class PatternMatcher
{
	enum SearchMode
	{
		INVALID = -1,
		SINGLE_MATCH = 0,  
		SINGLE_JOKER = 1,
		MULTI_JOKER = 2,
	};

public:
	PatternMatcher(CStringA pattern);
	~PatternMatcher(void);

	
	void AddTextBuffer(const unsigned char *bufferStr, unsigned int bufferSize);    //Add text buffer and try to match patterns
	
protected:
	const CStringA patternString;	

	std::vector<unsigned int> *indexList; 

	unsigned int positionOffset; 
	
	SearchMode searchMode; 

	int patternIndex, patternSize, lastAsteriskIndex;
	unsigned char patternChar, nextPatternChar;
	bool blockStarted;
	bool matchFlag;
	unsigned int blockAbsIndex;
	
	void RegisterMatch();
	void InitBlock();   //Init everything for begining of new block
	void SetMode();		//Set search mode depending on pattern char
};

PatternMatcher.cpp
Kod: 
#include "StdAfx.h"
#include "PatternMatcher.h"


PatternMatcher::PatternMatcher(CStringA pattern) : patternString(pattern)
{
	positionOffset = 0;
	indexList = new std::vector<unsigned int>();
	blockStarted = false;
	patternSize = patternString.GetLength();
	positionOffset = 0;
	InitBlock();

	return;
}

void PatternMatcher::SetMode()
{
	if(patternIndex >= patternSize)
	{
		searchMode = INVALID;
		return;
	}

	patternChar = patternString[patternIndex];

	searchMode = SINGLE_MATCH;

	if(patternChar == '*')
	{
		searchMode = MULTI_JOKER;
		lastAsteriskIndex = patternIndex;
	}

	if(patternChar == '?')
		searchMode = SINGLE_JOKER;
	
	return;
}

void PatternMatcher::InitBlock()
{
	patternIndex = 0;
	lastAsteriskIndex = -1;
	nextPatternChar = '*';
	matchFlag = true;
	
	SetMode();

	return;
}

void PatternMatcher::RegisterMatch()
{
	indexList->push_back(blockAbsIndex);

	return;
}

void PatternMatcher::AddTextBuffer(const unsigned char *bufferString, unsigned int bufferSize)
{
	const unsigned char *bufferPtr = bufferString, *limitPtr = bufferString + bufferSize - 1;

	while(bufferPtr <= limitPtr)
	{
		if(searchMode == MULTI_JOKER)
		{
			if(nextPatternChar == *bufferPtr)
			{
				patternIndex++;
				SetMode();
			}
		}

		if( (blockStarted == true) && (matchFlag == false) && (*bufferPtr != 0x00) )  //Skip to end of the block if match failed
		{
			bufferPtr++;
			continue;
		}
		
		if (blockStarted == false)
		{
			if (*bufferPtr == 0x00)
			{
				bufferPtr++;
				continue;
			}
		
			InitBlock();
			blockAbsIndex = (bufferPtr - bufferString) + positionOffset;
			blockStarted = true;
		}

		if (blockStarted == true)
		{
			if(*bufferPtr == 0x00) //Block closed
			{
				blockStarted = false;
				
				if(patternString[patternIndex] == '*')
					patternIndex++;

				if(patternIndex != patternSize)
					matchFlag = false;

				if(matchFlag == true)
					RegisterMatch();

				bufferPtr++;
				continue;
			}

			//MATCHING
			if(searchMode == INVALID)
			{
				matchFlag = false;
				continue;
			}

			if(searchMode == SINGLE_MATCH)
			{
				if(*bufferPtr != patternChar)
				{
					if(lastAsteriskIndex == -1)
						matchFlag = false;
					else
					{
						patternIndex = lastAsteriskIndex;
						nextPatternChar = '*';
						bufferPtr--;
						SetMode();
						continue;
					}
				}

				bufferPtr++;

				patternIndex++;
				SetMode();

				continue;
			}

			if(searchMode == SINGLE_JOKER) //one
			{
				bufferPtr++;

				patternIndex++;
				SetMode();

				continue;
			}

			if(searchMode == MULTI_JOKER) //one or more
			{
				bufferPtr++;
				nextPatternChar = patternString[patternIndex + 1];

				continue;
			}
		}
	
	} //while

	positionOffset += bufferSize;

	return;
}
PatternMatcher::~PatternMatcher()
{
	delete indexList;

	return;
}




test - pattern je veći od bafera. Pronaći će jedan match na poziciji 0 i jedan match na poziciji 18.

Kod: 
PatternMatcher *patternMatch = NULL;
unsigned char *textBuffer = NULL;

textBuffer = new unsigned char [64];
memset(textBuffer, 0x00, 64);
				
patternMatch = new PatternMatcher("*testFile*");
			
memcpy(textBuffer, "firs", 4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "ttes", 4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "tFil", 4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "e.do",4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "c\x00se",4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "cond", 4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "test", 4);
patternMatch->AddTextBuffer(textBuffer, 4);

memcpy(textBuffer, "File.txt\x00", 9);
patternMatch->AddTextBuffer(textBuffer, 9);

		
delete patternMatch;
delete [] textBuffer;




edit:
Ako koristiš regexp onda sve jedno moraš da praviš stejt mašinu, tako da sve ovo pada u vodu. 🙂
 
Poslednja izmena:
Nema kraj bloka za poredjenje. Kraj bloka je ceo file. String radi iskljucivo po principu duzine, kao u Delphiu otprilike, znaci \0 je validan karakter koji se uporedjuje.
Trebalo mi je vremena da shvatim kod, ali cini mi se kao dobra ideja. Probacu da ovako nesto implementiram u C-u sa counted stringovima.
vector je pretpostavljam dinamicki niz? Tako nesto nece moci da prodje 🙂
EDIT: Vidim da nije ni bitan u sustini indexList.
 
Poslednja izmena:
OK. Ja sam ovde pretpostavio da su celine za pretraživanje (blokovi) odvojeni karakterom 0x00 i da se mogu protezati kroz više različitih bafera. Ideja je da se ne radi nikada backtracking kroz tekst koji se pretražuje (pošto isti nije dostupan kada se učita sledeći bafer), nego da se backtracking radi isključivo na search patternu koji ceo imamo u memoriji.

Kreće se od početka paterna i bafera:
- ako je znak u paternu karakter koji nije joker (* ili ?) proverava se da li je isti kao onaj u baferu, prelazi se na sledeći znak u paternu i u baferu.
- ako je znak u paternu joker za jedan znak (?), ne vrši se provera. Prelazi se na sledeći znak u paternu i baferu.
- ako je znak u paternu asterisk, ne vrši se provera i beleži se pozicija asteriska. Prelazi se na sledeći znak u baferu, sve dok sledeći znak u baferu nije isti kao sledeći znak u paternu. Kada se naiđe na isti znak, prelazi se na sledeći znak u paternu. (nije predviđen patern koji u sebi ima sekvencu *?).

Pozicija asteriska u paternu se pamti da bi mogli da se vratimo na njega u slučaju da znak posle asteriska u paternu nije uparen sa onim u baferu. Time se praktično proširuje skup znakova koje smo uparili sa asteriskom.

Primer:

patern: *testFile*
string: firsttestFile.doc

Asterisk će se upariti sa firs, a zatim će t da se upari sa sledećim t (*t = first). U paternu nam je sledeći znak e, a u stringu opet t. Zato se vraćamo na asterisk i time proširujemo skup znakova koji smo mu pridružili - *t == firstt. Posle toga imamo uspešno uparivanje.

Uslov za uspešno uparivanje je da smo stigli do kraja bloka, i da smo stigli do kraja paterna. Ili smo stigli do poslednjeg karaktera u paternu, a on je asterisk. I naravno da je matchFlag ostao true.

U slučaju da smo stigli do kraja paterna a ne i do kraja bafera uparivanje nije uspelo.



indexList je std::vector (dinamički niz) i ne služi ničemu - osim da u njega smestim rezultate gde je pattern pronađen. To je praktično placeholder za kod koji nešto treba da uradi sa tim pronađenim stringovima.
 
Morate se prijaviti ili registrovati da odgovorite ovde.
Nazad
Vrh Dno