Re: Case mapping of sharp s

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> Given the fact that all the strings in the set are very similar,
>> it should be possible to come up with an efficient algorithm for it.
>> The basic idea I'd try is to build the BM table for each of the
>> alternative strings and then merge them into a single table that
>> takes for each entry the smallest shift distance of each table.
> So if the string has n characters and each of them has two case
> variants, then 2^n keys would be needed for the search? (Or even more,
> if the extra slots of the case table are used.)

Except that you only need to do that for those special chars where the
current approach doesn't work.  And except that you don't need to
generate all the combinations: you can generate the table directly from
the single input string (you'll probably need to keep something like
a "spread" count that says how many bytes there are between the shortest
and longest representation of the part of the string you've already
processed).
I don't claim it's trivial, but I'm pretty sure it's workable.


        Stefan