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

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

اسلاید 1: معماری موتورهای جستجوابوالفضل آسوده1390/02/18به نام خدا

اسلاید 2: موتور جستجو(Search Engine)برنامه هایی که موضوعات مورد نظر کاربران را در قالب کلمات کلیدی، درون اسناد و اطلاعات موجود در اینترنت کاوش و نتایج را در قالب «آدرس محل ذخیره» عرضه میکنند.خاص منظوره: برای جستجو در یک برنامه کاربردی(سایت) خاصموتورهای جستجوی جهانی(معمول): کلیه اسناد موجود در اینترنت را بررسی می کنندسوپر موتورهای جستجو: درخواست های کاربران را در موتورهای مختلف دنیا جستجو و نتایج حاصله را ترکیب می کنندمعماری موتورهای جستجو - ابوالفضل آسوده2

اسلاید 3: انواع موتورهای جستجو بر اساس نحوه عملکردمبتنی بر خزش – Crawler based Search Enginesمبتنی بر فهرست – Directory based Search Engines با دخالت مستقیم صاحبان اسنادبه صورت درختی به زیر شاخه های مرتبط دسته بندی می شوندبرای حفظ جایگاه، صاحبان اسناد باید توجه ویژه ای به کیفیت و محتوای صفحاتشان داشته باشند.با توجه به دسته بندی هوشمندانه معمولا نتایج سودمندتری ارائه می دهندترکیبی - Hybrid Search Enginesمعماری موتورهای جستجو - ابوالفضل آسوده3

اسلاید 4: صفحات وب درحال تغییرتقریبا 40% صفحات وب .com روزانه تغییر می کنند.نیمه عمر وب سایت های .com 10 روز است!!مدل آماری تغییر صفحات وب از توزیع پوآسون تبعیت میکندP(n)t=((λt)ne- λt)/n!22% صفحات اینترنتی لینک بازگشت به هسته(صفحه اصلی سایت) ندارند. 20% به هسته هایی لینک دارند که از طریق آنها قابل دسترس نیستند.معماری موتورهای جستجو - ابوالفضل آسوده4

اسلاید 5: معماری کلی موتورهای جستجومعماری موتورهای جستجو - ابوالفضل آسوده5WEBCrawlerPage RepositoryIndexerAnalyzerCrawl ControlClientQueryEngineRankingTextLinkStructureUtilityQueryResultUsage Feed Back

اسلاید 6: ماژول خزنده - Crawlerوظیفه: استخراج صفحات و ذخیره آنها در انباره صفحاتبا یک مجموعه اولیه از URLها که در یک صف اولویت دار قرار دارد شروع می کند.پس از استخراج صفحات همزمان با ذخیره آنها، لینک های درون آنها را برای اضافه شدن به صف تحویل ماژول کنترل کننده خزش می دهد.کنترل کننده آدرس های تکراری را از این مجموعه حذف و بقیه را درصورت داشتن معیارهای لازم به ترتیب اولویت به انتهای صف اضافه میکندمعماری موتورهای جستجو - ابوالفضل آسوده6

اسلاید 7: معیارهای اولویت صفحاتمبتنی بر گرایشات کاربران – Interest Drivenمبتنی بر شهرت - Popularity Drivenمبتنی بر محل قرار گرفتن صفحات – Location Drivenمعماری موتورهای جستجو - ابوالفضل آسوده7

اسلاید 8: Interest Driven معماری موتورهای جستجو - ابوالفضل آسوده8

اسلاید 9: Popularity DrivenBack link count: یکی از راههای اندازه گیری شهرت صفحه، شمارش تعداد صفحاتی است که به آن لینک داده اند. هرچه این تعداد بیشتر باشد نشان دهنده شهرت بیشتر صفحه است.معماری موتورهای جستجو - ابوالفضل آسوده9

اسلاید 10: Location Drivenفاکتورهای زیر می توانند برای مشخص کردن فاصله صفحات استفاده شوندمحل قرار گرفتن آدرس صفحهفاصله آن تا صفحه اصلی سایت(تعداد لینک)آدرس صفحهماهیت آدرس (.net, .com,..)معماری موتورهای جستجو - ابوالفضل آسوده10

