در ، داده ساختاری است که از فضایی استفاده می‌کند که به کران پایین نزدیک است؛ ولی (برخلاف دیگر نمایش‌های فشرده) هنوز برای عملیات‌ها کارایی دارد. مفهوم این داده ساختار اولین بار توسط جاکوبسون معرفی شد. با مفهوم رمز گذاری ، (بدون برچسب) و . برخلاف الگوریتم ، به‌طور کلی داده ساختار فشرده، این ویژگی را دارد که می‌توان بدون ناهم فشرده کردن داده‌ها از آن‌ها استفاده کرد.
 فرض کنید که تعداد بیت‌های مورد نیاز برای برای ذخیرهٔ برخی داده‌ها است. نمایش آن به شرح زیر است:
 
 
 برای مثال، یک داده ساختار بیت استفاده می‌کند برای ذخیرهٔ داده ساختار متراکم است، یا بیت برای داده ساختار فشرده است و بیت برای داده ساختار ضمنی است.
 داده ساختار ضمنی، بر اساس جایشگت‌های مختلف ورودی می‌تواند کاهش بیاید. مثال شناخته شدهٔ آن است.
 در درخت پیشوندی می‌توانیم در زمان دلخواه که با طول رشته مناسب است، جستجو کنیم، و در مورد آرایهٔ پیشوندی نیز، در این داده ساختار به نقطه‌ای که شاخص اش به آن اشاره دارد بر می‌گردد. این دو داده ساختار بسیار کاربردی هستند مخصوصاً زمانی که فقط با کاربر در ارتباط اند یا فقط در جستجو استفاده می‌شود. 
 اکنون مشکل ما آن است که آیا می‌توانیم داده ساختار درخت را در فضای قابل ملاحظهٔ کمتری نمایش دهیم؟
 به‌طور مثال در درخت جستحوی دودویی:
 
 واضح است که برای هر گره درخت در حدود بیت حافظه نیاز است .(۱-پدر، ۲-گره راست، ۳-گره چپ، ۴-اندازه، ۵-مدیریت حافظه، ۶-مرجع) 
 به عنوان مثال درخت پیشوندی کامل در حدود ۵ یا ۶ برابر آرایهٔ پیشوندی فضا از حافظه را نیاز دارد. (به عنوان مثال فقط مراجع برگ‌ها را در نظر بگیرید)
 این نظریه ابتدا با جاکوبسون شروع شد و سپس دیگران نیز با آن همراه شدند.
 عدد کاتالان = اوردر ریشهٔ جنگل یا درخت دودویی = 
 پس کران بالای آن در حدود بیت است. 
 در این روش برای نمایش درخت از علامت پرانتر استفاده می‌کنیم. به این صورت عمل می‌کنیم که برای هر گره ")" قرار می‌دهیم سپس زیر درخت، در آخر "(". در عمل در این روش هر گره ۲ بیت فضا از حافظه را به خود اختصاص می‌دهد. 
 به‌طور مثال برای شکل زیر رشته دودویی مقابل رشتهٔ آن است: " (((())())((())()())) "
 اگر به هرم مانند یک درخت دودویی نگاه کنیم، و سپس به هر گره آن (گره معادل عدد یک) و یک عدد اضافه کنیم (معادل عدد صفر) سپس شروع به خواندن سطر به سطر آن کنیم (مطابق شکل زیر):
 در نتیجه، یه طور مثال برای هرمی مانند شکل زیر، برداری مانند "۱۱۱۱۰۱۱۱۰۰۱۰۰۰۰۰۰" خواهیم داشت، که طول آن برابر خواهد بود و یعنی این مقدار بیت از حافظه را اشغال می‌کند.
 جاکوبسون پیشنهادی برای عملیا بردارهای بیتی داشت. به این صورت که چند تعریف جدید را بیان کرد. 
 
 
 به عبارت دیگر تعداد عناصری که برابر هستند و تا قبل از موقعیت قرار دارند را، بازمی‌گرداند. در حال که موقعیت امین رخ داد را بازمی‌گرداند. 
 در نتیجه برای درخت دودویی داریم :
 
 
 لغت‌نامه نمایه ساز فشرده، رتبه لغت‌نامه نیز نامیده می‌شود . بر اساس تعدادی از تکنیک‌های نمایش فشرده، از جمله ، و .
مشکل اساسی ذخیره‌سازی زیر مجموعهٔ از مجموعه جهانی ( )، معمولاً با ارائه بیتی که اگر نمایش داده می‌شوند. لغت‌نامه‌های نمایه ساز، تابع‌هایی را پشتیبانی می‌کند، مانند نمایش دادن، حذف و اضافه کردن در موارد پویا.
 یک نمایش ساده وجود دارد که از بیت از فضای حافظه ( برای بیت اصلی آرایه و برای ساختار کمکی) استفاده می‌کند و در زمان ثابت، و را پشتیبانی می‌کند. این از یک ایدهٔ مشابه که برای بوده‌است، استفاده می‌کند. این یک عدد ثابت از تابع بازگشتی است قبل از پایان زیر مسئله‌ای که اندازهٔ محدود دارد.
{"title": "داده ساختارهای فشرده", "link": "https://fa.wikipedia.org//w/index.php?title=%D8%AF%D8%A7%D8%AF%D9%87_%D8%B3%D8%A7%D8%AE%D8%AA%D8%A7%D8%B1%D9%87%D8%A7%DB%8C_%D9%81%D8%B4%D8%B1%D8%AF%D9%87&oldid=29634142", "language": "fa"}