در این مطلب، الگوریتم Z یا Z Algorithm که یک «الگوریتم جستجوی الگو» (Pattern Searching Algorithm) با زمان خطی است مورد بررسی قرار می‌گیرد و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) انجام می‌شود. الگوریتم Z، همه وقوع‌های یک الگو در متن را در یک زمان خطی پیدا می‌کند. اگر طول متن n و طول الگو m باشد، کل زمان گرفته شده O(m + n)‎ است و در واقع، پیچیدگی زمانی و فضایی، خطی محسوب می‌شود. اکنون، می‌توان مشاهده کرد که هم پیچیدگی زمانی و هم پیچیدگی فضایی مشابه الگوریتم KMP است؛ اما درک الگوریتم KMP ساده‌تر است. در این الگوریتم، یک آرایه Z ساخته می‌شود.

آرایه Z در الگوریتم Z

برای رشته str[0..n-1]‎، آرایه Z دارای طولی مشابه با رشته است. عنصر Z[i]‎ از آرایه Z، طول بلندترین زیر رشته را با شروع از str[i]‎ ذخیره می‌کند که خود پیشوندی از str[0..n-1]‎ است. اولین ورودی آرایه Z فاقد معنا است، زیرا رشته کامل همیشه پیشوندی از خودش محسوب می‌شود. مثال‌های زیر در این راستا، جالب توجه هستند.

آرایه Z چطور به جستجوی الگو در زمان خطی کمک می‌کند؟

ایده اصلی این روش آن است که با تمرکز روی الگو و متن، رشته «P$T» را ساخت که در آن، P الگو و $ یک کاراکتر ویژه محسوب می‌شود که نباید در الگو و متن ظاهر شود و T خود متن است. آرایه Z را برای رشته الحاق شده باید ساخت. در آرایه Z، اگر مقدار Z در هر نقطه‌ای مشابه با طول الگو باشد، الگو در آن نقطه نمایش داده می‌شود. مثال زیر در این راستا قابل توجه است.

روش ساخت آرایه Z

یک راهکار ساده، اجرای دو حلقه تو در تو است، حلقه بیرونی به تک تک اندیس‌ها می‌رود؛ حلقه درونی، طول بلندترین پیشوندی را پیدا می‌کند که دارای یک ویژگی خاص باشد. این ویژگی در واقع مطابقت داشتن با زیر رشته‌ای است که از اندیس کنونی آغاز می‌شود. پیچیدگی زمانی این راهکار، از درجه O(n2)‎ است. می‌توان آرایه Z را در زمان خطی ساخت.

این الگوریتم، در زمان خطی اجرا می‌شود. زیرا، هرگز کاراکترهایی کمتر از R مقایسه نمی‌شوند و با تطبیق دادن، R یک واحد افزایش پیدا می‌کند؛ بنابراین، حداکثر T مقایسه وجود دارد که پیچیدگی خطی کلی را می‌سازد. در ادامه، پیاده‌سازی الگوریتم Z برای جستجوی الگو، ارائه شده است.

پیاده‌سازی الگوریتم Z در ++C

پیاده‌سازی الگوریتم Z در جاوا

پیاده‌سازی الگوریتم Z در پایتون ۳

پیاده‌سازی الگوریتم Z در #C

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

^^

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

بر اساس رای 1 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *