Хеширане

Hashing

Какво е хеш и какво е хеширане?
Защо ни трябва да ползваме хеширане?
Хешираща функция.
Какво е колизия? Начини за справяне с колизиите.
Rolling Hash.
Алгоритъм на Rabin-Karp.
Употреба в реалния живот.
Автор: Александър Георгиев

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

Съществуват, обаче, и определен брой задачи, в които не е толкова лесно да представим обектите като числа. Примери за такива задачи е когато зададените ни обекти са, например, string, vector, или друга по-сложна структура. В тази тема ще разгледаме как можем да представим и тях като "числа", ползвайки техника, наречена хеширане.

Какво е хеш?

?Hash на английски означава "каша, бъркотия", а като глагол - "нарязвам". Това в основен смисъл е начинът, по който се получават "псевдонимите" на входните обекти - те се нарязват и разбъркват по някакъв начин, и (малка част от) кашата, която се получи е така нареченият хеш. Важно е да се отбележи, че от "кашата" не може да се възстанови първоначалният обект - само се знае, че е получена от него.
Хеш (от английски hash), или хеш стойност, е удобен за нас "псевдоним" на някакъв сложен обект. По псевдонима обикновено не можем да възстановим целия обект, но все пак можем да извършваме някои по-прости операции - като например да видим дали два обекта (например стринга) са еднакви или не. Най-често хешът е число, но в някои случаи може да бъдат две или повече числа, или последователност от битове. По-общо, хешът е представяне на данни с произволен размер (един стринг може да има произволна дължина) чрез данни с фиксиран размер (размерът на int в байтове е фиксиран).

Основното изискване към хеша е да бъде:
  • Лесно сравним: обикновено ще ползваме хешовете за да търсим дубликати (повтарящи се елементи) между обектите, които те представят. Съответно най-често искаме да имат дефиниран operator==, който работи за O(1) време.
  • Компактен: когато хешът е малък по размер, той може да бъде местен с минимален разход на време. Допълнително, тъй като обикновено имаме голям брой обекти, на които даваме хеш стойност, а така и съответно голям брой хешове, ако те са малки по размер няма да заемат голямо количество памет.

Много е важно да забележите, че това представяне не е задължително уникално или еднозначно - хешът е просто псевдоним. Наистина, двама различни човека могат да имат един и същи псевдоним (например има поне няколко мутри с прякор "Картофа"). По-нататък в темата ще видим защо представянето не е еднозначно, дали това е проблем, и как да се справим с него.

Какво е хеширане?

?Един възможен начин да "хешираме" човек е да ползваме неговия пръстов отпечатък - нещо много по-малко от самия човек, но което го определя (почти) еднозначно. Затова понякога хешът се нарича digital fingerprint, или на български - дигитален пръстов отпечатък. Нарязването и ползването на ДНК-то е друг добър, но за съжаление не твърде приложим начин за хеширане на човек.
Хеширане (от английски hashing) е действието, при което асоциираме даден обект с хеш стойност. Тъй като самото хеширане много зависи от обектите, върху които го прилагаме, а също така и какви хеш стойности ще използваме (може да са един int, няколко int-а, последователност от битове, или нещо друго), това е по-скоро техника, отколкото алгоритъм.

Защо ни трябва да хешираме?

?За разлика от много други алгоритми и техники, които се ползват често в състезателното програмиране (например Динамично Оптимиране или Потоци), хеширането намира огромно приложение и в "реалния живот" - тоест в комерсиалното програмиране. Без него целият интернет и голям брой програми (включително операционната система) биха били значително по-бавни и несигурни, отколкото ги познаваме днес.
Нека сега разгледаме и защо, аджеба, би ни било полезно хеширането. Всъщност ще ни е доста лесно да покажем това с пример.

Нека имаме стринга "Elly". На него можем да съпоставим числото (хеша) 1164733561 (защо и как точно решихме да е това число ще разгледаме малко по-надолу). Допълнително имаме стринговете "Stancho" с хеш 1852008559 и "Ellen" с хеш 1819043182. Нека имаме масив с голям брой от тези стрингове и искаме да видим кой от тях се среща най-често. Ако ползваме самите стрингове, ще имаме много сравнения между "Elly" и "Elly", "Elly" и "Stancho", "Elly" и "Ellen", "Stancho" и "Stancho", "Stancho" и "Ellen", и "Ellen" и "Ellen". Докато при двойките "Elly" и "Stancho" и "Stancho" и "Ellen" бихме намерили разлика още на първата буква, при всички останали ще ни трябват по няколко сравнения докато намерим разлика или установим, че са един и същ стринг. Наистина, например при "Elly" и "Ellen" ще намерим разлика чак на четвъртата буква, а при "Stancho" и "Stancho" ще сравним всичките осем, за да установим, че е един и същ стринг.

От друга страна, ако сравнявахме техните хешове, щяхме да се нуждаем от точно едно сравнение, за да видим дали стринговете са различни или не.

Ако имахме същата задача, но със стринговете "aaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaab", и "aaaaaaaaaaaaaaaaaaac", разликата щеше да е още по-осезаема - решението с хешове ще е двадесет пъти по-бързо! Можете да видите, че ако максималната дължина на стринговете е O(N), решението с хешове ще е около N пъти по-бързо.

