home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C!T ROM 2
/
ctrom_ii_b.zip
/
ctrom_ii_b
/
PROGRAM
/
PASCAL
/
SEARCHBM
/
POSBM.DOC
< prev
next >
Wrap
Text File
|
1988-07-01
|
13KB
|
228 lines
Faster String Searches
Dr. Dobb's Journal #153 July 1989, p.74 and 98.
-----------------------------------------
Boyer-Moore may be the algorithm you need
-----------------------------------------
by Costas Menico
Costas Menico is a senior software developer and part owner of The
Software Bottling Company. He can be reached at 6600 Long Island
Expressway, Maspeth, NY 11378.
While programming several of my company's products, I have many times
come across the need to perform a string search to accomplish a certain
task. A string search is the function used to find a string A (the
pattern) in a string B (the text) and return the position of A in B.
After realizing that the built-in string search functions of many
language compilers used simple brute-force algorithms, I set out to
find and implement an equivalent string-search function that would
perform at a fraction of the speed of the built-in function.
The Brute-Force Method
As the name implies, the brute-force method of performing a string
search involves an exhaustive search from the start of the pattern
until there is a match or the end of the string is reached.
Each character in the pattern is compared left to right with each
character in the string. The scanning is continued until all of the
characters in the pattern match an equivalent length in the string. If
no match occurs, the pattern is moved one character to the right and a
new search is begun.
Assume we want to search for the pattern HEAD in the string
"MAXIMOODHEADROOM". The search is shown in Figure 1. The method shown
is time-consuming, because every character in the string must be
compared with every other character until a final match is found. Nine
steps were taken to discover the sample pattern. Using a program that
must perform thousands of searches is a time-consuming way of looking
up a pattern.
+--------------------------------------------------------------------+
| Pattern = H E A D |
| String = M A X I M O O D H E A D R O O M |
| |
| 1) H H Does not match, move right. |
| 2) H H Does not match, move right. |
| 3) H H Does not match, move right. |
| 4) H H Does not match, move right. |
| 5) H H Does not match, move right. |
| 6) H H Does not match, move right. |
| 7) H H Does not match, move right. |
| 8) H H Does not match, move right. |
| 9) H E A D HEAD finally matches. |
+--------------------------------------------------------------------+
Figure 1: Brute-force search
The Boyer-Moore Method
After looking through some impressive (and complex) algorithms, I came
across an elegant and easily implemented algorithm called the Boyer-
Moore method, named for the pair of scientists who invented it. This is
a hybrid algorithm that uses pattern analysis combined with brute
force.
To implement the algorithm in assembler, I used MASM and linked it into
Turbo Pascal 4.0. The algorithm is also easily converted to work with C
and Basic. For the assembly language program (called POSBM), see
Listing One, page 98; for the benchmark test program see Listing Two,
page 99.
The basic idea behind the Boyer-Moore technique is the movement of the
pattern more than one character at a time during the search for a
matching character. This saves search steps, thereby increasing search
speed. You may wonder how a whole pattern can be moved to the right
without a search through any of the characters in between. The answer
is simple. All that is required is a 256-character array that defines
the pattern. This array (called a SKIPARRAY) is built every time the
search function is called. Each position corresponds to the value of
each character in the ASCII character set.
The algorithm is simple. A SKIPARRAY of 256 bytes is filled with the
length of the pattern. Starting from the right of the pattern, each
character is read and its offset placed into the SKIPARRAY, using the
characters ASCII value as the index (see Figure 2).
+--------------------------------------------------------------------+
| A B C D E F G H I ... Z |
| SKIPARRAY position ... 65 66 67 68 69 70 71 72 73 ... 91 |
| Original values 4 4 4 4 4 4 4 4 4 ... 4 |
| Values with "HEAD" 1 4 4 0 2 4 4 3 4 ... 4 |
+--------------------------------------------------------------------+
Figure 2: SKIPARRAY values with the HEAD pattern
The pattern is then placed against the string for the search. At the
rightmost position of the pattern the corresponding character in the
string is read and its ASCII value ist used as an index into the
SKIPARRAY. The value in the SKIPARRAY will determine how far to slide
the pattern to the right, with one exception. A value of 0 means that
the rightmost character in the pattern is lined up with an exact
character in the string. Because this is a possible match, a reverse
compare is performed on the remaining characters in the string (that
is, a reverse brute-force compare). If the pattern matches, the offset
is noted in the string. Otherwise, the pattern slides over by one
position and the process is repeated.
To better explain this process I will use as an example the pattern
HEAD. The SKIPARRAY is first filled with the length of the pattern.
Once this is completed the SKIPARRAY will contain 4s in all 256
positions.
Next, we put the skip value for each character in the pattern into the
SKIPARRAY. To do this, the offset of each character is taken from the
end of HEAD and placed at the ASCII position in the SKIPARRAY. For the
pattern HEAD, the SKIPARRAY is transformed by putting in the
corresponding values of 3, 2, 1 and 0 at 72 (H), 69 (E), 65 (A) and 68
(D) positions (see Figure 3).
+--------------------------------------------------------------------+
| Pattern = H E A D |
| String = M A X I M O O D H E A D R O O M |
| 1) H E A D |
| 2) H E A D |
| 3) H E A D |
| 4) H E A D |
+--------------------------------------------------------------------+
Figure 3: Using Boyer-Moore, we find a match in four steps
The pattern is then scanned right to left to determine how far to move
the pattern for each character in the string. To find the pattern HEAD
in MAXIMOODHEADROOM, HEAD is positioned at the start of the string.
This places the character D of the pattern HEAD under the character I
in the string (see step 1 in Figure 3).
Because there is no match, that is, D is not equal to I, the SKIPARRAY
is indexed at the position of the value for I, which is found to be 4.
As I is not in the pattern, HEAD is positioned four characters to the
right of the mismatched position.
The D in the pattern (see step 2 in Figure 3) is now positioned under
the D in the string. This indicates, that the last character of the
pattern matches the corresponding character in the string. We therefore
proceed to match the remaining characters by using a reverse brute-
force method. In this case, the A in the pattern will not match the O
in the string. Because this was a brute-force compare, we only move the
pattern one character to the right.
The D (see step 3 in Figure 3) is now positioned under the H in the
string. As D is not equal to H, we index into the SKIPARRAY and find
that the skip value for H is three. HEAD now slides to the right three
characters.
The D in the pattern (see step 4 in Figure 3) is again lined up under
the D in the string. By comparing the remaining characters of HEAD
backwards from the D position, we find that the pattern matches
successfully and record the starting position in the string.
The program used to perform the Boyer-Moore search method is shown in
Listing One. It is assembled using MASM (or TASM) and the OBJ file is
linked in to the Turbo Pascal program. It is called by using the name
POSBM the same way you would call the POS() function in Turbo Pascal.
The way this is set up will only work on parameters of type STRING (see
Listing Two), which limit the search to 255 characters. You can easily
modify the program to pass arrays the same way they are passed in C.
To call POSBM from C you must modify the structure CSTK to conform to
the C calling sequence. You must change the initial code to copy the
addresses of the PATADDR and STRADDR from the calling stack, to PATTXT
and STRTXT. The length of the strings must also be computed (by
searching for a 0 using a SCASB instruction) and placed in the
variables PATLEN and STRLEN. Last, the way in which you return from the
function should be changed to leave the calling values on the stack.
Note that the function POSBM is declared FAR.
Limitations to the Boyer-Moore Method
Some patterns may not be suitable for this method. If your pattern has
repeating characters matching against a text of repeating characters,
the Boyer-Moore method will actually be slower than brute-force. For
example, the bit-map pattern 01111111 in a bit-map string of all
11111111 would require a lengthy search because the 0 in the pattern
would not be compared until all the 1s have been matched from right to
left. The pattern would then be moved over by one position and the
search tries again, thus defeating the algorithm's purpose.
There have been some clever ways to avoid this problem by analyzing the
pattern but, for all intents and purposes, the simple algorithm works
very well for text searches.
Benchmarks
To illustrate the speed difference between brute force and Boyer-Moore,
I have put together a small test program that compares the speed of the
built-in function POS() of Turbo Pascal 4.0 (which uses the brute-force
method) and the assembly language function POSBM() presented in this
article.
To run the program, you must first assemble the function POSBM.ASM on
Listing One with MASM or TASM. This will create an .OBJ module. Next,
compile the Turbo Pascal program in Listing Two. The function will be
linked in when the {$L POSBM.OBJ} directive is encountered. Because the
function is declared as FAR, we must include the directive {$F+} in the
program to notify Pascal that the function should be called with FAR
instructions.
The program starts out by generating a random string 255 characters
long and uses the last five characters of the string as the pattern.
The pattern is then searched in the string using POS() and POSBM() by
putting the searches in a long loop to emphasize the time difference.
You may want to increase the value of 'longloop' if you have a fast
machine to see the significantly higher start and end times. The
POSBM() is usually 400 percent faster than the POS() function.
Conclusion
I have used this algorithm in a number of programs with impressive
results. If you're looking for a way to speed up your program, check to
see if the bottleneck is your string search functions. The Boyer-Moore
algorithm will give immediate results.
Man at the keyboard: Tom Weitzel #114
224 Winthrop Avenue
Lawrence MA 01843
(508) 975-2834
U.S.A.