بررسی :الگوریتم های جستجو در بانک اطلاعاتی

[siavosh1]

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

[Bracket]

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

[siavosh1]

فرض کنید یک بانک اطلاعاتی درست کردید که شامل اطلاعاتی در مورد نرم افزارهای موجود در فروشگاه اینترنتی یک شرکت هست . خوب کاربر میاد و نرم افزار مورد نظرش رو سرچ می کنه .. خوب حالا به عنوان مثال اگر از MySQL به عنوان بانک اطلاعاتی استفاده کرده باشید ، از طریق دستور select میتونید جداول بانک اطلاعاتی تون رو سرچ کنید و اگر فیلدی مطابق با گزینه سرچ شده پیدا شد ، نمایش داده بشه .
تا اینجا قضیه چیز مبهمی نداشت . اما مسئله اینجاست که دستور select یک نوع سرچ ابتدایی رو انجام میده و فقط در صورتی که عبارت تایپ شده توسط کاربر دقیقاً مثل اطلاعات فیلد باشه ، اون رو میتونه پیدا کنه .
به عنوان مثال کاربری به دنبال نرم افزار 3D studio max هست . این نرم افزار در جداول بانک اطلاعاتی فروشگاه ما هست و ما توسط دستور select می تونیم نتیجه مناسب رو نشون بدیم .
یک مشکل دیگه دستور سرچ اینه که کل جدول رو برای پیدا کردن فیلد مناسب سرچ میکنه که در واقع یک کار زاید و وقت گیر هست . البته تو MySQL با index کردن فیلدها تا حدودی این مشکل رو میشه برطرف کرد و دیگه کل جدول مورد وارسی قرار نمیگیره .
اما بحث سرچ کردن و نیاز به الگوریتم ها از اینجا به بعد شروع میشه . حالا فرض کنید کاربر دیگه میاد و عبارت 3D stodio max رو سرچ می کنه . دیگه دستور select نمی تونه نتیجه مناسب رو به کاربر نشون بده . با اینکه ما این نرم افزار رو موجود داریم ولی یک مشتری به خاطر عدم توانایی موتور سرچ می پره !!
همچنین ممکنه کاربر عبارت 3d studio یا 3d max رو به کار ببره . که باز هم نتیجه ای نخواهد گرفت . تازه اگر از سرور لینوکس استفاده کنید حتی اگر کاربر عبارت 3d studio max رو هم وارد کنه باز هم به نتیجه نمیرسه چون لینوکس به حروف کوچک و بزرگ حساسه (3D یا 3d )
در واقع الگوریتم سرچ راه حل ها یا کلک هایی هستند که قابلیت نمایش نتایج مشابه رو هم به موتور سرچ اضافه میکنند .
البته این مثال در مورد یک بانک اطلاعاتی کوچیک بود و در بانک های اطلاعاتی متوسط یا بزرگ این موضوع خیلی مهم تر و مشکل تر میشه . مثلا در یک موتور سرچ بزرگ با میلیاردها صفحه این موضوع بحث زندگی و مرگه چون باید موتور سرچ به قدری باهوش باشه که با دریافت چند کلمه از کاربر بتونه نزدیک ترین و بهترین نتایج رو نشون بده . برای درک اهمیت این موضوع کافیه همین رو بدونید که کمپانی گوگل فقط به خاطر استفاده از همین الگوریتم هاست که میلیاردها دلار درآمد سالانه داره و از پر سود ترین شرکت های آمریکا ست و سالانه افراد زیادی برای تولید الگوریتم های جدید و بهتر در گوگل کار میکنند و گوگل رو شاید بتونیم مترادف یا الگوریتم های سرچ بدونیم .

ولی بحث ما بیشتر مربوط به همین الگوریتم های نسبتاً ساده هست که قابل استفاده در بانک های اطلاعاتی کوچک و متوسط (مثل MySQL) باشه.

[siavosh1]

خوب برای مثالی که زدم یک الگوریتم طراحی میکنیم .

