home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / agrep / agrep.chronicle < prev    next >
Encoding:
Text File  |  1995-05-16  |  8.4 KB  |  173 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. Started in Feb 1991.
  3. This chronicle briefly describes the progress of agrep.
  4.  
  5. Feb/91: The approximate pattern matching algorithm called 'bitap'
  6.     (bit-parallel approximate pattern matching) is designed.
  7.     The algorithm is a generalization of Baeza-Yates' "shift-or"
  8.     algorithm for exact matching.
  9.  
  10. Mar/91: Many extensions of the algorithm 'bitap' are found, especially
  11.     for approximate regular expression pattern matching.  Preliminary
  12.     implementation of the algorithm showed a strong promise for 
  13.     a general-purpose fast approximate pattern-matching tool.
  14.  
  15. Apr/91: Approximate regular expression pattern matching was implemented.
  16.     The result is even better than expected. 
  17.     The design of the software tool is pinned down.
  18.     (For example, record oriented, multi-pattern, AND/OR logic queries.)
  19.     A partition technique for approximate pattern matching is used.
  20.     
  21. May/91: The prototype of "agrep" is completed.
  22.     A lot of debugging/optimization in this month.
  23.  
  24. Jun/91: The first version of agrep is released.
  25.     agrep 1.0 was announced and made available by anonymous ftp 
  26.     from cs.arizona.edu.
  27.  
  28. Jul/91: A sub-linear expected-time algorithm, called "amonkey" for 
  29.     approximate pattern matching (for simple pattern) is designed.
  30.     The algorithm has the same time complexity as that of
  31.     Chang&Lawler but is much much faster in practice.
  32.     The algorithm is based on a variation of Boyer-Moore technique,
  33.     which we call "block-shifting." 
  34.     A sub-linear expected-time algorithm, called "mgrep" for 
  35.     matching a set of patterns is designed based on the "block-shifting" 
  36.     technique with a hashing technique.
  37.  
  38. Aug/91: "amonkey" is implemented and incorporated into agrep.
  39.     It is very fast for long patterns like DNA patterns.
  40.     (But roughly the same for matching English words as the bitap
  41.     algorithm using the partition technique.)
  42.     Prototype of "mgrep" is implemented.
  43.  
  44. Sep/91: "mgrep" is incorporated into agrep to support the -f option.
  45.     An algorithm for approximate pattern matching that combines the 
  46.     'partition' technique with the sub-linear expected-time algorithm 
  47.     for multi-patterns is designed.
  48.     Implementation shows it to be the fastest for ASCII text (and pattern).
  49.     Boyer-moore technique for exact matching is incorporated.
  50.  
  51. Nov/91: The final paper of "agrep" that is to appear in USENIX
  52.     conference (Jan 1992)  is finished.
  53.  
  54. Jan/92: Some new options are added, such as find best matches (-B), 
  55.     and file outputs (-G).
  56.     The man pages are revised.
  57.     agrep version 2.0 is released.
  58.     Fixed the following bugs and change the version to be 2.01.
  59.     1. -G option doesn't work correctly.
  60.     2. multiple definition of some global variables.
  61.     3. -# with -w forced the first character of the pattern to be matched
  62.  
  63. Mar/92: Fixed the following bugs and change the version to be 2.02.
  64.     1. agrep sometimes misses some matches for pipeline input.
  65.     2. the word delimiter was not defined consistantly.
  66.  
  67. ------------------------------------------------------------------------------
  68. bgopal: The following changes were made to the original agrep during 1993-94:
  69.  
  70. 1. Modifications to make main() take multiple options from the same '-' group:
  71.     - the only modifications were in main.c.
  72.  
  73. 2. Now, to make agrep take input from a buffer so that it can be used as a
  74.    procedure from another program. Places where changes have to be done:
  75.  
  76.     - asearch.c/fill_buf(), bitap.c/fill_buf()
  77.     - main.c/read() statements
  78.     - mgrep.c/read() statements
  79.     - sgrep.c/read() statements
  80.     - probably don't have to change scanf in main.c where a y/n is asked.
  81.     - probably don't have to change readdir in recursive.c.
  82.  
  83. I have used fill_buf everywhere for reading things from a file. I have to
  84. verify whether this is actually used to take input in which it has to search
  85. for patterns or to read things REALLY from a file (-f option, file_out, etc.).
  86. If former, then I can simply modify fill_buf to read from an fd or from
  87. an input string. How to specify that string / area of memory is a separate
  88. issue to be resolved during the weekend.
  89.  
  90. I have resolved it. I've also made a library interface for agrep. So 2 is done.
  91.  
  92. 3. Make errno = exit code whenever you return -1 instead of exiting.
  93.  
  94. 4. See if there is a way to avoid copying of memory bytes in agrep
  95.    by using pointer manipulation instead of fill_buf: a part of making agrep
  96.    a callable routine. Important to make it really fast, that's why do this.
  97.  
  98.    Solution:
  99.    ---------
  100.    I think I've solved the problem: but there is a restriction for within the
  101.    memory pattern matching: THE SEARCHBUFFER HAS TO BEGIN WITH A NEWLINE --
  102.    otherwise we cannot avoid the copying. This fact can be checked in the
  103.    library interface.
  104.  
  105.    There are some more problems whose solution I'm not sure of: ask Udi.
  106.    The problem is:
  107.     a. In asearch(), asearch0() and asearch1(), some data is copied after
  108.        the data read in the buffer. Is that crucial? The same thing can be
  109.        seen in bitap(). This is done when num_read < BlockSize -- why?
  110.     b. In sgrep(), the whole buffer is filled with pat[m-1] so that bm()
  111.        does not enter an infinite-loop. Is that crucial if there is an
  112.        equivalent of a single iteration of the while-fill_buf-loop.
  113.  
  114.    I have not modified prepf() to read the multi-pattern from memory, not a
  115.    file.  I have to modify it later (including agrep.c). Function fill_buf now
  116.    simply reads from the fd given: it does not bother about pointer
  117.    manipulation.  Note: wherever there is a while(i<end) loop,
  118.    buffer[0] = buffer[end-1] = '\n'; assignment is made, and wherever
  119.    monkey(..start,end..) is called, the assignment
  120.    buffer[0] = buffer[end] = '\0'; is made. The semantics are consistent
  121.    with what end happens to be.
  122.  
  123.    NOTE:
  124.    -----
  125.    The amount of "space" expected is = length of the pattern. Now, is there a
  126.    way to avoid buserr/segv by using a syscall to find out if buffer+pattern
  127.    is in valid memory? If so, we can return error to user, instead of
  128.    terminating! Painful since we have to trap SIGSEGV and ruin an already
  129.    trapped SIGSEGV, and we don't know if the fault was due to us or them.
  130.  
  131. 5. Is there a way to modify agrep so that it can search through tcompress-ed
  132.    files? One way would be to handle them separately in a function called
  133.    tgrep(), say.  But we would then have to call the functions bitap(),
  134.    mgrep() and sgrep() from WITHIN tgrep() anyway. The other way would be
  135.    to modify the pattern in the beginning and let the normal processing of
  136.    agrep continue.
  137.  
  138.    The next thing would be to uncompress the matched line for printout purposes.
  139.    This is complicated in the sense that -- we might have to look for a literal
  140.    char#10 within verbatim, OR the code for '\n' among the special characters.
  141.  
  142.    Also, we have to search not only for words in the dictionary, but words in
  143.    verbatim too! Moreover, I have to be careful about the exact translation of
  144.    a verbatim/non-verbatim word.
  145.  
  146.    - I'm working on this now: I know the translation algo (its just like
  147.      uncompress) but the interface to agrep (I have to rewrite the input
  148.      handling by myself since the way '\n's are searched for in normal files
  149.      is quite different.  The difficult thing is going backwards and looking
  150.      for the previous '\n' -- I don't have to literally search for '\n' --
  151.      I can remember the position of the previous one. Identifying '\n' in
  152.      sgrep(), mgrep() and other functions has to be changed.
  153.    - Moreover, I have to uncompress a file not from the beginning, but from the
  154.      position of a '\n' to the next '\n' or eof. So compress/uncompress must
  155.      also be callable routines.
  156. **** This including modifications to all routines in sgrep.c and newmgrep.c
  157.      were completed and debugged by Aug '94.
  158.  
  159. 6. What options can be added to agrep as a callable routine so that the output
  160.    can be put into a user-level buffer / returned as values which can be
  161.    examined, etc., so that the thing does not go onto the stdout! Moreover,
  162.    copying the matched lines might not be desirable -- the user might want
  163.    line numbers, or pointers to the beginning of the lines where the match
  164.    occurs and the offset of the match...  (* Callable routine => lots of
  165.    problems! *).
  166. **** These were completed and added into glimpse/glimpseindex in Spring 1994.
  167.  
  168. 7. One other problems with agrep as a callable routine: the variable names used
  169.    by agrep can clash with user defined variable names. Making agrep variables
  170.    static is not going to help since they are accessed throughout agrep code.
  171.    Making code reentrant is not the issue (it is almost impossible!).
  172.  
  173.