آشنایی با مهم‌ترین الگوریتم‌های بازیابی اطلاعات

بخش اول: آشنایی با مهم‌ترین الگوریتم‌های بازیابی اطلاعات

الگوریتم جست‌وجوی اول سطح

در نظریه گراف، جست‌وجوی اول سطح (Breadth-first Search) یکی از الگوریتم‌های پیمایش گراف است. استراتژی جستجوی سطح اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی سطح به سطح گراف» است. الگوریتم از ریشه شروع می‌کند (در گراف‌ها یا درخت‌های بدون ریشه رأس دلخواهی به عنوان ریشه انتخاب می‌شود) و آن را در سطح یک قرار می‌دهد. سپس در هر مرحله همه همسایه‌های رئوس آخرین سطح دیده شده را که تا به حال دیده نشده‌اند بازدید می‌کند و آنها را در سطح بعدی می‌گذارد. این فرایند زمانی متوقف می‌شود که همه همسایه‌های رئوس آخرین سطح قبلاً دیده شده باشند. همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گراف‌اند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است که در عین حال در بین همه رئوس هدف با آن خصوصیات به ریشه نزدیک‌ترین باشد، جستجوی سطح اول به صورت غیرخلاق عمل می‌کند. بدین ترتیب که الگوریتم هر دفعه همه همسایه‌های یک رأس را بازدید کرده و سپس به سراغ رأس بعدی می‌رود و بنابراین گراف سطح به سطح پیمایش خواهد شد. این روند تا جایی ادامه می‌یابد که رأس هدف پیدا شود یا احتمالاً همه گراف پیمایش شود. براساس آنچه گفته شد پیاده‌سازی هوشمندانه الگوریتم آنقدر مؤثر نخواهد بود.

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

الگوریتم تطابق رشته با زمان خطی

الگوریتم تطابق رشته با زمان خطی توسط دانلد کنوت و وان پرت و همچنین جیمز ه. موریس به صورت مستقل پرداخته شد، اما این سه فرد با هم آن را منتشر کردند. به همین خاطر به الگوریتم KMP نیز مشهور است. این الگوریتم در میان رشته S وجود کلمه W را بررسی می‌کند، به‌طوری‌که وقتی یک عدم مطابقت اتفاق می‌افتد، خود کلمه اطلاعات کافی را در بردارد تا محلی را که مطابقت بعدی ممکن است از آنجا شروع شود، با آزمایش دوبارۀ حروف تطبیق داده شده قبلی تعیین کند.

الگوریتم تطابق رشته‌ها

