کاوشگر وب - بخش اول

0 نظر
این مقاله در تاریخ 22:45 - 1391/02/19 ویرایش شده است

این مقاله قسمت اول از مجموعه مقالاتی است که در طی انها به بحث پیرامون کاوشگر وب یا Web Crawling خواهم پرداخت.لازم به ذکر است که منبه این مقالات تحقیق و ترجمه ای را که در مورد این موضوع برای یکی واحد های دوره فوق لیسانسم انجام دادم.در ضمن از همکاری دوستانم جناب مهندس پویا رضایی و مهندس حسن امیری در این مورد تشکر میکنم.

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

کاربردهای فراوانی برای کاوشگر های وبی وجود دارد. یکی کسب و کار همشمند یا business intelligence است که به موجب آن سازمان اطلاعات مربوط به رقبای و همکاران خود را جمع آوری می نماید. یکی دیگر از موارد کاربرد برای نظارت بر وب سایت ها و صفحات مورد علاقه کاربر است، به طوری که یک کاربر و یا مجموعه می توانند به سرعت از قرار گیری و ارائه اطلاعات جدید در بخشی مشخص در وب مطلع شوند.البته کاربردهای مخرب نیز برای یک کاوشگر وجود دارد. به عنوان مثال، آدرس ایمیل که به جهت ارسال اسپم استخراج می شود و یا جمع آوری اطلاعات شخصی از طریق فیشینگ یا phishing و یا سایر حملات اینترنتی، نمونه هایی از آن می باشند.
با این حال گسترده ترین مورد استفاده کاوشگر ها توسط موتورهای جستجو است. در واقع کاوشگر ها مصرف کنندگان اصلی پهنای باند در اینترنت هستند. آنها اطلاعات صفحات وب را برای ایجاد ایندکس های مورد نیاز برای موتورهای جستجو، جمع آوری می نمایند. موتورهای جستجوی شناخته شده ای مانند گوگل ، یاهو و MSN از یک مدل بسیار کارآمد جهانی با طراحی مبتنی بر کاوشگر های برای جمع آوری تمام صفحات، صرف نظر از محتوای آنها استفاده می نمایند. دسته ای از کاوشگر های دیگر که گاهی به نام کاوشگر های ترجیحی - preferential crawlers شناخته می شوند، بصورت هدفمندتر عمل می کند.این نوع کاوشگرا تنها اقدام به دانلود صفحاتی خاص یا مربوط به موضوعی مشخص می نمایند.
 این مجموعه مقالات به معرفی مفاهیم اصلی ، الگوریتم ها و ساختمان داده موجود در پشت کاوشگر وب می پردازد. پس از بحث در مورد مسائل پیاده سازی که در مورد تمامی انواع کاوشگر ها صادق است به توضیح انواع مختلف کاوشگر ها یعنی جهانی-  universal، تمرکز یافته – focused و موضعی – topical خواهیم پرداخت. ما همچنین برخی از مسائل اخلاقی مورد بحث پیرامون کاوشگر هارا نیز مورد مطالعه قرار خواهیم داد. در نهایت نیم نگاهی به استفاده از کاوشگر ها در پشتیبانی از مدل های جایگزینی خواهیم انداخت که در آن کاوشگر ها و فعالیت های کاوشگری در میان یک مجموعه بزرگ از کاربران که بصورت غیر ایستا توسط یک شبکه به هم متصل شده توسط اند، توضیع شده است.


