11301

11301

الگوريتمي جديد براي فشرده‌سازي شاخص‌هاي معكوس در موتورهاي جستجو

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

كامپيوتر گرايش نرم¬افزار

دي ماه 1391

دي ماه 1391

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

چكيده همگام با رشد روزافزون اطلاعات موجود در وب، روز به روز بر اهميت موتورهاي جستجو افزوده مي‌شود. بر هيچ كس پوشيده نيست كه دنياي وب بدون موتورهاي جستجو دنياي بسيار كوچكي خواهد بود. از طرفي تمام موتورهاي جستجو با دو دسته مشكل كارايي و كيفيت مواجه هستند كه با افزايش ميزان اطلاعات موجود در وب، بر شدت اين مشكلات افزوده مي‌شود. در موتورهاي جستجو؛كارآيي به معني ارائه‌ي پاسخ به پرس‌وجوي كاربر در كوتاه‌ترين زمان ممكن است. در صورتي كه كيفيت به معني ارائه‌ي پاسخ‌هاي درست و مرتبط با پرس‌وجوي كاربران است. موتورهاي جستجو براي غلبه بر مشكلات كيفيت از روش‌هاي مختلفي مانند شخصي‌سازي و الگوريتم‌هاي تحليل پيوند استفاده مي‌كنند. اما براي حل مشكلات كارايي، مفاهيم جديدي مانند سبك برنامه‌نويسي نگاشت-كاهش و جدول بزرگ توسط موتورهاي جستجو مطرح شده و به كار گرفته مي‌شود. يكي ديگر از روشهايي كه موتورهاي جستجو براي حل مشكل كارايي از آن بهره مي‌گيرند، استفاده از الگوريتم‌هاي فشرده‌سازي است. اين الگوريتم‌ها در قسمت‌هاي مختلفي از يك موتور جستجو مانند ذخيره‌سازي اسناد و شاخص‌هاي معكوس به كار گرفته مي‌شوند. اين پايان‌نامه يك الگوريتم كاملاً جديد و با قابليت پيكربندي زياد رابراي فشرده‌سازي شاخص‌هاي معكوس ارائه مي¬كند. به منظور ارزيابي اين الگوريتم، آن را با چند الگوريتم بسيار معروف ديگري كه در اين حوزه وجود دارند مقايسه كرده‌ايم. نتايج حاصل از ارزيابي¬ها نشان داد كه نرخ فشردهسازي اين الگوريتم در حالتي كه از بهترين پيكربندي استفاده شود 1.6 واحد بيشتر از بهترين الگوريتم مورد مقايسه است. همچنين سرعت فشرده¬سازي اين الگوريتم تقريباً دو برابر بهتر از دو الگوريتم موردِ مقايسه¬ي ديگر بوده است. اين در حالي است كه بنا به دلايلي سرعت بازگشايي آن كمتر از الگوريتم¬هاي ديگر بوده است. واژه¬هاي كليدي : موتورهاي جستجو، شاخص¬هاي معكوس، فشرده‌سازي شاخص‌هاي معكوس، بازيابي اطلاعات از داده‌هاي حجيم.