طراحی و ساخت خزنده وب برای موتور جستجوی وب

چکیده

جمع آوری و پردازش اطلاعات در وب نیاز به استفاده از تکنولوژی های مختلفی چون ساخت خزنده، ذخیره سازی داده ها و پردازش اطلاعات دارد.

واژه های کلیدی: خزنده وب، ربات، عنکبوت، موتور جستجوی وب

معرفی پژوهش

مبانی نظری و پیشینه پژوهش

مقدمه

استفاده از اینترنت به عنوان ابزار دسترسی سریع، امروزه بیشتر مورد توجه کاربران قرار گرفته و برای شناخت و دستیابی به وب سایتهای مختلف نیازمند به استفاده از موتورهای جستجو می باشیم. همانطور که میدانیم موتورهای جستجوی مختلفی کمک اصلی را بدست گرفته اند که امروزه، Google در حدود 73 درصد، Baidu در حدود 13 درصد، Bing در حدود 8 درصد، Yahoo در حدود 4 درصد، Yendex در حدود 1 درصد و به ترتیب مابقی، Ask، DuckDuckGo، Naver و چندی دیگر زیر یک درصد سهم موتورهای جستجوی دنیا را بدست گرفته اند. [1] از این آمار میتوان نتایج جالبی گرفت:

  • گوگل بزرگترین موتور جستجو، کنجکاوی های 73 درصد مردم دنیا رو جواب می دهد؛ پس این شرکت میداند که مردم دنیا بیشتر دنبال چی هستن، مثلا گوگل دریافت بشتر مردم به یک سیستم عامل راحت برای گوشیهای همراهشان نیاز دارند و به راحتی با استفاده از پلتفرم اندروید این سیستم عامل را در بین بیشترین گوشیهای همراه دنیا رواج داد. پس حالا از طریق تلفن های همراه اطلاعات مورد نیاز را جمع آوری می کند که دوباره مثلا اطلاعات ترافیکی کوچه و خیابان ها را به راحتی به ما نمایش می دهد! حالا این سوال پیش می آید که گوگل الان در حال نتیجه گیری چیست؟
  • دومین موتور جستجوی دنیا موتور جستجوی Baidu می باشد. 73 درصد از مردم چین از این موتور جستجو استفاده می کنند در حالی که در میان کاربران چینی گوگل تنها در حدود 2 درصد مورد استفاده قرار می گیرد. [2] پس این سوال پیش می آید که چرا مردم چین از موتور جستجو بومی استفاده می کنند؟
  • سومین موتور جستو Bing که مربوط به شرکت مایکروسافت است، موتور جستجوی Yahoo رو هم ازان خود کرده، در واقع فرقی بین بینگ و یاهو وجود ندارد. باز این سئوال پیش می آید که مایکروسافت چرا تلاش برای معروف کردن موتور جستجوی خود دارد؟
  • پنجمین موتور جستجو Yendex، برای کشور روسیه می باشد که در حدود 40 درصد در میان مردم روسیه مورد توجه قرار گرفته و گوگل در حدود 60 درصد در بین کاربران روسیه طرفدار دارد. [3] آیا این مسئله مهمی در میان سیاست مردان روسیه بوده؟

و سوال آخر؛ آیا ما در ایران موتور جستجو کاربر پسند و کاربردی داریم؟

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

جمع آوری و پردازش اطلاعات در وب نیاز به استفاده از تکنولوژی های مختلفی چون ساخت خزنده، ذخیره سازی داده ها و پردازش اطلاعات دارد.

در گام نخست به ساختار خزنده وب و طراحی و ساخت آن می پردازیم.

معماری خزنده وب [4]
تعریف:

خزنده وب برنامه ای است که با توجه به یک یا چند آدرس اینترنتی ریشه، صفحات وب مرتبط با این آدرس ها را بارگیری و لینک های موجود در آنها را استخراج می کند و سپس به صورت چرخشی به ادامه بارگیری صفحات وب مشخص شده توسط این لینک ها ادامه می دهد.

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

بر خلاف سادگی مفهومی، اجرای خزنده های وب با کارایی بالا به دلیل مقیاس بزرگی وب چالش های اساسی در مهندسی ایجاد می کند. به منظور خزش بخش قابل توجهی از "سطح وب" در مدت زمان معقول، خزندگان وب باید هزاران صفحه در ثانیه بارگیری و معمولا در ده ها یا صدها رایانه توزیع کنند.

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