یک الگوریتم کاوشگر ساده
در ساده ترین شکل آن، کاوشگر از مجموعه ای از صفحات فرزند – Seed یاURL ها شروع می کند و سپس با استفاده از لینک های درون آنها به واکشی صفحات دیگر می پردازد. لینکهای موجود در این صفحات نیز به همین منوال استخراج شده و صفحات مربوطه مورد بازدید قرار می گیرد. این روند تا زمانی که تعداد مشخصی از صفحات بازدید شده و یا برخی از اهداف مشخص شده به دست آید، ادامه می یابد. البته این توضیحات ساده بسیاری از مسائل ظریف مربوط به اتصالات شبکه ، تله های عنکبوت – Spider traps ، URL canonicalization ، پارس کردن و تجزیه صفحه و قوانین اخلاقی کاوشگر ها را ارائه نکرده و آنها را مخفی نموده است. بنیانگذاران گوگل یهنی سرگئی برین Sergey Brin و لارنس پیج – Lawrence Page، در مقاله اولیه خود،کاوشگر وب به عنوان یچیده ترین و در عین حال شکننده ترین بخش از یک موتور جستجو معرفی نموده اند.
شکل 1 به ترتیب، مسیر پایه عملکرد یک کاوشگر را نشان می دهد. این نوع کاوشگر در هر لحظه یک صفحه را واکشی می نماید که نشان دهنده استفاده ناکارآمد از منابع آن است. بعدها در این فصل فصل بحث می کنیم که چگونه می توان بهره وری را با استفاده سیستم چند پردازش – multiple process، ریسمان ها – thread، و دسترسی به منابع بصورت غیر همزمان – asynchronous بهبود دارد. کاوشگر لیستی از آدرس ها دیده نشده را تحت عنوان مرز یا Frontier نگهداری می نماید. این لیست در ابتدا با URL ها فرزند که ممکن است توسط کاربر و یا یک برنامه دیگر ارائه شده با شد مقداردهی می شود. در هربار تکرار حلقه ی اصلی، کاوشگر URL بعدی را از لیست برداشته و به واکشی صفحه مربوط به آن آدرس از طریق HTTP پرداخته و در ادامه عملیات پارس کردن و تجزیه صفحه بازیابی شده را برای استخراج آدرس ها موجود در آن انجام می دهد. در نهایت این URL های تازه کشف شده را نیز به لیست موجود اضافه می نماید. در همین حین اطلاعات دیگری نیز استخراج و احتمالا ایندکس گذاری و در یک مخزن  ذخیره میگردد.پروسه عملیات کاوشگر ممکن است زمانی که تعداد معینی از صفحات مورد قرار گرفت به پایان برسد و یا ممکن است پایان عملیات منوط به خالی شدن لیست آدرس ها باشد، البته هر چند این مورد در عمل با توجه به میزان بالا تعداد لینک های (تقریبا به ازای هر صفحه در وب حدود 10 لینک خارجی) به ندرت اتفاق می افتد. یک کاوشگر، در اصل ، یک الگوریتم جستجوی گراف - graph search algorithm است. یک وب سایت را میتوان به عنوان یک گراف بزرگ تصور کرد که در آن، صفحات به عنوان گره ها و لینک های موجود به عنوان یال ها دیده می شوند. کاوشگر از تعدادی از گره ها (Seedها) شروع می کند و سپس از طریق یال ها برای رسیدن به گره های دیگر.استفاده می نماید. روند واکشی یک صفحه و استخراج پیوندهای درون آن، مشابه به بسط دادن یک گره در جستجوی گراف است.
Frontier ساختار داده ی اصلی است که حاوی URLهای مشاهده نشده می باشد.معمولا کاوشگر ها سعی می کنند که Frontier را برای بدست آوردن بهره وری بالا در حافظه اصلی ذخیره نمایند. با توجه به قیمت رو به کاهش حافظه و گسترش پردازنده های 64 بیتی،  افزایش سایز Frontier امری امکان پذیر است. با این حال طراح کاوشگر باید تصمیم بگیرد که از بینURL ها کدام یک دارای اولویت پایین تر بوده  و در زمان پر شدن Frontier قابل دور انداختن می باشد. توجه داشته باشید که با وجود اندازه های بزرگ برای Frontier، به علت گسترده بودن فضای عملیات و صفحات، Frontier به سرعت پر خواهد شد. مهمتر از آن ، الگوریتمی است که کاوشگر می بایست برای تشخیص URLهای بعدی که باید از Frontier برای واکشی استخراج شود، مورد استفاده قرار دهد. این ساز و کارها الگوریتم جستجو گراف  پیاده سازی شده توسط کاوشگر را مشخص می کند.

شکل1 نمودار مسیر پایه عملکرد یک کاوشگر. عملیات بر روی داده­ها اصلی در سمت چپ و بصورت خط چین نشان داده شده است.

 

