[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Surrogates and character representation
William D Clinger wrote:
Alex Shinn quoting me:
> > I acknowledged that the algorithm will still work. My point
> > is that its asymptotic complexity may be degraded.
> I'm sorry, perhaps I'm just misunderstanding, but if the exact
> same algorithm, in fact the exact same code, can be used,
> how is the asymptotic complexity affected?
The different representations for the string being searched
(UTF-8 vs UTF-32) change the problem. The main difference
is that UTF-32 admits random access of characters, while
UTF-8 does not. UTF-8 admits random access of bytes, but
there is no way to convert a byte value obtained by random
access into a UTF-8 string into the character offset on
which the Boyer-Moore algorithm depends,
I don't claim to understand Boyer-Moore, beyond what I gather
is the key insight: if you're searching for "ABC" and character
N is "D" there is no point in checking characters N+1 or N+2.
(Hence the non-obvious part of building the appropriate delta
tables before you start.)
But I'm puzzled, since I think Alex's point is this: A Boyer-Moore
implementation that works on 8-bits characters (e.g. Latin-1) will
work unchanged on UTF-8 characters. Naively, one would think it
would have the same performance characteristics. I guess that
statistics of multi-byte characters might throw off the "delta"
tables so they delta will tend to be smaller. (However, don't
go into details for my sake: I suspect t would take me too much
effort to delve into it.)
As Per Bothner agreed, that can degrade the asympototic
complexity of the algorithm from O(n/m) to O(n).