سرانجام، نیاز به "احترام و ادب" برای ارائه دهندگان محتوا و اضافه نکردن ترافیک بیش از حد به وب سرورهای آنها و تمایل به اولویت بندی خزش به سمت صفحات با کیفیت بالا و نگهداری تازگی محتوا بدنه باعث ایجاد چالش های مهندسی دیگری می شود.

پیشینه تاریخی:

خزنده های وب تقریباً به اندازه خود وب قدیمی هستند. در بهار سال 1993، فقط چند ماه پس از انتشار NCSA Mosaic آقای Matthew Gray اولین خزنده وب World Wide Web Wanderer را نوشت، که از سال 1993 تا 1996 برای جمع آوری آمار در مورد رشد وب استفاده شد. یک سال بعد David Eichmann اولین مقاله تحقیقاتی را که شرح مختصری از یک خزنده وب، عنکبوت RBSE را نوشت. Burner اولین شرح مفصلی درباره معماری یک خزنده وب، یعنی خزنده اصلی Archive Internet را ارائه داد. مقاله اصلی Brin و Page’s در مورد معماری (اولیه) موتور جستجوی گوگل شرح مختصری از خزنده گوگل را نشان می دهد، که از یک سیستم توزیع شده از مراحل پردازش صفحه و یک بانک اطلاعاتی مرکزی برای هماهنگی خزیدن استفاده می کند. Heydon و Najork یک خزنده وب توزیع شده و گسترده به نام Mercator را توصیف کردند که قرار بود طرح تعدادی از خزندگان دیگر شود. سایر سیستم های خزنده توزیع شده در ادبیات شامل PolyBot، UbiCrawler، C-proc و Dominos.

مبانی:

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

با این وجود، ساختن یک خزنده در مقیاس وب، چالش های اساسی مهندسی را ایجاد می کند، که همه در نهایت به بزرگی مقیاس مربوط می شود. به منظور حفظ اطلاعات مربوط به موتور جستجو در حالت نگهداری تازگی محتوا برای ده میلیارد صفحه وب با صفحاتی که به طور میانگین هر 4 هفته یک بار ویرایش می شوند، خزنده باید بیش از 4000 صفحه در ثانیه بارگیری کند. برای رسیدن به این هدف، خزنده باید در چندین رایانه توزیع شود و هر دستگاه خزنده، باید بارگیری های چندگانه را به صورت موازی دنبال کند. اما اگر خزنده وب توزیع شده و کاملاً موازی درخواستهای همزمان زیادی را به یک وب سرور واحد ارسال کند، به احتمال زیاد این سرور وب را دچار اضافه بار و خراب می کند.

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

در برخی از طراحی های خزنده وب (به عنوان مثال ، خزنده اصلی Google و PolyBot)، فرآیندهای بارگیری صفحه، توزیع می شوند. در حالی که ساختارهای اصلی داده ها یعنی مجموعه آدرس های اینترنتی کشف شده و مجموعه آدرس هایی که باید بارگیری شوند، توسط یک دستگاه واحد نگهداری می شوند. این طرح از نظر مفهومی ساده است، اما به طور نامحدود مقیاس ندارد. سرانجام ساختار داده های مرکزی به یک تنگنا تبدیل می شوند. راه حل دیگر تقسیم ساختارهای مهم داده بر ماشینهای خزنده است. در حالت ایده آل، این کار باید به گونه ای انجام شود که ارتباط بین خزنده ها به حداقل برسد. یك راه برای دستیابی به این هدف، اختصاص آدرس به دستگاههای خزنده بر اساس نام میزبان آنها است. تقسیم بندی آدرس ها با نام میزبان بدان معنی است که تصمیمات برنامه ریزی خزیدن ناشی از سیاست های احترام سرور ها می تواند به صورت محلی و بدون هیچ گونه ارتباطی با گره های همسالان انجام شود. علاوه بر این، از آنجا که اکثر لینک ها به صفحات در همان سرور وب مراجعه می کنند، اکثر پیوندهای استخراج شده از صفحات وب بارگیری شده علیه آنها آزمایش می شوند و به ساختار داده های محلی اضافه می شوند، نه به خزندگان همکار. این طرح را Mercator و C-proc اتخاذ کردند.

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

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

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

علاوه بر این داده ساختار های اصلی، بسیاری از خزندگان وب در مقیاس وب نیز برخی از ساختارهای داده کمکی را حفظ می کنند، مانند حافظه کش برای نتایج جستجوی DNS. باز هم، این داده ساختار ها ممکن است در بین دستگاههای خزنده تقسیم شوند.

