# Byte-Pair Encoding tokenization

<CourseFloatingBanner chapter={6}
  classNames="absolute z-10 right-0 top-0"
  notebooks={[
    {label: "Google Colab", value: "https://colab.research.google.com/github/huggingface/notebooks/blob/master/course/th/chapter6/section5.ipynb"},
    {label: "Aws Studio", value: "https://studiolab.sagemaker.aws/import/github/huggingface/notebooks/blob/master/course/th/chapter6/section5.ipynb"},
]} />

ดั้งเดิมแล้ว Byte-Pair Encoding (BPE) เป็นอัลกอริทึมที่ถูกสร้างเพื่อใช้บีบอัดข้อความให้เล็กลง (compress texts) ภายหลัง OpenAI ได้นำอัลกอริทึมนี้มาใช้ในการตัดคำ ในขั้นตอนเตรียมข้อมูลเพื่อเทรน GPT อัลกอริทึมตัวนี้ยังถูกนำมาใช้อย่างกว้างขวางกับโมเดลประเภท Transformer เช่น GPT, GPT-2, RoBERTa, BART, และ DeBERTa

<Youtube id="HEikzVL-lZU"/>

<Tip>

💡 บทนี้จะพูดถึง BPE อย่างละเอียด เราจะเจาะลึกถึงไปถึงการ implement อัลกอริทึมนี้ คุณสามารถข้ามไปตอนท้ายได้ ถ้าคุณสนใจเพียงแค่ภาพรวมคร่าวๆเท่านั้น

</Tip>

## อัลกอริทึมที่ใช้ในการเทรน

BPE เริ่มการเทรนด้วยการคำนวณรายการของคำที่อยู่ในคลังข้อมูล (คลังข้อมูลจะต้องผ่านการ normalization และ pre-tokenization มาแล้ว) จากนั้นมันจะเริ่มสร้างชุดคำศัพท์ (vocabulary) จากตัวอักษรที่อยู่ในแต่ละคำ มาดูตัวอย่างง่ายๆกัน เราจะสมมติว่าคลังข้อมูลของเรามีเพียงห้าคำเท่านั้น :

```
"hug", "pug", "pun", "bun", "hugs"
```

vocabulary ตั้งต้นสำหรับชุดข้อมูลนี้คือ `["b", "g", "h", "n", "p", "s", "u"]`  ในการใช้งานจริง vocabulary ตั้งต้นจะประกอบด้วยตัวอักษร ASCII เป็นอย่างต่ำ หรืออาจจะมีตัวอักษร Unicode ได้ด้วย

ถ้าข้อความใหม่ที่คุณต้องการจะตัดคำ มีสัญลักษณ์ที่ไม่ได้อยู่ใน training corpus สัญลักษณ์พวกนี้จะถูกแปลงเป็น unknown token นี่เป็นเหตุผลว่าทำไมโมเดล NLP จึงประมวลผลข้อความที่มีอีโมจิได้ไม่ดีนัก

<Tip>

Tokenizer ของ GPT-2 และ RoBERTa (ซึ่งค่อนข้างคล้ายกัน) มีวิธีการจัดการกับปัญหานี้ได้อย่างประสิทธิภาพ มันจะไม่มองแต่ละคำเป็น Unicode แต่จะมองว่าเป็น byte การทำแบบนี้ทำให้ vocabulary ตั้งต้น มีขนาดที่เล็ก (256) แต่ยังสามารถบันทึกทุกๆสัญลักษณ์ได้ โดยไม่ต้องแปลงสัญลักษณ์พิเศษต่างๆเป็น unknown token เทคนิคนี้เรียกว่า *byte-level BPE*

</Tip>

