Hi, a note from one of the coauthors of the paper ;-)
Yes, it is a theoretical paper and then the presentation focuses on what is needed in such a paper: to establish that the big-Oh complexity can be reached. Some theoretical papers will never become practical, but we believe this one can. However, this will require a fair amount of algorithm engineering, to take the important theoretical ideas and implement them with common sense, changing theoretically appealing but practically useless modules by others that work better, even if they do not reach the desired worst-case complexity. A promising aspect of this algorithm is that it is easily parallelizable (the batched queries). A postdoc of mine that has experience in multithreading and compact data structures is already working on this. I won't dare to say how competitive will be the resulting LZ-parsing algorithm, though.
Another well-known case is the first paper on the FM-index, with constants like sigma^sigma multiplying the space, and its current realizations, e.g. Burrows-Wheeler Aligner.
In this case, I think it will not be that hard, but still it will not be a matter of just translating the algorithm into code.
Yes, it is a theoretical paper and then the presentation focuses on what is needed in such a paper: to establish that the big-Oh complexity can be reached. Some theoretical papers will never become practical, but we believe this one can. However, this will require a fair amount of algorithm engineering, to take the important theoretical ideas and implement them with common sense, changing theoretically appealing but practically useless modules by others that work better, even if they do not reach the desired worst-case complexity. A promising aspect of this algorithm is that it is easily parallelizable (the batched queries). A postdoc of mine that has experience in multithreading and compact data structures is already working on this. I won't dare to say how competitive will be the resulting LZ-parsing algorithm, though.
We have had some experiences with good theoretical results whose implementation looks unsurmountable but that turned out to work very well after some algorithm engineering. An example is our work on top-k document retrieval: http://epubs.siam.org/doi/abs/10.1137/140998949 http://dl.acm.org/citation.cfm?id=3043958
Another well-known case is the first paper on the FM-index, with constants like sigma^sigma multiplying the space, and its current realizations, e.g. Burrows-Wheeler Aligner.
In this case, I think it will not be that hard, but still it will not be a matter of just translating the algorithm into code.
Best, Gonzalo