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