داده ساختارهای فشرده
در علوم کامپیوتر ،داده ساختار فشرده داده ساختاری است که از فضایی استفاده می‌کند که به نظریه اطلاعات کران پایین نزدیک است؛ ولی (برخلاف دیگر نمایش‌های فشرده) هنوز برای عملیات‌ها کارایی دارد. مفهوم این داده ساختار اولین بار توسط جاکوبسون معرفی شد. با مفهوم رمز گذاری آرایه بیتی، درخت (بدون برچسب) و گراف مسطح. برخلاف الگوریتم فشرده‌سازی بی‌اتلاف داده‌ها، به‌طور کلی داده ساختار فشرده، این ویژگی را دارد که می‌توان بدون ناهم فشرده کردن داده‌ها از آن‌ها استفاده کرد.
فرض کنید که تعداد بیت‌های مورد نیاز برای برای ذخیرهٔ برخی داده‌ها است. نمایش آن به شرح زیر است:
برای مثال، یک داده ساختار formula_4 بیت استفاده می‌کند برای ذخیرهٔ داده ساختار متراکم است، formula_5 یا formula_6 بیت برای داده ساختار فشرده است و formula_7 بیت برای داده ساختار ضمنی است.
داده ساختار ضمنی، بر اساس جایشگت‌های مختلف ورودی می‌تواند کاهش بیاید. مثال شناخته شدهٔ آن هرم است.
در درخت پیشوندی می‌توانیم در زمان دلخواه که با طول رشته مناسب است، جستجو کنیم، و در مورد آرایهٔ پیشوندی نیز، در این داده ساختار به نقطه‌ای که شاخص اش به آن اشاره دارد بر می‌گردد. این دو داده ساختار بسیار کاربردی هستند مخصوصاً زمانی که فقط با یک کاربر در ارتباط اند یا فقط در موتور جستجو استفاده می‌شود.
اکنون مشکل ما آن است که آیا می‌توانیم داده ساختار درخت را در فضای قابل ملاحظهٔ کمتری نمایش دهیم؟
به‌طور مثال در درخت جستحوی دودویی: واضح است که برای هر گره درخت در حدود formula_10 بیت حافظه نیاز است .(۱-پدر، ۲-گره راست، ۳-گره چپ، ۴-اندازه، ۵-مدیریت حافظه، ۶-مرجع)
به عنوان مثال درخت پیشوندی کامل در حدود ۵ یا ۶ برابر آرایهٔ پیشوندی فضا از حافظه را نیاز دارد. (به عنوان مثال فقط مراجع برگ‌ها را در نظر بگیرید)
این نظریه ابتدا با جاکوبسون شروع شد و سپس دیگران نیز با آن همراه شدند.
عدد کاتالان = اوردر ریشهٔ جنگل یا درخت دودویی = formula_11
پس کران بالای آن در حدود formula_12 بیت است.
در این روش برای نمایش درخت از علامت پرانتر استفاده می‌کنیم. به این صورت عمل می‌کنیم که برای هر گره ")" قرار می‌دهیم سپس زیر درخت، در آخر "(". در عمل در این روش هر گره ۲ بیت فضا از حافظه را به خود اختصاص می‌دهد.
به‌طور مثال برای شکل زیر رشته دودویی مقابل رشتهٔ آن است: " (((())())((())()())) "
اگر به هرم مانند یک درخت دودویی نگاه کنیم، و سپس به هر گره آن (گره معادل عدد یک) و یک عدد اضافه کنیم (معادل عدد صفر) سپس شروع به خواندن سطر به سطر آن کنیم (مطابق شکل زیر):
در نتیجه، یه طور مثال برای هرمی مانند شکل زیر، برداری مانند "۱۱۱۱۰۱۱۱۰۰۱۰۰۰۰۰۰" خواهیم داشت، که طول آن برابر formula_13 خواهد بود و یعنی این مقدار بیت از حافظه را اشغال می‌کند.
جاکوبسون پیشنهادی برای عملیا بردارهای بیتی داشت. به این صورت که چند تعریف جدید را بیان کرد.
به عبارت دیگر formula_17 تعداد عناصری که برابر formula_18 هستند و تا قبل از موقعیت formula_19 قرار دارند را، بازمی‌گرداند. در حال که formula_20 موقعیت formula_19 امین رخ داد formula_18 را بازمی‌گرداند.
در نتیجه برای درخت دودویی داریم :
formula_23
formula_24
formula_25 لغت‌نامه نمایه ساز فشرده، رتبه لغت‌نامه نیز نامیده می‌شود . بر اساس تعدادی از تکنیک‌های نمایش فشرده، از جمله درخت دودویی، چندمجموعه و درخت پسوندی. مشکل اساسی ذخیره‌سازی زیر مجموعهٔ از مجموعه جهانی (formula_26)، معمولاً با ارائه بیتی formula_27 که formula_28 اگر formula_29 نمایش داده می‌شوند. لغت‌نامه‌های نمایه ساز، تابع‌هایی را پشتیبانی می‌کند، مانند نمایش دادن، حذف و اضافه کردن در موارد پویا.
یک نمایش ساده وجود دارد که از formula_30 بیت از فضای حافظه (formula_9 برای بیت اصلی آرایه و formula_32 برای ساختار کمکی) استفاده می‌کند و در زمان ثابت، formula_17 و formula_20 را پشتیبانی می‌کند. این از یک ایدهٔ مشابه که برای بوده‌است، استفاده می‌کند. این یک عدد ثابت از تابع بازگشتی است قبل از پایان زیر مسئله‌ای که اندازهٔ محدود دارد.