Ushbu mavzu string key’lar qidiruvi uchun mo’ljallangan ma’lumotlar tuzilmasi – tries (trays) haqida bo’ladi.
Shu vaqtgacha ko’rib o’tgan ma’lumotlar tuzilmalaridan qidiruv uchun eng yaxshisi red-black tree – key’ni qidirish / qo’shish / o’chirish uchun O(log N) vaqtni kafolatlardi. Shuningdek red-black tree’da tartib amallarini (k-key’ni topish, maksimum/minimum key’ni topish) ham bajarish imkoni bor edi. Hash table ma’lumot tuzilmasida esa ma’lum shartlar asosida O(1) vaqtda qidirish / qo’shish / o’chirish imkoni bor, ammo hash table’da tartib amallarini bajarishning iloji yo’q.
Biz string key’larni samarali tartiblashni o’rgangan ekanmiz, ro’yhat ichidan key’ni qidirishda ham biz butun so’zni tekshirmasdan, faqat kerakli harf/belgilarini tekshirish bilan yaxshi samaradorlikka erishishimiz mumkin.
Tries
Trie (retrieval, qidirish) tartiblangan tree ma’lumotlar tuzilmasi bo’lib o’zida string key’larni saqlaydi. Trie yana digital tree yoki prefix tree deb ham ataladi. Uning hususiyatlari:
- Root’da qiymat (value) bo’lmaydi.
- Har bir node’ning R child’i bor, har bir child ehtimoliy belgi uchun ajratilgan. R bu yerda radix soni. Quyidagi trie’da null child’lar ko’rsatilmagan ammo kod yozishda null child’lar bo’ladi.
- Key’ning qiymati key’dagi ohirgi qiymatda saqlanadi.
Trie’da root barcha key’larga yo’lning boshlanishi bo’lib, undan key’larning dastlabki belgilariga (harflariga) boriladi. Masalan biz s dan boshlanadigan key’ni qidirmoqchi bo’lsak, biz root -> s node’ga o’tamiz. Key’ning ikkinchi belgisiga birinchi belgi node’idan o’tiladi. Agar biz «she» key’ni qidirmoqchi bo’lsak, root -> s -> h -> e ko’rinishida topiladi. Key’ning ohirgi belgisiga key’ning qiymati biriktirilgan bo’ladi. Bizning misolda «she» key uchun 0 qiymati e node’da turipti.
Trie’da qidiruv
Agar key’ni qidirish jarayonida, keyingi belgining node’i null bo’lsa, qidiruv to’xtaydi. Masalan, «sheep» so’zini qidirishda root -> s -> h -> e dan keyin qidiruv to’xtaydi, chunki path’dagi ohirgi node – «e» dan keyin ikkinchi «e» ga yo’l yo’q.
Agar key’ni qidirish jarayonida key’ning barcha belgilari trie path’da chiqsayu, lekin ohirgi belgida qiymat bo’lmasa, qidiruv yakunlangan yoki key topilgan deb hisoblanmaydi. Key topilgan bo’lishi uchun, trie’da key’ning ohirgi belgisida qiymat bo’lishi shart. Masalan, «sell» ni qidirmoqchi bo’lsak, qidiruv root -> s -> e -> l -> l da to’xtaydi, ammo ikkinchi «l» da qiymat bo’lmagani uchun key topilmagan bo’ladi.
Qiymatlar path’ning ohirida (leaf node) bo’lishi shartmas. Masalan, «she» key uchun root -> s -> h -> e da qiymat bor, ammo «e» trie’dagi leaf node emas. Undan keyin «shells» key ham saqlanyapti. Bunda «she» ikki key (she va shells) uchun prefix hisoblanadi. «she» key qidirilganda «e» dan keyin qidiruv to’xtaydi, «l» ga o’tib ketmaydi.
Trie’ga key qo’shish
Tries ga key qo’shish huddi tree’dagi singari ro’y beradi. Dastlab key’ning belgilari bo’yicha qidiruv boshlanib, qaysi belgi topilmasa, keyin usha belgi va undan keyingi belgilar qo’shib boriladi. Masalan, «shoe» key’ni qo’shishda root -> s -> h -> o bo’yicha kelinadi. «o» dan keyin «e» node yo’q, demak «o» ga «e» node qo’shiladi va unga «shoe» key’ning qiymati beriladi.
Agar yangi qo’shiladigan key trie’da topilsa, key’ning qiymati yangilanadi.
Tries ni kodda ifodalash
Trie’ni kodda ifodalash uchun API yozamiz. E’tiborga olish kerak bo’lgan jihat – key belgilari kodlarini node’ning indeksi ko’rinishida saqlaymiz, key belgilarining asli o’zi saqlanmaydi. Masalan R sonini ASCII belgilari bo’yicha 128 yoki 256 qilib oladigan bo’lsak, «s» belgisi 115 indeksda saqlanadi. Belgining indeks nomeri Javascriptda «s».charCodeAt() bilan olinadi.
Belgilarning ASCII nomeri bilan bu yerda tanishib chiqishingiz mumkin.
Trie ishlash vaqti – key topilganda L ga teng. L – key’ning uzunligi. Agar key topilmasa, o’rtacha holatda sublinear ( O(logR L) ) vaqtni oladi, chunki odatda key’ning dastlabki belgilaridayoq qidiruv to’xtaydi.
Joy. Har bir child’da R sondagi link bo’lgani uchun katta joy oladi ammo keyingi mavzularda biz joy muammosini ham hal qilishga harakat qilamiz. Ko’pincha string key ishlatiladigan dasturlar, masalan lug’at dasturida faqat harflar ishlatilgani bois, R sonini 26 ga tushirish va charCode() funksiyasini R=26 ga moslab yozish katta hajmdagi joyni tejashga olib keladi.
Xulosa
Trie hash table kabi tez ishlaydi va tartib operatsiyalarini amalga oshira oladi. Bu katta hajmdagi string ma’lumotlar ichidan kerakli key/qiymatni tez vaqt ichida topishda qo’l keladi.