The fastest autocomplete + sorting, which date structure to choose?

Question

Algorithms

Good afternoon.
There was a task of searching through autocomplete, I did trie, but sorting is very slow
150,000 words with a priority
of 10,000 requests, it should work no more than 10 seconds.
Console application, output 5 seconds

Answer 1

Answer found, used 2 structures, trie+red-black trees.
Each node has a SortedSet collection, it works like a red-black-tree.
Accordingly, the collection includes all the nodes that pass the tree.
We end up with a sorted collection.
As for memory, it’s just not efficient, but classes are used there for the node, not structures. So only references are stored in the collection.
There was no memory requirement.

Answer 2

• Bloom filter.
  
• Bor Aho-Korasik.