تحقیق در مورد آناتومی یک موتور جستجو وب فوق متنی در مقیاس وسیع

بخشی از مقاله

آناتومي يك موتور جستجو وب فوق متني در مقياس وسيع

خلاصه:
در اين بخش، به گوگل خواهم پرداخت، يك نمونة اصلي از يك موتور جستجوي در مقياس وسيع كه استفاده وسيعي از ساختار اراده شده در فوق متني مي كند. گوگل براي جستجو و يافتن (Crawl) و شاخص بندي وب به طور مؤثر و توليد نتايج هرچه رضايت بخش تر نسبت به سيستم هاي موجود طراحي شده است. اين نمونه اصلي با پايگاه داده اي متشكل متن و فوق پيوند كامل 24 ميليون صفحه در http://google.standard.edi/ موجود مي باشد. مهندسي يك موتور جستجو يك وظيفة چالش آور است. موتورهاي جستجو دهها تا صدها ميليون صفحه وب متشكل از تعداد قابل ملاحظه اي موضوعهاي متفاوت را شاخص بندي مي كنند و پاسخ گوي دهها ميليون پرس و جو به صورت روزانه هستند. بر خلاف اهميت بالاي موتورهاي جستجوي برروي وب تحقيقات آكادميك بسيار اندكي برروي آنها صورت گرفته است (در كشور عزيز ما دقيقاً هيچ مطالعه و تحقيقي صورت نگرفته است). علاوه بر اين به دليل سرعت پيشرفت تكنولوژي وب، امروزه ساخت يك موتور جستجو مسبت به سه سال پيش بسيار متفاوت است. اين بخش به بررسي و توصيف عمقي اين موتور جستجوي وب در مقياس وسيع مي پردازد. جداي از مشكلات تغيير مقياس تكنيكهاي جستجوي قديمي داده با اين وسعت، چالشهاي تكنيكي جديدي در زمينه استفاده از اطلاعات اضافي ارائه شده در فوق متن براي توليد نتايج جستجوي بوجود آمده است. اين بخش به اين كه چگونه مي توان يك سيستم در مقياس وسيع عملي كه بتواند اطلاعات اضافي ارائه شده در فقو متن را استخراج كند را توليد كرد، پاسخ خواهد گفت. همچنين ما به اين مشكل كه چگونه مي توان با مجموعه هاي فوق متن كنترل نشده (هر كسي مي تواند هر چه خواست بنيسد) كنار آمد، نيز دقت خواهيم كرد.
1. معرفي
وب چالشهاي جديدي براي بازيابي اطلاعات ايجاد مي كند. حجم اطلاعات موجود برروي وب به سرعت در حال افزايش است و به همان نسبت تعداد كاربران جديد كه در جستجوي وب بي تجربه هستند افزايش مي يابد. مردمي كه احتمالاً وب را از طريق گراف پيوند آن مرور مي كنند، اغلب كار خود را با شاخصهاي ذخيره شده با كيفيت بالاي انساني مانند ياهو! يا موتورهاي جستجو شروع مي كنند. ليتهاس ذخيره و نگهداري شده توسط انساني موضوعهاي معروف را به طور موثري پوشش مي دهند اما شخصي بودن، گران و پرهزينه بودن براي ساخت و نگهداري، كندي در پيشرفت و ناتواني در پوشش موضوعهاي مبهم و پيچيده از عيبتهاي عمده آنها محسوب مي شود. موتورهاي جستجو بر پاية هم خواني كلمات كليدي معمولاً نتيج را با كيفيت بسيار پايين برمي گرداند. براي بهتر شدن شرايط، بعضي شركتهاي تبليغاتاي تلاش وسيعي براي بدست آوردن نظر مردم از طريق گمراه كردن موتورهاي جستجوي اتوماتيك مي كنند. اقايان سرگي برين و لاورنس پيج موتور جستجوي در مقياس وسيعي ساخته اند كه به تعداد زيادي از مشكلات سيستم هاي موجود پرداخته است. و آن استفاده وسيعي از اين ساختمام ارائه شده در فوق متن مي كند به منظور فراهم كردن نتايج جستجوي با كيفيت بالاتر، اسيم اين سيستم، گوگل، انتخاب شده است. زيرا گوگل تلفظ معمول googol يا 10100 است و بسيار مناسب هدف ما براي ساختن يك موتور جستجوي بسيار در مقياس وسيع است.
1.1 موتورهاي جستجوي وب – گسترش يافتن: 1994-2001
تكنولوژي موتورهاي جستجو بايد به ميزان زيادي تغيير پيدا مي كرد تا بتواند هماهنگي خود را با گسترش وب حفظ كند. در 1994، يكي از اولين موتورهاي جستجوي وب يعمي كرم وب گسترة جهاني (WWWW) شاخصي از000/110 صفحه وب و اسناد در دسترس وب داشت. از نوامبر 1998 موتورهاي جستجوي برتر ادعاي شاخص بندي از 2 ميليون (WebCrawler) تا 100 ميليون (از (Search Engine Watch صفحه وب و سند را داشتند. قابل پيش بيني است كه تا سال 2001 يك شاخص جامع از وب شامل بيش از دو ميليارد سند باشد. در همان زمان تعداد پرس و جوهايي كه موتورهاي جستجو اداره مي كنند به طور شگفت آوري افزايش مي يابد. در ماه مارس و آوريل 1994، كرم وب گستره جهاني (wwww) به طور روزانه حدوداً 1500 پرس و جو را دريافت مي كرد. در ماه نوامبر 1998، آلتاويستا (Altavista) اظهار داشت كه روزانه حدود 20 ميليون پرس و جو را اداره مي كند. با افزايش تعداد كاربران وب و سيستمهاي اتوماتيك كه از موتورهاي جستجو پرس و جو مي كنند به نظر مي رسد كه تا سال 2001 موتورهاي جستجو صدها ميليون پرس و جو را اداره خواهند كرد. هدف سيستم گوگل توجه به بسياري از مشكلات كيفيتي و مقياس پذيري است كه با عرضه تكنولوژي موتورهاي جستجوي اينترنتي به ميزان زيادي گسترش يافته اند.
1.2.1 گوگل: تغيير دادن وب
اين موتور جستجوايي كه در سطح وب امروز باشد چالشهاي بسياري را پديد مي آورد. تكنولوژي جستجو و يافتن سريع براي جمع آوري و به روز رساني سندهاي وب لازمي مي باشد. فضاي ذخيره سازي بهيد به طور كارآمدي براي ذخيره شاخصها و به طور اختياري خود سندها بكار گرفته شود. سيستم شاخص بندي بايد صدها گيگا بايت داده را به طور كارآمد پردازش كند. پرس و جحوها بايد به سرعت اداره شوند (با نرح صدها تا هزاران پرس و جو در ثانيه).
همان گونه كه وب گسترش مي يابد اين وظايف نيز به طور صعودي مشكل مي شوند. اگرچه عملكرد سخت افزار و هزينه ها به طور چشمگيري بهبود يافته اند و تا حدي از اين سختي را تعديل كرده اند. با اين وجود تعدادي استثناي قابل اشاره نيز مانند زمان استوانه يابي ديسك و قابليت ادامه كار در شرايط غيرمنتظره سيستم عامل وجود دارند. در طراحي گوگل هر دو مسئلهع گسترش وب و تغييرات تكنولوژيك در نظر گرفته شده اند. گ.گل براي تغيير مقياس دادن مجموعه داده ها به خوبي طراحي شده است و از فضاي ذخيره سازي به طور مؤثري استفاده مي كند. ساختمان داده هاي آن براي دسترسي سريع بهينه سازي شده اند (به بخش 4.2 نگاه كنيد). علاوه بر اين، هزينه شاخص بندي و ذخيره متن يا HTML نهايتاً بستگي نمسبي به ميزان در دسترسي آنها دارد و اين بر تغيير مقياس منتاسب براي سيستم هاي متمركز شده مانند گوگل تاثيرگذار است.
.3.1 اهداف طراحي
.1.3.1 كيفيت جستجوي بهينه شده
هدف اصلي در طراحي گوگل بهينه كردنم موتورهاي جستجوي وب است. در سال 1994، بعضي از مردم تصور مي كردند يك شاخص جستجوي كامل امكان يافتن هر چيزي را ميسر مي سازد. بر طبق مقالة بهترينهاي وب 1994 – پيمايشگرها و «بهترين سرويس پيمايشي بايد امكان يافتن تقريباً هر چيزي را به آساني فراهم كند (هنگامي كه تمام داده ها وارد شدند)». اگرچه وب 1999 كاملاً متفاوت است. هر كسي كه اخيراً از يك موتور جستجو استفاده كرده باشد به سادگي در مي يابد كه كامل بودن شاخص تنها عامل مؤثر بر كيفيت نتايج جستجو نمي باشد. «نتايج آشغال» اغلب تمام نتايج مورد علاقه كاربر را خراب مي كنند. در حقيقت در نوامبر 1999، تنها يكي از چهار مكوتور تجاري برتر نتايج را خودش مي يابد (در پاسخ در ده نتيجه برتر، صفحه جستجو شده خودش را برمي رگداند). يكي از دلايل اصلي اين مشكل اين است كه تعداد سندهاي موجود در شاخصها به دلايل روشني افزايش پيدا كرده اند اما توانايي كاربر بريا يافتن و نگاه كردن اسناد پيشرفت نكرده است. مردم هنوز خواستار نتيجه اول جستجو هستند. به همين دليل، همان طور كهئ اندازة مجموعه گسترش مي يابد، به ابزارهايي كه دقت بسيار بالايي دارند نياز بيشتري پيدا مي شود (تعداد اسناد مربوط و مناسب برگردانده شده، در بين ده نتيجه برتر مي آيد). در واقع، گوگل مي خواهد مفهوم «مناسب» فقط شامل بهترين اسناد باشد درحاليكه ممكن است، ده ها هزار سند تقيرباً وجود داشته باشد. خوش بيني هاي جديدي در زمينه بهبود عملكرد موتورهاي جستجو و ساير برنامه هاي اجرايي با استفاده بيشتر از اطلاعات فوق متني بوجود آمده است
[Kleinberg 98]. علي الخصوص، ساختمان پيوندها [Page 98] و نوشته پيوندها اطلاعات زيادي براي قضاوت مناسب و فيلترينگ كيفيت فراهم مي كند. گوگل از هر دوي ساختمان پيوند و متن انكر استفاده مي كند.
.2.3.1 تحقيقات موتور جستجوي آكادميك
جداي از گسترش بسيار زياد، وب به طور افزايشي در طول زمان حالت تجاري به خود گرفته است، در سال 1993، %5/1 از سرويس دهندگان وب بر دامنه .com قرار داشتند. اين مقدار در سال 1998 به %60 رسيد. در همان زمان، موتورهاي جستجو از حوزة آكادميك به تجاري كوچ كردند. تا امروز اغلب پيشرفتهاي موتورهاي جستجو در شركتهايي صورت مي گيرد كه حداقل ميزان انتشار جزئيات را دارند. اين باعث مي شود تكنولوژي موتور جستجو تا حد زيادي مثل جادوي سياه مخفي باقي بماند و گرايش تبليغاتي پيدا كند. با گكوگل، سعي شده است تا پيشرفت و فهم بيشتري در قلمرو آكادميك صورت گيرد.
يكي ديگر از اهداف طراحي ساخت سيستمهايي بود كه تعداد قابل قبولي از مردم مي توانند استفاده كنند. قابليت كاربري در طراحي بسيار مهم بوده است زيرا بنظر مي آيد كه اغلب تحقيقات جالب شامل تأثير استفاده گسترده از سيستمهاي مدرن وب در دسترس هستند مي باشد. براي مثال، هر روز دهها ميليون جستجو اجرا مي شوند. اگرچه، بدست آوردن اين داده ها مشكل است، بيشتر به اين دليل كه با توجه به جوانب اقتصادي اين داده ها ارزشمند هستند.
هدف نهايي طراحي گوگل ساخت يك معماري كه قابليت پشتيباني از فعاليتهاي تحقيق نوظهور برردي داده هاي در مقياس وسيع وب را داشته بوده است. براي پشتيباني از استانداردهاي تحقيقاتي نوول، گ.گل تمام اسناد فعلي را كه جستجو مي كند و مي يابد به صورن فشرده ذخيره مي كند. يكي از اهداف اصلي طراحي گوگل بوجود آوردن محيطي بود تا ساير محققات بتوانند به سرعت وارد شده، قسمت بزرگي از وب را پردازش كرئه و نتايج جالب توجهي را توليد كنند كه در غير اين صورت تولدي آنها غير ممكن باشد. در مدت زمان كوتاهي سيستم به جايي رسيد كه تعداد زيادي مقاله و تحقيق با استفاده از پايگاه داده گ.گل ايجاد شده بودند و بسياري ديگر، در دست اقدام هستند. هدف ديگر بوجود آوردن يك محيط لابراتوار مانند بود كه محققان و حتي دانشجويان بتوانند تجربيات جالب و پيشنهادات مفيدي برروي داده هاي وب در مقياس وسيع گوگل داشته باشند.
2. ويژگيهاي سيستم
موتور جستجوي گوگل دو ويژگي مهم دارد كه به توليد نتايج با وضوح و دقت بالا كمك مي كند. اول، گوگل از ساختار پيوند وب براي محاسبه رتبه بندي كيفيت براي هر صفحه وب استفاده مي كند. اين رتبه بندي، رتبه صفحه ناميده مي شود. دوم، گوگل از پيوند براي بهبود نتايج جستجو بهره مي گيرد.
1.2- رتبه صفحه: نظم بخشيدن به وب
گراف فراخواني (پيوند) وب يك منبع بسيار مهم است كه توسط موتورهاي جستجوي وب كنوني بي استفاده مانده است. گوگل نقشه هايي شامل بيش از يك ميليارد از اين فقو پيوندها كه نمونه اي چشمگير از كل هسته را بوجود آورده است. اين نقشه ها اجازه محاسبه سريع «رتبه صفحه» يك صفحه وب را مي دهند، يك معيار عيني كه اهميت اشاره به آن برابر با تصوير ذهني مردم از اهميت است. بخاطر اين تطابق، رتبه يك صفحه راه عالي براي اولويت دادن به نتايج جستجوهاي كلمه كليدي در وب. براي اغلب موضوعهاي معروف يك نوشته ساده متناظر با جستجحو است به اين معني كه محدود به تيترهاي صفحات باشد يعني زماني كه نتايج جتوسط رتبه بندي صفحه اولويت بندي مي شوند به طور قابل تحسيني اجرا مي شوند. براي جستجوهاي كاملاً متني نيز در سيستم اصلي گوگل رتبه بندي صفحه كمك قابل ملاحظه اي مي كند.
1.2.2. توصيف محاسبه رتبه صفحه
منابع نوشته آكادميك در وب عمدتاً از طريق شمارش نوشته ها يا پيوندهاي بازگشتي به يك صفحه خاص به كار گرفته شده اند. اين كار تقريبي از اهميت يا كيفيت صفحه به دست مي دهد. رتبه بندي صفحه اين مفهوم را از طريق نرمال سازي بوسيله تعداد پيوندها در يك صفحه و نه شمارش پيوندها به طور مساوي در تمام صفحات، گسترش مي دهد، رتبه بندي صفحه به صورت زير تعريف مي شود:
در نظر بگيريد كه صفحات TN…T1 به صفحه a اشاره مي كند (يعني منبع هستند). پارامتر d يك گامل محدود ساز است كه مي تواند بين 0 تا 1 تنظيم شود و اغلب d با مقدار 0.85 تنظيم مي شود. توضيحات بيشتر در مورد d در بخش بعيد اارئه مي شود. بنابراين C(A) به عنوان تعداد صفحاتي كه از صفحه A خارج مي شوند، تعريف مي شود. رتبه صفحه A به صورت زير داده مي شود.
RR (A)=)1-d)+d(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))
توجه كنيد كه رتبه هاي صفحه يك توضيح احتمالي برروي صفحات مي دهد، بنابراين مجموع رتبه هاي تمام صفحات وب يك (1) خواهد بود.
رتبه صفحه يا PR(a) مي تواند بوسيلة يك الگوريتم تكرار ساده محاسبه شود و با بردار خاص اصلي از ماتريس پيوند نرمال شده از وب تطابق داده شود. بنابراين، رتبه بندي صفحه 26 ميليون صفحه وب مي تواند در كمتر از چند ساعت برروي يك ايستگاه كاري متوسط محاسبه شود. بسياري جزئيات ديگري هستند كه از محدوده اين مقاله خارج است.
2.1.2. توجيه شهودي
رتبه صفحه مي تواند به عنوان يك مدل از رفتار عملكرد كاربر فرض شود. فرض مي كنيم كه يه «مرورگر تصادفي» وجود دارد چكه يك صفحه به طور تصادفي به او داده مي شود و او برروي پيوندها كليك مي كند و هيچگاه دكمه (BACK) را نمي زند اما سرانجام خسته مي شود و از يك صفحه تصادفي ديگر كار خود را ادامه مي دهد. احتمال اينكه اين مرورگر تصادفي يك صفحه را ملاقات كند رتبه آن صفحه مي باشد و d يعني عامل محدودساز احتمال اين است كه آن «مرورگر تصادفي» از هر نسخهع خسته شود و تقاضاي يك صفحه تصادفي ديگر بكند. تفاوت مهم اين است كه عامل محدودساز d را تنها يك صفحه، يا گروهي از صفحات اضافه كنيم. اين كار امكان شخصي سازي را ايجاد مي كند و تقريباً گمراه كردن عمدي سيستم به منظور بدست آوردن يك رتبه بالاتر را غيرممكن مي سازد. گوگل انشعابات متعدد ديگري براي رتبه بندي صفحه دارد كه از محدوده اين نوشته خارج است.
توجيه شهودي ديگر اين است كه يك صفحه مي توان يك رتبه صفحه بالا داشته باشد اگر صفحات زيادي به آن اشاره كنند يا صفحاتي وجود دارند كه به آن اشاره مي كنند و خود رتبه صفحه بالايي دارند. به ضوح، صفحاتي كه به خوبي از جاهاي محتلفي از وب تكرار مي شوند ارزش نگاه كردن دارند. همچنين، صفحاتي كه ممكن است يك احضار از طرف جايي مانند صفحه خانگي ياهو! داشته باشند عموماً ارزش نگاه كردن دارند. اگر يك صفحه كيفيت بالايي نداشته باشد يا يك پيوند شكسته شده باشد به احتمال زياد صفحه خانگي ياهو! به آن پيوند نمي شود. ضمناً رتبه بندي صفحه هر دوي اين حالات و حالات ديگر را با وزن دهي تبليغي به طور بازگشتي از طريق ساختار پيوند وب انجام مي دهد.
.2.2 متن انكر (Anchor)
در موتور جستجوي گوگل با نوشتة پوندها به شيوه هاي خاصي برخورد مي شود. اغلب موتورهاي جستجو نوشته يك پويند را به صفحه اي كه پيوند در آن است مربوط مي سازند. گ.گل علاوه بر اين نوشته پيوند را به صفحه اي كه به آن اشاره مي كند نميز مربوط مي سازد. اين كار منافع زيادي دارد. اول، انكرها اغلب توصيف دقيق تري از صفحات وب نسبت به خود صفحات ارائه مي دهند. دوم، انكرها ممكن است براي سندهايي كه نمي توانند توسط موتورهاي جستجوي بر پايه متن شاخص بندي شوند وجود داشته باشندذ. مانند عكسها، برنامه ها، و پايگاه ها داده. اين كار در حقيقت امكان بازگرداندن صفحاتي را كه عمل جستجو و دانلود (Crawl) برروي آنها صورت نگرفته است را مي دهد. توجه كنيد كه صفحاتي كه عمل جستجو و دانلود برروي آنها صورت نگرفته است مي توانند ايجاد مشكل كنند از آنجا كه آنها هيچ گاه براي صحت و اعتبار منطقي قبل از برگردانده شدن به كاربر چك نمي شود. در اين حالت موتور جستجو حتي مي تواند صفحه اي را كه اصلاً وجود ندارد اما فوق پيوندها به آن اشاره مي كنند بازگرداند. اگرچه امكان دسته بندي نتايج وجوود دارد درنتيجه اين مشكل خاص به ندرت اتفاق مي افند.
ايده متن انكر تبليغاتي به صفحه اي كه به آن باز مي گرئئ توسط كرم وب گسترده جهاني (WWWW) تحقق پيدا كرد. زيرا اين متن به جستجوي اطلاعات غيرمتني و گسترش دامنه جستجو با سندهاي دانلودي كمتر كمك مي كند. گوگل به اين دليل از انكر تبليغاتي استفاده مي كند كه متن انكر مي تواند در فراهم كردن كيفيت بهتر نتايج كمك كند. استفاده مفيد از متن انكه به دليل حجم بالاي كه بايد پردازش شود از نظر تكنيكي مشكل است. در مجموعه جستوجو و يافته شده حال حاضر گوگل كه شامل 240 ميليون صفحه است بيش از دو و نيم ميليارد انكر شاخص بندي شده وجود دارد.
.3.2 ويژگيهاي ديگر
جدار از رتبه صفحه (PageRank) و استفاده از متن انكر، گكوگل ويژگيهاي متعدد ديگري دارد. اول، اطلاعات مكاني تمام بهترينها (Hits) را دارد و بنابراين استفاده وسيعي از اطلاعات مجاورتي در جستجو مي كند. دوم، گوگل جزئيات بعضي بخشهاي ديداري مانند اندازه فونتهاي كلمات را نگهداري مي كند. به كلماتي كه بزرگتر نوشته شده اند يا پررنگتر هستند وزن بالاتري داده مي شود. سوم، HTML كل و خام هر ضفحه در انباره موجود مي باشد.
3. كارهاي مربوطه
تحقيقات جستجو برروي وب تاريخچه كوتاه و موجزي دارد. كرم وب جهاني (wwww) يكي از اولين موتورهاي جستجو وب بوده است. اين حركت متعاقباً توسط موتورهاي جستجوي آكادميك متعددي دنبال شد كه بسياري از آنها هم اكنون تبديل به شركتهاي تجاري شده اند. در مقايسه با گسترش وب و اهميت موتورهاي جستجو سمدهاي اندكي در مورد موتورهاي جستجو اخير وجود دارد. به عقيده مايكل ماولدين (سرمحقق شركت Lycos)، سرويسهاي مختلف (شامل Lycos) يه سختي از جزئيات پايگاه داده هايشان محافظ مي كنند. اگرچه كار قابل توجهي برروي ويژگيهاي خاصي از موتورهاي جستجو صورت گرفته است. به خصوص كار و تحقيقي كه بيشتر نمودار است و بارز است كاري است كه برروي عمليات بعد از پردازش براي بدست آوردن نتايج در موتورهاي جستجوي تجاري فعلي صورت گرفته است و در ايجاد موتورهاي جستجوي در مقياس كوچك «شخص شده» كاربرد دار. در نهايت تحقيقات زيايد چبرروي سيستمهاي بازيافت اطلاعات صورت گرفته است به خصوص بر مجموعه هايي كه نظارت درستي بر آنها اعمال مي شود.