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

در علوم کامپیوتر ، داده ساختار فشرده داده ساختاری است که از فضایی استفاده می کند که به نظریه اطلاعات کران پایین نزدیک است؛ ولی ( برخلاف دیگر نمایش های فشرده ) هنوز برای عملیات ها کارایی دارد. مفهوم این داده ساختار اولین بار توسط جاکوبسون[ ۱] معرفی شد. با مفهوم رمز گذاری آرایه بیتی، درخت ( بدون برچسب ) و گراف مسطح. برخلاف الگوریتم فشرده سازی بی اتلاف داده ها، به طور کلی داده ساختار فشرده، این ویژگی را دارد که می توان بدون ناهم فشرده کردن داده ها از آن ها استفاده کرد.
فرض کنید که Z تعداد بیت های مورد نیاز برای برای ذخیرهٔ برخی داده ها است. نمایش آن به شرح زیر است:
• داده ساختار ضمنی: Z + O ( 1 ) {\displaystyle Z+O ( 1 ) } بیت از فضا
• داده ساختار فشرده: Z + O ( Z ) {\displaystyle Z+O ( Z ) } بیت از فضا
• داده ساختار متراکم: O ( Z ) {\displaystyle O ( Z ) } بیت از فضا
برای مثال، یک داده ساختار 2 Z بیت استفاده می کند برای ذخیرهٔ داده ساختار متراکم است، Z + Z یا Z + lg ⁡ Z بیت برای داده ساختار فشرده است و Z + 3 بیت برای داده ساختار ضمنی است.
داده ساختار ضمنی، بر اساس جایشگت های مختلف ورودی می تواند کاهش بیاید. مثال شناخته شدهٔ آن هرم است.
در درخت پیشوندی می توانیم در زمان دلخواه که با طول رشته مناسب است، جستجو کنیم، و در مورد آرایهٔ پیشوندی نیز، در این داده ساختار به نقطه ای که شاخص اش به آن اشاره دارد بر می گردد. این دو داده ساختار بسیار کاربردی هستند مخصوصاً زمانی که فقط با یک کاربر در ارتباط اند یا فقط در موتور جستجو استفاده می شود. [ ۲]
اکنون مشکل ما آن است که آیا می توانیم داده ساختار درخت را در فضای قابل ملاحظهٔ کمتری نمایش دهیم؟
به طور مثال در درخت جستحوی دودویی:
• اندازه: n − 1 {\displaystyle n - 1} گره داخلی و n {\displaystyle n} برگ
• عملکرد: بچه، پدر، سایز زیر درخت، داده های برگ ها
واضح است که برای هر گره درخت در حدود 6 n l o g ( n ) بیت حافظه نیاز است . ( ۱ - پدر، ۲ - گره راست، ۳ - گره چپ، ۴ - اندازه، ۵ - مدیریت حافظه، ۶ - مرجع ) [ ۲]
به عنوان مثال درخت پیشوندی کامل در حدود ۵ یا ۶ برابر آرایهٔ پیشوندی فضا از حافظه را نیاز دارد. ( به عنوان مثال فقط مراجع برگ ها را در نظر بگیرید )
این نظریه ابتدا با جاکوبسون شروع شد و سپس دیگران نیز با آن همراه شدند.