Хешираща функция

Окей, да приемем, че хеширането е полезно - как точно го правим? Как решихме, че хешът на "Elly" е 1164733561, а този на "Stancho" е 1852008559?

Реално, в зависимост от входните обекти (какво искаме да хешираме) ползваме различни хеширащи функции. Хешираща функция е функция, която приема като аргумент обект и връща неговия хеш. Логиката в тях е различна именно в зависимост какви са обектите. Например бихме ползвали различна логика ако хешираме стрингове и ако хешираме дати.
!Бройната система, в която представяме стринга, се нарича "база". Изискване за нея е да е по-голяма от най-голямата стойност, която кодираме. Тъй като в случая имаме ASCII символи, най-голямата стойност е 255, правейки 256 валидна база. Ако изискването за базата не е изпълнено хеш стойностите ще са "дефектни" - ще можем много лесно да направим два различни стринга с един и същ хеш.
Един прост начин да хешираме стрингове е да ги разглеждаме като числа в 256-тична бройна система (ако считаме, че стринговете се състоят само от ASCII символи, можем да ползваме техните ASCII кодове като "цифри" в тази система).

Така хеширащата функция би изглеждала по следния начин:
unsigned
simpleHash(
const
string
&
str) {
unsigned
ret
=
0
;
for
(
int
i
=
0
;
i
<
(
int
)str.size()
;
i
+
+
) { ret
=
ret
*
256u
+
(
unsigned
)str[i]
;
}
return
ret
;
}
?По-късно ще видим, че това не е особено добра хешираща функция за стрингове. По възможност ползвайте дадената по-долу версия с проста база и модул.
Ако забелязвате, при по-дълги имена променливата ret би overflow-нала, но това няма значение, тъй като крайният резултат ще е число от типа, който го искаме (unsigned int). Именно с тази функция сме кодирали и имената "Elly", "Stancho", и "Ellen" в по-горните примери.

Колизии

Нека разгледаме следния пример. Отнякъде сме взели информация за имената на всички хора по света (малко над седем милиарда, в момента на писане на тази статия), и техния ден на раждане във формат YYYY-MM-DD. Записали сме тази информация в един огромен файл, като на всеки ред е информацията за един от тези хора във формат "<собствено_име> <фамилия> <ден_на_раждане>". Например "Alexander Georgiev 1987-04-12".
?Задачата е еквивалентна на това да преброим колко неуникални реда има във файла.
Сега сме решили да преброим колко на брой "двойници" има по света: хора с едни и същи имена и ден на раждане. Не очакваме да има твърде много такива - като цяло не е твърде често срещано да видим двама човека с еднакви първо и последно име, или с еднаква дата на раждане, а с двете заедно става съвсем рядко. Но все пак такива хора има! Можем да предвидим, че едва ли повече от 1% от хората на земята си имат двойник (най-малкото заради датата на раждане), но нас ни интересува колко точно си имат такъв.

Можем да хешираме всеки ред (ползвайки функцията, която дадохме малко по-горе, или някоя друга, която да се справя със специалните знаци в имената), да заделим един голям масив с 232 клетки, и след всеки ред да увеличаваме клетката с индекс получения хеш с единица. Накрая всяка клетка със стойност по-голяма от едно ще означава, че в нея са попаднали двойници, тоест отговорът би бил сумата на всички клетки със стойност ≥ 2. Или поне би било така в един прекрасен свят.

Защо това не е така? Ако имаме седем милиарда души и от тях 1% си имат "двойник", то 6,930,000,000 биха били без двойник - тоест би трябвало да имат различни хешове. Но тъй като хешът ни е с лимит от само 232 == 4,294,967,296, то от принципа на чекмеджетата следва, че поне две от тях ще имат еднакъв хеш, въпреки, че са различни!

Случаи като горния, в които два различни обекта са асоциирани с една и съща хеш стойност се наричат колизия.
!Хеширане, при което не възникват колизии, се нарича перфектно (на английски perfect hashing). Това най-често се случва когато имаме директно представяне на обекта в число, и максималното резултатно число е относително малко. Например дата във формата YYYY-MM-DD може да се превърне в число YYYY * 13 * 32 + MM * 32 + DD, което да е достатъчно малко (малко над 4 милиона различни стойности) за да ползваме директно като хеш. Интересно свойство на перфектното хеширане е, че от хеша може да се възстанови оригиналния обект, стига да се знае хеширащата функция.
Колизии могат да се получат и не само когато тоталният брой възможни хеш стойности е по-малък от броя хеширани обекти. Например, ако в горния пример бяхме заделили масив с 10,000,000,000 клетки (което е с почти 50% по-голям от очаквания брой различни стойности) и хеш функцията ни връщаше стойности в интервала [0, 9,999,999,999], с голяма вероятност отново би се получила колизия! Това пък следва от небезизвестния birthday paradox. Наистина, нека вече сме обработили 6,000,000,000 от хората и ни остават още "само" 1,000,000,000. Ако хипотезата ни, че под 1% от хората си имат "двойници", бихме очаквали, че вече над 5,000,000,000 клетки (което е около половината от целия масив) биха имали стойност, различна от нула. Тъй като хеширащата функция връща относително произволна стойност, всеки от оставащите 1,000,000,000 човека ще има шанс от около 50% да попадне във вече запълнена клетка - независимо дали тя е запълнена от негов "двойник" или не!

