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

هَشینگ رشته

الگوریتم‌های هشینگ در حل بسیاری از مسائل مفید هستند.

می‌خواهیم مسئله‌ی مقایسه بهینه‌ی رشته‌ها را حل کنیم. روش brute force برای این کار، مقایسه‌ی کاراکتر به کاراکتر دو رشته است که پیچیدگی زمانی آن $O(\min(n_1, n_2))$ است، اگر $n_1$ و $n_2$ طول دو رشته باشند. ما می‌خواهیم بهتر از این عمل کنیم. ایده‌ی اصلی در هشینگ رشته این است: هر رشته را به یک عدد صحیح نگاشت می‌کنیم و به جای مقایسه‌ی رشته‌ها، این اعداد را با هم مقایسه می‌کنیم. این کار به ما اجازه می‌دهد زمان اجرای مقایسه‌ی رشته‌ها را به $O(1)$ کاهش دهیم.

برای این تبدیل، به چیزی به نام تابع هَش (hash function) نیاز داریم. هدف این تابع، تبدیل یک رشته به یک عدد صحیح است که به آن هَش (hash) رشته می‌گویند. شرط زیر باید برقرار باشد: اگر دو رشته‌ی $s$ و $t$ برابر باشند ($s = t$)، آنگاه هَش‌های آن‌ها نیز باید برابر باشند ($\text{hash}(s) = \text{hash}(t)$). در غیر این صورت، قادر به مقایسه‌ی رشته‌ها نخواهیم بود.

توجه کنید که عکس این موضوع لزوماً برقرار نیست. اگر هَش‌ها برابر باشند ($\text{hash}(s) = \text{hash}(t)$)، رشته‌ها لزوماً برابر نیستند. مثلاً، یک تابع هَش معتبر می‌تواند به سادگی $\text{hash}(s) = 0$ برای هر رشته‌ی $s$ باشد. البته این یک مثال احمقانه است، چون این تابع کاملاً بی‌فایده است، اما یک تابع هَش معتبر محسوب می‌شود. دلیل اینکه عکس این موضوع لزوماً برقرار نیست این است که تعداد رشته‌ها به صورت نمایی زیاد است. اگر بخواهیم این تابع هَش تمام رشته‌های متشکل از حروف کوچک انگلیسی با طول کمتر از ۱۵ را از هم متمایز کند، دیگر مقدار هَش در یک عدد صحیح ۶۴ بیتی (مثلاً unsigned long long) جا نمی‌شود، چون تعداد این رشته‌ها بسیار زیاد است. و البته، ما نمی‌خواهیم اعداد صحیح با طول دلخواه را مقایسه کنیم، زیرا این کار نیز پیچیدگی $O(n)$ خواهد داشت.

بنابراین، معمولاً می‌خواهیم تابع هَش، رشته‌ها را به اعدادی در یک بازه‌ی ثابت $[0, m)$ نگاشت کند. در این صورت، مقایسه‌ی رشته‌ها تنها مقایسه‌ی دو عدد صحیح با طول ثابت خواهد بود. و البته، می‌خواهیم اگر $s \neq t$ باشد، به احتمال خیلی زیاد $\text{hash}(s) \neq \text{hash}(t)$ نیز برقرار باشد.

این بخش مهمی است که باید به خاطر داشته باشید. استفاده از هشینگ ۱۰۰٪ قطعی و درست نخواهد بود، زیرا ممکن است دو رشته‌ی کاملاً متفاوت، هَش یکسانی داشته باشند (که به آن برخورد یا collision می‌گویند). با این حال، در اکثر قریب به اتفاق مسائل، می‌توان این موضوع را با خیال راحت نادیده گرفت، زیرا احتمال برخورد هَش دو رشته‌ی متفاوت بسیار کم است. و در این مقاله، تکنیک‌هایی را برای پایین نگه داشتن احتمال برخوردها بررسی خواهیم کرد.

محاسبه هَش یک رشته

روش خوب و پراستفاده برای تعریف هَش یک رشته $s$ به طول $n$ به صورت زیر است:

$$\begin{align} \text{hash}(s) &= s[0] + s[1] \cdot p + s[2] \cdot p^2 + ... + s[n-1] \cdot p^{n-1} \mod m \\ &= \sum_{i=0}^{n-1} s[i] \cdot p^i \mod m, \end{align}$$

که در آن $p$ و $m$ اعدادی مثبت و منتخب هستند. این تابع، تابع هَش غلتان چندجمله‌ای (polynomial rolling hash function) نامیده می‌شود.