برنامه های کلیدی:

خزنده وب عنصر اصلی موتورهای جستجوگر وب می باشد، از آنها برای جمع آوری صفحاتی که قرار است ایندکس شوند استفاده می شود. خزندگان برنامه های کاربردی فراتر از جستجوی کلی دارند، به عنوان مثال در کاوش داده های وب (به عنوان مثال ،Attributor، خدماتی که وب را به دلیل نقض حق نسخه برداری یا ShopWiki، یک سرویس مقایسه قیمت استخراج می کند).

کارهای آینده:

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

Heritrix یک خزنده توزیع شده ، گسترده ، در مقیاس وب است که به زبان جاوا نوشته شده و به عنوان منبع باز توسط بایگانی اینترنت توزیع می شود.

سندهایی وب

انواع سندی که یک خزنده وب وظیفه بارگیری آنرا به عهده دارد را می توان صورت زیر بیان کرد

  • صفحهات وب (مانند صفحات HTML و یا صفحات متنی با پسوند txt و غیره)
  • تصاویر (مانند فایل های با پسوند png ،gif ،jpg و غیره)
  • ویدیو ها (مانند فایل هایی با پسوند mpeg ،mp4 و غیره)
  • فایل های PDF
انتخاب محتوا در یک صفحه وب
مقدمه

بعد از اینکه یک صفحه وب توسط خزنده وب استخراج شد، محتوای مورد نظر را باید پیدا کرد. ابزارهای مختلفی برای انتخاب محتوای صفحه وب طراحی شده اند که می تواند محتوای مورد نظر را انتخاب و به طور کارآمد استخراج کرد. مهمترین آنها را می توان به ترتیب زیر نام برد

  • Regular expression: (عبارات باقاعده) تطبیق رشته در متن با استفاده از الگو مانند استخراج تاریخ با الگوی yyyy-mm-dd.
  • XPath[7]: بخشهایی از یک سند با ساختار درخت را مشخص می کند، سندهای XML یا HTML. آنها می توانند گره ها را به خوبی انتخاب و استخراج کنند.
  • CSS Selectors: (انتخابگر CSS) عملکردی مشابه XPath در انتخاب قسمتهای یک سند HTML دارند، اما برای توسعه وب طراحی شده اند. همانطور که می دانیم از CSS برای دسترسی به عناصر صفحات وب و صفحه آرایی استفاده می شود.
Web Crawling
Abstract

This is a survey of the science and practice of web crawling. While at first glance web crawling may appear to be merely an application of breadth-first-search, the truth is that there are many challenges ranging from systems concerns such as managing very large data structures to theoretical questions such as how often to revisit evolving content sources. This survey outlines the fundamental challenges and describes the state-of-the-art models and solutions. It also highlights avenues for future work.

Introduction

A web crawler (also known as a robot or a spider) is a system for the bulk downloading of web pages. Web crawlers are used for a variety of purposes. Most prominently, they are one of the main components of web search engines, systems that assemble a corpus of web pages, index them, and allow users to issue queries against the index and find the web pages that match the queries. A related use is web archiving (a service provided by e.g., the Internet archive [77]), where large sets of web pages are periodically collected and archived for posterity. A third use is web data mining, where web pages are analyzed for statistical properties, or where data analytics is performed on them (an example would be Attributor [7], a company that monitors the web for copyright and trademark infringements). Finally, web monitoring services allow their clients to submit standing queries, or triggers, and they continuously crawl the web and notify clients of pages that match those queries (an example would be GigaAlert [64]).

The raison d’ˆetre for web crawlers lies in the fact that the web is not a centrally managed repository of information, but rather consists of hundreds of millions of independent web content providers, each one providing their own services, and many competing with one another. In other words, the web can be viewed as a federated information repository, held together by a set of agreed-upon protocols and data formats, such as the Transmission Control Protocol (TCP), the Domain Name Service (DNS), the Hypertext Transfer Protocol (HTTP), the Hypertext Markup Language (HTML) and the robots exclusion protocol. So, content aggregators (such as search engines or web data miners) have two choices: They can either adopt a pull model where they will proactively scour the web for new or updated information, or they could try to establish a convention and a set of protocols enabling content providers to push content of interest to the aggregators. Indeed, the Harvest system [24], one of the earliest search services, adopted such a push model. However, this approach did not succeed, and virtually all content aggregators adopted the pull approach, with a few provisos to allow content providers to exclude all or part of their content from being crawled (the robots exclusion protocol) and to provide hints about their content, its importance and its rate of change (the Sitemaps protocol [110]).