Тук идва моментът да се запитаме дали хеширащата функция не е "счупена", след като за различни стойности връща еднакъв хеш, дори когато би могла да не връща (ако връща стойности в интервала [0, 9,999,999,999])? Оказва се, че не е - на практика е много трудно да се направи такава, освен ако хешираните обекти нямат някакви специфични свойства.

Справяне с колизии

!Тъй като хеширането рядко е перфектно, съответно не е еднозначно, то няма как тази трансформация да е двупосочна - тоест от обект да получавате хеш, и по хеша да можете да получите обратно обекта. Наистина, ако познаваме двама човека с прякор "картофа", то казвайки "Онзи ден срещнах картофа в центъра." няма как да знаем за кого от двамата става дума.
Ако не можем да направим перфектна хешираща функция (което в повечето случаи наистина не можем), единственият начин за връщане на 100% верен отговор е всеки път, когато получим еднакви хешове, да сравняваме истинските обекти по "бавния" начин. Това би ни гарантирало, че върнатият резултат е верен и би работило за задачи от реалния живот - и като цяло за задачи, където входът е относително произволен.

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

Единственото, което можем да направим за да избегнем това, е да не сравняваме оригиналните обекти по бавния начин, допускайки възможност да имаме колизия и да не я забележим (и, съответно, да върнем грешен резултат). За да работи това трябва да сведем шанса за колизия до пренебрежимо малък.

!Можем да ползваме два unsigned int-а вместо един unsigned long long, тъй като операции от типа на умножение и взимане на остатък са по-бързи при стандартния тип за процесора - в случая int.
Можем да направим това като увеличим максималната стойност на хешовете. Ако, например, хеширащата функция изчисляваше резултата в unsigned long long вместо в unsigned int, бихме имали много по-голямо "пространство", където да попадат стойностите, и, в следствие на това, значително по-малък шанс за колизия.

Двоен и троен хеш

Доразвиване на идеята за разширяване на пространството от стойности на хешовете би било да ползваме две или дори три числа като хеш (което се нарича, съответно, "двойно" и "тройно" хеширане).
?Шансът за колизия при троен хеш е по-малък от шанса лъч, идващ от космоса, да проникне в паметта и да промени бит там, като това да доведе до грешка.
Ако ползваме unsigned за всеки един от тях, бихме постигнали стойности до около 1018 за двойно и 1027 за тройно хеширане. Тройното хеширане дава достатъчно голямо хеш пространство за да не се получават колизии при повечето състезателни задачи.

Нека да се върнем на задачата с хората по света и "двойниците" им. Ако има 7,000,000,000 човека и ползваме троен хеш (тоест стойности до 1027), шансът за колизия е по-малък от 0.000003% - достатъчно малък за да считаме за пренебрежим. В състезателни задачи рядко хешираме повече от милион елемента, в който случай шансът за колизия при троен хеш би бил по-малък от 0.000000000000005%.

Разбира се, за да не са еднакви тези два или три хеша, трябва всеки от тях да е генериран с различна хешираща функция. В случая можем да променим единствено числото, по което умножаваме (базата на бройната система, в която представяме стринга). Да кажем първият хеш ще е с база 256 (както до сега), вторият с база 257, а третият - с база 258.

Стандартни методи за хеширане

Тук ще разгледаме няколко стандартни метода за хеширане на различни обекти, които често се ползват в състезанията.

Хеширане на числа

?Други възможности можете да видите тук.
Колкото и да е странно, може да има смисъл да хешираме и числа. Например, ако числата са много големи (примерно дълги числа), или поне достатъчно големи да не влизат в някакви разумни за нас граници (вижте темата за хештаблица), то би имало смисъл да ги хешираме.

Най-простият, а и най-често ползваният начин за това е като просто ги вземем по модул някакво число MOD:
unsigned
hash(
unsigned
num) {
return
num
%
MOD
;
}
Това е относително лесно за счупване, ако човекът, който създава тестовете, знае какъв модул сме си избрали. Така той може да вземе числата 1, MOD + 1, MOD * 2 + 1, ... и т.н., всички даващи остатък 1 (и, съответно, създаващи колизия).

Доналд Кнут предлага съвсем малко по-сложен вариант, който се държи по-добре (и е по-труден, но все пак далеч от невъзможен за счупване):
unsigned
hash(
unsigned
num) {
return
(
long
long
)num
*
(num
+
3
)
%
MOD
;
}
Забележете, че за да не овърфлоуне умножението е нужно да го cast-нем към по-голям тип.

Още малко по-усложнен вариант е да приложим няколко операции върху входното число, като например в следната функция (взета от тук):
unsigned
hash(
unsigned
num) { num
=
((num
>
>
16
)
^
num)
*
0x45d9f3b
;
num
=
((num
>
>
16
)
^
num)
*
0x45d9f3b
;
num
=
((num
>
>
16
)
^
num)
;
return
num
;
}

