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

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

توجه: در این مقاله رشته‌ها با استفاده از آرایه‌های مبتنی بر صفر نمایش داده می‌شوند؛ به گونه‌ای که حرف 'C' در $S=\{'A','B','C'\}$ به صورت $S[2]$ نشان داده می‌شود.

الگوریتم KMP

یک مثال از الگوریتم جست‌وجو

برای نشان دادن جزئیات این الگوریتم، یک اجرا (تقریبا ساختگی) از آن را بررسی می‌کنیم. در هر زمان دلخواهی، الگوریتم در یک حالت مشخص‌شده با دو عدد صحیح m و i قرار دارد. به طوری که هرکدام به ترتیب موقعیتی در S را مشخص می‌کنند که شروع یک تطابق ممکن برای W و اندیسی از W است که نشان می‌دهد کدام کاراکتر در حال حاضر تحت بررسی است. در ابتدای اجرا الگوریتم به این شکل است:

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

با مقایسه‌ی پی‌درپی کاراکترهای W با کاراکترهای "متناظر" از S ادامه می‌دهیم و اگر کاراکترها یکسان بودند به کاراکتر بعدی آن می‌رویم. در مرحله‌ی چهارم $S[3]$ یک فاصله و $W[3]$ کاراکتر 'D' است که این یک عدم تطابق است. به جای اینکه دوباره جست‌وجو را از $S[1]$ شروع کنیم، در نظر می‌گیریم که 'A' بین موقعیت‌های 0 و 3 فقط در اندیس 0 از S دیده شده است؛ از این رو با دانستن این مطلب و اینکه آن کاراکترها قبلا بررسی شده‌اند، می‌دانیم که اگر دوباره آنها بررسی کنیم، هیچ موقع یک تطابق دیگر را پیدا نخواهیم کرد. پس به کاراکتر بعدی می‌رویم و m را برابر 4 و i را برابر 0 در نظر می‌گیریم. (از آنجایی که m + i – T[i] = 0 + 3 – 0 = 3 و T[0] = -1 پس m برابر 4 خواهد بود.)

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

در اینجا تقریبا به یک تطابق دست پیدا می‌کنیم، اما در $(S[10])$ $W[6]$ اختلاف مشاهده می‌شود. با این حال در انتهای تطابق از "AB" گذر کردیم که می‌تواند شروع یک تطابق جدید باشد، پس باید این را در نظر بگیریم. همانطور که از قبل می‌دانیم، این کاراکترها با دو کاراکتر قبل از موقعیت فعلی تطابق داشتند، پس نیاز نیست که دوباره بررسی شوند؛ به راحتی m = 8 و i = 2 قرار داده و تطابق کاراکتر فعلی را ادامه می‌دهیم. پس به این شکل هم کاراکترهای تطابق داده‌شده‌ی قبلی از S و هم از W را حذف می‌کنیم.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

جست‌وجو بلافاصله متوقف می‌شود، هرچند از آنجایی که رشته دارای فاصله نیست، مانند قبل به اول W بازمی‌گردیم و جست‌وجو را از کاراکتر بعدی S آغاز می‌کنیم: m = 11 و i = 0.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

دوباره به یک تطابق برای "ABCDAB" دست پیدا کردیم، اما کاراکتر بعدی ('C') با کاراکتر آخر W یعنی 'D' مطابقت ندارد. مانند قبل m را برابر 15 و i را برابر 2 درنظر می‌گیریم و تطابق را از موقعیت فعلی ادامه می‌دهیم.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

در این مرحله موفق به یافتن تطابقی که شروعش از کاراکتر $S[15]$ است می‌شویم.

توضیحات و شبه‌برنامه برای الگوریتم جست‌وجو

