From: http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm
"The algorithm preprocesses the target string (key) that is being searched for, but not the string being searched. The execution time of the Boyer-Moore algorithm can actually be sub-linear: it doesn't need to actually check every character of the string to be searched but rather skips over some of them. Generally the algorithm gets faster as the key being searched for becomes longer."
The Boyer-Moore string searching is like free beer. Unlike most string searching approaches it is sub-linear and improves as key length increases.
Lots of patents are filed related to this innovation - go to http://patft.uspto.gov/netahtml/PTO/search-bool.html and enter "Boyer Moore".
I particularly liked patent 6,768,991- July 27, 2004 (Searching for sequences of character data - Hearnden; Stephen Owen (Great Holm, GB) - Networks Associates Technology, Inc. (Santa Clara, CA)) - This patent does not try to patent Boyer Moore itself - but at least they are honest about the 30 year old prior art upon which their work builds. In summary the patent is "we used Boyer-Moore to search E-Mail!".
But here is the key idea - Boyer and Moore *did not* patent the idea - the *real* innovation - they just published it. This essential "free" idea has led to tons of innovation (withness all the other patents) or type Boyer-Moore into Google.
What would have happenned if Boyer-Moore filed and received a patent? That would suck.
But what happens is a *lot of people* with less talent than Boyer or Moore had in their little fingers - have filed a ton of patents touting their *use* of Boyer-Moore. I guess that this makes people feel good and makes sure that no one else can file such a silly patent and attack them. Such is the nature of software patents.
To me this is like inventing the "color blue" but not patenting it and then having lots of people patent "I made a picture of a lake and used the color blue - Eureka! - give me a patent on the use of the color blue in paintings of lakes.".
But since the USPTO gives out patents for "I saw this cool idea and used it" -you need to file defensive patents all the time. Grrr.
Dang - I should have *patented* the use of asterisks to indicate emphasis within a blogging system stored in MySql on a plurality of servers!
Posted by csev at September 2, 2006 02:29 PM