Algorithme de Trie || Fonctionnalité de saisie semi-automatique utilisant Javascript

Introduction

Un Trie, également connu sous le nom d'arbre de préfixes, est une structure de données arborescente spécialisée qui est utilisée pour une récupération efficace des informations.

C'est particulièrement utile pour les cas d'utilisation qui impliquent une recherche et une correspondance de préfixes dans des chaînes.

1. Si je vous parle de l'algorithme de Trie, cet algorithme pourrait vous intéresser ou non

2. Mais si je vous disais, vous pouvez créer un algorithme de saisie semi-automatique en utilisant ceci. vous serez plus excité d'apprendre cela.

Cas d'utilisation de cet algorithme

1. Saisie semi-automatique :

a. Les essais sont souvent utilisés dans les moteurs de recherche ou les éditeurs de texte pour implémenter la fonctionnalité de saisie semi-automatique.
b. Lorsque vous commencez à taper, l'application suggère des complétions possibles en fonction du préfixe que vous avez saisi.

2. Correcteurs orthographiques :

a. Les essais peuvent être utilisés pour implémenter des correcteurs orthographiques. Si un mot n'est pas présent dans le trie, il est probablement mal orthographié.
b. Le trie peut également suggérer des corrections en trouvant des mots similaires.

3. Routage IP :

a. Les essais sont utilisés dans les routeurs pour stocker les tables de routage.
b. Le routeur utilise un essai pour faire correspondre le préfixe le plus long, ce qui détermine le prochain saut d'un paquet.

4. Stockage et recherche efficaces de chaînes :

a. Si vous disposez d'un ensemble de données de chaînes contenant de nombreux préfixes partagés, un trie peut stocker ces chaînes en utilisant moins d'espace que de les stocker individuellement.
b. L'opération de recherche est également efficace, avec une complexité temporelle proportionnelle à la longueur de la chaîne que vous recherchez.

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

class Trie {
    constructor() {
        this.root = new Node ();
    }

    insert(word) {
        let head = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!head.children[word[i]]) {
                head.children[word[i]] = new Node();
            }
            head = head.children[word[i]];
        }
        head.end = true;
    }

    search(word){
        let current = this.root;

        for (let i = 0; i < word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]]
        }

        return true;
    }

    autoComplete(word) {
        let current = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]];
        }
        if (Object.keys(current.children).length === 1) {
            console.log('Please Type More...');
            return;
        }
        console.log('children =---> ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word+key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

N'hésitez pas à me contacter si vous avez des préoccupations/questions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!