LSH per un elenco di parole

Sto cercando di scrivere un correttore ortografico, ho una lista di parole enorme (almeno 500K, a causa della natura della lingua). La performance ne risentirebbe molto se avessi la distanza di lavenshtein di tutte le parole nella wordlist nella parola corrente.

Quindi sto cercando di distribuire la lista delle parole in bucket in base ai caratteri nella parola. In questo modo, ho solo bisogno di ottenere la distanza Levenshtein delle parole nel bucket specifico anziché l'intera lista di parole.

Quindi mi chiedevo se esistono buoni algoritmi di hash di Locality Sensitive per il mio problema? Ho scritto un algoritmo molto semplice che sembra funzionare bene e la performance è almeno 20 volte migliore. Anche se la precisione soffre un bel po '.

Ecco cosa ho scoperto:

static string GetHash(string word)
{
    word = word.ToUpperInvariant();
    var lettersToTake = word.Length - (int)(word.Length * 0.70);

    var chars = word.GroupBy(c => c)
                    .OrderByDescending(c => c.Count())
                    .ThenBy(c => GetFrequency(c.Key))
                    .Take(lettersToTake)
                    .Select(g => g.Key)
                    .ToList();

    return new string(chars.ToArray());
}

Ecco i passaggi dell'algoritmo:

1. Capitalizza tutti i caratteri
2. Ordina i caratteri nella parola in base alla frequenza della lettera nella parola
3. Quindi ordina i caratteri in base alla frequenza della parola nell'intero elenco di parole (GetFrequency)
4. Prendi il 30% dei caratteri nella parola