Ability to add score for top k results

[nhaberl]

Hi, its a nice library ... is there a way to add data to any Node so when retriueving thousand of results for given prefix only the top k results are returned.
Adding any kinf of score to an entry which is internally sorted would be great.
Guess any mix of length and score would be great ... so if there is a key which matches the prefix it should return always as with others which are ranked higher.

This allows for early termination when searching for top k (10 or 20) ...
A custom comparer would be fine so you can customize this behaviour.

[kpol]

Thanks for your feedback.
Could you please provide an example?
EnumerateByPrefix returns IEnumerable<T>, so you can simply use LINQ Take method and it won't iterate through the entire collection. If I understand your question correctly...

[nhaberl]

Yes but it has to be guaranteed that is sorted ... by any Comparer I set. So T should implement IComparable or the Trie itself to hold a sorted List (or similar)

[kpol]

Hm... can you provide an example (mb some pseudo-code?), because I can't get the idea

[nhaberl]

Yes the texts you add / index are sorted but I mean something like this

var trie = new Trie<T>(IComparer<T> comparer); // maybe new EntityOccurenceDescComparer() so all T values are automatically sorted so we can top 10 or 10 to 20 in a fast ways (SortedList maybe supports indexer)
trie.Add(new Entry() { Occurence = 12, Anything = "Nice one" });
...add more entries
var entries = trie.GetByPrefix("ch", int topK = 10) --> gets the top kost items by comparer (could do also over Take(...) if its IEnumerable()

The point is when you have millions of entries and wanna show up 10 to the user it's not useful to return all items of the trie ...

[kpol]

Not quite sure if I understood this correctly, just to confirm:
Let's say you have this object
class Entry { int Rank; }
You construct a trie:

var trie = new StringTrie<Entry>();
trie.Add("ch_key1", new Entry {Rank = 1});
trie.Add("ch_key2", new Entry {Rank = 1});
... 
trie.Add("ch_key100", new Entry {Rank = 50});

Then you want to select by prefix (e.g. "ch") let's say first 10 entries ordered by the highest Rank (priority), i.e. "select first 10 entries with prefix ch starting from the highest rank"

[nhaberl]

Yes, but in a performant way so the entries have to be presorted. So Linq is no option on the whole set.
Maybe its best to store inside a sortedlist or sorted set within the trie node.

One more example would be prefix "sch" in German language...there are 600000 words. But within my domain I manage some kind of statistics and would fetch these words based om that.

[kpol]

Got it. Yeah, it is not possible with the current implementation.
Right, probably the easiest way will be to extend TrieNode to be able to swap collection of the Children property.

[haneefkassam]

I suppose another example could be: word starting with "ch" sorted by occurrence (if you were parsing some text and incrementing the occurrence of words as a property on that node), but now we're drifting into elasticsearch/Apache Solr territory.

[nhaberl]

This isnexactly the same, you just use the occurence as score22:38, 7. Juli 2021, haneefkassam ***@***.***>: I suppose another example could be: word starting with "ch" sorted by occurrence (if you were parsing some text and incrementing the occurrence of words as a property on that node), but now we're drifting into elasticsearch/Apache Solr territory. —You are receiving this because you authored the thread.Reply to this email directly, view it on GitHub, or unsubscribe.

[haneefkassam]

I meant occurrences of words...every time a certain word occurs, update the occurrence of that word (in the example above, "Rank" could be "Occurrences"). I was just highlighting another use case to provide validity to the request.

[kpol]

@nhaberl Recently, I’ve done some work on the library and was looking into your case. Consider this example:

Trie trie = ["star", "start", "stack", "stop", "stay", "key"];
// where 'star' has rank 1, 'start' has rank 2, 'stack' has rank 3, etc

          {root}
            /\
           s  k
          /    \
         t      e
        / \      \
      a    o     [y]
    / | \    \
  [r][y] c   [p]
  /       \
[t]       [k]

where [char] -- is end of word

So the trie node s will need to somehow store these different ranks, then the node t will also need to store all the ranks, etc.
This will significantly increase the trie’s memory usage and complicate retrieval.

In your case, I think a more effective approach would be to have multiple tries, for example:

Trie trieRank1 = [ ... ]; // all words with rank 1
Trie trieRank2 = [ ... ]; // all words with rank 2
...

Then, if you need to select 10 words starting with "st" prioritizing rank 1 first, then rank 2, and so forth, you would:

First, select the required words from trieRank1.

If there are fewer than 10 results, select the remaining words from trieRank2, and so on.