2

In my app i have about 50Mb of strings that have lot's of common parts. I'd like to reduce memory consumption by using Radix Trie (Patricia Tree), eg. Apache collections impl.

The goal is to keep references to entries and get full strings once they are needed:

val trie = PatriciaTrie()
val node1 = trie.put("Long string #1", null) // what's the method to add and return TrieEntry?
someObject1.setNode(node1)
val node2 = trie.put("Long string #2", null)
someObject2.setNode(node2)
val node3 = trie.put("Long string #3", null)
someObject3.setNode(node3)

So i expect it to be stored in memory like follows:

 root
  \
   "Long string #"
                 \"1"
                 \"2"
                 \"3"

When it's needed i should be able to get full string (in someObjectN):

 val fullString = node.getKey(); // How can i do it?

There are 2 questions:

  1. How can i put a string to the trie and get TrieEntry instance? Since it implements java.util.map, put method returns value:

    public V put(final K key, final V value)

  2. How can i get full string from TrieEntry instance?

Values (node payload) are useless in my use case as primary goal is just save memory (without any payload).

Is Apache's PatriciaTrie suitable for that use case at all? Any thoughts?

4ntoine
  • 19,816
  • 21
  • 96
  • 220

0 Answers0