معماری موتورهای جستجو

صفحه 1:
معماری موتورهای جسنجو 6 ‎١‏ أ ابوالفضل آسوده ‎٠ 1390/02/18‏ 

صفحه 2:
:© (SEARCH ENGINE) game j 390 ‎٩‏ برنامه هایی که موضوعات مورد نظر کاربران را در قالب کلمات کلیدی. درون اسناد و اطلاغات موجود در اينترنت كاوش و نتايج را در قالب «آدرس محل ذخيره» عرضه میکنند. ‏# خاص منشلوره: برای جستجو در یک برنامه کاربردی(سایت) خاص ‏موتورهای جستجوی جهانی(معمول): کلیه اسناد موجود در اینترنت را بررسى مى كنند ‏سوير موتورهاى جستجو: درخواست هاى كاربران را در موتورهاى مختلف دنيا جستجو و نتايج حاصله را تركيب مى كنند 

صفحه 3:
: © انواع موتورهاى جستجو بر اساس نحوه عملكرد © مبتنی بر خزش - ۴0910656 ‎Crawler based Search‏ ‎٩‏ مبتنی بر فهرست - ۴۳0910656 56۵۲6۳ ‎Directory based‏ # با دخالت مستقیم صاحبان اسناد # به صورت درختی به زیر شاخه های مرتبط دسته بندی می شوند * برای حفظ جایگاه صاحبان اسناد باید توجه ویژه ای به کیفیت و محتوای صفحاتشان داشته باشند. * با توجه به دسته بندی هوشمندانه معمولا نتایج سودمندتری ارائه می دهند Hybrid 56۵۲6۳ ۴091۴65 - ‏ترکیبی‎ 9 

صفحه 4:
صفحات وب درحال تغییر 2 تقریبا ۲۸40 صفحات وب ۲0۲۳۰ روزانه تغییر می کنند. 0 نیمه عمر وب سایت های .10 60۳0 روز است!! ‎٩‏ مدل آماری تفییر صفحات وب از توزیع پوآسون تبعیت میکند ‎P(n),=((At)"e-*)/n!‏ ‎ ‏0 2256 صفحات اینترنتی لینک بازگشت به هسته(صفحه اصلی سایت) ندارند. 0 به هسته هایی لینک دارند که از طریق آنها قابل دسترس نیستند. ‎© ‎ 

صفحه 5:
معمارى كلى موتورهاى جستجو 1 

صفحه 6:
۰ © ماژول خزنده - 68۵۷۷۱8 ‎٩‏ وظیفه: استخراج صفحات و ذخیره آنها در انباره صفحات ‎٩‏ با یک مجموعه اولیه از ا*آلاها که در یک صف اولویت دار قرار دارد شروع می کند. ‎٩‏ پس از استخراج صفحات همزمان با ذخیره آنهاء لینک های درون آنها را برای اضافه شدن به صف تحویل ماژول کنترل کننده خزش می دهد. ‎٩‏ کنترل کننده آدرس های تکراری را از اين مجموعه حذف و بقیه را درصورت داشتن معیارهای لازم به ترتیب اولویت به انتهای صف اضافه میکند ‎ 

صفحه 7:
معبارهای اولوبت صفحات ۱0۲6۲65] 0۲۷6۳ - ‏مبتنی بر گرایشات کاربران‎ ٩ Popularity Driven - ‏مبتنی بر شهرت‎ ٩ Location Driven - ‏مبتنى بر محل قرار كرفتن صفحات‎ © 7 

صفحه 8:
INTEREST DRIVEN 0 : مجموعه فراوانی کلمات کلیدی که در درخواست های کاربران بودهه ‎Q={W,,W,,..,W,,}, W; is the relative frequency of Keyword;‏ ‎oO‏ ۳: مجموعه فراوانی کلمات کلیدی استخراج شده از یک صفحه ‎frequency of keyword, in‏ مه قذ ۱۷ بل ‎P={W’,, W’,,..,‏ ‎current page‏ ‎llell - Bow it Bo ‎WW", ‎1011۳۲ ۱۱۱ ‎PageImportance = 

صفحه 9:
1 POPULARITY DRIVEN )۱۱۳۱6 961: یکیاز رلمهای‌لندانه گبری‌شهرتصفحه. شمیش تعداد صفحاتملسنکه بسه نا ینکدادم لند. هرجه لين عداد بيشتر 

