trie Unduh - trie unduh kode sumber

trie

Kode sumber lainnya

v0.0.1

Unduh

mencoba

Implementasi struktur data Trie di Go. Ini menyediakan lebih banyak fitur daripada pencarian awalan Trie biasa, dan dimaksudkan untuk digunakan untuk pelengkapan otomatis.

Demo

Demo WebAssembly dapat dicoba di shivamMg.github.io/trie.

Fitur

Kuncinya adalah []string bukan string , sehingga mendukung lebih banyak kasus penggunaan - misalnya []string{the quick brown fox} dapat menjadi kunci di mana setiap kata akan menjadi simpul di Trie
Dukungan untuk tombol Put dan tombol Hapus
Dukungan untuk pencarian Awalan - misalnya mencari negara mungkin akan menghasilkan nation , national , nasionalism , nationalist , dll.
Dukungan untuk pencarian Edit jarak (alias jarak Levenshtein) - misalnya mencari gandum mungkin menghasilkan kata-kata yang mirip seperti gandum , curang , panas , apa , dll.
Urutan hasil pencarian bersifat deterministik. Ini mengikuti perintah penyisipan.

Contoh

 tri := trie.New()// Masukkan kunci ([]string) dan nilai (apa saja)tri.Put([]string{"the"}, 1)tri.Put([]string{"the", " cepat", "coklat", "rubah"}, 2)tri.Put([]string{"the", "cepat", "olahraga", "mobil"}, 3)tri.Put([]string{" itu", "hijau", "pohon"}, 4)tri.Put([]string{"an", "apel", "pohon"}, 5)tri.Put([]string{"an", "payung"}, 6)tri.Root(). Print()// Output (percobaan penuh dengan terminal diakhiri dengan ($)):// ^// ├─ the ($)// │ ├─ quick// │ │ ├─ coklat// │ │ │ └─ rubah ($)// │ │ └─ olahraga// │ │ └─ mobil ($)// │ └─ hijau// │ └─ pohon ($)// └─ an// ├─ apel// │ └─ pohon ($)// └─ payung ($)hasil := tri.Search([]string{"the", "quick"})untuk _, res := rentang hasil.Hasil { fmt.Println(res.Key, res.Value)
}// Output (penelusuran berbasis awalan):// [rubah coklat cepat] 2// [mobil sport cepat] 3key := []string{"the", "tree"}results = tri.Search(key , trie.WithMaxEditDistance(2), // Pengeditan dapat disisipkan, dihapus, digantitrie.WithEditOps())untuk _, res := rentang hasil.Hasil { fmt.Println(res.Key, res.EditDistance) // EditDistance adalah jumlah pengeditan yang diperlukan untuk mengkonversi ke [pohon]}// Output (hasil tidak lebih dari 2 pengeditan dari [pohon]):// [yang] 1// [pohon hijau ] 1// [pohon apel] 2// [payung] 2hasil := hasil.Hasil[2]fmt.Printf("Untuk mengubah %v ke %v:n", hasil.Key, key)printEditOps(result.EditOps)// Output (operasi edit diperlukan untuk menyembunyikan hasil ke [pohon]):// Untuk mengonversi [pohon apel] menjadi [pohon]:// - hapus "an"// - ganti "apple" dengan "the"// - jangan edit "tree"results = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2))for _, res := rentang hasil.Hasil { fmt.Println(res.Key, res.Value, res.EditDistance)
}// Keluaran (2 hasil teratas yang paling sedikit diedit):// [yang] 1 1// [pohon hijau] 4 1