Full-Text Search

مقدمه

احتمالا برایتان پیش آمده است که بخواهید بین تعداد زیادی محتوای متنی، یک عبارت یا یک واژه خاص را پیدا کنید. یا به طور دقیق‌تر، همه فایل‌هایی که شامل آن عبارت می‌شوند را بیابید. به این نوع جست‌وجو، full-text search یا همان جستجوی متنی گفته می‌شود. اگر کمی دقت کنیم، هر بار که وارد گوگل می‌شویم و عبارتی را جست‌وجو می‌کنیم، در واقع داریم در بین تمام وبسایت‌های موجود، یک جست‌وجوی متنی انجام می‌دهیم و انتظار داریم، سایت‌هایی که شامل عبارت مورد نظر ما هستند به ما برگردانده شود.

• آیا تا به حال فکر کرده‌اید که گوگل چطور این کار را انجام می‌دهد؟
• یا به طور دقیق‌تر، چطور تا این حد سریع، این کار را انجام می‌دهد؟

در این فاز، نه تنها پاسخ این سوالات را میابیم، بلکه سرویس جست‌وجوی خودمان را نیز پیاده‌سازی می‌کنیم؛ با این تفاوت که به جای سایت‌ها به سراغ کتاب‌ها می‌رویم و این جست‌وجو را در بین انبوهی از کتاب‌ها انجام می‌دهیم.

آشنایی با مفاهیم اولیه جستجوی متنی

قبل از ادامه مطالعه مطالب، به دو سوال زیر فکر کنید و به آن‌ها پاسخ دهید:

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

• مرتبه زمانی روش پیشنهادی شما چقدر است؟! آیا می‌توان این کار را در مرتبه یک یا همان O1 انجام داد؟
• نکته: لطفا حتما پیش از ادامه مطالعه مطالب، روی سوالات بالا به خوبی فکر کنید و پاسخ خود را بنویسید.

یکی از داده‌ساختار‌های مورد استفاده به این منظور، Inverted Index می‌باشد. برای آشنایی با این داده ساختار Inverted Index - GeeksforGeeks را مطالعه کنید؛  سپس برای فهم بهتر ویدئوی The Inverted Index را مشاهده نمایید.

موتور جستجو

با توجه به دانشی که درباره جست‌وجوی متنی و داده‌ساختار inverted index بدست آوردیم، می‌خواهیم یک موتور جست‌وجو برای کتاب‌ها بسازیم تا با گرفتن تعدادی سند متنی (شامل خلاصه کتاب‌ها)، امکان جست‌وجوی سریع روی آن‌ها را فراهم کند.

پیش از ادامه اما لازم است با مفهوم برنامه‌نویسی دونفره یا Pair Programming آشنا شویم. از آنجا که باید تمام پروژه‌های فاز‌های آموزشی را به صورت pair و در قالب تیم‌های دو‌نفره انجام دهیم خوب است پیش از ادامه کار، درباره این سبک برنامه‌نویسی مطالعه کنیم.

تعریف پروژه

برنامه‌ای به زبان Java بنویسید که سند متنی (Document) را بخواند و از روی آن‌ها یک Inverted Index بسازد؛ سپس در Console از کاربر یک کلمه به عنوان ورودی بگیرد و نام یا شماره Documentهایی که شامل آن کلمه هستند را چاپ کند. 

note

در این پروژه، از خلاصه‌‌ کتاب‌های مهندسی نرم‌افزار به عنوان document استفاده خواهیم کرد. توجه کنید که می‌توانید از نام فایل‌ها به عنوان نام کتاب استفاده کنید.  (فایل‌های مربوط به این کتاب‌ها را می‌توانید از اینجا دانلود کنید)

info

در طراحی پروژه، به تفاوت دو واژه software و Software توجه کنید!به طور مثال، می‌توانید همه کلمات را uppercase کنیم تا برنامه، به بزرگی و کوچکی حروف حساس نباشد. به این کار به اصطلاح، normalization می‌گویند.

چه روش‌های دیگری برای بالا بردن دقت جستجو به ذهنتان می‌رسد؟ (پاسخ را در ایشو بنویسید)

در ادامه برنامه خود را تست کنید و درستی خروجی را بررسی کنید. در اینجا نمونه‌ای از ورودی و خروجی مورد انتظار برنامه آورده شده است:

مثال

  

ورودی

query

خروجی

Result1, Result2, Result3, ...

برای بررسی صحت خروجی خود می‌توانید وجود کوئری را در فایل‌های خروجی بررسی کنید.

موتور جستجوی پلاس!

هرچند موتور جستجوی ما کامل است، اما یک محدودیت بزرگ دارد! آن هم اینکه فقط یک عبارت ورودی می‌گیرد و نتایج شامل همان عبارت را برمی‌گرداند. سعی کنید موتور جستجویتان را به نحوی توسعه دهید که از سه نوع ورودی پشتیبانی کند:

1. کلماتی که حتما باید در نتیجه وجود داشته باشند. (این کلمات پیشوندی ندارند)
2. کلماتی که حداقل یکی از آن‌ها باید در نتیجه وجود داشته باشند. (این کلمات با پیشوند + مشخص می‌شوند)
3. کلماتی که نباید در نتیجه وجود داشته باشند. (این کلمات با پیشوند - مشخص می‌شوند)

ورودی نوع اول مانند And، نوع دوم مانند Or و نوع سوم مانند Not می‌باش د.

مثال

  

get help +illness +disease -cough

با استفاده از Query بالا می‌توانیم کتاب‌هایی را پیدا کنیم که حتماً شامل عبارات get و help و همچنین حداقل یکی از عبارات illness و disease باشند و شامل عبارت cough نباشند.

جمع‌بندی و مطالعه بیشتر

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

برای آشنایی بیشتر با نحوۀ کار موتور‌های جستجو دیدن ویدیو How Google searches one document among Billions of documents quickly توصیه می‌شود.