اسلاید 11: الگوهای کاوش ماژول خزندهخزش و توقف – Crawl & Stop: با شروع از یک آدرس دقیقا k صفحه را(به ترتیب اولویت) استخراج میکند و خارج می شودخزش و توقف با آستانه – Crawl & Stop with Threshold: با شروع از یک آدرس تمام صفحاتی را که اولویتشان از حد آستانه بیشتر است ملاقات می کندمعماری موتورهای جستجو - ابوالفضل آسوده11

اسلاید 12: سرکشی و ذخیره مجدد صفحات - Refreshتازه سازی یکنواخت: تمام صفحات فارغ از اینکه تغییر کرده باشند یا نه به صورت دوره ای سرکشی می شوندتازه سازی متناسب با تغییر: با فرض اینکه صفحه ای با دوره تناوب λ تغییر میکند، بهترین سیاست سرزدن مجدد با همین دوره است. در این الگوریتم ابتدا زمان refresh به یک مقدار سریغ تنظیم می شود. (در یک روش) درصورتیکه در این بازه محتویات صفحه تغییر نکرده بود زمان refresh باضریب α افزوده می شود.معماری موتورهای جستجو - ابوالفضل آسوده12

اسلاید 13: لا لا لا لا... !!معماری موتورهای جستجو - ابوالفضل آسوده13

اسلاید 14: معماری کلی موتورهای جستجومعماری موتورهای جستجو - ابوالفضل آسوده14WEBCrawlerPage RepositoryIndexerAnalyzerCrawl ControlClientQueryEngineRankingTextLinkStructureUtilityQueryResultUsage Feed Back

اسلاید 15: انباره ذخیره سازی – Page Repositoryچالش هاگسترش پذیری تا بینهایت(Scalability)پشتیبانی از دسترسی تصادفی و ترتیبیبه روز رسانی توده ایصفحات منسوخمعماری موتورهای جستجو - ابوالفضل آسوده15

اسلاید 16: ماژول اندیس گذار – استخراج اندیس هاشاخص متنساختار لینکمعماری موتورهای جستجو - ابوالفضل آسوده16

اسلاید 17: شاخص متن – Text Indexپایگاه داده ای از کل کلمات ممکن در هر ادبیات، به همراه اندیس صفحاتی که این کلمات در آنها به کار رفته است.سه تایی «واژه»، «صفحه» و «موقعیت واژه در صفحه» و همچنین اطلاعات اضافی مانند «bold» بودن ذخیره می شود.معماری موتورهای جستجو - ابوالفضل آسوده17

اسلاید 18: ساختار لینک – Link Structureگراف جهت داری که گره های آن صفحات و یال های آن لینکهای بین آنهاست.با توجه به پیچیدگی الگوریتم های گراف، ساده سازی آن اهمیت ویژه ای دارد.می توان برای ساده کردن گراف از روش های سلسله مراتبی استفاده کرد.معماری موتورهای جستجو - ابوالفضل آسوده18

اسلاید 19: رتبه بندی و تحلیل لینکموتور جستجو پس از بررسی هر جستجو در میان شاخص ها با انبوهی از صفحات مواجه می شود. سوال این است که کدام صفحه باید در رتبه بالاتری قرار گیرد.برای رتبه بندی صفحات از دو مجموعه کاملا مجزای اطلاعات استفاده می شود.اطلاعات درون صفحهاطلاعات خارج از صفحه(در صفحات دیگر)معماری موتورهای جستجو - ابوالفضل آسوده19

اسلاید 20: عوامل رتبه بندی درون صفحهدفعات تکرار کلماتترتیب و مجاورت کلمات کلیدیمحل درج کلمهکلمات کلیدی تکرار شده در URLپررنگ بودن کلمات کلیدیاستفاده از تگ <meta>برچسب های alt استفاده شده برای تصاویرمعماری موتورهای جستجو - ابوالفضل آسوده20

