پاورپوینت بررسی روشهای درهمسازی اطلاعات و پیادهسازی و مقایسه روشهای مختلف درهمسازی آدرسدهی باز بر روی دادههای قرآنی و کلمات فارسی

بخشی از پاورپوینت

اسلاید 1 :

بررسی روشهای درهمسازی اطلاعات و پیادهسازی و مقایسه روشهای مختلف درهمسازی آدرسدهی باز بر روی دادههای قرآنی و کلمات فارسی

اسلاید 2 :

فهرست
رفع برخوردارها

اسلاید 3 :

تعاریف

اسلاید 4 :

روند حرکتی توابع درهم ساز
بر اساس مطالعه انجام شده جهت استفاده مناسب از توابع درهم ساز دو مدل کاری انتخاب شده است:
توابع درهم ساز بدون تصادم
Perfect Hash Function (PHF): جهت ذخیره سازی مجموعه n مشخص کلید بدون برخورد
Minimal PHF(MPHF): جهت ذخیره سازی n کلید مشخص بدون برخورد در حداقل فضا
Preserving Order MPHF (POMPHF): جهت ذخیره سازی n کلید به ترتیب در n آدرس بدون برخورد
.
رفع برخورد
اگر مجموعه کلید از ابتدا مشخص نباشد
استفاده از هر نوع تابع امکان ایجاد تصادم را خواهد داشت.
بعد از بوجود آمدن برخورد به رفع آن می پردازیم.

اسلاید 5 :

آدرسدهی باز: تلاش جهت حل برخورد با استفاده از یک آدرس دیگر
زنجیر کردن: کلیدهای مترادف درون یک لیست پیوندی قرار میگیرند
سه استراژی جانشین سازی برای حل برخورد: اگر کلیدی بخواهد وارد سلولی از جدول شود که توسط کلید دیگر اشغال شده است:
FCFS: کلیدقدیمی در سلول نگه داشته میشود و کلید جدید به یک فضای منتقل می شود.
LCFS : کلید قدیمی سلولهای بعدی را بررسی میکند تا یک فضای خالی پیدا کند
ROBIN HOOD: در بین دو کلید ، کلیدی که بزرگترین تغییر مکان را دارد در سلول نگه داشته میشود و دیگری به یک فضای خالی منتقل می شود.
تلاش برای رسیدن به آدرس دهی کامل
بدترین رفتار درهمسازی زمانی است که n کلید به یک سلول درهمسازی شود.
زنجیره سازی دوطرفه: یک مجموعه کلید به صورت متوالی به جدول Tاضافه میکند.
از دو تابع درهمسازی استفاده میکند .
هر کلید x به کوتاهترین زنجیر (با کمترین تعداد کلید ) از میان دو تا زنجیر وارد میشود.
رفع برخوردها
رفع برخورد

اسلاید 6 :

روشهای درهم سازی آدرس باز
درهمسازی خطی
درهمسازی دوگانه
استفاده از دو تایع درهمسازی بطور همزمان.
آدرسهاي توليد شده در اين دنباله داراي روابط مشخصي با يكديگرند و اصل پخش كليدها و افزايش ميزان بينظمي را زير سوال ميبرند
مشكل خوشه بندي اولیه را رفع می نمايد
اما همچنان مشکل خوشهبندی ثانویه را دارد.
مشكل ديگري كه مي توان به آن اشاره كرد توليد آدرسهاي يكسان و تكراري در دنبالههاي آدرس ميباشد.
مشكل خوشهبندي اوليه: به ازاي مقدار ثابت c و تمام مقادير اوليه براي تابع يك دنباله آدرس مشخص توليد خواهد نمود.
مشكل خوشهبندي ثانويه: به ازاي دو كليد مختلفk2 و k1، رابطهي h(k1)=h(k2)، برقرار باشد. در اين صورت تمام آدرسهاي دو دنباله يكسان است.
درهمسازی درجه دوم

اسلاید 7 :

درهمسازي دامنه محدود
به منظور استفاده از روش دامنه محدود، روند زير براي بدست آوردن آدرس كليد K در فضايي با m= pn مكان اجرا مي شود:
به ازاي هر کليد k دو عدد a,b را محاسبه کنيد:
a= k mod m, b = k mod (m-2)
واضح است که روابط 0≤b≤m-2 , 0≤a≤m-1 برقرار مي شود.
اعداد a وb درمبنايp بر اساس محدوده ي GF(pn) نشان دهنده ي دو چندجمله اي به نامهاي gk (X) و hk (X) مي­باشند.
a= ( an-1, an-2,., a0)P
b= ( bn-1, bn-2,., b0)P
gk (X)= an-1Xn-1 + an-2Xn-2 + … + a0
hk (X)= bn-1Xn-1 + bn-2Xn-2+ … + b0
 شماره دنباله آدرس ها، كه نشان دهنده ی چندمين آدرس توليدي است، را نيز در مبناي p نمايش داده و چندجمله اي fi(x) در فضاي GF(pn) توليد مي شود.
i= ( in-1, in-2,., i0)P
fi (X)= in-1Xn-1 + in-2Xn-2 + … + i0
حال بر اساس قوانين حاکم بر GF(pn) و با در نظر گرفتن fλ(X) به عنوان چند جمله اي ثابت در فضاي GF(pn)رابطه زير نشان دهنده تابع در هم ساز جديد است.
Hf(k,i) = (gk(X) + fλ(X) fi(X) hk(X)) mod t(x)
Hf(k,i)چندجمله اي از فضاي GF(pn) مي باشد که ضرايب آن نشان دهنده عددي است در مبناي p که همان آدرس توليد شده تابع درهمساز است.

اسلاید 8 :

شرایط پیادهسازی
كلمات موجود در كتب تفاسير قرآن كريم: 646،816
افعال زبان فارسی از روزنامه همشهری: 373،344
روشهاي بررسي شده: درهم ساز خطي، دوگانه، دامنه محدود و دوطرفه.
اندازه حافظه برای دادههای قرآنی: 707،293
اندازه حافظه برای کلمات روزنامهها : 390،647
دامنه محدود
دادههای قرآنی: p=29 , n=4
707،281
کلمات روزنامهها: p=5 , n=8 390،625
تعداد و فضا

اسلاید 9 :

معیارهای مقایسه
متوسط تعداد دسترسي به حافظه: اگر در هنگام بازيابي n كليد به طور كلي N بار دسترسي به حافظه نياز باشد، اين مقدار برابر با N/n خواهد بود
پراکنده سازی: هر چه مقدار آن در حین درهمسازي بیشتر باشد احتمال برخورد کمتر است.
pi : برابر با تعداد دسترسیها به خانه iام از حافظه نسبت به کل تعداد دسترسیها.

اسلاید 10 :

مقایسه- متوسط تعداد دسترسی
متوسط تعداد دسترسی در داده های قرآنی
متوسط تعداد دسترسی در داده های قرآنی در حالت خوشه 0.1
خوشه 0.1: شامل کلیدهایی که باقیمانده تقسیم شان بر تعداد خانههای حافظه در بازه [0,0.1*m] قرار دارد

اسلاید 11 :

مقایسه- متوسط تعداد دسترسی
متوسط تعداد دسترسی در داده های فارسی
متوسط تعداد دسترسی در داده های فارسی در حالت خوشه 0.1

اسلاید 12 :

مقایسه- پراکنده سازی
پراکنده سازی بعد از افزودن تمامی داده های قرآنی
پراکندگی داده های قرآنی در خوشه 0.1÷

اسلاید 13 :

مقایسه- پراکنده سازی
پراکنده سازی بعد از افزودن تمامی داده های فارسی
پراکندگی داده های فارسی در خوشه 0.1÷

اسلاید 14 :

نتایج