Project: BPE Tokenizer from Scratch

কী বানাবে

পুরো একটা byte-level BPE tokenizer, GPT ধরনের model যে algorithm ব্যবহার করে সেটাই: বাংলা আর English corpus এ train করো, একটা file এ save করো, যেকোনো text কোনো তথ্য না হারিয়ে encode আর decode করো, আর দুইটা আসল model এর tokenizer, OpenAI এর cl100k_base আর o200k_base (tiktoken library দিয়ে), এর সাথে token এর সংখ্যা মেলাও।

Corpus টা এই course নিজেই: এইমাত্র যে lesson গুলো পড়লে তাদের text, দুই ভাষাতেই, প্রায় 211,000 অক্ষর। শেষে তুমি ঠিকঠাক জানবে ঠিক ভাষায় train করা tokenizer কেন একটা বাংলা product কে সস্তা করে, আর একটা tokenizer file এ আসলে কী থাকে।

যা আগে জানা লাগবে

• Tokenization: BPE merge, byte, বাংলায় খরচ কেন বেশি।
• Python 3; তুলনার জন্য pip install tiktoken (দুইটা encoding একবার download করে)।
• একটা text corpus। বাংলা আর English এর যেকোনো মিশ্রণ চলবে; code corpus_en.txt আর corpus_bn.txt চায়।

Architecture

Play

অংশ	কাজ
SPLIT regex	pre-tokenisation: সামনের space সহ একটা শব্দ, সর্বোচ্চ 3 digit, যতিচিহ্ন, whitespace
BPE.train	শব্দের frequency ধরে জোড়া গোনা, সেরাটা merge, লক্ষ্যের vocabulary পর্যন্ত চালানো
BPE.encode	প্রতিটা টুকরোয়, সবচেয়ে আগে শেখা যে merge পাওয়া যায় সেটা লাগাও, যতক্ষণ না আর লাগে
BPE.decode	প্রতিটা id এর byte বের করো, জোড়া দাও, UTF-8 decode করো
save / load	merge এর list JSON হিসেবে: ওই list টাই tokenizer

ধাপে ধাপে বানাও

Step 1: pre-tokenise। Lesson এর ছোট্ট BPE এমন merge শিখেছিল যেগুলো শব্দের সীমানা পেরিয়ে যায় (" আমার অর্ডার ক..."), ফলে space ছাড়া শুরু হওয়া বাক্যে মিলত না। আসল tokenizer আগে text কে টুকরোয় ভাগ করে আর শুধু টুকরোর ভেতরে merge করে। এখানে একটা টুকরো মানে সামনের space সহ একটা শব্দ, সর্বোচ্চ 3 টা digit এর একটা টানা অংশ (যাতে লম্বা সংখ্যা একটা token না হয়ে যায়), যতিচিহ্নের টানা অংশ, বা whitespace। । (বাংলা দাঁড়ি) যতিচিহ্ন হিসেবে গোনা।

Step 2: শব্দ গুনে train। প্রতিটা merge এর জন্য 300,000 byte ঘাঁটার বদলে, প্রতিটা আলাদা শব্দ একবার গোনো (Counter) আর তার জোড়াগুলোকে সেই সংখ্যা দিয়ে weight দাও। সমান হলে id দিয়ে ভাঙা হয়, যাতে training প্রতিবার একই ফল দেয়।

Step 3: encode। প্রতিটা টুকরোর জন্য বারবার সেই জোড়াটা খোঁজো যার merge rank সবচেয়ে কম (সবচেয়ে আগে শেখা), আর merge করো। Training এর text যেভাবে ভাগ হয়েছিল, হুবহু সেটাই আবার হয়।

Step 4: decode আর save। Decode মানে একটা lookup আর একটা জোড়া দেওয়া। Tokenizer file এ শুধু সাজানো merge গুলো; vocabulary সেখান থেকেই আবার বানানো হয়।

"""A byte-level BPE tokenizer: train, encode, decode, save and load."""
import json
import re
from collections import Counter

# Pre-tokenisation: a word with its leading space, a run of up to 3 digits, punctuation, or spaces.
# Merges never cross these pieces, so " order" and "order." share the token for "order".
PUNCT = r"!-/:-@\[-`{-~।"
SPLIT = re.compile(rf" ?[^\s\d{PUNCT}]+| ?\d{{1,3}}| ?[{PUNCT}]+|\s+")