Хеширане на стрингове

По-горе вече показахме един вариант за хеширане на стрингове. Той обаче има няколко проблема:
  1. Първоначалната стойност на хеша (променливата ret) е нула. Това не е добре, тъй като ако символът със стойност 0 е валиден, произволно-дълга последователност от този символ ще има хеш 0 (независимо от базата). Например ако имаме азбуката {A-Z} и сме я сбили до числата в интервала [0, 25], стринговете "A" и "AA" ще имат хеш нула и ще предизвикат колизия. Едно от възможните решения на този проблем е да инициализираме началния хеш със стойност 1. Друг вариант е да не ползваме символ със стойност 0.
  2. Базата, която ползваме, е 256 - точно една четвърт от 32-битовото число, което ползваме за хеш. Така при всяка буква от петата нататък изхвърляме по една буква от хеша и добавяме нова. Отново е много лесно да се създаде колизия - например "Stancho" и "ncho" биха имали един и същ хеш, а както и {"aaaa", "aaaaa", "aaaaaa", ...}. Това може да се оправи като или променим базата (например я направим 257), или променим модула (да сложим наш модул, а не да ползваме overflow-а, който на практика е 232).
  3. Модулът, който ползваме, е 232. Има лесни за създаване, специфични тестове, на които ще има колизии независимо каква база изберем! Можем да ползваме избран от нас модул (за предпочитане просто число).
?Тъй като повечето символи, които обикновено се дават на вход, са с ASCII стойности под 127, то 127 почти винаги е по-добър избор на база от 257.
Във висшата алгебра е доказано, че се получават значително по-добри резултати когато базата и модулът са взаимно-прости. Един лесен начин да направим това е като вземем и двете да са прости числа. В следната имплементация (която е модификация на функцията от началото на темата) сме ползвали проста база, прост модул, и инициализация на хеша с 1.
const
int
BASE
=
257
;
const
int
MOD
=
1000000007
;
int
stringHash(
const
string
&
str) {
int
ret
=
1
;
for
(
int
i
=
0
;
i
<
(
int
)str.size()
;
i
+
+
) { ret
=
((
long
long
)ret
*
BASE
+
str[i])
%
MOD
;
}
return
ret
;
}
Забележете, че модулът е над четири пъти по-малък, отколкото беше преди. Въпреки това, така се предпазваме от лесни начини, по които биха могли да ни зададат вход, създаващ колизии.

А защо избрахме модулът да е 1,000,000,007 (просто число около 1,000,000,000), а не, примерно, 2,000,000,011 (просто число около 2,000,000,000)?

Често ще ни се налага не само да хешираме числата, ами и да извършваме някакви операции с тях (виж Rolling Hash и Rabin-Karp по-надолу).
!Научавайки наизуст простите числа 1,000,000,007 и 1,000,000,009 ни дава бърз начин за избор на подходящи модули за много задачи.
От една страна ще ни трябва да можем да изваждаме хешове (потенциално получавайки отрицателни временни стойности) - което не позволява да ползваме unsigned, а от друга ще ни се налага да събираме хешове (потенциално получавайки двойно по-големи от модула числа) - което не позволява да ползваме повече от 1,073,741,823.

?При двойно и тройно хеширане кастването и извършването на деление с long long може осезаемо да забавят програмата ви. Вместо това можете да смалите модулите до достатъчно малки числа за да извършвате всички операции в int.
За да не се налага да cast-ваме към long long можем да ползваме по-малък модул - например 7782067. Избрахме тази константа, защото ни трябва число, което умножено по базата да не overflow-ва типа. Тъй като типът е int, който поддържа до малко над 2,000,000,000, то взехме най-голямото просто число, което е по-малко от 2000000000 / 257. Това обаче значително намали възможните стойности на хеша (близо 128 пъти) - което предразполага за получаване на повече колизии (срещу едва 2-3 пъти подобрение на бързодействието). Ползвайте този трик само ако ви трябва наистина бързо хеширане - например ако имате малко на брой различни обекти, които се налага да хеширате много пъти, или пък когато ползвате двойно или тройно хеширане.

Последно, тъй като обикновено се налага да хеширате стрингове, съставени от някакво малко подмножество на ASCII (например само малките и главните латински букви), то може да намалим базата.
!Тук е особено важно да инициализираме началния хеш със стойност, различна от нула, тъй като в противен случай стринговете "A", "AA", "AAA", и т.н. ще имат еднакъв хеш.
Тъй като азбуката {'A'-'Z', 'a'-'z'} съдържа едва 52 символа, може да ползваме база 53, което от една страна ще ни позволи да ползваме по-голям модул (ако искаме да избегнем cast-ването към long long), а от друга вероятно ще доведе до по-добро запълване на хеш-пространството ни. За целта, обаче, трябва да "прекодираме" буквите от 'A' до 'Z' с числата от 0 до 25, а 'a' до 'z' - с тези от 26 до 51. Това става с лесна модификация:
const
int
BASE
=
53
;
const
int
MOD
=
37735849
;
int
stringHash(
const
string
&
str) {
int
ret
=
1
;
for
(
int
i
=
0
;
i
<
(
int
)str.size()
;
i
+
+
) {
int
charCode
=
str[i]
<
=
'Z'
?
str[i]
-
'A'
:
str[i]
-
'a'
+
26
;
ret
=
(ret
*
BASE
+
charCode)
%
MOD
;
}
return
ret
;
}
По подобен начин можем да се справим ако имаме и други допълнителни символи - например цифри, шпации, запетайки и т.н.

