In a previous blog article, I presented the beginnings of a Keyword Lookup class. This article takes that work, turns it into a template and makes it useful for longest match lookups.
I'll have to compare this lookup library with what a C++ map or unordered_map does for lookup speed. I'm hoping that when a comparison is made, that this routine is indeed faster. I'm thinking it might be because, even though a map will do a binary search through it's map, complete strings are compared at each step. With this library, keyword patterns are added to a rooted tree of characters, possibly reducing the amount of time spent matching.
I must admit that at each match step, there is a linear search performed through a list of likely character candidates. To improve the search, I've been thinking that once the pattern tree has been created, it could be sorted so that each step search can be done with a binary search. This will be something for next time. Continue reading "Keyword Matching v2" »