مثال بالا همه‌ی اجزای الگوریتم را در بر دارد. فرض می‌کنیم یک جدول "تطابق جزیی" T (که در پایین توضیح داده شده) داریم که مشخص می‌کند از کجا باید به دنبال یافتن شروع یک تطابق جدید باشیم. درایه‌های جدول T نشان می‌دهند که اگر تطابقی از $S[m]$ شروع شود و هنگام مقایسه‌ی $S[m + i]$ با $W[i]$ شکست بخورد، مطابقت بعدی ممکن است از اندیس $m + i - T[i]$ رشته‌ی S آغاز شود. (که $T[i]$ مقدار "برگشتن"ای است که ما نیاز داریم بعد از یک عدم مطابقت انجام دهیم.) اینجا دو مفهوم داریم: اول، $T[0] = -1$ که نشان می‌دهد اگر در $W[0]$ عدم مطابقت داریم، نمی‌توانیم برگردیم و باید کاراکتر بعدی را بررسی نماییم. دوم، با وجود اینکه مطابقت احتمالی از اندیس $m + i - T[i]$ آغاز می‌شود، مانند مثال بالا، نیاز نیست که هیچ‌کدام از $T[i]$ کاراکتر بعد از آن را بررسی کنیم، پس جست‌وجو را از $W[T[i]]$ ادامه می‌دهیم. شبه‌برنامهی ساده‌ی زیر الگوریتم جست‌وجوی KMP را نشان می‌دهد:

algorithm kmp_search:
    input:
        an array of characters, S (the text to be searched)
        an array of characters, W (the word sought)
    output:
        an integer (the zero-based position in S at which W is found)

    define variables:
        an integer, m ← 0 (the beginning of the current match in S)
        an integer, i ← 0 (the position of the current character in W)
        an array of integers, T (the table, computed elsewhere)

    while m+i is less than the length of S, do:
        if W[i] = S[m + i],
            if i equals the (length of W)-1,
                return m
            let i ← i + 1
        otherwise,
            let m ← m + i - T[i],
            if T[i] is greater than -1,
                let i ← T[i]
            else
                let i ← 0
            
    (if we reach here, we have searched all of S unsuccessfully)
    return the length of S

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

با فرض داشتن جدول T، الگوریتم KMP دارای پیجیدگی $O(k)$ است که k طول رشته‌ی S و O نماد O بزرگ می‌باشد. به جز مخارج کلی وارد شده هنگام وارد شدن به تابع و خارج شدن از آن، همه‌ی محاسبات در حلقه‌ی while انجام می‌گیرد که در اینجا کرانی از تعداد تکرارهای این حلقه را محاسبه خواهیم کرد. برای انجام این کار باید اول یک مشاهده‌ی کلیدی روی ماهیت T داشته باشیم. این جدول برای این ساخته شده که نشان دهد اگر تطابقی از $S[m]$ شروع شود و هنگام مقایسه‌ی $S[m + i]$ با $W[i]$ شکست بخورد، مطابقت بعدی ممکن است از $S[m + (i - T[i])]$ آغاز شود. به طور خاص، تطابق احتمالی بعدی باید در اندیسی بالاتر از m رخ دهد، پس $T[i] <i$.

با استفاده از این واقعیت، نشان می‌دهیم که حلقه می‌تواند حداکثر 2k بار اجرا شود. در هر بار تکرار، یکی از دو شاخه‌ی داخل حلقه اجرا خواهد شد. شاخه‌ی اول i را مداوم افزایش داده و مقدار m را تغییر نمی‌دهد تا اندیس m + i کاراکتر دقیق فعلی از S افزایش یابد. شاخه‌ی دوم $i - T[i]$ را به m اضافه می‌کند و همانطور که دیده می‌شود، این همواره یک عدد مثبت می‌باشد. در نتیجه محل m از شروع تطابق احتمالی فعلی افزایش می‌یابد. حال اگر m + i = k باشد، حلقه تمام می‌شود، پس هر شاخه از حلقه می‌تواند حداکثر k بار اجرا شود. از آنجایی که هر شاخه به ترتیب m یا m + i را افزایش می‌دهند و m ≤ m + i، اگر m = k باشد، پس قطعا m + i ≥ k. در نتیجه چون حداکثر افزایش را دارد، باید قبلا شرط m + i = k برقرار شده باشد، پس هر کدام از راه‌ها می‌تواند انجام شده باشد.

در نتیجه حلقه حداکثر 2k بار اجرا می‌شود که نشان می‌دهد پیچیدگی زمانی الگوریتم $O(k)$ است.

جدول "تطابق جزیی" ("عمل شکست")

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

