نمایش مبدأ برای داده ساختارهای فشرده

در [[علوم کامپیوتر]] ،'''داده ساختار فشرده''' داده ساختاری است که از فضایی استفاده می‌کند که به [[نظریه اطلاعات]] کران پایین نزدیک است؛ ولی (برخلاف دیگر نمایش‌های فشرده) هنوز برای عملیات‌ها کارایی دارد. مفهوم این داده ساختار اولین بار توسط جاکوبسون<ref name="jacobson1988succinct">{{Cite journal|last=Jacobson|first=G. J|year=1988|title=Succinct static data structures}}</ref> معرفی شد. با مفهوم رمز گذاری [[آرایه بیتی]]، [[درخت (ساختار داده)|درخت]] (بدون برچسب) و [[گراف مسطح]]. برخلاف الگوریتم [[فشرده‌سازی بی‌اتلاف داده‌ها]]، به‌طور کلی داده ساختار فشرده، این ویژگی را دارد که می‌توان بدون ناهم فشرده کردن داده‌ها از آن‌ها استفاده کرد.<ref name="jacobson1988succinct" /><ref name="salam">{{Ian Munro|last=Jacobson|first=G.|title=Succinct Data Structures|year=1989|url=https://cs.uwaterloo.ca/~imunro/cs840/SuccinctDS.pdf}}</ref><ref name="jacobson1989space">{{Cite journal|last=Jacobson|first=G.|year=1989|title=Space-efficient static trees and graphs|url=https://www.computer.org/csdl/proceedings/focs/1989/1982/00/063533.pdf|dead-url=yes|journal=|archive-url=https://web.archive.org/web/20160604033839/https://www.computer.org/csdl/proceedings/focs/1989/1982/00/063533.pdf|archive-date=4 ژوئن 2016|access-date=28 ژوئن 2016}}</ref>

فرض کنید که {{mvar|Z}} تعداد بیت‌های مورد نیاز برای برای ذخیرهٔ برخی داده‌ها است. نمایش آن به شرح زیر است:
* داده ساختار ضمنی: <math>Z + O(1)</math> بیت از فضا
* داده ساختار فشرده: <math>Z + O(Z)</math> بیت از فضا
* داده ساختار متراکم: <math>O(Z)</math> بیت از فضا

برای مثال، یک داده ساختار <math>2Z</math> بیت استفاده می‌کند برای ذخیرهٔ داده ساختار متراکم است، <math>Z + \sqrt{Z}</math> یا <math>Z + \lg Z</math> بیت برای داده ساختار فشرده است و <math>Z + 3</math> بیت برای داده ساختار ضمنی است.

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

== درخت پیشوندی و آرایهٔ پیشوندی ==
در [[درخت پیشوندی]] می‌توانیم در زمان دلخواه که با طول رشته مناسب است، جستجو کنیم، و در مورد آرایهٔ پیشوندی نیز، در این داده ساختار به نقطه‌ای که شاخص اش به آن اشاره دارد بر می‌گردد. این دو داده ساختار بسیار کاربردی هستند مخصوصاً زمانی که فقط با '''یک''' کاربر در ارتباط اند یا فقط در '''موتور''' جستجو استفاده می‌شود.<ref name="salam" />

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

به‌طور مثال در درخت جستحوی دودویی:
* اندازه: <math>n-1</math> گره داخلی و <math>n</math> برگ
* عملکرد: بچه، پدر، سایز زیر درخت، داده‌های برگ‌ها
واضح است که برای هر گره درخت در حدود <math>6nlog(n)</math> بیت حافظه نیاز است .(۱-پدر، ۲-گره راست، ۳-گره چپ، ۴-اندازه، ۵-مدیریت حافظه، ۶-مرجع)<ref name="salam" />

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

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

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

پس کران بالای آن در حدود <math>2n</math> بیت است.<ref name="salam" />

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

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

[[پرونده:Tree node.jpg|بندانگشتی|وسط]]

=== برای هرم ===
اگر به هرم مانند یک درخت دودویی نگاه کنیم، و سپس به هر گره آن (گره معادل عدد یک) و یک عدد اضافه کنیم (معادل عدد صفر) سپس شروع به خواندن سطر به سطر آن کنیم<ref name="salam" /> (مطابق شکل زیر):

[[پرونده:Succinct.jpg|بندانگشتی|وسط]]

در نتیجه، یه طور مثال برای هرمی مانند شکل زیر، برداری مانند "۱۱۱۱۰۱۱۱۰۰۱۰۰۰۰۰۰" خواهیم داشت، که طول آن برابر <math>2n+1</math> خواهد بود و یعنی این مقدار بیت از حافظه را اشغال می‌کند.

[[پرونده:Heap succient.png|بندانگشتی|وسط]]

== پیشنهاد کلیدی جاکوبسون ==
جاکوبسون پیشنهادی برای عملیا بردارهای بیتی داشت. به این صورت که چند تعریف جدید را بیان کرد.<ref name="salam" />
{{چپ‌چین}}
* <math>\mathbf{rank}_q(x) = |\{ k \in [0 \dots x]: B[k] = q \}|</math>
* <math>\mathbf{select}_q(x)= \min \{k \in [0 \dots n) : \mathbf{rank}_q(k) = x\}</math> برای <math>q \in \{0, 1\}</math>.
{{پایان چپ‌چین}}

به عبارت دیگر <math>\mathbf{rank}_q(x)</math> تعداد عناصری که برابر <math>q</math> هستند و تا قبل از موقعیت <math>x</math> قرار دارند را، بازمی‌گرداند. در حال که <math>\mathbf{select}_q(x)</math> موقعیت <math>x</math> امین رخ داد <math>q</math> را بازمی‌گرداند.<ref name="salam" />

در نتیجه برای درخت دودویی داریم :
{{چپ‌چین}}
<math>liftChild(X) = 2 rank(x)</math>

<math>rightChild(X) = 2 rank(x) + 1</math>

<math>parent(X) = select(lfloor x / 2\rfloor)</math>
{{پایان چپ‌چین}}

== لغت‌نامه فشرده ==
لغت‌نامه نمایه ساز فشرده، رتبه لغت‌نامه نیز نامیده می‌شود . بر اساس تعدادی از تکنیک‌های نمایش فشرده، از جمله [[درخت دودویی]]، [[چندمجموعه]] و [[درخت پسوندی]].
مشکل اساسی ذخیره‌سازی زیر مجموعهٔ {{mvar|S}} از [[مجموعه جهانی]] (<math>U =[0 \dots n) = \{0, 1, \dots, n - 1\}</math>)، معمولاً با ارائه بیتی <math>B[0 \dots n)</math> که <math>B[i] = 1</math> اگر <math>i \in S</math> نمایش داده می‌شوند. لغت‌نامه‌های نمایه ساز، تابع‌هایی را پشتیبانی می‌کند، مانند نمایش دادن، حذف و اضافه کردن در موارد پویا.

یک نمایش ساده وجود دارد<ref name="jacobson1989space" /> که از <math>n + o(n)</math> بیت از فضای حافظه (<math>n</math> برای بیت اصلی آرایه و <math>o(n)</math> برای ساختار کمکی) استفاده می‌کند و در زمان ثابت، <math>\mathbf{rank}_q(x)</math> و <math>\mathbf{select}_q(x)</math> را پشتیبانی می‌کند. این از یک ایدهٔ مشابه که برای [[:en:Range minimum query|محدوده حداقل نمایش]] بوده‌است، استفاده می‌کند. این یک عدد ثابت از [[بازگشت (علوم رایانه)|تابع بازگشتی]] است قبل از پایان زیر مسئله‌ای که اندازهٔ محدود دارد.

== منابع ==
{{پانویس}}
[[رده:داده ساختارهای فشرده]]
[[رده:ساختمان داده]]