Algoritma Cuba || Ciri Auto Lengkap menggunakan Javascript

pengenalan

A Trie, juga dikenali sebagai pepohon awalan, ialah struktur data berasaskan pepohon khusus yang digunakan untuk mendapatkan maklumat yang cekap.

Ia amat berguna untuk kes penggunaan yang melibatkan pencarian dan padanan awalan dalam rentetan.

1. Jika saya memberitahu anda tentang Algoritma Percubaan, anda mungkin berminat atau tidak dengan algoritma ini

2. Tetapi jika saya memberitahu anda, anda boleh mencipta algoritma autolengkap menggunakan ini. anda akan lebih teruja untuk mempelajari ini.

Kes Penggunaan Algoritma ini

1. Autolengkap:

a. Percubaan sering digunakan dalam enjin carian atau penyunting teks untuk melaksanakan ciri autolengkap.
b. Semasa anda mula menaip, aplikasi mencadangkan kemungkinan penyiapan berdasarkan awalan yang anda masukkan.

2. Penyemak Ejaan:

a. Percubaan boleh digunakan untuk melaksanakan penyemak ejaan. Jika perkataan tidak terdapat dalam trie, ia mungkin tersilap ejaan.
b. Percubaan juga boleh mencadangkan pembetulan dengan mencari perkataan yang serupa.

3. Penghalaan IP:

a. Percubaan digunakan dalam penghala untuk menyimpan jadual penghalaan.
b. Penghala menggunakan percubaan untuk memadankan awalan terpanjang, yang menentukan lompatan seterusnya untuk satu paket.

4. Menyimpan dan Mencari Rentetan dengan Cekap:

a. Jika anda mempunyai set data rentetan yang terdapat banyak awalan dikongsi, percubaan boleh menyimpan rentetan ini menggunakan ruang yang lebih sedikit daripada menyimpannya secara berasingan.
b. Operasi carian juga cekap, dengan kerumitan masa berkadar dengan panjang rentetan yang anda cari.

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

Sila hubungi saya jika anda mempunyai sebarang kebimbangan/pertanyaan.

Atas ialah kandungan terperinci Algoritma Cuba || Ciri Auto Lengkap menggunakan Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!