لغت نامه و جدول درهم سازی

لغت نامه و جدول درهم سازی

اسلاید 1: لغت نامه و جدول درهم سازي Dictionaries and Hash Tables ساختمان داده ها و الگوريتم

اسلاید 2:

اسلاید 3: لغت نامه - Dictionaryمجموعه اي از زوج هاي مرتب به صورت:(key, element)کليد زوج هاي مرتب متفاوت استعمليات روي لغت نامه:get(theKey)put(theKey, theElement)remove(theKey)

اسلاید 4: کاربرد Applicationمجموعه دانشجويان اين کلاس(key, element) = (student name, linear list of assignment and exam scores)همه کليدها منحصر بفرد هستندمثال:پيدا کردن زوج مرتبي که کليد آن ”علي تقي زاده“ باشدبروز رساني رکوردي که کليد آن ”ايمان معتمدي“ استبروز رساني معادل حذف رکورد فعلي و سپس اضافه کردن رکورد با تغييرات جديد استUpdate(x) R = get(x) ; // get the record with key Xremove(x) ; Modify RPut(x , R)

اسلاید 5: کليدهاي تکراري در لغت نامه لغت نامه ممکن است کليد تکراري داشته باشدهمانند کلمات تکراري يک لغت نامه روان : روح، جانروان: رونده ، جاريروان: اسم خاص (اسم شهر)روان: اسم خاص (اسم شخص)مي توان ركوردهاي هم كليد را با يك ليست نشان داد

اسلاید 6: نمايش لغت نامه با يک ليست خطيL = (e0, e1, e2, e3, …, en-1)Each ei is a pair (key, element).5-pair dictionary D = (a, b, c, d, e).a = (aKey, aElement), b = (bKey, bElement), etc.مي توان از آرايه يا ليست پيوندي استفاده کرد

اسلاید 7: نمايش با آرايهabcde get(theKey) O(size) time put(theKey, theElement) O(size) براي تشخيص دادن کليد تکراري و , O(1) براي افزودن کليد به سمت راست آرايه. remove(theKey) O(size) time.

اسلاید 8: آرايه مرتبABCDEاعضا بر اساس کليد به صورت صعودي مرتب شده اند get(theKey) O(log size) time put(theKey, theElement) O(log size) براي يافتن کليد تکراري, O(size) براي افزودن کليد در محل مناسب remove(theKey) O(size) time.

اسلاید 9: زنجيره نامرتب get(theKey) O(size) time put(theKey, theElement) O(size) براي تشخيص دادن کليد تکراري و , O(1) براي افزودن کليد به سمت راست آرايه. remove(theKey) O(size) time.abcdenullfirstNode

اسلاید 10: زنجيره مرتب اعضا بر اساس کليد به صورت صعودي مرتب شده اند. get(theKey) O(size) time put(theKey, theElement) O(size) براي تشخيص دادن کليد تکراري و , O(1) براي افزودن کليد به سمت راست آرايه.ABCDEnullfirstNode

اسلاید 11: زنجيره مرتباعضا بر اساس کليد به صورت صعودي مرتب شده اندABCDEnullfirstNode remove(theKey) O(size) time.چگونه مي توان در ليست هاي پيوندي هم جستجوي لگاريتمي انجام داد ؟

اسلاید 12: بحث و بررسيلغت نامه ساختاري براي نگهداري رکوردهاي اطلاعاتي استدر اغلب برنامه ها مانند كامپايلرها و پردازش متن كاربرد زيادي داردبنابراين هزينه عمليات اين ساختار داده بايد تا حد ممكن كم شودزمان اجراي عمليات حذف ، اضافه كردن و جستجوي لغت نامه از خطي يا لگاريتمي استپياده سازي هاي مختلف برخي عمليات را با هزينه كمتري نسبت به ديگر پياده سازي ها انجام مي دهندهزينه افزودن به آرايه نامرتب O(1)‌ است اما همين هزينه براي ليست مرتب O(Size) است ؟ايده ال ما اين است كه هزينه عمليات مختلف حذف روي لغت نامه ها را به O(1) ‌ كاهش دهيم .

