Lucene has basically always been really fast for just-plain-indexing-and-search. Certain additional features are pretty expensive to do the obvious way and came in as "it works" first and "it's fast" later. Reading the blog entry, this seems to be the case for fuzzy searches. One thing to take note of is that you can't just change your index structure for one feature, that might make other features slower and not worth it.
One thing I'd forgot to mention, and is probably applicable in this case, is that 'non-standard' approaches may in fact not be computationally feasibly when a project first starts out. Precomputing loads of tables of data makes sense when you're on 3ghz processors, but probably not if you're on 200mhz CPUs, for example.