صفحه 10:
LOCATION DRIVEN ‎٩‏ فاکتورهای زیر می توانند برای مشخص کردن فاصله صفحات استفاده شوند *محل قرار گرفتن آدرس صفحه * فاصله آن تا صفحه اصلی سایت(تعداد لینک) آدرس صفحه ‏© ماهيت آدرس (60۳۰. ,/6,.» 

صفحه 11:
الگوهای کاوش ماژول خزنده ‎x‏ 60 ° © خزش و توقف - 5000 »6 ۲۵۷۷1: با شروع از یک آدرس دقیقا 6 صفحه را(به ترتیب اولویت) استخراج میکند و خارج می شود خزش و توقف با آستانه - ۲۳۳65۳۵۱0 ‎Crawl & Stop with‏ با شروع از یک آدرس تمام صفحاتی را که اولویتشان از حد آستانه بيشت است ملاقات می کند 

صفحه 12:
0 سرکشی و ذخیره مجده صفحات - 32۲8۴5۳۱ © تازه سازی یکنواخت: تمام صفحات فارغ از اينکه تغییر کرده باشند يا نه به صورت دوره ای سرکشی می شوند ‎٩‏ تازه سازی متناسب با تغییر: با فرض اينکه صفحه ای با دوره تناوب 7۱ تغییر میکند. بهترین سیاست سرزدن مجدد با همین دوره است. در اين الگوریتم ابتدا زمان ۲6۴۲65۱ به یک مقدار سریغ تنظیم می شود. (در یک روش) درصورتیکه در ‎Gul‏ بازه محتویات صفحه تغییر نکرده بود زمان ۲6۲۲۳65/۱ باضریب 0 افزوده می شود. ‎ ‎© 

صفحه 13:
pl jak poor ee ae 

صفحه 14:
معمارى كلى موتورهاى جستجو 1 

صفحه 15:
انباره ذخیره سازی - ‎OR ce REPOSITORY‏ © جالش ها ©كسترش يذيرى تا ‎(Scalability‏ يشتيبانى از دسترسى تصادفى و ترتيبى #به روز رسانی توده ای #صفحات منسوخ 

صفحه 16:
ماژول اندیس گذار - استخراج اندیس ها 1 ‎٩‏ شاخص متن ° اساختار لينك 

صفحه 17:
۰ شاخص متن ۱۱۱۸۲۶۰ 1۴۲ © پایگاه داده ای از کل کلمات ممکن در هر ادبیات به همراه اندیس صفحاتی که این کلمات در آنها به کار رفته است. ‎٩‏ سه تایی «واژه». «صفحه» و «موقعیت واژه در صفحه» و همچنین اطلاعات اضافی مانند «00161» بودن ذخیره می شود. 

صفحه 18:
1 LINK STRUCTURE - ‏ساختار لینگ‎ 2 گراف جهت داری که گره های آن صفحات و یال های آن لینکهای بین آنهاست. ‎O‏ با توجه به پیچیدگی الگوریتم های گراف ساده سازی آن اهمیت ویژه ای دارد. ‏9 ام توا برا :ساده كردن عراف از زو هی سلسله مرالبی استفاده کرد: 

صفحه 19:
رتبه بندی و تحلیل لینک 2 موتور جستجو پس از بررسی هر جستجو در میان شاخص ها با انبوهی از صفحات مواجه می شود. سوال این است که کدام صفحه باید در رتبه بالاتری قرار گیرد. ‎٩‏ برای رتبه بندی صفحات از دو مجموعه کاملا مجزای اطلاعات استفاده می شود. ‎٩‏ اطلاعات درون صفحه ‏0 اطلاعات خارج از صفحه(در صفحات دیگر) ‎‌ ‎ 

صفحه 20:
عوامل رتبه بندی درون صفحه 0 دفعات تکرار کلمات © ترتیب و مجاورت کلمات کلیدی © محل درج كلمه © كلمات كليدى تكرار شده در ‎URL‏ © يررنك بودن كلمات كليدى <meta> ‏استفاده از تگ‎ ٩ ‎٩‏ برچسب های ۵1 استفاده شده برای تصاویر ‎‌ ‎ 

صفحه 21:
ا ۳ عوامل رتبه بندى بيرون صفحه 1 © مهمترين آنها تعداد ارجاعاتى است كه از صفحات ديكر به اين صفحه شده است و اهميت صفحاتى كه به اين صفحه ارجاع داشته اند. © یکی از بهترین نمونه های این رتبه بندی الگوریتم ۳306182111 گوگل می باشد 0۵ ۵ — 8۶ 

صفحه 22:
pl jak poor ee ae 4 PAGE RANK 0 (۳11)۸: امتیاز صفحه ۸ که عددی بین صفر و یک است ° (6): تعداد کل لینکهای خارج شده از صفحه »ر © 0: ضریب میرایی اک 6000 © به طور خلاصه اين الكوريتم يا شروع از مقادير تصادفى براى 72[9ها شروع ميكند با توجه به فرمول بالا امتيازات را تصحيح ميكند تا زمانيكه كه ديكر تغييرى در مقادير 81 به وجود نيايد =@ PR(T,) =(1-d) +a) 

صفحه 23:
pl jak poor ee ae © امکان سنحی 9 ار یی که می توان موتورهای جستجو را به عنوان نماد وب دانست. پیاده سازی یک موتور جستجوی موفق علاوه بر درآمد زایی و اشتغال زایی در سطح کلان می تواند گامی به سوی توسعه یافته شدن به حساب آید. © همانگونه که دیدیم اینچنین پروژه ای عزم ملی می طلبد و با چالشهای نرم افزاری. سخت افزاری زیادی مواجه است و البته قدرت یک موتور جستجوگر با الگوریتم ها و مکانیزم های اندیس گذاری و رتبه بندی ارتباط مستقیم دارد 6 توجه به اينكه 9040 صفحات وب روزانه تغيير مى كنند يهناى باند بالا و پردازش بالای سخت افزاری لازم است. 

صفحه 24:
© تعداد صفحات وب ۵ با بررسی که در سایت ‎slass a5) WOrldwidewebsize.com‏ صفحات اندیس شده در موتورهای جستجوی دنیا را نشان می دهد) به عمل آمد به این نتجه رسیدیم که تعداد صفحات وب در سالهای اخیر کاملا قابل پیش بینی و ابت(42 میلیارد) شده است!! 

