Return to pep4grep.doc2 CVS log

Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / grep / README

Annotation of 43BSDReno/usr.bin/grep/README/pep4grep.doc2, revision 1.1

1.1     ! root        1: >From postnews Tue Mar 18 18:05:22 1986
        !             2: Subject: More Pep for Boyer-Moore Grep (part 2 of 2)
        !             3: Newsgroups: net.unix
        !             4: 
        !             5: #  "Gratiano speaks an infinite deal of nothing, more than any man in all
        !             6:    of Venice.  His reasons are as two grains of wheat hid in two bushels of
        !             7:    chaff:  you shall seek all day ere you find them, they are not worth
        !             8:    the search."  -- Shakespeare, Merchant of Venice
        !             9: 
        !            10: ... or, part 2, "Reach out and Boyer-Moore Egrep Someone"
        !            11: 
        !            12:      Maybe you never use 'grep'.  Then ignore this.  But if you do, why not
        !            13: use the best algorithm?  Serious addicts know that for unstructured yet
        !            14: stable text, B-trees are used for speed, or something like Lesk's nifty
        !            15: (and unavailable) 'grab' suite for inverted files are ways to go.  Barring file
        !            16: inversion daemons for netnews and other ephemera, we are limited to the
        !            17: present improvements.
        !            18: 
        !            19:      Proper skeptics should question why a nearly I/O-bound program (but
        !            20: not for any CPU with less than the power of several VAX MIPS, alas) should
        !            21: be made more so.  The question was posed in B & M's classic 1978 CACM
        !            22: paper -- the answer then was to free up more CPU cycles for timesharing.
        !            23: Now, our motivations are more mundane (we won't have desktop 5 MIP machines
        !            24: for another year), but not only that, we've discovered that the Cray 2's
        !            25: standard 'egrep' is also very anemic, performing 8-12 times as worse as ours
        !            26: on simple patterns.  For shame, especially since hearing of the rumor that
        !            27: certain group theorists have a search application ready for testing.
        !            28: Boyer-Moore could fill in until a Cray vectorizing C compiler shows up.
        !            29: Sheer speed for machines whose filesystems are cached in memory is nice too.
        !            30: 
        !            31:      A quick-and-dirty rundown of the debts to which the new hybrid pays
        !            32: now follows.
        !            33: 
        !            34:        Thompson, K. T. (CACM, November 1968):
        !            35:                Regular Expression Search Algorithm.  As usual, obvious
        !            36:                once you understand it.  The current 'egrep'.  Still
        !            37:                useful as a base.  Abstracted by Aho/Ullman as Algorithm
        !            38:                9.1 in Design and Analysis of Computer Algorithms.
        !            39: 
        !            40:        Boyer/Moore:
        !            41:                Not quite pre-Unix.  Oh well.  Modern designers should
        !            42:                know better now, if they want their stuff to get out there.
        !            43:                By the way, I haven't used delta2 (or 1) since the O(mn) case
        !            44:                case doesn't come up too often.  Sure Knuth stood on his head
        !            45:                to better the linearity, but his proof had a bug in it until
        !            46:                the 1980 SIAM J. Comput. retraction.  Would you want to code
        !            47:                something that even Knuth trips up on?
        !            48: 
        !            49:                Now to assuage nagging feelings that geneticists might want
        !            50:                to search entire libraries of 9000-unit nucleotide protein
        !            51:                sequences for ((AGCA|TTGCA).*TGC)|AGCT)?T?A+ or some nonsense
        !            52:                which MIGHT be nonlinear, you would want delta2.  So convince
        !            53:                someone to do the Galil/Apostolico/Giancarlo 2n comparison
        !            54:                worst case stuff.  See egrep.c for reference.
        !            55:                
        !            56:        Gosper, W. (HAKMEM 1972):
        !            57:                Gosper didn't get around to the Thompson-like machine until
        !            58:                1972 with HAKMEM.  His PDP 10 code is nevertheless valiant.
        !            59:                He is also (barely) credited with conceiving the backwards
        !            60:                match idea independently.  Where is he now?
        !            61:                
        !            62:        Morris/Pratt:
        !            63:                Nice guys, but for this purpose, has-beens.
        !            64:                Neat to see a hacker's triumph bury some theory.
        !            65: 
        !            66:        Horspool (Software Practice & Experience, 1980):
        !            67:                Now here's a Canadian after the heart of things
        !            68:                (perfect hashing, text compression, NP-complete
        !            69:                code generation probs., etc.)  Did some Amdahl
        !            70:                timings to show that delta2 is not so hot.
        !            71:                Knows about Search For Least Frequent Character First,
        !            72:                which is useful for short patterns. 
        !            73: 
        !            74:        {,e,f}grep man page:
        !            75:                The laughable bugnote "but we do not know a single algorithm
        !            76:                that spans a wide enough range of space-time tradeoffs"
        !            77:                certainly presumes that there is no such thing as switching
        !            78:                logic.  How the 'grep' family got into a multiple-version
        !            79:                mess is probably a Guy Harris story; 'egrep' looks like the
        !            80:                winner, as its functionality is pretty much a superset of
        !            81:                the other two.  The K & P teaser (p. 105) offers hope for
        !            82:                unification, but we see no difference with extant V8 code.
        !            83: 
        !            84:      "Not cited in the text" -- the sexy randomized Karp/Rabin string searcher
        !            85: (Sedgewick, Algorithms, or Karp's Turing Award Lecture), and the ribald classic
        !            86: Time Warps, String Edits, and Macromolecules -- The Theory and Practice
        !            87: of Sequence Comparison (Kruskal & Sankoff).  Inquire within.
        !            88: Thanks for your patience,
        !            89: 
        !            90:      James A. Woods (ames!jaw)
        !            91:      NASA Ames Research Center
        !            92: 
        !            93: P.S.
        !            94:      Current applications for Boyer-Moore code include modification of 
        !            95: 'fastfind' for true speed, as well as substring search for 'grab', both
        !            96: benefiting from BM-style search thru incrementally-compressed files/indices.
        !            97: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.