home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / myers.grep / README < prev   
Text File  |  1998-07-14  |  4KB  |  100 lines
  1.                                              July 13, 1998
  2.  
  3. This is the code archive for the experiments performed in the paper
  4.  
  5. "A Fast Bit-Vector Algorithm for Approximate String Matching
  6.  Based on Dynamic Programming",  by Gene Myers
  7.  
  8. UNBUNDLING:
  9.  
  10. To unbundle the code archive, get the file "package" and then say
  11. "sh package" on any UNIX box and the contents will unpack in the
  12. current directory.  The package is not gzipped or otherwise compressed
  13. as it is very modest in size to begin with.
  14.  
  15. PROGRAM DESCRIPTIONS:
  16.  
  17. We developed codes for the approximate string matching algorithms listed
  18. below.  The parameters used to describe the algorithms' performances are
  19. N = text length, M = pattern length, K = number of errors, S = size of
  20. alphabet, and W = size of machine word in bits.
  21.  
  22. ukk:
  23.   E. Ukkonen, "Finding approximate patterns in strings",
  24.       J. of Algorithms 6 (1985), 132-137.
  25.   O(KN) expected time.
  26.  
  27. wmmX:
  28.   S. Wu, U. Manber, and G. Myers, "A subquadratic algorithm
  29.       for approximate limited expression matching",
  30.       Algorithmica 15 (1996), 50-67.
  31.   O(KN/X) expected time with O(6^X) space.  We use X=4 or 5.
  32.  
  33. agrep:
  34.   S. Wu and U. Manber,"Fast Text Searching Allowing Errors",
  35.       Communications of the ACM 35 (1992), 83-91.
  36.   O(NK [M/W] worst-case time.
  37.  
  38. chang:
  39.   W.I. Chang and J. Lampe, "Theoretical and empirical comparisons
  40.       of approximate string matching algorithms", 3rd Combinatorial
  41.       Pattern Matching Conf., Springer LNCS 644 (1992), 172-181.
  42.   O(KN/sqrt(S)) expected time.
  43.  
  44. bngrep and banav:
  45.   R.A. Baeza-Yates and G. Navarro, "A faster algorithm for approximate
  46.       string matching", 7th Combinatorial Pattern Matching Conf.,
  47.       Springer LNCS 1075 (1996), 1-23.
  48.   bngrep is a version that works in only one-word and so is limited to
  49.     the case where (M-K)(K+2) <= W.  O(N) worst-case time in this case.
  50.   banav is the unrestricted version implemented as suggested in an
  51.     as yet unpublished version so it takes
  52.      O(N [ K^2 / (W sqrt(S)) ]) expected time.
  53.  
  54. mygrep and myers:
  55.   This paper.
  56.   mygrep is a version that works in only one-word and so is limited to
  57.     the case where M <= W. O(N) worst-case time in this case.
  58.   myers is the unrestricted version that runs in O(N [K/W]) expected time.
  59.  
  60. Each algorithm has a .c file in the package and each includes two .i files,
  61. main.i and parse.i, common to them all.  main.i is the top level routine
  62. that determines the command line behavior and parse.i is a routine that
  63. parses and encodes a limited regular expression.  Each algorithm is
  64. partitioned into a "setup" subroutine that performs any initialization
  65. neeeded for a search, and a "search" subroutine that performs the search.
  66. "SHOW" and "STATS" conditional compilation flags are used throughout to
  67. selective compile code for debugging and performance statistics respectively.
  68.  
  69. COMPILATION:
  70.  
  71. A makefile is included.  Say "make all" and a version of each algorithm
  72. above gets made plus a "stats" version that separately shows statistics
  73. for a search.  If the name of the program is foo, then the stats-version
  74. is names fooS.  This was done so that timing trials and the parameters
  75. for performance prediction are separated.
  76.  
  77. Say "make data" and the makefile runs a small routine that makes random
  78. texts of length one million for alphabet sizes 2, 4, 8, 16, 32, and 64.
  79.  
  80. USAGE:
  81.  
  82. The command line call to any routine take one of two forms:
  83.  
  84. 1. <name> <pattern> [K] [file]
  85.  
  86. or
  87.  
  88. 2. <name> "<M>,<S>" [K] [file]
  89.  
  90. The parameters M,K,S are as above and all should be given as integers.
  91. File is a text file over which the search is performed.  If ommitted
  92. the standard input is read.  If K is ommitted then K=0 is assumed.
  93. In form 1, give the pattern as a string on the text line, e.g.
  94.  
  95.   agrep "neverfindit" 2 bigoltext
  96.  
  97. In form 2, a random pattern of length M over an alphabet of size S
  98. is generated.  The alphabet in each case is the same one generated
  99. by "genseq.c" that makes the datasets for "make data".
  100.