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

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

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

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

با مقایسۀ پی‌درپی کاراکترهای W با کاراکترهای "متناظر" از S ادامه می‌دهیم و اگر کاراکترها یکسان بودند به کاراکتر بعدی آن می‌رویم. در مرحلۀ چهارم ${\displaystyle S[3]}$

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

در اینجا تقریباً به یک تطابق دست پیدا می‌کنیم، اما در ${\displaystyle (S[10])}$

             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

در این مرحله موفق به یافتن تطابقی که شروعش از کاراکتر ${\displaystyle S[15]}$

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

مثال بالا همۀ اجزای الگوریتم را در بر دارد. فرض می‌کنیم یک جدول "تطابق جزئی" T (که در پایین توضیح داده شده) داریم که مشخص می‌کند از کجا باید به دنبال یافتن شروع یک تطابق جدید باشیم. درایه‌های جدول T نشان می‌دهند که اگر تطابقی از ${\displaystyle S[m]}$

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 دارای پیجیدگی ${\displaystyle O(k)}$

با استفاده از این واقعیت، نشان می‌دهیم که حلقه می‌تواند حداکثر 2k بار اجرا شود. در هر بار تکرار، یکی از دو شاخۀ داخل حلقه اجرا خواهد شد. شاخۀ اول i را مداوم افزایش داده و مقدار m را تغییر نمی‌دهد تا اندیس m + i کاراکتر دقیق فعلی از S افزایش یابد. شاخۀ دوم ${\displaystyle i-T[i]}$

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

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

می‌خواهیم بتوانیم برای هر موقعیت در W، طول بلندترین قطعۀ ابتدایی ممکن از W را پیدا کنیم که از آن موقعیت آغاز شده اما آن را شامل نمی‌شود، به جای اینکه قطعۀ کاملی را در نظر بگیریم که از ${\displaystyle W[0]}$

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

ابتدا مثال "W = "ABCDABD را بررسی می‌کنیم. خواهیم دید که همان روال الگوریتم جستجوی اصلی را پیش می‌گیرد و به همان دلایل کارا است. در نظر می‌گیریم: ${\displaystyle T[0]=-1}$

با ${\displaystyle T[3]}$

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

به ${\displaystyle W[4]}$

حال کاراکتر بعدی یعنی ${\displaystyle W[4]}$

اگر یک زیررشته را که از قبل از کاراکتر ${\displaystyle W[4]}$

در نهایت، خواهیم دید که کاراکتر بعدی در قطعۀ موردنظر که از ${\displaystyle W[4]{=}^{\prime }{A}^{\prime }}$

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

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

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

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

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

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

پیچیدگی الگوریتم جدول از ${\displaystyle O(n)}$

از آنجایی که دو قسمت الگوریتم به ترتیب دارای پیچیدگی ${\displaystyle O(k)}$

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

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