پرش به محتویات

یافتن تکرارها

یک رشته‌ی $s$ به طول $n$ داده شده است.

یک تکرار (repetition) به دو رخداد از یک رشته به صورت پشت سر هم گفته می‌شود. به عبارت دیگر، یک تکرار را می‌توان با یک جفت اندیس $i < j$ توصیف کرد، به طوری که زیررشته‌ی $s[i \dots j]$ از دو رشته‌ی یکسان که پشت سر هم نوشته شده‌اند، تشکیل شده باشد.

چالش، یافتن همه‌ی تکرارها در رشته‌ی داده‌شده‌ی $s$ است. یا یک وظیفه‌ی ساده‌تر: یافتن هر تکرار دلخواه یا یافتن طولانی‌ترین تکرار.

الگوریتم توصیف‌شده در اینجا در سال ۱۹۸۲ توسط Main و Lorentz منتشر شد.

مثال

تکرارها را در رشته‌ی مثال زیر در نظر بگیرید:

$$acababaee$$

این رشته شامل سه تکرار زیر است:

  • $s[2 \dots 5] = abab$
  • $s[3 \dots 6] = baba$
  • $s[7 \dots 8] = ee$

مثال دیگر:

$$abaaba$$

در اینجا فقط دو تکرار وجود دارد

  • $s[0 \dots 5] = abaaba$
  • $s[2 \dots 3] = aa$

تعداد تکرارها

به طور کلی، در یک رشته به طول $n$ می‌تواند تا $O(n^2)$ تکرار وجود داشته باشد. یک مثال واضح، رشته‌ای است که از $n$ بار تکرار یک حرف یکسان تشکیل شده است. در این حالت، هر زیررشته با طول زوج یک تکرار محسوب می‌شود. به طور کلی، هر رشته‌ی متناوب با یک دوره‌ی تناوب کوتاه، شامل تعداد زیادی تکرار خواهد بود.

از سوی دیگر، این واقعیت مانع از محاسبه‌ی تعداد تکرارها در زمان $O(n \log n)$ نمی‌شود، زیرا الگوریتم می‌تواند تکرارها را به صورت فشرده، در قالب گروه‌هایی از چند بخش به طور همزمان ارائه دهد.

حتی مفهومی وجود دارد که گروه‌هایی از زیررشته‌های متناوب را با چندتایی‌هایی (tuple) به اندازه‌ی چهار توصیف می‌کند. ثابت شده است که تعداد چنین گروه‌هایی حداکثر از مرتبه‌ی خطی نسبت به طول رشته است.

همچنین، در اینجا چند نتیجه‌ی جالب دیگر در رابطه با تعداد تکرارها آورده شده است:

  • تعداد تکرارهای اولیه (primitive) (آنهایی که نصف‌هایشان خودشان تکرار نیستند) حداکثر $O(n \log n)$ است.
  • اگر تکرارها را با چندتایی‌هایی از اعداد (که سه‌تایی‌های Crochemore نامیده می‌شوند) به صورت $(i,~ p,~ r)$ کدگذاری کنیم (که در آن $i$ موقعیت شروع، $p$ طول زیررشته‌ی تکرارشونده و $r$ تعداد تکرارها است)، آنگاه تمام تکرارها را می‌توان با $O(n \log n)$ از این سه‌تایی‌ها توصیف کرد.

  • رشته‌های فیبوناچی که به صورت زیر تعریف می‌شوند:

    $$\begin{align} t_0 &= a, \\\\ t_1 &= b, \\\\ t_i &= t_{i-1} + t_{i-2}, \end{align}$$

    "قویاً" متناوب هستند. تعداد تکرارها در رشته‌ی فیبوناچی $f_i$، حتی در حالت فشرده با سه‌تایی‌های Crochemore، از مرتبه‌ی $O(f_n \log f_n)$ است. تعداد تکرارهای اولیه نیز $O(f_n \log f_n)$ است.

الگوریتم Main-Lorentz

ایده‌ی اصلی الگوریتم Main-Lorentz، تقسیم و حل (divide-and-conquer) است.

این الگوریتم رشته‌ی اولیه را به دو نیمه تقسیم می‌کند و تعداد تکرارهایی که به طور کامل در هر نیمه قرار دارند را با دو فراخوانی بازگشتی محاسبه می‌کند. سپس بخش دشوار کار فرا می‌رسد. الگوریتم تمام تکرارهایی را که از نیمه‌ی اول شروع شده و در نیمه‌ی دوم خاتمه می‌یابند (که آنها را تکرارهای عبوری (crossing repetitions) می‌نامیم) پیدا می‌کند. این بخش اصلی الگوریتم Main-Lorentz است و ما در اینجا آن را با جزئیات بررسی خواهیم کرد.

پیچیدگی الگوریتم‌های تقسیم و حل به خوبی مطالعه شده است. قضیه‌ی اصلی می‌گوید که اگر بتوانیم تکرارهای عبوری را در زمان $O(n)$ محاسبه کنیم، به یک الگوریتم با پیچیدگی $O(n \log n)$ خواهیم رسید.

