ساختار داده مختصر

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو

در علوم کامپیوتر ، یک ساختار داده مختصر ، ساختار داده ای است که از مقدار فضایی استفاده می کند که "نزدیک" به کران پایینی نظری اطلاعات است، اما (برخلاف سایر نمایش های فشرده) هنوز امکان عملیات پرس و جو کارآمد را فراهم می کند. این مفهوم در ابتدا توسط Jacobson [1] برای رمزگذاری بردارهای بیت ، درختان (بدون برچسب) و نمودارهای مسطح معرفی شد. برخلاف الگوریتم‌های عمومی فشرده‌سازی داده‌های بدون تلفات ، ساختارهای داده مختصر توانایی استفاده از آن‌ها را در جای خود، بدون اینکه ابتدا از حالت فشرده خارج کنند، حفظ می‌کنند. یک مفهوم مرتبط، ساختار داده فشرده است، که در آن اندازه ساختار داده به داده خاصی که نمایش داده می شود بستگی دارد.

فرض کنید کهتعداد بهینه اطلاعات نظری بیت های مورد نیاز برای ذخیره برخی داده ها است. یک نمایش از این داده ها نامیده می شود:

  • ضمنی اگر طول بکشدتکه های فضا،
  • مختصر اگر طول بکشدتکه های فضا، و
  • فشرده اگر طول بکشدتکه های فضا

به عنوان مثال، یک ساختار داده که استفاده می کندبیت های ذخیره سازی فشرده است،بیت ها مختصر است،بیت نیز مختصر است وبیت ها ضمنی است.

بنابراین ساختارهای ضمنی معمولاً به ذخیره سازی اطلاعات با استفاده از تغییر داده های ورودی کاهش می یابد. شناخته شده ترین مثال در این مورد Heap است.

لغت نامه های مختصر

فرهنگ لغت های قابل نمایه سازی مختصر، که به آنها لغت نامه های رتبه/انتخاب نیز می گویند ، اساس تعدادی از تکنیک های نمایش مختصر، از جمله درختان دودویی را تشکیل می دهند .درخت‌ها و چند مجموعه‌ها ، [ 2] و همچنین درخت‌ها و آرایه‌های پسوندی . [3] مشکل اساسی ذخیره یک زیر مجموعه استاز یک کیهان، معمولاً به صورت یک آرایه بیت نمایش داده می شودجایی کهاگریک فرهنگ لغت قابل نمایه سازی از روش های معمول در دیکشنری ها (پرس و جوها و درج/حذف ها در حالت پویا) و همچنین عملیات زیر پشتیبانی می کند:

برای.

به عبارت دیگر،تعداد عناصر برابر باتا موقعیتدر حالی که موقعیت را برمی گرداند-ام وقوع.

یک نمایش ساده [4] وجود دارد که از آن استفاده می کندبیت های فضای ذخیره سازی (آرایه بیت اصلی و یکساختار کمکی) و از رتبه و انتخاب در زمان ثابت پشتیبانی می کند. از ایده ای مشابه برای پرس و جوهای محدوده حداقل استفاده می کند . قبل از توقف در یک مشکل فرعی با اندازه محدود، تعداد ثابتی از بازگشت وجود دارد. آرایه بیتبه بلوک های بزرگ در اندازه تقسیم می شودبیت ها و بلوک های کوچک اندازهبیت ها برای هر بلوک بزرگ، رتبه اولین بیت آن در یک جدول جداگانه ذخیره می شود; هر ورودی از این قبیل طول می کشدبیت برای مجموعبیت های ذخیره سازی در یک بلوک بزرگ، دایرکتوری دیگررتبه هر یک را ذخیره می کندبلوک های کوچکی که حاوی آن است. تفاوت در اینجا این است که فقط نیاز داردبیت ها برای هر ورودی، زیرا فقط تفاوت های رتبه بیت اول در بلوک بزرگ حاوی باید ذخیره شود. بنابراین، این جدول در مجموع ازبیت ها یک جدول جستجوسپس می توان از آن استفاده کرد که پاسخ هر درخواست رتبه ممکن را در یک رشته بیت از طول ذخیره می کندبرای; این نیاز داردتکه های فضای ذخیره سازی بنابراین، از آنجایی که هر یک از این جداول کمکی می گیرندفضا، این ساختار داده از پرس و جوهای رتبه بندی پشتیبانی می کندزمان وتکه های فضا

