Trie-Algorithmus || Autovervollständigungsfunktion mit Javascript

Einführung

Ein Trie, auch Präfixbaum genannt, ist eine spezielle baumbasierte Datenstruktur, die zum effizienten Abrufen von Informationen verwendet wird.

Es ist besonders nützlich für Anwendungsfälle, bei denen es um die Suche und den Präfixabgleich innerhalb von Zeichenfolgen geht.

1. Wenn ich Ihnen vom Trie-Algorithmus erzähle, könnten Sie an diesem Algorithmus interessiert sein oder auch nicht

2. Aber wenn ich Ihnen sagen würde, dass Sie damit einen Autovervollständigungsalgorithmus erstellen können. Sie werden mehr Freude daran haben, dies zu lernen.

Anwendungsfall dieses Algorithmus

1. Automatische Vervollständigung:

a. In Suchmaschinen oder Texteditoren werden häufig Versuche verwendet, die Autovervollständigungsfunktion zu implementieren.
B. Wenn Sie mit der Eingabe beginnen, schlägt die Anwendung basierend auf dem von Ihnen eingegebenen Präfix mögliche Vervollständigungen vor.

2. Rechtschreibprüfung:

a. Versuche können zur Implementierung von Rechtschreibprüfungen verwendet werden. Wenn ein Wort im Versuch nicht vorkommt, ist es wahrscheinlich falsch geschrieben.
B. Der Versuch kann auch Korrekturen vorschlagen, indem er ähnliche Wörter findet.

3. IP-Routing:

a. Versuche werden in Routern verwendet, um Routing-Tabellen zu speichern.
B. Der Router verwendet einen Versuch, um das längste Präfix zu finden, das den nächsten Hop für ein Paket bestimmt.

4. Effizientes Speichern und Suchen nach Zeichenfolgen:

a. Wenn Sie einen Datensatz mit Zeichenfolgen haben, in dem es viele gemeinsame Präfixe gibt, kann ein Versuch diese Zeichenfolgen mit weniger Speicherplatz speichern als sie einzeln zu speichern.
B. Der Suchvorgang ist ebenfalls effizient, da die zeitliche Komplexität proportional zur Länge der gesuchten Zeichenfolge ist.

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
*/

Wenn Sie Bedenken/Fragen haben, können Sie sich gerne an mich wenden.

Das obige ist der detaillierte Inhalt vonTrie-Algorithmus || Autovervollständigungsfunktion mit Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!