หลังจากสร้าง vocabulary ตั้งต้นแล้ว เราจะเพิ่ม token ใหม่ๆ เข้าไปจนว่าจะได้ vocabulary ขนาดใหญ่พอกับที่เราต้องการ โดยเราจะเทรน BPE ให้เรียน กฎที่เรียกว่า *merges* ซึ่งเป็นกฎสำหรับการรวมสองหน่วยใน vocabulary เข้าด้วยกัน
ตอนช่วงเริ่มต้น กฎ merges พวกนี้จะสร้างคำย่อยที่ประกอบด้วยตัวอักษรสองตัว ระหว่างที่เราเทรนต่อไปเรื่อยๆ คำย่อยที่ได้ก็จะยาวขึ้น
ในแต่ละรอบของการเทรน BPE จะคำนวณหาคู่ของคำย่อยที่พบบ่อยที่สุด (คู่ของคำย่อย ในที่นี้เราหมายถึง token ที่อยู่ติดกัน)
คู่ที่มีความถี่มากที่สุดจะถูกรวมเข้าด้วยกัน จากนั้นโมเดลจะทำแบบเดิมอีกในการเทรนรอบต่อไป

กลับมาที่ตัวอย่างของเรา สมมติว่าแต่ละคำมีความถี่ดังต่อไปนี้ :

```
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)
```

ซึ่งแปลว่า `"hug"` พบ 10 ครั้งใน corpus, `"pug"` พบ 5 ครั้ง, `"pun"` พบ 12 ครั้ง, `"bun"` พบ 4 ครั้ง, และ `"hugs"` พบ 5 ครั้ง

เราจะเริ่มการเทรน โดยแยกแต่ละคำออกเป็นตัวอักษร (ตัวอักษรจะต้องมาจาก vocabulary ตั้งต้นที่เราสร้างมาก่อนหน้านี้แล้ว) ตอนนี้คุณจะเห็นว่าแต่ละคำถูกแปลงเป็น list ที่ประกอบไปด้วยหลายๆ token

```
("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)
```

จากนั้น เราจะดูทีละคู่ ตัวอย่างเช่น คู่ `("h", "u")` ซึ่งมาจากคำว่า `"hug"` และ `"hugs"` และพบ 15 ครั้งใน corpus
อย่างไรก็ตาม คู่นี้ไม่ใช่คู่ที่พบบ่อยที่สุด คู่ที่พบบ่อยที่สุดคือ `("u", "g")` ซึ่งพบใน คำว่า `"hug"`, `"pug"`, และ `"hugs"` ซึ่งความถี่รวมของมันคือ 20 ครั้ง
ดังนั้น กฎแรกของการ merge ที่ tokenizer เรียนคือ `("u", "g") -> "ug"` แปลว่ามันจะเพิ่ม `"ug"` เข้าไปใน vocabulary และใน corpus คู่นี้ก็จะถูกรวมเป็น token เดียวด้วย

หลังจากขั้นตอนนี้ vocabulary และ corpus จะมีค่าดังนี้ :

```
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)
```

ตอนนี้ จะเห็นว่าเรามีคู่ที่เมื่อรวมกันจะได้ token ที่ยาวกว่าสองตัวอักษร ตัวอย่างเช่น คู่ `("h", "ug")` ซึ่งพบ 15 ครั้งใน corpus
อย่างไรก็ตาม คู่ที่พบบ่อยที่สุดคือ `("u", "n")` ซึ่งพบ 16 ครั้ง ดังนั้นกฎที่สองก็คือ `("u", "n") -> "un"` หลังจากที่เราเพิ่มคู่นี้ไปใน vocabulary และ merge token ใน corpus เข้าด้วยกันแล้ว เราจะได้ :

```
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("h" "ug" "s", 5)
```

ตอนนี้ คู่ที่พบบ่อยที่สุดคือ `("h", "ug")` ดังนั้นกฎที่ได้คือ `("h", "ug") -> "hug"` ซึ่งจะทำให้เราได้ token ที่มีสามตัวอักษร หลังจากการ merge เราจะได้ :

```
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]
Corpus: ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)
```

เราจะทำแบบนี้ต่อไปเรื่อยๆ จนกว่าจะได้ขนาดของ vocabulary ที่ต้องการ

<Tip>

✏️ **ตาคุณแล้ว!** คุณคิดว่ากฎ merge ต่อไปคืออะไร

</Tip>

## Tokenization algorithm

การ tokenization เป็นขั้นตอนหลังจากการเทรน โดย input ใหม่จะถูก tokenize ด้วยขั้นตอนดังต่อไปนี้