کاوشگر اول پهنا
Frontier ممکن است برای یک کاوشگر اول پهنا یا breadth-first به صورت یک صف first-in-first-out (FIFO) پیاده سازی شود. در این مدل URL بعدی برای واکشی از سر صف برداشته شده وURLهای جدید نیز به انتهای صف اضافه می شود. هنگامی که Frontier به حداکثر اندازه خود را می رسد، کاوشگر تنها قادر خواهد بود از هر صفحه تنها یک URL مشاهده نشده را به صف اضافه نماید.
استراتژی اول پهنا به این معنی نیست که صفحات با ترتیب "تصادفی" مورد بازدید قرار بگیرد. برای درک آن باید ابتدا گراف وب با یال های به شدت نامتوازن و طولانی را در نظر بگیریم. بعضی از صفحات حاوی تعدادی لینک هستند که با ترتیبی طولانی در نهایت به یکدیگر اشاره می نمایند و این ترتیب از آنچه مورد نظر است طولانی تر می باشد. در واقع تعداد یال ها در زمانی که یال k بر اساس قانون توان Pr(k) ≈ k- γ توضیع شده است برای توان γ <3 چندان مهم نیست [437]. برای گراف وب، این حالت برابر با γ≈ 2.1 می باشد[69]. این بدان معنا است که نوسانات یال ها بینهایت است. به عنوان مثال، انحراف معیار تنها به بخش محدودی از گراف وابسته شده است. به طور معمول صفحات محبوب حاوی لینک های ورودی بسیاری در صفحات دیگر می باشند که همین امر همانند یک عامل جذب کننده برای یک کاوشگر اول پهنا عمل می کند. بنابراین تعجب آور نیست که ترتیب بازدید صفحات توسط کاوشگر اول پهنا به طور مستقیم با رتبه و PageRank یا ارزش یال ها آن صفحه مرتبط است. یک از دلایل مهم این پدیده تمایل ذاتی موتورهای جستجو برای اندیس کردن صفحات با لینک های خوب است.
یکی دیگر از دلایلی نشان میدهد کاوشگرای اول پهنا "تصادفی" نیستند این است که آنها به شدت تحت تاثیر انتخاب صفحات Seed قرار می گیرند. تحقیقات موردی نشان می دهد که صفحاتی که از طریق برسی صفحات پایه یا Seed یافته میشوند نسبت به صفحاتی که بصورت تصادفی انتخاب می شوند دارای ارتباط معنایی می باشند. این موضوع و دیگر علاقمندی ها برای کاوشگرای جهانی یا universal crawlers (بخش 3-8) مهم هستند.
همانطور که قبلا ذکر شد ، تنهاURLهای دیده نشده به Frontier اضافه می شود. این امر مستلزم نوعی ساختار داده می باشد که توسط URLهای واکشی شده بدست می آید. تاریخچه خزیدن یا crawl history یک لیستی از URL ها به همراه زمان یا time-stamp مربوطه به واکشی صفحه مربوطه توسط کاوشگر می باشد. یک URL تنها هنگامی به این لیست افزوده می شود که صفحه مربوط به آن دیده شده باشد. این تاریخ ممکن است بعنوان پیش نیازی برای عملیات واکشی توسط کاوشگر در آینده و یا تجزیه، تحلیل و ارزیابی مورد استفاده قرار گیرد. به عنوان مثال، ما می خواهیم از منابع مربوطه و یا مهمتر در ابتدا برای فرایند جستجو و کاوش استفاده نماییم در حالی که تاریخچه ممکن است بر روی دیسک ذخیره شود. به این ترتیب یک ساختار داده ای در حافظه برای دسترسی سریع بصورت Look-up برای بررسی اینکه آیا یک صفحه قبلا واکشی شده یا خیر لازم است. این بررسی برای جلوگیری از بازبینی صفحات واکشی شده و یا به هدر رفتن فضا درFrontier لازم است. به طور معمول یک جدول hash برای دسترسی سریع و سرعت درج بالا در موردURL  مناسب است(O (1)) . پروسه look-up دو URL را که به یک صفحه اشاره می کنند مشابه تشخیس میدهد. این امر نیاز به URL های استاندارد را مشخص می نماید.(بخش دوم مقاله)
یکی دیگر از جزئیات مهم نیاز به جلوگیری از افزوده شدنURL های تکراری به Frontier است.یک جدول hash جداگانه نیز می توان برای ایجاد امکان دسترسی سریع به URLهای ذخیره شده در Frontier و تشخیص تکراری بودن آنها مورد استفاده قرار بگیرد.

 کاوشگرای ترجیحی
