Fix Boyer-Moore searcher with the Rytter correction
1–10 of 56 posts
Re: Fix Boyer-Moore searcher with the Rytter correction
#2> 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 correction, I wanted greater correspondence with the published algorithms in order to verify the implementation.
And
> Rename 1-based _Idx to 1-based _Jx. (While the code was correct, I found it confusing that _Idx was 0-based in other loops but 1-based in this loop.)
Naming is one of the most strangely difficult aspects of programming, but if there is one rule it's be consistent. I really hate code that uses a variable name to mean one thing in one place and other somewhere else. I just learned what that meant! Why change it?! And yet this is common, and sometimes a comment about it in code review might get a response like "the code works, why does it matter?" This. This is why it matters. It causes confusion, which makes code difficult to verify, which causes bugs.
Re: Fix Boyer-Moore searcher with the Rytter correction
#3By i’m still wondering if this bug could have been detected by automatic fuzzing testing ?
Re: Fix Boyer-Moore searcher with the Rytter correction
#4- Boyle, Moore (1977) https://www.cs.utexas.edu/users/moore/publications/fstrpos.p...
- Knuth, Morris, Pratt (1977) https://pdfs.semanticscholar.org/4479/9559a1067e06b5a6bf052f...
- Rytter (1980) https://doi.org/10.1137/0209037 (paywalled without subscription, but you know where to find it cough scihub cough).
Re: Fix Boyer-Moore searcher with the Rytter correction
#5Re: Fix Boyer-Moore searcher with the Rytter correction
#6Fits what Knuth said: "Beware of bugs in the above code; I have only proved it correct, not tried it."
Re: Fix Boyer-Moore searcher with the Rytter correction
#7This 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 ?
Re: Fix Boyer-Moore searcher with the Rytter correction
#8Re: Fix Boyer-Moore searcher with the Rytter correction
#9The reply I got from STL himself was fantastic, pointing out that it was [paraphrasing here] a wart in the spec, and that neither were actually incorrect.
To my lasting regret, I didn't keep an ahem offsite backup of some of those corp emails. Hence I can't recall the exact details.
Re: Fix Boyer-Moore searcher with the Rytter correction
#10> The original paper contained errors for computing the table of pattern shifts which was corrected by Wojciech Rytter in 1980 [1]
But that's still actually wrong. Computing the table was not even discussed in the "original paper" -- see the papers linked by @oefrha in this thread. They're two different 1977 papers!
[1] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-sea...