lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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. ;-)

Philippe Lhoste
--  (near) Paris -- France
--  --  --  --  --  --  --  --  --  --  --  --  --  --