Pohon awalan dengan indeks bitmap

Belum lama ini saya perlu mengimplementasikan fungsionalitas yang sudah diterapkan oleh orang lain dan lebih dari sekali, tetapi tidak cocok untuk beberapa karakteristik. Dalam hal ini, beberapa jenis struktur data diperlukan dengan kemampuan untuk mencari dengan kunci string atau beberapa karakter awal kunci. Kuncinya adalah serangkaian huruf Latin dalam hal apa pun, spasi, dan angka.

Implementasi lain tidak sesuai, pertama-tama, pada memori yang dikonsumsi. Dan dalam hal apa pun, implementasi lain dari pohon awalan tidak akan berlebihan.

Idenya mungkin terinspirasi oleh artikel ini , karena diputuskan untuk menggunakan indeks bitmap untuk mengindeks tautan ke node berikutnya dalam node.

Jelas, jumlah tautan dalam satu simpul tidak boleh lebih dari 63 (10 digit, 26 huruf dalam setiap kasus, ditambah spasi). Oleh karena itu, untuk indeks bitmap, angka 64-bit digunakan pada setiap node. Bit yang disetel di posisi apa pun berarti keberadaan simbol dan simpul yang sesuai (subtree).

Distribusi dalam indeks bitmap adalah sebagai berikut: angka dari 0 hingga 9 menempati dari 0 hingga 9 bit, huruf az dari 10 hingga 35 bit, huruf AZ dari 36 hingga 62 bit, dan sebuah ruang menempati 63 bit. Untuk mendapatkan nomor bit, kode karakter ASCII hanya digunakan, dikurangi dengan angka tertentu. Untuk setiap rentang karakter, angkanya berbeda: untuk angka 48 (kisaran digit dalam kode ASCII dimulai dengan 48), untuk huruf az 87 (rentang huruf az dimulai dengan minus 10 bit yang sudah ditempati oleh 10 digit) dan seterusnya.

Tabel yang sesuai ditunjukkan di bawah ini.


Node diwakili oleh kode di bawah ini:

type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} } 

Dengan demikian, setiap node menyimpan indeks bitmap dari karakter berikut, sebuah irisan dengan tautan ke subtrees dan data itu sendiri. Saya akan memberi tahu secara singkat tentang mekanisme pencarian, penyisipan dan penghapusan.

Saat memasukkan input, kunci secara simbolis melewati pohon, mulai dari simpul akar. Untuk setiap karakter dari kode ASCII-nya, jumlah bit dihitung, dan berdasarkan indeksnya dihitung dalam irisan tautan (subTries) ke subtrees. Nilai indeks adalah jumlah bit sebelum bit yang diinginkan. Misalnya, kami memiliki indeks seperti itu: 00 ... 101. Ini berarti bahwa dalam indeks bitmap ada angka 0 dan 2. Kemudian indeks untuk angka 0 akan menjadi nol, dan untuk angka 2 itu akan menjadi 1, yaitu, SubTries akan menyimpan 2 tautan ke subtree: subTries [0] dan subTries [1] .

Kode untuk mendapatkan nomor bit untuk karakter:

 func calcBitNum(char rune) (uint64, bool) { // Characters az use bit positions 10-35 if char > 96 && char < 123 { return uint64(char - 87), true } // Characters AZ use bit positions 36-61 if char > 64 && char < 91 { return uint64(char - 29), true } // digits 0-9 use bit positions 0-9 if char > 47 && char < 58 { return uint64(char - 48), true } // space uses 62 bit position if char == 32 { return 62, true } return 0, false } 

Kode untuk mendapatkan indeks simpul untuk karakter:

 func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) } 

Kode untuk mendapatkan simpul untuk karakter yang diberikan:

 func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum) // There is no subTrie under given character since the corresponding bit is zero if trie.characters&(1<<bitNum) == 0 { return bitNum, subTrieId, nil } return bitNum, subTrieId, trie.subTries[subTrieId] } 

Masukkan

Sebuah pohon dilintasi untuk memasukkan elemen. Jika ada karakter (dan oleh karena itu semua yang berikutnya) hilang, itu dimasukkan ke dalam indeks bitmap. Subtree dibuat, tautan yang dimasukkan ke tempat yang tepat dari subtri slice (tempat yang tepat ditentukan oleh jumlah bit ke yang diinginkan). Ketika mereka mencapai karakter terakhir dari kunci, data dimasukkan ke dalam subtree terakhir.

Cari

Untuk mencari, kunci secara simbolis "berjalan" melalui pohon. Begitu selesai, hasilnya dikembalikan. Jika tidak ada data untuk kunci tersebut, tetapi ada sub-cabang lebih lanjut, maka hasilnya dipilih dari semua sub-sub berikutnya yang memiliki data. Batas jumlah data yang dikembalikan dapat diatur. Dengan demikian, adalah mungkin untuk mencari satu simpul oleh kebetulan seluruh kunci, atau satu set simpul oleh kebetulan beberapa karakter awal.

Hapus

Prosedur penghapusan keluar lebih rumit (seperti yang diharapkan) daripada yang lain. Untuk menghapus kunci, pohon dilintasi, di mana node yang tidak memiliki data dicatat dalam irisan terpisah. Jika sebuah simpul dengan data ditemukan, maka irisan diatur ulang ke nol, dan bagian melalui pohon berlanjut lebih jauh. Yaitu, irisan node untuk dihapus harus berisi urutan node yang tidak memiliki data. Jika pada akhirnya slice tidak kosong, maka ia berjalan dalam urutan terbalik dan bit yang sesuai dihapus dari indeks bitmap dan node dihapus.

Ringkasan

Hasilnya adalah pohon awalan yang lebih unggul dari analog lain dalam kecepatan dan konsumsi memori (rata-rata memori 30% lebih sedikit dan lebih cepat). Juga, saya tidak terlalu malas untuk membuat operasi multithreaded dengan pohon mungkin, yang secara signifikan meningkatkan produktivitas, terutama dalam operasi pencarian. Tentu saja, solusinya cukup khusus (pembatasan dalam bentuk karakter Latin, angka dan spasi sebagai komponen utama).

Berdasarkan tujuan pohon awalan, solusi ini dapat digunakan untuk membuat kamus, indeks pencarian.

Saya tidak mengutip kode sisipkan, cari dan hapus, agar tidak mengacaukan artikel, di samping itu, kode sumber tersedia di github .