From Turtle to HDT

01

Parse the Turtle

pyhdtkit.ttl.parse_ttl() — rdflib does the grammar

Turtle's conveniences — prefixes, shorthand, punctuation — exist for humans and carry no information HDT needs. rdflib expands all of it, and every term is flattened to one canonical string: IRIs lose their angle brackets, blank nodes become _:label, literals keep their N-Triples spelling. From here down, a triple is just three strings.

input · graph.ttl123 B

@prefix ex: <http://example.org/> .

ex:alice ex:knows ex:bob .
ex:alice ex:name "Alice"@en .
ex:bob   ex:knows ex:alice .

output · 3 triplesstrings

(http://example.org/alice,
 http://example.org/knows,
 http://example.org/bob)

(http://example.org/alice,
 http://example.org/name,
 "Alice"@en)

(http://example.org/bob,
 http://example.org/knows,
 http://example.org/alice)

02

Sort the terms into four sections

pyhdtkit.hdt.dictionary.build_four_section_dictionary()

HDT never stores a term twice. Every distinct string goes into a dictionary once and is replaced by a number. The reason there are four sections rather than three is overlap: a term used as both subject and object — very common in a graph, where one node points at another — would otherwise be stored twice. Those terms are pulled into a shared section and get one ID valid in both roles.

Predicates get their own ID space because a predicate never occupies a subject or object slot in the triples encoding — so sharing with them would save nothing.

the dictionary · sorted, IDs are 1-based rank4 sections

Section	Terms	IDs
`shared`	`http://example.org/alice` `http://example.org/bob`	1, 2
`subjects`	empty — every subject here is also an object	—
`predicates`	`http://example.org/knows` `http://example.org/name`	1, 2
`objects`	`"Alice"@en`	3

Sorting is the index. Terms are sorted bytewise and a term's ID is its position in that order. Nothing extra is stored to map strings to numbers — and that ordering is what makes the next layer's compression possible.

03

Replace every string with its ID

three strings per triple → three small integers

Object IDs continue past the shared section: IDs 1–2 are the shared terms, so the object-only term "Alice"@en is ID 3. The graph is now pure arithmetic, and the strings are not touched again until someone reads the file back.

before~120 B of text

alice   knows   bob
alice   name    "Alice"@en
bob     knows   alice

after · sorted SPO9 integers

1   1   2
1   2   3
2   1   1

04

Front-code the dictionary

pyhdtkit.hdt.dictionary.encode_pfc_section()

Sorted IRIs share long prefixes with their neighbours, and sorting has already put those neighbours next to each other. So each string records only how many leading bytes it borrows from the previous one, then its own tail. The first string in every block of 16 is written in full, which is what stops a reader having to decode from the beginning of the file.

shared section · string buffer48 B → 30 B

block start ─ http://example.org/alice\0
            └ [19] bob\0
                 ↑
                 borrow the first 19 bytes — "http://example.org/"
                 then store only the 3 that differ

on disk: 93 62 6f 62 00 · 0x93 = VByte(19) · 62 6f 62 = bob

Why the number looks wrong. HDT's VByte sets the high bit on the last byte of a value rather than on the continuation bytes — the reverse of most varint schemes. That is why 19 is written 0x93 and not 0x13.

05

Encode the triples as a tree

pyhdtkit.hdt.triples.encode_bitmap_triples()

Sorted SPO triples repeat constantly: a subject repeats for each of its predicates, a predicate for each of its objects. BitmapTriples stores each level once and spends a single bit marking where each group ends. Subject IDs are never written down at all — they are recovered by counting end-markers on the way through.

Reading it back: walk ArrayY left to right, taking objects from ArrayZ until BitmapZ says stop; when BitmapY says stop, move to the next subject. Subject 1 owns the first two columns because its BitmapY bit stays 0 until the second.

packed to bits · least-significant first4 bytes of payload

BitmapY  [0,1,1]  1 bit each   →  0x06   0000 0110
BitmapZ  [1,1,1]  1 bit each   →  0x07   0000 0111
ArrayY   [1,2,1]  2 bits each  →  0x19   00 01 10 01
ArrayZ   [2,3,1]  2 bits each  →  0x1e   00 01 11 10

the width per entry is stored in the file, not assumed — 2 bits here, because the largest ID is 3

06

Assemble the file

pyhdtkit.hdt.reader.write_hdt()

Four sections, each introduced by a control block that names its own format as a URI and carries its own checksum. A reader walks the file section by section without needing to know in advance what any of them contain.

At three triples HDT is bigger than the Turtle it came from — 123 bytes in, 376 out — because the format's fixed scaffolding has nothing to amortise against yet. The dictionary dominates for the same reason: the strings are the one thing that cannot be compressed away. Both ratios invert as a graph grows, since terms repeat and triples do not — a million triples land at about 8.4 bytes each.

the first 40 bytes · global control informationreal output

24 48 44 54 01 3c 68 74 74 70 3a 2f 2f 70 75 72 6c 2e 6f 72 67 2f 48 44 54 2f 68 64 74 23 48 44 54 76 31 3e 00 00 76 35
"$HDT"      Global  "<http://purl.org/HDT/hdt#HDTv1>\0"                                    none   CRC16

magic cookie section type format URI properties checksum

Three different checksums. Control blocks use CRC-16/ARC, section headers use CRC-8, and payloads use CRC-32C — none of them the CRC-32 in Python's standard library. Each was identified by testing candidate algorithms against a real HDT file until the computed value matched the bytes already stored there.

↑

Reading runs the same layers backwards

pyhdtkit.hdt.reader.read_hdt() → hdt2ttl()

Every layer above is reversible, and each verifies its checksum on the way through, so a truncated or corrupt file fails at the section that broke rather than returning plausible nonsense. Blank node labels are the one thing that does not survive a round trip — their names are arbitrary and scoped to a single file, so the graph returns equivalent rather than identical.

hdt2ttlthe inverse

bytes  →  verify CRCs, read each section's control block
       →  rebuild the dictionary from front-coded blocks
       →  walk BitmapY / BitmapZ back into (s, p, o) IDs
       →  swap IDs back for strings
       →  rdflib serializes Turtle