فهرست مطالبعنوان صفحهچکیده1فصل اول: کلیات21-1 مقدمه31-2 بیان مسأله41-3 اهمیت و ضرورت انجام تحقیق51-4 ساختار پایان نامه6فصل دوم: مبانی و مفاهیم پایه 72-1 مقدمه82-2 انواع موتورهای جستجو13 2-2-1 موتورهای کلید واژه ای132-2-2 موتورهای جستجو بر اساس فهرست راهنمای موضوعی132-2-3 موتورهای جستجوی مبتنی بر خزنده152-2-3-1 تفاوت موتورهای دایرکتوری با موتورهای مبتنی بر خزنده162-2-4 موتورهای جستجوی ترکیبی162-2-5 موتورهاي جستجوی متا172-2-5-1 فهرستي از موتورهاي جستجو172-2-5-2 جستجوي متوالي172-2-5-3 جستجوي هم زمان172-2-6 موتورهاي جستجوي هوشمند182-2-7 موتورهای جستجوگر مبتنی بر هزینه182-3 معماری موتورهای جستجو202-4 اجزای معماری موتورهای جستجو222-5 استراتژی های روزآمد سازی مخزن272-5-1 روش دسته ای يا خزنده دائمی272-5-2 جستجوهای نسبی یا کامل322-6 دو نمايه اصلي واحد نمايه ساز282-7 یک مثال از نحوه عملکرد موتور جستجو312-8 مراحل كار موتورهاي جستجو.......................... 312-8-1 پیش پردازش دادها312-8-2 الویت بندی نتایج322-9 برچسب ها332-9-1 برچسب های توصیفی متن332-9-2- بر چسب alt tag332-10 فایلrobots.txt342-11 موقعیت و مسافت342-12 مشکلات خزنده352-13 روشهای بهینه سازی موتورهای جستجو352-13-1شاخص گذاری352-13-2 جلوگیری از خزش و استاندارد خروج روبات ها352-13-3 افزایش اهمیت362-14الگوريتم هاي رتبه بندي372-14-1 پارامتر های رتبه دهی372-14-2 وزن دهی به کلمات372-14-3 ارزیابی کلمات کلیدی372-14-4 پارامتر های وزن دهی382-14-5 بازیابی تحمل پذیر382-14-6 الگوریتم کلی غلط یابی املایی در موتور های جستجو382-14-7 غلط یابی املایی392-14-8 الگوریتم فاصله ویرایشی392-14-9 الگوریتم مجاورت کی-گرم402-14-10 غلط یابی حساس به متن402-14-11 مفهوم ربط412-14-11-1 ربط از نظر کاربر422-14-11-2 ربط از نظر سیستم بازیابی422-14-12 نظر خواهی از کاربر در رتبه بندی432-14-13 موتورهاي جستجوي اصلي432-14-13-1Google432-14-13-2 Excite442-14-13-3 Altavista442-14-13-4 Yahoo442-14-13-5 Fast442-14-13-6 Lycos442-14-14 موتورهاي جستجوي خبري452-14-15 متا كراولر462-14-16 موتورهاي جستجوي منفعتي482-14-17 موتورهاي جستجوي ليست پرداخت492-14-18 موتورهاي جستجوي اختصاصي492-14-19 جستجوي پاسخ502-14-20 موتورهاي جستجوي كودكان512-14-21 موتورهاي جستجوي منطقه اي512-15 نتیجه گیری52فصل سوم: معماری خزنده وب و استراتژی های خزش533-1 مقدمه543-2 معماري خزنده هاي وب543-3 انتخاب صفحه563-4 اهمیت صفحه573-5 چالش های اجرای یک خزنده57 3-5-1 انتخاب صفحات برای دانلود573-5-1 انتخاب صفحات برای دانلود57 3-6 پيچيدگي هاي فرآيند خزیدن583-6-1 استراتژي هاي سنجش انتخاب صفحات58 3-6-1-1 معیار مبتنی بر گرایشات کاربران583-6-1-2 معیار مبتنی بر شهرت صفحات58 3-6-1-3 معیار مبتنی بر محل قرار گرفتن صفحات583-7 چگونگی آغاز و ختم فرآیند استخراج و ذخیره سازی صفحات وب593-7-1 خزش و توقف................................. 59 3-7-2 خزش و توقف مبتنی بر مقدار آستانه........... 593-8 استراتژی های روزآمدسازی صفحات603-8-1 سیاست روزآمد سازی یکپارچه603-8-2 سیاست روزآمد سازی نسبی603-9 به حداقل رساندن بار روی وب سایت های بازدید شده603-10 موازی سازی روند خزنده603-11 ساختار وب613-12 استراتژی های خزش623-12-1 جستجوی ناآگاهانه623-12-1-1 حركت اول عمق623-12-1-2 حركت اول سطح633-12-1-3 جستجو با هزینه یکنواخت653-12-2 جستجوی آگاهانه یا اکتشافی663-12-2-1 حركت بهترين-شروع673-12-2-2 جستجوی *A693-12-3 جستجوی محلی693-12-3-1 جستجوی تپه نوردی703-12-3-2 جستجوی پرتو محلی703-12-3-3 جستجوی شبیه سازی حرارت713-12-3-4 الگوریتم آستانه پذیرش723-12-3-2 جستجوی پرتو محلی703-13 نتیجه گیری73فصل چهارم: تجزیه و تحلیل نتایج حاصل از تحقیق744-1 مقدمه754-2 مرحله اول: بررسی روشاول سطح754-3 مرحله دوم: بررسی روش اول عمق804-4 مرحله سوم: بررسی روش ترکیبی864-4-1 ترکیب اول: پیمایش اولین سطح به صورت BFS864-4-2 ترکیب دوم: پیمایش اولین و دومین سطح به صورت BFS864-4-3 ترکیب سوم: پیمایش اولین و دومین و سومین سطح به صورت BFS864-5 مرحله چهارم: بررسی روش بهترین-شروع864-6 مرحله پنجم: بررسی روش تپه نوردی874-7 نتایج تجربی بدست آمده884-8 تعداد صفحات دانلود شده برای هر پرس و جو904-9 نتیجه گیری91فصل پنجم: نتیجه گیری و ارائه پیشنهادات975-1 نتیجه گیری و جمع بندی نهایی935-2 پیشنهادات و کارهای آینده100منابع101 فهرست جداولعنوان صفحهجدول 4-1 میزان مرتبط بودن صفحات با استفاده از روش های اول سطح، اول عمق، بهتـرین- شروع و تپه نوردی88جدول 4-2 میزان مرتبط بودن صفحات با استفاده از روش های ترکیبی اول، دوم و سوم89جدول 4-3 تعداد صفحات خزش شده برای هر پرس و جو در الگوریتم های مختلف90 فهرست اشکالعنوان صفحهشکل 2-1 درصد تغییرات صفحه8شکل 2-2 متوسط تغییرات صفحه در هر 10 روز8شکل 2-3 موتور جستجوی یاهو16شكل 2-4 معماري موتورهاي جستجو20شكل2-5 كدهایHTMLسازنده یك صفحه وب 23شكل2-6 خزش در وب24شكل2-7 ماتريس اطلاعات كليدواژه ها25شكل 2-8 نحوه استخراج و شاخص دهي32شکل 3-1 معماری خزنده وب55شکل 3-2 الگوریتم پایه خزنده وب56شکل3-3 نمایی کلی از ساختار وب61شکل3-4 ساختار گراف وب61شکل3-5 حركت خزنده در بين صفحات با استفاده از الگوريتم اول عمق62شکل3-6حركت خزنده در بين صفحات با استفاده از الگوريتم اول سطح63شکل3-7 يك خزنده با استراتژي اول سطح63شکل 3-8 الگوریتم خزنده با استراتژی اول سطح64شکل 3-9 محاسبه پيچيدگی زمانی يک درخت جستجوی دودويی با استفاده از جستجوی اول سطح33شکل 3-10 مراحل رسیدن به هدف با استفاده از روش UCS66شکل 3-11 يك خزنده با استراتژي بهترين-شروع68شکل 3-12 الگوریتم خزنده با استراتژی بهترین-شروع69شکل 3-13 شبه کد جستجوی تپه نوردی70شکل 3-14 شبه الگوریتم پرتومحلی71شکل 3-15 شبه الگوریتم شبیه سازی حرارت72شکل 4-1 لینک های استخراج شده سطح اول با استفاده از تکنیک BFS75شکل 4-2 لینک های استخراج شده سطح دوم با استفاده از تکنیک BFS76شکل 4-3 لینک های استخراج شده سطح سوم با استفاده از تکنیک BFS77شکل 4-4 مسیر طی شده در اولین هسته از پرس و جوی Computer networks در روش اول سطح77شکل4-5 مسیر طی شده در دومین هسته از پرس و جوی Computer networks در روش اول سطح78شکل4-6 مسیر طی شده در سومین هسته از پرس و جوی Computer networksدر روش اول سطح80شکل 4-7 محتوای S181شکل 4-8 محتوای a1S181شکل 4-9b1S1 a181شکل 4-10 c1b1S1 a182شکل 4-11d1c1b1S1 a182شکل 4-12 مسیر طی شده در اولین مرحله از روش اول عمق82شکل 4-13 مسیر طی شده در nامین مرحله از روش اول عمق در هسته اول84شکل 4-14 مسیر طی شده در اولین مرحله از روش اول عمق84شکل 4-15 مسیر طی شده در nامین مرحله از روش اول عمق90شکل5-1 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی”Computer networks“94شکل 5-2 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی”Artificial Intelligence“94شکل 5-3 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی“Web crawler“95 شکل 5-4 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی”Search engine“95شکل 5-5 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی ”Cloud Computing“96 شکل 5-6 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی ”Software engineering“96 شکل 5-7 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی”Data mining“97 شکل5-8 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی ”Computer architecture“97 شکل 5-9 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی”Operatin system“98شکل5-10 نمودار ستونی درصد مرتبط بودن صفحات در پرس و جوی”Wi-Fi“98 فهرست نشانه ها(فرمول ها)............................................................................................................................................................... 67 Sim(q , p) = ................................................................................................................................. 68 h(n)≤h*(n)h(n)≥0 ..................................................................................................................690 ≤h(n) ≤h*(n) فهرست اختصاراتBFS. Best First SearchDFS. Depth First SearchDNS. Domain Name SystemFTP. File Transfer Protocol HTTP. Hyper Text Transfer ProtocolIP. Internet ProtocolPPC.. Pay Per ClickSA.. Simulated AnnealingTA.. Threhsold AcceptanceURL.. Uniform Resource LocatorTFIDF ………………………....……………...Term Frequency Inverse Document Frequency چکیدهدر عصر اطلاعات، وب امروزه به یکی از قدرتمند ترین و سریع ترین ابزارهای ارتباطات و تعـامل میان انسان ها بدل شده است. موتورهای جستجو به عنوان برنامه های کاربردی وب به طور خودکار پهنه وب را پیمایش نموده و مجموعـه ای از اسناد و مـدارک بروز موجـود را دریافـت می کننـد. فرآینـد دریافت، ذخیره سازی، رده بندی و شاخص دهی بر اساس الگوریتم های نيمه هوشمند به صورت خودکار انجـام می شود. اگر چه بسیاری از حقایق در مورد ساختار این برنامه های کاربردی به عنـوان اسـرار تجاری پنهان باقی مانـده است، ادبيات تحقيق در شاخه ی موتورهای جستجو و ابزارهای بازيابی اطلاعات تلاش در يافتن بهترین راهکارها برای عملکرد بهينه ی هر ماژول در ساختار موتورهای جستجو دارد. با توجه به زمان محدود کاربران وب امروزی، ارائه مرتبط ترين و تازه ترين اسناد به آنها اغلب مهمترين چالشی برای موتورهای جستجو می باشد. برای انجام اين مهم، هر ماژول در معماری موتور جستجو باید به گونه ای هوشمند طراحی شود که نه تنها اسناد مرتبط را ارائه دهد بلـکه به پاسخگویی در سريع ترين زمان ممکن بپردازد. در میـان این ماژول ها بخش حساس و حیاتی به نام خزنده وجود دارد. یکی از مسائل قابل بحث در بهینه سازی عملکرد موتورهای جستجو این است که، سیاست خزیدن پیکربندی مجـدد گردد به طریقی که لینک های خارجی مرتبطی که به محتوای مرتبط با صفحات منبع پيوند می خورند دنبال گردد. ماژول خزنده مسئول واکشی صفحات برای ماژول رتبه بندی است. اگر صفحات با کیفیت بالاتر با انحراف موضوع کمتر توسط خزنده نمایه سازی شوند، رتبه بندی سریع تر انجام خواهد شد.با در نظر گرفتن ساختار وب به صورت گراف، نحوه ی پیمایش وب به صورت روش های جستجوی گرافی می باشد. در این پژوهش، با بکار بردن تجربی روشهای مختلف جستجوی گراف و ترکیبات مختلف آنها و با صدور پرس و جوهایی به موتور جستجوی گوگل جهت اندازه گیری کیفیت صفحات دریافتی و با ثابت در نظر گرفتن فاکتور عمق پيمايش به شناسایی بهترین روش با پیچیدگی زمانی و فضایی معقول به منظور بکار گيری در بخش خزنده در معماری موتور جستجو پرداخته خواهد شد.کلمات کلیدی: خزنده وب، پيمايش گراف، موتورهاي جستجو، انحراف موضوع.فصل اولکلیاتبدون وجود موتورهای جستجوگر تقریباً وب جهان گستر بدون فایده است. اما سؤال این است که موتورهای جستجوگر چگونه در میان این همه وب سایت اطلاعات مورد نیاز ما را پیدا می کنند. اینترنت بسیار وسیع است و کاربران وب در حدود دو میلیارد برآورد می شوند. در این میان حداقل 250 میلیون وب سایت اینترنتی وجـود دارد که در مجمـوع چیزی در حدود 30 میلیارد صفحه وب را در خود جـای داده اند. گشتن در محیط وب[1] زمانی که بسیار کوچک و وب سایت ها بسیار کم بودند معمولاً اختصاص به پژوهشگران و اساتید دانشگاه داشت و می توان گفت که کار دشواری نیز به شمار می رفت[9].با توسعه وب و زیاد شدن حجم اطلاعات و وب سایت ها نیاز به ابزاری جهت یافتن اطلاعات در این اقیانوس اطلاعات بیش از پیش احساس می شد. در همین حال در اوایل دهه نود میلادی بود که اولین موتورهای جستجوگر به نام آرچی[2] پا به عرصه حضور گذاشتند. یک موتور جستجوگر در قدم اول و قبل از آنکه بخواهد نتایجی را به کاربر نمایش دهد بایستی اطلاعات را جمع آوری و طبقه بندی کرده باشد. بنابراین موتورهای جستجو باید تا حد امکان وب سایت ها را مرور کنند و آدرس صفحات را با چکیده ای از محتویات صفحه ذخیره و طبقه بندی کنند. این وظیفه بسیار سنگین است و توسط خزندگان وب[3] انجام می شود[53].این برنامه ها به صورت خودکار در وب به جستجو پرداخته و محتویات صفحات وب سایت ها را برای تحلیل بعدی ذخیره می کنند. از آنجا که تعداد صفحات و حجم آنها بسیار بالاست از این رو این کار در مقیاس بسیار بزرگی انجام می شود و به زمان و پهنای باند بالایی نیاز دارد. موتورهای جستجوگر معروف مخزن بسیار بزرگی را در صفحات وب ایجاد کـرده اند اما خزندگان جدیدتر باید این کار را از صفر شـروع کنند. خزنده ها برای شروع معمولاً به سراغ دایرکتوری های معروف می روند چون از طریق آنها می توانند به لیست بزرگی از سایت های مرتبط دسترسی پیدا کنند و با مرور این وب سایت ها خزنده وب هر چه بیشتر در فضای داخلی وب سایت ها فرو می رود و اطلاعات بیشتری بدست می آورد. تمامی این اطلاعات در مخزن ذخیره می شوند تا بعداً مورد تجزیه و تحلیل قرار گیرند[44].یک خزنده با طراحی خوب می تواند محتوای صفحـات وب را با سرعت بالایی مرور کند و در عین حال همگی خزندگان با کمک یک برنامه هماهنگ کننده اقدام به جستجو در وب می کنند تا این عمل دوباره تکرار نشود. این هماهنگ کننده باعث می شود که فاکتور تازگی صفحات حفظ شود تا جدیدترین نسخه آنها در بانک اطلاعاتی موتور جستجو قرار گیرد[46].پس از آنکه خزندگان اطلاعات را در صفحات وب جمع آوری کردند این اطلاعات باید بر روی سرورهای سایت جستجوکننده ذخیره شوند. ذخیره و ایندکس کردن صفحات فراوان و بی شمار در وب یک چالش بزرگ است اما از آن مهم تر این است که موتور جستجو بداند که کاربرانش به دنبال چه چیزی هستند. هر چه قدر اطلاعات نمایـش داده شده توسط یک موتـور جستجو با عبارت جستجـو شده توسـط کاربر منطبق تر باشد، موتور جستجو عملکرد و محبوبیت بهتری دارد.اما آنچه که یک وب سایت را در نتایج جستجوی یک موتور جستجوگر در رتبه ی بالاتری قرار می دهد در واقع نوع الگوریتم موتور جستجوگر در رتبه بندی صفحات یافت شده است. این الگوریتم مجموعه ای پیچیده از قواعد و ملاحظات گوناگون است که البته مدام در حال بهینه سازی است تا نتایج بهتری را در معرض نمایش کاربران قرار دهد. هر چقدر الگوریتم یک موتور جستجوگر بهتر عمل کند آن وب سایت نیز نتایج بهتری را به کاربران ارائه می دهد و از همین رو ضامن موفقیت یک موتور جستجوگر همان معماری و نوع الگوریتم جستجوی آن است. موتورهای جستجو همگی کل صفحات را بر اساس کلمات موجود در آن مورد ارزیابی قرار می دهند. اهمیت یک وب سایت هم در رتبه آن تاثیر مهمی دارد و اگر سایت های زیادی به یک صفحه خاص لینک دهند، موتور جستجو با وزن دهی[4] متوجه می شود که آن صفحه مهم است و به آن صفحه توجه بیشتری می کنـد. هر چه تعـداد لینک ها از سایت های دیگر به یک سایت بیشتر باشد یعنی آن وب سایت مهمتر و معتبرتر است.حال اگر وب سایتی که رتبه بالایی دارد به وب سایت دیگری لینک دهد، آن لینک ارزش بیشتری نسبت به چندین لینک خواهد داشت[35].يک خـزنده وب برنامـه اي است که صفحـات وب را عمـوماً براي يـک موتور جستجـوي وب دانلـود مي کند. خزنده هاي موتورهاي جستجوي بزرگ مانند گوگل، آلتاويستا و ... از بخش قابل توجهي از صفحات وب متني به منظور ساخت شاخص هاي محتوا استفاده می کنند. خزنده هاي ديگر همچنين ممکن است صفحات زيادي را مشاهده کنند و تنها براي نوع خاصي از اطلاعات مانند آدرس ايميل مورد استفاده قرار گيرند. در انتهاي ديگر اين طيف، خزنده هاي شخصي سازی شده وجود دارد که صفحات مورد علاقه يک کاربر خاص را به منظور ساخت يک حافظه نهان در دسترس سريع پيمايش مي کنند. طراحي يک خزنده خوب چالش هاي بسياري را به دليل گسترده بودن وب به همراه دارد و به طور دائم بايد بروز باشد. بر طبق مطالعـات مختلف بيش از يک ميليون صفحه در دسترس در وب وجود دارد و پيش بيني مي شود که اين نرخ رشد همچنان ادامه يابد. گذشته از اين، صفحاتي که به تازگي ايجاد شده اند به طـور مداوم درحال بروز رساني مي باشند[5].