Хеширане

Нека имамe произволен вид обекти и искаме да можем лесно да разпознаваме кога два от тях съвпадат. Най-лесно би било ако можем да им съпоставяме числа и просто сравняваме дали числата са равни или не. Това е същността на хеширането. Съпоставяме на обекти числа по някакъв хеширащ алгоритъм.

Определение: Нека множеството обекти означим с $D$. Тогава математически хеширането е функция $h: D \rightarrow N,$ т.е. на елемент от $D$ съпоставя число, което се нарича хеш-код или хеш накратко.

Преди да продължим нататък нека дадем един практически пример. Всеки е теглил файлове от интернет чрез торенти. След като даден торент завърши, се прави кратка проверка за това дали е изтеглен цял файл (и без вируси). Тази проверка в същността си е да провери хеша на изтегления файл дали съвпада с хеша на ориганала.

Идеята е хубава, но тя има един голям проблем. Нека да се насочим към често срещан пример в състезателната информатика. Ще хешираме низове, т.е. хеш-функцията е $h:$ низове $\rightarrow$ числа, като числата ги ограничаваме до около $2^{64}$, колкото е броят на 64-битовите числа (съответно големината на тип long long в C++). Ако разглеждаме низове с малки латински букви с до $10^5$ символа, то различните такива низове са $26^{10^5}$. Така на тази голяма бройка съпоставяме едва $2^{64}$ числа. По принципа на Дирихле е ясно, че ще имаме повторения, т.е. на различни низове ще съпоставяме едно и също число. Това наричаме колизия на хеш-функцията.

Определение: Нека имаме два обекта $d_1$ и $d_2$ от $D$. Тогава ако $d_1 \ne d_2,$ но $h(d_1) = h(d_2),$ казваме че имаме колизия на хеш-функцията.

Ясно е, че няма как, използвайки по-малко множество, да кодираме по-голямо множество без да имаме колизии. Затова има разчлични алгоритми и практики, чрез които да намалим негативните ефекти на това. Има два основни типа хеширащи алгоритми:

  • позиционно хеширане
  • непозиционно хеширане

Този вид се изпозва за хеширане на низове, редици, въобще обекти, в които наредбата има значение. Нека да се върнем към примера с низовете от малки латински букви (...), за да демонстрираме стандартното хеширане, използвано в състезателната информатика. Разглеждаме низа като число в позиционна бройна система. Лесно можем да съпоставяме на всяка буква, индексът в азбуката или по-универсално ASCII кода. Така ако фиксираме основата на бройната система $p$ можем лесно да сметнем какви числа, съпоставяме на низовете. По този начин обаче не се съобразяваме, че ще съпоставяме единствено числа, които се събират в типа long long в C++, защото хешът на низа лесно ще стане много по-голям, отколкото може да се побере в типа. Затова стандартно се добавя модул $m$, по който извършваме сметките смятаме. По този начин възможните хеш-кодове са числата $0,1, \dots , m-1$ $-$ общо $m$ на брой. По математически причини е силно препоръчително това число да е просто (...). Желателно е и основата на бройната система $p$ да е просто число, по-голямо от най-големия ASCII код (255). Нека разгледаме точно как става описаното хеширане със следният интерактивен пример:

Като работим със C++ трябва да подберем модулът, така че $m^2 \le 2^{63}-1$, за да може спокойно да умножаваме числа по този модул, без да се притесняваме от overflow в long long. По прицип, колкото е по-голям модулът, толкова по-добре. Стандартни модули, които се използват са $10^9+7, 10^9+9, \dots$ Пресмятането на хеша на даден низ в програма става по-лесно, отколкото в примера, например така:

Тук използваме схемата на Хорнер за пресмятане на стойността на "число", като знаем цифрите му. Ако погледнем по-внимателно ще видим, че единствената по-тежка операция, която се извършва е $\%$. Понеже тази операция се извършва постоянно при работата с хешове, то тя прави по-голямата константа при използването на техниката. Има един трик, с който понякога можем да спестим модването. Можем да използваме естественото модване на тип unsigned long long - когато дадена сметка надвиши максималната допустима стойност става т.нар. overflow или превъртане на типа. Това от своя страна е естествено модване по модул $2^{64}$. Така ако използваме този тип няма нужда от измислянето на модул. Негативите са следните. Първо, по-лесно ще стават колизии, защото модулът е далеч от просто число. Второ, много от задачите имат така наречените анти-хеш тестове, които са направени специално срещу този вид хеширане. Затова по принцип се използва стандартното хеширане с модул просто число.

Сега ще приложим тази техника за оптимално решаване на една стандартна задача - търсене на шаблон в текст. Нека текстът е с големина $n$, а шаблонът с големина $m$. От сега нататък, основата на бройната система ще означаваме с base, а модулът с mod. Наивният алгоритъм за решаване на тази задача, със сложност $O(nm)$, работи по следния начин. Пробва всяка позиция в текста за срещането на шаблона, като проверката дали се среща е линейна по дължината на шаблон - в най-лошия случай $O(m)$. Тук идва място на хеширането за оптимизиране на проверката. В алгоритъма на Рабин-Карп, преди да почнем да обхождаме текста, ще изчислим хеша на шаблона. Да разгледаме точно как се променя изразът за намиране на хеша на подниз в текста при последователното обхождане на текста, чрез следното примерче:

