Re: Trie?

[David Kastrup <dak@...>]

Philippe Lhoste <PhiLho@GMX.net> writes:

> Some words on my algorithm: I developed an idea on a fast and compact
> dictionary. Frankly, I don't know if it can be faster than a hash
> table, although I have no collisions to manage, and every bit stored
> is useful (no holes). And it was fun to implement!
>
> The dictionary build is very slow and write only: if you want to add a
> word afterward, you have to rebuild the trie from scratch... Not a
> problem for a lexer, for example, which has a fixed list of words
> (primary use case).
>
> I started to write the C implementation, but I have yet to finish
> it. I will publish it under my usual zlib/libpng license once it is
> well tested. Just in case somebody is foolish enough to try it... :-P
>
> PA, I am not sure my code can have any utility for you (it is mostly
> to check whole words, although one can end before reaching the end)
> but it was an opportunity to show it. ;-)

Given today's insanity and your description of the algorithm's
_performance_ characteristics (without any of the implementation
details), I consider it likely somebody will already have patented it.
So you might see yourself unable to provide this as suitably free
software (with patents, however, it is the duty of the _user_ rather
than the distributor to check for possible violations if I understand
correctly), unless you can dig up a previous publication ("The Art of
Computer Programming" is rather good for that) that would point to the
non-patentability of the algorithm.

-- 
David Kastrup