Inner weights order in dictionaries

[AlejandroMarin-Veeva]

Hi Hendrick, hope you are doing well! :)

I have a question related to the weights and the order of the matches in complete_multiword. In the following example:

import keyvi
from keyvi.compiler import CompletionDictionaryCompiler
from keyvi.dictionary import Dictionary

compiler = CompletionDictionaryCompiler()
compiler.add("a", 1)
compiler.add("ab", 2)
compiler.add("abc", 3)
compiler.compile()
compiler.write_to_file("dict.kv")


d = Dictionary("dict.kv")
[(match.weight, match.matched_string) for match in list(d.complete_multiword("a"))]

I would expect to return first the key with the highest weight, 3, however is returning them in alphabetical order. Why is that the case?

[(1, 'a'), (2, 'ab'), (3, 'abc')]

[hendrikmuhs]

That's because of depth-first traversal, at lookup keyvi 1st traverses to the highest weight, however if it finds final states on the way it returns those. If you change abc to def, it returns [(2,'def'),(1, 'a'), (2, 'ab')]. Note, again it would return a before ab, but only because a is on the path to ab.

By design I decided to not built any kind of memory into the traversers to keep them as lightweight as possible. Imagine: if I want to return in order, I would need to remember a and ab until I know I can return them. In extreme cases this could lead to memory spikes. That's why I left this to the client.

[AlejandroMarin-Veeva]

Thanks for your answer. And what about the case where the same query has several matches? The results are also not ordered by weight and also the order depends on the order added.

As an example, when adding 100 keys with the same query but different value, the order retrieved when inserted 0 to 99 is, for the first samples:

