Re: find words that contains some specific letters

Re: find words that contains some specific letters

[John B. Matthews]

In article <78rpbkF1mqrc7U1@mid.individual.net>,
 "Giovanni Azua" <bravegag@hotmail.com> wrote:

> "Patricia Shanahan" <pats@acm.org> wrote in message
> > A perfect hash function is one that guarantees distinct hash codes 
> > for a specific set of keys. There are algorithms for constructing 
> > one, given a set of keys.
>
> For example the Character class.

I think all of the primitive wrappers (except Double) have trivially 
perfect integer hashes, as they wrap distinct values. Patricia was 
perhaps referring to algorithms of the kind discussed here:

<http://en.wikipedia.org/wiki/Perfect_hash_function>

The jumble algorithm relies on a hashed map for efficiency, but a
perfect hash is not essential. I recently implemented the algorithm
in both Java and Ada using library routines:

<http://en.wikipedia.org/wiki/Jumble>
<http://sites.google.com/site/drjohnbmatthews/jumble>
<http://home.roadrunner.com/~jbmatthews/jumble.html>

I was intrigued to compare the two languages' library implementations 
of a general purpose string hash. Using a multiplicative function with 
an initial value of zero, both offer excellent performance. Java uses a 
multiplier of 31 on a signed 32-bit integer; Ada uses a multiplier of 
eight on an unsigned (modular) value whose size is implementation 
defined (e.g. mod 2**32):

<http://www.docjar.org/html/api/java/lang/String.java.html>
<http://gcc.gnu.org/viewcvs/trunk/gcc/ada/a-strhas.adb>

[Cross-posted to comp.lang.java.programmer and comp.lang.ada;
Followup-To header not set.]

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: find words that contains some specific letters

[Patricia Shanahan]

John B. Matthews wrote:
> In article <78rpbkF1mqrc7U1@mid.individual.net>,
>  "Giovanni Azua" <bravegag@hotmail.com> wrote:
> 
>> "Patricia Shanahan" <pats@acm.org> wrote in message
>>> A perfect hash function is one that guarantees distinct hash codes 
>>> for a specific set of keys. There are algorithms for constructing 
>>> one, given a set of keys.
>> For example the Character class.
> 
> I think all of the primitive wrappers (except Double) have trivially 
> perfect integer hashes, as they wrap distinct values. Patricia was 
> perhaps referring to algorithms of the kind discussed here:
> 
> <http://en.wikipedia.org/wiki/Perfect_hash_function>

Yes, that's the sort of thing I meant.

The Long hash code is also not perfect, and cannot be, because there are
more longs than ints.

Patricia

Re: find words that contains some specific letters

[Giovanni Azua]

"Patricia Shanahan" <pats@acm.org> wrote:
>>>> A perfect hash function is one that guarantees distinct hash codes for 
>>>> a specific set of keys. There are algorithms for constructing one, 
>>>> given a set of keys.

"Giovanni Azua" <bravegag@hotmail.com> wrote:
>>> For example the Character class.

"John B. Matthews" <nospam@nospam.invalid> wrote:
>> I think all of the primitive wrappers (except Double) have trivially 
>> perfect integer hashes, as they wrap distinct values. Patricia was 
>> perhaps referring to algorithms of the kind discussed here:
>>
>> <http://en.wikipedia.org/wiki/Perfect_hash_function>

"Patricia Shanahan" <pats@acm.org> wrote:
> Yes, that's the sort of thing I meant.
>
> The Long hash code is also not perfect, and cannot be, because there are
> more longs than ints.
>

To achieve the perfect, optimal and ideal no collisions Hash table "perfect 
Hash table" these are the two factors that play a role:

1-. the "perfect" property of the hash function as defined in the wiki page 
cited above
2-. the size of the elements set

If #2 goes arbitrarily large meaning allocating a hash table of the size of 
that elements set becomes prohibitive memory-wise then it does not really 
matter how perfect the hash function is, there will be collisions anyway and 
an additional search algorithm will be needed to disambiguate the colliding 
elements that fall under the same buckets. This is what I think John 
Matthews hasn't realized yet about his implementation of the Jumble 
algorithm. For a realistic dataset he will be returning elements that do not 
match the of input (String built on top of the sorted character input) but 
matches that happen to collide under the same bucket.