Хеширане на произволни обекти

!Тук е важно да вземем байтовете на самите данни, а не на указателите към тях! Например ако имаме char* или int[] то трябва да вземем байтовете на всеки един елемент от тях, а не на "самия масив" (който реално е само указател).
Хеширането на произволни обекти не е особено по-различно. Данните на всеки от тях можем да представим като последователност от байтове и да хешираме тях - ползвайки, например, алгоритъма за стрингове. В действителност, ако има дефиниран operator == трябва да хешираме само данните, които се ползват там. Един сложен, но хубав начин за хеширане на произволни обекти, е алгоритъмът за хеширане MD5, разработен от единия от авторите на книгата Introduction to Algorithms.

Overflow вместо модул

?Всъщност и ние ползвахме това в първия пример в темата, като казахме, че това не е хубава имплементация на хеширане на стринг. Тук ще покажем още една причина защо.
Много състезатели ползват unsigned int или unsigned long long за хеш като ползват overflow-а на числото вместо модул. Това реално е еквивалентно на това да ползваме модул, съответно, 232 и 264. Ако изберем за база просто число (различно от 2), то базата и модулът ще са взаимно-прости което, поне на теория, трябва да работи добре. Макар и неколкократно по-ефективно откъм скорост, а също така и ползващо изцяло пространството на типа, това не винаги е добра идея - особено на състезания!

Причината е, че преди няколко месеца едни руснаци постнаха много интересен блог-пост за това как може да се счупи тройно, че дори и по-голямо хеширане с произволни бази, стига те да ползват за модул 232 или 264 (и, всъщност, две на която и да е степен по-малка или равна на 64). При това за целта те ползват фиксиран стринг, съставен от едва два различни символа! Въпросният стринг е от вида:
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBA...
който се образува като многократно приложим S = S + ~S, където ~S означава всяко 'A' в S е заменено с 'B' и обратно, започвайки с S = "A". Реално първите няколко стъпки са:
    ?Задачка, свързана с дадената редица, е CodeZeroOne.
  1. S = "A";
  2. S = "A" + "B";
  3. S = "AB" + "BA";
  4. S = "ABBA" + "BAAB";
  5. S = "ABBABAAB" + "BAABABBA";
Друг начин да генерираме същото нещо е ползвайки следното парче код:
char
S[N]
;
for
(
int
i
=
0
;
i
<
N
;
i
+
+
) { S[i]
=
'A'
+
__builtin_popcount(i)
%
2
;
}
За обяснение защо това се случва, прочетете целия блог пост: http://codeforces.com/blog/entry/4898.

Rolling Hash

Често в състезателни задачи трикът е не само да ползваме хешове, ами и да можем да ги генерираме бързо. Досега намирането на стринг с дължина L ставаше за O(L). Можем да се възползваме от факта, че обикновено генерираме хешовете на събстрингове на даден по-голям стринг и да забързаме тази процедура до O(1).

Примерна задача

Представете си следната задача:
Даден ви е стринг S с дължина N, съставен от главни латински букви. Да се намери най-дългият му substring, който се среща поне K пъти. Разрешено е срещанията да се застъпват. Ограниченията са 1 ≤ K ≤ N ≤ 100,000; 'A' ≤ Si ≤ 'Z'.

Например за "ABRACADABRABE" и K = 2, този събстринг е "ABRA". Ако K беше 3, той би бил "AB".
Тук най-тъпото решение би било да вземем всеки възможен substring и да преброим колко пъти се среща той в целия входен стринг. Тъй като сравнението на два стринга с дължина L е O(L), а има O(N2) възможни събстринга, цялото решение би било със сложност O(N4) (сравняваме всеки възможен събстринг с всеки друг).
?Задачата има относително просто O(N3) по време и O(N2) по памет решение без хеширане. Сещате ли се какво?

Като подсказка, за всеки индекс i трябва да преброите колко са еднаквите събстрингове на тези с дължина 1, 2, ..., N започващи от този индекс.
Можем да се сетим, че ако имаме отговор с дължина A, то със сигурност ще имаме и отговор с дължина A-1. Аналогично, ако нямаме отговор с дължина A, то със сигурност няма да имаме и с дължина A+1. Това ни позволява да направим двоично търсене по дължината на събстринга, сваляйки сложността на най-тривиалното решение до O(logN∙N∙N∙N).

Следващото наблюдение, което трябва да направим, е че само сравняваме дали двойки стрингове са еднакви. При това го правим за O(N)! Тук като че ли е много удачно да ползваме хеширане.