There are several reasons why the push model did not become the primary means of acquiring content for search engines and other content aggregators: The fact that web servers are highly autonomous means that the barrier of entry to becoming a content provider is quite low, and the fact that the web protocols were at least initially extremely simple lowered the barrier even further — in fact, this simplicity is viewed by many as the reason why the web succeeded where earlier hypertext systems had failed. Adding push protocols would have complicated the set of web protocols and thus raised the barrier of entry for content providers, while the pull model does not require any extra protocols. By the same token, the pull model lowers the barrier of entry for content aggregators as well: Launching a crawler does not require any a priori buy-in from content providers, and indeed there are over 1,500 operating crawlers [47], extending far beyond the systems employed by the big search engines. Finally, the push model requires a trust relationship between content provider and content aggregator, something that is not given on the web at large — indeed, the relationship between content providers and search engines is characterized by both mutual dependence and adversarial dynamics (see Section 6).

Challenges

The basic web crawling algorithm is simple: Given a set of seed Uniform Resource Locators (URLs), a crawler downloads all the web pages addressed by the URLs, extracts the hyperlinks contained in the pages, and iteratively downloads the web pages addressed by these hyperlinks. Despite the apparent simplicity of this basic algorithm, web crawling has many inherent challenges:

  • Scale. The web is very large and continually evolving. Crawlers that seek broad coverage and good freshness must achieve extremely high throughput, which poses many difficult engineering problems. Modern search engine companies employ thousands of computers and dozens of high-speed network links.
  • Content selection tradeoffs. Even the highest-throughput crawlers do not purport to crawl the whole web, or keep up with all the changes. Instead, crawling is performed selectively and in a carefully controlled order. The goals are to acquire high-value content quickly, ensure eventual coverage of all reasonable content, and bypass low-quality, irrelevant, redundant, and malicious content. The crawler must balance competing objectives such as coverage and freshness, while obeying constraints such as per-site rate limitations. A balance must also be struck between exploration of potentially useful content, and exploitation of content already known to be useful.
  • Social obligations. Crawlers should be “good citizens” of the web, i.e., not impose too much of a burden on the web sites they crawl. In fact, without the right safety mechanisms a high-throughput crawler can inadvertently carry out a denial-of-service attack.
  • Adversaries. Some content providers seek to inject useless or misleading content into the corpus assembled by the crawler. Such behavior is often motivated by financial incentives, for example (mis)directing traffic to commercial web sites.
Outline

Web crawling is a many-faceted topic, and as with most interesting topics it cannot be split into fully orthogonal subtopics. Bearing that in mind, we structure the survey according to five relatively distinct lines of work that occur in the literature:

  • Building an efficient, robust and scalable crawler (Section 2).
  • Selecting a traversal order of the web graph, assuming content is well-behaved and is interconnected via HTML hyperlinks (Section 4).
  • Scheduling revisitation of previously crawled content (Section 5).
  • Avoiding problematic and undesirable content (Section 6).
  • Crawling so-called “deep web” content, which must be accessed via HTML forms rather than hyperlinks (Section 7).

روش پژوهش

مقدمه

با توجه به تصمیم گیری به طراحی و ساخت خزنده وب و مشخص بودن هدف پژوهش و توسعه دانش کاربردی و مواجعه شدن با چالش های متعدد مهندسی

تجزیه و تحلیل یافته ها

نتیجه گیری و پیشنهاد ها

منابع (Harvard Type)

[1] November, 2018 market share reports are now live. Link by:
https://netmarketshare.com/search-engine-market-share.aspx

[3] By East-West Digital News / August 1, 2018 , link by:
http://www.ewdn.com/2018/08/01/yandex-consolidates-leadership-on-russian-search-market

[5] Olston, C. and Najork, M., 2010. Web crawling. Now Publishers Inc.
https://homepages.dcc.ufmg.br/~nivio/cursos/ri12/transp/olston-najork@web-crawling10.pdf

[6] Manning, C., Raghavan, P. and Schütze, H., 2010. Introduction to information retrieval. Natural Language Engineering, 16(1), pp.100-103.
http://eprints.bimcoordinator.co.uk/35/1/Introduction to Information Retrieval.pdf
https://nlp.stanford.edu/IR-book/html/htmledition/irbook.html

[7] Clark, J. and DeRose, S., 1999. XML path language (XPath).
https://www.w3.org/TR/xpath/