می‌خواهیم بتوانیم برای هر موقعیت در W، طول بلندترین قطعه‌ی ابتدایی ممکن از W را پیدا کنیم که از آن موقعیت آغاز شده اما آن را شامل نمی‌شود، به جای اینکه قطعه‌ی کاملی را در نظر بگیریم که از $W[0]$ آغاز شده و عدم مطابقت داشته است. از این رو $T[i]$ دقیقا طول بلندترین قطعه‌ی ابتدایی ممکن و مناسب از W است که همچنین یک قطعه از زیررشته‌ای است که پایانش در $W[i - 1]$ می‌باشد. قرارداد می‌کنیم که رشته‌ی خالی طول 0 را دارد. از آنجایی که یک عدم تطابق از ابتدای طرح یک حالت خاص است (هیچ امکانی برای بازگشت نیست)، $T[0] = -1$ در نظر می‌گیریم، همان‌طور که در بالا توضیح داده شد.

یک مثال از الگوریتم ساختن جدول

ابتدا مثال "W = "ABCDABD را بررسی می‌کنیم. خواهیم دید که همان روال الگوریتم جست‌وجوی اصلی را پیش می‌گیرد و به همان دلایل کارا است. در نظر می‌گیریم: $T[0] = -1$. برای یافتن $T[1]$، باید یک پسوند مناسب از "A" کشف کنیم که یک پیشوند از W هم هست. اما هیچ پسوند مناسبی از "A" نداریم پس $T[1] = 0$ و به همین شکل $T[2] = 0$.

با $T[3]$ ادامه می‌دهیم. توجه می‌کنیم که یک میان‌بر برای بررسی کردن همه‌ی پسوندها وجود دارد: فرض می‌کنیم یک پسوند مناسب یافته‌ایم که پیشوند مناسب نیز هست و در $W[2]$ با طول 2 تمام می‌شود (تا حداکثر ممکن)؛ سپس اولین کاراکتر یک پیشوند مناسب از پیشوند مناسب W است، از این رو خودش یک پیشوند مناسب است و در $W[1]$ تمام می‌شود که قبلا تعیین شده که نمی‌تواند در حالت $T[2]$ اتفاق بیفتد. از این رو در هر مرحله، راه میان‌بر آن است که تنها در صورتی نیاز به بررسی پسوند به اندازه‌ی داده‌شده‌ی m + 1 داریم که یک پسوند معتبر از اندازه‌ی m در مرحله‌ی قبل یافت شده باشد. (به طور مثال $T[x] = m$)

در نتیجه نیاز نیست درگیر یافتن زیررشته‌هایی به طول 2 شویم و مانند حالت قبل تنها یکی با طول 1 شکست می‌خورد، پس: $T[3] = 0$.

به $W[4]$ یعنی 'A' می‌رویم. همان منطق نشان می‌دهد که بلندترین زیررشته‌ای که ما نیاز به بررسی آن داریم دارای طول 1 است، و با اینکه در این حالت 'A' کار می‌کند، به خاطر بیاورید که ما به دنبال قطعه‌هایی هستیم که قبل از کاراکتر فعلی تمام می‌شوند. از این رو $T[4] = 0$.

حال کاراکتر بعدی یعنی $W[4]$ را که همان 'B' است بررسی می‌کنیم. منطق زیر را پیش می‌گیریم:

اگر یک زیررشته را که از قبل از کاراکتر $W[4]$ آغاز می‌شود و تا $W[5]$ ادامه دارد بخواهیم پیدا کنیم، آنگاه به طور خاص خودش یک قطعه‌ی ابتدایی مناسب خواهد داشت که در $W[4]$ تمام و قبل از آن شروع می‌شود، که با این واقعیت در تضاد است که ما قبلا فهمیده‌ایم 'A' خودش جلوترین وقوع از یک قطعه‌ی مناسب است که در $W[4]$ تمام می‌شود. پس نباید قبل از $W[4]$ را جست‌وجو کنیم تا یک رشته‌ی پایانی برای $W[5]$ پیدا کنیم. در نتیجه $T[5] = 1$.

در نهایت، خواهیم دید که کاراکتر بعدی در قطعه‌ی موردنظر که از $W[4] = 'A'$ آغاز می‌شود، 'B' خواهد بود، که در واقع همان $W[5]$ است. به علاوه همین استدلال مانند بالا نشان می‌دهد که نیازی نیست قبل از $W[4]$ را بررسی کنیم تا یک قطعه برای $W[6]$ پیدا کنیم، پس $T[6] = 2$.