صفحه 25:
تعداد صفحات وب 12 0ee 2010 Size Google ‏سا‎ oF vetazes) 26 Feb 200049 Jul 2010 

صفحه 26:
تعداد صفحات وب 6 ny 2008 30 oe 204 ‘Size Gooule ‘urber of webpages? i Aka 3B Fe DOLL 28 Ape ot خلا > 12 مرن 0500010 

صفحه 27:
pl jak poor ee ae © امکان سنجی ۱ ‎٩‏ بی شک برای پوشش چنین پهنه ای از اطلاعات استفاده از تکنیک توزیع شدگی بار - 015۲101010۳ ناگزیر است. ‎٩‏ فرض کنیم برای انجام اين کار از 20 سرور که به صورت فیزیکی در نقاط مختلف کشور پخش شده اند استفاده می شود ‎٩‏ (با توجه به عدم نیاز به ذخیره اسناد چندرسانه ای) متوسط اندازه هر صفحه را 210 درنظر گرفتیم ‏ین انباره اطلاعاتی با حجم 84 ترابایت نیاز می باشد كه به هر سرور 5 ترابایت میرسد(کاملا ممکن و مقرون به صرفه) ‎٩‏ فرض کنیم که صفحات با دوره 5 روزه ۲6۲۲651۱ می شوند. بنابراین با تبدیل روز به ثانيه و بايت به بيت هر سرور به پهنای باند 10011005 (بدون درنظركرفتن يهناى باند لازم براى ارتباط با كاربر)نياز دارد كه ممكن به نظر می رسد. ‎° ‎ 