1. Normalization (การปรับข้อความให้เป็นมาตรฐาน)
2. Pre-tokenization (การเตรียมข้อความให้พร้อมสำหรับการ tokenize จริง)
3. แยกคำออกเป็นตัวอักษรเดี่ยว
4. ใช้กฎ merge ที่ได้จากการเทรนเพื่อรวมตัวอักษรที่เราได้จากขั้นตอนก่อนหน้า

มาดูกฎสามตัวที่เราได้จากการเทรนก่อนหน้านี้ :

```
("u", "g") -> "ug"
("u", "n") -> "un"
("h", "ug") -> "hug"
```

คำว่า`"bug"` จะถูกแยกเป็น `["b", "ug"]` ส่วนคำว่า `"mug"` จะถูกแยกเป็น `["[UNK]", "ug"]` เพราะว่า `"m"` ไม่ได้อยู่ใน vocabulary ของเรา
้เช่นเดียวกัน คำว่า `"thug"` จะถูกแยกเป็น `["[UNK]", "hug"]` เพราะว่า `"t"` ไม่ได้อยู่ใน vocabulary กฎแรกจะรวม `"u"` และ `"g"` เข้าด้วยกัน จากนั้น `"hu"` และ `"g"` ก็จะถูกรวมเข้าด้วยกัน

<Tip>

✏️ **ตาคุณแล้ว!** คุณคิดว่าคำว่า `"unhug"` จะถูกแยกอย่างไร

</Tip>

## การสร้าง BPE (Implementing BPE)

ตอนนี้เราจะมาดูกันว่า คุณจะสามารถ implement อัลกอริทึม BPE ได้อย่างไร สิ่งที่เราจะเรียนต่อไปนี้ไม่ใช่ implementation ที่ดีที่สุด เราเพียงต้องการให้คุณเข้าใจโค้ดและเข้าใจว่า BPE ทำงานอย่างไร

อันดับแรก เราต้องการ corpus ดังนั้น เราจะสร้าง corpus แบบง่ายๆขึ้นมา โดยประกอบไปด้วยไม่กี่ประโยค :

```python
corpus = [
    "This is the Hugging Face course.",
    "This chapter is about tokenization.",
    "This section shows several tokenizer algorithms.",
    "Hopefully, you will be able to understand how they are trained and generate tokens.",
]
```

จากนั้นเราจะทำการ pre-tokenize corpus นี้ เพื่อแยกข้อความออกเป็นคำๆ เนื่องจากเราจะสร้าง BPE tokenizer ตามตัวที่ใช้ใน GPT-2 เราจึงต้องใช้ `gpt2` tokenizer ในการ pre-tokenize

```python
from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")
```

จากนั้นเราจะคำนวณความถี่ของแต่ละคำ:

```python
from collections import defaultdict

word_freqs = defaultdict(int)

for text in corpus:
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    new_words = [word for word, offset in words_with_offsets]
    for word in new_words:
        word_freqs[word] += 1

print(word_freqs)
```

```python out
defaultdict(int, {'This': 3, 'Ġis': 2, 'Ġthe': 1, 'ĠHugging': 1, 'ĠFace': 1, 'ĠCourse': 1, '.': 4, 'Ġchapter': 1,
    'Ġabout': 1, 'Ġtokenization': 1, 'Ġsection': 1, 'Ġshows': 1, 'Ġseveral': 1, 'Ġtokenizer': 1, 'Ġalgorithms': 1,
    'Hopefully': 1, ',': 1, 'Ġyou': 1, 'Ġwill': 1, 'Ġbe': 1, 'Ġable': 1, 'Ġto': 1, 'Ġunderstand': 1, 'Ġhow': 1,
    'Ġthey': 1, 'Ġare': 1, 'Ġtrained': 1, 'Ġand': 1, 'Ġgenerate': 1, 'Ġtokens': 1})
```

ขั้นตอนต่อไป คือการคำนวณ vocabulary ตั้งต้น ซึ่งสร้างจากแต่ละตัวอักษรใน corpus :

