স্ট্রিং হ্যাশিং#

হ্যাশিং অ্যালগরিদম অনেক সমস্যা সমাধানে সহায়ক।

আমরা স্ট্রিং দক্ষতার সাথে তুলনা করার সমস্যাটি সমাধান করতে চাই। ব্রুট ফোর্স পদ্ধতি হলো উভয় স্ট্রিং-এর অক্ষরগুলো তুলনা করা, যার টাইম কমপ্লেক্সিটি $O(\min(n_1, n_2))$ যদি $n_1$ এবং $n_2$ দুটি স্ট্রিং-এর আকার হয়। আমরা আরও ভালো করতে চাই। স্ট্রিং হ্যাশিং-এর পেছনের ধারণাটি নিম্নরূপ: আমরা প্রতিটি স্ট্রিংকে একটি পূর্ণসংখ্যায় ম্যাপ করি এবং স্ট্রিং-এর পরিবর্তে সেগুলো তুলনা করি। এটি করলে স্ট্রিং তুলনার এক্সিকিউশন সময় $O(1)$-এ কমানো যায়।

রূপান্তরের জন্য, আমাদের একটি তথাকথিত হ্যাশ ফাংশন দরকার। এর লক্ষ্য হলো একটি স্ট্রিংকে একটি পূর্ণসংখ্যায় রূপান্তর করা, যাকে স্ট্রিং-এর তথাকথিত হ্যাশ বলা হয়। নিম্নলিখিত শর্তটি পূরণ হতে হবে: যদি দুটি স্ট্রিং $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)$ হওয়ার সম্ভাবনা খুব বেশি হোক।

এটি গুরুত্বপূর্ণ অংশ যা মনে রাখতে হবে। হ্যাশিং ব্যবহার ১০০% নিশ্চিতভাবে সঠিক হবে না, কারণ দুটি সম্পূর্ণ ভিন্ন স্ট্রিং-এর একই হ্যাশ থাকতে পারে (হ্যাশ কলিশন হয়)। তবে, বেশিরভাগ কাজে এটি নিরাপদে উপেক্ষা করা যায় কারণ দুটি ভিন্ন স্ট্রিং-এর হ্যাশ কলিশনের সম্ভাবনা এখনও খুব কম। এবং আমরা এই নিবন্ধে কিছু কৌশল আলোচনা করব কিভাবে কলিশনের সম্ভাবনা খুব কম রাখা যায়।

একটি স্ট্রিং-এর হ্যাশ গণনা#

$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$-এর হ্যাশ সংজ্ঞায়িত করার ভালো এবং বহুল ব্যবহৃত উপায় হলো

$$\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$ হলো কিছু নির্বাচিত, ধনাত্মক সংখ্যা। এটিকে পলিনোমিয়াল রোলিং হ্যাশ ফাংশন বলা হয়।

$p$-কে ইনপুট বর্ণমালার অক্ষর সংখ্যার কাছাকাছি একটি মৌলিক সংখ্যা করা যুক্তিসঙ্গত। উদাহরণস্বরূপ, যদি ইনপুট শুধু ইংরেজি বর্ণমালার ছোট হাতের অক্ষর নিয়ে গঠিত হয়, $p = 31$ একটি ভালো পছন্দ। যদি ইনপুটে বড় হাতের এবং ছোট হাতের উভয় অক্ষর থাকতে পারে, তাহলে $p = 53$ একটি সম্ভাব্য পছন্দ। এই নিবন্ধের কোডে $p = 31$ ব্যবহার করা হবে।

স্পষ্টতই $m$ একটি বড় সংখ্যা হওয়া উচিত কারণ দুটি র‍্যান্ডম স্ট্রিং-এর কলিশনের সম্ভাবনা প্রায় $\approx \frac{1}{m}$। কখনও কখনও $m = 2^{64}$ বেছে নেওয়া হয়, যেহেতু তখন ৬৪-বিট ইন্টিজারের পূর্ণসংখ্যা ওভারফ্লো ঠিক মডুলো অপারেশনের মতো কাজ করে। তবে, এমন একটি পদ্ধতি আছে, যা কলিশন করা স্ট্রিং তৈরি করে ($p$-এর পছন্দ নির্বিশেষে)। তাই বাস্তবে, $m = 2^{64}$ সুপারিশ করা হয় না। $m$-এর জন্য একটি ভালো পছন্দ হলো কোনো বড় মৌলিক সংখ্যা। এই নিবন্ধের কোডে $m = 10^9+9$ ব্যবহার করা হবে। এটি একটি বড় সংখ্যা, কিন্তু যথেষ্ট ছোট যাতে আমরা ৬৪-বিট ইন্টিজার ব্যবহার করে দুটি মানের গুণ করতে পারি।