class BPE:
    def __init__(self):
        self.merges = {}                                  # (a, b) -> new id, in the order learned
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        words = Counter(tuple(w.encode("utf-8")) for w in SPLIT.findall(text))
        while len(self.vocab) < vocab_size:
            pairs = Counter()
            for w, n in words.items():
                for p in zip(w, w[1:]):
                    pairs[p] += n
            if not pairs:
                break
            best = max(pairs, key=lambda p: (pairs[p], -p[0], -p[1]))   # ties broken the same way every run
            new = len(self.vocab)
            self.merges[best] = new
            self.vocab[new] = self.vocab[best[0]] + self.vocab[best[1]]
            words = Counter({self._merge(w, best, new): n for w, n in words.items()})
        return self

    @staticmethod
    def _merge(ids, pair, new):
        out, i = [], 0
        while i < len(ids):
            if i + 1 < len(ids) and (ids[i], ids[i + 1]) == pair:
                out.append(new); i += 2
            else:
                out.append(ids[i]); i += 1
        return tuple(out)

    def encode(self, text):
        out = []
        for piece in SPLIT.findall(text):
            ids = tuple(piece.encode("utf-8"))
            while len(ids) > 1:                           # always apply the earliest-learned merge first
                pair = min(zip(ids, ids[1:]), key=lambda p: self.merges.get(p, float("inf")))
                if pair not in self.merges:
                    break
                ids = self._merge(ids, pair, self.merges[pair])
            out.extend(ids)
        return out

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

    def save(self, path):
        json.dump({"merges": [[a, b, n] for (a, b), n in self.merges.items()]}, open(path, "w"))

    @classmethod
    def load(cls, path):
        t = cls()
        for a, b, n in json.load(open(path))["merges"]:
            t.merges[(a, b)] = n
            t.vocab[n] = t.vocab[a] + t.vocab[b]
        return t

Train, তারপর তিনটা আলাদা রাখা বাক্যে তুলনা যেগুলো tokenizer কখনো দেখেনি: English, বাংলা, আর Banglish (Latin অক্ষরে বাংলা)।

import tiktoken
from bpe import BPE

corpus = open("corpus_en.txt").read() + "\n" + open("corpus_bn.txt").read()
print(f"corpus: {len(corpus):,} characters, {len(corpus.encode('utf-8')):,} bytes")

tok = BPE().train(corpus, vocab_size=2000)
tok.save("tokenizer.json")
learned = [tok.vocab[n].decode("utf-8", errors="replace") for n in list(tok.merges.values())]
print("first merges:", learned[:8])
print("some later tokens:", [t for t in learned[-400:] if len(t) > 4][:8])

# Held-out sentences the tokenizer never saw.
tests = {
    "en": "The rider called to say the parcel will arrive after the evening prayer.",
    "bn": "রাইডার ফোন করে বলল পার্সেলটা সন্ধ্যার পরে পৌঁছাবে।",
    "banglish": "Rider call kore bollo parcel ta shondhar pore pouchabe.",
}
real = {name: tiktoken.get_encoding(name) for name in ("cl100k_base", "o200k_base")}
print(f"\n{'text':<9} {'chars':>5} {'ours (2k)':>9} {'cl100k':>7} {'o200k':>6}")
for name, s in tests.items():
    ours = tok.encode(s)
    assert tok.decode(ours) == s
    print(f"{name:<9} {len(s):>5} {len(ours):>9} {len(real['cl100k_base'].encode(s)):>7} {len(real['o200k_base'].encode(s)):>6}")

print("\nhow ours splits the Bangla sentence:")
print(" | ".join(tok.decode([i]) for i in tok.encode(tests["bn"])))

Output:

corpus: 211,034 characters, 308,746 bytes
first merges: ['�', ' �', '�', 'া', 'ে', 'র', ' t', 'া�']
some later tokens: ['Attention', ' দেওয়া', ' distribution', ' descent', ' একসাথে', ' English', 'training', ' make']

text      chars ours (2k)  cl100k  o200k
en           72        30      14     14
bn           50        27      60     19
banglish     55        27      16     15

how ours splits the Bangla sentence:
র | াই | � | � | ার |  ফ | োন |  করে |  বল | ল |  পার | ্� | � | েল | টা |  স | ন | ্� | � | ্য | ার |  পরে |  পৌ | ঁ | ছ | াবে | ।

কী দেখলাম:

• প্রথম merge গুলো বাংলার byte এর জোড়া। Byte এ বাংলা corpus English এর দ্বিগুণ, আর প্রতিটা বাংলা অক্ষর একই byte দিয়ে শুরু হয়, তাই e0 a6 এর মতো জোড়া আগে জেতে (� হিসেবে দেখানো, অর্ধেক অক্ষর)। তারপর আসে আসল কার (া, ে) আর অক্ষর (র)।
• পরের token গুলো দুই ভাষারই পুরো শব্দ: " দেওয়া", " একসাথে", " distribution", " descent", "Attention"। Tokenizer course এর শব্দভাণ্ডার শিখে ফেলেছে।
• English: আমাদেরটা নেয় 30 token, আসলগুলো 14। তাদের 1 থেকে 2 লাখ token এর vocabulary তে এমন পুরো common শব্দ আছে যেগুলো 2,000 এ আমরা রাখতে পারি না।
• বাংলা: আমাদেরটা 27 token, cl100k_base 60, o200k_base 19। বাংলায় train করা 2,000 token এর vocabulary মূলত English এ train করা 1 লাখ token এর vocabulary কে 2 গুণের বেশি হারায়। বেশি বহুভাষিক data তে train করা নতুন o200k_base আরো ভালো করে। একই বাক্য, দুইটা আসল tokenizer এর মধ্যে খরচে 3 গুণ পার্থক্য।
• Banglish: আমাদেরটায় 27, আসলগুলোয় 15 থেকে 16। Latin অক্ষর সস্তা (প্রতিটা 1 byte), আর আমাদের corpus এ Banglish কম।
• বাংলা ভাগ আসল টুকরো দেখায় (" করে", " পরে", "াবে", "টা") আর কিছু অর্ধেক অক্ষর (�) বাকি থাকে rare অক্ষরের জন্য, যেমন "রাইডার" এর "ই"। আরো merge বা আরো বাংলা text হলে এগুলোও জোড়া লাগত।

