Marisa-Trie – Matching Algorithm with Recursively Implemented Storage (code.google.com) 19 points by wfunction 10y ago ↗ HN
[–] amelius 10y ago ↗ How fast are (small) updates to the trie? (Does the trie need to be recomputed from scratch?) [–] wfunction 10y ago ↗ Good call! Apparently it's a static, not dynamic, data structure. http://kmike.ru/python-data-structures/ [–] madisonmay 10y ago ↗ So in other words, O(n) where n is the number of elements in the trie? That's rough.
[–] wfunction 10y ago ↗ Good call! Apparently it's a static, not dynamic, data structure. http://kmike.ru/python-data-structures/ [–] madisonmay 10y ago ↗ So in other words, O(n) where n is the number of elements in the trie? That's rough.
[–] madisonmay 10y ago ↗ So in other words, O(n) where n is the number of elements in the trie? That's rough.
[–] madisonmay 10y ago ↗ I've used this thing to reduce the size of scikit-learn's TfidfVectorizer, which stores a giant dictionary of words --> occurrence counts, and have seen close to 10X memory reductions. Great project!
[–] rurban 10y ago ↗ I updated it here: https://github.com/rurban/marisa-trie with the original wiki docs and some fixes for latest toolchains
5 comments
[ 4.9 ms ] story [ 35.9 ms ] thread