اسلاید 13: Symbol Tableبرنامه نويسان مي توانند طبق قواعد زبان، متغيرها را به دلخواه نامگذاري کنندکامپايلر براي اختصاص حافظه و مديريت متغيرها، آنها را در جدولي به نام Symbol Table نگهداري مي کنداين جدول نمونه اي از ساختار داده Dictionary است.دسترسي به اين جدول از مرتبه Θ(N) است. براي دسترسي Θ(1) لازم است آرايه هاي خيلي بزرگ تعريف کنيماعداد صحيح: 65536رشته ها: بيشتر از اين مقدار

اسلاید 14: Symbol Tableكامپايلر از اين جدول براي نگهداري و مديريتمتغيرها و علايم تعريف شده در برنامه ها استفاده مي كندKey[X]RecordXdata fieldsهر Symbol Table شامل مجموعه اي از ركوردها مثل x استSymbol Table ADTClass SymbolTable{Records[1..N]//Operations:Insert(X:Record)Delete(X:Record)Search(K:key)}

اسلاید 15: HashingHashing روشي براي دسترسي به اعضاي آرايه هايي مثل Symbol Table است که از مرتبه Θ(1) استVariable Name(String)Index Generator (Hash Function)K(Integer)62005500454313028512500100OffsetIndexتابع Hashing تابعي معين (Deterministic) است!

اسلاید 16: دسترسي مستقيمفرض كنيد كليد ركوردها اعدادي در بازه 0..m-1 باشندآرايه اي m عضويT[0..m-1] را مي توان ساخت: T[k] = x if key(x)=k T[k] = nil otherwise Complexity: Θ(1)مساله: اگر دامنه كليدها بزرگ باشد ...؟مثلا اعداد صحيح !

اسلاید 17: راه حلتعريف تابع Hash كه مجموعه كليدها را به مجموعه انديسها ترجمه مي كند:مساله جديد: اگر دو كليد به يك مكان ترجمه شوند؛ برخورد اتفاق مي افتدCollision

اسلاید 18: حل برخورد با ليست پيونديبدترين حالتهمه كليدها به يك محل نگاشت شوند:دسترسي: Θ(n)

اسلاید 19: جستجوي يك ركورداگر n كليد داشته باشيم و آرايه m عضوي باشد و تابع نگاشت يكنواخت باشد:a = n /m = load factor  كليد به ازاي هر خانه آرايه Θ(1 + a ) : هزينه جستجوي ناموفق!Θ(1) : يافتن محل كليدΘ(a) : يافتن ركورد در ليستif a = O(1)  Θ(1) = هزينه جستجوي ناموفقهزينه جستجوي موفق هم در نهايت، همين اندازه است: Θ(1+a)

اسلاید 20: انتخاب تابع Hashنگاشت يكنواخت كليدها به خانه هاي آرايهعدم حساسيت به تركيب خاص ركوردهاي وروديquicksort را به خاطر بياوريد!روش تقسيم:h(k) = k mod m نگاشت كليدهاي k به 0..m-1نگاشت يكنواخت 1..kاگر m=2r باشد، تابع Hash ، به r بيت كم ارزش بستگي دارد!

اسلاید 21: انتخاب تابع Hashm را طوري انتخاب كنيد كه عددي اول باشدm را عددي نزديك تواني از 2 يا 10 انتخاب نكنيد!گرچه الگوريتمهاي تقسيم و حل با آرايه هايي كه طول آنها عدد اول باشد خوب كار نمي كنند؛ در اينجا چنين انتخابي لازم استروش ضربh(k) = ⌊ m (kA - ⌊kA⌋) ⌋ . , 0 < A < 1 پياده سازي سريع روش ضرببا استفاده از عملگرهاي شيفت، اين تابع پياده سازي سريعي دارد

اسلاید 22: پياده سازي روش ضربعملگرهاي شيفت بيت11101101 >> 1 = 01110110  shr(x,n) == x /2n11101101 << 1 = 11011010 shl(x,n) == x * 2n

اسلاید 23: پياده سازي روش ضرباگر اعداد صحيح مورد استفاده در کامپيوتر w‌ بيتي و m =2p باشد.و k يك عدد W بيتي و عدد اعشاري A به شكل A =S/2W باشد كه در آن S‌ يك عدد W‌بيتي استبه زبان ساده ، A‌عددي به فرم 1/2, 3/4, 1/8, 7/16,… باشد[KA] =[KS/2W] = [KS >> W ]f= KA – [KA] = (KS >> w) – [KS >> w] = fractional wbitse.g. 0.1110101 f * m = f * 2p = f << p  select p bits

اسلاید 24: حل برخورد با آدرس دهي بازآدرس دهي باز: به جاي استفاده از ليست پيوندي، از خود آرايه براي نگهداري رکوردهاي برخوردي استفاده مي شودبراي افزودن رکوردي جديد؛ ابتدا محلي خالي در آرايه پيدا مي شود و رکورد جديد در اين محل جاي مي گيردتابع افزودن رکورد جديد ، علاوه بر کليد يک پارامتر ديگر به نام Probe Number هم داردh: U * { 0 , 1 , …, m -1}  {0, 1, … , m-1}مجموعه {h(k,0), h(k,1) , …, h(k,m-1)} بايد ترکيبي از مجموعه {0..m-1} ‌باشدبه زبان رياضي: تابع Hash روي مجموعه {0..M-1} بسته باشد

اسلاید 25: مثال Open Addressing

اسلاید 26: مثال Open Addressing

اسلاید 27: مثال Open Addressing

اسلاید 28: جستجو با Open Addressingعمل جستجو از همين روش تابع افزودن، براي پيدا کردن رکورد مورد نظر استفاده مي کند

اسلاید 29: روشهاي Probing Linear : h(k ,i ) = (h’(k) + i ) mod mPrimary Clustering Problemافزايش زمان متوسط جستجوي رکوردهاm distinct probe seq.Quadratic:h(k,i)= (hi(k) + c1 i + c2 i2) mod mSecondary Clusteringm distinct probe seq.Double Hashing:h(k, i) = (h1(k) + ih2(k)) mod mSemi-Random Behavior m2 distinct probe seq.

اسلاید 30: آناليز Open Addressingn = Number of records to be storedm = size of hash table (hash array)a = n/m = load factorExpected number of probes = 1 / (1- a)if a = 0.5  E(probes) = 2if a = 0.9  E(probes) = 10

اسلاید 31: Perfect Hashingهمانند Randomized Quick sort‌تابع hash‌را ازبين مجموعه اي از توابع معين به صورت تصادفي انتخاب کنيدافزايش کارايي متوسط الگوريتمورودي خاصي از رکوردها در اغلب موارد منجر به بدترين حالت نمي شود

اسلاید 32: درهم سازي مجدد Re-HashingRecordsDoubleSizedNew Hash FunctionHashاگر جدول درهم سازي ، پر شود؛ جدول بزرگتري ساخته مي شود. سپس با استفاده از تابع جديد درهم سازي ركوردهاي موجود در حافظه قبلي و همچنين ركوردهاي جديد به اين جدول منتقل مي شونددرهم سازي مجدد عمل هزينه بري است؛ ازهمان ابتدا حافظه بزرگتري استفاده كنيدسعي كنيد هميشه load factor ‌كمتر از 20 درصد باشد

اسلاید 33: توابع Hash پيشرفته شبكه هاي عصبيتخمين توابع نگاشت فضاهاي برداريتوليد تابع Hashing با روشهاي تكاملي Genetic Programming

اسلاید 34: تمرينيک ADT ‌ براي نگهداري رکوردهايي تعريف کنيد که کليد رکوردها، رشته حرفي باشد؛ چه تابع Hashing ‌پيشنهاد مي کنيد ؟ با استفاده از روش Open addressing ؛ الگوريتمهاي حذف، اضافه و جستجو کردن در جدول رکوردها را بنويسيد.class StringHashTable{Record T[0..m-1] ;void insertRecord(Record r) ;void deleteRecord(Record r) ;