Hugging Face's logo

Spaces:
AEUPH
/
DMCRA-LAB
Running

App Files Community
DMCRA-LAB / bpe.js
AEUPH's picture
AEUPH
DMCRA Lab: elastic level-set quantisation over real GGUF weights, measured end to end
de22210 verified
Raw History Blame Contribute Delete
13.7 kB
/* Exact byte-level BPE for the HDC engine — browser-native, no dependencies.
*
* Why this file exists: the page used to tokenise by greedy longest match over the decoded
* vocabulary, which is NOT the model's tokenisation. Its own comment said so ("this is NOT the
* model's exact BPE merge process"). It does not have to be an approximation: a GPT-2-family GGUF
* carries the whole merge table in its header — Qwen2.5-0.5B carries all 151,387 merges and all
* 151,936 tokens, untruncated — and a merge table plus a rank is sufficient to reproduce the exact
* merge sequence. So this module reproduces it.
*
* Algorithm (the same order HF's GPT2Tokenizer and llama.cpp use):
* 1. bytes of the input text -> the byte-level alphabet (printable bytes map to themselves, the
* other 68 map to U+0100 + n, which is GPT-2's bytes_to_unicode table),
* 2. split with the model's pre-tokeniser regex (`tokenizer.ggml.pre`, "qwen2" here),
* 3. inside each pre-token, repeatedly merge the adjacent pair with the lowest merge rank until
* no merge applies,
* 4. map each surviving piece back through the alphabet to its surface string, and look it up in
* the vocabulary for its id.
*
* SURFACE FORMS ARE THE CONTRACT. The page builds its item memory from the decoded surface form of
* every vocabulary entry, so `tokenize` must return exactly what `decodeToken(token, "gpt2")` in
* app.js returns — `c >= 256 ? (c - 256) & 0xFF : c & 0xFF` per character, then UTF-8 decode. A
* different convention here would make every token unmatchable and the output would be noise.
*
* FALLBACK, NOT A CRASH. If the model is not byte-level BPE (`tokenizer.ggml.model !== "gpt2"`) or
* the file carries no merges — true of the llama SentencePiece fixtures stories260K and stories15M,
* which store 0 merges — then exact merging is impossible and the module falls back to greedy
* longest match over the decoded tokens, reporting `exact: false` so the caller can say so on the
* page instead of implying an exactness it does not have.
*/
(function (root) {
"use strict";
/* ---------------------------------------------------------------- byte-level alphabet */
// GPT-2 bytes_to_unicode: 33..126, 161..172, 174..255 map to themselves; the remaining 68 bytes
// (0..32, 127..160, 173) are pushed to U+0100+n, which is what keeps every byte printable and
// space-free inside a token string.
var BYTE_TO_CHAR = (function () {
var table = new Array(256), extra = 0, b;
function printable(x) {
return (x >= 0x21 && x <= 0x7e) || (x >= 0xa1 && x <= 0xac) || (x >= 0xae && x <= 0xff);
}
for (b = 0; b < 256; b++) if (printable(b)) table[b] = String.fromCharCode(b);
for (b = 0; b < 256; b++) if (!printable(b)) table[b] = String.fromCharCode(256 + extra++);
return table;
})();
// The inverse, matching app.js's decodeToken(token, "gpt2") character-for-character.
function charToByte(c) { return c >= 256 ? (c - 256) & 0xFF : c & 0xFF; }
var textEncoder = typeof TextEncoder !== "undefined" ? new TextEncoder() : null;
var textDecoder = typeof TextDecoder !== "undefined" ? new TextDecoder("utf-8") : null;
function utf8Bytes(str) {
if (textEncoder) return textEncoder.encode(str);
var out = [], i, c, cp; // minimal UTF-8 encoder for environments without it
for (i = 0; i < str.length; i++) {
c = str.charCodeAt(i);
if (c >= 0xd800 && c <= 0xdbff && i + 1 < str.length) {
cp = (c - 0xd800) * 0x400 + (str.charCodeAt(i + 1) - 0xdc00) + 0x10000;
i++;
} else cp = c;
if (cp < 0x80) out.push(cp);
else if (cp < 0x800) out.push(0xc0 | (cp >> 6), 0x80 | (cp & 0x3f));
else if (cp < 0x10000) out.push(0xe0 | (cp >> 12), 0x80 | ((cp >> 6) & 0x3f), 0x80 | (cp & 0x3f));
else out.push(0xf0 | (cp >> 18), 0x80 | ((cp >> 12) & 0x3f), 0x80 | ((cp >> 6) & 0x3f), 0x80 | (cp & 0x3f));
}
return new Uint8Array(out);
}
function bytesToString(bytes) {
if (textDecoder) {
try { return textDecoder.decode(bytes instanceof Uint8Array ? bytes : new Uint8Array(bytes)); }
catch (e) { /* fall through */ }
}
var s = "", i;
for (i = 0; i < bytes.length; i++) s += String.fromCharCode(bytes[i]);
return s;
}
// text -> the tokeniser's alphabet. Every character of the result represents exactly one byte.
function encodeText(text) {
var bytes = utf8Bytes(text), out = "", i;
for (i = 0; i < bytes.length; i++) out += BYTE_TO_CHAR[bytes[i]];
return out;
}
// one vocabulary piece (already in the alphabet) -> the text it represents
function decodePiece(piece) {
var bytes = new Uint8Array(piece.length), n = 0, i;
for (i = 0; i < piece.length; i++) bytes[n++] = charToByte(piece.charCodeAt(i));
return bytesToString(bytes.subarray(0, n));
}
/* ---------------------------------------------------------------- pre-tokeniser */
var CONTRACTIONS = ["s", "t", "re", "ve", "m", "ll", "d"];
// Both spellings of each contraction, so the pattern works without an inline case-insensitive
// group: `(?i:...)` only compiles on engines that support RegExp modifier groups.
function contractionAlternation() {
var parts = [], i, w, a, b;
for (i = 0; i < CONTRACTIONS.length; i++) {
w = CONTRACTIONS[i];
parts.push("'" + w);
for (a = 0; a < w.length; a++) {
var mixed = "";
for (b = 0; b < w.length; b++) mixed += (b === a) ? w.charAt(b).toUpperCase() : w.charAt(b);
parts.push("'" + mixed);
}
}
return parts.join("|");
}
// llama.cpp's qwen2 pre-tokeniser, and GPT-2's own pattern for other byte-level models.
var PATTERNS = {
qwen2: "|" + "[^\\r\\n\\p{L}\\p{N}]?\\p{L}+" + "|\\p{N}" +
"| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*" + "|\\s*[\\r\\n]+" + "|\\s+(?!\\S)" + "|\\s+",
gpt2: "|" + " ?\\p{L}+" + "| ?\\p{N}+" +
"| ?[^\\s\\p{L}\\p{N}]+" + "|\\s+(?!\\S)" + "|\\s+"
};
function compilePretokenizer(pre) {
var name = PATTERNS[pre] ? pre : "gpt2";
var body = "(" + contractionAlternation() + ")" + PATTERNS[name];
var re = null, used = null, uFlag = false;
try { re = new RegExp(body, "gu"); used = name; uFlag = true; }
catch (e) {
try { re = new RegExp(body, "g"); used = name; }
catch (e2) { re = null; used = null; }
}
return { re: re, name: used, unicode: uFlag };
}
function pretokenize(re, text) {
if (!re) return [text];
if (!re.global) return [text];
re.lastIndex = 0;
var out = [], m;
while ((m = re.exec(text)) !== null) {
if (m[0].length) out.push(m[0]);
if (m.index === re.lastIndex) re.lastIndex++; // never spin on a zero-length match
}
return out.length ? out : [text];
}
/* ---------------------------------------------------------------- merges */
// "A B" -> rank, keyed on A + SEP + B. SEP is a character that cannot occur in the alphabet
// (which is entirely printable and space-free), so keys cannot collide.
var SEP = "\u0000";
function buildMerges(list) {
var rank = new Map(), i, s, at;
for (i = 0; i < list.length; i++) {
s = list[i];
if (typeof s !== "string") continue;
at = s.indexOf(" ");
if (at < 1 || at === s.length - 1) continue;
rank.set(s.slice(0, at) + SEP + s.slice(at + 1), i);
}
return rank;
}
// The standard BPE reduction: merge the lowest-ranked adjacent pair, ties going to the leftmost,
// until no recorded merge applies.
function bpeReduce(piece, rank) {
var parts = [], i;
for (i = 0; i < piece.length; i++) parts.push(piece.charAt(i));
if (parts.length < 2) return parts;
while (true) {
var bestRank = Infinity, bestAt = -1, r;
for (i = 0; i + 1 < parts.length; i++) {
r = rank.get(parts[i] + SEP + parts[i + 1]);
if (r !== undefined && r < bestRank) { bestRank = r; bestAt = i; }
}
if (bestAt < 0) break;
parts.splice(bestAt, 2, parts[bestAt] + parts[bestAt + 1]);
}
return parts;
}
/* ---------------------------------------------------------------- greedy fallback */
// Mirrors app.js's tokenize(): longest match first, whitespace skipped only when no symbol
// matches at that position, unknown non-space characters kept as their own symbol.
function makeGreedy(surfacesByPiece, maxLen) {
var set = new Set(), i;
surfacesByPiece.forEach(function (surface) { set.add(surface); });
return function (text) {
var toks = [], i = 0, n = text.length, best, limit, L, sub, c;
while (i < n) {
best = null;
limit = Math.min(maxLen, n - i);
for (L = limit; L >= 1; L--) {
sub = text.substr(i, L);
if (set.has(sub)) { best = sub; break; }
}
if (best) { toks.push(best); i += best.length; continue; }
c = text.charAt(i);
if (c === " " || c === "\n" || c === "\t" || c === "\r") { i += 1; continue; }
toks.push(c);
i += 1;
}
return toks;
};
}
/* ---------------------------------------------------------------- the entry point */
function fromVocab(vocab) {
vocab = vocab || {};
var model = vocab.model || "";
var tokens = vocab.tokens || [];
var merges = vocab.merges || [];
var pre = vocab.pre || "";
var idOf = new Map(), surfaceOfPiece = new Map(), i, t, surf;
for (i = 0; i < tokens.length; i++) {
t = tokens[i];
if (typeof t !== "string") continue;
if (!idOf.has(t)) idOf.set(t, i);
if (model === "gpt2") surfaceOfPiece.set(t, decodePiece(t));
}
var rank = buildMerges(merges);
var exact = model === "gpt2" && rank.size > 0;
var pt = exact ? compilePretokenizer(pre) : { re: null, name: null, unicode: false };
var surfaces = [];
if (!exact) {
var seen = new Set();
for (i = 0; i < tokens.length; i++) {
t = tokens[i];
if (typeof t !== "string") continue;
surf = decodeSurface(t, model);
if (!surf || seen.has(surf)) continue;
seen.add(surf);
surfaces.push([t, surf]);
}
}
var maxLen = 1;
for (i = 0; i < surfaces.length; i++) if (surfaces[i][1].length > maxLen) maxLen = surfaces[i][1].length;
var greedy = makeGreedy(new Map(surfaces), Math.min(maxLen, 24));
function decodeSurface(piece, m) {
if (m === "gpt2") return decodePiece(piece);
var mm = /^<0x([0-9A-Fa-f]{2})>$/.exec(piece);
if (mm) return bytesToString([parseInt(mm[1], 16)]);
return piece.replace(/\u2581/g, " ");
}
// Exact path: pre-tokenise -> merge -> surface. Returns both surfaces and pieces, because the
// id lookup needs the encoded piece while the page needs the decoded surface.
function piecesFor(text) {
if (!exact) return null;
var words = pretokenize(pt.re, encodeText(text));
var out = [], w, j, merged;
for (w = 0; w < words.length; w++) {
merged = bpeReduce(words[w], rank);
for (j = 0; j < merged.length; j++) out.push(merged[j]);
}
return out;
}
function tokenize(text) {
if (typeof text !== "string" || !text.length) return [];
if (!exact) return greedy(text);
var pieces = piecesFor(text), out = [], i2;
for (i2 = 0; i2 < pieces.length; i2++) out.push(surfaceOfPiece.get(pieces[i2]) || decodePiece(pieces[i2]));
return out;
}
function ids(text) {
if (typeof text !== "string" || !text.length) return [];
if (!exact) {
var gs = greedy(text), out = [], i3, id;
for (i3 = 0; i3 < gs.length; i3++) {
id = idForSurface(gs[i3]);
out.push(id);
}
return out;
}
var pieces = piecesFor(text), res = [], j, id2;
for (j = 0; j < pieces.length; j++) {
id2 = idOf.has(pieces[j]) ? idOf.get(pieces[j]) : byteFallbackId(pieces[j]);
res.push(id2);
}
return res;
}
// reverse lookup for the fallback path, built lazily
var surfaceIndexOf = null;
function idForSurface(s) {
if (!surfaceIndexOf) {
surfaceIndexOf = new Map();
for (var k = 0; k < surfaces.length; k++) if (!surfaceIndexOf.has(surfaces[k][1])) surfaceIndexOf.set(surfaces[k][1], surfaces[k][0]);
}
var piece = surfaceIndexOf.get(s);
return piece !== undefined && idOf.has(piece) ? idOf.get(piece) : -1;
}
// A piece with no vocabulary entry is a byte sequence the vocabulary cannot represent; the
// byte tokens <0xNN> on a SentencePiece vocabulary are the usual backstop. -1 means "no id".
function byteFallbackId(piece) {
if (piece.length !== 1) return -1;
var hex = charToByte(piece.charCodeAt(0)).toString(16).toUpperCase();
if (hex.length < 2) hex = "0" + hex;
var key = "<0x" + hex + ">";
return idOf.has(key) ? idOf.get(key) : -1;
}
return {
model: model,
pre: pre,
exact: exact,
pretokenizer: pt.name,
unicodeRegex: pt.unicode,
mergeCount: rank.size,
vocabSize: tokens.length,
tokenize: tokenize,
ids: ids,
encodeText: encodeText,
decodePiece: decodePiece,
pieces: piecesFor
};
}
var api = { fromVocab: fromVocab, encodeText: encodeText, decodePiece: decodePiece,
bytesToString: bytesToString, BYTE_TO_CHAR: BYTE_TO_CHAR, charToByte: charToByte,
buildMerges: buildMerges, bpeReduce: bpeReduce };
if (typeof module !== "undefined" && module.exports) module.exports = api;
root.HDCBPE = api;
})(typeof globalThis !== "undefined" ? globalThis : this);