Един вариант е да преизчислим хешовете на събстринговете между всяка двойка индекси i и j. Така вече сравнението ще става за O(1), а прекалкулацията ще е за O(N2). Имайки предвид, че все пак трябва да фиксираме дължината (O(logN)), да обходим всяко начало, където би могъл да започва търсеният събстринг (O(N)), и да преброим на колко други места се среща (O(N)), постигнахме решение със сложност О(N2 + logN∙N∙N), демек O(logN∙N∙N). Ползвайки хеширане в най-простия му вариант намалихме сложността с фактор от N!

Ако сме малко по-хитри ще забележим, че можем да премахнем още O(N) от втората част, като просто намерим хешовете на стринговете с фиксираната дължина, започващи от всяка позиция и преброим кой колко пъти се среща ползвайки map. Ако има такъв, който се среща повече от K пъти, значи с дадената дължина имаме отговор. Това решение е O(N∙N + logN∙N). И макар да направихме втората част доста бърза, сега самото преизчисляване на хешовете стана bottle neck - тя е O(N2). При дадените ограничения това все още не е окей.

Rolling hash

За да решим проблема ще ползваме нещо, наречено плъзгащ се хеш (на английски rolling hash). Основната идея е, че ако имаме някакъв събстринг с дължина L и искаме да намерим хеша на събстринг със същата дължина, започващ една позиция надясно от текущия, можем да направим това много бързо. Например ако имаме хеша на "CADAB" и търсим този на "ADABR" в стринга "ABRACADABRA" (ABRACADABRA -> ABRACADABRA), можем да направим следното:

Нека h1 е хешът на "CADAB". От него можем да премахнем първата буква като направим h2 = h1 - 'C' * pow(BASE, 4). Това е така, тъй като при хеширането всеки път като сме добавяли буква след началното 'C' сме умножавали хеша по BASE.
!Забележете, че всички тези операции трябва да извършваме по модул MOD. При изваждането (h1 - 'C' * pow(BASE, 4)) може да се получи отрицателна стойност. Това не е хубаво, но пък можем лесно да се справим с проблема, като добавим MOD към резултата ако той стане отрицателен.
Тъй като имаме четири букви след 'C', то явно сме го умножили по BASE4. Ако го извадим ще останем само с хеша за "ADAB". След това можем да умножим хеша на "ADAB" по BASE и да добавим следващата буква (в случая 'R'), получавайки хеша на "ADABR". Забележете, че единствената неконстантна операция беше pow(BASE, 4). Но тъй като дължината е фиксирана тази стойност можем да изчислим само веднъж и да я ползваме за плъзгането на хеша по целия стринг.

Така кодът, който ще имаме за плъзгащия хеш, е нещо от сорта на:
// Фиксирали сме дължината len с двоичното.
int
rollingHash(
const
string
&
s
,
int
len) {
// Намираме хеша на първия събстринг (с дължина len)
int
hash
=
0
;
for
(
int
i
=
0
;
i
<
len
;
i
+
+
) hash
=
(hash
*
BASE
+
s[i])
%
MOD
;
// Тук ще пазим кой хеш колко пъти сме срещали
map
<
int
,
int
>
cnt
;
cnt[hash]
+
+
;
// Изчисляваме веднъж колко е BASE^(len - 1);
int
basePow
=
1
;
for
(
int
i
=
0
;
i
<
len
-
1
;
i
+
+
) basePow
=
(basePow
*
BASE)
%
MOD
;
// Обхождаме остатъка от стринга с rolling hash
for
(
int
i
=
len
;
i
<
(
int
)s.size()
;
i
+
+
) {
// Махаме първата буква
hash
=
hash
-
(s[i
-
len]
*
basePow)
%
MOD
;
if
(hash
<
0
) hash
+
=
MOD
;
// Добавяме новата буква
hash
=
(hash
*
BASE
+
s[i])
%
MOD
;
// "Преброяваме" новия събстринг в map-а
cnt[hash]
+
+
;
// Ако това е K-тото срещане на този събстринг, връщаме true
if
(cnt[hash]
>
=
K)
return
true
;
}
// Не сме намерили събстринг, който да се среща K или повече пъти.
return
false
;
}
?Разбира се, при имплементацията на тази задача бихме ползвали двоен или троен хеш за да се справим с колизиите, но промяната не е голяма.
Самият rolling hash е линеен, но тъй като ползваме map тази функция е със сложност O(N∙logN). Като имаме предвид, че я викаме логаритъм на брой пъти (заради двоичното), така цялото решение е със сложност O(logN∙N∙logN) - значително по-добре от началното O(N4)! В (тясно-свързаната с тази) тема за хештаблица ще видим как можем да свалим тази сложност до O(logN∙N), правейки map-ът да работи със сложност O(1) вместо O(logN).

Алгоритъм на Rabin-Karp

При Rolling Hash сме леко ограничени от това, че можем да намерим константно само:
  • Хеша на стрингове с еднаква дължина.
  • Хеша на почти изцяло припокриващи се стрингове.
