Algorithme pour la saisie semi-automatique?

Je voudrais juste dire...
Une bonne solution à ce problème est d'aller à incorporer plus d'un Ternaire Arbre de Recherche.
Ngrams, et les Bardeaux (Expressions) sont nécessaires. Mot-limite les erreurs doivent également être détecté. "l'enfer o" doit être "bonjour" ... et "whitesocks" doit être "chaussettes blanches" - ce sont des pré-étapes de traitement. Si vous n'avez pas prétraiter les données correctement, vous n'allez pas obtenir de précieux résultats de la recherche.
Ternaire arbres de recherche sont un élément utile dans la compréhension de ce qu'est un mot, et également pour la mise en œuvre connexes-parole de deviner quand un mot saisi n'est pas valide d'un mot dans l'index.

L'algorithme de google effectue une expression de la suggestion et de la correction.
L'algorithme de google a aussi la notion de contexte... si le premier mot que vous recherchez est liée aux conditions météorologiques et que vous les combinez "weatherforcst" vs "monsoonfrcst" vs "deskfrcst" - je suppose que derrière les scènes les classements sont en train d'être changé dans la suggestion basée sur le premier mot rencontrés - les prévisions et les conditions météorologiques sont liées mots devrait donc obtenir un rang élevé dans le Saviez-Vous-Dire deviner.

mot-partiels (ngrams), de la phrase, les termes (zona), mot de proximité (mot-clustering-index), ternaire-recherche-arbre (mot de recherche).

Il existe des outils comme soundex et levenshtein qui peuvent être utilisés pour trouver des correspondances floues qui sont dans une certaine plage.

Soundex trouve des mots que son semblable et de levenshtein trouve des mots qui sont à une certaine distance d'édition à partir d'un autre mot.

Pour les sous-chaînes et flous, l'algorithme de Levenshtein a fonctionné assez bien pour moi. Même si je dois admettre, il ne semble pas être aussi parfait que l'industrie des implémentations de saisie semi-automatique/suggérer. Google et Microsoft Intellisense faire un meilleur travail, je pense, parce qu'ils ont affiné cette algorithme de base de peser le genre d'opérations d'édition il faut pour correspondre aux différentes chaînes. E. g. la transposition de deux personnages devraient probablement seulement compter comme 1, pas 2 (un insert & supprimer).

Mais même si je trouve que c'est assez proche. Ici, c'est que c'est la mise en œuvre en C#...

//This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make
//it more like Google's autocomplete/suggest.  It returns the number of operations 
//(insert/delete/substitute) required to change one string into another, with the 
//expectation that userTyped is only a partial version of fullEntry.
//Gives us a measurement of how similar the two strings are.
public static int EditDistance(string userTyped, string fullEntry)
{
    if (userTyped.Length == 0) //all entries are assumed to be fully legit possibilities 
        return 0; //at this point, because the user hasn't typed anything.

    var inx = fullEntry.IndexOf(userTyped[0]);
    if (inx < 0) //If the 1st character doesn't exist anywhere in the entry, it's not
        return Int32.MaxValue; //a possible match.

    var lastInx = inx;
    var lastMatchCount = 0;
TryAgain:
    //Is there a better starting point?
    var len = fullEntry.Length - inx;
    var matchCount = 1;
    var k = 1;
    for (; k < len; k++)
    {
        if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx])
        {
            if (matchCount > lastMatchCount)
            {
                lastMatchCount = matchCount;
                lastInx = inx;
            }
            inx = fullEntry.IndexOf(userTyped[0], inx + 1);
            matchCount = 0;
            if (inx > 0)
                goto TryAgain;
            else
                break;
        }
        else
            matchCount++;
    }
    if (k == len && matchCount > lastMatchCount)
        lastInx = inx;

    if (lastInx > 0)
        fullEntry = fullEntry.Substring(lastInx); //Jump to 1st character match, ignoring previous values 

    //The start of the Levenshtein Distance algorithem.
    var m = userTyped.Length;
    var n = Math.Min(m, fullEntry.Length);

    int[,] d = new int[m + 1, n + 1]; //"distance" - meaning number of operations.

    for (var i = 0; i <= m; i++)
        d[i, 0] = i; //the distance of any first string to an empty second string
    for (var j = 0; j <= n; j++)
        d[0, j] = j; //the distance of any second string to an empty first string

    for (var j = 1; j <= n; j++)
        for (var i = 1; i <= m; i++)
            if (userTyped[i - 1] == fullEntry[j - 1])
                d[i, j] = d[i - 1, j - 1];       //no operation required
            else
                d[i, j] = Math.Min
                           (
                             d[i - 1, j] + 1,  //a deletion
                             Math.Min(
                             d[i, j - 1] + 1,  //an insertion
                             d[i - 1, j - 1] + 1 //a substitution
                             )
                           );

    return d[m, n];
}

Je pense que l'on pourrait être mieux de construction spécialisés trie, plutôt que la poursuite de complètement différent de la structure de données.

J'ai pu voir que la fonctionnalité se manifeste dans un trie dans lequel chaque feuille était un domaine qui reflète la fréquence des recherches de son mot correspondant.

La requête de recherche de la méthode d'affichage, le descendant les nœuds feuilles avec la plus grande des valeurs calculées à partir de la multiplication de la distance de chaque descendant nœud feuille par la fréquence de recherche associés à chaque descendant nœud feuille.

La structure des données (et, par conséquent, l'algorithme) utilisations de Google sont probablement beaucoup plus compliqué, potentiellement en tenant un grand nombre d'autres facteurs, tels que la recherche des fréquences à partir de votre propre compte (et à l'heure de la journée... et de la météo... la saison... et phase lunaire... et... ).
Cependant, je crois que la base trie de la structure de données peut être étendu à tout type de recherche spécialisé préférence en incluant des champs supplémentaires à chacun des nœuds et à l'aide de ces champs dans la requête de recherche de la méthode.