Räsifunktsioon: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Resümee puudub |
Resümee puudub |
||
55. rida:
Selle meetodi üks variatsioonidest on Fibonacci arvu räsimine, mis põhineb kuldlõige omadustel. <math>A</math> arvuna võetakse lähedasemat <math>\varphi^{-1}*w</math> arvule algarvu, mis on vastastikult harilik <math>w</math>-ga.
=== Muutliku suurusega ridade räsimine ===
Üleval mainitud meetodid on kasutatavad ka sel juhul, kui me peame tegelema võtmetega, mis koosnevad mitmetest sõnadest, või muutliku suurusega võtmetega. Näiteks võib kombineerida sõnad ühte <math>w</math> mooduliga liitmise või "välistav või" operatsiooni abil. Üks algoritmitest, mis töötab sel põhimõttel, on Pearsoni räsifunktsioon.
{{Pearsoni räsimine||en|Pearson hashing}} on Peter Pearsoni pakutud algoritm 8-bitiste registritega protsessorite jaoks, mille ülesandeks on suvalise suurusega rea jaoks räsikoodi kiire arvutus. Sisendile funktsioon saab sõna <math>W</math>, mis koosneb <math>n</math> sümbolitest, igaüks 1 baiti suurusega, ning tagastab tähenduse diapasoonis nullist kuni 255-ni. Seejuures räsikoodi tähendus sõltub sisendsõna iga sümbolist.
Algoritmi saab kirjeldada järgmise pseudokoodiga, mis saab sisendile rida <math>W</math> ning kasutab vaheste tabeli <math>T</math>
<code lang="pseudo">
h := 0
'''for each''' c '''in''' W '''loop'''
index := h '''xor''' c
h := T[index]
'''end loop'''
'''return''' h
</code>
Algoritmi eeliste hulgas tasub märkida:
* Arvutuse lihtsust;
* Pole olemas selliseid sisendandmeid, mille jaoks kollisiooni tõenäosus on suurim;
* Võimalikkus modifitseerida ideaalseks räsifunktsiooniks.
Võtmete <math>K</math>, mis koosnevad <math>l</math> sümbolitest (<math>K=x_{1}x_{2}...x_{l}</math>), räsimise alternatiivse viisina võib välja pakkuda arvutust
: <math>h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l})) \mod M</math>.
=== Ideaalne räsimine ===
Ideaalseks räsifunktsiooniks ({{lang-en|Perfect hash function}}) nimetatakse sellist funktsiooni, mis kujutab iga võtme <math>S</math> komplektist täisarvude hulka ilma kollisioonideta. Matemaatilistes terminites see on injektiivne kujutis.
==== Kirjeldus ====
# Funktsiooni <math>h(k)\colon U\to [m]</math> nimetatakse ideaalseks räsifunktsiooniks <math>S\subseteq U</math> jaoks, kui ta on injektiivne <math>S</math> jaoks;
# Funktsiooni <math>h(k)\colon U\to [m]</math> nimetatakse minimaalseks ideaalseks räsifunktsiooniks <math>S\subseteq U</math> jaoks, kui ta on ideaalne räsifunktsioon ning <math>m = n = |S|</math>;
# <math>k\ge 1</math>, mis on täisarv, jaoks funktsiooni <math>h(k)\colon U\to [m]</math> nimetatakse <math>k</math>-ideaalseks räsifunktsiooniks (k-PHF) <math>S\subseteq U</math> jaoks, kui iga <math>j\in [m]</math> jaoks meil on <math>|\{x\in S | h(x) = j\}|\le k</math>.
Ideaalset räsimist kasutatakse nendel juhustel, kui me tahame omistada unikaalset identifikaatori võtmele, säilitamata mingitki infot võtme kohta. Üheks kõige ilmselgemaks ideaalse (võib pigem k-ideaalse) räsimise kasutamise näiteks on olukord, kui meil on käsutusel väike kiire mälu, kuhu me paneme selliste räsi võtmete tähendusi, mis on seotud suures, aga aeglases mälus säilitatavate andmetega. Seejuures ploki suurust võib valida selliseks, et vajatavad andmed, mis säilivad aeglases mälus, võivad olla saadud ühe päringuga. Sellist lähenemist kasutatakse, näiteks, aparaatruuterites. Samuti ideaalset räsimist kasutatakse algoritmide töö graafidel kiirendamiseks, neil juhustel, kui graafi kujundus ei mahu põhimälus.
=== Universaalne räsimine ===
{{|Universaalne räsimine|Universaalseks räsimiseks|en|Universal hashing}} nimetatakse räsimist, mille puhul kasutatakse mitte üht konkreetset räsifunktsiooni, vaid toimub valik antud parvest juhusliku algoritmi järgi. Universaalse räsimise kasutamine tavaliselt tagab väikest kollisioonide arvu. Universaalset räsimist kasutatakse mitmel viisil, näiteks, räsitabelite realiseerimises ning krüptograafias.
==== Kirjeldus ====
Oletame, et me tahame kujutada võtmed ruumist <math>U</math> arvudesse <math>[m]</math>. Sisendile algoritm saab teatud andmete hulka <math>S\in U</math> suurusega <math>n</math>, kusjuures ta on teadmata ebaselge. Reeglina räsimise eesmärgiks on kollisioonide minimaalse arvu saamine, mida on raske saavutada, kasutades mingit teatud räsifunktsiooni.
Sellise probleemi lahendusena võib valida funktsiooni juhuslikul viisil teatud hulgast (kogusest), mida nimetatakse universaalseks parveks <math>H = \{ h : U \to [m] \}</math>.
| |||