```python
alphabet = []

for word in word_freqs.keys():
    for letter in word:
        if letter not in alphabet:
            alphabet.append(letter)
alphabet.sort()

print(alphabet)
```

```python out
[ ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's',
  't', 'u', 'v', 'w', 'y', 'z', 'Ġ']
```

เราจะเพิ่ม token พิเศษเข้าไปในข้างหน้า list นี้ด้วย GPT-2 ใช้ token พิเศษคือ `"<|endoftext|>"` :

```python
vocab = ["<|endoftext|>"] + alphabet.copy()
```

จากนั้นเราจะแยกแต่ละคำใน corpus ให้เป็นตัวอักษร เพื่อที่เราจะได้เริ่มการเทรน :

```python
splits = {word: [c for c in word] for word in word_freqs.keys()}
```

ตอนนี้เราก็พร้อมที่จะเทรนแล้ว เราจะเริ่มด้วยการเขียนฟังก์ชันที่คำนวณความถี่ของแต่ละคู่ token :

```python
def compute_pair_freqs(splits):
    pair_freqs = defaultdict(int)
    for word, freq in word_freqs.items():
        split = splits[word]
        if len(split) == 1:
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            pair_freqs[pair] += freq
    return pair_freqs
```

มาดูส่วนผลลัพธ์ (ซึ่งเป็น dictionary) กัน :

```python
pair_freqs = compute_pair_freqs(splits)

for i, key in enumerate(pair_freqs.keys()):
    print(f"{key}: {pair_freqs[key]}")
    if i >= 5:
        break
```

```python out
('T', 'h'): 3
('h', 'i'): 3
('i', 's'): 5
('Ġ', 'i'): 2
('Ġ', 't'): 7
('t', 'h'): 3
```

จากนั้นเราจะหาคู่ที่พบบ่อยที่สุด ซึ่งทำได้ง่ายๆดังนี้ :

```python
best_pair = ""
max_freq = None

for pair, freq in pair_freqs.items():
    if max_freq is None or max_freq < freq:
        best_pair = pair
        max_freq = freq

print(best_pair, max_freq)
```

```python out
('Ġ', 't') 7
```

ดังนั้น กฎแรกที่เราได้ก็คือ `('Ġ', 't') -> 'Ġt'` และเราจะต้องเพิ่ม `'Ġt'` เข้าไปใน vocabulary :

```python
merges = {("Ġ", "t"): "Ġt"}
vocab.append("Ġt")
```

จากนั้น เราจะต้องทำการ merge คำย่อยที่อยู่ใน dictionary `splits` ด้วย โดยเราจะเขียนฟังก์ชันต่อไปนี้ :

```python
def merge_pair(a, b, splits):
    for word in word_freqs:
        split = splits[word]
        if len(split) == 1:
            continue

        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                split = split[:i] + [a + b] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits
```

และนี่ก็คือผลลัพธ์จากการ merge ครั้งแรก :

```py
splits = merge_pair("Ġ", "t", splits)
print(splits["Ġtrained"])
```

```python out
['Ġt', 'r', 'a', 'i', 'n', 'e', 'd']
```

ตอนนี้เราก็มีทุกอย่างพร้อมสำหรับการเทรนแล้ว เราจะเทรนจนกว่าขนาดของ vocabulary จะเท่ากับ 50 :

```python
vocab_size = 50

while len(vocab) < vocab_size:
    pair_freqs = compute_pair_freqs(splits)
    best_pair = ""
    max_freq = None
    for pair, freq in pair_freqs.items():
        if max_freq is None or max_freq < freq:
            best_pair = pair
            max_freq = freq
    splits = merge_pair(*best_pair, splits)
    merges[best_pair] = best_pair[0] + best_pair[1]
    vocab.append(best_pair[0] + best_pair[1])
```

ผลลัพธ์ที่ได้คือ tokenizer ของเราได้เรียน 19 กฎ (vocabulary ตั้งต้นมี 31 token ซึ่งมาจากตัวอักษรที่เรามี 30 ตัวและ token พิเศษอีกหนึ่งตัว) :

```py
print(merges)
```