e.g. trying to allocate a Hash table of the size ( Integer.MAX_VALUE - 
Integer.MIN_VALUE) would be prohibitive unless you place unrealistic 
requirements so you have the Integer with a perfect hash function but you 
will not get a "perfect Hash table". It is of course worse for the String 
class where neither #1 nor #2 are fulfilled.

Character class offers the perfect hash function but since the elements set 
is discrete i.e. 26 elements http://en.wikipedia.org/wiki/English_alphabet 
you can build a perfect Hash structure like the one I described and edited 
by Tom McGlynn.

Best regards,
Giovanni 

Re: find words that contains some specific letters

[Giovanni Azua]

"Giovanni Azua" <bravegag@hotmail.com> wrote in message
> elements that fall under the same buckets. This is what I think John 
> Matthews hasn't realized yet about his implementation of the Jumble 
> algorithm. For a realistic dataset he will be returning elements that do 
> not match the of input (String built on top of the sorted character input) 
> but matches that happen to collide under the same bucket.
>
I am sorry, this is wrong. Matthews's Jumble implementation is correct and 
does not have the problem I described here.

Best regards,
Giovanni 

Re: find words that contains some specific letters

[Mark Space]

John B. Matthews wrote:

>> For example the Character class.
> 
> I think all of the primitive wrappers (except Double) have trivially 
> perfect integer hashes, as they wrap distinct values. Patricia was 
> perhaps referring to algorithms of the kind discussed here:
> 
> <http://en.wikipedia.org/wiki/Perfect_hash_function>


I remember in school we implemented a minimal perfect hash function on a 
given set of keys:  the keywords in the Pascal language.  We were given 
the parameters of the algorithm: use the length of the keyword, the 
first character and the last character only.

The concept was obviously to show how a fast look-up could be done when 
implementing a compiler, but the hash function itself was interesting at 
the time.

Re: find words that contains some specific letters

[Lew]

John B. Matthews wrote:
> The jumble algorithm relies on a hashed map for efficiency, but a

Because it has constant-time performance for get() with the String hash code.

> perfect hash is not essential. I recently implemented the algorithm
> in both Java and Ada using library routines:
> 
> <http://en.wikipedia.org/wiki/Jumble>
> <http://sites.google.com/site/drjohnbmatthews/jumble>
> <http://home.roadrunner.com/~jbmatthews/jumble.html>
> 
> I was intrigued to compare the two languages' library implementations 
> of a general purpose string hash. Using a multiplicative function with 
> an initial value of zero, both offer excellent performance. Java uses a 
> multiplier of 31 on a signed 32-bit integer; Ada uses a multiplier of 
> eight on an unsigned (modular) value whose size is implementation 
> defined (e.g. mod 2**32):
> 
> <http://www.docjar.org/html/api/java/lang/String.java.html>
> <http://gcc.gnu.org/viewcvs/trunk/gcc/ada/a-strhas.adb>

The Java String hash is just about verbatim from Knuth.  It has the virtue of 
being a well-studied algorithm that has been shown to have good distribution 
characteristics.

I'm not so sure about the Ada one.  I haven't studied this in a while, but I 
seem to recall that power-of-two multipliers mod 2**32 don't have as good a 
distribution.  Perhaps someone could correct me on that.

-- 
Lew

Re: find words that contains some specific letters

[Tom Anderson]

On Sat, 6 Jun 2009, Lew wrote:

> John B. Matthews wrote:
>> The jumble algorithm relies on a hashed map for efficiency, but a
>> perfect hash is not essential. I recently implemented the algorithm
>> in both Java and Ada using library routines:
>> 
>> <http://en.wikipedia.org/wiki/Jumble>
>> <http://sites.google.com/site/drjohnbmatthews/jumble>
>> <http://home.roadrunner.com/~jbmatthews/jumble.html>
>> 
>> I was intrigued to compare the two languages' library implementations of a 
>> general purpose string hash. Using a multiplicative function with an 
>> initial value of zero, both offer excellent performance. Java uses a 
>> multiplier of 31 on a signed 32-bit integer; Ada uses a multiplier of eight 
>> on an unsigned (modular) value whose size is implementation defined (e.g. 
>> mod 2**32):
>> 
>> <http://www.docjar.org/html/api/java/lang/String.java.html>
>> <http://gcc.gnu.org/viewcvs/trunk/gcc/ada/a-strhas.adb>

John, i think you've missed a trick there - doesn't Rotate_Left do a 
barrel shift, where the bits that fall off the left-hand end get shoved 
back in at the right, rather than a plain shift? If so, the basic 
algebraic structure is actually a bit different to java's hash.

