Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fix Boyer-Moore searcher with the Rytter correction

github.com

Post reply on HN
Print view View original

31–40 of 56 posts

Re: Fix Boyer-Moore searcher with the Rytter correction

#31

Post by billyoneal »

jameshart wrote: post #28
StephanTLavavej wrote: post #23

Earlier quoted context omitted.

The smallest test case appears to be a needle of "aaa" and a haystack of "xxaaa", where VS 2019 16.5's boyer_moore_searcher will report "not found", while the corrected code finds the needle at offset 2 in the haystack.

Seems astonishing that nobody has run into this in the wild. How does it do on finding ‘www’ in ‘ http://www.example.com/ , for example?

You need a needle that triggers the problem, AND a haystack where the delta2 table matters, AND the algorithm to stop at a problematic index where it uses a bad delta2 value.

There's a reason the published version even in 'the papers' was wrong for 3 years.

Re: Fix Boyer-Moore searcher with the Rytter correction

#32

Post by billyoneal »

dvt wrote: post #10

What I find most interesting about this bugfix is simply how terrible of a source Wikipedia is and, at the same time, how valuable professional insight can be (e.g. someone that knows what they're talking about). And to add insult to injury, someone quickly edited Wikipedia (for the "street cred" I'm sure): > The original paper contained errors for computing the table of pattern shifts which was corrected by Wojciech…

He meant the original paper for calculating delta2 which was merely referenced by the original BM paper.

Sadly this seems to be the pattern for most everything coming from 'academia' ever.

Re: Fix Boyer-Moore searcher with the Rytter correction

#33

Post by burntsushi »

praptak wrote: post #21

Lol, I was taught by Rytter like 20 years ago. He did much more in text algorithms than just correcting B-M. The two books by Crochemore & Rytter are basically the books on text algorithms.

> the books on text algorithms.

And also "Flexible Pattern Matching in Strings" by Navarro and Raffinot.

Re: Fix Boyer-Moore searcher with the Rytter correction

#34

Post by kazinator »

> I find it very curious that it isn't constantly mentioned when explaining Boyer-Moore

Papers need "superseded by ..." type forward references, like IETF RFC's. Or rather "corrected by", in this case.

Maybe important algorithms need to be summarized in RFC-like documents.

Re: Fix Boyer-Moore searcher with the Rytter correction

#35

Post by ahelwer »

tacitusarc wrote: post #2

What I really enjoy about this merge request are these comments: > Rename _Suffix_fn to _Fx, again following the papers. Note that in the usage below, there is a semantic change: _Suffix_fn stored 0-based values, while _Fx stores 1-based values. This undoes a micro-optimization (_Suffix_fn avoided unnecessarily translating between the 0-based and 1-based domains), but with the increased usage of f in the Rytter corre…

I've implement a few string search algorithms and translating between 1- and 0- based offset functions was the source of a huge number of bugs, as you might expect. For some reason a lot of sources present the algorithms as 1-based.

Re: Fix Boyer-Moore searcher with the Rytter correction

#36

Post by ahelwer »

dvt wrote: post #10

What I find most interesting about this bugfix is simply how terrible of a source Wikipedia is and, at the same time, how valuable professional insight can be (e.g. someone that knows what they're talking about). And to add insult to injury, someone quickly edited Wikipedia (for the "street cred" I'm sure): > The original paper contained errors for computing the table of pattern shifts which was corrected by Wojciech…

Yeah I wrote that Wikipedia article, as much as a single person can. Used the textbook Strings, Trees, and Sequences by Gusfield; it never made mention of Rytter. I wouldn't say Wikipedia is a "terrible" source, though; compared to what? Papers? Textbooks? During the course of my career I've found major technical errors in about half of CS papers. Now the error is being documented & fixed in the Wikipedia article.

My main takeaway was that people should avoid BM in favor of KMP as much as possible if you're writing a string search function, because you're guaranteed to have some bugs when implementing BM. Writing your own string search function seems nearly on the same level as implementing your own cryptographic functions, though.