برای پاسخ به یک سوال برایدر زمان ثابت، یک الگوریتم زمان ثابت محاسبه می کند:

در عمل، جدول جستجورا می توان با عملیات بیتی و جداول کوچکتر جایگزین کرد که می توان از آنها برای یافتن تعداد بیت های تنظیم شده در بلوک های کوچک استفاده کرد. این اغلب سودمند است، زیرا ساختارهای داده مختصر کاربردهای خود را در مجموعه داده های بزرگ پیدا می کنند، در این صورت از دست دادن حافظه پنهان بسیار بیشتر می شود و شانس حذف جدول جستجو از حافظه پنهان CPU نزدیک تر می شود. [5] پرس و جوهای انتخابی را می توان به راحتی با انجام یک جستجوی باینری در همان ساختار کمکی مورد استفاده برای رتبه پشتیبانی کرد . با این حال، این طول می کشدزمان در بدترین حالت یک ساختار پیچیده تر با استفاده ازبیت های فضای ذخیره اضافی را می توان برای پشتیبانی از انتخاب در زمان ثابت استفاده کرد. [6] در عمل، بسیاری از این راه‌حل‌ها دارای ثابت‌های پنهانی هستندعلامت گذاری که قبل از آشکار شدن هر مزیت مجانبی غالب است. پیاده‌سازی‌هایی که از عملیات پهن‌کلمه و بلوک‌های همتراز با کلمه استفاده می‌کنند، اغلب در عمل بهتر عمل می‌کنند. [7]

فرهنگ لغت فشرده با آنتروپی

رارویکرد فضایی را می توان با توجه به اینکه وجود دارد بهبود بخشیدمتمایز-زیر مجموعه های(یا رشته های باینری با طولدقیقا با1)، و بنابراینیک کران پایینی نظری اطلاعات بر روی تعداد بیت های مورد نیاز برای ذخیره سازی است. یک فرهنگ لغت موجز (ایستا) وجود دارد که به این حد می رسد، یعنی با استفاده ازفضا. [8] این ساختار را می توان برای پشتیبانی از رتبه بندی و انتخاب پرس و جوها و برداشت ها گسترش دادفضا. [2] پرس‌وجوهای رتبه‌بندی صحیح در این ساختار به عناصر موجود در مجموعه محدود می‌شوند، مشابه نحوه عملکرد حداقل توابع هش‌سازی کامل. این کران را می توان با کاهش فضای ذخیره سازی فرهنگ لغت به یک مبادله فضا/زمان کاهش دادبا پرس و جو گرفتنزمان. [9]

مثالها

یک رشته با پایان تهی ( رشته C ) فضای Z + 1 را می گیرد و بنابراین ضمنی است. رشته ای با طول دلخواه ( رشته پاسکال ) فضای Z + log( Z ) را می گیرد و بنابراین موجز است. اگر حداکثر طول وجود داشته باشد - که در عمل هم همینطور است، زیرا 2 32 = 4 گیگا بایت داده یک رشته بسیار طولانی است و 2 64 = 16 EiB داده در عمل بزرگتر از هر رشته ای است - پس رشته ای با طول همچنین ضمنی است، با گرفتن فضای Z + k ، که در آن k تعداد داده‌هایی است که حداکثر طول را نشان می‌دهند (مثلاً 64 بیت).

هنگامی که دنباله ای از آیتم های با طول متغیر (مانند رشته ها) نیاز به رمزگذاری دارند، احتمالات مختلفی وجود دارد. یک رویکرد مستقیم این است که یک طول و یک مورد را در هر رکورد ذخیره کنید - سپس می توان آنها را یکی پس از دیگری قرار داد. این امکان کارآمدی بعدی را فراهم می کند، اما k امین مورد را پیدا نمی کند. یک جایگزین این است که آیتم ها را به ترتیب با یک جداکننده (به عنوان مثال، رشته با پایان تهی) قرار دهید). این از یک جداکننده به جای طول استفاده می کند، و به طور قابل توجهی کندتر است، زیرا کل دنباله باید برای جداکننده ها اسکن شود. هر دوی اینها در فضا کارآمد هستند. یک رویکرد جایگزین، جداسازی خارج از باند است: آیتم‌ها را می‌توان به سادگی یکی پس از دیگری، بدون مرزبندی قرار داد. سپس کران های آیتم را می توان به عنوان دنباله ای از طول، یا بهتر، جابجایی در این دنباله ذخیره کرد. متناوبا، یک رشته باینری مجزا شامل 1ها در موقعیت‌هایی که یک آیتم شروع می‌شود، و 0s در هر جای دیگر همراه با آن کدگذاری می‌شود. با توجه به این رشته،تابع می تواند به سرعت تعیین کند که هر آیتم با توجه به شاخص آن از کجا شروع می شود. [10] این فشرده است اما مختصر نیست، زیرا 2 فضای Z را اشغال می کند که O( Z ) است.

