Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #32145

Re: Reduce dictionary lookups using LIT ?

Show key headers only | View raw

On Wed, 02 Jul 2014 17:30:03 -0400, chitselb <chitselb@gmail.com> wrote:
> On Tuesday, July 1, 2014 8:24:36 PM UTC-4, Rod Pemberton wrote:
>> Reduce dictionary lookups using LIT ? ...

> What I wound up doing was a Bloom filter.  Take each character of the  
> forth word.  Is it a digit?  Add that digit + 1 to the sum.  Finally,  
> take the sum modulo 64  (my filter has 64 bits) and index the bit.  Most  
> words like DUP ROT SWAP will total 0.  Anything that's a number or has a  
> number in it will be nonzero.  If the bit we are looking at in the Bloom  
> filter is off, that token can not be in the dictionary, and FIND can be  
> bypassed.

I recalled the name, but I had to look that up.

Really?  A Bloom filter?  Wow ...

I read the first paragraph on Wikipedia and immediately
knew it was to filter out inputs that would cause
unecessary collisions for hash functions.  Then, the
second paragraph said just that.

It appears you've mentioned this here in the past,
perhaps elsewhere ...  So, it's possible I'd read
Wikipedia on the topic previously.

Anyway, cool!

Couldn't you have just used an extensible perfect hash?

;-)


Do you think this is cool?

I have a 8-bit, brute-force, hash generator for strings
that gets about 120 non-collision values out of 256.
Yes, that's not quite 128 out of 256, but still almost
50%, on an *8-bit* value.  That's a near impossible
task by hand or random guess, as most hashes seem to
be designed.  (This is coded in C.)

The values for the hash function are produced via a
brute-force program.  It generates random values used
in the hash function.  The program runs the entire set
of strings through the hash function.  It identifies
the total collisions per string set and total collisions
per hash value.  It repeats this for numerous iterations.
Once the total collisions and collisions per hash value
are low enough for a given hash, it displays the values
used for the hash.

I've used it with a simple DOS style command interpreter.
It uses the names of various DOS commands.  The set I chose
to use has only one collision between two words, upper-
and lowercase of the same word.  IIRC, I originally used
it, or a variation, for hashes on a C language keyword set.

The algorithm is really simple: 128 random bytes, another
128 bytes with the same values.  This constitutes an ASCII
8-bit character lookup table that adds bit randomness to
the string.  I.e., it's a string conversion like upper- or
lower-case, but to randomized values.  These were determined
by brute-force for minimal collisions on the entire string
set.  The hash function itself is just the XOR of the hash,
starting with zero, with the random value from the character
translation table for each character plus a constant, for
each character in the string.  The constant is also
randomized.

I hadn't thought to try it with the Forth ANS core
or core extension names since I had no apparent need
of it in my Forth interpreter.  I don't have a list of
them as text.  Of course, the Forth wordset isn't fixed,
so it wouldn't be of use for additionally defined words.
I.e., the dataset is not fixed, but it would be useful
for the initial dictionary, or perhaps where the
dictionary is fixed, maybe an embedded environment.


Rod Pemberton

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-01 20:24 -0400
  Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-01 19:39 -1000
    Re: Reduce dictionary lookups using LIT ? bruce.mcfarling@gmail.com - 2014-07-02 10:30 -0700
      Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-02 08:53 -1000
      Re: Reduce dictionary lookups using LIT ? Mark Wills <markwills1970@gmail.com> - 2014-07-02 13:47 -0700
        Re: Reduce dictionary lookups using LIT ? BruceMcF <agila61@netscape.net> - 2014-07-02 19:45 -0700
          Re: Reduce dictionary lookups using LIT ? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-07-03 16:56 +0000
            Re: Reduce dictionary lookups using LIT ? bruce.mcfarling@gmail.com - 2014-07-03 10:34 -0700
  Re: Reduce dictionary lookups using LIT ? Mark Wills <markwills1970@gmail.com> - 2014-07-02 01:27 -0700
    Re: Reduce dictionary lookups using LIT ? Bernd Paysan <bernd.paysan@gmx.de> - 2014-07-02 17:11 +0200
      Re: Reduce dictionary lookups using LIT ? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-07-02 16:31 +0000
        Re: Reduce dictionary lookups using LIT ? Bernd Paysan <bernd.paysan@gmx.de> - 2014-07-02 20:32 +0200
      Re: Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-03 03:01 -0400
        Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-02 21:42 -1000
        Re: Reduce dictionary lookups using LIT ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-03 16:05 +0000
    Re: Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-03 03:00 -0400
  Re: Reduce dictionary lookups using LIT ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-02 09:35 +0000
    Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-02 06:51 -1000
  Re: Reduce dictionary lookups using LIT ? chitselb <chitselb@gmail.com> - 2014-07-02 14:30 -0700
    Re: Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-03 03:51 -0400
  Re: Reduce dictionary lookups using LIT ? Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2014-07-03 02:41 -0700
    Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 11:44 +0100
      Re: Reduce dictionary lookups using LIT ? Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2014-07-03 06:03 -0700
        Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 15:16 +0100
          Re: Reduce dictionary lookups using LIT ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-03 16:31 +0000
            Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 19:58 +0100
              Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 20:02 +0100

csiph-web