On 24/02/2014, at 5:34 PM, Alan Silverstein wrote:
First: lets assume multiples of word size only. This is WLOG
due to the Ocaml trick: store the length of the string modulo
word size at the end of the string. This preserves lexicographical
ordering. For example a single byte 100 is encoded as
(100,0,0,1)
Four bytes:
(100,101,102,103),(0,0,0,0)
[32 bit machine]
Or something like this .. :)
> bytes appended. Each of those is unique at this level, but how do you
> distinguish, say in a 4-byte word, the value 0x11121300 (key ends after
> 0x13 byte) from the same byte pattern that's the leading part (all four
> bytes) of a longer key? You only get one value = subarray pointer from
> JudyL.
There are two issues, one is how to track the length when
recursing down the tree. That's easy in principle, just maintain
a depth counter. It's probably hard in practice.
The other problem is even easier. If there is a string ending
in this node, then set the low order but of the JudyL value.
Mask it back to zero when looking for the next array.
Use NULL if there are no keys with that proper prefix
(with the low bit set).
Hmm .. this could be done now using JudySL.
Instead of storing an integer value, store a pointer to a structure
containing a flag and an integer value. If the flag is set,
the null byte really was the end of the string, use the
integer value. If the flag is not set, its not the end of the string,
cast the integer value to a pointer which is the next JudySL
array. Null butes would be very expensive :)
--
john skaller
[email protected]
http://felix-lang.org
------------------------------------------------------------------------------
Flow-based real-time traffic analytics software. Cisco certified tool.
Monitor traffic, SLAs, QoS, Medianet, WAAS etc. with NetFlow Analyzer
Customize your own dashboards, set traffic alerts and generate reports.
Network behavioral analysis & security monitoring. All-in-one tool.
http://pubads.g.doubleclick.net/gampad/clk?id=126839071&iu=/4140/ostg.clktrk
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