এখানে একটি স্ট্রিং $s$-এর হ্যাশ গণনার একটি উদাহরণ, যেটিতে শুধু ছোট হাতের অক্ষর আছে। আমরা $s$-এর প্রতিটি অক্ষরকে একটি পূর্ণসংখ্যায় রূপান্তর করি। এখানে আমরা রূপান্তর $a \rightarrow 1$, $b \rightarrow 2$, $\dots$, $z \rightarrow 26$ ব্যবহার করি। $a \rightarrow 0$ রূপান্তর করা ভালো ধারণা নয়, কারণ তাহলে $a$, $aa$, $aaa$, $\dots$ স্ট্রিংগুলোর হ্যাশ সব $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$-এর সর্বোচ্চ) এবং এখন এই হ্যাশগুলো কোনো ভাগ ছাড়াই সহজে তুলনা করা যায়।

হ্যাশিং-এর প্রয়োগ#

এখানে হ্যাশিং-এর কিছু সাধারণ প্রয়োগ:

$O(n)$ সময়ে স্ট্রিং-এ প্যাটার্ন ম্যাচিং-এর জন্য রবিন-কার্প অ্যালগরিদম
$O(n^2)$-এ একটি স্ট্রিং-এর ভিন্ন সাবস্ট্রিং-এর সংখ্যা গণনা (নিচে দেখুন)
একটি স্ট্রিং-এ প্যালিন্ড্রোমিক সাবস্ট্রিং-এর সংখ্যা গণনা।

একটি স্ট্রিং-এ ভিন্ন সাবস্ট্রিং-এর সংখ্যা নির্ণয়#

সমস্যা: $n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে, যাতে শুধু ইংরেজির ছোট হাতের অক্ষর আছে, এই স্ট্রিং-এ ভিন্ন সাবস্ট্রিং-এর সংখ্যা বের করুন।

এই সমস্যা সমাধানের জন্য, আমরা সকল সাবস্ট্রিং দৈর্ঘ্য $l = 1 \dots n$-এর উপর ইটারেট করি। প্রতিটি সাবস্ট্রিং দৈর্ঘ্য $l$-এর জন্য আমরা $p$-এর একই পাওয়ার দিয়ে গুণিত সকল $l$ দৈর্ঘ্যের সাবস্ট্রিং-এর হ্যাশের একটি অ্যারে তৈরি করি। অ্যারেতে ভিন্ন উপাদানের সংখ্যা স্ট্রিং-এ $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$ এর জন্য সম্ভাবনা $\approx 10^{-9}$ যা বেশ কম। কিন্তু লক্ষ্য করুন, আমরা শুধু একটি তুলনা করেছি। যদি আমরা একটি স্ট্রিং $s$-কে $10^6$ বিভিন্ন স্ট্রিং-এর সাথে তুলনা করি? কমপক্ষে একটি কলিশন হওয়ার সম্ভাবনা এখন $\approx 10^{-3}$। এবং যদি আমরা $10^6$ বিভিন্ন স্ট্রিংকে পরস্পরের সাথে তুলনা করতে চাই (যেমন কতগুলো অনন্য স্ট্রিং আছে গণনা করা), তাহলে কমপক্ষে একটি কলিশন হওয়ার সম্ভাবনা ইতিমধ্যে $\approx 1$। এটি প্রায় নিশ্চিত যে এই কাজটি কলিশনসহ শেষ হবে এবং ভুল ফলাফল দেবে।

আরও ভালো সম্ভাবনা পেতে একটি সত্যিই সহজ কৌশল আছে। আমরা কেবল প্রতিটি স্ট্রিং-এর জন্য দুটি ভিন্ন হ্যাশ গণনা করতে পারি (দুটি ভিন্ন $p$, এবং/অথবা ভিন্ন $m$ ব্যবহার করে), এবং এই জোড়াগুলো তুলনা করতে পারি। যদি প্রতিটি হ্যাশ ফাংশনের জন্য $m$ প্রায় $10^9$ হয় তাহলে এটি $m \approx 10^{18}$ এর একটি হ্যাশ ফাংশনের সমতুল্য। $10^6$ স্ট্রিং পরস্পরের সাথে তুলনা করার সময়, কমপক্ষে একটি কলিশন হওয়ার সম্ভাবনা এখন $\approx 10^{-6}$-এ কমে যায়।