Kružni heš

Kružni heš je heš funkcija kod koje se ulaz obrađuje pomoću prozora koji sekvencijalno prolazi kroz podatke. Postoji nekoliko heš funkcija koje omogućavaju da se kružni heš izračuna veoma brzo - nova heš vrednost se brzo računa uz pomoć prethodno izračunate a zatim se stara vrednost u prozoru zamenjuje novom. Mnogi algoritmi koriste kružni heš a jedna od glavnih primena kružnog heša je Rabin-Karp algoritam za pretragu koji koristi funkciju opisanu ispod. Još jedna od popularnih primena je rsync program koji kao svoj kružni heš koristi algoritam za kontrolu prenosa zasnovan na Adlerovom algoritmu. U najboljem slučaju, kružna heš funkcija je parno nezavisna ili garantuje mali broj kolizija. Na primer, kružni heš ne može biti trostruko nezavisan.

Rabin-Karp kružni heš

Rabin-Karp algoritam za pretragu stringova se obično koristi uz pomoć jednostavne kružne heš funkcije koja koristi samo množenje i sabiranje: H = c₁a^k-1 + c₂a^k-2 + c₃a^k-3 + ... + c_ka⁰ pri čemu je a konstanta, a c₁, ..., c_k ulazni karakteri. Kako bi se izbeglo rukovanje ogromnim vrednostima H, sva matematika se vrši po modulu n. Izbor a i n je ključan da bi se obavilo dobro heširanje. Izbacivanje i dodavanje novih karaktera jednostavno uključuje izbacivanje ili dodavanje prvog ili poslednjeg terma. Šiftovanje svih karaktera za jedno mesto u levo podrazumeva množenje cele sume H sa a. U aritmetici po modulu, a može biti izabrano tako da ima multiplikativni inverz a^-1 koji množenjem sa H zapravo vrši deljenje.

Sečenje zasnovano na sadržaju koristeći Rabin-Karp heš

Jedna od interesantnih primena kružnog heša je stvaranje dinamičkih delova ulaznih podataka ili fajla, orijentisanih ka sadržaju. Ovo je pogotovo korisno kada je potrebno poslati samo promenjene delove velikog fajla i jednostavno smeštanje dodatnog bajta ispred početka fajla bi uzrokovalo da se npr. sve fiksirane veličine prozora podese, a zapravo je samo prvi deo podataka modifikovan.

Najjednostavniji pristup izračunavanju dinamičkih delova je upotrebiti kružni heš i ako se pojavi šablon (npr. nižih N bitova su nule) to je onda granica jednog dela. Ovaj pristup obezbeđuje da bilo kakve promene u fajlu utiču na tekući i eventualno na sledeći deo podataka, ali ni na šta više. Kada su granice poznate, delovi se upoređuju po svojim heš vrednostima da bi se utvrdilo koji je deo modifikovan i potrebno ga je ponovo slati.

Softver

• Java kružni heš Apače licencirana Java implemetacija funkcija kružnog heširanja
• Ngram heširanje C++ implementacija nekoliko funkcija kružnog heširanja

Spoljašnje veze

• Predavanja MIT Mit 6.006: Uvod u algoritme 2011 - Beleške sa predavanja - Kružni heš