الگوریتم‌های تطابق رشته ای، که گاهی الگوریتم‌های جسیتجوی رشته ای گقته می‌شوند، دسته مهمی از الگوریتم‌های رشته‌ای هستند که سعی می‌کنند محل رخداد یک یا چند رشته (الگو) در یک رشته بزرگتر (یا متن) را پیدا کنند. Σ را مجموعه الفبای محدودی فرض کنید.معمولا، هم الگو و هم متن مورد نظر، ترکیبی از عناصرΣ می‌باشند. Σ می‌تواند یک الفبای انسانی معمولی باشد (مثلا، حروف A تا Z در زبان انگلیسی). در کاربردهای دیگر ممکن است از الفبای دودویی ({(Σ = {0,1) یا الفبای DNA در بیوانفورماتیک استفاده شود.

به‌طور خاص، این که رشته چگونه رمز شده‌است می‌تواند روی الگوریتم ملموس تطابق، تأثیرگذار باشد. مخصوصاً اگر رمز نگاری طولی متغیر مورد استفاده قرار گیرد، به کندی می‌توان کاراکتر N ام را پیدا کرد. این می‌تواند به‌طور محسوسی الگوریتم‌های جستجوی پیشرفته تر را کند، کند. یک راه حل این است که به دنبال دنباله‌ای از واحدهای رمز بگردیم، اما این روش ممکن است باعث ایجاد مطابقت‌های اشتباه گردد. اگر رمز نگاری به گونه‌ای خاص طراحی شده باشد، از این مشکل جلوگیری می‌شود.

جست‌وجوی ناآگاهانه

یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیت مسئله کاری ندارد. از این رو می‌توانند به‌طور عمومی طراحی شوند و از همان طراحی برای محدوده عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتم‌هایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونه‌های کوچک) می‌باشد. از این رو برای بالا بردن سرعت پردازش غالباً از الگوریتم‌های آگاهانه استفاده می‌کنند.

جست‌وجوی فهرست

الگوریتم‌های جستجوی لیست شاید از ابتدایی‌ترین انواع الگوریتم‌های جستجو باشند. هدف آن پیدا کردن یک عنصر از مجموعه‌ای از کلید هاست (ممکن است شامل اطلاعات دیگری مرتبط با آن کلید نیز باشد). ساده‌ترین این الگوریتم‌ها، الگوریتم جستجوی ترتیبی است که هر عنصر از لیست را با عنصر مورد نظر مقایسه می‌کند. زمان اجرای این الگوریتم از (O(n است وقتی که n تعداد عناصر در لیست باشد. اما می‌توان از روش دیگری استفاده کرد که نیازی به جستجوی تمام لیست نباشد. جستجوی دودویی اندکی از جستجوی خطی است. زمان اجرای آن از(O(lgn است. این روش برای لیستی با تعداد داده زیاد بسیار کار آمد تر از روش الگوریتم جستجوی ترتیبی است. اما در این روش لیست باید قبل از جستجو مرتب شده باشد.جستجو با میان یابی برای داده‌های مرتب شده با تعداد زیاد و توزیع یکنواخت، مناسب تر از جستجوی دودویی است. زمان اجرای آن به‌طور متوسط ((O(lg(lgn است ولی بدترین زمان اجرای آن (O(n می‌باشد. الگوریتم graver الگوریتم پله‌ای است که برای لیست‌های مرتب نشده‌استفاده می‌شود. جدول درهم‌سازی نیز برای جستجوی لیست به کار می‌رود. به‌طور متوسط زمان اجرای ثابتی دارد. اما نیاز به فضای اضافه داشته و بدترین زمان اجرای آن از(O(n است.

جست‌وجوی درختی

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

جست‌وجوی گراف

بسیاری از مسائل در نظریه گراف می‌تواند با الگوریتم‌های پیمایش درخت حل شوند، مثل الگوریتم دایجسترا، الگوریتم کروسکال، الگوریتم نزدیک‌ترین همسایه و الگوریتم پریم. می‌توان این الگوریتم‌ها را توسعه یافته الگوریتم‌های جستجوی درختی دانست.

جست‌وجوی آگاهانه

در یک جستجوی آگاهانه، از نوع خاصی از مسائل به عنوان راهنما استفاده می‌شود. یک گونهٔ خوب یک جستجوی آگاهانه با کارایی قابل توجهی نسبت به جستجوی ناآگاهانه به وجود می‌آورد. الگوریتم‌های برجستهٔ کمی از جستجوی آگاهانهٔ یک لیست وجود دارد. یکی از این الگوریتم‌ها hash table با یک تابع hash که برمبنای نوع مسئله‌ای که دردست است می‌باشد. بیشتر الگوریتم‌های جستجوی آگاهانه، بسطی از درخت‌ها هستند. همانند الگوریتم‌های ناآگاهانه، این الگوریتم‌ها برای گراف‌ها نیز می‌توانند به کار روند.

جست‌وجوی خصمانه

در یک بازی مثل شطرنج، یک درخت بازی شامل تمام حرکات ممکن توسط هر دو بازیکن و نتایج حاصل از ترکیب این حرکات وجود دارد، و ما می‌توانیم این درخت را جستجو کرده و مؤثرترین استراتژی برای بازی را بیابیم. این چنین مسائلی دارای مشخصه منحصر به فردی هستند. برنامه‌های بازی‌های رایانه‌ای، و همچنین فرم‌های هوش مصنوعی مثل برنامه‌ریزی ماشین‌ها، اغلب از الگوریتم‌های جستجو مثل الگوریتم minimax (مینیمم مجموعه‌ای از ماکزیمم‌ها)، هرس کردن درخت جستجو و هرس کردن آلفا-بتا استفاده می‌کنند.

الگوریتم اف اسکن

FSCAN یک الگوریتم زمان‌بندی دیسک است که حرکت آرم و هد دیسک در سرویس دهی درخواست‌های خواندن و نوشتن را تعیین می‌کند. طی روبش تمام درخواست‌ها در صف اول داده‌ها ی اولیه هستند و تمام درخواست‌های جدید در صف داده‌های ثانویه قرار داده می‌شوند. بنابراین سرویس دهی به درخواست‌های جدید به تأخیر می‌افتد تا زمانی که تمام درخواست‌های قدیمی تحت پردازش قرار گیرد. هنگامی که روبش پایان می‌یابد آرم به تمام صف داده‌های اولیه برده می‌شود و دوباره سرتاسر آن شروع می‌شود.

الگوریتم F-SCAN مطابق N-Step-SCAN از چسبانکی آرم جلوگیری می‌کند در صورتی که در الگوریتم‌های دیگر مانند SSTF, SCAN و C-LOOK چنین امری اتفاق نمی‌افتد. چسبانکی آرم در الگوریتم‌های دیگر وقتی رخ می‌دهد که هجمه‌ای از درخواست‌ها برای مسیر مشترک موجب می‌شود تا آرم دیسک توقف پردازش در آن مسیر گردد، از این رو ترجیح داده می‌شود که هیچ جستجوئی برای درخواست‌های آن مسیری که در آن است مورد تأیید واقع نشود، از آن جا که F-SCAN درخواست‌ها را به دو صف داده‌ها جدا می‌کند، روبرو شدن با درخواست‌های جدید به صف داده‌های در حال انتظار برده می‌شود، آرم روبش خود را تا مسیر بیرونی ادامه می‌دهد و از این رو چسبانکی پیش روی الگوریتم نیست. یک معاوضه آشکار وجود دارد به طوری که درخواست‌ها در صف داده‌های در حال انتظار باید انتظار طولانی‌تر تا برای به اجرا درآوردن بکشند، اما در مبادله F-SCAN برای تمام درخواست‌های رضایت بخش تر است.

الگوریتم جست‌وجوی اول عمق

در نظریه گراف، جستجوی عمق اول (Depth-first Search، به‌اختصار DFS) یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار می‌رود. استراتژی جستجوی عمق اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی عمیق‌تر در گراف تا زمانی که امکان دارد» است. الگوریتم از ریشه شروع می‌کند (در گراف‌ها یا درخت‌های بدون ریشه راس دلخواهی به عنوان ریشه انتخاب می‌شود) و در هر مرحله همسایه‌های رأس جاری را از طریق یال‌های خروجی رأس جاری به ترتیب بررسی کرده و به محض روبه‌رو شدن با همسایه‌ای که قبلاً دیده نشده باشد، به صورت بازگشتی برای آن رأس به عنوان رأس جاری اجرا می‌شود. در صورتی که همه همسایه‌ها قبلاً دیده شده باشند، الگوریتم عقب‌گرد می‌کند و اجرای الگوریتم برای رأسی که از آن به رأس جاری رسیده‌ایم، ادامه می‌یابد. به عبارتی الگوریتم تا آنجا که ممکن است، به عمق بیشتر و بیشتر می‌رود و در مواجهه با بن‌بست عقب‌گرد می‌کند. این فرایند تا زمانی که همه رأس‌های قابل دستیابی از ریشه دیده شوند ادامه می‌یابد. از دیدگاه عملی، برای اجرای الگوریتم، از یک پشته استفاده می‌شود. بدین ترتیب که هر بار با ورود به یک رأس دیده نشده، آن رأس را در پشته قرار می‌دهیم و هنگام عقب‌گرد رأس را از پشته حذف می‌کنیم؛ بنابراین در تمام طول الگوریتم اولین عنصر پشته رأس در حال بررسی است. جزئیات پیاده‌سازی در ادامه خواهد آمد. وقتی در گراف‌های بزرگی جستجو می‌کنیم که امکان ذخیره کامل آن‌ها به علت محدودیت حافظه وجود ندارد، در صورتی که طول مسیر پیمایش شده توسط الگوریتم که از ریشه شروع شده، خیلی بزرگ شود، الگوریتم با مشکل مواجه خواهد شد. در واقع این راه‌حل ساده که «رئوسی را که تا به حال دیده‌ایم ذخیره کنیم» همیشه کار نمی‌کند. چرا که ممکن است حافظه کافی برای این کار نداشته باشیم. البته این مشکل با محدود کردن عمق جستجو در هر بار اجرای الگوریتم حل می‌شود که در نهایت به الگوریتم جستجوی عمق اول عمیق‌کننده تکراری خواهد انجامید.

الگوریتم جست‌وجوی دودویی

الگوریتم جستجوی دودویی (Binary Search)، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدوده جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد. جستجوی دودویی فقط در آرایه‌های مرتب استفاده می‌شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می‌شود اگر با این خانه برابر بود جستجو تمام می‌شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می‌شود (فرض کرده‌ایم آرایه به صورت صعودی مرتب شده‌است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه‌های آرایه ادامه می‌یابد. پیدا کردن اندیس یک عنصر خاص در یک لیست مرتب شده مفید است زیرا با استفاده از اندیس داده شده می‌توان به سایر اطلاعات مربوطه دست یافت.

الگوریتم جست‌وجوی رشته

الگوریتم‌های جستجوی رشته (تطبیق رشته‌ها) به رده‌ی مهمی از الگوریتم‌های موجود در رابطه با رشته‌ها اطلاق می‌شود. در این گونه از الگوریتم‌ها، مسئله‌ی اصلی پیدا کردن مکان‌های تکرار یک یا چند الگوی مورد جستجو (Pattern) در یک رشته‌ بزرگ‌ (Text) است. در هر حالت از محیط اجرای الگوریتم و شرایط مسئله، باید این شرایط را به خوبی بررسی کرد و بهترین الگوریتم را برای پیاده‌سازی و استفاده برگزید. برای گرفتن بهترین کارایی در هر یک از این شرایط، باید الگوریتم مشخصی را انتخاب کرد. همچنین در نوعی از این مسئله، رشته‌های Pattern به صورت یک عبارت منظم داده می‌شوند، و باید جایگاه تمام زیررشته‌هایی که با آن عبارت منظم مطابق هستند به عنوان خروجی برگردانده ‌شود.

الگوریتم دایجسترا

در نظریه گراف، الگوریتم دایجسترا (به انگلیسی: Dijkstra's algorithm) یکی از الگوریتم‌های پیمایش گراف است که مسئله کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همه رأس‌های گراف را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد. الگوریتم دایجسترا یکی از الگوریتم‌های مورد استفاده برای محاسبه کوتاه‌ترین مسیر تک منبع (single-source shortest path) است و مشابه الگوریتم پریم می‌باشد در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی‌کند و می‌بایست از الگوریتم‌های دیگر نظیر الگوریتم بلمن-فورد که پیچیدگی زمانی آن‌ها بیشتر است استفاده کنیم.

انباشتن سیلابی

انباشتن سیلابی (Flood fill) یک الگوریتم است که ناحیه متصل به یک رأس داده شده در یک آرایه چند بعدی را مشخص می‌کند. به‌طور مثال این الگوریتم در ابزار پر کردن ”سطل” در برنامه‌های نقاشی به منظور پر کردن ناحیه‌های متصل و هم‌رنگ با رنگی متفاوت با رنگ قبلی یا در بازی‌هایی مانند گو یا مین‌روب برای مشخص کردن تکه‌های پاک‌سازی شده به کار می‌رود. این الگوریتم اگر روی تصویری برای پر کردن ناحیه محدود و خاصی از آن اعمال شود، به عنوان انباشتن مرزی نیز شناخته می‌شود. الگوریتم انباشتن سیلابی سه پارامتر را به عنوان ورودی می‌پذیرد: راس آغازین، رنگ هدف و رنگ جایگزین. این الگوریتم به دنبال تمامی راس‌هایی در آرایه می‌گردد که به وسیله مسیر به رنگ هدف به گره آغازین متصلند، سپس آن‌ها را با رنگ جایگزین عوض می‌کند. راه‌های بسیار زیادی برای بنا کردن الگوریتم انباشتن سیلابی وجود دارد، اما همه آن‌ها از ساختمان داده پشته یا صف به صراحت یا به‌طور ضمنی استفاده می‌کنند.