WikiDer > Ma'lumotlarning aniq tuzilishi

Yilda Kompyuter fanlari, a qisqacha ma'lumotlar tuzilishi a ma'lumotlar tuzilishi bu "ga" yaqin bo'lgan bo'shliqni ishlatadi axborot-nazariy pastki chegarasi, ammo (boshqa siqilgan vakolatxonalardan farqli o'laroq) hali ham samarali so'rovlarni bajarishga imkon beradi. Kontseptsiya dastlab Jeykobson tomonidan kiritilgan^[1] kodlash bit vektorlari, (yorliqsiz) daraxtlarva planar grafikalar. Umumiydan farqli o'laroq ma'lumotlarni yo'qotmasdan siqish algoritmlar, qisqacha ma'lumotlar tuzilmalari, avval ularni dekompressiyadan chiqarmasdan, ularni joyida ishlatish qobiliyatini saqlab qoladi. Tegishli tushuncha a siqilgan ma'lumotlar tuzilishi, unda ma'lumotlar strukturasining kattaligi taqdim etilayotgan ma'lum ma'lumotlarga bog'liq.

Aytaylik ${displaystyle Z}$ bu ba'zi ma'lumotlarni saqlash uchun zarur bo'lgan bitlarning axborot-nazariy maqbul soni. Ushbu ma'lumotlarning vakili:

• yashirin agar kerak bo'lsa ${displaystyle Z + O (1)}$ bo'sh joy,
• qisqacha agar kerak bo'lsa ${displaystyle Z + o (Z)}$ bo'sh joy bitlari va
• ixcham agar kerak bo'lsa ${displaystyle O (Z)}$ bo'sh joy.

Masalan, foydalanadigan ma'lumotlar tuzilishi ${displaystyle 2Z}$ saqlash joylari ixcham, ${displaystyle Z + {sqrt {Z}}}$ bitlar qisqacha, ${displaystyle Z + lg Z}$ bitlar ham qisqacha va ${displaystyle Z + 3}$ bitlar aniq emas.

Yashirin tuzilmalar, odatda, kirish ma'lumotlarining ba'zi bir almashtirishlari yordamida ma'lumotni saqlashga qisqartiriladi; Buning eng taniqli misoli bu uyum.

Qisqacha lug'atlar

Qisqacha indekslanadigan lug'atlar, shuningdek, deyiladi daraja / tanlang lug'atlar, shu jumladan bir qator qisqacha tasvirlash texnikasining asosini tashkil etadi ikkilik daraxtlar, ${displaystyle k}$-ariy daraxtlari va multisets,^[2] shu qatorda; shu bilan birga qo'shimchali daraxtlar va massivlar.^[3] Asosiy muammo pastki to'plamni saqlashdir ${displaystyle S}$ koinotning ${displaystyle U = [0 nuqta n) = {0,1, nuqta, n-1}}$, odatda bit qatori sifatida ifodalanadi ${displaystyle B [0dots n)}$ qayerda ${displaystyle B [i] = 1}$ iff ${displaystyle iin S.}$ Indekslashtiriladigan lug'at lug'atlarda odatiy usullarni (so'rovlar va dinamik holatda qo'shimchalar / o'chirishlar) hamda quyidagi operatsiyalarni qo'llab-quvvatlaydi:

• ${displaystyle mathbf {rank} _ {q} (x) = | {kin [0 nuqta x]: B [k] = q} |}$
• ${displaystyle mathbf {select} _ {q} (x) = min {kin [0dots n): mathbf {rank} _ {q} (k) = x}}$

uchun ${displaystyle qin {0,1}}$.

Boshqa so'zlar bilan aytganda, ${displaystyle mathbf {rank} _ {q} (x)}$ ga teng elementlar sonini qaytaradi ${displaystyle q}$ holatiga qadar ${displaystyle x}$ esa ${displaystyle mathbf {select} _ {q} (x)}$ holatini qaytaradi ${displaystyle x}$- paydo bo'lishi ${displaystyle q}$.

Oddiy vakillik mavjud^[4] qaysi foydalanadi ${displaystyle n + o (n)}$ xotira maydoni (asl bit qatori va an ${displaystyle o (n)}$ yordamchi tuzilma) va tayanchlar daraja va tanlang doimiy vaqt ichida. Buning uchun shunga o'xshash fikr ishlatiladi minimal minimal so'rovlar; cheklangan hajmdagi kichik muammoga to'xtashdan oldin doimiy rekursiyalar soni mavjud. Bit qatori ${displaystyle B}$ bo'linadi katta bloklar hajmi ${displaystyle l = lg ^ {2} n}$ bit va kichik bloklar hajmi ${displaystyle s = lg n / 2}$ bitlar. Har bir katta blok uchun uning birinchi bitining darajasi alohida jadvalda saqlanadi ${displaystyle R_ {l} [0dots n / l)}$; har bir bunday yozuv oladi ${displaystyle lg n}$ jami bit ${displaystyle (n / l) lg n = n / lg n}$ saqlash joylari. Katta blok ichida boshqa katalog mavjud ${displaystyle R_ {s} [0dots l / s)}$ har birining martabasini saqlaydi ${displaystyle l / s = 2lg n}$ tarkibida kichik bloklar mavjud. Bu erda farq shundaki, u faqat kerak ${displaystyle lg l = lg lg ^ {2} n = 2lg lg n}$ har bir kirish uchun bit, chunki faqat katta bitdagi birinchi bit darajasidan farqlarni saqlash kerak. Shunday qilib, ushbu jadval jami oladi ${displaystyle (n / s) lg l = 4nlg lg n / lg n}$ bitlar. Qidiruv jadvali ${displaystyle R_ {p}}$ keyin har qanday darajadagi so'rovlarga javobni biroz uzunlikdagi satrda saqlaydigan foydalanilishi mumkin ${displaystyle s}$ uchun ${displaystyle iin [0, s)}$; bu talab qiladi ${displaystyle 2 ^ {s} slg s = O ({sqrt {n}} lg nlg lg n)}$ saqlash joyining bitlari. Shunday qilib, chunki bu yordamchi jadvallarning har biri oladi ${displaystyle o (n)}$ bo'sh joy, ushbu ma'lumotlar tuzilishi darajadagi so'rovlarni qo'llab-quvvatlaydi ${displaystyle O (1)}$ vaqt va ${displaystyle n + o (n)}$ bo'sh joy.

So'roviga javob berish ${displaystyle mathbf {rank} _ {1} (x)}$ doimiy vaqt ichida doimiy vaqt algoritmi quyidagilarni hisoblab chiqadi:

• ${displaystyle mathbf {rank} _ {1} (x) = R_ {l} [lfloor x / lfloor] + R_ {s} [lfloor x / sfloor] + R_ {p} [xlfloor x / sfloor, x {ext { mod}} lar]}$

Amalda, qidiruv jadvali ${displaystyle R_ {p}}$ o'rniga bitli operatsiyalar va kichik bloklarda o'rnatilgan bitlar sonini topish uchun ishlatilishi mumkin bo'lgan kichik jadvallar qo'yilishi mumkin. Bu tez-tez foydalidir, chunki qisqacha ma'lumotlar tuzilmalari katta hajmdagi ma'lumotlar to'plamlarida foydalanishni topadi, bu holda keshni o'tkazib yuborish juda tez-tez uchraydi va qidiruv jadvalining yaqin CPU keshlaridan chiqarib yuborilishi ehtimoli yuqori bo'ladi.^[5] Tanlangan so'rovlar uchun ishlatiladigan bir xil yordamchi tuzilishda ikkilik qidiruvni amalga oshirish orqali osongina qo'llab-quvvatlanishi mumkin daraja; ammo, bu oladi ${displaystyle O (lg n)}$ eng yomon holatda vaqt. Keyinchalik murakkab tuzilish ${displaystyle 3n / lg lg n + O ({sqrt {n}} lg nlg lg n) = o (n)}$ qo'llab-quvvatlash uchun qo'shimcha saqlash bitlaridan foydalanish mumkin tanlang doimiy vaqt ichida.^[6] Amalda, ushbu echimlarning aksariyati ${displaystyle O (cdot)}$ asimptotik ustunlik paydo bo'lguncha ustunlik qiladigan yozuv; keng so'z operatsiyalari va so'zlarga mos bloklardan foydalangan holda amalga oshirish ko'pincha amalda yaxshiroq ishlaydi.^[7]

Entropiya bilan siqilgan lug'atlar

The ${displaystyle n + o (n)}$ borligini ta'kidlab, kosmik yondashuvni yaxshilash mumkin ${displaystyle extstyle {inom {n} {m}}}$ aniq ${displaystyle m}$-subets ${displaystyle [n)}$ (yoki uzunlikning ikkilik qatorlari ${displaystyle n}$ aniq bilan ${displaystyle m}$ Va shuning uchun ${displaystyle extstyle {mathcal {B}} (m, n) = lceil lg {inom {n} {m}} shift}$ bu saqlash uchun zarur bo'lgan bitlar sonining pastki teoretik chegarasi ${displaystyle B}$. Ushbu chegaraga erishgan, ya'ni foydalanib qisqacha (statik) lug'at mavjud ${displaystyle {mathcal {B}} (m, n) + o ({mathcal {B}} (m, n))}$ bo'sh joy.^[8] Ushbu tuzilmani qo'llab-quvvatlash uchun kengaytirish mumkin daraja va tanlang so'rovlar va qabul qiladi ${displaystyle {mathcal {B}} (m, n) + O (m + nlg lg n / lg n)}$ bo'sh joy.^[2] To'g'ri daraja Ushbu tuzilmadagi so'rovlar to'plamdagi elementlar bilan cheklangan bo'lib, minimal minimal xeshlash funktsiyalarining ishlashiga o'xshashdir. Ushbu chegarani lug'atning saqlash maydonini qisqartirish orqali bo'shliq / vaqt almashinuviga kamaytirish mumkin ${displaystyle {mathcal {B}} (m, n) + O (nt ^ {t} / lg ^ {t} n + n ^ {3/4})}$ so'rovlarni olish bilan ${displaystyle O (t)}$ vaqt.^[9]

Misollar

A null tugagan satr (C simli) oladi Z + 1 bo'shliq va shuning uchun yopiq. Ixtiyoriy uzunlikdagi mag'lubiyat (Paskal qatori) oladi Z + jurnal (Z) bo'shliq va shu bilan qisqacha. Agar maksimal uzunlik bo'lsa - bu amalda shunday, chunki 2 dan³² = 4 GiB ma'lumotlar juda uzun satr va 2⁶⁴ = 16 EiB ma'lumotlari amaldagi har qanday satrdan kattaroq - keyin uzunlikdagi satr ham yopiq bo'ladi Z + k bo'sh joy, qaerda k bu maksimal uzunlikni ifodalaydigan ma'lumotlar soni (masalan, 64 bit).

O'zgaruvchan uzunlikdagi elementlarning ketma-ketligini (masalan, satrlarni) kodlash zarur bo'lganda, turli xil imkoniyatlar mavjud. To'g'ridan-to'g'ri yondashuv uzunlik va buyumni har bir yozuvda saqlashdir - keyinchalik ularni birin-ketin joylashtirish mumkin. Bu keyingi samaradorlikni beradi, ammo topolmaydi kth-modda. Shu bilan bir qatorda, narsalarni ajratuvchi bilan tartibda joylashtirish (masalan, null tugagan satr). Bu uzunlik o'rniga ajratuvchidan foydalanadi va sezilarli darajada sekinroq, chunki butun ketma-ketlikni ajratuvchilar uchun skanerlash kerak. Ularning ikkalasi ham kosmosdan samarali. Muqobil yondashuv - bu banddan tashqari ajratish: buyumlar bir-birining ortidan joylashtirilishi mumkin, ajratuvchilarsiz. Keyinchalik, element chegaralari uzunlik ketma-ketligi sifatida saqlanishi yoki ushbu ketma-ketlikning o'rnini bosishi mumkin. Shu bilan bir qatorda, element boshlanadigan pozitsiyalarda 1-lardan va hamma joyda 0-lardan tashkil topgan alohida ikkilik satr u bilan birga kodlangan. Ushbu qatorni hisobga olgan holda ${displaystyle select}$ funktsiya har bir elementning indeksini hisobga olgan holda qaerdan boshlanishini tezda aniqlay oladi.^[10] Bu ixcham lekin emas qisqa, chunki bu 2 oladiZ bo'shliq, bu O (Z).

Yana bir misol - $ a $ ning namoyishi ikkilik daraxt: o'zboshimchalik bilan ikkilik daraxt yoqilgan ${displaystyle n}$ tugunlarni ifodalash mumkin ${displaystyle 2n + o (n)}$ bitlar har qanday tugunda turli xil operatsiyalarni qo'llab-quvvatlaydi, bu o'z ota-onasini, chap va o'ng bolasini topishni va har bir doimiy vaqtda kichik daraxt hajmini qaytarishni o'z ichiga oladi. Turli xil ikkilik daraxtlarning soni ${displaystyle n}$ tugunlar ${displaystyle {binom {2n} {n}}}$${displaystyle / (n + 1)}$. Katta uchun ${displaystyle n}$, bu haqida ${displaystyle 4 ^ {n}}$; Shunday qilib, bizga kamida kerak ${displaystyle log _ {2} (4 ^ {n}) = 2n}$ uni kodlash uchun bitlar. Shunday qilib, lo'nda binar daraxt faqat egallaydi ${displaystyle 2}$ tugun boshiga bit.

Shuningdek qarang

• Minimal mukammal xash funktsiyasi

Adabiyotlar