Live data from Hacker News

Fix Boyer-Moore searcher with the Rytter correction

github.com

1–10 of 56 posts

Re: Fix Boyer-Moore searcher with the Rytter correction

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

#4
The papers:

- 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

#6
> However, the published algorithm for dd' was incorrect! This was discovered and fixed by Rytter in 1980, which we weren't aware of until we received a bug report.

Fits 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

#9
A while back I filed an issue on the MSVC std::vector implementation as the behaviour of a weird corner case differed from GCC/Clang.

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

Post reply on HN