特里算法 ||使用 Javascript 自動完成功能

介紹

Trie，也稱為前綴樹，是一種專門的基於樹的資料結構，用於高效的資訊檢索。

它對於涉及字串內搜尋和前綴匹配的用例特別有用。

1. 如果我告訴你關於 Trie 演算法，你可能會對這個演算法感興趣，也可能不感興趣

2. 但是如果我告訴你，你可以用它來建立一個自動完成演算法。你會更興奮地了解這一點。

該演算法的用例

1。自動完成：

a.搜尋引擎或文字編輯器中經常使用嘗試來實現自動完成功能。
b.當您開始輸入時，應用程式會根據您輸入的前綴建議可能的補全。

2。拼字檢查器：

a.嘗試可用於實現拼字檢查器。如果某個單字不存在於 trie 中，則它可能是拼字錯誤的。
b.特里樹也可以透過尋找相似的單字來建議更正。

3。 IP 路由：

a.嘗試在路由器中用於儲存路由表。
b.路由器使用 trie 來匹配最長前綴，從而確定資料包的下一跳。

4。高效率儲存與搜尋字串：

a.如果您有一個包含大量共享前綴的字串資料集，則 trie 可以使用比單獨儲存它們更少的空間來儲存這些字串。
b. 搜尋操作也很高效，時間複雜度與您要搜尋的字串的長度成正比。

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

如果您有任何疑慮/疑問，請隨時與我聯繫。

以上是特里算法 ||使用 Javascript 自動完成功能的詳細內容。更多資訊請關注PHP中文網其他相關文章！