Майкъл Рабин и Ричард Карп предлагат интересно надграждане над плъзгащите се хешове, което решава и двата проблема и позволява намирането на хеша на произволен събстринг за O(1). За целта, обаче, е нужна O(N) допълнителна памет и O(N) по време преизчисление. Това надграждане се нарича алгоритъм на Рабин-Карп (макар и да е по-скоро структура данни, отколкото алгоритъм).

Идеята е да направим масив с хешовете на всеки префикс на входния стринг - тоест с хеша на първата буква, на първите две букви, на първите три букви и т.н. Ако входният стринг е "ABRACADABRA" бихме имали хешовете на {"A", "AB", "ABR", "ABRA", "ABRAC", ..., "ABRACADABRA"}. Нека запишем тези хешове в масив prefixHash[], като на i-та позиция е хешът на префикса от стринга до позиция i включително.

Допълнително ни трябва втори масив, в който сме записали всички степени на базата по модул - тоест basePow[], където basePow[0] = 1;, basePow[1] = BASE % MOD;, basePow[2] = (BASE * BASE) % MOD; и т.н.

Тези преизчисления можем да направим със следния код (тук и в остатъка от примера ще считаме, че BASE * MOD * 2 ≤ 2,000,000,000):
int
basePow[MAX]
;
int
prefixHash[MAX]
;
void
rabinKarpPrecalc(
const
string
&
s) { basePow[
0
]
=
1
;
for
(
int
i
=
1
;
i
<
(
int
)s.size()
;
i
+
+
) basePow[i]
=
(basePow[i
-
1
]
*
BASE)
%
MOD
;
prefixHash[
0
]
=
s[
0
]
;
for
(
int
i
=
1
;
i
<
(
int
)s.size()
;
i
+
+
) prefixHash[i]
=
(prefixHash[i
-
1
]
*
BASE
+
s[i])
%
MOD
;
}

След като имаме тези масиви, когато ни поискат хеша на събстринга, започващ в индекс left и завършващ в индекс right:
  1. Взимаме хеша на префикса до right, включително;
  2. От него изваждаме хеша на префикса до left - 1, включително, умножен по BASE на степен дължината на събстринга, чиито хеш търсим.
Ползвайки двата преизчислени масива, всяка от тези две стъпки става за O(1).

Реално което правим може би ще се види по-лесно с пример. Нека имаме низа "ABRACADABRA" и искаме да намерим хеша на подниза от индекс 4 до индекс 6, включително (тоест "CAD").
  1. Взимаме хеша на "ABRACAD";
  2. Взимаме хеша на "ABRA";
  3. Умножаваме втория хеш по базата на степен дължината на събстринга, който търсим (в случая 3). Получаваме хеша на "ABRA___" (където с '_' сме отбелязали "празен" символ).
  4. От хеша на "ABRACAD" изваждаме хеша на "ABRA___" и получаваме хеша на "CAD".

Откъм код (ползвайки двата вече преизчислени масива) това би изглеждало нещо от сорта на:
int
getSubstringHash(
int
left
,
int
right) {
int
h1
=
prefixHash[right]
;
int
h2
=
left
>
0
?
prefixHash[left
-
1
]
:
0
;
h2
=
((
long
long
)h2
*
basePow[right
-
left
+
1
])
%
MOD
;
return
(h1
-
h2
+
MOD)
%
MOD
;
}
Тук кастваме към long long, защото макар и MOD * BASE да не овърфлоува, стойностите в basePow[] са също с размер до MOD. Така при тази операция имаме MOD * MOD, което вече най-вероятно ще овърфлоува.

Употреба в реалния живот

Хеширането намира разноорбазни употреби в реалния живот. Някои от тях сме споменали тук.

Пазене на пароли

Голяма част от сайтовете, които изискват парола, не пазят самата парола на сървърите си, а само нейн хеш. Всеки път, когато се log-вате на сайта, въведената от вас парола се хешира и се изпраща на сайта, а там хешът се сравнява със запазения при регистрацията хеш.
?Признайте си, че ползвате или сте ползвали една и съща парола за поне няколко различни сайта.
Така дори някой да се добере до вашата парола на сайта, той няма да има лесен начин да разбере каква е самата парола и да пробва да влезе с вашето потребителско име и паролата в друг сайт. Например, бихте ли познали, че "0d861189ea06014cd6d272a181682e54" e "informatika.bg"? (Тук сме ползвали един от най-разпространените стандартни хешове: md5.)

Верификация на файлове

?Това е познато като чексума (от английски, checksum).
Когато теглите изпълним файл (например .exe) от даден сайт, понякога фирмата производител предоставя за него хеш, с който можете да проверите, че файлът не е променян (примерно не е заразен с вирус). Така теглите файла, намирате неговия очакван хеш от производителя, хеширате изтегления файл и сравнявате хешовете. Ако те са еднакви, значи файлът не е променян (и е окей за ползване). Ако не са еднакви, значи или е имало проблем при тегленето, или файлът е инфектиран с нещо.

Internet Cache