مثال دیگر نمایش درخت باینری است : درخت باینری دلخواه درگره ها را می توان در نمایش دادبیت ها در حالی که از انواع عملیات بر روی هر گره پشتیبانی می کند، که شامل یافتن والد، فرزند چپ و راست آن، و برگرداندن اندازه درخت فرعی آن، هر کدام در زمان ثابت است. تعداد درختان باینری مختلف رویگره است. برای بزرگ، این در مورد است; بنابراین ما حداقل در مورد نیاز داریمبیت هایی برای رمزگذاری آن بنابراین یک درخت دودویی مختصر فقط اشغال می‌شودبیت در هر گره

همچنین مشاهده کنید

منابع

  1. جیکوبسون، جی جی (۱۹۸۸). ساختارهای داده ایستا مختصر (پایان نامه دکتری). پیتسبورگ، PA: دانشگاه کارنگی ملون.
  2. ^ a b رامان، آر. V. رامان; S. S Rao (2002). "لغت نامه های قابل نمایه سازی مختصر با برنامه های کاربردی برای رمزگذاری درختان k-ary و چند مجموعه" . مجموعه مقالات سیزدهمین سمپوزیوم سالانه ACM-SIAM در مورد الگوریتم های گسسته . صص  233-242 . arXiv : 0705.0552 . CiteSeerX 10.1.1.246.3123 . doi : 10.1145/1290672.1290680 . شابک   0-89871-513-X.
  3. ^ صداکانه، ک. R. Grossi (2006). "فشردن ساختارهای داده مختصر در مرزهای آنتروپی" (PDF) . مجموعه مقالات هفدهمین سمپوزیوم سالانه ACM-SIAM در مورد الگوریتم گسسته . صص 1230–1239. شابک  0-89871-605-5. بایگانی شده از نسخه اصلی (PDF) در 29/09/2011.
  4. Jacobson, G. (1 نوامبر 1989). درختان و نمودارهای ایستا با فضای کارآمد (PDF) . سی امین سمپوزیوم IEEE در مبانی علوم کامپیوتر. doi : 10.1109/SFCS.1989.63533 . بایگانی شده از نسخه اصلی (PDF) در 2016-03-12.
  5. ^ گونزالس، آر. اس. گرابوفسکی; V. Mäkinen; جی ناوارو (2005). "اجرای عملی پرس و جوهای رتبه و انتخاب" (PDF) . جلد مجموعه مقالات چهارمین کارگاه آموزشی الگوریتم های کارآمد و تجربی (WEA) . صص 27-38.
  6. کلارک، دیوید (1996). درختان پت فشرده (PDF) (پایان نامه دکتری). دانشگاه واترلو
  7. ^ ویگنا، اس (2008). اجرای گسترده کلمات جستجوهای رتبه/انتخاب (PDF) . الگوریتم های تجربی نکات سخنرانی در علوم کامپیوتر. جلد 5038. صص 154-168. CiteSeerX 10.1.1.649.8950 . doi : 10.1007/978-3-540-68552-4_12 . شابک   978-3-540-68548-7.
  8. ^ برودنیک، ا. J. I Munro (1999). "عضویت در زمان ثابت و فضای تقریباً حداقل" (PDF) . SIAM J. Comput . 28 (5): 1627-1640. CiteSeerX 10.1.1.530.9223 . doi : 10.1137/S0097539795294165 .  
  9. Pătraşcu، M. (2008). "Succincter" (PDF) . مبانی علوم کامپیوتر، 2008. FOCS'08. IEEE چهل و نهمین سمپوزیوم سالانه IEEE در . صص 305-313.
  10. بلاززوگی، جمال. "هش، جابجایی و فشرده سازی" (PDF) .