Algorithme pour la saisie semi-automatique?

(heh) génial floue ou partielle de la chaîne des algorithmes d'appariement, découvrez Sacrément Cool Algorithmes:

• http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

ceux-ci ne remplacent pas les essais, mais empêchent plutôt la recherche de force brute dans les essais - qui est encore un grande victoire. Ensuite, vous voulez probablement un moyen de lier la taille du trie:

• tenir un essai des mots récents / Top N utilisés à l'échelle mondiale;
• pour chaque utilisateur, gardez un essai de mots récents/Top N pour cet utilisateur.

enfin, vous voulez prévenir les recherches chaque fois que possible...

• résultats de recherche de cache: si l'utilisateur clique sur les résultats de recherche, vous pouvez servir ceux-ci très rapidement et puis récupérez de façon asynchrone la totalité de la recherche partielle/floue.
• précalculer les résultats de la recherche: si l'utilisateur a tapé "appl", ils sont susceptibles de continuer avec "apple", "appliquer".
• données de préfetch: par exemple, une application web peut envoyer un plus petit ensemble de résultats au navigateur, assez petit pour rendre la recherche brute-force dans JS viable.

j'aimerais juste dire... Une bonne solution à ce problème va intégrer plus qu'un arbre de recherche ternaire. Ngrams, et Shingles (Phrases) sont nécessaires. Il faut également déceler les erreurs de délimitation des mots. "l'enfer o" doit être "bonjour" ... et " whitesocks "devrait être" white socks " - ce sont des étapes de pré-traitement. Si vous ne prétraitez pas les données correctement, vous n'obtiendrez pas de résultats de recherche valables. Les arbres de recherche ternaires sont un élément utile pour déterminer ce qu'est un mot, et aussi pour la mise en œuvre de la devinette de mots apparentés quand un mot tapé n'est pas un mot valide dans l'index.

l'algorithme de google effectue la suggestion et la correction de phrase. L'algorithme de google a également un certain concept de contexte... si le premier mot que vous recherchez est lié à la météo et que vous les combinez "weatherforcst" vs "monsoonfrcst" vs "deskfrcst" - mon hypothèse est dans les coulisses les classements sont en train d'être changés dans la suggestion basée sur le premier mot rencontré - Prévision et la météo sont des mots liés donc la prévision obtenir un rang élevé dans le di-Vous-moyen 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 distance qui peuvent être utilisés pour trouver des correspondances floues qui se situent dans une certaine fourchette.

Soundex trouve des mots qui semblent similaires et levenshtein distance trouve des mots qui sont à une certaine distance d'édition d'un autre mot.

regardez Awesome bar de Firefox algorithme

Google suggest est utile, car il prend en compte les millions de requêtes populaires + vos requêtes associées passées.

il n'a pas un bon algorithme d'achèvement / UI cependant:

1. Ne pas faire de sous-chaînes
2. semble être un algorithme de préfixe de limite de mots relativement simple.
   
   Par exemple: essayez tomcat tut --> suggérez correctement "tutoriel tomcat". Maintenant, essayez tomcat rial -- > pas de suggestions ) -:
3. ne supporte pas " tu veux dire?"- comme dans les résultats de recherche google.

l'algorithme exact de Google est inconnu, mais il est dit pour travailler par l'analyse statistique des entrées des utilisateurs. Une approche qui ne convient pas dans la plupart des cas. Le plus souvent, l'auto completion est mise en œuvre à l'aide de l'un des éléments suivants:

• Arbres . En indexant le texte à rechercher dans une structure arborescente (arbre de préfixe, arbre de suffixe, dawg, etc..) on peut exécuter des recherches très rapides au détriment du stockage de mémoire. Arbre la traversée peut être adapté pour la correspondance approximative.
• Schéma De Partitionnement . En partitionnant le texte en jetons (ngrams), on peut exécuter des recherches d'occurrences de pattern en utilisant un simple système de hachage.
• filtrage . Trouver un ensemble de correspondances possibles et ensuite appliquer un algorithme séquentiel pour vérifier chaque candidat.

regardez complètement , une bibliothèque Java autocomplete qui implémente certains de ces derniers concepts.

pour les substrats et les correspondances floues, L'algorithme de distance de Levenshtein a assez bien fonctionné pour moi. Bien que je dois admettre qu'il ne semble pas être aussi parfait que les mises en œuvre de l'industrie d'autocomplete/suggest. Google et Intellisense de Microsoft font un meilleur travail, je pense que parce qu'ils ont raffiné cet algorithme de base pour peser le genre d'opérations d'édition qu'il faut pour correspondre aux chaînes dissemblables. Par exemple: la transposition de deux caractères ne devrait probablement compter que pour une opération, pas pour deux (an insérer et supprimer).

mais je trouve que c'est assez proche. Voici sa 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];
}

si vous cherchez une conception globale pour le problème, essayez de lire le contenu à https://www.interviewbit.com/problems/search-typeahead / .

ils commencent par construire autocomplete par une approche naïve d'utiliser un trie et puis construire sur elle. Ils expliquent également les techniques d'optimisation comme l'échantillonnage et les mises à jour hors ligne pour répondre aux cas d'utilisation spécifiques.

pour garder la solution évolutive, vous devez partagez vos données intelligemment.

je pense qu'il serait préférable de construire un tri spécialisé plutôt que de poursuivre une structure de données complètement différente.

je pouvais voir cette fonctionnalité manifestée dans un trie dans lequel chaque feuille avait un champ qui reflétait la fréquence des recherches de son mot correspondant.

la méthode de requête de recherche affichera les noeuds de feuilles descendantes avec les plus grandes valeurs calculées en multipliant la distance à chaque descendant nœud foliaire par la fréquence de recherche associée à chaque nœud foliaire descendant.

la structure des données (et par conséquent l'algorithme) que Google utilise sont probablement beaucoup plus compliquées, prenant potentiellement en compte un grand nombre d'autres facteurs, tels que les fréquences de recherche à partir de votre propre compte (et l'Heure de la journée... et de la météo... saison... et phase lunaire... et... ). Cependant, je crois que la structure de base des données trie peut être étendue à n'importe quel type de recherche spécialisée. préférence en ajoutant des champs additionnels à chacun des noeuds et en utilisant ces champs dans la méthode de requête de recherche.