جستجو برای تکرارهای عبوری

بنابراین، می‌خواهیم تمام تکرارهایی را پیدا کنیم که از نیمه‌ی اول رشته، که آن را $u$ می‌نامیم، شروع شده و در نیمه‌ی دوم، که آن را $v$ می‌نامیم، به پایان می‌رسند:

$$s = u + v$$

طول آنها تقریباً برابر با نصف طول $s$ است.

یک تکرار دلخواه را در نظر بگیرید و به کاراکتر میانی آن نگاه کنید (به طور دقیق‌تر، اولین کاراکتر نیمه‌ی دوم تکرار). یعنی اگر تکرار، زیررشته‌ی $s[i \dots j]$ باشد، کاراکتر میانی در موقعیت $(i + j + 1) / 2$ قرار دارد.

ما یک تکرار را بسته به اینکه این کاراکتر در کدام رشته قرار دارد - در رشته‌ی $u$ یا در رشته‌ی $v$ - چپ یا راست می‌نامیم. به عبارت دیگر، یک تکرار را چپ می‌نامیم اگر بخش عمده‌ی آن در $u$ قرار داشته باشد، در غیر این صورت آن را راست می‌نامیم.

اکنون نحوه‌ی یافتن همه‌ی تکرارهای چپ را مورد بحث قرار می‌دهیم. یافتن تمام تکرارهای راست را می‌توان به همین روش انجام داد.

طول تکرار چپ را با $2l$ نشان می‌دهیم (یعنی هر نیمه‌ی تکرار طولی برابر با $l$ دارد). اولین کاراکتر تکرار را که در رشته‌ی $v$ قرار می‌گیرد در نظر بگیرید (این کاراکتر در موقعیت $|u|$ در رشته‌ی $s$ قرار دارد). این کاراکتر با کاراکتری که $l$ موقعیت قبل از آن قرار دارد، یکسان است. این موقعیت را $cntr$ می‌نامیم.

ما این موقعیت $cntr$ را ثابت در نظر می‌گیریم و به دنبال همه‌ی تکرارها در این موقعیت $cntr$ می‌گردیم.

برای مثال:

$$c ~ \underset{cntr}{a} ~ c ~ | ~ a ~ d ~ a$$

خط عمودی دو نیمه را از هم جدا می‌کند. در اینجا موقعیت $cntr = 1$ را ثابت در نظر گرفتیم و در این موقعیت، تکرار $caca$ را پیدا می‌کنیم.

واضح است که اگر موقعیت $cntr$ را ثابت در نظر بگیریم، همزمان طول تکرارهای ممکن را نیز ثابت کرده‌ایم: $l = |u| - cntr$. وقتی بدانیم چگونه این تکرارها را پیدا کنیم، روی تمام مقادیر ممکن برای $cntr$ از $0$ تا $|u|-1$ پیمایش کرده و تمام تکرارهای عبوری چپ با طول $l = |u|,~ |u|-1,~ \dots, 1$ را پیدا خواهیم کرد.

شرط لازم و کافی برای تکرارهای عبوری چپ

حال، چگونه می‌توانیم تمام این تکرارها را برای یک $cntr$ ثابت پیدا کنیم؟ به خاطر داشته باشید که هنوز هم ممکن است چندین تکرار از این نوع وجود داشته باشد.

بیایید دوباره به یک تصویرسازی نگاه کنیم، این بار برای تکرار $abcabc$:

$$\overbrace{a}^{l_1} ~ \overbrace{\underset{cntr}{b} ~ c}^{l_2} ~ \overbrace{a}^{l_1} ~ | ~ \overbrace{b ~ c}^{l_2}$$

در اینجا طول‌های دو قطعه از تکرار را با $l_1$ و $l_2$ مشخص کرده‌ایم: $l_1$ طول تکرار تا موقعیت $cntr-1$ است، و $l_2$ طول تکرار از $cntr$ تا انتهای نیمه‌ی تکرار است. طول کل تکرار برابر است با $2l = l_1 + l_2 + l_1 + l_2$.

بیایید شرایط لازم و کافی را برای چنین تکراری در موقعیت $cntr$ با طول $2l = 2(l_1 + l_2) = 2(|u| - cntr)$ استخراج کنیم:

  • فرض کنید $k_1$ بزرگترین عددی باشد که $k_1$ کاراکتر قبل از موقعیت $cntr$ با $k_1$ کاراکتر آخر رشته‌ی $u$ یکسان باشند:
$$ u[cntr - k_1 \dots cntr - 1] = u[|u| - k_1 \dots |u| - 1] $$
  • فرض کنید $k_2$ بزرگترین عددی باشد که $k_2$ کاراکتر که از موقعیت $cntr$ شروع می‌شوند با $k_2$ کاراکتر اول رشته‌ی $v$ یکسان باشند:
$$ u[cntr \dots cntr + k_2 - 1] = v[0 \dots k_2 - 1] $$
  • آنگاه دقیقاً برای هر جفت $(l_1,~ l_2)$ که در شرایط زیر صدق کند، یک تکرار خواهیم داشت:
