15331

15331

ارائه‌ي روشي جهت ساخت و استفاده‌ي نمايه‌سازي معكوس پويا در موتورهاي جستجو

كارشناسي ارشد

نرم افزار

اسفند ماه1393

اسفند ماه1393

دكتر حسن نادري

كامپيوتر

چكيده امروزه مباحث زيادي در مورد حجم وسيع اطلاعاتي كه به صورت پويا و لحظه¬اي در حال افزايش و تغيير هستند مطرح است كه از جمله‌ي اين بحث‌ها مي‌توان به انجام عمليات جست‌وجو در ميان اسناد اشاره كرد. موتورهاي جست¬وجوي متنييكي از كارآمدترين ابزارهاي موجود براي جست¬وجو در حجم زياد از اطلاعات است. كارآيي بالاي اين موتورها بدليل استفاده از ساختمان¬داده¬ي " نمايه¬ي معكوس" در قلب آنها است. سرعت اين نمايه¬ها وابسته به حجم داده¬اي است كه در خود ذخيره كرده¬اند. از اين رو محققين سعي در يافتن روش¬هايي براي كاهش حجم اين نمايه¬ها هستند تا به وسيله¬ي آن بتوانند سرعت موتورهاي جست¬وجو را افزايش دهند. تحقيقات جديد انجام شده نشان مي¬دهد كه يافتن ترتيب مناسبي از اسناد براي تخصيص شناسه¬ي جديد به آنها مي¬تواند حجم نمايه¬ي معكوس را تا حد زيادي كاهش دهد. در اين پايان¬نامه ابتدا يك مدل جديد براي نمايش مجموعه اسناد در قالب يك گراف دوبخشي ارائه شده است. هر يال از اين گراف متناظر با يك پستينگ از نمايه¬ي معكوس است و وزن آن برابر حجمي است كه آن پستينگ بر روي ديسك اشغال كرده است. با مدل ارائه شده مسأله¬ي شناسه¬گذاري مجدد اسناد به مسآله¬ي برچسب گذاري در نظريه گراف¬ها تبديل مي¬شود. پس از آن الگوريتمي ارائه شده است كه با تخصيص شناسه¬ي جديد به رأس¬هاي گراف، مجموع وزن يال¬هاي گراف را كاهش مي¬دهد. طبيعتاً با كاهش مجموع وزن يال¬ها، حجم نمايه¬ي متناظر با آن نيز كاهش مي¬يابد. بدليل تعداد بالاي رأس¬ها و يال-هاي گراف موردنظر، تعداد پردازش¬هاي لازم براي يافتن شناسه¬هاي جديد بسيار زياد است. براي كاهش تعداد پردازش¬ها و متناسب با آن كاهش زمان اجراي الگوريتم ارائه شده، يك الگوريتم خلاصه¬سازي گراف نيز ارائه شده است. در اين الگوريتم رأس¬هايي از گراف كه تأثير زيادي در عمليات شناسه¬گذاري ندارند از گراف حذف شده و در نتيجه سرعت اجراي الگوريتم بالاتر مي¬رود. نتايج حاصل از پياده¬سازي اين روش و نمودارهاي ارائه شده نشان مي¬دهد كه با تخصيص مجدد شناسه به اسناد حجم نمايه¬ي معكوس را مي¬توان بين 15% تا 45% كاهش داد. همچنين با اجراي اين الگوريتم بر روي نمايه¬ي معكوس پويا مي¬توان حجم نمايه¬ي نهايي را تا 30% كاهش داد.كه اين امر تأثير مستقيم در بالا رفتن سرعت بازيابي اطلاعات در نمايه¬ي معكوس دارد. واژه‌هاي كليدي:نمايه ي معكوس، فشرده سازي، برچسب گذاري گراف، شناسه گذاري مجدد اسناد