دانلود پاورپوینت Extendible Hashing, tries

\n

Extendible Hashing, tries

\n

\n

عنوان های پاورپوینت  : 

\n

Extendible Hashing, tries

\n

Lecture 19 Extendible Hashing, tries (Sections 12.1-12.4)

\n

روش Hashing قابل توسعه

\n

روش Hashing با فضای قابل توسعه

\n

روش Hashing با فضای قابل توسعه

\n

ساختار Trie

\n

ساختار Trie

\n

روش استفاده از ساختار Trie در Hashing

\n

نگهداری ساختار Trie روی دیسک

\n

نگهداری ساختار Trie روی دیسک

\n

نگهداری ساختار Trie روی دیسک

\n

نگهداری ساختار Trie روی دیسک

\n

 نگهداری ساختار Trie روی دیسک

\n

 نگهداری ساختار Trie روی دیسک

\n

کارآیی Hashing با فضای قابل توسعه

\n

\n \n\n \n\n

---

\n\nقسمت ها و تکه های اتفاقی از فایل\n\n \n\n \n\nExtendible Hashing, tries\n\n \n\n.....\n\n \n\nروش Hashing با فضای قابل توسعه (Extendible) چیست؟\n\n \n\nروش Hashing با فضای پویا (Dynamic) چیست؟\n\n \n\nروش Hashing با توسعه خطی (Linear) چیست؟\n\n \n\n \n\nروش Hashing با فضای قابل توسعه\n\nمشکلات روش Hashing با فضای ثابت (Static) چیست؟\n\n \n\nفضای ایجاد شده در آغاز ممکن است بسیار بیش ازحد نیاز باشد.                             (چرا؟)\n\n \n\nممکن است مرتبا نیاز به تجدید ساختار داشته باشد.                                              (چرا؟)\n\n \n\nدر مقایسه با B-tree برای فایل های داده با اندازه متغیر (Dynamic) مناسب نمیباشد.  (چرا؟)\n\n \n\nتعداد زیاد عملیات حذف و اضافه کلیدها باعث پایین آمدن راندمان میشود.                    (چرا؟)\n\n \n\nروش Hashing با فضای قابل توسعه (Extendible) چیست؟\n\n \n\nدر این روش فضای رزرو شده برحسب نیاز بزرگتر یا کوچکتر میشود.\n\n \n\nتعداد زیاد عملیات حذف و اضافه کلیدها باعث پایین آمدن راندمان نمی شود.                 (چرا؟)\n\n \n\nبرای فایل های داده با اندازه متغیر (Dynamic) مناسب تر میباشد.                  (درمقایسه با؟)\n\n \n\nروش Hashing با فضای قابل توسعه\n\nساختار Hashing با فضای قابل توسعه چگونه است؟\n\n \n\nترکیبی از روش Hashing با ساختاری به نام Trie میباشد.\n\n \n\nکلیدها در تعدادی Bucket قرار می گیرند.\n\n \n\nBucketها به صورت اجزاء مستقل از یکدیگر روی فضای موجود دیسکها رزرو شده اند.\n\n \n\nکلیدهایی که آدرس Hash آنها Prefix مشترکی داشته باشد در یک Bucket قرار می گیرند.\n\nساختار Trie\n\nساختار Trie چیست؟\n\n \n\nنوعی ساختار درختواره ای که برای دسته بندی کلیدها استفاده میشود.\n\n \n\nاین ساختار را به نام Radix Searching نیز می شناسند.\n\n \n\nشکل زیر یک ساختار Trie موسوم به Radix 26 را نشان میدهد.\n\n \n\n۰۰۰۰\n\nچگونه از ساختار Trie در Hashing استفاده میشود؟\n\n \n\nدر روش Hashing از نوعی ساختار Trie به نام Radix 2 استفاده می کنیم.\n\n \n\nدر این ساختار، هر نود بر مبنای یکی از بیتهای Prefix کلید ، آنرا به یکی از دو شاخه زیرین خود تخصیص می دهد.\n\n \n\nمثال: شکل زیر نمونه ای از این ساختار را نشان می دهد.\n\nBucket A  شامل کلیدهایی خواهد بود که دو بیت اول کلید Hash آنها 00 یا 01 باشد.\n\nBucket B  شامل کلیدهایی خواهد بود که دو بیت اول کلید Hash آنها 10 باشد.\n\nBucket C  شامل کلیدهایی خواهد بود که دو بیت اول کلید Hash آنها 11 باشد.\n\n \n\nنگهداری ساختار Trie روی دیسک\n\nروش نگهداری یک ساختار Trie روی دیسک چگونه است؟\n\n \n\nهنگامیکه حجم داده ها بالا برود و فضای RAM برای کلیه نودها کافی نباشد،\n\n \n\nبایستی بتوان به هریک از نودهای این ساختار مستقیما روی دیسک دسترسی پیدا نمود.\n\n \n\nدراینصورت مسائلی مشابه با ساختارهای B-Tree دوباره مطرح می گردند و\n\n \n\nمکانیزم Hashing مزیت خود را در مقابل B-Tree از دست میدهد.\n\n \n\nنگهداری ساختار Trie روی دیسک\n\nتبدیل یک ساختار Trie به Directory چگونه است؟\n\n \n\nبرای حفظ مزیتهای مکانیزم Hashing لازم است که ساختار درختواره ای Trie را به یک ساختار مسطح و یکپارچه تبدیل کنیم.\n\n \n\nدر این صورت کافیست که ساختار Trie را بسط داده تا یک Binary Tree کامل بدست آوریم و سپس آنرا بصورت یک Array پیاده سازی نماییم.\n\n \n\nاین ساختار جدید (Array) بعنوان یک Directory که به Bucketهای مختلف اشاره میکند استفاده خواهد شد.\n\nنگهداری ساختار Trie روی دیسک\n\nدر صورت پر شدن یک Bucket  چگونه عمل میشود؟\n\nحالت اول:\n\nفضای Directory امکان اضافه نمودن یک Bucket جدید برادر (یا Buddy Bucket) در مجاورت Bucket پر شده را میدهد.\n\nدر اینصورت Bucket جدید اضافه گشته و کلیدها بین دو Bucket برحسب Prefix مربوطه توزیع میشوند.\n\nمثال: شکل زیر این حالت را پس از پرشدن Bucket A و ایجاد Bucket D نشان می دهد.\n\nنگهداری ساختار Trie روی دیسک\n\nدر صورت پر شدن یک Bucket  چگونه عمل میشود؟\n\nحالت دوم:\n\nامکان ایجاد یک Buddy Bucket وجود ندارد.\n\n \n\nبنابراین درصورت Overflow بایستی از روش Splitting استفاده نمود.\n\n \n\nمثال: شکل زیر این حالت را پس از پر شدن Bucket B و ایجاد Bucket D نشان میدهد.\n\nنگهداری ساختار Trie روی دیسک\n\n(ادامه...)\n\nدر اینصورت لازم است که یک سطح (Level) به تعداد سطوح ساختار Trie اضافه گردد.\n\nبه عبارت دیگر، یک Bit به تعداد Bitها اضافه شود.\n\nبنابراین فضای Directory دو برابر می گردد و\n\nآدرس Bucketها دوباره در فضای جدید توزیع میگردد.\n\nنگهداری ساختار Trie روی دیسک\n\n \n\nسؤال:\n\n \n\nنقش Hashing در این میان چیست؟\n\n \n\nجواب:\n\n....\n\n \n\nقابل تطبیق با نیازهای ما بر حسب کم یا زیاد شدن تعداد کلیدها در ایندکس می باشد.\n\n \n\nتعداد دسترسی به دیسک همیشه ثابت می باشد و از دو حالت خارج نیست:\n\nاگر اندازه Directory اجازه دهد آن را در حافظه RAM داشته باشیم تنها یک دسترسی به دیسک برای یافتن کلید کافی خواهد بود.\n\nاگر اندازه Directory ایجاب نماید که آن را روی دیسک نگاه داریم، دو دسترسی به دیسک برای یافتن کلید کافی خواهد بود.\n\n \n\nخارج از این دو حالت تعداد I/O وابسته به تعداد کلیدها نمیباشد و کارآیی ایندکس ثابت میباشد.\n\n \n\nبه عبارت دیگر هدف اصلی ما در Hashing که تامین O(1) بود با این روش تامین میگردد،\n\n \n\nزیرا بر خلاف روشهای قبل مساله Overflow وجود ندارد.\n\n \n\n \n\n30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و  توجیهی |  پایان-نامه |  پی دی اف  مقاله ( کتاب ) | نقشه | پلان طراحی |  های آماده به صورت رایگان میباشد ( word | pdf | docx | doc )