[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Case mapping of sharp s

From: Stefan Monnier
Subject: Re: Case mapping of sharp s
Date: Wed, 18 Nov 2009 20:16:16 -0500
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux)

>> 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
I don't claim it's trivial, but I'm pretty sure it's workable.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]