hashrope

A BB[2/7] weight-balanced binary tree augmented with polynomial hash metadata at every node.

Zero dependencies. Pure Python. Python 3.10+.

What it does

hashrope is a rope data structure where every node carries a polynomial hash. This enables:

• O(k log w) concat and split with strict BB[2/7] rebalancing via Adams-style balanced join
• O(k log q) repetition encoding via RepeatNode -- represents "repeat this subtree q times" without materializing the data
• O(k log w) substring hashing without allocating new nodes
• O(1) whole-sequence hash at any point during streaming ingestion
• Bounded-memory sliding window that evicts old data while maintaining a running hash of everything seen

All arithmetic uses Mersenne prime modular reduction (bit-shift, no division).

Install

pip install hashrope

Quick start

from hashrope import PolynomialHash, Leaf, rope_concat, rope_split, rope_substr_hash, rope_hash

h = PolynomialHash()

# Build a rope
a = Leaf(b"hello ", h)
b = Leaf(b"world", h)
ab = rope_concat(a, b, h)

# Whole-string hash matches direct computation
assert rope_hash(ab) == h.hash(b"hello world")

# Split at any byte position
left, right = rope_split(ab, 6, h)

# Substring hash without allocation
sub_h = rope_substr_hash(ab, 0, 5, h)
assert sub_h == h.hash(b"hello")

RepeatNode

Encode repetitions in O(log q) time and O(1) space:

from hashrope import PolynomialHash, Leaf, rope_repeat, rope_hash

h = PolynomialHash()
pattern = Leaf(b"ab", h)
repeated = rope_repeat(pattern, 1000, h)  # "ab" x 1000

# Hash computed in O(log 1000), not O(2000)
assert rope_hash(repeated) == h.hash(b"ab" * 1000)

SlidingWindow

Bounded-memory streaming hash with copy-from-window support:

from hashrope import PolynomialHash, SlidingWindow

h = PolynomialHash()
sw = SlidingWindow(d_max=1024, m_max=256)

# Stream data in
sw.append_bytes(b"hello ")
sw.append_bytes(b"world")

# Hash of everything seen so far
assert sw.current_hash() == h.hash(b"hello world")

# Copy-from-window (like LZ77 back-references)
sw.append_copy(offset=5, length=5)  # copies "world" again
assert sw.final_hash() == h.hash(b"hello worldworld")

API reference

Polynomial hash

Rope nodes

Rope operations

SlidingWindow

Mathematical foundation

The data structure and its correctness proofs come from the compressed-domain hashing framework (24 theorems, 14 lemmas, 5 corollaries). Key results used by hashrope:

Changelog

See CHANGELOG.md for version history and details on the v0.2.1 balance bugfix.

Provenance

Extracted from UHC (Unified Hash-Compression Engine). The rope and polynomial hash modules are verbatim copies with import paths updated. The sliding window is adapted from UHC's SlidingRopeState with the LZ77 dependency removed.

License

MIT