Нека текстът е: $abcba$ и търсим шаблон с големина 3, т.е. $m=3$. Нека сме намерили хеша $num$ на първите три букви - $num=h(abc)$. Да видим как се променя тази стойност за хеша на вторите три букви в шаблона или по-точно колко е $h(bcb)$, използвайки намерения $h(abc)$. Лесно може да се види, като се разпише, че $h(bcb)$ $= (h(abcb)-h(a)*base^3) \space \% \space mod$ $=(h(abc)*base+h(b)-h(a)*base^m)$ $\% \space mod$ $=(num*base+h(b)-h(a)*base^m) \space \% \space mod$. Това следва от работата в бройната системат с основа base. Забелязва се общият модел на това как се променя последователно хеша на поднизовете с дължина $m$ в текста - ако на текущ подниз сме сметнали, че хеш-стойността е $num$, то за да получим новата хеш-стойност трябва да умножим по основата, да добавим новата буква отзад и да махнем излишната буква най-отпред. Така с последователното обхождане на текста, хешът се "плъзга" по поднизовете с дължина $m$. Затова се казва също, че този алгоритъм използва метода rolling hash. Ако се вгледаме подробно виждаме, че за смятането на хешовете едниствено ще ни трябва да знаем $base^m$. Вече можем да напишем точните стъпки на алгоритъма, след което следва и примерна реализация на езика C++:

  1. Определяме основа и модул за хеша.
  2. Намираме хеш-стойността на модела и едновременно с това $base^m$.
  3. Последователно намираме хеша на всички поднизове с дължина $m$ в текста, използвайки техниката rolling hash.

Алгоритъмът работи с линейна сложност по входа - $O(n+m)$. Една от подробностите по този код е, че основата и модулът са константи, за да е по-бърза работата с тях (те така или иначе не се променят). Друга подробност е, че там където трябва да вадим по модул, стандартно добавяме модула преди изваждането, за да не получим отрицателни числа (в случая добавяме $mod*mod$). Също много важна подробност е, че тук реализираме в някакъв смисъл "смело" алгоритъма, вярвайки напълно, че няма да получим колизии с хеша. На практика това няма как да е вярно. Затова по принцип като се реализира този алгоритъм, при съвпадение на хешовете се използва наивния начин, за да се провери дали наистина е намерен шаблона. Разбира се, за състезания това не се прави. Има начини да се подсигури липсата на колизии. Един такъв начин е да се използва повече от една основа и модул за хеширане, т.нар. двоен хеш, троен хеш, ... Същността на този начин е, че правим същото като преди само че няколко пъти (колкото основи и модули имаме). Минусът на това е, че се утежнява програмата, обикновено така се умножава времето по 2 или по 3 съответно. Математически може да се сметне, че при размери на низовете, каквито има по състезанията, при използване на троен хеш, вероятността да се получи колизия е по-малка, отколкото да се спечели тотото :) Тук също има различни начини, като може например да имаме само една основа и различни модули и т.н. (...)

Досега говорихме най-вече за хеширане на низове, което разбира се налага да вземаме предвид позицията на елементите на низа. Нека разглеждаме следната задача. Дадена ни са две редици от неотрицателни числа - $a$ с дължина $m$ и $b$ с дължина $n$. Трябва да преброим тези $m$-елементните подредици на $b$, които са същите като редицата $a$ или при разместване на числата се получава $a$. Например, ако $a=(1,2,3)$, а $b=(1,3,1,2)$, то имаме едно срещане от описания вид на $a$ във $b$, а именно: $(1,\textit{3,1,2})$. Задачата е много подобна като стандартната за търсене на шаблон в текст. Тук голямата разлика е, че всъщност освен конкретната редица $a$, броим за срещане във $b$ и всяка друга пермутация на $a$. Това означава, че не ни интересува редът на елементите във $a$ и можем да я гледаме като мултимножество, а не като редица. Така ако измислим удобен алгоритъм, с който да хешираме мултимножество, бихме могли да приложим отново алгоритъма на Рабин-Карп за решаване на задачата. Отново ще използваме предната идея - ще имаме основа на бройна система $p$ и модул $mod$. При хеширането на низове умножавахме кодовете на символите с основата, повдигната на степен спрямо позицията. Тук обаче ще постъпим малко по-различно. Когато срещнем число $t$ в мултимножеството, то към хеша ще прибавяме $p^t$. Ето един интерактивен пример за онагледяване на този вид хеширане:

Тук отново е желателно основата на бройната система, която подбираме да е просто число по-голямо от най-голямата кратност на число в мултимножеството. Специално за този пример с хеширането на числа е важно да се отбележи, че в някои задачи числата в редиците могат да бъдат много големи (до $10^9$ или $10^{18})$, но броят им няма как да е толкова голям. В такъв случай е добре първо да компресираме числата в двете редици и едва след това да прилагаме хеширането.