Test করো

from bpe import BPE

tok = BPE().train(open("corpus_bn.txt").read()[:20000] + open("corpus_en.txt").read()[:20000], vocab_size=400)

def test_roundtrip_any_text():
    for s in ["", "hello", "আমার অর্ডার", "mixed বাংলা and English 123,456!", "emoji 🚚 and tabs\tand\nlines", "zxqv ঋৠ"]:
        assert tok.decode(tok.encode(s)) == s, s

def test_unseen_characters_fall_back_to_bytes():
    ids = tok.encode("🚚")
    assert all(i < 256 for i in ids) and len(ids) == 4      # 4 UTF-8 bytes, no merges learned for it

def test_save_and_load_give_identical_ids(tmp="/tmp/t.json"):
    tok.save(tmp)
    s = "the order is late, অর্ডার দেরি হচ্ছে"
    assert BPE.load(tmp).encode(s) == tok.encode(s)

def test_merges_make_text_shorter():
    s = "the training loss goes down"
    assert len(tok.encode(s)) < len(s.encode("utf-8"))

if __name__ == "__main__":
    for name, fn in list(globals().items()):
        if name.startswith("test_"):
            fn()
            print("pass", name)

pass test_roundtrip_any_text
pass test_unseen_characters_fall_back_to_bytes
pass test_save_and_load_give_identical_ids
pass test_merges_make_text_shorter

• যেকোনো কিছুতে round-trip: খালি string, মিশ্র লিপি, comma সহ সংখ্যা, একটা emoji, tab আর newline, rare বাংলা অক্ষর। Tokenizer কখনো text হারাতে বা বদলাতে পারবে না।
• অদেখা অক্ষর byte এ ফিরে যায়: 🚚 emoji টা তার 4 টা UTF-8 byte হয়ে যায়। Byte-level BPE এর কারণই এটা: কোনো "unknown token" নেই।
• Save আর load একই id দেয়: আবার load করার পরে অন্যভাবে encode করা tokenizer চলমান একটা model কে চুপচাপ ভেঙে দিত।
• Merge সত্যিই ছোট করে: সাধারণ text এ encode করা দৈর্ঘ্য byte এর দৈর্ঘ্যের চেয়ে কম।

Trade-offs

Choice	ভালো দিক	খরচ
Vocabulary 2,000	কয়েক second এ train, ছোট embedding table	English এ 1 লাখ vocabulary র tokenizer এর 2 গুণ token লাগে
Byte থেকে শুরু	কখনো অজানা token নেই, যেকোনো ভাষা বা emoji	merge একটা অক্ষরকে টুকরো করতে পারে; streaming কে অর্ধেক UTF-8 সামলাতে হয়
Pre-tokenisation regex	merge শব্দের সীমানা মানে; ভাগ সবসময় একই রকম	regex এ কিছু ধারণা বাঁধা থাকে (কোনটা যতিচিহ্ন, digit কীভাবে দলে) যেগুলো পরে বদলানো কঠিন
Corpus = এই course	আসল দ্বিভাষিক text, domain এর শব্দ একটা token হয়ে যায়	ছোট আর সংকীর্ণ: course এর বাইরের রোজকার শব্দ ভাঙাই থাকে
শুধু Python এ training	পড়া যায়	বড় corpus এ ধীর; production এর tokenizer Rust এ train হয় (Hugging Face tokenizers, SentencePiece)

একটা model একবার কোনো tokenizer এ train হয়ে গেলে tokenizer বাঁধা পড়ে যায়: বদলানো মানে embedding table আবার train করা। তাই vocabulary size আর training এর মিশ্রণ (কতটা বাংলা, Banglish আর code) দীর্ঘমেয়াদি product এর সিদ্ধান্ত।

আরো এগিয়ে নাও

1. 1,000, 4,000 আর 8,000 vocabulary size এ train করো, আর প্রতিটায় প্রতি অক্ষরে বাংলা আর English এর token আঁকো। লাভ কোথায় গিয়ে থেমে যায়?
2. Corpus এর মিশ্রণ বদলাও (শুধু English, শুধু বাংলা) আর মাপো প্রতিটা ভাষার খরচ কোন দিকে যায়।
3. Special token যোগ করো (<|user|>, <|end|>) যেগুলো encode user এর text থেকে কখনো বানায় না, শুধু একটা আলাদা API থেকে, আর test করো যে user আক্ষরিক <|end|> টাইপ করলে সাধারণ token পায়।
4. 1 MB text এ encode এর সময় মাপো, তারপর প্রতিটা আলাদা শব্দের encoding cache করে দ্রুত করো।