https://virgool.io/feed/@n1rna توسعه دهنده وب fa 2026-06-10 12:53:13 https://files.virgool.io/upload/users/5012/avatar/n67bIJ.png?height=120&width=120 https://virgool.io/@n1rna https://virgool.io/@n1rna/%D9%86%D9%82%D8%B7%D9%87-%D8%B4%DA%A9%D8%B3%D8%AA-%D8%AA%DA%A9%DB%8C%D9%86-%D8%AF%D8%B1-%D8%A7%D8%B1%D8%A7%D8%A6%D9%87-%D8%AF%D9%87%D9%86%D8%AF%DA%AF%D8%A7%D9%86-dns-ggpiu2m0foxw این نوشته شامل توضیحاتی در زمینه ماهیت DNS یا نحوه کارکرد ارائه دهندگان DNS *نمی باشد* و در صورتی که با این مباحث آشنایی کافی ندارید، خواندن این نوشته برای شما پیشنهاد نمی شود :)در این نوشته میخواهیم درباره ایجاد Single Point of Failure در استفاده از ارائه دهندگان DNS صحبت کنیم. با توجه به اینکه در روز های اخیر، با فاصله زمانی چند روز، با قطعی سرویس DNS شرکت ابرآروان روبرو شدیم و بسیاری از وبسایت های ایرانی که از خدمات این شرکت استفاده می کردند، از دسترس خارج شدند، به این فکر افتادم که نوشته ای درباره مقاوم سازی در برابر چنین مشکلاتی بنویسم. اشاره به این نکته هم خالی از لطف نیست که بنده دانش تخصصی در این زمینه ندارم و پیشاپیش از روبرو شدن شما متخصص عزیز با اشتباهات احتمالی پوزش میطلبم :)موضوع از دسترس خارج شدن سرویس های ارائه دهنده DNS، موضوع جدیدی نیست. جدا از مشکلات فنی ای که می توانند باعث بوجود آمدن چنین مسأله ای بشوند، حملات DDoS به این سرویس ها، یکی از اصلی ترین و شایع ترین دلایل چنین اختلالاتی می باشند. برای مثال می توانید اینجا درباره یکی از بزرگترین حملات از این نوع، که با هدف از دسترس خارج کردن سرویس Dyn در سال ۲۰۱۶ اتفاق افتاده بود، مطالعه کنید. مشکلات فنی هم همونطور که اشاره کردیم، در خیلی از موارد باعث چنین مشکلاتی شده اند که برای مثال میتونیم به اختلالی که در سرویس cloudflare در ماه جولای سال میلادی جاری اشاره کنیم که به دلیل دیپلوی شدن کد مشکل دار اتفاق افتاده بود.اما مسأله اصلی، مقاوم سازی سرویس ها در برابر چنین اختلالاتی هست. چون بهرحال، اعتماد کردن به uptime یک سرویس ثالث (Third-Party) برای uptime سرویس خودتان، اصولا کار درستی نیست و در واقع در چنین حالتی، کیفیت سرویس شما کاملا وابسته به سرویس Third-Party خواهد بود. اما خیلی اوقات با توجه به دردسر راه اندازی و نگهداری چنین سرویس هایی (DNS Server)، بیزینس های مختلف ترجیح می دهند که حتی با پرداخت هزینه، این وظیفه را به شرکت های دیگر برونسپاری کنند و از خدمات آنها استفاده کنند.همونطور که احتمالا خوانندگان این نوشته در جریان هستند، برای اینکه DNS های دامنه مورد نظر شما از سرویسی مثل cloudflare یا ابرآروان یا سرویس های مشابه، ارائه بشوند، شما باید ابتدا رکورد های NameServer مربوطه را به درستی تنظیم کنید. معمولا تمامی Domain Registrar های مختلف، کمترین خدمتی که به شما ارائه می دهند، قابلیت اضافه کردن رکورد های NS برای دامنه شماست. در خیلی از موارد، رجیسترر شما، قابلیت اضافه کردن انواع مختلف DNS Record ها را می دهد، اما در مواردی مثل nic دوست داشتنی(!) خودمون، فقط قابلیت اضافه کردن رکورد NS را به کاربر می دهند.چیزی که در انتهای این نوشته میخوایم بهش برسیم، این هست که بتوانیم رکورد های DNS دامنه مورد نظرمون رو از دو - و بیشتر - سرویس ارائه کنیم؛ چون با توجه به اینکه شاید یکی از این سرویس ها، از دسترس خارج بشوند، کاربران سرویس ما، باید بتوانند از جای دیگری DNS های مربوط به دامنه ما را دریافت کنند و در واقع یک استراتژی Fallback برای چنین سناریو هایی تعریف کنیم.نکته اول و بسیار مهم، این هست که باید تمامی رکورد هایی که روی هریک از این ارائه دهنده ها تنظیم می کنید، روی ارائه دهنده دیگر هم موجود باشند. در صورتی که بین این تنظیمات ناهماهنگی وجود داشته باشد، امکان دارد که کاربران مختلف، با وارد کردن یکی از آدرس های دامنه شما، نتایج مختلفی دریافت کنند. [اگر درخواست resolve به ارائه دهنده A ارسال شود و این ارائه دهنده تنظیمات مربوط به آن درخواست را نداشته باشد (روی ارائه دهنده B موجود باشد)، خطا ایجاد می شود - در صورتی که اگر این درخواست به ارائه دهنده B ارسال می شد، بدون مشکل درخواست حل می شد.]نکته دوم، هماهنگی رکورد های NS روی ارائه دهنده های مختلف هست. این نکته، در واقع بخشی از نکته قبلی هست، اما به خاطر اهمیت آن، بصورت جدا به بررسی اش می پردازیم :دیبعضی از شرکت هایی که خدمات DNS ارائه می دهند، قابلیت تغییر و ثبت رکورد های NS جدید را به کاربران خود نمی دهند. اما این قابلیت، مهم ترین پیش نیاز انجام این تنظیمات است! پس قبل از هرچیز، مطمئن شوید که ارائه دهنده DNSی که انتخاب میکنید، این قابلیت را به شما می دهد. [معمولا، این ارائه دهندگان، این قابلیت را به شما می دهند اما چیزی که نمی توانید تغییر بدهید، رکورد های NS مربوط به خود آن شرکت است - که معمولا هم نیاز نیست]فرض کنیم که ما میخواهیم رکورد های DNS دامنه مان را جوری تنظیم کنیم که از هر دو سرویس Cloudflare و ابرآروان [اصطلاحا] propagate بشوند و در صورتی که هر یک از این دو سرویس با اختلال روبرو شد، کاربران سرویس ما، همچنان بتوانند به دامنه های ما دسترسی داشته باشند و ما با مشکل روبرو نشویم. یکی دیگر از خوبی های چنین تنظیمی، میتواند بالا رفتن سرعت resolve شدن DNS های دامنه شما از نقاط مختلف دنیا باشد. با توجه به اینکه افراد مختلف، از DNS Server های مختلفی روی ماشین هایشان استفاده میکنند، در نتیجه امکان اینکه DNS شما از یکی از سرویس های Cloudflare یا ابرآروان (در مثال ما) سریعتر از دیگری resolve شود، وجود دارد. [اگر فردی از 1.1.1.1 استفاده بکند، Cloudflare را زودتر پیدا خواهد کرد نسبت به ابرآروان]سرویس Cloudflare از شما میخواهد که این NS ها را تنظیم کنیدسرویس ابرآروان از شما میخواهد که این NS ها را تنظیم کنیدتنظیماتی که شما باید روی دامنه خود انجام بدهید هم باید چیزی شبیه به تصویر زیر باشد:معمولا به NS اول، به عنوان Primary Record و به باقی رکورد ها بعنوان Secondary Record نگاه می شود - پس رعایت اولویت در انتخاب شما می تواند مؤثر باشد. *اما بصورت عمومی، نمی توان اطمینان داشت که به همین ترتیب اولویت ها اتفاق می افتد*پس از اینکه این تنظیمات را انجام دادید، باید بصورت «ضربدری» رکورد های هر سرویس را در سرویس دیگر نیز وارد کنید. به تصویر زیر دقت کنید:رکورد های NS مربوط به ابرآروان را در Cloudflare وارد میکنیمرکورد های NS مربوط به Cloudflare را در ابرآروان وارد میکنیمدر حال حاضر، تنظیمات مورد نیاز بصورت کامل انجام شده اند. اما همچنان تأکید به این نکته لازم است که همیشه سعی کنید رکورد هایی که روی هر یک از این سرویس ها اضافه میکنید، روی دیگری نیز بصورت یکسان اضافه شوند. برای automate کردن این فرایند و جلوگیری از خطای انسانی، میتوانید اسکریپتی بنویسید که با استفاده از API هایی که هر یک از این سرویس ها در اختیارتون قرار می دهند، رکورد ها را از یکی از این سرویس ها دریافت و در سرویس دیگر تنظیم کند.در نهایت خواندن این مقاله رو هم بهتون پیشنهاد میکنم که بخش زیادی از نوشته بنده نیز برگرفته از آن مقاله است. نیما یزدان مهر نیما یزدان مهر Mon, 04 Nov 2019 19:39:46 +0330 https://virgool.io/coderlife/%D9%85%D9%88%D8%AA%D9%88%D8%B1%D9%87%D8%A7%DB%8C-%D8%AC%D8%B3%D8%AA%D8%AC%D9%88-%D8%A8%D8%B1%D8%B1%D8%B3%DB%8C-%D9%86%D8%AD%D9%88%D9%87-%D8%B9%D9%85%D9%84%DA%A9%D8%B1%D8%AF-%D9%88-%D9%BE%DB%8C%D8%A7%D8%AF%D9%87-%D8%B3%D8%A7%D8%B2%DB%8C-%D9%82%D8%B3%D9%85%D8%AA-%D8%AF%D9%88%D9%85-fccobe4lkgql اگر قسمت اول را نخوانده اید، از اینجا می توانید به آن دسترسی داشته باشید.در قسمت اول، درباره مفاهیم اولیه مکانیزم یک موتور جستجو، صحبت کردیم و بخش های اصلی این مکانیزم را معرفی، و توضیح مختصری، درباره هریک از آنها دادیم. در انتهای قسمت اول، به این اشاره کردیم که پیش پردازش های زیادی، به روی اسناد ایندکس شده، و همچنین، کوئری هایی که کاربر وارد میکند، انجام می شود. همینطور، زمانی که نتایج مرتبط با یک کوئری، از موتور ایندکس کننده، بازیابی می شوند، پردازش هایی به روی همین نتایج انجام میشود و در نهایت این نتایج، به دست کاربر می رسند. در این قسمت میخواهیم درباره این پیش پردازش ها (روی کوئری و اسناد) و پس پردازش ها (روی نتایج بازیابی شده توسط موتور ایندکس کننده) و برخی روش های استفاده شده در هریک از این مراحل، صحبت کنیم.ابتدا، به چند مورد از پیش پردازش هایی که حتما قبلا به چشمتان آمده و برایتان آشنا هستند، اشاره ای می کنیم.همسان سازی کوئری وارد شده - normalizationکامل کردن ادامه جمله (کوئری) بصورت خودکار - auto-completeپیشنهاد کلمه صحیح، هنگام تایپ - auto-correctتشخیص دسته مرتبط با کوئری وارد شده (در جستجوگر هایی که اسنادشان قابل دسته بندی باشد)درست کردن غلط های تایپی موجود در کوئری - spellcheckingآنالیز کردن کوئری و همینطور فیلد های مهم در اسناد (قبل یا حین ایندکس کردن)...مسأله پیش پردازش، از این رو اهمیت بالایی دارد که، اگر حتی تمام لایه های موتور جستجو ما، به درستی و با دقت بالایی، در حال انجام کارشان باشند، اگر چیز اشتباهی را از آن درخواست کنیم، قطعا به نتیجه دلخواهمان نمی رسیم. این چیز های اشتباه، می توانند شامل:غلط های املایی غلط های تایپیکلماتی که در هیچ یک از اسناد ما حضور نداشته انداشتباهاتی که به دلیل تفاوت تلفظ محاوره ای یک کلمه با تلفظ رسمی آن بوجود می آیند (این مورد شامل لهجه های مختلف برای تلفظ یک کلمه هم می شود)...به همین دلیل، این موضوع بسیار مهم می باشد که سعی کنیم هرچه بیشتر، به چیزی که در ذهن کاربر بوده، در هنگام تایپ کردن کوئری، نزدیک شویم و نتایج مرتبط تر را به کاربر نمایش دهیم.در این نوشته، سعی میکنم هریک از این سه موردی که اشاره کردم را، شرح مختصری بدهم؛ اما تمرکز بیشتری به روی موضوع spellchecking خواهم داشت.همسان سازی کوئری - normalizationاین پروسه، شاید در برخی موتور های جستجو، اصلا لازم نباشد. همینطور ممکن است بنا به نوع و زبان اصلی اسناد مورد جستجو توسط موتور جستجو، متفاوت باشد. از مثال هایی از بلا هایی که در این مرحله، به سر کوئری وارد شده می آیند، می توان به موارد زیر اشاره کرد:تبدیل تمامی حروف به حالت lower-caseحذف یا جایگزینی symbol ها (!,@,#,$,...)جدا کردن کلمات از اعداد. برای مثال: iphone6 به iphone 6حذف کاراکتر های اضافی مثل علائم نگارشی، نشانه های ثانویه فارسی ( َ ِ ُ ً ٍ ٌ آ أ ء ...) برای مثال، حروفی مثل «آ» و «أ» را به «ا» تبدیل می کنیم.پیشنهاد ادامه جمله - autocomplete*مفهوم autocomplete را با autocorrect اشتباه نگیرید. موضوع autocorrect بسیار شبیه به spellchecking می باشد، که این موضوع را در ادامه بررسی میکنیم.*حتما با پیشنهاد های سرچ گوگل در هنگام سرچ کردن مواجه شده اید. به محض اینکه اولین کاراکتر یا اولین کلمه را در جعبه جستجو گوگل وارد میکنید، پیشنهاد های متعددی به شما نمایش داده می شوند که در اکثر اوقات هم، بسیار نزدیک به چیزی که در ذهنتان بوده، هستند. اگر دقت کرده باشید، هرچه تعداد کلماتی که می نویسید، بیشتر باشد، پیشنهاد های دقیق تری هم به شما نمایش داده می شوند. تمام کوئری هایی که خودتان، یا کاربران دیگر، در طول عمر یک موتور جستجو، در این موتور جستجو وارد کرده اید، در انجام این پروسه، به کار گرفته می شوند. همینطور تیتر اسناد ایندکس شده، در عملکرد بهتر سرویس autocomplete تاثیر میگذارند. ایده کلی درباره کارکرد قابلیت autocomplete، استفاده از تعداد زیادی string می باشد که احتمال اینکه کاربر چیزی نزدیک به یکی از آنها را بنویسد، زیاد باشد.روشی که بصورت معمول استفاده می شود، استفاده از درخت پسوندی - suffix tree می باشد. suffix های یک string، در واقع همان زیر رشته (substring) های یک string می باشند. اگر یک درخت تشکیل دهیم که فرزندان هر گره، substring های آن رشته باشند، زمانی که کاربر بخشی از کوئری مورد نظرش (به این تکه از کوئری sq می گوییم) را وارد کرده، میتوانیم با اجرای یک الگوریتم سرچ روی این درخت، رشته هایی که بخشی از آنها، شبیه به sq هستند را پیدا کنیم و به عنوان پیشنهاد، به کاربر نمایش دهیم.روش دیگری که برای حدس زدن کلمه بعدی یک جمله به کار می رود، استفاده از مدل Markov می باشد. به دنباله ای از رویداد ها که از مدل Markov پیروی می کنند، یک زنجیره مارکوف - Markov Chain می گویند. در این روش به همون شکل قبل، یک مجموعه از جملات محتمل را پردازش، و با توجه به توزیع احتمالاتی دنباله کلمات وارد شده (qs)، سعی میکنیم کلمه بعدی را حدس بزنیم. به دلیل اینکه توضیح این روش، این متن رو بسیار طولانی (تر) می کند، به ارائه یک مثال بسنده می کنم و اگر علاقه ای به خواندن بیشتر در این مورد دارید، پیشنهاد میکنم این مقاله را مطالعه کنید.جملات زیر را در نظر بگیرید:I like PhotographyI like ScienceI love Mathematicsتشخیص دسته بندیاین قسمت، در موتور جستجو هایی که اسنادشان قابل دسته بندی هستند و یا به هر نوعی، مفهوم دسته بندی روی این اسناد قابل تعریف باشد، نیاز می شود و تجربه کاربری را بسیار بهبود می دهد. اگر به تصویری که از جعبه جستجو وبسایت ترب که بالاتر قرار گرفته، دقت کنید، سه پیشنهاد اول، شامل پیشنهاد دسته بندی نیز می باشند. روشی که برای پیاده سازی این قابلیت استفاده شده، naive bayes classification می باشد. دیتایی که برای آموزش این مدل استفاده شده، اسم تمام محصولات موجود در یک دسته بندی مشخص می باشد. مدل naive bayes، برای دیتا هایی که اصطلاحا لیبل دار هستند، مدل بسیار مناسبی است. همانطور که می توانید ببینید، دیتای ما، کاملا لیبل دار است و با استفاده از naive bayes، میتوانیم به این قابلیت برسیم که یک یا چند کلمه را به عنوان ورودی به مدل بدهیم و دسته بندی هایی که این دنباله از کلمات، احتمالا به آن دسته مربوطند را، به عنوان خروجی، از مدل بگیریم.رفع غلط های تایپی - spellcheckingحتما تابحال با صحنه ای مشابه تصویر بالا روبرو شده اید. شاید حتی خیلی اوقات، برای پیدا کردن املای صحیح یک کلمه، اولین املایی که به ذهنتون میرسه رو تو گوگل وارد میکنید و در نهایت به املای درست اون کلمه میرسید. غلط های تایپی/املایی، رایج ترین نوع خطاهای انسانی در سطح دنیا محسوب می شوند. هرروز، هنگام چت کردن، نوشتن یک ایمیل، نوشتن توییت، سرچ کردن و ... با غلط های تایپی/املایی روبرو می شوید. این مشکل، نه مختص شماست، نه مشکل کیبرد شماست!! هنگام استفاده از تلفن همراه، به دلایل مختلف، ممکن است که کلید اشتباهی را بفشارید (انگشتان بزرگی دارید :joy:) یا کلید ها را به ترتیب اشتباهی بفشارید. به هرحال، این نوع اشتباهات، کاملا رایج هستند و هیچ راهی برای جلوگیری از اتفاق افتادنشان وجود ندارد. اگر شما کلمه اشتباهی را جستجو کنید، به صورت منطقی، نباید هم به نتایج دلخواهتان برسید. اما، از آنجایی که شاید خیلی اوقات، حتی متوجه این موضوع نشوید که کلمه اشتباهی را جستجو کرده اید، در اکثر اوقات، نرسیدن به نتایج مطلوب را، به «بد» بودن آن موتور جستجو نسبت می دهید :)) اما خب امروزه، با استفاده از تکنیک های مختلف، میشه تا حدی، این غلط های املایی و تایپی رو، متوجهشون شد و در نهایت به کلمه درست (کلمه ای که از ابتدا تو ذهن کاربر بوده) رسید.موضوع spellchecking، موضوع جدیدی نیست و مدت هاست که افراد زیادی برای رسیدن به روشی برای تشخیص و تصحیح غلط های املایی در تلاشند. روشی که ما در موتور جستجو ترب، برای تشخیص و تصحیح غلط های املایی استفاده کردیم، ترکیبی از چند روش مختلف می باشد که در این قسمت، به شرح این روش پرداخته ام.ما از کجا می فهمیم که یک کلمه، اصلا یک کلمه واقعی است؟ پاسخ این سوال ساده است. تعداد کلماتی که در دنیا، به زبان های مختلف، وجود دارند، شاید عددی نزدیک به چند ده میلیون باشد (هیچ ایده ای ندارم!). یک الگوریتم کامپیوتری، تنها با استفاده از مجموعه ای از کلمات درست، می تواند کلمات درست را تشخیص بدهد. کلمات درست، با توجه به زمینه ای که آن الگوریتم در آن استفاده خواهد شد تعریف می شوند. اگر شما میخواهید این الگوریتم را بروی جملات فارسی اجرا کنید، باید مجموعه ای از جملات فارسی را به عنوان ورودی به الگوریتم بدهید. حس میکنم این موضوع کاملا واضح است و توضیح بیشتری احتیاج نیست.فرض کنیم که یک corpus از کلمات و جملات مورد نظرمان را جمع آوری کرده ایم. نحوه تشخیص کلمات درست، بسیار ساده است. اگر یک کلمه خاص، در corpus ما، بیشتر از یک threshold خاصی، تکرار شده باشد، می توانیم بگوییم که این کلمه، کلمه درستی است. برای مثال، اگر فرکانس یک کلمه، بزرگتر از ۱۵ باشد، با احتمال بیش از ۹۰ درصد، این کلمه، کلمه درستی است. یکی از مشکلاتی که در این مرحله با آن مواجه می شویم، مشکل کثیف بودن corpus می باشد. فرض کنیم که corpus ما، تعدادی article جمع آوری شده از سطح اینترنت باشد. مشکلی که پیش می آید، این است که اگر یک کلمه اشتباه (دارای غلط املایی)، در چند جای مختلف از این article ها، تکرار شده باشد، الگوریتم ما، این کلمه اشتباه را هم بعنوان یک کلمه درست در نظر میگیرد. به همین دلیل، تمیز بودن corpus و بالانس کردن threshold برای تشخیص کلمات درست، در این مرحله، اهمیت بالایی دارد.بعد از اینکه کلمات درست موجود در یک جمله (کوئری کاربر) را تشخیص دادیم، می توانیم بگوییم که کلمات باقی مانده، کلمات اشتباهی هستند (که غلط املایی یا تایپی دارند).بازیابی کلماتدر ابتدا، اجازه دهید که کمی درباره مفهوم فاصله کلمات با یکدیگر صحبت کنیم. فاصله ای که از آن حرف میزنیم، یک معیار قابل اندازه گیری، برای میزان اختلاف دو string مختلف می باشد. برای مثال، رشته های زیر را در نظر بگیرید.neat, beat, bear, seatblack, red, apple, kiwiمی توانید ببینید که کلمات دسته اول، بسیار شبیه به هم و نزدیک به هم هستند. در صورتی که کلمات دسته دوم، تقریبا هیچ شباهتی به یکدیگر ندارند. اگر شباهت از نظر نحوه گفته شدن و تلفظ کلمات را در نظر نگیریم، می توانیم ببینیم که اختلاف کلمات دسته اول، هر کدام با دیگری، تنها در یک کاراکتر می باشد (bear و beat را با هم در نظر بگیرید :joy:) به اینصورت که، یکی از کاراکتر ها باید به کاراکتر دیگری تبدیل شود. حال، به تغییرات دیگری که می توان روی یک کلمه ایجاد کرد تا به کلمه دیگری رسید فکر کنید. این تغییرات، یکی از این حالت ها هستند: جابجا کردن حروف، اضافه کردن یا حذف کردن یکی از حروف، تغییر دادن یکی از حروف (که می توان به چشم یک حذف و یک اضافه به این عمل نگاه کرد). پس می توان با اندازه گیری تعداد تغییرات مورد نیاز، برای رسیدن از یک کلمه، به یک کلمه دیگر، فاصله این دو رشته را از هم حساب کرد. روش های مختلفی برای محاسبه این نوع از فاصله بین string ها (که به آنها editing distance گفته می شود) ابداع شده اند. روش های Levenshtein Distance و Damerau-Levenshtein Distance و Jaro Score، از جمله معروف ترین این روش ها هستند.نکته بعدی که در ادامه از آن استفاده خواهیم کرد، این نکته هست که، هنگام محاسبه فاصله دو کلمه از یکدیگر، می توانیم برای هر یک از اعمالی (تغییرات) که روی کلمه اول باید اتفاق بیوفتد تا به کلمه دوم برسد، یک امتیاز تعریف کنیم. برای مثال، اگر عمل ما، جابجا کردن دو تا از حروف می باشد، می توان این عمل را با توجه به فاصله آن دو حرف از یکدیگر، امتیاز دهی کرد. یا اگر یکی از حروف، با حرف دیگری قرار است جایگزین شود، فاصله کاراکتر ها، می تواند متفاوت باشد. به تصویر زیر توجه کنید:کلید های نزدیک به کلید حرف G، فاصله کمتری دارندحروفی که روی یک کیبرد استاندارد qwerty، نزدیک تر به یک حرف هستند، امتیاز بالاتری برای جایگزینی دارند (یعنی فاصله شان کمتر است).ایده پردازش متقارنایده اصلی که در پروسه spellchecking استفاده شده، پردازش کلمات corpus و کوئری کاربر، بصورت متقارن می باشد. فرض کنید که ما میخواهیم سرویسی ارائه کنیم، که قابلیت بازیابی کلمات تا حداکثر فاصله ۴ را داشته باشد. کاری که در ابتدا انجام می دهیم، تشکیل یک دیکشنری از تمام token های موجود در corpusمان می باشد. نحوه تشکیل این دیکشنری، به این شکل هست که، به ازای هر token، تمام token های ممکن، در فاصله حداکثر ۲ را، در کنار یک object بعنوان راهنمای بازیابی کلمه، می سازیم. برای فهم بهتر، به مثال زیر توجه کنید:کلمه مورد بررسی ما، کلمه iphone می باشد. وقتی از token های با فاصله حداکثر ۲ صحبت می کنیم، منظورمان token هایی است که با عمل «کم کردن» از iphone ساخته می شوند. در نتیجه، token های تولید شده برای کلمه iphone، به شرح زیر می باشند:['phone', 'ihone', 'ipone', 'iphne', 'iphoe', 'iphon', 'hone', 'pone', 'phne', 'phoe', 'phon', 'ione', 'ihne', 'ihoe', 'ihon', 'ipne', 'ipoe', 'ipon', 'iphe', 'iphn', 'ipho']حال برای هر یک از این token ها، یک object راهنما، برای بازیابی این کلمه به کلمه اصلی نیز ذخیره می کنیم. این object در واقع، به ما می گوید که برای رسیدن به هر یک از این token ها، چه حروفی، از کجای کلمه اصلی حذف شده اند. برای مثال، برای رسیدن از کلمه iphone، به ihone، باید حرف p را از جایگاه دوم این کلمه، حذف کنیم. این object، توانایی نگهداری ۲ فاصله را دارد (به شکل یک آرایه ۲ تایی). در حال حاضر، ما تمام token های با فاصله حداکثر ۲، از تمام کلمات corpus خودمان را داریم. یکی از نکات جالب توجه در این مرحله، تقلیل کلمات مختلف به یکدیگر می باشد. در مثال بالا، دیدیم که کلمه iphone، با حذف حرف اولش، به کلمه phone تبدیل می شود. مثال های متعددی از این نوع اتفاق، می توان پیدا کرد (هدفون -> هدف، مردانه -> مردان، ...).ساختمان داده ای که در مرحله قبل ساختیم، که شامل یک دیکشنری از تک تک کلمات corpus و فرکانسشان (freq) و یک mapping از هر کلمه، به token های در فاصله ۲ از آن کلمه (deleted) می باشد، برای سرعت دسترسی بالا، در مرحله initial سرویس اسپل چکر، محاسبه و بروی رم قرار داده می شود.زمانی که کلمه ای برای تصحیح اسپلینگ، به ما داده می شود (کوئری کاربر)، مراحل حذف و تولید token های با فاصله ۲ را، روی آن اجرا می کنیم و تک تک token های تولید شده را، با لیست token های موجود در deleted، چک میکنیم و به دنبال match ها میگردیم.تولید token های در فاصله ۲ از کوئری کاربربرای هریک از این token ها، به دنبال match در deleted می گردیم.هر یک از این match ها را، با توابع مختلف، امتیاز دهی می کنیم. (درباره نحوه امتیازدهی، در ادامه صحبت شده)بالاترین امتیاز را بعنوان پاسخ بر میگردانیم.به مثال زیر توجه کنید:کوئری کاربر: مانتیور - پاسخ تصحیح شده: مانیتورهر یک از token های بالا، ممکن است با نسخه تقلیل یافته یک کلمه ای که در corpus قرار داشته، match شود.با این روش (Symmetric Delete spelling correction algorithm) می توانیم تا فاصله حداکثر ۴، هر کلمه را اسپل چک کنیم. در این روش، با انجام یک trade-off روی میزان رم مصرفی و تایم پردازش سر هر درخواست، به سرعت بسیار بالایی با دقت ۴ فاصله می رسیم. می توانید این مقاله رو هم برای توضیحات بیشتر درباره این روش، بخوانید.امتیازدهیپارامتر های زیادی برای محاسبه امتیاز هریک از این «تبدیل» (transform) ها وجود دارد. می توان گفت که این مرحله، مهم ترین مرحله پروسه اسپل چکینگ می باشد. شاید برای هر کلمه ای که miss-spell شده، بتوانید بالای ۱۰ تا match پیدا کنید. اینکه کدام یک از این match ها را بعنوان پاسخ صحیح معرفی کنید. بسیار موضوع مهمی است.هزینه تبدیلدر هر عمل تبدیل، اتفاقات مختلفی ممکن است رخ دهد. در ساده ترین حالت، این اعمال یا بصورت حذف کردن چند حرف خواهند بود، یا به صورت اضافه کردن چند حرف. اما این حذف و اضافه ها، می توانند از انواع خاصی باشند. برای مثال، یک حذف و یک اضافه، می تواند به صورت جایگزین شدن یک حرف باشد. مثل: ipjone و iphone. فاصله ای که برای این دو کلمه در نظر گرفته می شود، فاصله ۲ است. درصورتی که ارزش (هزینه) این تبدیل، کمتر از ۲ باید محاسبه شود. مخصوصا اگر حرف جایگزین شده، از کلید های دور و اطراف کلید حرف اولیه باشد (تصویر مربوط به همسایگی کلیدها در کیبرد). همینطور، این حذف و اضافه ها می توانند به شکل جابجایی دو حرف باشند. حالت جابجایی، با فاصله ۴ قابل شبیه سازی است. اما هزینه این تبدیل، مشخصا کمتر از ۴ است. به این شکل، امتیازی که برای هر تبدیل حساب می کنیم، می تواند به عنوان امتیاز فاصله (فاصله واقعی) در نظر گرفته شود. امتیاز اندازه تغییر و فرکانسدر اینجا، منظور از «اندازه تغییر»، کسر زیر می باشد.d: فاصله s: اندازه کلمه (d/s)این پارامتر، از این رو اهمیت دارد که، اگر یک کلمه شامل ۴ حرف باشد، اضافه یا حذف کردن ۳ حرف به این کلمه، واقعا زیاد است!! یعنی کاربر باید ۳ حرف را اشتباها اضافه کرده باشد یا ننوشته باشد. درصورتی که اگر این کلمه شامل ۱۰ حرف باشد، اختلاف ۳ حرف، انقدر غیر منطقی نیست. پارامتر بعدی، فرکانس کلمات است. اگر ما با پردازش match های کوئری کاربر، بین دو کلمه، با امتیاز یکسان مانده باشیم، قاعدتا باید گزینه ای که فرکانس بالاتری دارد را به عنوان جواب برگردانیم. فرمولی که ما در سرویس اسپل چکر ترب استفاده کرده ایم، چیزی شبیه به فرمول زیر است:1000 * exp(-15 * (distance / origin_size + 0.3) + 10) * ln(1 + freq)بردار کلمات (word2vec)در قسمت اول این نوشته، درباره نحوه تبدیل کردن دنباله ای از کلمات، به یک بردار و نحوه برخوردمان با این بردار ها توضیح دادیم. به دلیل بیش از اندازه طولانی نشدن این نوشته، از توضیح درباره خود الگوریتم word2vec میگذریم. برای اینکه بیشتر با این الگوریتم آشنا شوید، می توانید از صفحه ویکیپدیا این الگوریتم شروع کنید. جایی که ما از این الگوریتم استفاده می کنیم، در همین قسمت امتیازدهی می باشد. همونطور که در ادامه بحث گفتیم، زمانی که یک دنباله از کلمات (درواقع کل کوئری کاربر) به سرویس ما ارسال می شود، ما کلماتی که فرکانسشان بیشتر از threshold مورد نظرمان باشد را بعنوان کلمه صحیح میشناسیم و پردازشی روی آنها انجام نمی دهیم. استفاده جالبی که می توان از این کلمات کرد، تولید بردار حاصل از کنار هم قرار دادن این کلمات صحیح، با استفاده از مدل train شده word2vec می باشد. می توانیم مدلمان را با همان corpusی که تا الان با آن کار میکردیم، train کنیم و با توجه به همان مدل، برای کلمات و جملات مختلف، بردار مربوطه شان را بسازیم. استفاده ای که از این بردار می کنیم، به این شکل هست که، اگر کلمه بازیابی شده، در این بردار وجود داشته باشد، امتیازش یک ضریب خیلی خوب میگیرد. یعنی هنگام امتیاز دهی هر یکی از match هایی که در مراحل قبل پیدا کردیم، هربار چک می کنیم که آیا این match، مشابهش در بردار تولید شده توسط بقیه کلمات وارد شده توسط کاربر، موجود هستند یا خیر. به مثال زیر توجه کنید:کوئری کاربر: گوشی اپل آیفن - کوئری صحیح: گوشی اپل آیفونزمانی که ما میخواهیم این کوئری را پردازش کنیم، کلمات «گوشی» و «اپل» به دلیل داشتن فرکانس بالاتر از threshold، بعنوان کلمه صحیح شناخته می شوند. این دو کلمه را بعنوان ورودی، به مدل word2vec مان می دهیم و برداری مشابه بردار زیر به ما برگردانده می شود:['موبایل', 'تلفن', 'آیفون', 'سامسونگ', 'آیفون۶', '۶۴گیگ', 'همراه', 'گیگابایت']اینکه سایز بردار چه اندازه باشد، دست خودمان است و می توانیم به هر اندازه بزرگ در نظر بگیریمش. ترتیب این کلمات، بر اساس میزان ارتباطشان می باشد.بعد از اینکه این بردار را تولید کردیم، در زمان امتیاز دهی، هربار چک میکنیم که کلمه ای که تولید شده، در این بردار حضور دارد یا نه. اگر حضور داشته باشد، ضریب نسبتا بزرگی را در امتیاز آن match ضرب می کنیم.با استفاده از این الگوریتم، ما توانستیم دقت تشخیص و تصحیح سرویس اسپل چکر را به چیزی نزدیک به ۷۰ درصد افزایش دهیم. قبل از اینکه روش word2vec به این سرویس اضافه شود، دقتش حدود ۵۰ درصد بود؛ که امروز با افزایش ۲۰ درصدی، روی موتور جستجو اصلی ترب در حال استفاده می باشد.در تلاش هستیم که سورس کد این سرویس را سریعتر، بصورت متن باز منتشر کنیم. منطق اصلی این سرویس با زبان c++ نوشته شده و اینترفیس نرم افزاری آن را با استفاده از cython و twisted پیاده سازی کرده ایم.یادگیری رتبه بندی اسنادتا اینجای کار، درباره پیش پردازش هایی که روی کوئری و همچنین اسناد قابل انجام بود، صحبت کردیم. این عملیات، بصورت مستقل از موتور ایندکس کننده ما انجام می شوند و پس از این مراحل، کوئری پردازش شده به موتور ایندکس کننده تحویل داده می شود و در نهایت نتایج مورد نظر ما، توسط موتور ایندکس کننده بازیابی می شوند. اما برخی پردازش ها هم وجود دارند که پس از بازیابی نتایج و روی همین نتایج بازیابی شده انجام می شوند.یکی از جالب ترین مسائل در بحث بهینه سازی نتایج، فیدبک های کاربران می باشد. اینکه شما چقدر الگوریتم پیچیده ای برای رتبه بندی اسنادتان استفاده می کنید، تا زمانی که کاربر از نتایج شما رضایت نداشته باشد، «تقریبا» هیچ اهمیتی ندارد :)) یکی از ساده ترین پارامتر ها برای اینکه متوجه شوید کاربر چقدر از نتایج شما رضایت داشته و از این مهم تر، از کدامیک از نتایجی که نمایش داده اید، رضایت بیشتری داشته است، توجه به کلیک های کاربر می باشد. اگر در لیست نتایج مربوط به یک کوئری، اولین سندی که روی آن کلیک شده، سند پنجم باشد، الگوریتم شما «بهتر بود» آن سند را در رتبه اول نمایش میداد!! در ادامه به شرح کلیتی از روشی که در این مقاله توضیح داده شده می پردازیم.این مقاله، به معرفی روشی با استفاده از مدل SVM برای رتبه بندی اسناد با توجه به «کلیک های کاربران» برروی اسناد می پردازد. رتبه بندی ای که موتوری مانند ElasticSearch به شما می دهد، با توجه به پارامتر های (محتوا) داخل سند انجام می شود. کار ساده ای که میتوان انجام داد، ایجاد یک فیلد جدید در ساختار سند است، که شمارنده تعداد کلیک های کاربران بروی اون سند می باشد. می توان یک تابع امتیاز دهی بر اساس این فیلد، داخل کوئری الستیک نوشت. مشکل این روش، و درواقع تفاوتی که باعث می شود ما نتوانیم از این روش به درستی استفاده کنیم، این است که، یک سند، ممکن است در نتیجه جستجوی هزاران کوئری متفاوت ظاهر شود و کلیک بخورد. اما مسأله ما، بهینه کردن نتایج کوئری های مختلف بصورت مستقل می باشد. یک سند (a) ممکن است در ۱۰۰ کوئری مختلف، کلیک خورده باشد. اما کاربری، یک کوئری متفاوت از این ۱۰۰ کوئری را وارد کند و سند دیگری (b)، از سند (a) مرتبط تر با این کوئری وجو داشته باشد. اگر سند (b) تا به امروز، تعداد کلیک های پایینی داشته باشد، با توجه به نرخ بالای کلیک ها در سند (a)، سند (b) در نتایج، پایین تر از سند (a) نمایش داده می شود. در نتیجه ما به مدل پیچیده تری برای در نظر گرفتن این نوع از فیدبک ها و تاثیر دادنشان در نتایج، نیاز داریم. اگر کاربران، هر باری که با صفحه نتایج یک کوئری روبرو می شدند، درباره نتایج به ما فیدبک می دادند، ما می توانستیم از این داده ها برای آموزش مدلمان استفاده کنیم. اما کاربران به ندرت حاضر می شوند که نظرشان را اعلام کنند. درصورتی که دیتای مورد نیاز ما، واقعا در لاگ فعالیت کاربران در صفحه نتایج بصورت نیمه-پنهان وجود دارد. دیتای مورد نظر ما، دیتای clickthrough نامیده می شود. ساختار این نوع دیتا، به شکل زیر می باشد:(q, r, c) q: کوئری کاربر r: رتبه بندی (رنکینگ) ای که به کاربر ارائه شده c: مجموعه اسنادی که کاربر روی آنها کلیک کردهنتایج ارائه شده به کاربر، در نتیجه کوئری support vector machineسه تایی مربوط به تصویر بالا، به شکل زیر است:q: "support vector machine" r: ["http://svm.first.gmd.de/", "http://jbolivar.freeservers.com/", ..., "http://www.cs.wisc.edu/dmi/lsvm"] c: ["http://svm.first.gmd.de/", "http://ais.gmd.de/~thorsten/svm_light/", "http://svm.research.bell-labs.com/SVT/SVMsvt.html"]این داده ها، به ازای هر کوئری که هر کاربر وارد می کند، قابل ثبت هستند. همچنین می توانیم مجموعه c را برای هر کوئری (بصورت unique شده) با در نظر گرفتن فرکانس هر سند، بزرگتر کنیم - به این دلیل که کاربران مختلفی ممکن است کوئری یکسانی را وارد کنند (درباره اشتراک کوئری های کاربران در ادامه حرف می زنیم).اطلاعاتی که از تحلیل این داده ها بدست می آیند، می توانند به رتبه بندی «نسبی» اسناد در رنکینگ مربوط به یک کوئری، به کار بیایند. این اطلاعات، به شکل زیر قابل استفاده اند:سه تایی ای که بالاتر برای کوئری "support vector machine" معرفی شد را در نظر بگیرید. با استفاده از الگوریتم زیر، می توانیم اطلاعات مورد نیازمان را استخراج کنیم.معرفی نمادگذاری: در اینجا منظور از *r، رنکینگ مطلوب (ایده آل) می باشد. و نماد *r> به معنای ترتیب قرار گیری اسناد در رنکینگ ایده آل (*r) می باشد.پس برای تصویر بالا، نتایج به این شکل خواهند بود.در نهایت، این pair ها و همچنین feature های استخراج شده مربوطه دیگر (که قبلا درباره آنها حرف زدیم) را به عنوان ورودی به الگوریتم SVM می دهیم و مدلمان را آموزش می دهیم. توجه داشته باشید که مراحل پیچیده تری برای طراحی توابعی که باید بهینه شوند و تعریف پارامتر های بهینه سازی طی می شود که از بیان آنها در این مطلب پرهیز می کنیم.از این مدل، می توان به عنوان تابع re-ranking استفاده کرد و پس از بازیابی نتایج از موتور ایندکس کننده، با توجه به این تابع، رتبه بندی بهتری را به کاربر ارائه کرد.کوئری های تکراریطبق این پست که در بلاگ گوگل منتشر شده، گوگل ادعا می کند که تنها ۱۵ درصد از کوئری هایی که در هرروز دریافت می کنند کوئری هایی هستند که جدیدند!We see billions of queries every day, and 15 percent of queries are ones we’ve never seen before. Given this scale, the only way to provide Search effectively is through an algorithmic approach. This helps us not just solve all the queries we’ve seen yesterday, but also all the ones we can’t anticipate for tomorrow.با یک پردازش ساده بروی کوئری های وارد شده در موتور جستجو ترب، در طول یک ماه، به این نتیجه رسیدیم که چیزی نزدیک به ۶۰ درصد کوئری هایی که در طول روز توسط کاربران وارد می شوند، در بازه زمانی یک ماه قبل از هر روز، حداقل ۱ بار تکرار شده اند. این نکته، بسیار جالب توجه است! متاسفانه، این موضوع، هم بُعد خوب دارد و هم بُعد بد. قابلیت پردازش و رتبه بندی آفلاین نتایج مربوط به کوئری های پر طرفدار، می تواند منجر به مهندسی نتایج و نمایش نتایج دلخواه سازمان ها (!!) در نتایج شود. مسأله پرفورمنس و کم کردن بار روی موتور ایندکس کننده، با cache کردن کوئری ها و نتایجشان، آنچنان موضوع مهمی نیست. به این دلیل که این موتور ها، قابلیت مقیاس پذیری بالایی دارند و به راحتی می توانند چندین هزار درخواست در ثانیه را پاسخ دهند. اما این پردازش آفلاین واقعا می تواند به بهبود نتایج کمک کند.--ممنون از اینکه توجه کردید و تا انتهای این مطلب را خواندید. امیدوارم توانسته باشم چالش های مربوط به طراحی یک موتور جستجو را تا حد ممکن توضیح داده باشم و این مطلب بتواند نقطه آغاز مناسبی برای افراد و سازمان هایی که با یک موتور جستجو سر و کار دارند و به دنبال بهبود نتایجشان هستند، باشد.سعی کردم تمامی منابع را بصورت hyperlink در دل مطالب بگنجونم تا برای مطالعه بیشتر و عمیق تر بتوانید از همین نوشته استفاده کنید. نیما یزدان مهر نیما یزدان مهر Fri, 25 Jan 2019 15:48:48 +0330 https://virgool.io/@n1rna/%D9%85%D9%88%D8%AA%D9%88%D8%B1%D9%87%D8%A7%DB%8C-%D8%AC%D8%B3%D8%AA%D8%AC%D9%88-%D8%A8%D8%B1%D8%B1%D8%B3%DB%8C-%D9%86%D8%AD%D9%88%D9%87-%D8%B9%D9%85%D9%84%DA%A9%D8%B1%D8%AF-%D9%88-%D9%BE%DB%8C%D8%A7%D8%AF%D9%87-%D8%B3%D8%A7%D8%B2%DB%8C-%D9%82%D8%B3%D9%85%D8%AA-%D8%A7%D9%88%D9%84-bd9wy1t3baws در این نوشته، سعی میکنم بصورت کلی، نحوه کارکرد موتورهای جستجو در فضای وب رو بررسی کنم و همچنین بصورت خاص، از تجربه ای که در سه ماه کار کردن روی موتور جستجو سرویس ترب کسب کردم، بنویسم. در قسمت اول این نوشته دو بخشی، سعی کرده ام درباره مفاهیم اولیه جستجو و موتور های جستجو صحبت کنم و چالش ها را معرفی کنم. خواندن این بخش، برای افرادی که سررشته ای از مفاهیم فنی ندارند هم، بسیار توصیه می شود. به این دلیل که وقتی با این مفاهیم اولیه آشنا باشید، جستجو کردن شما در فضای وب، قطعا بهبود خواهد یافت.با توجه به اینکه ترجمه کلمات انگلیسی، در اکثر موارد، باعث ایجاد سردرگمی و گاها برداشت اشتباه می شود، در این نوشته، هیچ تلاشی برای ترجمه کلمات، یا نوشتن لغات با املای فارسی، نشده است. همچنین به این دلیل که این نوشته، اولین تجربه بنده در تشریح یک موضوع فنی و تا حدی تخصصی بصورت مکتوب می باشد، امیدوارم کمی ها و کاستی ها را به بزرگی خودتون ببخشید. :)شاید اولین برخورد اکثر ما با مفهومی به اسم «موتور جستجو»، سرویس جستجوگر غولی به نام گوگل بوده است. هرچند گوگل هرگز ادعای «اولین» بودن در این عرصه را نکرده است؛ اما بدون تردید، میتوان گفت که تجربه کاربری بهتر و دقیق تری از گوگل را، در موتور جستجو دیگری، نخواهید یافت! گوگل با دریافت بیش از ۷۵ درصد کوئری های سرچ در دنیا، با در اختیار داشتن بیش از هزار ترابایت اطلاعات، ذخیره شده بر روی سرور هایش و همچنین میلیون ها (میلیارد؟) کاربر در سرتاسر دنیا، در دهه اخیر، به حق، یا به ناحق، به صفت «غیر قابل مقایسه» بودن دست یافته. اما بیایید این موضوع را در ذهنمان داشته باشیم که، راهی که گوگل با استفاده از آن به این اقتدار رسیده، احتمالا بهترین و عادلانه ترین راه، نبوده.ما به دنبال چه چیزی میگردیم؟این سوال، سوال مهمی است. قبل از اینکه به جزئیات فنی، وارد شویم، بهتر است درباره این موضوع هم کمی صحبت کنیم. موتور های جستجو مختلفی در دنیا وجود دارند. اما همه آنها جستجوگر صفحات وب، نیستند. صفحات وب، تنها یک نوع از اسنادی هستند که جستجو روی آنها انجام میشود و اهمیت دارد. کتاب ها، تصاویر، فیلم ها، موزیک ها، افراد (نام، انواع شماره های شناسایی، ...)، موقعیت های جغرافیایی و شاید صدها نوع دیگر از اسناد در دنیا وجود دارند که جستجو برروی آنها معنا دارد و از اهمیت بالایی هم برخوردار است. بصورت کلی، اگر تعداد بالایی از هر نوع موجودیتی را در اختیار داشته باشید و به دنبال یک instance خاص از نوع اون موجودیت باشید، یا به یک موتور جستجو نیاز دارید، یا خودتان در مقام یک موتور جستجو در حال عملکرد هستید. در طراحی ساختار یک موتور جستجو، مشخص بودن نوع اسناد مورد جستجو، در بخش های مختلفی، اهمیت خودش را نشان می دهد. انتخاب (طراحی) موتور index کننده، استخراج مشخصه ها (features)، طراحی رابط کاربری نمایش دهنده نتایج و دریافت کوئری و ... پس نکته اول در ورود به مسأله «جستجو»، مشخص کردن نوع سند مورد جستجو می باشد.الگوریتم های جستجواحتمالا با الگوریتم های مختلف جستجو، مثل سرچ خطی (linear search)، سرچ دودویی (binary search) و ... آشنا هستید. شاید بپرسید که موتور های جستجو، از کدامیک از این الگوریتم ها استفاده میکنند؟ جواب شما را اینطور میدهم که، هیچکدام و در عین حال، همه آنها. جمله ای نسبتا کلیشه ای، در عین حال صحیح. الگوریتم سرچ خطی، بصورت میانگین، دارای پیچیدگی زمانی o(n) می باشد. سرچ دودویی با ایجاد بهبودی چشمگیر، دارای پیچیدگی زمانی o(log n) می باشد. می توانید تصور کنید که گوگل، با داشتن بیش از ۳۰ میلیارد صفحه crawl شده، اگر بخواهد از این الگوریتم ها استفاده کند، هربار جستجو کردن شما، چقدر زمان می برد؟ در اصل، موتور های جستجو، کارشان رتبه بندی اسناد، نسبت به یکدیگر می باشد و نه یافتن یک سند خاص، از میان میلیارد ها سند موجود. پس استفاده از این الگوریتم ها درواقع، به کاری که موتور های جستجو انجام می دهند، آنچنان مربوط نیست.رتبه بندی اسنادبخش قبلی رو با این جمله تموم کردیم که، موتور های جستجو، کارشون پیدا کردن یک سند بصورت خاص، نیست. هرچند، این سیستم ها، در عمل، چنین قابلیتی «هم» دارند. پس کاربرد اصلی این سیستم ها، چیست؟ به نحوه جستجو کردن خودتان فکر کنید. شما صفحه جستجوگر موردنظر خودتون رو باز می کنید و جمله ای شبیه به «چگونه ماکارونی بپزیم» را وارد می کنید. شما انتظار دارید که در نهایت به صفحه ای برسید، که در آن دستور پخت ماکارونی وجود داشته باشد؛ در صورتی که صفحه مورد نظر شما، شاید هیچوقت شامل رشته (string) «چگونه ماکارونی بپزیم» نباشد. پس چطور ممکن است که این صفحه به عنوان اولین لینک، به شما پیشنهاد شده باشد؟ حتما تابحال اسم SEO به گوشتان خورده است. این کلمه مخفف Search Engine Optimization، به معنای «بهبود موتور های جستجو» می باشد. خب درواقع این مفهوم، به معنای بهبود کارکرد خود یک موتور جستجو، نمی باشد. این مفهوم، به بهبود پارامتر های یک صفحه، در فضای وب، به منظور یافته شدن بهتر آن صفحه، توسط موتور های جستجو می باشد. کار یک موتور جستجو، بصورت دقیق، پیدا کردن «مرتبط ترین» صفحات با ورودی شما (از این به بعد، به ورودی کاربر، میگوییم کوئری - query) می باشد. اگر کوئری شما، «چگونه ماکارونی بپزیم» باشد، موتور جستجو، سعی می کند که «تمام» صفحات وب (صفحاتی که توسط آن موتور جستجو ایندکس(!) شده اند) را، با توجه به میزان ارتباطشان با کوئری وارد شده، رتبه بندی کند و نتایج را در اختیار شما بگذارد. هرچقدر در صفحات نتایج، جلوتر بروید، به نتایجی با ارتباط «کمتر» با کوئری وارد شده می رسید. پارامتر های بسیار زیادی برای تخمین زدن میزان ارتباط یک صفحه، با یک کوئری وجود دارد. حالا می توان دید که SEO در واقع چه معنایی دارد. اگر شما یک وبسایت مرتبط به آشپزی دارید و در آن دستور پخت غذاهای مختلف را قرار می دهید، برای اینکه وبسایت شما در نتایج صفحه اول گوگل نمایش داده شود، باید پارامتر هایی که گوگل برای تخمین میزان ارتباط صفحات، با کوئری ها در نظر میگیرد را، بدانید، و سعی کنید که آن پارامتر ها را با توجه به الگوریتم های گوگل، بهینه کنید.پارامتر های اصلی تخمین میزان ارتباطاگر بخواهیم این پارامتر ها را، یک به یک، بررسی کنیم، نه تنها از مقصود اصلی این نوشته، دور می شویم، بلکه به دلیل طولانی شدن این بحث، احتمالا قابلیت خوانده شدن این نوشته هم از بین خواهد رفت! اما بصورت خلاصه، اصلی ترین پارامتر ها را بررسی میکنیم.مورد اول و شاید مهم ترین مورد در «بالاتر» قرار گرفتن یک صفحه، نسبت به یک صفحه دیگر، رتبه وبسایت شامل آن صفحه، بین تمام وبسایت های دیگر می باشد. احتمالا نام سرویس alexa، را شنیده اید. این سرویس، تمام وبسایت های دنیا را با توجه به پارامتر های بسیار زیادی، در یک رتبه بندی قرار می دهد. پارامترهایی که الکسا، با توجه به آنها، وبسایت ها را رتبه بندی میکند، شامل میزان بازدید، موقعیت جغرافیایی بازدید ها، میزان زمان گذرانده شده توسط کاربران در یک وبسایت، میزان ورودی های یک وبسایت از منابع مختلف (لینک یک وبسایت در وبسایت های دیگر) و ... می باشد. هرچند این پارامتر، خیلی پارامتر قابل اتکایی نیست. موضوع رتبه بندی صفحات و وبسایت ها، موضوع بسیار مهمی است. شبکه بزرگی از لینک های ریفرال و وبسایت های مبدأ و مقصد، اعداد بسیار دقیق تری برای رتبه بندی وبسایت ها تولید می کنند. این شبکه، می تواند میزان تاثیر گذاری وبسایت ها را در دسته بندی های مختلف و لینک های ورودی و خروجی از این وبسایت های تاثیر گذار را با دقت خوبی محاسبه کند. اطلاعات بسیار خوبی درباره الگوریتم رتبه بندی وبسایت ها در گوگل، در این صفحه قابل دسترسی است.موارد دیگری که خود یک موتور جستجو بصورت مستقل، یک صفحه را بررسی می کند و میزان ارتباطش با یک کوئری را می سنجد، شامل موارد زیر می شود:پینوشت: پارامتر هایی که در زیر، لیست شده اند، ابتدایی ترین پارامتر های ممکن هستند. در ادامه خواهیم دید که موتور های جستجو بسیار پیشرفته تر، چگونه با استفاده از مفاهیم یادگیری ماشین، پردازش زبان های طبیعی (nlp)، مفاهیمی مثل nlu و پارامتر های پیچیده تر (بخوانید ترسناک تر) دیگر، نتایج بهتری را به شما نمایش می دهند.وجود تک تک کلمات یک کوئری، در متن آن صفحهمیزان تکرار هر یک از کلمات (فرکانس) یک کوئری، در متن آن صفحهتعداد تبلیغات موجود در آن صفحهحجم محتوای موجود در آن صفحه (انواع فرمت تصاویر، نوشته، فایل های استاتیک css/js و ...)طول جملات تیتر در آن صفحه (طول تیتر ها، پارامتر مهمی است و کوتاه بودن تیتر ها، باعث بهبود تجربه کاربر می شود)طول لینک صفحه (تعداد کاراکتر ها)پروتوکل های ارتباطی آن صفحه (امن بودن ارتباط، گواهینامه ssl، تعداد و نوع ریکوئست های کلاینت به سرور موجود در آن صفحه)گزارش ها و فیدبک های کاربران قبلی که آن صفحه را بازدید کرده اند...ایندکس کردن به چه معناست؟ (Indexing)بصورت کلی، مفهوم ایندکس کردن، به معنای ذخیره کردن و قرار دادن داده ها در ساختاری است که چند قابلیت برای ما به همراه دارد. مهم ترین قابلیت این ساختار ها، سرعت بالای بازیابی اطلاعات (data retrieval) می باشد. مهم ترین تفاوت یک indexing engine با یک DBMS، در نحوه parse کردن دیتا ها و نوع ساختمان داده مورد استفاده برای ذخیره سازی و نگهداری دیتا ها می باشد. برای اینکه بخواهید حضور یک کلمه را در تمام اسناد ذخیره شده برروی دیتابیس خود، چک کنید، نیاز دارید که تمام رکورد های دیتابیس خود را یک بار بررسی کنید. حتی با این فرض که پیچیدگی زمانی دسترسی به یک رکورد در DBMS شما o(1) باشد، باز هم در مواردی که دیتابیس شما شامل چندین میلیون رکورد باشد، عمل بررسی تک تک آنها، زمان قابل توجهی طول خواهد کشید. این در صورتی است که اگر همین میزان داده را در یک indexing engine، ایندکس کنید، بررسی حضور یک کلمه در تمامی این چند میلیون رکورد، در حدود چند میلی ثانیه زمان میبرد. برای اینکه بیشتر با مفهوم ایندکسینگ آشنا بشیم، بهتر است ابتدا با برخی الگوریتم ها و روش ها که در این موتور ها استفاده می شوند، آشنا شویم.ابتدا اجازه بدهید که برای اسنادمان، یک ساختار تعریف کنیم. شاید بهتر باشد که یک نوع سند را، پیشفرض ادامه صحبت هایمان قرار دهیم. فرض کنیم اسنادی که میخواهیم روی آنها جستجو کنیم، از نوع محصولات فروشگاهی باشند. محصولات فروشگاهی هم، مثل اسناد دیگر، مشخصه های مختلفی دارند.چندتا از این مشخصه ها:نام محصول به فارسینام محصول به انگلیسیدسته بندیمشخصات فنی محصول (specifications)برند (کارخانه تولید کننده)...پس table دیتابیس ما، شامل این ستون ها (فیلد) خواهد بود.توضیحات زیر، تا حد زیادی، از این صفحه برداشته/ترجمه شده است.همونطور که گفتیم، موتور های ایندکسینگ کار اصلیشون، رتبه بندی اسناد بر اساس میزان ارتباطشون با کوئری وارد شده توسط کاربر هست. یکی از اصلی ترین روش هایی که برای تخمین میزان ارتباط اسناد (متنی)، استفاده می شود، روش TF/IDF هست. این عبارت، کوتاه شده عبارت Term Frequency/Inverse Document Frequency هست. بخش اول این عبارت (Term Frequency)، به معنای «فرکانس یک کلمه خاص، در یک فیلد» می باشد. پس اگر یک محصول، در فیلد مربوط به نام فارسی، ۳ بار، کلمه «آیفون» را داشته باشد، احتمال مرتبط بودنش به کوئری «آیفون»، بیشتر از محصولی است که در همان فیلد، کلمه «آیفون»، ۱ بار تکرار شده باشد. پس در روش TF، کار ما، این هست که فرکانس هر کلمه را در هر فیلد مربوط به هر سند، محاسبه کنیم. بخش دوم عبارت TF/IDF، به نوعی، حالت معکوس روش اول است. در این روش (Inverse Document Frequency)، میزان تکرار یک کلمه خاص را در تمام اسناد محاسبه می کنیم. اگر کمی دقت کنید، متوجه این موضوع می شوید که، هرچه تعداد تکرار یک کلمه خاص، در تمام اسناد، بیشتر باشد، میزان تاثیر گذار بودن آن کلمه، کمتر است. برای مثال، در اسناد از نوع محصولات فروشگاهی، کلمه هایی مثل «مدل»، «گوشی» و کلمات مشابه در فارسی و کلمه هایی مثل «and» و «the» در انگلیسی، کلمات به شدت پر تکراری در اسم محصولات مختلف به شمار می آیند که عملا در جستجو کاربر و تخمین میزان ارتباط اسناد، بی تاثیر هستند. پارامتر بعدی، تعداد کلمات موجود در یک فیلد است. هرچقدر طول یک فیلد، کمتر باشد، میزان تاثیر گذاری اش، بیشتر است. فرمول هایی که برای محاسبه هریک از این سه پارامتر، استفاده می شود، در زیر آمده است.tf(t in d) = √frequency idf(t) = 1 + log ( numDocs / (docFreq + 1)) - (طول یک فیلد) norm(d) = 1 / √numTerms با در اختیار داشتن مقدار این پارامتر ها، می توانیم امتیاز یک کلمه خاص، در یک فیلد (در واقع در یک سند) را محاسبه کنیم.پس از محاسبه این امتیاز ها برای هر یک از کلمات، ما یک دیکشنری از کلمه های موجود در بین تمام اسناد و امتیازشان، در اختیار داریم. ساخت این دیکشنری، مهم ترین قسمت مفهوم ایندکس کردن اسناد توسط Indexing engine ها می باشد.روشی که در کار کردن با Indexing engine ها، مرسوم است، اضافه کردن یک فیلد جدید، مخصوص جستجو، به فیلد های فعلی سند هایمان است. فرض کنید که فیلد جدیدی که اضافه کرده ایم، ترکیبی از فیلد های «نام فارسی محصول»، «نام انگلیسی محصول» و «برند» آن محصول می باشد. این روش، تا حد خوبی، کار را برای موتور ایندکس کننده ما، آسان می کند. به این دلیل که، ما می توانیم بخش های مختلفی از فیلد های مختلف را بصورت پیش-پردازش شده (pre processed)، در آن فیلد ذخیره کنیم و فرایند پردازش فیلد های سند را یک مرحله بهبود دهیم. فایده دیگر این کار را در مرحله tokenization خواهیم دید.فرض کنید که کاربر، کوئری «گوشی آیفون ایکس» را جستجو کرده است. اسنادی که ما آنها را در سیستم خود، ایندکس کرده ایم هم، به شرح زیر می باشند:گوشی آیفون xآیفون مدل ایکس اسگوشی آیفون 8میخواهیم بصورت فرضی، اعدادی را بعنوان وزن هر یک از کلمات موجود در این سند ها، به هریک نسبت دهیم. کلمه ای مثل کلمه «گوشی» با توجه به پرتکرار بودنش، باید نسبتا وزن کمی در حد ۲ داشته باشد. کلمه «آیفون» هم کلمه پرتکراری محسوب می شود، اما نسبت به کلمه «گوشی» قطعا وزن بیشتری خواهد داشت. پس وزن ۴ را نیز به کلمه «آیفون» نسبت می دهیم. در نهایت، کلمه «ایکس» را داریم. حقیقتا، نمی توانم تصمیم درستی درباره وزن این کلمه بگیرم، اما احتمالا، وزن این کلمه هم فقط کمی، کمتر از کلمه «آیفون» می باشد. پس وزن ۳.۵ را به کلمه «ایکس» نسبت می دهیم. دنباله این اعداد (وزن کلمات) در واقع، تشکیل برداری می دهند، که می توانیم جمله «گوشی آیفون ایکس» را به این بردار، در فضای برداری کلمات، نسبت دهیم. پس تا اینجای کار، با نحوه تبدیل کردن دنباله n تایی از کلمات، به یک بردار n بعدی عددی، آشنا شدیم. در نتیجه بردار کوئری کاربر، برابر با [2, 4, 3.5] می باشد. حال، با روشی مشابه، برای هر یک از اسناد موجود، برداری n بعدی، تشکیل می دهیم. برداری که تشکیل دادیم، در واقع یک map از دنباله [گوشی، آیفون، ایکس] می باشد. حال همین mapping رو به این شکل در نظر بگیرید، که به ازای حضور هر یک از درایه های این بردار، در یک سند، امتیاز، و در غیر اینصورت، صفر جایگزین میکنیم. برای مثال، بردار متناسب با سند "آیفون مدل ایکس اس"، به شکل [0, 4, 3.5] می باشد. یا بردار سند "گوشی آیفون x" برابر با [2, 4, 0] خواهد بود.در نهایت، ما توانستیم به ازای هر کوئری وارد شده توسط کاربر، برای هر یک از اسناد ایندکس شده، یک بردار تولید کنیم. استفاده اصلی این بردار ها، در واقع، برای پیدا کردن (تعریف کردن) یک نوع فاصله قابل سنجش میان کوئری و اسناد، و اسناد نسبت به یکدیگر، می باشد. در ریاضیات، در هر فضای برداری n بعدی، میان بردار های آن فضا، مفهوم فاصله، قابل تعریف است. همین تعریف را بعنوان فاصله میان بردار هایی که خودمان ساخته ایم، تصور کنید. برای مثال، در یک فضای دو بعدی، میتوان کسینوس زاویه میان دو بردار را، بعنوان فاصله دو بردار در نظر گرفت. بر همین اساس، می توان تمام اسناد موجود در موتور ایندکس کننده را، بر اساس میزان ارتباط با کوئری وارد شده توسط کاربر، مرتب سازی کرد.دو نکته قابل توجه دیگر درباره کارکرد موتور های ایندکس کننده، موضوع tokenizations و الگوریتم N-gram و نحوه ذخیره سازی داده ها برروی ماشین های مختلف (نگهداری داده ها به روی رم بصورت memory intensive، کلاسترینگ و شاردینگ) می باشند.شاید برایتان جالب باشد که اصولا «کلمه» ها در یک متن، چطور مشخص می شوند. برای مثال کلماتی مثل «قهوه ای»، «شاهنامه»، «موتور جستجو»، «نقشه» یا بسیاری کلمات دیگر، چگونه و با چه معیاری قسمت قسمت می شوند. ساده ترین ایده، جدا کردن کلمات با استفاده از جدا کننده (delimiter) های مختلف است. برای مثال، می گوییم، هرجا به کاراکتر هایی مثلwhite spaces (new line, space, نیم-فاصله, ..), special characters (- , . * & _ ...)رسیدیم، فرض کنیم که به انتهای یک کلمه رسیده ایم. به این عمل قسمت قسمت کردن متن، tokenization می گویند. هر توکن، بعنوان یک کلمه کامل در نظر گرفته می شود. پس هرگاه ما درباره کلمات مجزا، صحبت میکنیم، منظورمان، هر یک از این توکن ها می باشد. اگر این مفهوم را کمی extend کنیم، به مفهوم الگوریتم N-gram می رسیم. این نوع از tokenization که درباره آن حرف زدیم، درواقع قسمت کردن متن به 1-gram ها می باشد. با توجه به delimiter هایی که تعریف کرده ایم، هر n توکن که در کنار هم قرار بگیرند، تشکیل n-gram می دهند. به مثال زیر توجه کنید:جمله (متن): The quick brown fox jumps over the lazy dog 1-gram(s):['The', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog'] 2-gram(s): ['The quick', 'quick brown', 'brown fox', 'fox jumps', 'jumps over', 'over the', 'the lazy', ' lazy dog']به همین شکل، می توانیم n-gram ها را تشکیل دهیم. این الگوریتم، در زمینه nlp (پردازش زبان های طبیعی)، کاربرد های زیاد دارد. از جمله مهم ترین کاربرد های این الگوریتم، پیدا کردن phrase ها، در یک متن می باشد. برای اطلاعات بیشتر درباره این الگوریتم هم پیشنهاد میکنم صفحه ویکی پدیا این الگوریتم رو یه بررسی بکنید.تا اینجای کار، با مفاهیم ابتدایی موتور های جستجو و نحوه کارکردشان آشنا شدیم. سعی کردم در بخش اول، به زبان ساده و قابل فهم برای همه، این مفاهیم رو توضیح بدم و امیدوارم که مفید بوده باشه. اما! هیچ موتور جستجو قدرتمندی، با استفاده از یک موتور ایندکس کننده، به تنهایی، هیچوقت توانایی و قابلیت این رو نخواهد داشت که نتایجی، به دقیقی نتایجی که روزانه در گوگل یا داک داک گو میبینید، به شما ارائه کند. مراحل و لایه های زیادی، بین کوئری وارد شده تا موتور ایندکس کننده و همینطور از نتایج ارائه شده توسط موتور ایندکس کننده تا نتایجی که به دست کاربر می رسند، وجود دارند. موتور های ایندکس کننده نیز، خودشان مراحل پیچیده تری را، نسبت به چیزی که در این نوشته توضیح داده شد، برای رتبه بندی دقیق تر اسناد، انجام می دهند. در بخش بعدی این نوشته، سعی می کنم از پیش-پردازش هایی که روی کوئری ها انجام می شود، الگوریتم های مربوط به رتبه بندی اسناد با استفاده از تجربه کاربران قبلی که اصطلاحا learn2rank گفته میشه بهشون و الگوریتم های مربوط به پردازش زبان های طبیعی که با بحث جستجو و رتبه بندی دقیق تر اسناد با توجه به کوئری وارد شده، می شوند، بنویسم.لینک قسمت دوم این نوشته، پس از انتشار، در انتهای همین نوشته، قرار خواهد گرفت.-- ویرایش --لینک قسمت دوم این نوشته: https://virgool.io/@n1rna/fccobe4lkgql نیما یزدان مهر نیما یزدان مهر Fri, 04 Jan 2019 16:57:00 +0330