موضوع مقاله: الگوریتم تطابق رشته با زمان خطی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم تطابق رشته با زمان خطی | مقدمه: این الگوریتم در میان رشته S وجود کلمه W را بررسی می‌کند، به‌طوری‌که وقتی یک عدم مطابقت اتفاق می‌افتد، خود کلمه اطلاعات کافی را در بردارد تا محلی را که مطابقت بعدی ممکن است از آنجا شروع شود، با آزمایش دوبارۀ حروف تطبیق داده شده قبلی تعیین کند. | ## بخش 1: الگوریتم تطابق رشته با زمان خطی | توجه: در این مقاله رشته‌ها با استفاده از آرایه‌های مبتنی بر صفر نمایش داده می‌شوند؛ به گونه‌ای که حرف 'C' در به صورت نشان داده می‌شود. الگوریتم KMP یک مثال از الگوریتم جستجو برای نشان دادن جزئیات این الگوریتم، یک اجرا (تقریباً ساختگی) از آن را بررسی می‌کنیم. در هر زمان دلخواهی، الگوریتم در یک حالت مشخص‌شده با دو عدد صحیح m و i قرار دارد. به‌طوری‌که هرکدام به ترتیب موقعیتی در S را مشخص می‌کنند که شروع یک تطابق ممکن برای W و اندیسی از W است که نشان می‌دهد کدام کاراکتر در حال حاضر تحت بررسی است. به جای اینکه دوباره جستجو را از شروع کنیم، در نظر می‌گیریم که 'A' بین موقعیت‌های 0 و 3 فقط در اندیس 0 از S دیده شده‌است؛ از این رو با دانستن این مطلب و اینکه آن کاراکترها قبلاً بررسی شده‌اند، می‌دانیم که اگر دوباره آن‌ها بررسی کنیم، هیچ موقع یک تطابق دیگر را پیدا نخواهیم کرد. با این حال در انتهای تطابق از "AB" گذر کردیم که می‌تواند شروع یک تطابق جدید باشد، پس باید این را در نظر بگیریم. همانطور که از قبل می‌دانیم، این کاراکترها با دو کاراکتر قبل از موقعیت فعلی تطابق داشتند، پس نیاز نیست که دوباره بررسی شوند؛ به راحتی m = 8 و i = 2 قرار داده و تطابق کاراکتر فعلی را ادامه می‌دهیم. مانند قبل m را برابر 15 و i را برابر 2 در نظر می‌گیریم و تطابق را از موقعیت فعلی ادامه می‌دهیم. توضیحات و شبه‌برنامه برای الگوریتم جستجو مثال بالا همۀ اجزای الگوریتم را در بر دارد. فرض می‌کنیم یک جدول "تطابق جزئی" T (که در پایین توضیح داده شده) داریم که مشخص می‌کند از کجا باید به دنبال یافتن شروع یک تطابق جدید باشیم. درایه‌های جدول T نشان می‌دهند که اگر تطابقی از شروع شود و هنگام مقایسۀ با شکست بخورد، مطابقت بعدی ممکن است از اندیس رشتۀ S آغاز شود. (که مقدار "برگشتن"ای است که ما نیاز داریم بعد از یک عدم مطابقت انجام دهیم.) اینجا دو مفهوم داریم: اول، که نشان می‌دهد اگر در عدم مطابقت داریم، نمی‌توانیم برگردیم و باید کاراکتر بعدی را بررسی نماییم. دوم، با وجود اینکه مطابقت احتمالی از اندیس آغاز می‌شود، مانند مثال بالا، نیاز نیست که هیچ‌کدام از کاراکتر بعد از آن را بررسی کنیم، پس جستجو را از ادامه می‌دهیم. | ## بخش 2: الگوریتم تطابق رشته با زمان خطی | به جز مخارج کلی وارد شده هنگام وارد شدن به تابع و خارج شدن از آن، همۀ محاسبات در حلقۀ while انجام می‌گیرد که در اینجا کرانی از تعداد تکرارهای این حلقه را محاسبه خواهیم کرد. این جدول برای این ساخته شده که نشان دهد اگر تطابقی از شروع شود و هنگام مقایسۀ با شکست بخورد، مطابقت بعدی ممکن است از آغاز شود. شاخۀ اول i را مداوم افزایش داده و مقدار m را تغییر نمی‌دهد تا اندیس m + i کاراکتر دقیق فعلی از S افزایش یابد. شاخۀ دوم را به m اضافه می‌کند و همانطور که دیده می‌شود، این همواره یک عدد مثبت می‌باشد. حال اگر m + i = k باشد، حلقه تمام می‌شود، پس هر شاخه از حلقه می‌تواند حداکثر k بار اجرا شود. در نتیجه چون حداکثر افزایش را دارد، باید قبلاً شرط m + i = k برقرار شده باشد، پس هر کدام از راه‌ها می‌تواند انجام شده باشد. در نتیجه حلقه حداکثر 2k بار اجرا می‌شود که نشان می‌دهد پیچیدگی زمانی الگوریتم است. جدول "تطابق جزئی" ("عمل شکست") هدف از ساختن این جدول آن است که الگوریتم هیچ کاراکتری از S را بیش از یک بار مطابقت ندهد. یک مشاهدۀ کلیدی دربارۀ ماهیت یک جستجوی خطی که اجازه می‌دهد این کار انجام شود، آن است که با بررسی کردن قطعه‌ای از رشتۀ اصلی در مقابل یک قطعۀ ابتدایی از طرح اصلی، خواهیم دانست که دقیقاً از چه اندیس‌هایی یک مطابقت احتمالی جدید شروع خواهد شد. در واقع یک جستجو از قبل روی طرح انجام خواهیم داد و یک لیست از همۀ موقعیت‌های احتمالی ارائه می‌کنیم. به‌طوری‌که از حداکثر تعداد کاراکتر گذر کند، در حالی که هیچ تطابق احتمالی را از دست ندهد. می‌خواهیم بتوانیم برای هر موقعیت در W، طول بلندترین قطعۀ ابتدایی ممکن از W را پیدا کنیم که از آن موقعیت آغاز شده اما آن را شامل نمی‌شود، به جای اینکه قطعۀ کاملی را در نظر بگیریم که از آغاز شده و عدم مطابقت داشته‌است. از این رو دقیقاً طول بلندترین قطعۀ ابتدایی ممکن و مناسب از W است که همچنین یک قطعه از زیررشته‌ای است که پایانش در می‌باشد. | ## بخش 3: الگوریتم تطابق رشته با زمان خطی | از آنجایی که یک عدم تطابق از ابتدای طرح یک حالت خاص است (هیچ امکانی برای بازگشت نیست)، در نظر می‌گیریم، همان‌طور که در بالا توضیح داده شد. خواهیم دید که همان روال الگوریتم جستجوی اصلی را پیش می‌گیرد و به همان دلایل کارا است. توجه می‌کنیم که یک میان‌بر برای بررسی کردن همه‌ی پسوندها وجود دارد: فرض می‌کنیم یک پسوند مناسب یافته‌ایم که پیشوند مناسب نیز هست و در با طول 2 تمام می‌شود (تا حداکثر ممکن)؛ سپس اولین کاراکتر یک پیشوند مناسب از پیشوند مناسب W است، از این رو خودش یک پیشوند مناسب است و در تمام می‌شود که قبلاً تعیین شده که نمی‌تواند در حالت اتفاق بیفتد. از این رو در هر مرحله، راه میان‌بر آن است که تنها در صورتی نیاز به بررسی پسوند به اندازۀ داده‌شدۀ m + 1 داریم که یک پسوند معتبر از اندازۀ m در مرحلۀ قبل یافت شده باشد. (به‌طور مثال ) در نتیجه نیاز نیست درگیر یافتن زیررشته‌هایی به طول 2 شویم و مانند حالت قبل تنها یکی با طول 1 شکست می‌خورد، پس: . همان منطق نشان می‌دهد که بلندترین زیررشته‌ای که ما نیاز به بررسی آن داریم دارای طول 1 است، و با اینکه در این حالت 'A' کار می‌کند، به خاطر بیاورید که ما به دنبال قطعه‌هایی هستیم که قبل از کاراکتر فعلی تمام می‌شوند. منطق زیر را پیش می‌گیریم: اگر یک زیررشته را که از قبل از کاراکتر آغاز می‌شود و تا ادامه دارد بخواهیم پیدا کنیم، آنگاه به‌طور خاص خودش یک قطعۀ ابتدایی مناسب خواهد داشت که در تمام و قبل از آن شروع می‌شود، که با این واقعیت در تضاد است که ما قبلاً فهمیده‌ایم 'A' خودش جلوترین وقوع از یک قطعۀ مناسب است که در تمام می‌شود. در نهایت، خواهیم دید که کاراکتر بعدی در قطعۀ موردنظر که از آغاز می‌شود، 'B' خواهد بود، که در واقع همان است. به علاوه همین استدلال مانند بالا نشان می‌دهد که نیازی نیست قبل از را بررسی کنیم تا یک قطعه برای پیدا کنیم، پس . قاعدۀ کلی برای جستجوی سراسری آن است که: بیشتر کارها قبلاً در هنگام یافتن موقعیت فعلی انجام شده‌است، پس اعمال کمی باید هنگام خروج از آن انجام شود. تنها پیچیدگی جزئی آن است که در ابتدای کار این منطق به اشتباه، زیررشته‌های نامناسبی از رشته می‌دهد. | ## جمع‌بندی | کارایی الگوریتم KMP از آنجایی که دو قسمت الگوریتم به ترتیب دارای پیچیدگی و هستند، در کل پیچیدگی الگوریتم از می‌باشد.