Crate cyclic_poly_23

source ·
Expand description

A recursive/rolling/decomposable hash using cyclic polynomials. This crate is an implementation of the algorithm given in Section 2.3 of the paper:

Jonathan D. Cohen, Recursive Hashing Functions for n-Grams, ACM Trans. Inf. Syst. 15 (3), 1997.

Most opensource implementations taken from the paper concentrate on the algorithms given in the later sections.

This algorithm is simple and, unlike some of the other algorithms given in the paper, supports block sizes > the size of the hash word, i.e. it is possible to hash arbitary data and not just n-Grams.

Another advantage of the algorithm is that the hash is decomposable as well as recursive/rolling.

§Recursive/Rolling

Is is possible to efficiently search for a block of data with a given hash value using rolling hash algorithms, such as Adler32 or Cyclic Polynomial hashing.

Given a hash, h1, of the bytes b[0..n], it is possible to efficiently calculate a second hash, h2, of the bytes b[1..(n+1)] from h1.

§Decomposable

Decomposable hash functions are useful for breaking up a large parent block with a known hash value and calculating the hash values of the smaller child blocks.

Given a hash, h1, of the bytes b[0..m], and a hash, h2, of the bytes b[0..n] where n < m, it is possible to efficiently calculate a hash, h3, of the bytes b[n..m] given h1 and h2.

Structs§

  • CyclicPoly
    A rolling hash function based on Cyclic Polynomials.

Type Aliases§