import base64
import pathlib
import struct
import sys
from collections import defaultdict
import zstandard
OUT_DIR = pathlib.Path(__file__).resolve().parent
ORACLE_DIR = OUT_DIR.parent.parent / "tests" / "vocab-oracle"
MAGIC = b"TKV1"
ZSTD_LEVEL = 19
DERIVED = {
"llama3": "cl100k_base",
"glm5": "glm4",
"p50k_base": "r50k_base",
}
def read_oracle(name: str) -> list[tuple[bytes, int]]:
raw = zstandard.ZstdDecompressor().decompress(
(ORACLE_DIR / f"{name}.tiktoken.zst").read_bytes(), max_output_size=64 << 20
)
out = []
for line in raw.split(b"\n"):
if not line:
continue
token, rank = line.rsplit(b" ", 1)
out.append((base64.b64decode(token), int(rank)))
return out
def varint(n: int) -> bytes:
out = bytearray()
while True:
byte = n & 0x7F
n >>= 7
if n:
out.append(byte | 0x80)
else:
out.append(byte)
return bytes(out)
def read_varint(buf: bytes, pos: int) -> tuple[int, int]:
n = shift = 0
while True:
byte = buf[pos]
pos += 1
n |= (byte & 0x7F) << shift
if not byte & 0x80:
return n, pos
shift += 7
def encode_frame(entries: list[tuple[bytes, int]]) -> bytes:
tokens = [t for t, _ in entries]
for i, (_, rank) in enumerate(entries):
if rank != entries[0][1] + i:
raise SystemExit(f"non-consecutive rank at index {i}: {rank}")
classes = defaultdict(list)
for token in tokens:
classes[len(token)].append(token)
body = b"".join(b"".join(classes[k]) for k in sorted(classes))
lengths = b"".join(varint(len(t)) for t in tokens)
header = MAGIC + struct.pack("<II", len(tokens), entries[0][1])
return zstandard.ZstdCompressor(level=ZSTD_LEVEL).compress(header + lengths + body)
def decode_frame(frame: bytes) -> list[tuple[bytes, int]]:
buf = zstandard.ZstdDecompressor().decompress(frame, max_output_size=64 << 20)
if buf[:4] != MAGIC:
raise SystemExit("bad magic")
n_tokens, rank0 = struct.unpack("<II", buf[4:12])
pos = 12
lengths = []
for _ in range(n_tokens):
length, pos = read_varint(buf, pos)
lengths.append(length)
counts = defaultdict(int)
for length in lengths:
counts[length] += 1
offsets, cursor = {}, pos
for length in sorted(counts):
offsets[length] = cursor
cursor += length * counts[length]
if cursor != len(buf):
raise SystemExit(f"body length mismatch: {cursor} != {len(buf)}")
out = []
for i, length in enumerate(lengths):
out.append((buf[offsets[length] : offsets[length] + length], rank0 + i))
offsets[length] += length
return out
def build(name: str) -> tuple[int, int]:
entries = read_oracle(name)
if name in DERIVED:
base = read_oracle(DERIVED[name])
if entries[: len(base)] != base:
raise SystemExit(f"{name} is not a rank-aligned extension of {DERIVED[name]}")
payload = entries[len(base) :]
else:
payload = entries
frame = encode_frame(payload)
if decode_frame(frame) != payload:
raise SystemExit(f"{name}: round-trip mismatch")
out = OUT_DIR / f"{name}.tkv.zst"
out.write_bytes(frame)
old = (ORACLE_DIR / f"{name}.tiktoken.zst").stat().st_size
print(
f"{name}: {len(entries)} tokens"
+ (f" ({len(payload)} beyond {DERIVED[name]})" if name in DERIVED else "")
+ f" -> {out.name} {len(frame)} bytes (was {old}, {100 * len(frame) / old - 100:+.0f}%)",
file=sys.stderr,
)
return old, len(frame)
if __name__ == "__main__":
names = sys.argv[1:] or sorted(p.name[: -len(".tiktoken.zst")] for p in ORACLE_DIR.glob("*.tiktoken.zst"))
total_old = total_new = 0
for n in names:
old, new = build(n)
total_old += old
total_new += new
print(
f"total: {total_old} -> {total_new} ({100 * total_new / total_old - 100:+.0f}%)",
file=sys.stderr,
)