صفحه 28:
pl jak poor ee ae امکان سنجی ۲ ‎٩‏ تنها نكته باقی مانده قدرت پردازشی و الگوریتم های اندیس گذاری و رتبه بندی و خزش است. ‏7 در یک دید خیلی خوش بینانه (0)10 برای الگوریتم های خزش و اندیس گذاری و (0)117) برای الگوریتم رتبه بندی در نظر می گیریم. ‏9 در این میان الگوریتم رتبه بندی با رسیدن به عدد 1077*2 به هیچ عنوان قابل تحمل به نظر نمى رسد ولى با توجه به اين واقعيت كه كراف ساختار _ ‎Kad‏ دن صورث سلسله مراتبى عمل كردن) يك عراف خلوث بدانظرمى آند عدد به دست آمده خيلى دور از واقعيت مى نمايد. ‏ربا ‎ ‏به نظر می رسد که بستر سخت افزاری لازم برای این باشد و آنچه اهمیت می یابد کشف الگوریتم های بهینه ا @2 گذاری صحیح در مجامع علمی این مهم ناممکن نمی نماید. ‎ ‎ 

صفحه 29:
asudeh@ce.sharif.edu 

به نام خدا معماری موتورهای جستجو ابوالفضل آسوده 1390/02/18 موتور جستجو()SEARCH ENGINE معماری موتورهای جستجو -ابوالفضل آسوده برنامه هایی که موضوعات مورد نظر کاربران را در قالب کلمات کلیدی ،درون اسناد و اطالعات موجود در اینترنت کاوش و نتایج را در قالب «آدرس محل ذخیره» عرضه میکنند. خاص منظوره :برای جستجو در یک برنامه کاربردی(سایت) خاص موتورهای جستجوی جهانی(معمول) :کلیه اسناد موجود در اینترنت را بررسی می کنند سوپر موتورهای جستجو :درخواست های کاربران را در موتورهای مختلف دنیا جستجو و نتایج حاصله را ترکیب می کنند 2 انواع موتورهای جستجو بر اساس نحوه عملکرد معماری موتورهای جستجو -ابوالفضل آسوده مبتنی بر خزش – Crawler based Search Engines مبتنی بر فهرست – Directory based Search Engines با دخالت مستقیم صاحبان اسناد به صورت درختی به زیر شاخه های مرتبط دسته بندی می شوند برای حفظ جایگاه ،صاحبان اسناد باید توجه ویژه ای به کیفیت و محتوای صفحاتشان داشته باشند. با توجه به دسته بندی هوشمندانه معموال نتایج سودمندتری ارائه می دهند ترکیبی Hybrid Search Engines - 3 صفحات وب درحال تغییر معماری موتورهای جستجو -ابوالفضل آسوده تقریبا %40صفحات وب com.روزانه تغییر می کنند. نیمه عمر وب سایت های com 10.روز است!! مدل آماری تغییر صفحات وب از توزیع پوآسون تبعیت میکند !P(n)t=((λt)ne- λt)/n 22% صفحات اینترنتی لینک بازگشت به هسته(صفحه اصلی سایت) ندارند. %20به هسته هایی لینک دارند که از طریق آنها قابل دسترس نیستند. 4 معماری کلی موتورهای جستجو Page Reposi tory WEB Client u Res Q ry e u lt Indexer Analyzer Crawl Control Text Link Struc ture Query Engine Ranking Utilit y 5 Usage Feed Back ابوالفضل آسوده- معماری موتورهای جستجو Crawler ماژول خزنده CRAWLER - معماری موتورهای جستجو -ابوالفضل آسوده وظیفه :استخراج صفحات و ذخیره آنها در انباره صفحات با یک مجموعه اولیه از URLها که در یک صف اولویت دار قرار دارد شروع می کند. پس از استخراج صفحات همزمان با ذخیره آنها ،لینک های درون آنها را برای اضافه شدن به صف تحویل ماژول کنترل کننده خزش می دهد. کنترل کننده آدرس های تکراری را از این مجموعه حذف و بقیه را درصورت داشتن معیارهای الزم به ترتیب اولویت به انتهای صف اضافه میکند 6 معیارهای اولویت صفحات معماری موتورهای جستجو -ابوالفضل آسوده مبتنی بر گرایشات کاربران – Interest Driven مبتنی بر شهرت Popularity Driven - مبتنی بر محل قرار گرفتن صفحات – Location Driven 7 INTEREST DRIVEN معماری موتورهای جستجو -ابوالفضل آسوده 8 POPULARITY DRIVEN معماری موتورهای جستجو -ابوالفضل آسوده ‏fایfندازfه fگffیریشffهfرتصffفحه ،شfمارfش :Back link count یfکیاز راfهه ا ‏fیfسfتکffه بffه آfنلffینکدادfه fاfند .هرچfه اfیfنتffعداد بffیشتر تfعداد صffفحات ا ‏fت بffاشد نffشاندfهنده fشffهfرتبffیشتر صffفحه اfس . 9 LOCATION DRIVEN معماری موتورهای جستجو -ابوالفضل آسوده فاکتورهای زیر می توانند برای مشخص کردن فاصله صفحات استفاده شوند محل قرار گرفتن آدرس صفحه فاصله آن تا صفحه اصلی سایت(تعداد لینک) آدرس صفحه ماهیت آدرس ()..,net, .com. 10 الگوهای کاوش ماژول خزنده معماری موتورهای جستجو -ابوالفضل آسوده خزش و توقف – :Crawl & Stopبا شروع از یک آدرس دقیقا k صفحه را(به ترتیب اولویت) استخراج میکند و خارج می شود خزش و توقف با آستانه – :Crawl & Stop with Threshold با شروع از یک آدرس تمام صفحاتی را که اولویتشان از حد آستانه بیشتر است مالقات می کند 11 سرکشی و ذخیره مجدد صفحات REFRESH - معماری موتورهای جستجو -ابوالفضل آسوده تازه سازی یکنواخت :تمام صفحات فارغ از اینکه تغییر کرده باشند یا نه به صورت دوره ای سرکشی می شوند تازه سازی متناسب با تغییر :با فرض اینکه صفحه ای با دوره تناوب λتغییر میکند ،بهترین سیاست سرزدن مجدد با همین دوره است .در این الگوریتم ابتدا زمان refreshبه یک مقدار سریغ تنظیم می شود( .در یک روش) درصورتیکه در این بازه محتویات صفحه تغییر نکرده بود زمان refresh باضریب αافزوده می شود. 12 ال ال ال ال!! ... معماری موتورهای جستجو -ابوالفضل آسوده 13 معماری کلی موتورهای جستجو Page Reposi tory WEB Client u Res Q ry e u lt Indexer Analyzer Crawl Control Text Link Struc ture Query Engine Ranking Utilit y 14 Usage Feed Back ابوالفضل آسوده- معماری موتورهای جستجو Crawler انباره ذخیره سازی – PAGE REPOSITORY معماری موتورهای جستجو -ابوالفضل آسوده چالش ها گسترش پذیری تا بینهایت()Scalability پشتیبانی از دسترسی تصادفی و ترتیبی به روز رسانی توده ای صفحات منسوخ 15 ماژول اندیس گذار – استخراج اندیس ها معماری موتورهای جستجو -ابوالفضل آسوده شاخص متن ساختار لینک 16 شاخص متن – TEXT INDEX معماری موتورهای جستجو -ابوالفضل آسوده پایگاه داده ای از کل کلمات ممکن در هر ادبیات ،به همراه اندیس صفحاتی که این کلمات در آنها به کار رفته است. سه تایی «واژه»« ،صفحه» و «موقعیت واژه در صفحه» و همچنین اطالعات اضافی مانند « »boldبودن ذخیره می شود. 17 ساختار لینک – LINK STRUCTURE معماری موتورهای جستجو -ابوالفضل آسوده گراف جهت داری که گره های آن صفحات و یال های آن لینکهای بین آنهاست. با توجه به پیچیدگی الگوریتم های گراف ،ساده سازی آن اهمیت ویژه ای دارد. می توان برای ساده کردن گراف از روش های سلسله مراتبی استفاده کرد. 18 رتبه بندی و تحلیل لینک معماری موتورهای جستجو -ابوالفضل آسوده موتور جستجو پس از بررسی هر جستجو در میان شاخص ها با انبوهی از صفحات مواجه می شود .سوال این است که کدام صفحه باید در رتبه باالتری قرار گیرد. برای رتبه بندی صفحات از دو مجموعه کامال مجزای اطالعات استفاده می شود. اطالعات درون صفحه اطالعات خارج از صفحه(در صفحات دیگر) 19 عوامل رتبه بندی درون صفحه معماری موتورهای جستجو -ابوالفضل آسوده دفعات تکرار کلمات ترتیب و مجاورت کلمات کلیدی محل درج کلمه کلمات کلیدی تکرار شده در URL پررنگ بودن کلمات کلیدی استفاده از تگ <>meta برچسب های altاستفاده شده برای تصاویر 20 عوامل رتبه بندی بیرون صفحه ‏ معماری موتورهای جستجو -ابوالفضل آسوده ‏ مهمترین آنها تعداد ارجاعاتی است که از صفحات دیگر به این صفحه شده است و اهمیت صفحاتی که به این صفحه ارجاع داشته اند. یکی از بهترین نمونه های این رتبه بندی الگوریتم PageRankگوگل می باشد ‏T1 ‏T2 ‏T3 ‏Current Page 21 ‏Tn PAGE RANK معماری موتورهای جستجو -ابوالفضل آسوده 22 امکان سنجی معماری موتورهای جستجو -ابوالفضل آسوده از آنجایی که می توان موتورهای جستجو را به عنوان نماد وب دانست ،پیاده سازی یک موتور جستجوی موفق عالوه بر درآمد زایی و اشتغال زایی در سطح کالن می تواند گامی به سوی توسعه یافته شدن به حساب آید. همانگونه که دیدیم اینچنین پروژه ای عزم ملی می طلبد و با چالشهای نرم افزاری ،سخت افزاری زیادی مواجه است و البته قدرت یک موتور جستجوگر با الگوریتم ها و مکانیزم های اندیس گذاری و رتبه بندی ارتباط مستقیم دارد. با توجه به اینکه %40صفحات وب روزانه تغییر می کنند پهنای باند باال و قدرت پردازش باالی سخت افزاری الزم است. 23 تعداد صفحات وب معماری موتورهای جستجو -ابوالفضل آسوده با بررسی که در سایت ( worldwidewebsize.comکه تعداد صفحات اندیس شده در موتورهای جستجوی دنیا را نشان می دهد) به عمل آمد به این نتجه رسیدیم که تعداد صفحات وب در سالهای اخیر کامال قابل پیش بینی و ثابت( 42میلیارد) شده است!! 24 تعداد صفحات وب معماری موتورهای جستجو -ابوالفضل آسوده 25 تعداد صفحات وب معماری موتورهای جستجو -ابوالفضل آسوده 26 امکان سنجی معماری موتورهای جستجو -ابوالفضل آسوده بی شک برای پوشش چنین پهنه ای از اطالعات استفاده از تکنیک توزیع شدگی بار – distributionناگزیر است. فرض کنیم برای انجام این کار از 20سرور که به صورت فیزیکی در نقاط مختلف کشور پخش شده اند استفاده می شود ( با توجه به عدم نیاز به ذخیره اسناد چندرسانه ای) متوسط اندازه هر صفحه را 2KBدرنظر گرفتیم بنابراین انباره اطالعاتی با حجم 84ترابایت نیاز می باشد که به هر سرور 5 ترابایت میرسد(کامال ممکن و مقرون به صرفه) فرض کنیم که صفحات با دوره 5روزه refreshمی شوند .بنابراین با تبدیل روز به ثانیه و بایت به بیت هر سرور به پهنای باند 100Mbps ( 27بدون درنظرگرفتن پهنای باند الزم برای ارتباط با کاربر)نیاز دارد که ممکن به نظر می رسد. امکان سنجی معماری موتورهای جستجو -ابوالفضل آسوده تنها نکته باقی مانده قدرت پردازشی و الگوریتم های اندیس گذاری و رتبه بندی و خزش است. در یک دید خیلی خوش بینانه ) O(nبرای الگوریتم های خزش و اندیس گذاری و ) O(n3برای الگوریتم رتبه بندی در نظر می گیریم. در این میان الگوریتم رتبه بندی با رسیدن به عدد 1027*2به هیچ عنوان قابل تحمل به نظر نمی رسد ولی با توجه به این واقعیت که گراف ساختار لینک (در صورت سلسله مراتبی عمل کردن) یک گراف خلوت به نظر می آید عدد به دست آمده خیلی دور از واقعیت می نماید. در پایان به نظر می رسد که بستر سخت افزاری الزم برای این پروژه ممکن باشد و آنچه اهمیت می یابد کشف الگوریتم های بهینه است .لذا با سیاست گذاری صحیح در مجامع علمی این مهم ناممکن نمی نماید. 28 خسته نباشید معماری موتورهای جستجو -ابوالفضل آسوده 29 ‏asudeh@ce.sharif.edu