Gaute Hvoslef Kvalnes gaute@verdsveven.com skreiv i innlegget news:200402251919.28621.gaute@verdsveven.com:
Er det noko med å søkja etter enkeltord, kanskje? Nokre innstillingar gjev iallfall enormt lange (og treige) resultatlister.
Hugsar eg las ein oversiktsartikkel om ulike tekstsøkealgoritmar for nokre år sidan. Det er veldig morosame greier.
Ja, no har eg sett litt på Internett òg. Det er mykje interessant her, for eksempel Boyer-Moore-algoritmen, som er veldig rask, men som òg blir raskare jo lengre søketeksten er! (Eg har ofte opplevd det motsette i program eg brukar.) Algoritmen har seinare blitt forbetra, blant anna av Horspool og Sunday[1], sistnemnte med sin «very fast substring search algorithm» («Quick Search»).
Ein har òg utvikla raske algoritmar for «uklare» søk, jf. f.eks. agrep-algoritmen (det finst endå raskare og betre algoritmar).
Men det mest overraskande for meg, er at ein har utvikla algoritmar for direktesøk i *komprimert* tekst. Her er kva Navarro og Tarhio skriv (dei har fleire artiklar om emnet):
[...] we show experimentally that speedups of up to 30% over the fastest previous approaches are obtained. Moreover, we show that using an encoding method that sacrifices some compression ratio our method is twice as fast as decompressing plus searching using the best available algorithms.
Og:
When searching complex or approximate patterns, our algorithms are up, to 8 times faster than the search on uncompressed text.
Søket støttar òg effektiv dekomprimering av *delar* av teksten direkte, uklare søk og regulære uttrykk.
Dei er so flinke!
[1] Orkar ikkje legga inn referansar. Interesserte klarer å finna dei sjølv!