بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارزیابی کارایی Web Crawler
چکیده
تار جهان گستر وب، در سال های اخیر، روند رو به رشدی را طی کرده است و از هزاران صفحه به بیشتر از دو میلیارد صفحه در زمان کنونی رسیده است. با گسترش روزافزون تعداد صفحات وب، موتورهای جستجوی وب باید اطلاعات مرتبط با عبارت مورد جستجو را در اختیار کاربر قرار دهند. موتورهای جستجوی وب همانند بیشتر ابزارهای مخصوص جستجو به WebCrawler ها برای بدست آوردن مجموعه ی بزرگی از صفحات، برای رتبه بندی و فهرست گذاری تکیه می کنند. از آنجاییکه Web Crawler ممکن است در طول چند هفته یا ماه به طور دوره ای، به صفحات جهت بهروزرسانی جداول خود مراجعه کند، بکارگیری روش قدرتمند، انعطاف پذیر و مدیریت پذیر برای این کار ضروری به نظر می رسد. بعلاوه کارایی I/O، منابع شبکه و محدودیتهای سیستم عامل نیز باید در نظر گرفته شود. در این مقاله ابتدا به بررسی طراحی یک نمونه Crawler می پردازیم و سپس آن را بر اساس دو روش Breadth-first و Depth-first شبیه سازی می کنیم و چهار معیار ارزیابی مهم یعنی تعداد پیوندهای تست شده، تعداد صفحات دیده شده در ثانیه، سایز فایل Crawl شده و حافظه ی مورد استفاده برای انجامCrawll را که تاکنون جهت ارزیابی کارایی Web Crawler ها در نظر گرفته نشده اند، مورد بررسی قرار می دهیم.
کلمات کلیدی: موتور جستجو، Web Crawler، ارزیابی کارایی، شبیهسازی
۱. مقدمه
موتورهای جستجوی عمومی از برنامه هایی معروف به Tobot ،Crawler و یا Spider برای یافتن و مرور صفحات وب استفاده می کنند. نحوه ی کار این برنامه ها بدین صورت است که با یافتن یک صفحه، کلمات مورد استفاده در آن را شناسایی کرده و به جداول فهرست بانک اطلاعاتی خود اضافه می کنند. در واقع موتورها، صفحات وب را در بانک اطلاعاتی نگهداری نمی کنند. بلکه در بانک اطلاعاتی فهرستی از کلمات و آدرس صفحات مشمول این کلمات میباشد. کار دیگر این برنامه ها این است که
به صفحات فهرست شده ی قبلی مراجعه کرده و در صورت بروز شدن صفحات، مجددا آنها را فهرست بندی می کنند.
یک Crawler خوب برای موتورهای جستجوی بزرگ باید دو موضوع را بررسی کند. ابتدا باید دارای یک استراتژی Crawling مناسب باشد؛ به طور مثال یک استراتژی خوب برای تصمیم گیری در مورد اینکه در مرحله ی بعد کدامیک از صفحات وب باید Crawl و بارگذاری شوند. دوم اینکه نیاز به داشتن معماری سیستم بهینه شده دارد که قادر به بارگذاری [1]-uel Laweb server شمار زیادی از صفحات در ثانیه به صورت صحیح، کاملا مهار شدنی و با توجه به منابع در بخش دوم این مقاله ابتدا به بررسی کارهای مرتبط در زمینه ی ارزیابی کارایی Web Crawler ها میپردازیم. در بخش سوم انواع برنامه های Crawling را مورد بررسی قرار می دهیم. هدف از این کار علاوه بر معرفی این برنامه ها، استفاده از دو استراتژی اول، Breadth-First و Depth-first به عنوان پارامتری جهت ارزیابی کارایی Web Crawler میباشد. در بخش چهارم یکك نمونه Web Crawler طراحی میگردد. در بخش پنجم چهار معیار جهت ارزیابی کارایی Web Crawler پیشنهاد میگردد. در بخش ششم نتایج مورد تحلیل و ارزیابی قرار میگیرد. در بخش هفتم نتیجه گیری از بحت های مطرح شده صورت میگیرد و کارهای آتی معرفی خواهند شد.
۲. کارهای مرتبط تا کنون طراحی و پیادهسازی های مختلفی برای Web Crawler ها صورت گرفته است. همچنین بسیاری از آنها شبیه سازی شده و معیارهای کارایی آنها از جهات مختلفی مورد ارزیابی قرار گرفته اند. در [۲] از گوگل به عنوان سریع ترین Crawler توزیع شده نام برده شده است. معیار کارایی در این مقاله بر میزان مراجعه است. در [۳] عمل و الگوریتم Crawlerهای همکار مورد بررسی قرار گرفته است. در [۱] Crawlهای موازی جهت رسیدن به کارایی بالا معرفی و پیادهسازی شده اند. تاکید این مقاله بیشتر بر روی تاثیر ویژگی مقیاس پذیری و مطالعه رفتار مولفه ها بوده است. در نهایت بر مبنای شبیه سازی انجام یافته بر روی Sun نمودارها بررسی شده و سیستم تست گردیده است. در [۴] Crawlهای توزیع شده با کارایی بالا معرفی و ارزیابی شده اند. در [۵] یک الگوریتم زمانبندی برای Web Crawler و چندین راهبرد برای مرتب کردن صفحات وب در طول عمل Crawlارائه شده، سپس با استفاده از شبیهساز Web Crawler مقایسه شده اند. از بین آن استراتژی ها کار اترین و مناسب ترین آنها انتخاب شده و در نهایت استراتژی انتخاب شده بر روی Web Crawler واقعی تست گردیده است. برای این کار از شبیه ساز C++ SIM ]۶[ که مبتنی بر فرآیندهای گسسته است، استفاده شده است. بعلاوه با تقسیم فایل Crawl شده بر زمان آن سرعت عمل Crawlاندازه گیری شده است و معیار ارزیابی کارایی مقاله ی مورد نظر، قرار گرفته است. در [۷] افزایش مجموعه جواب مرتبط با موضوع مدنظر بوده است. معیار کارایی در آنجا زمان پاسخ به پرس و جوی مطرح شده بوده است. در اینجا نیز هم شبیه سازی صورت گرفته و نتایج آماری و نمودارهای حاصل مورد بررسی قرار گرفته است. در [۸] بررسی Crawler موضوعی مورد بحث بوده است. برای بیشینه کردن کیفیت مجموعه جواب، کارایی زمانبندی درخواست به عنوان اصلی ترین معیار کیفیت در طول زمانبندی، در نظر گرفته شده است. برای محاسبه ی میزان کارایی نیز از معیارهای مشابه در بحسث بازیابی اطلاعات " استفاده شده است. تنها محدودیت روی سایز مجموعه ذکر شده است که ترکیبی از توان عملیاتی سیستم و نیاز به بروز نگهداری مجموعه را ایجاد می کند. لذا معیار کارایی در آن مقاله نیز فرآیند تصمیم گیری مارکوف "استفاده شده و از الگوریتم های برنامه نویسی پویا (DP) و NDP ]۹[ کمک گرفته شده است. تمام موارد فوق به گونه ای به طراحی Lls l-a -ul-ls web Crawler خود را مطرح نموده اند و به شبیه سازی و بررسی اطلاعات آماری آن پرداخته اند. اما هیچ یک از آنها چهار معیار اصلی که در این مقاله مطرح شده است را مورد ارزیابی قرار نداده اند. این چهار معیار از جهات مختلفی برای ارزیابی کارایی Web Crawler ها مهم هستند که در بخش پنج به تفضیل به هر یک از آنها خواهیم پرداخت.
۳. استراتژی های Crawling
برنامه های Crawler با توجه به نوع کاربرد انواع مختلفی دارند که در ذیل استراتژیهای گوناگون آن مطرح شده است
Broad Breadth-First Crawling - 1
به منظور ساخت یک موتور جستجو یا یک منبع بزرگ، Crawlerهایی با قابلیت اجرایی بالا، مورد استفاده قرار میگیرند که از یک سری صفحات کوچکی شروع شده و سپس سایر صفحات با استفاده از پیوندهایی در حالت Breadth-First، Crawlمی شوند.
D
DDebth-First Crawling -2
ددر این روش از یک سایت شروع کرده و تا عمق مورد نظر پیوندهای مجاور قبلی را Crawlمی کنیم. در این روش بعد از Crawlهر نود، نوبت به Crawlنود همسایه در عمق بعد میرسد. اما در روش قبلی بعد از Crawlهر نود، نودهای همسایه با آن
نود مورد Crawlقرار می گیرند. در بخش ششم این مقاله، با بررسی اثر عمق در Crawl به مقایسه این دو روش میپردازیم.
Crawling 3-3مجدد صفحات برای به روزرسانی
به دلیل تغییر مرتب صفحات وب، نیاز به کنترل و Crawlمجدد آنها برای بهروزرسانی اطلاعات جداول است. در سادهترین حالت این کار ممکن است با Crawl کردن یک Broad Breadth-First - شود یا یک درخواست ساده برای همه آدرس های اینترنتی موجود در مجموعه دوباره فرستاده شود. بهترین استراتژیهای Crawling مجدد برای حفاظت و به روزرسانی فهرست جستجوها با محدود کردن پهنای باند Crawlصورت می گیرد[۱]. برای بهروزرسانی صفحات سه روش وجود دارد:
۱- ترتیب ثابت که لیست مشخصی از آدرس های اینترنتی باید دیده شود.
۲- ترتیب تصادفی که از یک صفحه شروع می شود و پیوندهای آن دنبال می شود.
۳- تصادفی محضی که صفحات برحسب نیاز بهروزرسانی می شوند.
crawling 3 – 4متمرکز
بسیاری از موتورهای جستجوی مشخص و صاحب نام ممکن است از سیاست های Crawilling که بر روی یک نوع خاص از صفحات تمرکز دارند، استفاده کنند. به عنوان مثال صفحاتی که بر روی یک موضوع خاصی در مورد یک زبان مشخص، تصاویر، فایلهای صوتی یا صفحاتی که به علوم کامپیوتر اختصاص دارند. هدف از تمرکز Crawler، یافتن بسیاری از صفحات مورد نظر بدون استفاده از پهنای باند زیادی است. بنابراین اغلب اعمال قبلی در یک Crawler با قابلیت اجرای بالا، مورد استفاده قرار نمی گیرند. اگرچه انجام و پشتیبانی برای جمع آوری مجموعه اطلاعات بزرگ بسیار پر اهمیت تر از بروز نگه داری یک موتور جستجو است .
Crawling قدم های تصادفی و نمونه برداری
در این مرحله یک مجموعه حالت بصورت وجود دارد. از آنجایکه مجموعه حالت های ممکن، بسیار بزرگ است و دستیابی به آن کاری بسیار مشکل است، لذا یک مجموعه ی کوچکی از آن نمونه برداری شده و مورد بررسی قرار میگیرد. هر کدام از این حالت ها متناظر پیوندهایی هستند که در هر مرحله می تواند یکی از آنها از مجموعه به صورت تصادفی انتخاب شده و Crawlگردد. در هر مرحله انتقال از یک حالت به حالت دیگر مستقل از حالت های قبلی و فقط وابسته به حالت کنونی است. لذا قدم های تصادفی با فرآیند و زنجیره های مارکوف مدل می شوند [۸] [۱] با توجه به مفاهیم آماری و زنجیره های مارکوف [۸] می توان از یک مجموعه ی بصورت تصادفی Crawlشده، نمونه برداری کرد. برای هر صفحه X میتوان گفت .
Crawling وب مخفی
بسیاری از داده های در دسترسی که در پایگاه داده قرار دارند، فقط از طریق ارسال درخواستهای اختصاصی و یا پر کردن دادهها دسترسی پیدا می کنند. همچنین " صفحات مخفی" و " صفحات عمیق" نیز مورد دسترسی قرار میگیرند.
Crawling موازی
موازی نوعی از Crawling است که به طور موازی و همزمان بر روی قسمت هایی از وب که از پیش انتخاب شده اند انجام می شود. این نوع Crawling به دو صورت تخصیص پویا و ایتا صورت می پذیرد. در تخصیص پویا هماهنگ کننده ی مرکزی، وب را به بخش هایی تقسیم می کند. Crawlerها، در قسمتهایی که به آنها تخصیص داده شده، Crawl می کنند. پیوندهایی به آدرس های دیگر اینترنتی در هماهنگ کننده مرکزی قرار گرفتهاند. همچنین هماهنگ کننده مرکزی به دليل نگهداری تعداد زیادی از آدرسهای اینترنتی گزارش شده از تمام زیر برنامه ها و هماهنگ کردن آنها، ممکن است گلوگاه اصلی باشد. در تخصیص ایستا نیز وب تقسیم می شود. ولی هر قسمت به Crawlerهای داده می شود. Crawlerها فقط در وب خودشان، Crawlمی کنند. در این نوع تخصیص کاربر باید بداند که آنها چه چیزی را میخواهند Crawlکنند و آنها ممکن است تمام دامنه مورد نظر را نشناسند.
طراحی یک web Crawler
از آنجاییکه موتورهای جستجو نیازمند Crawler انعطاف پذیر، کم هزینه و با قابلیت Crawlچند صد صفحه در ثانیه هستند، طراحی معماری مناسب آنها بسیار حائز اهمیت است. در یک دید کلی میتوان بخش های Web Crawler را به سه دسته تقسیم نمود:
۴ Crawlerو تجزیه کننده
این بخش مهمترین قسمت طراحی است. آغاز کار به این صورت است که از یک دامنه ی معین، شروع به بارگذاری ستد و تجزیه ی آن می نماید. سپس آدرس های وب از داخل سند بدست می آیند و در داخل صف آماده برای انجام که یک صفFIFo است قرار میگیرند . بعد از پایان کار تجزیه هر سند .، ادرس وب بعدی از سند اماده برای انجام بیرون کشیده میشود .
ججدول اطلاعات
دو جدول در طول عمل Crawling نگهداری می شود جدول اول Tblword نام دارد. در این جدول به هر کلمه یی مختلف یک شماره واحد اختصاص داده میشود . جدول دوم TBIURL نام دارد . اطلاعات مربوط به تمام آدرس های وب دامنه را درون خود جای میدهد. برای کاهش زمان جستجو ساختارهای داده ی هر دو جدول، در هم هستند.
۳-۴ پایگاه داد
در یک پایگاه داده هر کلمه و محل آن در اسناد نگهداری می شود. برای جدول TblWord، کلید اصلی WordID است که با لیستی از DocID شامل کلمه و موقعیت کلمه در سند ادامه پیدا می کند. موقعیت کلمه در سند برای رتبه بندی نتایج به هنگام جستجو مورد نیاز است.
لذا معماری CraWiler بصورت زیر میباشد:
