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

41–50 of 56 posts

Re: Fix Boyer-Moore searcher with the Rytter correction

#41

Post by derefr »

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.

One might say that computing doesn't care about ordinal numbers, only cardinal numbers.

On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.)

Similarly, there is no "first byte" of a random-access memory, because the ordering of memory is not guaranteed (i.e. some memories have bit-planes, some memories have banks, some memories are big/little-endian, etc.) The only thing you can say about a memory (and thereby about a RAM-word machine, or about an array) is what exists at address 0 of it, at address 1 of it, etc. It would be incorrect to describe address 0 as "the first byte" of memory, as this would impose a canonical iteration order.

Re: Fix Boyer-Moore searcher with the Rytter correction

#42

Post by DeathArrow »

derefr wrote: post #41
ivanbakel wrote: post #39

Earlier quoted context omitted.

>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.

One might say that computing doesn't care about ordinal numbers, only cardinal numbers. On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.) Similarly, there is no "first byte" of a random-access memory, because the ordering of memory is not guaranteed (i.e. some memories have bit-planes, some memories have banks, some memories are big/lit…

>On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.)

Maybe, but human brain likes things starting at 1.

Re: Fix Boyer-Moore searcher with the Rytter correction

#43

Post by billyoneal »

skyde wrote: post #8

Any one know why the Turbo Boyer-Moore algorithm is not more popular. Any case when Boyer Moore would be better?

1. What empirical data we have suggests that the 'good suffix' rule engages fairly rarely; that's why the -Horspool variant wins most tests. (It isn't just that you don't have to build Delta2, it also saves a lot of comparisons in the algorithm itself for most inputs.) 2. Because the standard says this is the Boyer-Moore algorithm :D

Re: Fix Boyer-Moore searcher with the Rytter correction

#44

Post by marvy »

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…

It seems AFL might have been ported to Windows:

https://github.com/ivanfratric/winafl

(don't know; just found this two minutes ago)

Re: Fix Boyer-Moore searcher with the Rytter correction

#45

Post by a1369209993 »

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.

> Because that's a natural mathematical model.

No it's not; it's a artifact of humans numbering items based on "total I have, including this one" rather than the more sensible but contrary to a implementation detail of human neuropsychology "number of items preceeding this one".

> "the n-th element" being at position n is handy and natural.

Yes, starting with the 0th element at position 0.

Re: Fix Boyer-Moore searcher with the Rytter correction

#46

Post by a1369209993 »

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…

Speaking of things that make code needlessly difficult to verify, we really need to start insisting on correct (zero-based) indexing in academic algorithms.

Re: Fix Boyer-Moore searcher with the Rytter correction

#47

Post by StephanTLavavej »

hyperpape wrote: post #37
StephanTLavavej wrote: post #26

Earlier quoted context omitted.

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.

Indeed, the randomized test in this PR uses alphabets from AB to ABCDEF, because I noticed the same thing - small alphabets make repetitions more likely, which are the tricky cases.

Re: Fix Boyer-Moore searcher with the Rytter correction

#48

Post by StephanTLavavej »

marvy wrote: post #44
StephanTLavavej wrote: post #26

Earlier quoted context omitted.

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…

It seems AFL might have been ported to Windows: https://github.com/ivanfratric/winafl (don't know; just found this two minutes ago)

Very interesting, thanks!

Re: Fix Boyer-Moore searcher with the Rytter correction

#49

Post by StephanTLavavej »

ahelwer wrote: post #36
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…

> 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.

And that’s the Curse Of The Standard Library Implementers: we’re the ones that have to implement Boyer-Moore, floating-point string conversions, etc. so everyone else can use them :-)

Re: Fix Boyer-Moore searcher with the Rytter correction

#50

Post by 04091948 »

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.

maybe it's because of Pascal. I remember even Cormen used to have pascal style pseudo-code.
Post reply on HN