معقول است که $p$ را یک عدد اول، تقریباً برابر با تعداد کاراکترهای الفبای ورودی انتخاب کنیم. برای مثال، اگر ورودی فقط از حروف کوچک الفبای انگلیسی تشکیل شده باشد، $p = 31$ انتخاب خوبی است. اگر ورودی ممکن است شامل حروف بزرگ و کوچک باشد، $p = 53$ یک انتخاب ممکن است. کد موجود در این مقاله از $p = 31$ استفاده خواهد کرد.

بدیهی است که $m$ باید عدد بزرگی باشد، زیرا احتمال برخورد دو رشته‌ی تصادفی تقریباً برابر با $\frac{1}{m}$ است. گاهی اوقات $m = 2^{64}$ انتخاب می‌شود، زیرا در این صورت سرریز (overflow) اعداد صحیح ۶۴ بیتی دقیقاً مانند عملیات باقی‌مانده (modulo) عمل می‌کند. با این حال، روشی وجود دارد که رشته‌های دارای برخورد تولید می‌کند (و این روش مستقل از انتخاب $p$ عمل می‌کند). بنابراین در عمل، $m = 2^{64}$ توصیه نمی‌شود. یک انتخاب خوب برای $m$، یک عدد اول بزرگ است. کد موجود در این مقاله از $m = 10^9+9$ استفاده می‌کند. این عدد بزرگی است، اما همچنان به اندازه‌ای کوچک است که بتوانیم ضرب دو مقدار را با استفاده از اعداد صحیح ۶۴ بیتی انجام دهیم.

در اینجا مثالی از محاسبه‌ی هَش رشته‌ی $s$ که فقط شامل حروف کوچک است، آورده شده است. ما هر کاراکتر از $s$ را به یک عدد صحیح تبدیل می‌کنیم. در اینجا از تبدیل $a \rightarrow 1$، $b \rightarrow 2$، ...، $z \rightarrow 26$ استفاده می‌کنیم. تبدیل $a \rightarrow 0$ ایده‌ی خوبی نیست، زیرا در این صورت هَش رشته‌های $a$، $aa$، $aaa$ و ... همگی برابر با $0$ خواهد شد.

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

پیش‌محاسبه‌ی توان‌های $p$ می‌تواند باعث افزایش عملکرد شود.

مسائل نمونه

جستجوی رشته‌های تکراری در آرایه‌ای از رشته‌ها

مسئله: با داشتن لیستی از $n$ رشته‌ی $s_i$ که طول هیچ‌کدام بیشتر از $m$ کاراکتر نیست، تمام رشته‌های تکراری را پیدا کرده و آن‌ها را گروه‌بندی کنید.

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

ما هَش هر رشته را محاسبه می‌کنیم، هَش‌ها را به همراه اندیس‌هایشان مرتب می‌کنیم و سپس اندیس‌ها را بر اساس هَش‌های یکسان گروه‌بندی می‌کنیم.

vector<vector<int>> group_identical_strings(vector<string> const& s) {
    int n = s.size();
    vector<pair<long long, int>> hashes(n);
    for (int i = 0; i < n; i++)
        hashes[i] = {compute_hash(s[i]), i};

    sort(hashes.begin(), hashes.end());

    vector<vector<int>> groups;
    for (int i = 0; i < n; i++) {
        if (i == 0 || hashes[i].first != hashes[i-1].first)
            groups.emplace_back();
        groups.back().push_back(hashes[i].second);
    }
    return groups;
}

محاسبه سریع هَش زیررشته‌های یک رشته

مسئله: با داشتن یک رشته $s$ و اندیس‌های $i$ و $j$، هَش زیررشته‌ی $s[i \dots j]$ را پیدا کنید.

طبق تعریف داریم:

$$\text{hash}(s[i \dots j]) = \sum_{k = i}^j s[k] \cdot p^{k-i} \mod m$$

با ضرب کردن در $p^i$ داریم:

$$\begin{align} \text{hash}(s[i \dots j]) \cdot p^i &= \sum_{k = i}^j s[k] \cdot p^k \mod m \\ &= \text{hash}(s[0 \dots j]) - \text{hash}(s[0 \dots i-1]) \mod m \end{align}$$

بنابراین با دانستن مقدار هَش هر پیشوند از رشته‌ی $s$، می‌توانیم هَش هر زیررشته‌ای را مستقیماً با استفاده از این فرمول محاسبه کنیم. تنها مشکلی که در محاسبه‌ی آن با آن روبرو هستیم این است که باید بتوانیم $\text{hash}(s[0 \dots j]) - \text{hash}(s[0 \dots i-1])$ را بر $p^i$ تقسیم کنیم. بنابراین، باید وارون ضربی پیمانه‌ای $p^i$ را پیدا کرده و سپس در این وارون ضرب کنیم. می‌توانیم وارون هر $p^i$ را پیش‌محاسبه کنیم که این کار امکان محاسبه‌ی هَش هر زیررشته از $s$ را در زمان $O(1)$ فراهم می‌کند.