پس به این ترتیب جدول زیر را پر می‌کنیم:

i	0	1	2	3	4	5	6
W[i]	A	B	C	D	A	B	D
T[i]	-1	0	0	0	0	1	2

بقیه‌ی مثال‌ها جذابتر و پیچیده‌تر هستند:

i	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3
W[i]	P	A	R	T	I	C	I	P	A	T	E		I	N		P	A	R	A	C	H	U	T	E
T[i]	-1	0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	1	2	3	0	0	0	0	0

توضیحات و شبه‌برنامه برای الگوریتم ساختن جدول

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

algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (the current position we are computing in T)
        an integer, cnd ← 0 (the zero-based index in W of the next
character of the current candidate substring)

    (the first few values are fixed but different from what the algorithm
might suggest)
    let T[0] ← -1, T[1] ← 0

    while pos is less than the length of W, do:
        (first case: the substring continues)
        if W[pos - 1] = W[cnd],
          let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (second case: it doesn't, but we can fall back)
        otherwise, if cnd> 0, let cnd ← T[cnd]

        (third case: we have run out of candidates.  Note cnd = 0)
        otherwise, let T[pos] ← 0, pos ← pos + 1

کارایی الگوریتم ساختن جدول

پیچیدگی الگوریتم جدول از $O(n)$ است که n طول رشته‌ی W می‌باشد. به جز مقداردهی اولیه‌ی انجام‌شده، همه‌ی کارها در یک حلقه‌ی while انجام شده‌است. کافیست نشان دهیم این حلقه در زمان $O(n)$ اجرا می‌شود که با بررسی مقادیر pos و pos - cnd به طور هم‌زمان قابل اثبات است. در اولین شاخه، هم pos و هم cnd به طور هم‌زمان در حال افزایشند، پس pos - cnd محفوظ است. اما به طور طبیعی pos در حال افزایش است. در شاخه‌ی دوم، cnd با $T[cnd]$ جایگزین می‌شود. در شاخه‌ی سوم، pos در حال افزایش و cnd بدون تغییر است، پس pos و pos - cnd هر دو افزایش می‌یابند. از آنجایی که pos ≤ pos - cnd، در هر مرحله یا pos و یا یک کران پایین از pos افزایش می‌یابد؛ در نتیجه چون الگوریتم زمانی که pos = n باشد، به پایان می‌رسد، باید حداکثر بعد از 2n بار تکرار حلقه کار تمام شود. (چون pos - cnd از 1 آغاز می‌شوند.) پس پیچیدگی الگوریتم جدول از $O(n)$ می‌باشد.

کارایی الگوریتم KMP

از آنجایی که دو قسمت الگوریتم به ترتیب دارای پیچیدگی $O(k)$ و $O(n)$ هستند، در کل پیچیدگی الگوریتم از $O(n + k)$ می‌باشد.

بدون توجه به تعداد تکرار یک طرح در W یا S، این پیچیدگی‌ها همواره یکسان هستند.

منابع برای مطالعه‌ی بیشتر

• الگوریتم جست‌وجوی رشته‌ی Boyer-Moore
• الگوریتم جست‌وجوی رشته‌ی رابین-کارپ

منابع

• Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323–350. DOI:10.1137/0206024. http://citeseer.ist.psu.edu/context/23820/0. 
• توماس اچ کورمن; Charles E. Leiserson, Ronald L. Rivest, کلیفورد استین (2001). "Section 32.4: The Knuth-Morris-Pratt algorithm". مقدمه‌ای بر الگوریتم‌ها (Second ed.). MIT Press and McGraw-Hill. pp. 923–931. ISBN 978-0-262-03293-3. 

پیوند به بیرون

• String Searching Applet animation
• An explanation of the algorithm and sample C++ code by David Eppstein
• Knuth-Morris-Pratt algorithm description and C code by Christian Charras and Thierry Lecroq
• Explanation of the algorithm from scratch by FH Flensburg.
• Breaking down steps of running KMP by Chu-Cheng Hsieh.
• ویدیو در یوتیوبNPTELHRD YouTube lecture video