داده ساختارهای فشرده

در علوم کامپیوتر ،داده ساختار فشرده داده ساختاری است که از فضایی استفاده می‌کند که به نظریه اطلاعات کران پایین نزدیک است؛ ولی (برخلاف دیگر نمایش‌های فشرده) هنوز برای عملیات‌ها کارایی دارد. مفهوم این داده ساختار اولین بار توسط جاکوبسون معرفی شد. با مفهوم رمز گذاری آرایه بیتی، درخت (بدون برچسب) و گراف مسطح. برخلاف الگوریتم فشرده‌سازی بی‌اتلاف داده‌ها، به‌طور کلی داده ساختار فشرده، این ویژگی را دارد که می‌توان بدون ناهم فشرده کردن داده‌ها از آن‌ها استفاده کرد.

فرض کنید که $Z$ تعداد بیت‌های مورد نیاز برای برای ذخیرهٔ برخی داده‌ها است. نمایش آن به شرح زیر است:

داده ساختار ضمنی: $Z+O(1)$ بیت از فضا
داده ساختار فشرده: $Z+O(Z)$ بیت از فضا
داده ساختار متراکم: $O(Z)$ بیت از فضا

برای مثال، یک داده ساختار $2Z$

بیت استفاده می‌کند برای ذخیرهٔ داده ساختار متراکم است،

Z+{\sqrt {Z}}

یا

Z+\lg Z

بیت برای داده ساختار فشرده است و

Z+3

بیت برای داده ساختار ضمنی است.

داده ساختار ضمنی، بر اساس جایشگت‌های مختلف ورودی می‌تواند کاهش بیاید. مثال شناخته شدهٔ آن هرم است.

درخت پیشوندی و آرایهٔ پیشوندی

در درخت پیشوندی می‌توانیم در زمان دلخواه که با طول رشته مناسب است، جستجو کنیم، و در مورد آرایهٔ پیشوندی نیز، در این داده ساختار به نقطه‌ای که شاخص اش به آن اشاره دارد بر می‌گردد. این دو داده ساختار بسیار کاربردی هستند مخصوصاً زمانی که فقط با یک کاربر در ارتباط اند یا فقط در موتور جستجو استفاده می‌شود.

اکنون مشکل ما آن است که آیا می‌توانیم داده ساختار درخت را در فضای قابل ملاحظهٔ کمتری نمایش دهیم؟

به‌طور مثال در درخت جستحوی دودویی:

اندازه: $n-1$ گره داخلی و $n$ برگ
عملکرد: بچه، پدر، سایز زیر درخت، داده‌های برگ‌ها

واضح است که برای هر گره درخت در حدود $6nlog(n)$

بیت حافظه نیاز است .(۱-پدر، ۲-گره راست، ۳-گره چپ، ۴-اندازه، ۵-مدیریت حافظه، ۶-مرجع)

به عنوان مثال درخت پیشوندی کامل در حدود ۵ یا ۶ برابر آرایهٔ پیشوندی فضا از حافظه را نیاز دارد. (به عنوان مثال فقط مراجع برگ‌ها را در نظر بگیرید)

فشردگی

درخت فشرده

این نظریه ابتدا با جاکوبسون شروع شد و سپس دیگران نیز با آن همراه شدند.

عدد کاتالان = اوردر ریشهٔ جنگل یا درخت دودویی = $\textstyle {\binom {2n}{n}}/(n+1)$

پس کران بالای آن در حدود $2n$

بیت است.

برای درخت

در این روش برای نمایش درخت از علامت پرانتر استفاده می‌کنیم. به این صورت عمل می‌کنیم که برای هر گره ")" قرار می‌دهیم سپس زیر درخت، در آخر "(". در عمل در این روش هر گره ۲ بیت فضا از حافظه را به خود اختصاص می‌دهد.

به‌طور مثال برای شکل زیر رشته دودویی مقابل رشتهٔ آن است: " (((())())((())()())) "

برای هرم

اگر به هرم مانند یک درخت دودویی نگاه کنیم، و سپس به هر گره آن (گره معادل عدد یک) و یک عدد اضافه کنیم (معادل عدد صفر) سپس شروع به خواندن سطر به سطر آن کنیم (مطابق شکل زیر):

در نتیجه، یه طور مثال برای هرمی مانند شکل زیر، برداری مانند "۱۱۱۱۰۱۱۱۰۰۱۰۰۰۰۰۰" خواهیم داشت، که طول آن برابر $2n+1$

خواهد بود و یعنی این مقدار بیت از حافظه را اشغال می‌کند.

پیشنهاد کلیدی جاکوبسون

جاکوبسون پیشنهادی برای عملیا بردارهای بیتی داشت. به این صورت که چند تعریف جدید را بیان کرد.

$\mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|$
$\mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}$ برای $q\in \{0,1\}$ .

به عبارت دیگر $\mathbf {rank} _{q}(x)$

تعداد عناصری که برابر

q

هستند و تا قبل از موقعیت

x

قرار دارند را، بازمی‌گرداند. در حال که

\mathbf {select} _{q}(x)

موقعیت

x

امین رخ داد

q

را بازمی‌گرداند.

در نتیجه برای درخت دودویی داریم :

$liftChild(X)=2rank(x)$

$rightChild(X)=2rank(x)+1$

$parent(X)=select(lfloorx/2\rfloor )$

لغت‌نامه فشرده

لغت‌نامه نمایه ساز فشرده، رتبه لغت‌نامه نیز نامیده می‌شود . بر اساس تعدادی از تکنیک‌های نمایش فشرده، از جمله درخت دودویی، چندمجموعه و درخت پسوندی. مشکل اساسی ذخیره‌سازی زیر مجموعهٔ $S$ از مجموعه جهانی ( $U=[0\dots n)=\{0,1,\dots ,n-1\}$

)، معمولاً با ارائه بیتی

B[0\dots n)

که

B[i]=1

اگر

i\in S

نمایش داده می‌شوند. لغت‌نامه‌های نمایه ساز، تابع‌هایی را پشتیبانی می‌کند، مانند نمایش دادن، حذف و اضافه کردن در موارد پویا.

یک نمایش ساده وجود دارد که از $n+o(n)$

بیت از فضای حافظه (

n

برای بیت اصلی آرایه و

o(n)

برای ساختار کمکی) استفاده می‌کند و در زمان ثابت،

\mathbf {rank} _{q}(x)

و

\mathbf {select} _{q}(x)

را پشتیبانی می‌کند. این از یک ایدهٔ مشابه که برای محدوده حداقل نمایش بوده‌است، استفاده می‌کند. این یک عدد ثابت از تابع بازگشتی است قبل از پایان زیر مسئله‌ای که اندازهٔ محدود دارد.

منابع

↑
↑
↑

↑ Jacobson, G. J (1988). "Succinct static data structures".
↑
↑ Jacobson, G. (1989). "Space-efficient static trees and graphs" (PDF). Archived from the original (PDF) on 4 June 2016. Retrieved 28 June 2016.

[jacobson1988succinct-1] ↑

[salam-2] ↑

[jacobson1989space-3] ↑

[jacobson1988succinct-4] Jacobson, G. J (1988). "Succinct static data structures".

[salam-5] ↑

[jacobson1989space-6] Jacobson, G. (1989). "Space-efficient static trees and graphs" (PDF). Archived from the original (PDF) on 4 June 2016. Retrieved 28 June 2016.