$$ \begin{align} l_1 &\le k_1, \\\\ l_2 &\le k_2. \\\\ \end{align} $$

به طور خلاصه:

  • یک موقعیت خاص $cntr$ را ثابت می‌کنیم.
  • تمام تکرارهایی که اکنون پیدا می‌کنیم، طولی برابر با $2l = 2(|u| - cntr)$ دارند.
  • ممکن است چندین تکرار از این نوع وجود داشته باشد، که به طول‌های $l_1$ و $l_2 = l - l_1$ بستگی دارند.
  • ما $k_1$ و $k_2$ را همانطور که در بالا توضیح داده شد، پیدا می‌کنیم.
  • سپس تمام تکرارهای مناسب، آنهایی هستند که طول قطعات $l_1$ و $l_2$ در شرایط زیر صدق کنند:
$$ \begin{align} l_1 + l_2 &= l = |u| - cntr \\\\ l_1 &\le k_1, \\\\ l_2 &\le k_2. \\\\ \end{align} $$

بنابراین، تنها بخش باقی‌مانده این است که چگونه می‌توانیم مقادیر $k_1$ و $k_2$ را به سرعت برای هر موقعیت $cntr$ محاسبه کنیم. خوشبختانه می‌توانیم آنها را با استفاده از تابع Z در زمان $O(1)$ محاسبه کنیم:

  • برای پیدا کردن مقدار $k_1$ برای هر موقعیت، تابع Z را برای رشته‌ی $\overline{u}$ (یعنی رشته‌ی معکوس $u$) محاسبه می‌کنیم. سپس مقدار $k_1$ برای یک $cntr$ خاص برابر با مقدار متناظر در آرایه‌ی تابع Z خواهد بود.
  • برای پیش‌محاسبه‌ی تمام مقادیر $k_2$، تابع Z را برای رشته‌ی $v + \# + u$ (یعنی رشته‌ی $v$ الحاق‌شده با کاراکتر جداکننده $\#$ و رشته‌ی $u$) محاسبه می‌کنیم. دوباره، فقط کافی است مقدار متناظر در تابع Z را برای به دست آوردن مقدار $k_2$ جستجو کنیم.

بنابراین این کار برای یافتن تمام تکرارهای عبوری چپ کافی است.

تکرارهای عبوری راست

برای محاسبه‌ی تکرارهای عبوری راست، به طور مشابه عمل می‌کنیم: ما مرکز $cntr$ را به عنوان کاراکتری که متناظر با آخرین کاراکتر در رشته‌ی $u$ است، تعریف می‌کنیم.

سپس طول $k_1$ به عنوان بزرگترین تعداد کاراکترهایی تعریف می‌شود که قبل از موقعیت $cntr$ (شامل خود آن) قرار دارند و با کاراکترهای آخر رشته‌ی $u$ یکسان هستند. و طول $k_2$ به عنوان بزرگترین تعداد کاراکترهایی تعریف می‌شود که از $cntr + 1$ شروع می‌شوند و با کاراکترهای رشته‌ی $v$ یکسان هستند.

بنابراین، می‌توانیم مقادیر $k_1$ و $k_2$ را با محاسبه‌ی تابع Z برای رشته‌های $\overline{u} + \# + \overline{v}$ و $v$ پیدا کنیم.

پس از آن، می‌توانیم با بررسی تمام موقعیت‌های $cntr$ و با استفاده از همان شرطی که برای تکرارهای عبوری چپ داشتیم، تکرارها را پیدا کنیم.

پیاده‌سازی

پیاده‌سازی الگوریتم Main-Lorentz تمام تکرارها را به شکل چندتایی‌های (tuple) چهارعضوی خاص $(cntr,~ l,~ k_1,~ k_2)$ در زمان $O(n \log n)$ پیدا می‌کند. اگر فقط بخواهید تعداد تکرارها را در یک رشته پیدا کنید، یا فقط بخواهید طولانی‌ترین تکرار را پیدا کنید، این اطلاعات کافی است و زمان اجرا همچنان $O(n \log n)$ خواهد بود.

توجه داشته باشید که اگر بخواهید این چندتایی‌ها را برای به دست آوردن موقعیت شروع و پایان هر تکرار بسط دهید، آنگاه زمان اجرا $O(n^2)$ خواهد بود (به یاد داشته باشید که می‌تواند تا $O(n^2)$ تکرار وجود داشته باشد). در این پیاده‌سازی، ما این کار را انجام می‌دهیم و تمام تکرارهای یافت‌شده را در یک vector از جفت‌های اندیس شروع و پایان ذخیره می‌کنیم.

vector<int> z_function(string const& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r)
            z[i] = min(r-i+1, z[i-l]);
        while (i + z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int get_z(vector<int> const& z, int i) {
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}

vector<pair<int, int>> repetitions;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
        if (left && l1 == l) break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2*l - 1);
    }
}

void find_repetitions(string s, int shift = 0) {
    int n = s.size();
    if (n == 1)
        return;

    int nu = n / 2;
    int nv = n - nu;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++) {
        int l, k1, k2;
        if (cntr < nu) {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}