الگوریتم Z (جستجوی الگو با زمان خطی) – راهنمای کاربردی

در این مطلب، الگوریتم 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 فاقد معنا است، زیرا رشته کامل همیشه پیشوندی از خودش محسوب می‌شود. مثال‌های زیر در این راستا، جالب توجه هستند.

Index            0   1   2   3   4   5   6   7   8   9  10  11 
Text             a   a   b   c   a   a   b   x   a   a   a   z
Z values         X   1   0   0   3   1   0   0   2   2   1   0 

str  = "aaaaaa"
Z[]  = {x, 5, 4, 3, 2, 1}

str = "aabaacd"
Z[] = {x, 1, 0, 2, 1, 0, 0}

str = "abababab"
Z[] = {x, 0, 6, 0, 4, 0, 2, 0}

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

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

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

آرایه Z را برای رشته الحاق شده باید ساخت. در آرایه Z، اگر مقدار Z در هر نقطه‌ای مشابه با طول الگو باشد، الگو در آن نقطه نمایش داده می‌شود. مثال زیر در این راستا قابل توجه است.

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

یک راهکار ساده، اجرای دو حلقه تو در تو است، حلقه بیرونی به تک تک اندیس‌ها می‌رود؛ حلقه درونی، طول بلندترین پیشوندی را پیدا می‌کند که دارای یک ویژگی خاص باشد.

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

The idea is to maintain an interval [L, R] which is the interval with max R
such that [L,R] is prefix substring (substring which is also prefix). 

Steps for maintaining this interval are as follows – 

1) If i > R then there is no prefix substring that starts before i and 
   ends after i, so we reset L and R and compute new [L,R] by comparing 
   str[0..] to str[i..] and get Z[i] (= R-L+1).

2) If i <= R then let K = i-L, now Z[i] >= min(Z[K], R-i+1)  because 
   str[i..] matches with str[K..] for atleast R-i+1 characters (they are in
   [L,R] interval which we know is a prefix substring).     
   Now two sub cases arise – 
      a) If Z[K] < R-i+1 then there is no prefix substring starting at str[i] (otherwise Z[K] would be larger) so Z[i] = Z[K] and interval [L,R] remains same. b) If Z[K] >= R-i+1 then it is possible to extend the [L,R] interval
         thus we will set L as i and start matching from str[R]  onwards  and
         get new R then we will update interval [L,R] and calculate Z[i] (=R-L+1).

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

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

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

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

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

خروجی قطعه کدهای بالا، به صورت زیر است.

Pattern found at index 0
Pattern found at index 10

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

^^