ابتدا طرح کلی مسئله --> تطبیق اطلاعات ورودی کاربر با عبارت موجود در بانک اطلاعاتی یا شبیه ترین عبارات به آن

عبارت مو جود در بانک اطلاعاتی --> 3D studio max

عبارت ورودی توسط کاربر --> یکی از چند حالت زیر :

1 - 3D studio max
2 - 3D stodio max
3 - 3D max
4 - 3d studio max
و ...


راه حل -->

1 - خوب در مورد اول که مشکل خاصی نیست و در MySQL با دستور زیر می توان عبارت را پیدا کرد . ( فرض شد جدولی داریم که در آن یک ستون به نام software وجود دارد).
; select * from tablename where software =3D studio max

2 - در این مورد دیگه روش بالا کارایی نداره . خوب یک راه حل که من خودم پیشنهاد میکنم . میتونیم وقتی عبارت رو از کاربر میگیریم اونو در یک متغیر به نام A ذخیره کنیم . در php داریم :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

حالا میتونیم توسط تابع split ، عبارت ورودی رو تجزیه کنیم . به این ترتیب که عبارت ورودی به 3 کلمه 3D , stodio و max تجزیه میشه و درون آرایه ای به نام AS قرار میگیره :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

حالا برای راحتی کار مقدار هر عنصر آرایه رو توی یک متغیر جدید میریزیم :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

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

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

این قطعه کد برای هر دو کلمه دیگر نیز تکرار میشود .البته میتوان این قطعه کد را به صورت یک تابع نوشت تا در کدنویسی صرفه جویی کرد و یا ابتدا تقاضا ها را به بانک اطلاعاتی فرستاد و همه نتایج را در انتها نمایش داد که این برمیگرده به برنامه نویس و خوش سلیقگی
خوب درمورد کلمه اول مسلماً حداقل یک نتیجه مناسب پیدا خواهد شد و درمورد کلمه دوم نتیجه ای نخواهیم داشت و در مورد کلمه سوم هم نتیجه ای خواهیم داشت .
بدین ترتیب در صورت اشتباه تایپی نیز میتوانیم نزدیک ترین جواب ها را به مشتری بدهیم و این یعنی هوشمندی!!

3 - برای این حالت هم روش بالا کاربرد دارد و ما را به جواب میرساند . البته میتوانیم از تجزیه عبارت صرف نظر کرده و در فقط دستور sql را به شکل زیر تغییر دهیم :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

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

4 - در حالت چهار وقتی مشکل پیش میاد که سیستم عامل یا بانک اطلاعاتی به حروف کوچک و بزرگ حساس باشند مثل سیستم عامل لینوکس .
راه حل پیشنهادی من اینه که وقتی ورودی از کاربر دریافت میشه بعد از تجزیه کردن عبارت به کلمات تشکیل دهنده و قرار دادن در ارایه AS بیایم و هر عنصر آرایه رو در 2 حالت بررسی کنیم :
حالت اول : مقدار عنصر را به همان گونه که هست در بانک اطلاعاتی سرچ میکنیم .
حالت دوم : بعد از اعمال تابع strtoupper بر روی عنصر و تبدیل کردن کلیه حروف کلمه به حروف بزرگ ، متغیر حاصل رو در بانک اطلاعاتی سرچ میکنیم .

چون اینجا آرایه ای داریم که 3 عنصر دارد ( 3 کلمه تشکیل دهنده عبارت) و هر عنصر را در دو حالت بررسی کردیم ، در نهایت 6 پاسخ از بانک اطلاعاتی دریافت خواهیم کرد که یکی از آنها نتیجه درست هست .( کلمه 3d با تبدیل به حروف بزرگ به 3D تبدیل شده و طبق دستور select که در بالا گفته شد به نتیجه خواهیم رسید.)
البته در این مورد باز هم برنامه گفته شده در قسمت 2 کاملتر و بهتر هست .
----------------

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

[siavosh1]

کسی الگوریتم جدیدی ، پیشنهادی انتقادی نداره ؟؟ بیاید این جور تاپیک ها رو بیشتر کنیم فکر کنم به هممون کمک میتونه بکنه