2012-11-18

String pattern matching (part 1/?)

Part 1: Finding the needle in a haystack

Background

I have recently learned about the Boyer-Moore-Horspool (BMH) algorithm, but after reading through it again, I realized that there were parts of it I didn't quite understand. I decided to write this article as a way for me to repeat what I've learned and also help others that want to implement this algorithm.

Boyer-Moore-Horspool

BMH pre-processes the string you search for (pattern) to reduce the amount of compares needed when searching through the string you search in (text). The algorithm has an average-case complexity of O(N) and a worst case complexity of O(MN) where N is the text length and M is the pattern length.

A brute force approach to searching for a pattern in a text would be to start by comparing the two first characters in the text and the pattern. If they match, compare the next two and continue until we either have figured out that we've found a complete match or we find a mismatch. Upon finding a mismatch we skip one character ahead in the text and start over again.

Let's see an example of this naïve approach. We'll use the string "dream" as the pattern, and "ice creamer dreamer" as the text to search in (I know it doesn't make much sense, but whatever). I have replaced spaces with underscores to make it easier later to see which character we're dealing with. The red color indicates where a mismatch happen, and the blue indicates a match. The number on the left side indicates how many positions we shift the pattern before the next compare. I also use the character '|' to show the position of the pattern we're looking for in the text.

  iced_creamer_dreamer
  dream        |   |
1  dream       |   |
1   dream      |   |
1    dream     |   |
1     dream    |   |
1      dream   |   |
1       dream  |   |
1        dream |   |
1         dream|   |
1          dream   |
1           dream  |
1            dream |
1             dream|
1              dream

Each blue and red character represents a comparison, so that's a total of 19 compares. There must be a way to do this better! This is where BMH comes in. Let's go through the algorithm step by step. The first step of the algorithm is to start comparing the string from the end, and not the start. In the example below we see that there's a mismatch on the last character. The character in the text that causes the mismatch (whitespace) doesn't occur in the pattern, which means that we can skip ahead the entire length of the pattern.

  iced_creamer_dreamer
  dream
5      dream

But now we have a more complicated situation (below). The mismatch doesn't happen before we hit the d in the beginning of the word. How do we figure out how far we can skip ahead this time?

  iced_creamer_dreamer
  dream
5      dream

Luckily this information is something we can pre-compute based on the search pattern. Say hello to the bad character shift table (BCS). The table contains an entry for each possible character we can encounter in the text, and tells us how far we're allowed to skip ahead if it doesn't match the pattern. This is probably a good time to point out that this approach works perfectly for fixed width character encodings and will also work out of the box with multi-byte encodings if they are self-synchronizing (UTF-8). It's still possible to make it work with encodings that don't meet these criterias, but it requires some extra work that I won't cover here.

First we create a table containing each possible character in the text (128 in the case of ASCII) and fill each entry with the length of the pattern, since this is the default amount of characters we can skip if the mismatched character in the text doesn't appear in the pattern.

Next we iterate over every character in the pattern except the last one and set the shift value of that character to be how far we must move the pattern to align with the character we found in the text. We skip the last character since a mismatch would lead to the same character being compared since it's already in the mismatched position. The BCS table can easily be calculated with the following C-like pseudo code where 'last' represents the index of the last character in the pattern and we use zero-indexed arrays:

for (i = 0; i < MAX_CHARACTER; ++i)
    shift[i] = pattern.length;  

last = pattern.length - 1;
for (i = 0; i < last; ++i)
    shift[pattern[i]] = last - i;

By iterating from start to end, we make sure that we never shift longer than the last character of a certain kind if there are multiple occurrences of the same character. The table generated for the pattern (* here means every character that's not present in the pattern):


*  5 (pattern length)
d  4
r  3
e  2
a  1
m  5 (skipped)

With the BCS table made, it's time to go back to our example and study it again. The first mismatch happens on the whitespace as before, which gives us an offset of 5.

  iced_creamer_dreamer
  dream        |   |
5      dream   |   |
5           dream  |
3              dream

Well that was easy, and we reduced the amount of compares to 12. The algorithm seemed to work for the test string, but we haven't quite solved the problem yet. Look at the example below where the pattern is "ram ram", and the text is "rum ram ram tam" (another nonsensical string, but I can't be bothered to find good examples that make sense). We get a mismatch between the characters 'u' in the text and 'a' in the pattern. 'u' doesn't exist in the pattern, so we consider it safe to shift the entire length of the pattern, but that makes us overshoot an occurrence of the pattern in the text.

  rum_ram_ram_tam
  ram_ram
7        ram_ram

The reason for this is that the BCS table values tell us how long we need to shift the string if the mismatch happen on the last character, but here it happens on the second. There are at least two ways of handling this problem. The Boyer-Moore way is to subtract the amount of matches we have already found from the BCS. This might lead to negative shifts, but the Boyer-Moore algorithm will always choose the larger of two shifts (bad character and good suffix) which will solve this issue. The Horspool solution is to always use the last character of the compared text. In this case we would use 'm' which gives us a shift of 4 and therefore puts us directly at the pattern we're searching for.

  rum_ram_ram_tam
  ram_ram   |
4     ram_ram

It is worth pointing out that this solution has some bad side effects in very special cases. If the two last characters are the same, then any mismatch that doesn't happen on the last character will lead to a shift of only one. This isn't a big issue since we usually see a lot of mismatches on the first character comparison, and a shift of just one will most likely be followed by a larger shift, but it's something to keep in mind.

Let's sum it all up in some more pseudo code to make it clearer:

for (i = 0; i < MAX_CHARACTER; ++i)
    shift[i] = pattern.length;  

last = pattern.length - 1;
for (i = 0; i < last; ++i)
    shift[pattern[i]] = last - i;

pos = 0;
while (pos < (text.length - pattern.length)) {
    i = last;
    while (pattern[i] == text[pos + i]) {
        if (i == 0)
            return pos;
        ++i;
    }
    pos += shift[buffer[pos + last]];
}


One last thing before we're done. Let's say we want to find all occurrences of the pattern in the string and want to jump as far as possible after each match we find. Lets start with a couple of examples:

One last thing before we're done. Let's say we want to find all occurrences of the pattern in the string and want to jump as far as possible after each match we find. Intuitively we realize that the longest shift we can perform after a match is the length of the string minus the longest match between a suffix and a prefix in the pattern. Calculating this requires a bit more pre-processing (which I'll leave as an exercise), but we already have some information we can use to gain the second best thing: the bad character shift table. By using the BCS table entry for the last character in the pattern we're not guaranteed to shift as long as we can, but we're guaranteed to never overshoot the next match, and it will perform almost as good in most cases. Under is an example of some strings that match and how far we shift. The first entry is the optimal shift, and the second is using the BCS table.

No overlap:
  find
4     find
4     find

Single character overlap:
  test
3    test
3    test

Multiple character overlap:
  baobao
3    baobao
3    baobao

Multiple suffix match:
  bababa
2   bababa
2   bababa

Bad character shift skips too short ahead:
  this_is_this
8         this_is_this
5      this_is_this

That's it for now. It sure helped me writing this, and I hope it helped you if you're reading it. Please post a comment if you find anything that's incorrect or if you appreciate the article (it's getting pretty late and I'm pretty tired right now, so I can't guarantee that it's all bug free, plus I've already found a couple of bugs myself).

2012-10-18

Interesting blog

I found an interesting blog over at http://benryves.com. It belongs to a guy that seems to share my passion for low end systems. He's working on a 2.5D engine for the TI-83 and has a bunch of different hardware and software projects.


2012-10-10

GBA 3D Rendering

I've finally put all the pieces together, and it turned out pretty good imo. The video shows a rotating torus with a rotating directional light. I'd love to do point lights, but the inverse square root needed for normalization is extremely expensive in terms of CPU time needed.

2012-10-05

Fixed point division

Found an interesting article about fast fixed point division and multiplication on ARM processors over at Henry Thomas consulting. Originally I claimed that it didn't work for the GBA, but that was a lie. Some minor tweaks and now it runs like a charm. Fixed point division used to be a major bottleneck in my attempt at 3D rendering on the GBA, and now it's not a problem at all.

2012-09-29

Refreshing my memory (3d math)

So.. it's been a while since the last time I did all the 3D calculations myself. Nowadays I just use libraries since every decent graphics API have it build in, but that isn't the case for the GBA. I started implementing the functions needed for matrix transformations and quickly concluded with that I suspected before starting: a naive implementation will be way too slow. You still need the background information to start optimizing though. The following is a good starting point at least: Egon Rath's Notes: Basic 3D Math: Matrices.

2012-09-26

GBA: Useful links

Here are some useful links when developing for the GBA:

GBA
ARM
Math

GBA: Place functions/variables in iwram

Placing functions and variables in iwram will *seriously* speed up your program. You only have limited amounts on the other hand (32K). I made the following defines based on The Dev'rs GBA Dev FAQs.

Defines:
#define IWRAM_FUNCTION __attribute__((section (".iwram"), long_call))
#define IWRAM_VARIABLE __attribute__((section (".iwram")))
Usage:
const int somearray[] IWRAM_VARIABLE = { ... }
void IWRAM_FUNCTION SomeFunction( ... ) { ... }
I figured out that there's some more info on this over at tonc after I posted.