در این نوشته، سعی میکنم بصورت کلی، نحوه کارکرد موتورهای جستجو در فضای وب رو بررسی کنم و همچنین بصورت خاص، از تجربه ای که در سه ماه کار کردن روی موتور جستجو سرویس ترب کسب کردم، بنویسم.
در قسمت اول این نوشته دو بخشی، سعی کرده ام درباره مفاهیم اولیه جستجو و موتور های جستجو صحبت کنم و چالش ها را معرفی کنم. خواندن این بخش، برای افرادی که سررشته ای از مفاهیم فنی ندارند هم، بسیار توصیه می شود. به این دلیل که وقتی با این مفاهیم اولیه آشنا باشید، جستجو کردن شما در فضای وب، قطعا بهبود خواهد یافت.
با توجه به اینکه ترجمه کلمات انگلیسی، در اکثر موارد، باعث ایجاد سردرگمی و گاها برداشت اشتباه می شود، در این نوشته، هیچ تلاشی برای ترجمه کلمات، یا نوشتن لغات با املای فارسی، نشده است. همچنین به این دلیل که این نوشته، اولین تجربه بنده در تشریح یک موضوع فنی و تا حدی تخصصی بصورت مکتوب می باشد، امیدوارم کمی ها و کاستی ها را به بزرگی خودتون ببخشید. :)
شاید اولین برخورد اکثر ما با مفهومی به اسم «موتور جستجو»، سرویس جستجوگر غولی به نام گوگل بوده است. هرچند گوگل هرگز ادعای «اولین» بودن در این عرصه را نکرده است؛ اما بدون تردید، میتوان گفت که تجربه کاربری بهتر و دقیق تری از گوگل را، در موتور جستجو دیگری، نخواهید یافت! گوگل با دریافت بیش از ۷۵ درصد کوئری های سرچ در دنیا، با در اختیار داشتن بیش از هزار ترابایت اطلاعات، ذخیره شده بر روی سرور هایش و همچنین میلیون ها (میلیارد؟) کاربر در سرتاسر دنیا، در دهه اخیر، به حق، یا به ناحق، به صفت «غیر قابل مقایسه» بودن دست یافته. اما بیایید این موضوع را در ذهنمان داشته باشیم که، راهی که گوگل با استفاده از آن به این اقتدار رسیده، احتمالا بهترین و عادلانه ترین راه، نبوده.
این سوال، سوال مهمی است. قبل از اینکه به جزئیات فنی، وارد شویم، بهتر است درباره این موضوع هم کمی صحبت کنیم. موتور های جستجو مختلفی در دنیا وجود دارند. اما همه آنها جستجوگر صفحات وب، نیستند. صفحات وب، تنها یک نوع از اسنادی هستند که جستجو روی آنها انجام میشود و اهمیت دارد. کتاب ها، تصاویر، فیلم ها، موزیک ها، افراد (نام، انواع شماره های شناسایی، ...)، موقعیت های جغرافیایی و شاید صدها نوع دیگر از اسناد در دنیا وجود دارند که جستجو برروی آنها معنا دارد و از اهمیت بالایی هم برخوردار است. بصورت کلی، اگر تعداد بالایی از هر نوع موجودیتی را در اختیار داشته باشید و به دنبال یک instance خاص از نوع اون موجودیت باشید، یا به یک موتور جستجو نیاز دارید، یا خودتان در مقام یک موتور جستجو در حال عملکرد هستید. در طراحی ساختار یک موتور جستجو، مشخص بودن نوع اسناد مورد جستجو، در بخش های مختلفی، اهمیت خودش را نشان می دهد. انتخاب (طراحی) موتور index کننده، استخراج مشخصه ها (features)، طراحی رابط کاربری نمایش دهنده نتایج و دریافت کوئری و ... پس نکته اول در ورود به مسأله «جستجو»، مشخص کردن نوع سند مورد جستجو می باشد.
احتمالا با الگوریتم های مختلف جستجو، مثل سرچ خطی (linear search)، سرچ دودویی (binary search) و ... آشنا هستید. شاید بپرسید که موتور های جستجو، از کدامیک از این الگوریتم ها استفاده میکنند؟ جواب شما را اینطور میدهم که، هیچکدام و در عین حال، همه آنها. جمله ای نسبتا کلیشه ای، در عین حال صحیح. الگوریتم سرچ خطی، بصورت میانگین، دارای پیچیدگی زمانی o(n) می باشد. سرچ دودویی با ایجاد بهبودی چشمگیر، دارای پیچیدگی زمانی o(log n) می باشد. می توانید تصور کنید که گوگل، با داشتن بیش از ۳۰ میلیارد صفحه crawl شده، اگر بخواهد از این الگوریتم ها استفاده کند، هربار جستجو کردن شما، چقدر زمان می برد؟ در اصل، موتور های جستجو، کارشان رتبه بندی اسناد، نسبت به یکدیگر می باشد و نه یافتن یک سند خاص، از میان میلیارد ها سند موجود. پس استفاده از این الگوریتم ها درواقع، به کاری که موتور های جستجو انجام می دهند، آنچنان مربوط نیست.
بخش قبلی رو با این جمله تموم کردیم که، موتور های جستجو، کارشون پیدا کردن یک سند بصورت خاص، نیست. هرچند، این سیستم ها، در عمل، چنین قابلیتی «هم» دارند. پس کاربرد اصلی این سیستم ها، چیست؟ به نحوه جستجو کردن خودتان فکر کنید. شما صفحه جستجوگر موردنظر خودتون رو باز می کنید و جمله ای شبیه به «چگونه ماکارونی بپزیم» را وارد می کنید. شما انتظار دارید که در نهایت به صفحه ای برسید، که در آن دستور پخت ماکارونی وجود داشته باشد؛ در صورتی که صفحه مورد نظر شما، شاید هیچوقت شامل رشته (string) «چگونه ماکارونی بپزیم» نباشد. پس چطور ممکن است که این صفحه به عنوان اولین لینک، به شما پیشنهاد شده باشد؟ حتما تابحال اسم SEO به گوشتان خورده است. این کلمه مخفف Search Engine Optimization، به معنای «بهبود موتور های جستجو» می باشد. خب درواقع این مفهوم، به معنای بهبود کارکرد خود یک موتور جستجو، نمی باشد. این مفهوم، به بهبود پارامتر های یک صفحه، در فضای وب، به منظور یافته شدن بهتر آن صفحه، توسط موتور های جستجو می باشد. کار یک موتور جستجو، بصورت دقیق، پیدا کردن «مرتبط ترین» صفحات با ورودی شما (از این به بعد، به ورودی کاربر، میگوییم کوئری - query) می باشد. اگر کوئری شما، «چگونه ماکارونی بپزیم» باشد، موتور جستجو، سعی می کند که «تمام» صفحات وب (صفحاتی که توسط آن موتور جستجو ایندکس(!) شده اند) را، با توجه به میزان ارتباطشان با کوئری وارد شده، رتبه بندی کند و نتایج را در اختیار شما بگذارد. هرچقدر در صفحات نتایج، جلوتر بروید، به نتایجی با ارتباط «کمتر» با کوئری وارد شده می رسید. پارامتر های بسیار زیادی برای تخمین زدن میزان ارتباط یک صفحه، با یک کوئری وجود دارد. حالا می توان دید که SEO در واقع چه معنایی دارد. اگر شما یک وبسایت مرتبط به آشپزی دارید و در آن دستور پخت غذاهای مختلف را قرار می دهید، برای اینکه وبسایت شما در نتایج صفحه اول گوگل نمایش داده شود، باید پارامتر هایی که گوگل برای تخمین میزان ارتباط صفحات، با کوئری ها در نظر میگیرد را، بدانید، و سعی کنید که آن پارامتر ها را با توجه به الگوریتم های گوگل، بهینه کنید.
اگر بخواهیم این پارامتر ها را، یک به یک، بررسی کنیم، نه تنها از مقصود اصلی این نوشته، دور می شویم، بلکه به دلیل طولانی شدن این بحث، احتمالا قابلیت خوانده شدن این نوشته هم از بین خواهد رفت! اما بصورت خلاصه، اصلی ترین پارامتر ها را بررسی میکنیم.
مورد اول و شاید مهم ترین مورد در «بالاتر» قرار گرفتن یک صفحه، نسبت به یک صفحه دیگر، رتبه وبسایت شامل آن صفحه، بین تمام وبسایت های دیگر می باشد. احتمالا نام سرویس alexa، را شنیده اید. این سرویس، تمام وبسایت های دنیا را با توجه به پارامتر های بسیار زیادی، در یک رتبه بندی قرار می دهد. پارامترهایی که الکسا، با توجه به آنها، وبسایت ها را رتبه بندی میکند، شامل میزان بازدید، موقعیت جغرافیایی بازدید ها، میزان زمان گذرانده شده توسط کاربران در یک وبسایت، میزان ورودی های یک وبسایت از منابع مختلف (لینک یک وبسایت در وبسایت های دیگر) و ... می باشد. هرچند این پارامتر، خیلی پارامتر قابل اتکایی نیست. موضوع رتبه بندی صفحات و وبسایت ها، موضوع بسیار مهمی است. شبکه بزرگی از لینک های ریفرال و وبسایت های مبدأ و مقصد، اعداد بسیار دقیق تری برای رتبه بندی وبسایت ها تولید می کنند. این شبکه، می تواند میزان تاثیر گذاری وبسایت ها را در دسته بندی های مختلف و لینک های ورودی و خروجی از این وبسایت های تاثیر گذار را با دقت خوبی محاسبه کند. اطلاعات بسیار خوبی درباره الگوریتم رتبه بندی وبسایت ها در گوگل، در این صفحه قابل دسترسی است.
موارد دیگری که خود یک موتور جستجو بصورت مستقل، یک صفحه را بررسی می کند و میزان ارتباطش با یک کوئری را می سنجد، شامل موارد زیر می شود:
پینوشت: پارامتر هایی که در زیر، لیست شده اند، ابتدایی ترین پارامتر های ممکن هستند. در ادامه خواهیم دید که موتور های جستجو بسیار پیشرفته تر، چگونه با استفاده از مفاهیم یادگیری ماشین، پردازش زبان های طبیعی (nlp)، مفاهیمی مثل nlu و پارامتر های پیچیده تر (بخوانید ترسناک تر) دیگر، نتایج بهتری را به شما نمایش می دهند.
بصورت کلی، مفهوم ایندکس کردن، به معنای ذخیره کردن و قرار دادن داده ها در ساختاری است که چند قابلیت برای ما به همراه دارد. مهم ترین قابلیت این ساختار ها، سرعت بالای بازیابی اطلاعات (data retrieval) می باشد. مهم ترین تفاوت یک indexing engine با یک DBMS، در نحوه parse کردن دیتا ها و نوع ساختمان داده مورد استفاده برای ذخیره سازی و نگهداری دیتا ها می باشد. برای اینکه بخواهید حضور یک کلمه را در تمام اسناد ذخیره شده برروی دیتابیس خود، چک کنید، نیاز دارید که تمام رکورد های دیتابیس خود را یک بار بررسی کنید. حتی با این فرض که پیچیدگی زمانی دسترسی به یک رکورد در DBMS شما o(1) باشد، باز هم در مواردی که دیتابیس شما شامل چندین میلیون رکورد باشد، عمل بررسی تک تک آنها، زمان قابل توجهی طول خواهد کشید. این در صورتی است که اگر همین میزان داده را در یک indexing engine، ایندکس کنید، بررسی حضور یک کلمه در تمامی این چند میلیون رکورد، در حدود چند میلی ثانیه زمان میبرد. برای اینکه بیشتر با مفهوم ایندکسینگ آشنا بشیم، بهتر است ابتدا با برخی الگوریتم ها و روش ها که در این موتور ها استفاده می شوند، آشنا شویم.
ابتدا اجازه بدهید که برای اسنادمان، یک ساختار تعریف کنیم. شاید بهتر باشد که یک نوع سند را، پیشفرض ادامه صحبت هایمان قرار دهیم. فرض کنیم اسنادی که میخواهیم روی آنها جستجو کنیم، از نوع محصولات فروشگاهی باشند. محصولات فروشگاهی هم، مثل اسناد دیگر، مشخصه های مختلفی دارند.
چندتا از این مشخصه ها:
پس 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 خواهیم دید.
فرض کنید که کاربر، کوئری «گوشی آیفون ایکس» را جستجو کرده است. اسنادی که ما آنها را در سیستم خود، ایندکس کرده ایم هم، به شرح زیر می باشند:
میخواهیم بصورت فرضی، اعدادی را بعنوان وزن هر یک از کلمات موجود در این سند ها، به هریک نسبت دهیم. کلمه ای مثل کلمه «گوشی» با توجه به پرتکرار بودنش، باید نسبتا وزن کمی در حد ۲ داشته باشد. کلمه «آیفون» هم کلمه پرتکراری محسوب می شود، اما نسبت به کلمه «گوشی» قطعا وزن بیشتری خواهد داشت. پس وزن ۴ را نیز به کلمه «آیفون» نسبت می دهیم. در نهایت، کلمه «ایکس» را داریم. حقیقتا، نمی توانم تصمیم درستی درباره وزن این کلمه بگیرم، اما احتمالا، وزن این کلمه هم فقط کمی، کمتر از کلمه «آیفون» می باشد. پس وزن ۳.۵ را به کلمه «ایکس» نسبت می دهیم. دنباله این اعداد (وزن کلمات) در واقع، تشکیل برداری می دهند، که می توانیم جمله «گوشی آیفون ایکس» را به این بردار، در فضای برداری کلمات، نسبت دهیم. پس تا اینجای کار، با نحوه تبدیل کردن دنباله 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