Когато отваряте някой сайт, има голям шанс част от него да не бъде променян от последното му зареждане. Най-често това са картинки и бутони, flash картинки/игрички и други. Тези файлове, които са малко вероятно да бъдат променени, биват кеширани на друго ниво - например на някой сървър по пътя от вашия компютър до сайта, или дори на вашия компютър. Когато отваряте страница за първи път, цялото нейно статично (непроменливо) съдържание се сваля на компютъра ви, включително картинките, ако има такива. Следващият път, когато отворите сайта (и кешът на компютъра ви не се е изтрил), картинките, например, няма да бъдат свалени наново от сървъра (и да обиколят половината свят за да стигнат до вас), а ще бъдат показани вече свалените такива! Реално компютърът ви знае, че ги има свалени, като пази хеш на техния адрес.

Bloom Filters

Друга честа употреба на хеширането са така наречените Bloom Filters (повече информация за тях тук). Те се ползват за бърза проверка дали даден обект не принадлежи на дадено множество. Например ако имаме огромна база данни (или огромен файл с някаква информация) и търсим в него даден обект, това би могло да бъде много бавно - особено ако обектът го няма и се наложи да обходим всичките данни. Блуум филтърът представлява комбинация на хешовете на всички обекти в базата данни (или файла), която ни позволява (хеширайки обекта, който търсим) да проверим дали него със сигурност го няма там - в който случай не би се наложило изобщо да го търсим. Ако пък блуум филътърт каже, че е възможно да го има, ще трябва да направим отново стандартното (бавно) търсене. Забележете, че е възможно отново да сме обходили всички данни и да не го намерим - това би се случило ако сме имали колизия в блуум филтъра.

Много прост пример за блуум филтър е да хешираме обектите и да правим побитово "или" на техните хешове в една променлива. Нека създадем такъв блуум филтър за имената "Elly", "Stancho", и "Ellen", ползвайки най-простата хешираща функция (дадена в началото на темата):
String Hash Hash (as bits)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Elly
1164733561
01000101011011000110110001111001
Stancho
1852008559
01101110011000110110100001101111
Ellen
1819043182
01101100011011000110010101101110
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
Bloom
1869573503
01101111011011110110110101111111
Тествайки името "Kriss" с хеш 1919513459 и битова репрезентация 01110010011010010111001101110011 бихме казали (правилно) че не е сред имената, тъй като има 1-ца на трета позиция (индексирано от 0), докато блуум филтърът, и съответно никое от имената в него, няма 1-ца на тази позиция.
От друга страна името "Didi" с хеш 1147757673 и битова репрезентация 01000100011010010110010001101001 би минало блуум филтъра и въпреки всичко не присъства сред оригиналните имена. Затова отново наблягаме, че блуум филтрите само могат да ни кажат кога един елемент със сигурност не е в дадено множество (няма false negatives) но може да "излъже" ако каже, че е (може да има false positives).

Може би забелязвате, че при блуум филтрите имаме много по-голям шанс за колизия, отколкото при хеш таблица. Това е така, тъй като всичките хешове са наблъскани в много малко пространство - което е именно и предимството им. При стандартна хеш таблица бихме ползвали поне O(N) памет. Блуум филтрите ни позволяват да смалим тази памет до произволно малко число (например O(logN)), което е практично ако примерно правим алгоритъм за устройство с ограничени ресурси - да кажем GSM.

Задачи за тренировка

Примерни задачки, които се решават с хешове:
  • Sequence Members: За да е достатъчно ефективно решението ни трябва да нямаме колизии при броенето. За да стане това трябва първо да намерим перфектен хеш за специалните числа, и чак после да генерираме другите.

  • Chelly

    PrAnKA 2010

    Author: Alexander Georgiev
    Tags: Medium, Rolling Hash, Hashmap
    Statement | Archive | Online Judge
    Chelly: Можем да хешираме входните думи, да сортираме хешовете им и после за всеки начален индекс в текста и всяка дължина да намерим хеша на дадения substring и да го потърсим с двоично търсене във входните думи. Алтернативно, можем да ползваме хеш таблица.
  • Gattaca: Относително сложна задачка, подобна на примера за Rolling Hash (леко по-сложен вариант).
  • Davy Jones's Organ: Трябва първо да намерите къде е "центърът" на палиндрома (ако единият стринг е с дължина N, а другият с M, то "центърът" е с дължина max(N, M) - min(N, M) и се намира в по-дългата дума). След това задачата се свежда до прилагане на Rolling Hash (или Рабин-Карп) в права и обратна посока.
  • Cipher Message 2: Трябва да правите "плъзгащ се прозорец" с дължина K по стринга, като при всяко местене изхвърляте всички събстрингове, започващи в премахнатата буква и добавяте всички, завършващи в новата. Думите от прозореца пазите в хеш таблица.

Допълнителни материали

  1. Хештаблица (www.informatika.bg)
  2. Hash Function (en.wikipedia.org)
  3. MD5 message-digest algorithm (en.wikipedia.org)
  4. Birthday Paradox (en.wikipedia.org)
  5. Hash Functions (www.cs.hmc.edu)
  6. Good hash functions for integers (www.stackoverflow.com)
  7. Anti-hash test (www.codeforces.com)


За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
предишна тема
версия за печат
следваща тема
Страницата е посетена 16152 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: