پاورپوینت بررسی روشهای درهم‌سازی اطلاعات و پیاده‌سازی و مقایسه روشهای مختلف درهم‌سازی آدرس‌دهی باز بر روی داده‌های قرآنی و کلمات فارسی (pptx) 15 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 15 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بررسی روشهای درهم‌سازی اطلاعات و پیاده‌سازی و مقایسه روشهای مختلف درهم‌سازی آدرس‌دهی باز بر روی داده‌های قرآنی و کلمات فارسی
فهرست
رفع برخوردارها
S. M. Vahidipour UoK
تعاریف
S. M. Vahidipour UoK
روند حرکتی توابع درهم ساز
بر اساس مطالعه انجام شده جهت استفاده مناسب از توابع درهم ساز دو مدل کاری انتخاب شده است:
توابع درهم ساز بدون تصادم
Perfect Hash Function (PHF): جهت ذخیره سازی مجموعه n مشخص کلید بدون برخورد
Minimal PHF(MPHF): جهت ذخیره سازی n کلید مشخص بدون برخورد در حداقل فضا
Preserving Order MPHF (POMPHF): جهت ذخیره سازی n کلید به ترتیب در n آدرس بدون برخورد
...
رفع برخورد
اگر مجموعه کلید از ابتدا مشخص نباشد
استفاده از هر نوع تابع امکان ایجاد تصادم را خواهد داشت.
بعد از بوجود آمدن برخورد به رفع آن می پردازیم.
S. M. Vahidipour UoK
S. M. Vahidipour UoK
آدرس‌دهی باز: تلاش جهت حل برخورد با استفاده از یک آدرس دیگر
زنجیر کردن: کلیدهای مترادف درون یک لیست پیوندی قرار می‌گیرند
سه استراژی جانشین سازی برای حل برخورد: اگر کلیدی بخواهد وارد سلولی از جدول شود که توسط کلید دیگر اشغال شده است:
FCFS: کلیدقدیمی در سلول نگه داشته می‌شود و کلید جدید به یک فضای منتقل می شود.
LCFS : کلید قدیمی سلول‌های بعدی را بررسی می‌کند تا یک فضای خالی پیدا کند
ROBIN HOOD: در بین دو کلید ، کلیدی که بزرگترین تغییر مکان را دارد در سلول نگه داشته می‌شود و دیگری به یک فضای خالی منتقل می شود.
تلاش برای رسیدن به آدرس دهی کامل
بدترین رفتار درهم‌سازی زمانی است که n کلید به یک سلول درهم‌سازی شود.
زنجیره سازی دوطرفه: یک مجموعه کلید به صورت متوالی به جدول Tاضافه می‌کند.
از دو تابع درهم‌سازی استفاده می‌کند .
هر کلید x به کوتاه‌ترین زنجیر (با کمترین تعداد کلید ) از میان دو تا زنجیر وارد می‌شود.
رفع برخوردها
رفع برخورد
روشهای درهم سازی آدرس باز
درهم‌سازی خطی
درهم‌سازی دوگانه
استفاده از دو تایع درهم‌سازی بطور همزمان.
آدرس‌هاي توليد شده در اين دنباله داراي روابط مشخصي با يكديگرند و اصل پخش كليدها و افزايش ميزان بي‌نظمي را زير سوال مي‌برند
مشكل خوشه بندي اولیه را رفع می نمايد
اما همچنان مشکل خوشه‌بندی ثانویه را دارد.
مشكل ديگري كه مي توان به آن اشاره كرد توليد آدرس‌هاي يكسان و تكراري در دنباله‌هاي آدرس مي‌باشد.
مشكل خوشه‌بندي اوليه: به ازاي مقدار ثابت c و تمام مقادير اوليه براي تابع يك دنباله آدرس مشخص توليد خواهد نمود.
مشكل خوشه‌بندي ثانويه: به ازاي دو كليد مختلفk2 و k1، رابطه‌ي h(k1)=h(k2)، برقرار باشد. در اين صورت تمام آدرس‌هاي دو دنباله يكسان است.
درهم‌سازی درجه دوم
S. M. Vahidipour UoK
درهم‌سازي دامنه محدود
به منظور استفاده از روش دامنه محدود، روند زير براي بدست آوردن آدرس كليد 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 که همان آدرس توليد شده تابع درهمساز است.
S. M. Vahidipour UoK
شرایط پیاده‌سازی
كلمات موجود در كتب تفاسير قرآن كريم: 646،816
افعال زبان فارسی از روزنامه همشهری: 373،344
روشهاي بررسي شده: درهم ساز خطي، دوگانه، دامنه محدود و دوطرفه.
اندازه حافظه برای داده‌های قرآنی: 707،293
اندازه حافظه برای کلمات روزنامه‌ها : 390،647
دامنه محدود
داده‌های قرآنی: p=29 , n=4
707،281
کلمات روزنامه‌ها: p=5 , n=8 390،625
تعداد و فضا
S. M. Vahidipour UoK
معیارهای مقایسه
متوسط تعداد دسترسي به حافظه: اگر در هنگام بازيابي n كليد به طور كلي N بار دسترسي به حافظه نياز باشد، اين مقدار برابر با N/n خواهد بود
پراکنده سازی: هر چه مقدار آن در حین درهم‌سازي بیشتر باشد احتمال برخورد کمتر است.
pi : برابر با تعداد دسترسی‌ها به خانه iام از حافظه نسبت به کل تعداد دسترسی‌ها.
S. M. Vahidipour UoK