با این حال، یک راه آسان‌تر نیز وجود دارد. در بیشتر موارد، به جای محاسبه‌ی دقیق هَش زیررشته‌ها، کافی است هَش را در توانی از $p$ ضرب کنیم. فرض کنید هَش دو زیررشته را داریم، یکی ضرب شده در $p^i$ و دیگری در $p^j$. اگر $i < j$ باشد، هَش اول را در $p^{j-i}$ ضرب می‌کنیم، در غیر این صورت، هَش دوم را در $p^{i-j}$ ضرب می‌کنیم. با این کار، هر دو هَش در توان یکسانی از $p$ (که برابر با بیشینه‌ی $i$ و $j$ است) ضرب می‌شوند و اکنون این هَش‌ها را می‌توان به راحتی و بدون نیاز به هیچ تقسیمی مقایسه کرد.

کاربردهای هشینگ

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

  • الگوریتم Rabin-Karp برای تطبیق الگو در یک رشته در زمان $O(n)$
  • محاسبه‌ی تعداد زیررشته‌های متمایز یک رشته در $O(n^2)$ (در ادامه توضیح داده شده است)
  • محاسبه‌ی تعداد زیررشته‌های پالیندروم (palindrome) در یک رشته.

تعیین تعداد زیررشته‌های متمایز در یک رشته

مسئله: با داشتن یک رشته $s$ به طول $n$ که فقط از حروف کوچک انگلیسی تشکیل شده است، تعداد زیررشته‌های متمایز این رشته را پیدا کنید.

برای حل این مسئله، روی تمام طول‌های ممکن برای زیررشته، یعنی $l = 1 \dots n$، پیمایش می‌کنیم. به ازای هر طول $l$، آرایه‌ای از هَش‌های تمام زیررشته‌های به طول $l$ را که همگی در توان یکسانی از $p$ ضرب شده‌اند، می‌سازیم. تعداد عناصر متمایز در این آرایه برابر با تعداد زیررشته‌های متمایز به طول $l$ در رشته است. این عدد به پاسخ نهایی اضافه می‌شود.

برای راحتی، از $h[i]$ به عنوان هَش پیشوندی با $i$ کاراکتر استفاده می‌کنیم و $h[0] = 0$ را تعریف می‌کنیم.

int count_unique_substrings(string const& s) {
    int n = s.size();

    const int p = 31;
    const int m = 1e9 + 9;
    vector<long long> p_pow(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i-1] * p) % m;

    vector<long long> h(n + 1, 0);
    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;

    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        unordered_set<long long> hs;
        for (int i = 0; i <= n - l; i++) {
            long long cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n-i-1]) % m;
            hs.insert(cur_h);
        }
        cnt += hs.size();
    }
    return cnt;
}

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

بهبود احتمال عدم برخورد

اغلب اوقات، هَش چندجمله‌ای که در بالا ذکر شد به اندازه‌ی کافی خوب است و در حین تست‌ها هیچ برخوردی رخ نخواهد داد. به یاد داشته باشید، احتمال وقوع برخورد تنها $\approx \frac{1}{m}$ است. برای $m = 10^9 + 9$ این احتمال تقریباً $10^{-9}$ است که بسیار کم است. اما توجه کنید که ما فقط یک مقایسه انجام دادیم. چه اتفاقی می‌افتد اگر یک رشته $s$ را با $10^6$ رشته‌ی مختلف مقایسه کنیم؟ احتمال وقوع حداقل یک برخورد اکنون تقریباً $10^{-3}$ است. و اگر بخواهیم $10^6$ رشته‌ی مختلف را با یکدیگر مقایسه کنیم (مثلاً با شمردن تعداد رشته‌های یکتا)، احتمال وقوع حداقل یک برخورد تقریباً برابر با ۱ خواهد بود. تقریباً تضمین شده است که این مسئله با یک برخورد مواجه شده و نتیجه‌ی اشتباهی برمی‌گرداند.

یک ترفند بسیار ساده برای به دست آوردن احتمال بهتر وجود دارد. می‌توانیم برای هر رشته دو هَش متفاوت محاسبه کنیم (با استفاده از دو مقدار متفاوت برای $p$ و/یا دو مقدار متفاوت برای $m$) و به جای یک هَش، این زوج‌ها را مقایسه کنیم. اگر $m$ برای هر دو تابع هَش حدود $10^9$ باشد، این کار کم و بیش معادل داشتن یک تابع هَش با $m \approx 10^{18}$ است. هنگام مقایسه‌ی $10^6$ رشته با یکدیگر، احتمال وقوع حداقل یک برخورد اکنون به حدود $10^{-6}$ کاهش می‌یابد.

مسائل تمرینی