> The Java String hash is just about verbatim from Knuth.  It has the virtue of 
> being a well-studied algorithm that has been shown to have good distribution 
> characteristics.
>
> I'm not so sure about the Ada one.  I haven't studied this in a while, 
> but I seem to recall that power-of-two multipliers mod 2**32 don't have 
> as good a distribution.  Perhaps someone could correct me on that.

If Rotate_Left is a plain shift, then the Ada hash is based only on the 
last 10 characters of the string. Multiplying by eight is like shifting 
left three places; modding by 2*32 is like anding with 0xffffffff (if 
you'll pardon my verbs). When you add in a character, the rightmost bit 
you can affect is bit 0, the LSB; after ten shifts of three bits, that is 
now at bit thirty, and after one more, it's at bit thirty-three, and has 
vanished.

If Rotate_Left is a barrel shift, then our bit of interest doesn't vanish, 
because it comes back to the right-hand end of the hash after the eleventh 
shift in position 1. Because 3 is coprime with 32, it will then proceed to 
make a complete circuit of all positions in the hash over the following 
twenty-one shifts, winding up back in position 0 after the thirty-second. 
I have a vague worry that this means that strings built from the same 
32-character blocks arranged in any order will have the same hash, but i 
suspect that this is not the case, because of carries. My maths isn't up 
to proving it, though.

I still think this is a shoddy hash. It has no diffusion: if you hash two 
strings which differ at one character position, the difference between the 
hashes will always be confined to the sixteen bits which correspond to 
where that character ended up in the rotating hash. Java's 
multiply-and-mod approach quickly spreads the bits of each character out 
over the whole hash.

tom

-- 
Science of a sufficiently advanced form is indistinguishable from magic

Re: find words that contains some specific letters

[John B. Matthews]

In article <alpine.DEB.1.10.0906070035110.5405@urchin.earth.li>,
 Tom Anderson <twic@urchin.earth.li> wrote:

> > John B. Matthews wrote:
> >> The jumble algorithm relies on a hashed map for efficiency, but a 
> >> perfect hash is not essential. I recently implemented the 
> >> algorithm in both Java and Ada using library routines:
> >> 
> >> <http://en.wikipedia.org/wiki/Jumble>
> >> <http://sites.google.com/site/drjohnbmatthews/jumble>
> >> <http://home.roadrunner.com/~jbmatthews/jumble.html>
> >> 
> >> I was intrigued to compare the two languages' library 
> >> implementations of a general purpose string hash. Using a 
> >> multiplicative function with an initial value of zero, both offer 
> >> excellent performance. Java uses a multiplier of 31 on a signed 
> >> 32-bit integer; Ada uses a multiplier of eight on an unsigned 
> >> (modular) value whose size is implementation defined (e.g. mod 
> >> 2**32):
> >> 
> >> <http://www.docjar.org/html/api/java/lang/String.java.html>
> >> <http://gcc.gnu.org/viewcvs/trunk/gcc/ada/a-strhas.adb>
> 
> John, i think you've missed a trick there - doesn't Rotate_Left do a 
> barrel shift, where the bits that fall off the left-hand end get 
> shoved back in at the right, rather than a plain shift? If so, the 
> basic algebraic structure is actually a bit different to java's hash.

D'oh, you're absolutely right. I overlooked this when I was tinkering 
with my own hash function, too. Thank you for looking at this.

[...]

> I still think this is a shoddy hash.

Well, it's a legacy from GNAT.HTable.Hash, but it does very well in the 
context of Ada.Containers.Hashed_Maps. Java uses a bucket list whose 
size is an integral power of two, while (this implementation of) Ada 
uses the next largest prime. Modeling an Ada collision counter on your 
example <http://urchin.earth.li/~twic/tmp/Collisions.java>, I got these 
results for collision count, number of buckets having that count, and 
the percentage of the total:

$ ./collisions 
 0: 218586 (55.6%)
 1: 126250 (32.1%)
 2: 38432 (9.8%)
 3: 8362 (2.1%)
 4: 1354 (0.3%)
 5: 229 (0.1%)
 6: 24 (0.0%)
 7: 4 (0.0%)
 8: 1 (0.0%)

The code is here: <http://home.roadrunner.com/~jbmatthews/jumble.html>

[Followup-To set to comp.lang.ada.]
-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>