[('profile:0', 0),
('profile:9', 9),
('profile:99', 99),
('profile:98', 98),
('profile:97', 97),
('profile:96', 96),
('profile:95', 95),
('profile:94', 94),
('profile:93', 93),
('profile:92', 92),
('profile:91', 91),
('profile:90', 90),
('profile:8', 8),
('profile:89', 89),

When inserted 99 to 0:

[('profile:0', 99),
('profile:1', 98),
('profile:10', 89),
('profile:11', 88),
('profile:12', 87),
('profile:13', 86),
('profile:14', 85),
('profile:15', 84),
('profile:16', 83),
('profile:17', 82),
('profile:18', 81),
('profile:19', 80),
('profile:2', 97),
('profile:20', 79),
('profile:21', 78),
('profile:22', 77),
('profile:23', 76),

And the code used:

import keyvi
from keyvi.compiler import CompletionDictionaryCompiler
from keyvi.dictionary import Dictionary

MULTIWORD_QUERY_SEPARATOR = '\x1b'
compiler = CompletionDictionaryCompiler()
for i in range(100):
    compiler.add(f"a{MULTIWORD_QUERY_SEPARATOR}profile:{99-i}", i)
compiler.compile()
compiler.write_to_file("dict.kv")


d = Dictionary("dict.kv")
matches = [(match.matched_string, match.weight) for match in list(d.complete_multiword("a"))]
matches

What will be the solution in this case to retrieve the values matching "a" in descending order of weight?

[hendrikmuhs]

The reason is depth-first-traversal:

• the traverser goes directly to the top-match: ('profile:0', 99),
• afterwards it finds the 2nd best ('profile:1', 98)
• the 3rd one: ('profile:2', 97) however gets reported after all keys that have the same prefix as the match for number 2: (('profile:1', 98)): ('profile:10', 89), ('profile:11', 88), because of the tree:

p->r->o->f->i->l->e->:->1                   #98
                         `>0                #89
                         `>1                #88
                         `>2                #87

The traverser has to visit all subnodes, before it can go into the sub-tree profile:2. The same happens again regarding the next best match, before visiting profile:3, the traverser visits profile:{20, 21, 22,...}

To effectively find the top-n results, you can use a collector that sets the min weight, here an example for top-5:

from keyvi.dictionary import Dictionary

MULTIWORD_QUERY_SEPARATOR = '\x1b'
compiler = CompletionDictionaryCompiler()
for i in range(100):
    compiler.add(f"a{MULTIWORD_QUERY_SEPARATOR}profile:{99-i}", i)
compiler.compile()
compiler.write_to_file("dict.kv")


d = Dictionary("dict.kv")

import heapq
heap=[]

class TopNFilter:
    def __init__(self, n) -> None:
        self.n = n
        self.heap = []

    def filter(self, completer):
        for m in completer:
            if len(self.heap) < self.n:
                heapq.heappush(self.heap, m.weight)
                yield m
            elif m.weight > self.heap[0]:
                heapq.heappop(self.heap)
                heapq.heappush(self.heap, m.weight)

                print(f"prune the search tree by setting min_weight={self.heap[0]}")
                completer.set_min_weight(self.heap[0])
                yield m

n=5

top_n = TopNFilter(n)
matches = [(match.matched_string, match.weight) for match in top_n.filter(d.complete_multiword("a"))]

print(f"\nmatches after traversing: {matches}\n")

sorted_matches = sorted(matches, key=lambda m: m[1], reverse=True)[:n]
print(f"matches after sort: {sorted_matches}")

this outputs:

prune the search tree by setting min_weight=88
prune the search tree by setting min_weight=89
prune the search tree by setting min_weight=95

matches after traversing: [('profile:0', 99), ('profile:1', 98), ('profile:10', 89), ('profile:11', 88), ('profile:12', 87), ('profile:2', 97), ('profile:3', 96), ('profile:4', 95)]

matches after sort: [('profile:0', 99), ('profile:1', 98), ('profile:2', 97), ('profile:3', 96), ('profile:4', 95)]

• pruning the search tree means: we do not visit nodes that have a lower inner weight than the given weight
  • that's why we do not visit e.g. ('profile:12', 87), because we already have 5 results that are better
  • in a similar way we prune 2 more times, the last one 95 rules out all sub-trees profile:{5,6,7,8,9}
• we collected 8 matches out of 100 to get a list of matches that guaranteed contain the top-5, however it is 8 not 5
• to finally retrieve the top-5 we sort the list and cut it

I hope this helps.

[AlejandroMarin-Veeva]

This really helps, thank you so much for the detailed explanation.

My main confusion came from the fact that I thought that the weight was helping the search by ordering also the children of the trees, but it is helping only in the nodes which children are not leaves. For that, the tree structure should maintain an ordered list of children by weight which I suppose is not the case.

Thanks again for all the details.

[hendrikmuhs]

For that, the tree structure should maintain an ordered list of children by weight which I suppose is not the case.

In a normal dictionary the weight is only attached to the leaf. Coming from a completion use case, you would have no idea in which order to traverse the dict. It would just use lexicographic order(you can try this if you replace CompletionDictionaryCompiler with IntDictionaryCompiler).

In a completion dict the inner weight is the max of all inner weights from outgoing states, starting from the weight of the leaf propagating from "right to left":

abcx -> 1
abdy -> 2
abez -> 3

inner weight of c = weight of x = 1
inner weight of d = 2
inner weight of e = 3

For b, we have 3 outgoing states c, d, and e, so

inner weight of b = max(1,2,3) = 3
inner weight of a = max(3) = 3.

On lookup. after prefix "ab":

A normal dict would go in lexicographic order: c, d, e
The completion dict however re-orders the traversal according to the inner weights e(3), d(2), c(1)

That's why we always go the most promising path first. The top result is found in O(1). For the 2nd, 3rd, 4th best result it gets tricky. This is where the collector above comes into play. For that it is a combination of taking the best routes and taking the "weakest result" as minimum weight and pruning the traverser at runtime. I think this is still quite effective, as written above we found the top 5 results by only looking at 8 keys. This approach usually works quite well, but there are definitely corner cases, e.g. if the 2nd/3rd/4th best is in a completely different branch. In this case it can happen that the depth-first-search approach spends too much time in subtrees before finding the final matches. I have been thinking about combining DFS with BFS somehow, however it is tricky and would require e.g. backtracking.

One more remark about:

the tree structure should maintain an ordered list of children by weight

Already the inner weight makes completion dicts much larger, storing more weights means a larger dict which in the end might mean more read operations on lookup.