home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume4 / bm1.2 / README < prev    next >
Text File  |  1986-11-30  |  2KB  |  51 lines
  1. Bm is a fast pattern matching utility, intended to be almost
  2. identical in functionality to fgrep (ugh!) but much faster. It uses
  3. the Boyer-Moore algorithm, as described in the papers listed below:
  4.  
  5. D.E. Knuth, J.H. Morris, V.R. Pratt,"Fast Pattern Matching in Strings", 
  6. SIAM J. Comput., 6(2), June  1977, 323-350, 
  7.  
  8. Z. Galil,
  9. "On Improving the Worst Case Running Time of the Boyer-Moore String
  10. Matching Algorithm", 
  11. CACM, 22(9), Sept. 1979, ACM, 
  12.  
  13. R.S. Boyer, J.S. Moore,"A Fast String Searching Algorithm", CACM, 20(10), 
  14. Oct. 1977, 762-772, 
  15.  
  16. G. de V. Smit,"A Comparison of Three String Matching Algorithms", 
  17. Software - Practice and Experience, vol. 12,  1982, 57-66, 
  18.  
  19. *** NOTE *** There are certain system dependencies in the code.
  20. Please check whether your system uses "index" or "strchr" to
  21. find a character in a string: this affects MkDescVec.c.
  22. Also check whether your system uses <strings.h> or <string.h>.
  23. This affects match.c/bm.c, MkDescVec.c, and PrintLine.c.
  24. Also check whether your system has "bcopy". If so, see MoveResidue.c
  25.  
  26. The files are MkDescVec.c, PrintLine.c, bm.c, and 
  27. Execute.c: search a file for the patterns
  28. Extern.h: declarations of externs
  29. GetPatFile.c: read in patterns from a file and set up a vector of
  30.     pattern descriptors
  31. Global.c: global variables (complement to Extern.h)
  32. MakeDesc.c: create a pattern descriptor for one pattern, including
  33.     skip tables, etc.
  34. MakeSkip.c: make the skip tables for one pattern
  35. Makefile: you can figure this one out for yourself
  36. MatchFound.c: what to do when you actually FIND a pattern - print it,
  37.     update flags, etc.
  38. MkDescVec.c: make a vector of pattern descriptors, given a string
  39.     of newline-separated patterns
  40. MoveResidue.c: when you come to the end of the buffer, move the
  41.     unsearched "residue" to the beginning and start again
  42. PrintLine.c: print the appropriate stuff after finding a match
  43. PutUsage.c: mini-man page.
  44. README: this file
  45. Search.c: the guts. Implements B-M algorithm given a pattern, skip
  46.     tables for the pattern, and a buffer to search
  47. bm.c: mainline. mostly interpreting the command line and tidying
  48.     up at the end. Calls Execute for each file.
  49. bm.h: constants
  50. bm.p: man page
  51.