Тэмдэгт мөрийн хэшлэлт¶

Хэшлэх алгоритмууд олон бодлого бодоход тустай.

Бид тэмдэгт мөрүүдийг үр ашигтай харьцуулах бодлогыг бодохыг хүсэж байна. Үүнийг хийх шууд хүчний арга бол хоёр тэмдэгт мөрийн үсгүүдийг зүгээр л харьцуулах бөгөөд $n_1$ ба $n_2$ нь хоёр тэмдэгт мөрийн хэмжээ бол энэ нь $O(\min(n_1, n_2))$ time complexity-тэй. Бид үүнээс илүү сайныг хийхийг хүсэж байна. Тэмдэгт мөрийн хэшлэлтийн цаад санаа нь дараах юм: бид тэмдэгт мөр бүрийг бүхэл тоо руу буулгаж, тэмдэгт мөрүүдийн оронд тэдгээрийг харьцуулна. Ингэснээр бид тэмдэгт мөрийн харьцуулалтын гүйцэтгэлийн хугацааг $O(1)$ болгон бууруулж чадна.

Хөрвүүлэлтэд бидэнд хэш функц гэж нэрлэгддэг зүйл хэрэгтэй. Түүний зорилго нь тэмдэгт мөрийг бүхэл тоо буюу тэмдэгт мөрийн хэш гэж нэрлэгддэг зүйл рүү хөрвүүлэх явдал юм. Дараах нөхцөл биелэх ёстой: хэрэв $s$ ба $t$ гэсэн хоёр тэмдэгт мөр тэнцүү бол ($s = t$) тэдгээрийн хэш мөн тэнцүү байх ёстой ($\text{hash}(s) = \text{hash}(t)$). Эс бөгөөс бид тэмдэгт мөрүүдийг харьцуулж чадахгүй.

Эсрэг чиглэл нь биелэх албагүй гэдгийг анзаар. Хэрэв хэшүүд тэнцүү бол ($\text{hash}(s) = \text{hash}(t)$) тэмдэгт мөрүүд заавал тэнцүү байх албагүй. Жишээ нь $s$ бүрийн хувьд $\text{hash}(s) = 0$ гэдэг нь зүгээр л хүчинтэй хэш функц болно. Энэ бол зүгээр л тэнэг жишээ, учир нь энэ функц огт хэрэггүй байх ч энэ нь хүчинтэй хэш функц мөн. Эсрэг чиглэл биелэх албагүйн шалтгаан нь тэмдэгт мөр экспоненциал олон байдагт оршино. Хэрэв бид энэ хэш функцээр зөвхөн 15-аас бага урттай, жижиг үсгээс бүрдсэн бүх тэмдэгт мөрийг ялгахыг хүсвэл ч хэш нь 64 битийн бүхэл тоонд (жишээ нь unsigned long long) аль хэдийн багтахаа болино, учир нь тэдгээр маш олон байна. Мэдээж бид дурын урт бүхэл тоог харьцуулахыг хүсэхгүй, учир нь энэ нь мөн $O(n)$ complexity-тэй байх болно.

Тиймээс бид ихэвчлэн хэш функц нь тэмдэгт мөрүүдийг тогтмол $[0, m)$ мужийн тоо руу буулгаасай гэж хүсдэг, тэгвэл тэмдэгт мөр харьцуулах нь зүгээр л тогтмол урттай хоёр бүхэл тоог харьцуулах явдал болно. Мэдээж бид $s \neq t$ бол $\text{hash}(s) \neq \text{hash}(t)$ байх магадлал өндөр байгаасай гэж хүсэж байна.

Энэ бол таны санаж байх ёстой чухал хэсэг юм. Хэшлэлт ашиглах нь 100% детерминистикээр зөв байхгүй, учир нь огт өөр хоёр тэмдэгт мөр ижил хэштэй байж болно (хэшүүд мөргөлдөнө). Гэвч бодлогуудын дийлэнх олонхид үүнийг аюулгүйгээр үл тоомсорлож болно, учир нь өөр хоёр тэмдэгт мөрийн хэш мөргөлдөх магадлал маш бага хэвээр байдаг. Мөн бид энэ өгүүлэлд мөргөлдөөний магадлалыг маш бага байлгах зарим арга барилыг хэлэлцэнэ.

Тэмдэгт мөрийн хэшийг тооцоолох¶

$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$-г ашиглана.

Санамсаргүй хоёр тэмдэгт мөр мөргөлдөх магадлал ойролцоогоор $\approx \frac{1}{m}$ тул $m$ том тоо байх нь илэрхий. Заримдаа $m = 2^{64}$-г сонгодог, учир нь тэгвэл 64 битийн бүхэл тооны халилт нь модулийн үйлдэлтэй яг адилхан ажиллана. Гэвч мөргөлддөг тэмдэгт мөр үүсгэдэг арга байдаг ($p$-ийн сонголтоос үл хамааран ажилладаг). Тиймээс практикт $m = 2^{64}$-г зөвлөдөггүй. $m$-ийн сайн сонголт бол ямар нэг том анхны тоо юм. Энэ өгүүлэл дэх код зүгээр л $m = 10^9+9$-г ашиглана. Энэ бол том тоо боловч бид хоёр утгын үржүүлэлтийг 64 битийн бүхэл тоо ашиглан гүйцэтгэж чадахаар хангалттай бага хэвээр байна.

Зөвхөн жижиг үсэг агуулсан $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$-ийн зэргүүдийг урьдчилан тооцоолох нь гүйцэтгэлийг сайжруулж болно.

Жишээ бодлогууд¶

Тэмдэгт мөрийн массиваас давхардсан тэмдэгт мөрийг хайх¶

Бодлого: Тус бүр нь $m$ тэмдэгтээс урт биш $n$ ширхэг $s_i$ тэмдэгт мөрийн жагсаалт өгөгдсөн үед бүх давхардсан тэмдэгт мөрийг олж, тэдгээрийг бүлэгт хуваа.

Тэмдэгт мөрүүдийг эрэмбэлэх илэрхий алгоритмаас бид $O(n m \log n)$ time complexity авах ба энд эрэмбэлэлт $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)$ нь энэ бодлогын хамгийн сайн боломжит time complexity биш болохыг анзаар. $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}$ хүртэл буурна.