طبق سیاست روزآمد سازی نسبی، خزنده صفحاتی را که به طور نسبی در زمان های بیش تر تحت تغییرات بیش تری قرار گرفته اند، بیش تر مورد مرور مجدد قرار می دهد]۲۳[.
۳-۹ به حداقل رساندن بار روی وب سایت های بازدید شده
هنگامی که خزنده صفـحات را از وب سایـت جمع آوری می کنـد منابع متعلق به وب سایت های دیگر را مصـرف می نماید. برای مثال هنگامیکه خزنده صفحهp را از سایت s دانلود می کند، سایت احتیاج دارد که صفحه p را از فایل سیستم خود بازیابی کند، دیسک و منابع سی پی یو را مصرف نماید. بعد از این بازیابی صفحه باید از طریق شبکه منتقل شود، جاییکه منابع بسیاری از وب سایتها به اشتراک گذاشته شده است بنابراین، خزنده باید اثر خود را روی این منابع به حداقل برساند. از طرف دیگر ممکن است مدیریت وب سایت یا یک شبکه خاص شکایت کند و گاهی به طور کامل ممکن است دسترسی خزنده را بلوک نماید]۷[.
پایان نامه - مقاله - پروژه
۳-۱۰ موازی سازی روند خزنده
با توجه به اندازه بسیار بزرگ وب، خزنده ها اغلب روی دستگاه های متعدد اجرا و صفحات را به صـورت مـوازی دانـلود می کننـد. این موازی سـازی اغلب برای دانلود تعـداد زیادی از صفحات در یک میزان زمان قابل قبول لازم است. واضح است که این خزنده موازی باید به درستی هماهنگ شده باشد. بـنابراین خزنده های مختـلف در چنـدین زمان از یک صفحـه وب بازدیـد نمی کنند. به هر حـال این همـاهنگی می تواند موجب سرریز ارتباط معنادار و محدود کردن تعداد خزنده های همزمان گردد]۷ و ۲۳[.
۳-۱۱ ساختار وب
ساختار وب را می توان به صورت یک گراف عظیم جهت دار که در برگیرنده ی گره ها و اتصالهای متعدد است در نظر گرفت. در این گراف، صفحات وب معادل گره ها و لینک های بین صفحات معادل یال های گراف هستند که نمایی از ساختار آن در شکل های ۳-۳ و ۳-۴ نشان داده شده است.]۱[
شکل۳-۳ نمایی کلی از ساختار وب
شکل۳-۴ ساختار گراف وب
۳-۱۲ استراتژی های خزش
استراتژی های خزیدن صفحات وب را می توان به سه دسته کلی، جستجوی ناآگاهانه یا کورکورانه[۱۰۹]، جستجوی آگاهانه یا اکتشافی[۱۱۰] و جستجوی محلی[۱۱۱] تقسیم بندی نمود.
۳-۱۲-۱ جستجوی ناآگاهانه
در استراتژی جستجوی ناآگاهانه، ایده ای در رابطه با اینکه چگونه و در چه مسیرهایی هدف جستجو شود، وجـود ندارد و تنهـا اطلاعات موجود عبارت اسـت از تعریف مسـاله و تشخیـص حالـت هـدف از حـالت غیرهـدف. به همین دلیـل این روش جستجـو، کل فضای جستجـو را برای یافتـن هـدف پیمـایش می کند]۱۹ و ۲۲ و ۲۶[. در ذیل به بیان برخی از الگوریتم های این روش جستجو پرداخته شده است:
۳-۱۲-۱-۱ حرکت اول عمق[۱۱۲]
این الگوریتم در سال ۱۹۹۴ کشف شد و به عنوان بهترین الگوریتم خزنده های وب در تحقیقات به کار برده می شد. این الگوریتـم با بهره گرفتن از یک صف LIFO، لینک ها را در نظـم و ترتیبی که با آن مواجـه می شود می خزد. در این استراتژی، واحد کنترل خزنده یک صفحه را به عنوان صفحه هسته[۱۱۳] برای واحد واکشی مشخص می سازد. پس از جداسازی لینک ها، واحد کنترل یکی از لینکهای خارجی صفحه را انتخاب و گره مقصد را به واحد واکشی معرفی می کند. فرایند حرکت در بین صفحات تا زمانیکه سطح عمق مورد نظر برای واحد کنترل تعریف نشود ادامه خواهد یافت در این صورت صفحات بی کیفیت زیادی در پایگاه ذخیره خواهد شد]۲۹ و ۳۳[. در شکل ۳-۵، نمونه ای از حرکت خزنده در بین صفحات مختلف توسط الگوریتم اول عمق را نشان داده است:

شکل۳-۵ حرکت خزنده در بین صفحات با بهره گرفتن از الگوریتم اول عمق]۱[
چنانچه سطح عمق در این گراف یک در نظر گرفته شود ترتیب حرکت به صورت ۱ و ۵ و ۷ و چنانچه این سطح عمق دو در نظر گرفته شود حرکت واحد واکشی به صورت ۱ و ۲ و ۵ و ۶ و ۷ خواهد بود. حرکت اول عمق ساده ترین استراتژی خزش صفحات وب می باشد.
همانطور که بیان شد این روش در هر لحظه یک مسیر از ریشه تا برگ به همراه گره های همزاد[۱۱۴] هر گره در همان مسیر را در حافظه ذخیره می کند. وقتی یک گره و همه فرزندانش در آن مسیر گسترش یافتند، از حافظه حذف می شوند بنابراین این روش به حافظه کمی نیاز دارد و پیچیدگی فضایی این روش خیلی کم و به صورت خطی O(bm) است که b[115] فاکتور انشعاب که به حداکثر تعداد یالهایی که از درخت خارج می شون اشاره دارد و m ماکزیمم عمق درخت می باشد. در بدترین حالت، این روش جستجو همه نودهای درخت جستجو را گسترش می دهد، یعنی پیچیدگی زمانی آن T(bm) خواهد بود]۲۹[.
مشکل این روش جستجو، علاوه بر پیچیدگی زمانی بالا، احتمال گیر افتادن در یک مسیر نامتناهی و نرسیدن به جواب به دلیل یک انتخاب نادرست است، بنابراین این روش کامل نیست. اگر درخت دارای چندین هدف باشد، جستجوی اول عمق همیشه اولین گره ای که به عنوان هدف تشخیص می دهد را برمی گرداند درصورتی که ممکن است در زیردرخت های دیگر درخت، گره هدف بهینه تری وجود داشته باشد، پس این روش جستجو بهینه نیست. همچنین به منظور جلوگیری از گیـر افتادن در یک مسیـر نامتناهی، سطـح
عمقی از ابتدا تعریف شده و فرایند حرکت در بین صفحات تا عمق تعریف شده ادامه می یابد]۱[.
۳-۱۲-۱-۲ حرکت اول سطح[۱۱۶]
در این حرکت، واحد کنترل پس از تعیین صفحه هسته، کلیه گره های هم سطح را مشخص و آن ها را به ترتیـب به واحـد واکشی معرفی می کند. پس از آنکه خزنده کلیه صفحات مشخص شده ی آن سطح را مورد بازدید قرار داد، واحد کنترل به سراغ سطـح دوم رفته و آن را مورد بررسی قرار می دهـد]۱ و ۲۹ و ۳۳ و ۳۷[. در شکل ۳-۶ نمونه ای از حرکت خزنده با بهره گرفتن از الگوریتم اول سطح نشان داده شده است:

شکل۳-۶حرکت خزنده در بین صفحات با بهره گرفتن از الگوریتم اول سطح ]۱[
این روش به دلیل طراحی و اجرای ساده تر، همواره بیشتر مورد توجه طراحان نرم افزارهای خزنده قرار گرفته است. در این روش در صورتی که سیاست مورد استفاده به طور دقیق مشخص شود، حجم پایگاه داده موتور جستجو به دلیل محدود بودن دامنه لینک های هر صفحه به عنوان صفحه هسته، بیهوده افزایش نخواهد یافت]۱۴ و ۳۳ و ۳۸[.
در روش اول عمق، واحد واکشی ابتدا تمامی لینک های یک صفحه را تا عمق تعریف شده بررسی نموده و سپس سراغ صفحه ی بعدی می رود یعنی اطلاعات دریافتی بیشتر حول یک موضوع اختصاصی می باشد. بنابراین می توان حرکت اول عمق را یک حرکت جزء نگر دانست که در آن تمام جزئیات یا لینک های یک صفحه بررسی می شود. اما روش اول سطح روشی کلی نگر است]۱[.
در شکل ۳-۷ یک خزنده با استراتژی اول سطح نمایش داده شده است:
Web page
Link
FIFO Queue
شکل۳-۷ یک خزنده با استراتژی اول سطح ]۳۵[
با توجه به مطالب ذکر شده، الگوریتم یک خزنده با استراتژی اول سطح به صورت نشان داده شده در شکل ۳-۸ خواهد بود:
Breadth-First (starting_urls) {
foreach links (starting_urls) {
enqeueu(frontier, link);
}
While (visited < MAX_PAGES) {
link := dequeue_link(frontier);
doc := fetch(link);
enqeueu (frontier, extract_links(doc) );
if (#frontier > MAX_BUFFER) {
dequeue_last_links(frontier) ;
}
}
}

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...