Interestingly someone reported a bug in my BM sample code on the wikipedia article talk page some years ago (still not yet fixed) which might be related to this Rytter issue. And someone forked my wikipedia article code repo yesterday, which I thought was very weird; must be related to this.

I guess coming to a further defence of wikipedia: as you read technical books & papers (or philosophy!) you see knowledge is extremely unevenly-distributed in society. Much of it is locked up inside these dense, expensive books (if you're lucky!) and even more of it is sitting undigested in papers written for people with five years of postgrad education, and even more is in expert's brains and never put to paper. These barriers stay up for a long time, decades even. We just witnessed one such barrier falling. Wikipedia is an optimal resting place for such liberated knowledge, and I would go so far as to say knowledge that is not on Wikipedia is not yet liberated.

Re: Fix Boyer-Moore searcher with the Rytter correction

#37

Post by hyperpape »

StephanTLavavej wrote: post #26
skyde wrote: post #3

This guy is a hero! I have so much respect for his work. By i’m still wondering if this bug could have been detected by automatic fuzzing testing ?

I believe that fuzz testing would have found it, yes. I'm not sure if fuzz testing would have been guided towards highly repetitive patterns, given the relative lack of branches in the table construction code, but the incorrectly handled patterns can be very short so fuzz testing should have stumbled upon them (given a pattern that generated an incorrect table, finding a haystack which doesn't work is merely a matter…

A technique that I've used while fuzz testing string algorithms is to run all tests first with small alphabets (perhaps 4-6 characters), then with full alphabets. It seems to increase the probability of finding bugs with relatively small runs.

My work is on a personal project, not algorithms that have been in production for years, so it's possible that this wouldn't be that productive.

Re: Fix Boyer-Moore searcher with the Rytter correction

#38

Post by buckminster »

kazinator wrote: post #34

> I find it very curious that it isn't constantly mentioned when explaining Boyer-Moore Papers need "superseded by ..." type forward references, like IETF RFC's. Or rather "corrected by", in this case. Maybe important algorithms need to be summarized in RFC-like documents.

Exactly the same problem occurs with legislation. For years this was solved by third-parties publishing enormous annotated legal references. Nowadays the government (in the UK anyway) publishes legislation online incorporating all the edits made by later legislation.

Knuth's TAOCP serves as an annotated third-party reference, except that in this case he's not a third-party. I don't have a copy to hand to see if it has the correct version of the algorithm.

Re: Fix Boyer-Moore searcher with the Rytter correction

#39

Post by ivanbakel »

ahelwer wrote: post #35
tacitusarc wrote: post #2

What I really enjoy about this merge request are these comments: > Rename _Suffix_fn to _Fx, again following the papers. Note that in the usage below, there is a semantic change: _Suffix_fn stored 0-based values, while _Fx stores 1-based values. This undoes a micro-optimization (_Suffix_fn avoided unnecessarily translating between the 0-based and 1-based domains), but with the increased usage of f in the Rytter corre…

I've implement a few string search algorithms and translating between 1- and 0- based offset functions was the source of a huge number of bugs, as you might expect. For some reason a lot of sources present the algorithms as 1-based.

>For some reason a lot of sources present the algorithms as 1-based.

Because that's a natural mathematical model. "the n-th element" being at position n is handy and natural. What's nuts is that array indexing based on pointer offsets has made its way into nearly all high-level languages.

Re: Fix Boyer-Moore searcher with the Rytter correction

#40

Post by ahelwer »

ivanbakel wrote: post #39
ahelwer wrote: post #35

Earlier quoted context omitted.

I've implement a few string search algorithms and translating between 1- and 0- based offset functions was the source of a huge number of bugs, as you might expect. For some reason a lot of sources present the algorithms as 1-based.

>For some reason a lot of sources present the algorithms as 1-based. Because that's a natural mathematical model. "the n-th element" being at position n is handy and natural. What's nuts is that array indexing based on pointer offsets has made its way into nearly all high-level languages.

Yeah that makes sense. I recall 0-based actually making most index calculations easier though, as in fewer +1/-1 offsets.
Post reply on HN