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

در علوم کامپیوتر ،داده ساختار فشرده داده ساختاری است که از فضایی استفاده می کند که به نظریه اطلاعات کران پایین نزدیک است؛ ولی (برخلاف دیگر نمایش های فشرده) هنوز برای عملیات ها کارایی دارد. مفهوم این داده ساختار اولین بار توسط جاکوبسون معرفی شد. با مفهوم رمز گذاری آرایه بیتی، درخت (بدون برچسب) و گراف مسطح. برخلاف الگوریتم فشرده سازی بی اتلاف داده ها، به طور کلی داده ساختار فشرده، این ویژگی را دارد که می توان بدون ناهم فشرده کردن داده ها از آن ها استفاده کرد.
داده ساختار ضمنی: Z + O ( 1 ) {\displaystyle Z+O(1)} بیت از فضا
داده ساختار فشرده: Z + O ( Z ) {\displaystyle Z+O(Z)} بیت از فضا
داده ساختار متراکم: O ( Z ) {\displaystyle O(Z)} بیت از فضا
فرض کنید که Z تعداد بیت های مورد نیاز برای برای ذخیرهٔ برخی داده ها است. نمایش آن به شرح زیر است:
برای مثال، یک داده ساختار 2 Z {\displaystyle 2Z} بیت استفاده می کند برای ذخیرهٔ داده ساختار متراکم است، Z + Z {\displaystyle Z+{\sqrt {Z}}} یا Z + lg ⁡ Z {\displaystyle Z+\lg Z} بیت برای داده ساختار فشرده است و Z + 3 {\displaystyle Z+3} بیت برای داده ساختار ضمنی است.
داده ساختار ضمنی، بر اساس جایشگت های مختلف ورودی می تواند کاهش بیاید. مثال شناخته شدهٔ آن هرم است.