```python out
{('Ġ', 't'): 'Ġt', ('i', 's'): 'is', ('e', 'r'): 'er', ('Ġ', 'a'): 'Ġa', ('Ġt', 'o'): 'Ġto', ('e', 'n'): 'en',
 ('T', 'h'): 'Th', ('Th', 'is'): 'This', ('o', 'u'): 'ou', ('s', 'e'): 'se', ('Ġto', 'k'): 'Ġtok',
 ('Ġtok', 'en'): 'Ġtoken', ('n', 'd'): 'nd', ('Ġ', 'is'): 'Ġis', ('Ġt', 'h'): 'Ġth', ('Ġth', 'e'): 'Ġthe',
 ('i', 'n'): 'in', ('Ġa', 'b'): 'Ġab', ('Ġtoken', 'i'): 'Ġtokeni'}
```

ส่วน vocabulary ที่ได้จะประกอบไปด้วย token พิเศษ, ตัวอักษรตั้งต้น, และผลลัพธ์จากการ merge แต่ละครั้ง :

```py
print(vocab)
```

```python out
['<|endoftext|>', ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o',
 'p', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z', 'Ġ', 'Ġt', 'is', 'er', 'Ġa', 'Ġto', 'en', 'Th', 'This', 'ou', 'se',
 'Ġtok', 'Ġtoken', 'nd', 'Ġis', 'Ġth', 'Ġthe', 'in', 'Ġab', 'Ġtokeni']
```

<Tip>

💡 ถ้าคุณใช้ `train_new_from_iterator()` กับ corpus เดียวกันนี้ คุณจะไม่ได้ vocabulary เดียวกัน เพราะว่าอาจจะมีหลายคู่ token ที่มีความถี่สูงสุดเท่ากัน ในตัวอย่างของเรา เราเลือกคู่แรกที่โค้ดของเราอ่านเจอ ส่วน 🤗 Tokenizers library เลือกคู่แรกโดยเรียงตาม ID

</Tip>

หากเราต้องการ tokenize ข้อความใดข้อความหนึ่ง สิ่งที่ต้องทำคือ pre-tokenize จากนั้นจึงทำการ tokenize และสุดท้าย apply กฎ merge :

```python
def tokenize(text):
    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text)
    pre_tokenized_text = [word for word, offset in pre_tokenize_result]
    splits = [[l for l in word] for word in pre_tokenized_text]
    for pair, merge in merges.items():
        for idx, split in enumerate(splits):
            i = 0
            while i < len(split) - 1:
                if split[i] == pair[0] and split[i + 1] == pair[1]:
                    split = split[:i] + [merge] + split[i + 2 :]
                else:
                    i += 1
            splits[idx] = split

    return sum(splits, [])
```

คุณสามารถทดลองโค้ดนี้ได้กับข้อความทุกข้อความ ที่ประกอบไปด้วยตัวอักษรเท่านั้น :

```py
tokenize("This is not a token.")
```

```python out
['This', 'Ġis', 'Ġ', 'n', 'o', 't', 'Ġa', 'Ġtoken', '.']
```

<Tip warning={true}>

⚠️ การ implementation ในตัวอย่างของเราจะ return error ถ้าโปรแกรมอ่านเจอตัวอักษรที่ไม่มีใน vocabulary นั่นเพราะว่าเราไม่ได้เขียนโค้ดเพื่อจัดการกับกรณีแบบนี้
ใน GPT-2 ปกติจะไม่มี unknown token แบบนี้ เพราะว่า ถ้าเราใช้ byte-level BPE เราจะไม่มีทางได้ตัวอักษรที่ unknown อย่างไรก็ตามในตัวอย่างของเรา เราไม่ได้ใช้ทุกๆ byte เพื่อสร้าง vocabulary ตั้งต้น
อย่างไรก็ตาม หัวข้อนี้นั้นค่อนข้างลึก เราจึงจะไม่ขอพูดถึงรายละเอียดไปมากกว่านี้

</Tip>

นี่ก็คือ อัลกอริทึม BPE ในบทต่อไป เราจะมาดู WordPiece กัน