On Mon, 24 Oct 2011 18:25:25 -0400, Dmitry Olshansky
<dmitry.o...@gmail.com> wrote:
On 25.10.2011 0:52, Steven Schveighoffer wrote:
On Mon, 24 Oct 2011 16:18:57 -0400, Dmitry Olshansky
<dmitry.o...@gmail.com> wrote:
On 24.10.2011 23:41, Steven Schveighoffer wrote:
On Mon, 24 Oct 2011 11:58:15 -0400, Simen Kjaeraas
<simen.kja...@gmail.com> wrote:
On Mon, 24 Oct 2011 16:02:24 +0200, Steven Schveighoffer
<schvei...@yahoo.com> wrote:
On Sat, 22 Oct 2011 05:20:41 -0400, Walter Bright
<newshou...@digitalmars.com> wrote:
On 10/22/2011 2:21 AM, Peter Alexander wrote:
Which operations do you believe would be less efficient?
All of the ones that don't require decoding, such as searching,
would be less efficient if decoding was done.
Searching that does not do decoding is fundamentally incorrect. That
is, if you want to find a substring in a string, you cannot just
compare chars.
Assuming both string are valid UTF-8, you can. Continuation bytes can
never
be confused with the first byte of a code point, and the first byte
always
identifies how many continuation bytes there should be.
As others have pointed out in the past to me (and I thought as you did
once), the same characters can be encoded in *different ways*. They
must
be normalized to accurately compare.
Assuming language support stays on stage of "codepoint is a character"
it's totaly expected to ignore modifiers and compare identically
normalized UTF without decoding. Yes, it risks to hit certain issues.
Again, the "risk" is that it fails to achieve the goal you ask of it!
Last time I checked, the legion of "everything is ASCII" zealots was
pretty large ;) So the "goal" is a blury line, meaning that "search for
a substring on in this chunk of unicode text" can mean very different
things, and be correct in it's own sense on about 3 different levels.
There is no default way, so I'm not sure we have to embed all of this
complexity into language right now. Phobos is were we must first
implement this, once it works we may look at revisiting our pick of
default comparison method, etc.
If we say D obeys the subset of unicode that only works on ascii
characters, well, then I think we do not support unicode at all ;)
I agree the string type needs to be fleshed out before the language adopts
it. I think we could legitimately define a string type that auto-assigns
from it's respective char[] array type. Once it's shown that the type is
nearly as fast as a char[] array, it can be used as the default type for
string literals (the only real place where the language gets in the way).
D-language: Here, use this search algorithm, it works most of the time,
but may not work correctly in some cases. If you run into one of those
cases, you'll have to run a specialized search algorithm for strings.
User: How do I know I hit one of those cases?
D-language: You'll have to run the specialized version to find out.
User: Why wouldn't I just run the specialized version first?
D-language: Well, because it's slower!
User: But don't I have to use both algorithms to make sure I find the
data?
D-language: Only if you "care" about accuracy!
Call me ludicrous, but is this really what we want to push on someone as
a "unicode-aware" language?
No, but we might want to fix a string search to do a little more -
namely check if it skewed a graphem (assuming normalizations match).
That's a big assumption. Valid unicode is valid unicode, even if it's not
normalized.
BTW adding normalization to std.uni is another thing to do right now.
That should be a good enough start, and looking at unicode standard,
things are rather fluid there meaning that "unicode-aware" language
should be sufixed by version number :)
I agree we need normalization and it is not necessary to involve the
compiler in this. I'd suggest a two to three phase approach:
1. Leave phobos' schizo view of "char arrays are not arrays" for now, and
build the necessary framework to get a string type that actually works.
2. Remove schizo view.
3. (optional) make compiler use library-defined string type for string
literals.
Plus, a combining character (such as an umlaut or accent) is part of a
character, but may be a separate code point. If that's on the last
character in the word such as fiancé, then searching for fiance will
result in a match without proper decoding!
Now if you are going to do real characters... If source/needle are
normalized you still can avoid lots of work by searching without
decoding. All you need to decode is one codepoint on each successful
match to see if there is a modifier at end of matched portion.
But it depends on how you want to match if it's case-insensitive
search it will be a lot more complicated, but anyway it boils down to
this:
1) do inexact search, get likely match ( false positives are OK,
negatives not) no decoding here
2) once found check it (or parts of it) with proper decoding
There are cultural subtleties, that complicate these steps if you take
them into account, but it's doable.
I agree with you that simple searches using only byte (or dchar)
comparison does not work, and can be optimized based on several factors.
The easiest thing is to find a code unit sequence that only has one
valid form, then search for that without decoding. Then when found,
decode the characters around it. Or if that isn't possible, create all
the un-normalized forms for one grapheme (based on how likely it is to
occur), and search for one of those in the undecoded stream.
Yes, it's all revolves around find all of variations of a substring.
If user is willing to spend some time upfront, this could be done in one
pass e.g. using the trick I employed in new std.regex.
For a rough idea see ShiftOr string search,
that is easy & fast inexact search:
http://igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060
There are even better variations of this stuff in the wild.
This sounds good. I'll have a look at it when I have time.
This can all be built into a specialized string type. There's actually
some really interesting problems to solve in this space I think. I've
created a basic string type that has lamented in my unfinished pile of
stuff to do. I think it can be done in a way that is close to as
efficient as arrays for the most common operations (slicing, indexing,
etc.), but is *correct* before it is efficient. You should always be
able to drop into "array mode" and deal with the code-units.
Here is where we probably differ, to me there is no simple safe fast
string type. Why? Because if you need anything "not pedantic and safe
above all" you work with implicit data type of e.g. "a chunk of UTF-8
bytes that are normalized in NFC", ...
Specialized types which dictate normalization could be created. We do not
have to always assume the worst if we are optimizing.
But in general, when you read a utf-8 file, it could have anything in it.
It may not even be normalized.
I'd rather see them as sealed array with a bunch of meta info, and
string functions to specialize on them in order to do some cool speed
hacks. Of course, drilling down to row data should be possible for the
user as well.
This is exactly what I am envisioning ;) Except I'd build the meta-info
into the type.
Or if fiancé uses a
precomposed é, it won't match. So two valid representations of the
word
either match or they don't. It's just a complete mess without proper
unicode decoding.
It's a complete mess even with proper decoding ;)
Yes, all the more reason to solve the problem correctly so the hapless
unicode novice user doesn't have to!
Hapless novice unicode user don't stand a chance.
I'm serious. One needs to know a lot of these "basics" to e.g. know why
indexing by "true" character could be so slow, about encodings,
normalizations etc. Yet we can save a metric ton of special cased crap
from ever hitting his eyes.
I disagree. 99% of the time I use strings, I don't care about indexes. I
just want to deal with whole strings and substrings. I rarely use
arbitrary indexes, and when I do, I'm assuming ascii data.
The hapless novice unicode user doesn't need to know unicode to do:
writefln("hello, world!");
Or to do:
if(find(str, "xyz")) {...}
Or to even use regex!
-Steve
