Najbardziej wydajne i dokładne podpowiadanie słów

Witam serdecznie,

mam problem z algorytmem podpowiadania słów podczas wpisywania tekstu.
Stworzyłem sobie listę obiektów:

    public class FrequentDictionary
    {
        public string Value { get; set; }
        public int Frequent { get; set; }
        public int LevenshteinLength { get; set; }
        public uint IsPrivate { get; set; }
    }

Zaczytałem do pamięci 3mln takich obiektów.
Następnie przy wpisywaniu każdej nowej litery obliczam odległość Levenshteina:

checkedList = frequentDictionary.Where(x => x.Value.StartsWith(text.Remove(1))).Select(item => new FrequentDictionary()
{
     Value = item.Value,
     Frequent = item.Frequent,
     LevenshteinLength = LevenshteinDistance.Compute(text, item.Value),
});

Samo obliczanie odległości Levenshteina w ten sposób zajmuje bardzo szybko: 2-3ms.
Aby znaleźć najlepsze dopasowanie filtruję tą listę w taki sposób:

var bestMatched = checkedList.OrderBy(x => x.LevenshteinLength)
                    .ThenByDescending(x => x.Frequent)
                    .Take(5);

No i wiadomo, że tu następuje załamanie prędkości. Materializacja sortowań zajmuje do 3000ms na moim kompie.
Próbuję przerobić to na HashSet'y ale na razie z mizernym skutkiem.
Mógłby mi ktoś podpowiedzieć jakie będzie najlepsze rozwiązanie?

Pozdrawiam.

Przecież nie potrzebujesz podpowiadania trzech milionów słów, tylko pewnie na przykład dziesięć najbardziej prawdopodobnych - nie sortuj więc wszystkich słów, tylko wybieraj te o najwyższej wartości funkcji oceny - bez problemu da się to zrobić w czasie liniowym.

Linq robi lazy evaluation, i i żadne metody nie są wywoływane aż do take(5). dlatego obliczenie odległości 3 milionów rektorów 'zajmuje' tylko 3ms, co swoja drogą jest nie realne.
Wywal to text.Remove(1), i zobacz czy jest różnica, powinno być trochę szybciej, bo tworzenie nowego stringa 3 miliony razy jednak trochę zasobów zużywa.

Możesz to też na pisać zwykłym forem/ foreachem, i wyniki dodawać do jakiegoś kopca, to nie wiele roboty i będzie szybciej, zwłaszcza jak dodasz if'a na odrzucającego zbytnio oddalone wyniki(gorsze od 5). Mnożnik przy sortowaniu ( ln n) spadnie Ci kilkukrotnie, i zaoszczędzisz czas na tworzeniu nowych obiektów. Poza tym for/foreach mozesz zamienic na parallel for/foreach tylko dużo zalezy od użytej struktury danych. Najprościej obejść wszystkie problemy,z równoległością dodając wyniki do listy. a potem podzielić listę indeksami na Environment.ProcessorCount części i odpalić Parallel.Invoke, i każdą z tych części sortować strukturą danych, a potem z wyników wybrać 5 najlepszych. Obliczenia będą prawie idealnie równoległe wiec kod będzie pare razy szybszy.

Jeśli nie przeszkadza Ci ograniczenie na maksymalną odległość edycyjną możesz skorzystać z bkTree i obliczałbyś odległość tylko 5-10% wszystkich słów.
https://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/

Ps. nie zapomnij włączyć optymalizacji w właściwościach projektu, i budować na wybraną architekturę.