اسلاید 21: عوامل رتبه بندی بیرون صفحهمهمترین آنها تعداد ارجاعاتی است که از صفحات دیگر به این صفحه شده است و اهمیت صفحاتی که به این صفحه ارجاع داشته اند.یکی از بهترین نمونه های این رتبه بندی الگوریتم PageRank گوگل می باشدمعماری موتورهای جستجو - ابوالفضل آسوده21Current PageT1T2T3Tn

اسلاید 22: Page Rank معماری موتورهای جستجو - ابوالفضل آسوده22

اسلاید 23: امکان سنجیاز آنجایی که می توان موتورهای جستجو را به عنوان نماد وب دانست، پیاده سازی یک موتور جستجوی موفق علاوه بر درآمد زایی و اشتغال زایی در سطح کلان می تواند گامی به سوی توسعه یافته شدن به حساب آید.همانگونه که دیدیم اینچنین پروژه ای عزم ملی می طلبد و با چالشهای نرم افزاری، سخت افزاری زیادی مواجه است و البته قدرت یک موتور جستجوگر با الگوریتم ها و مکانیزم های اندیس گذاری و رتبه بندی ارتباط مستقیم دارد.با توجه به اینکه 40% صفحات وب روزانه تغییر می کنند پهنای باند بالا و قدرت پردازش بالای سخت افزاری لازم است.معماری موتورهای جستجو - ابوالفضل آسوده23

اسلاید 24: تعداد صفحات وببا بررسی که در سایت worldwidewebsize.com (که تعداد صفحات اندیس شده در موتورهای جستجوی دنیا را نشان می دهد) به عمل آمد به این نتجه رسیدیم که تعداد صفحات وب در سالهای اخیر کاملا قابل پیش بینی و ثابت(42 میلیارد) شده است!!معماری موتورهای جستجو - ابوالفضل آسوده24

اسلاید 25: تعداد صفحات وبمعماری موتورهای جستجو - ابوالفضل آسوده25

اسلاید 26: تعداد صفحات وبمعماری موتورهای جستجو - ابوالفضل آسوده26

اسلاید 27: امکان سنجیبی شک برای پوشش چنین پهنه ای از اطلاعات استفاده از تکنیک توزیع شدگی بار – distribution ناگزیر است.فرض کنیم برای انجام این کار از 20 سرور که به صورت فیزیکی در نقاط مختلف کشور پخش شده اند استفاده می شود(با توجه به عدم نیاز به ذخیره اسناد چندرسانه ای) متوسط اندازه هر صفحه را 2KB درنظر گرفتیمبنابراین انباره اطلاعاتی با حجم 84 ترابایت نیاز می باشد که به هر سرور 5 ترابایت میرسد(کاملا ممکن و مقرون به صرفه)فرض کنیم که صفحات با دوره 5 روزه refresh می شوند. بنابراین با تبدیل روز به ثانیه و بایت به بیت هر سرور به پهنای باند 100Mbps (بدون درنظرگرفتن پهنای باند لازم برای ارتباط با کاربر)نیاز دارد که ممکن به نظر می رسد.معماری موتورهای جستجو - ابوالفضل آسوده27

اسلاید 28: امکان سنجیتنها نکته باقی مانده قدرت پردازشی و الگوریتم های اندیس گذاری و رتبه بندی و خزش است.در یک دید خیلی خوش بینانه O(n) برای الگوریتم های خزش و اندیس گذاری و O(n3) برای الگوریتم رتبه بندی در نظر می گیریم.در این میان الگوریتم رتبه بندی با رسیدن به عدد 2*1027 به هیچ عنوان قابل تحمل به نظر نمی رسد ولی با توجه به این واقعیت که گراف ساختار لینک (در صورت سلسله مراتبی عمل کردن) یک گراف خلوت به نظر می آید عدد به دست آمده خیلی دور از واقعیت می نماید.در پایان به نظر می رسد که بستر سخت افزاری لازم برای این پروژه ممکن باشد و آنچه اهمیت می یابد کشف الگوریتم های بهینه است. لذا با سیاست گذاری صحیح در مجامع علمی این مهم ناممکن نمی نماید.معماری موتورهای جستجو - ابوالفضل آسوده28

اسلاید 29: خسته نباشیدمعماری موتورهای جستجو - ابوالفضل آسوده29asudeh@ce.sharif.edu