home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / README < prev    next >
Encoding:
Text File  |  1990-03-16  |  3.3 KB  |  81 lines
  1.  
  2.     DGREP - nopea egrep klooni
  3.  
  4. Dgrep on Unixin egrepin kopio. Ohjelma toimii ainakin PC:ss{, OS/2:ssa
  5. ja Bsd-Unixissa. Lis{ksi se on varsin helppo siirt{{ muihin
  6. ymp{rist|ihin joissa on ANSI C -k{{nt{j{. Dgrepin pit{si olla varsin
  7. yhteensopiva egrepin kanssa lukuunottamatta muutamia optiota.
  8.  
  9. Dgrep on varsin nopea. Nopeus perustuu siihen, ett{ se k{ytt{{
  10. etsitt{v{n merkkijonon mukaan parasta mahdollista algoritmia. Jos
  11. etsitt{v{ss{ merkkijonossa ei ole s{{nn|llisi{ lausekkeita, etsimiseen
  12. k{ytet{{n Boyer-Moore-algoritmia. Muussa tapauksessa dgrep rakentaa
  13. deterministisen tila-automaatin merkkijonon etsint{{n. Hakujen
  14. nopeuttamiseksi s{{nn|llisest{ lausekkeesta pyrit{{n etsim{{n
  15. merkkijono, joka on pakko l|yty{. T{t{ merkkijonoa etsit{{n ensin
  16. Boyer-Moore-algoritmilla. Tila-automaatti k{ytt{{ ns. laiskaa
  17. evaluointia eli tarvittavat tilasiirtym{t lasketaan vain jos niit{
  18. tarvitaan. Molemmat algoritmit ovat lineaarisia.
  19.  
  20. Seuraavassa on vertailtu dgrepin ja systeemin egrepin nopeutta
  21. Bsd-Unixissa. Taulukossa on user- ja sys-ajat muutamalle testille, kun
  22. l{hdetiedostona on ollut /usr/dict/words:
  23.  
  24.         dgrep    system egrep
  25. 'u.*nix'    0.3u    2.4u
  26.         0.4s    0.3s
  27. 'first'        0.2u    2.5u
  28.         0.2s    0.2s
  29. 'first|second'    1.8u    2.2u
  30.         0.3s    0.2s
  31.  
  32. GNUegrepin ja dgrepin nopeusvertailu PC:ss{. Testiaineistona on
  33. k{ytetty dgrepin sorsia kahteen kertaan luettuna, 32 tiedostoa ja 7544
  34. rivi{. GNUegrepill{ k{ytettiin aina optiota -E (== use Egrep syntax).
  35.  
  36.             GNU egrep    dgrep
  37.     Int            11.8         8.1
  38. -ic Int            13.4         8.4
  39.     first|second    28.6        16.9
  40. -c  first|second    19.8        10.8    -- v{hemm{n tulostusta
  41.     Unsigned        10.6         7.9
  42.  
  43. Kirjoittamalla pelkk{ dgrep saa lyhyemm{n aputekstin ja kirjoittamalla
  44. dgrep -h saa seuraavan aputekstin:
  45.  
  46. Usage: dgrep [options] {-f expression file | [-e] expression} [file...]
  47. Options: -An  n lines after the matching line are printed
  48.          -Bn  n lines before the matching line are printed
  49.          -b   filename is displayed only once before matches
  50.          -d   only dfa is used for searching
  51.          -c   only a count of matching lines is printed
  52.          -i   case insensitive match
  53.          -l   only names of files with matching lines are printed
  54.          -n   each line is preceded by its relative line number in file
  55.          -s   silent mode, nothing is printed except error messages
  56.          -t   all files that contain matches are touched
  57.          -v   all lines but those matching are printed
  58.          -x   exact, all characters in expression are taken literally
  59.          -1-9 1-9 lines before and after the matching line are printed
  60.          -e expression, useful when expression begins with -
  61.          -f file that contains expression
  62. Regular expressions:                    .       any single character
  63. *       zero or more repeats            (...)   grouping
  64. +       one or more repeats             ^       beginning of line
  65. ?       zero or one repeat              $       end of line
  66. [...]   any character in set            \c      quote special character c
  67. [^...]  any character not in set        |       alternative ("or")
  68.  
  69. --
  70. muutos versiosta 1.62 versioon 1.71:
  71. T{ss{ versiossa on mahdollista tehd{ nopeampi tila-automaatti
  72. k{ytt{m{ll{ enemm{n muistia.
  73.  
  74. --
  75.  
  76. Dgrepin on tehnyt:
  77.  
  78. Jarmo Ruuth
  79. f30932a@puukko.hut.fi
  80. jruuth@otax.tky.hut.fi
  81.