method to convert CharTrie into a compact trie for space-optimized representation (feature request)

[manthanchauhan]

char_trie['he'] = 3
char_trie['him'] = 4

---h

    |__e: 3

    |__i

        |__m: 4

can be compressed as,
---h

    |__e: 3

    |__i m:4

since removing each redundant node saves atleast 56 bytes, this can provide high memmory optimisation to a data structure that is used for memmory optimized storage.

[manthanchauhan]

I'd like to contribute code for this, if required.

[mina86]

I’m always happy to review pull requests though adding a ‘compressed’ representation to the library is rather involved change so this might benefit from discussion of the design before code is written. There are non-obvious cases to consider such as how would the data structure look with trie['foo'] = trie['foobar'] = trie['foobarbaz'] = 42.

Lastly, you should be looking at https://github.com/mina86/pygtrie repository since that’s where the latest code resides.

[manthanchauhan]

One solution for the example you provided is, node decomposition, as shown,
trie['foobarbaz'] = 42

---foobarbaz: 42

trie['foobar'] = 42
no we will perform sub-string matching of 'foobar' starting from the keys at root node. From the first character in 'foobar' we'll find a key in the node such that it has the same corresponding characters.

in this example, 'foobar' matched with 'foobarbaz' upto 5th position, therefore, the root node breaks at the 5th position creating,
---foobar: 42

   |-- baz: 42

after trie['foo'] = 42,
---foo: 42
   |-- bar: 42
       |-- baz: 42

It is to be noted that, at a node, no two keys start form same character and hence time complexity of addition is unaffected after compression.

[manthanchauhan]

In the above trie, if I perform,
trie['foobie'] = 9

the resulting structure would be,
---foo: 42
   |-- b
       |--ie: 9
       |--ar: 42
           |-- baz: 42

ie, node with key 'bar' decomposed at 0th position ('b').

[mina86]

What if I then did trie['bar'] = 42? If I understand you correctly, you suggest that the root node would keep ‘foo’ as the key in children dictionary but that won’t quite work and goes opposed to how trie is meant to behave.

[manthanchauhan]

If you do trie['bar'] = 42,
the root node will now have two children, one with key 'foo' and another with key 'bar'. I don't understand your point, how does it violates any behaviour of a trie.

[mina86]

When a lookup for ‘foo’ is done, trie’s behaviour is to look for a child ‘f’ of the root node. If root’s node children wolud hold ‘foo’ and ‘bar’, you’d never find ‘foo’ in there.

[manthanchauhan]

Look-ups would be implemented similar to additions, at each node we find the key which has the same first character as that of the query,
If I were to look-up for 'foobar' in the following trie,
---foo: 42
   |-- b
       |--ie: 9
       |--ar: 42
           |-- baz: 42

at root node 'foo' starts with an 'f' just like 'foobar', this indicates that 'foobar' must belong to the subtrie at 'foo'.

in the 'foo' subtrie now we lookup for 'bar', this time 'b' matches with 'bar',

now in 'b' subtrie we look-up for 'ar' where it matches with 'ar', since the query has been found, we stop here.

Yes, at every node, we need to traverse to all the children until we find the matching first character, therefore time complexity increases. But, lots of storage is saved which is often helpful for storage concerned applications.

[mina86]

The _Node object has two fields: children and value. In your diagram, what does:

---foo: 42
   |-- b

correspond to? What’s the value of children and value fields in the root node?

Because if the root node has children field equal to a {'foo': <some-node-object>} than there is no efficient way to find the foo key when looking for foobar since the way trie works is that you will look for a child under f.

When I say that design discussion may be in order, I mean discussion of how each kind of node is represented. What are children and value fields values and how are key lookup, addition and deletion performed.

[manthanchauhan]

Your interpretation of children field is correct.

after compression, now trie keys are strings and hence now at each node, rather than looking of a character like 'f' we look for strings beginning with 'f' like 'foo',

at each node, log(N) complexity is required to find a key, where N is the total number of children of that node. Yes the operations are not time efficient, but this is the cost of the saved memory space.

If I'm right, combining each pair of nodes saves 56B.

[mina86]

at each node, log(N) complexity is required to find a key, where N is the total number of children of that node.

I don’t see how that’s correct. The actual complexity is linear to the length of the prefix. Recall that Python uses hash maps for dictionaries, not binary search trees. As a result, when looking for child ‘foobar’ you have to first check ‘f’, than ‘fo’, then ‘foo’ etc.

At that point it’s simpler to just have a flat dictionary and do key lookups by doing longer and longer prefix matches.

[manthanchauhan]

Actually, at one node there will be only one key starting from 'f' or any other character. In the following trie,
---foo: 42
   |-- bar: 42

if I do trie['foob'] = 9
this happens,
---foo: 42
   |-- b: 9
        |--ar: 42

the node with key 'bar' decomposes at 'b' to avoid having both 'bar' and 'b' as keys.

Once we match the first character of query (in O(logN) ), we can simply traverse the matched key to find out upto which position it matches with the query ie, 'foo' with 'foob' upto 2nd position, then in the subtrie we search for remaining part of the query ie. the remaining 'b' of 'foob'.

[mina86]

So then also if I add trie['bar'] = 42 the root node gets decomposed?

[manthanchauhan]

no, in this case the root node will have one more key as 'bar', due to the fact that no existing key of root node matches with 'b'.

[mina86]

So again, how do you look up a key in such a node?