<meta charset="utf-8"><font face="times new roman,serif" style="font-family: arial; ">You could do isNFD with a DFA (too many <a href="http://en.wikipedia.org/wiki/Three-letter_acronym">TLA</a>s there) without much problem. It'd look something like this (I haven't checked it in detail, tho’):</font><div style="font-family: arial; ">
<font class="Apple-style-span" face="'times new roman', serif"><br></font></div><font class="Apple-style-span" face="'times new roman', serif" style="font-family: arial; ">start + disallowed => FAIL</font><div style="font-family: arial; ">
<font class="Apple-style-span" face="'times new roman', serif">start + allowedStarter => start</font></div><div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">start + EOS => SUCCESS</font></div>
<div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif"><br></font></div><div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">// for each of the distinct n values of CCC* (< 255), have the following transitions</font></div>
<div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">start + CCCn => state_n</font></div><font class="Apple-style-span" face="'times new roman', serif" style="font-family: arial; ">state_n + disallowed => FAIL<br>
</font><div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">state_n + allowedStarter => start</font></div><div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">state_n + CCCm => state_m // for all m >= n</font></div>
<div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">state_n + CCCm => FAIL // for all other m</font></div><div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif">state_n + EOS => SUCCESS</font></div>
<div style="font-family: arial; "><font class="Apple-style-span" face="'times new roman', serif"><br></font></div><div style="font-family: arial; "><span class="Apple-style-span" style="font-family: 'times new roman', serif; ">You could do a DFA for toNFC, but the table of transitions would be huge, since you would have to split every set of transitions based on every class of non-starter you were dealing with. For example:</span></div>
<div><font class="Apple-style-span" face="'times new roman', serif" style="font-family: arial; "><div><br></div><div><a CCC1 CCC1 CCC1 .... CCC55 ... umlaut> is not valid, but</div></font><div style="font-family: arial; ">
<font class="Apple-style-span" face="'times new roman', serif"><div><b CCC1 CCC1 CCC1 .... CCC55 ... umlaut> is valid.</div><div><br></div><div>So while theoretically feasible, in practice not. It is easier, faster, and smaller to do this in code.</div>
</font></div><div><div><div><div><font class="Apple-style-span" face="'times new roman', serif"><br></font></div></div></div></div></div><font face="georgia, serif">Mark<br><br><i>— Il meglio è l’inimico del bene —</i></font><br>

<br><br><div class="gmail_quote">On Fri, Apr 15, 2011 at 13:47, Bjoern Hoehrmann <span dir="ltr"><<a href="mailto:derhoermi@gmx.net">derhoermi@gmx.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">* Mark Davis wrote:<br>
>NFD is a better internal format for some forms of processing, because it has<br>
>a smaller data-table footprint for the implementation, and is a bit faster.<br>
>Here is a simple example for an ASCII string (on my laptop, in Java, so<br>
>caveats apply). Where you are converting an NFD string to NFC, or vice<br>
>versa, then the times for that conversion go up.<br>
><br>
>   isNFC: 50ns<br>
><br>
>toNFC: 84ns<br>
><br>
>isNFD: 21ns (-57.8%)<br>
><br>
>toNFD: 84ns (+0%)<br>
<br>
</div>The set of strings that are in NFC, and the set of strings that are in<br>
NFD, are both regular languages, so you can implement isNFC and isNFD as<br>
deterministic finite automata which would be pretty much optimal in in-<br>
struction count the only performance differences would come from cache<br>
and memory performance (you can do little tricks beyond that but you'd<br>
be in hardware-dependent optimization land in any case), so I think the<br>
figures are a bit misleading.<br>
<br>
I don't think this is particularily relevant to Peter Saint-Andre's con-<br>
cern though, if you are primarily interested in comparisons of few and<br>
short strings that repeat a lot, as you would be when, say, routing, it<br>
may be wiser to simply cache frequently used strings and their properly<br>
normalized forms, or XMPP could mandate a particular form, like, always<br>
send the U-Label, only do binary comparisons, which would remove all the<br>
pressure from the wire protocol implementations.<br>
<br>
I suppose it would be easier for us to make recommendations if we knew<br>
more about the underlying performance and interoperability concerns in-<br>
stead of discussing the properties of NFC and NFD without a good under-<br>
standing of those concerns.<br>
<div class="im">--<br>
Björn Höhrmann · mailto:<a href="mailto:bjoern@hoehrmann.de">bjoern@hoehrmann.de</a> · <a href="http://bjoern.hoehrmann.de" target="_blank">http://bjoern.hoehrmann.de</a><br>
Am Badedeich 7 · Telefon: <a href="tel:%2B49%280%29160%2F4415681" value="+491604415681">+49(0)160/4415681</a> · <a href="http://www.bjoernsworld.de" target="_blank">http://www.bjoernsworld.de</a><br>
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · <a href="http://www.websitedev.de/" target="_blank">http://www.websitedev.de/</a><br>
_______________________________________________<br>
</div><div><div></div><div class="h5">Idna-update mailing list<br>
<a href="mailto:Idna-update@alvestrand.no">Idna-update@alvestrand.no</a><br>
<a href="http://www.alvestrand.no/mailman/listinfo/idna-update" target="_blank">http://www.alvestrand.no/mailman/listinfo/idna-update</a><br>
</div></div></blockquote></div><br>