On Wed, Oct 14, 2020 at 7:57 PM Tim Peters <tim.peters@gmail.com> wrote:
[Guido]
Maybe someone reading this can finish the Wikipedia page on Two-Way Search? The code example trails off with a function with some incomprehensible remarks and then a TODO..
Yes, the Wikipedia page is worse than useless in its current state, although some of the references it lists are helpful. This is a much better summary:
http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
but, I believe, still far too telegraphic.
The original paper is by far the best account I've seen so far, with complete code and exhaustive explanations and proofs. Even examples ;-)
But here's the thing: I don't believe this algorithm this _can_ be reduced to an elevator pitch. Excruciating details appear to be fundamental at every step, and I've seen nothing yet anywhere approaching an "intuitive explanation" :-( What happens instead is that you run it on the hardest cases you can dream up, and your jaw drops in amazement :-)
That sounds very interesting! I'll definitely be digging deeper into the algorithm, papers and proofs of the underlying "Critical Factorization" theorem. My goal would be to find a good way to explain them, ideally some kind of interactive article. Ideally that would also lead to better Wikipedia pages. I'd be happy to help with this project. I've done quite a bit of relevant work while developing my fuzzysearch[1] library. - Tal Einat [1] https://pypi.org/project/fuzzysearch/