در صورتی که Frontier به جای یک صف FIFO بصورت یک صف ترجیحی ارائه شود، یک استراتژی کاوشگر متفاوت به دست می آید. به طور معمول ، یک کاوشگر ترجیحی برای هر لینک دیده نشده بر اساس برآورد ارزش صفحه ای که به آن اشاره میکند یک اولویت مشخص می نماید. این برآورد را می توان بر اساس خواص توپولوژیکی - به عنوان مثال تعداد یال هایی که به صفحه هدف اشاره میکنند -،خصوصیات محتوا - به عنوان مثال، شباهت بین پرس و جو های کاربر و صفحه منبع و یا هر ترکیب دیگر از ویژگی های قابل اندازه گیری باشد. به عنوان مثال، هدف کاوشگر موضعی یا Topical crawler دنبال کردن خطوط ارتباطی است که انتظار می رود منجر یافتن بخشهایی از گراف وب که مربوط به یک موضوع انتخاب شده توسط کاربر باشد گردد. در اینجا انتخاب محل شروع یا Seed حتی از کاوشگر اول پهنا مهم تر است. ما الگوریتم های مختلف کاوشگر ترجیحی را در بخش چهارم و پنجم مقاله  مورد بحث قرار خواهیم داد. در حال حاضر اجازه دهید فرض کنیم تابعی برای تعیین اولویت یا نمره برای URL های دیده نشده وجود دارد. درصورتی که صفحات به ترتیب مشخص شده توسط ارزش های اولویت در Frontier مورد بازدید قراربگیرند، در این حالت ما یک کاوشگر بهترین-اولین یا Best-first خواهیم داشت.
صف اولویت ممکن است آرایه ای پویا باشد که همیشه بر اساس امتیاز URLها مرتب شده است. در هر مرحله، بهترینURL  از ابتدای صف برداشته میشود. هنگامی که صفحه مربوطه برداشته شد، آدرس های استخراج شده از آن نیز می بایست به نوبه خود امتیاز دهی شوند و سپس به شکلی به Frontier افزوده گردند که ترتیب صف اولویت حفظ شود.همانند کاوشگر اول پهنا، در کاوشگر بهترین-اولین نیز نیاز به جلوگیری افزوده شدن URLهای تکراری به Frontier وجود دارد. یک روش کار آمد، استفاده از یک جدول جداگانه hash بعنوان یک راه برای رسیدن به این هدف است. پیچیدگی زمان وارد کردن یکURL  در صف اولویت O (logF)  است که در آن، F اندازه Frontier است. (برسی جدول hash به یک زمان ثابت نیاز دارد). برای استخراج یا dequeue کردن یک URL، ابتدا میبایست از صف اولویت برداشته شده (O (logF)) و سپس از جدول hash نیز حذف شود (O (1)). بنابراین، استفاده موازی از این دو ساختار داده برای هر URL هزینه ای لگاریتمی ایجاد خواهد نمود. هنگامی که Frontier به حداکثر اندازه خود رسید، تنها بهترین URL ها نگه داری خواهند شد و Frontier می بایست بعد از افزودن هر مجموعه جدید از لینک ها مورد بازبینی قرار گرفته و موارد اضافی حذف شود و اصطلاحا هرس شود.
 


مقالات مرتبط
سید علیرضا قمصری

سلام. من یک برنامه نویس آشنا به C#.NET3.5,MVC.NET 3 ,ASP.NET3.5,SqlServer 2008,Reporting هستم، ساکن تهران که از سال 1385 به برنامه نویسی مشغول بوده و خوشبختانه در محیط وب و ویندوز دارای تجربیات عملیاتی شده متعددی نیز می باشم. خوشحال خواهم شد که در سایت خودم به آدرس qamsari.com میزبان شما باشم.

برای ثبت نظر می بایست ابتدا وارد شوید در صورتی که عضو نیستید یک حساب جدید ایجاد نمایید.