Subject: [Ltru] FYI: validating

From: Mark Davis <[email-masked]>
Date: Thu, 26 Feb 2009 10:49:17 -0800

For those interested in validation:

We were looking at validation of 7,000 base language entries and Markus had
an idea. Algorithmically map the two-letter codes onto values from 0..675,
and the three letter codes onto 676..18251. These numbers can be put into a
bit-string of ~2K bytes. That allows for fast validation with a small table.
Registered codes would need an exception table. One could do the same for
region codes, about a 750 byte table.

Script codes don't lend themselves to the same approach.

Mark

---

From: John Cowan <[email-masked]>
Date: Thu, 26 Feb 2009 14:54:02 -0500

> Script codes don't lend themselves to the same approach.

It so happens that except for Teng/Tfng, the second letter of
the script code is redundant, so you can special-case those
two, remove the second letter, and use the same algorithm
as for ISO 639-2.

You could incorporate this rule into the ISO 15924/JAC's
standing rules.

-- 
You know, you haven't stopped talking           John Cowan
since I came here. You must have been           http://www.ccil.org/~cowan
vaccinated with a phonograph needle.            [email-masked]
        --Rufus T. Firefly

---

From: Mark Davis <[email-masked]>
Date: Thu, 26 Feb 2009 13:02:02 -0800

Doug pointed out a math error; that the second table is a bit over 200
bytes.

Mark

---

From: Mark Davis <[email-masked]>
Date: Thu, 26 Feb 2009 13:05:47 -0800

Theoretically. However, the JAC would have to buy off on that...

Given so few scripts, probably a hash table would be fine, or one could try
a trie.

Mark

On Thu, Feb 26, 2009 at 11:54, John Cowan <[email-masked]> wrote:

> since I came here. You must have been           http://www.ccil.org/~cowan<http://www.ccil.org/%7Ecowan>

---

From: Martin Duerst <[email-masked]>
Date: Fri, 27 Feb 2009 11:46:14 +0900

At 06:05 09/02/27, Mark Davis wrote:
>Given so few scripts, probably a hash table would be fine, or one could try a trie.

My guess would be that perfect hashing would be perfect for
script codes :-).

Regards,    Martin.

>Mark
>
>
>On Thu, Feb 26, 2009 at 11:54, John Cowan <<mailto:[email-masked]>[email-masked]> wrote:
>>Mark Davis scripsit:
>>
>>You know, you haven't stopped talking ツ  ツ  ツ  ツ  ツ  John Cowan
>>since I came here. You must have been ツ  ツ  ツ  ツ  ツ  <http://www.ccil.org/%7Ecowan>http://www.ccil.org/~cowan
>>vaccinated with a phonograph needle. ツ  ツ  ツ  ツ  ツ  ツ <mailto:[email-masked]>[email-masked]
>>ツ  ツ  ツ  ツ --Rufus T. Firefly
>
>_______________________________________________
>Ltru mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/ltru

#-#-#  Martin J. Du"rst, Assoc. Professor, Aoyama Gakuin University
#-#-#  http://www.sw.it.aoyama.ac.jp       mailto:[email-masked]

---

From: Mark Davis <[email-masked]>
Date: Thu, 26 Feb 2009 20:48:29 -0800

Perfect hashing is not necessarily perfect (same with
http://en.wikipedia.org/wiki/Cuckoo_hashing). The extra complications of the
hashing function cost something. Depending on size and behavior, it may or
may not be better than a simple hash table.

Mark

On Thu, Feb 26, 2009 at 18:46, Martin Duerst <[email-masked]> wrote:

> >>since I came here. You must have been ツ  ツ  ツ  ツ  ツ  <
> http://www.ccil.org/%7Ecowan>http://www.ccil.org/~cowan<http://www.ccil.org/%7Ecowan>

---

From: John Cowan <[email-masked]>
Date: Fri, 27 Feb 2009 00:09:47 -0500

> My guess would be that perfect hashing would be perfect for

That's what I thought too, but when I ran gperf, it insists on keeping
the full unpacked table around as well, because even a perfect hash
table may be passed a string that hashes to the same thing as one of
the existing strongs, so you have to check against the source strings.
positive.

-- 
Only do what only you can do.               John Cowan <[email-masked]>
  --Edsger W. Dijkstra's advice
    to a student in search of a thesis