Trained tokenizer has broken encoding for cyrillic
Author: Anna-Pinewood
Pull request: no
Labels: name: Core: Tokenization

### System Info

transformers-4.40.2
Python 3.10.12
Distributor ID: Ubuntu
Description:    Ubuntu 22.04.3 LTS
Release:        22.04

### Who can help?

@ArthurZucker 


### Information

- [ ] The official example scripts
- [x] My own modified scripts

### Tasks

- [ ] An officially supported task in the `examples` folder (such as GLUE/SQuAD, ...)
- [x] My own task or dataset (give details below)

### Reproduction

**Summary:**
I am encountering unexpected behavior while training the tokenizer on Cyrillic texts using AutoTokenizer from the meta-llama/Meta-Llama-3-8B model. Despite my expectation that each character in the Cyrillic alphabet would be represented by a single token in the vocabulary, I am observing that some single characters, such as 'б', are being represented by multiple tokens

**Description:**
As far as I understand, BPE encoding works like this: we start with tokens for single characters, then merge pairs of characters into new tokens, and so on. Therefore, each single character should be represented in the token vocabulary as a single token. For example, "a" might be token 1, "b" might be token 117, etc.

I trained an AutoTokenizer on Cyrillic texts and expected the Cyrillic alphabet to be represented in the vocabulary with a separate token for each letter. However, I am getting two tokens for a single character, such as 'б' in this example.

**Reproduction:**
[Colab notebook with examples of unexpected behavior](https://colab.research.google.com/drive/1OTd3ys8TMVcXTRKOy2JW5v2pKL-a9kVo?usp=sharing)
Toy example with unexpected behavior:
```
from transformers import AutoTokenizer
tokenizer_name = 'meta-llama/Meta-Llama-3-8B'
old_tokenizer = AutoTokenizer.from_pretrained(tokenizer_name)
toy_corpus_ru = ["Моя цель – обладать величием и властью. Я бы хотела решать, куда будет двигаться проект. Я хочу быть великой. Я хочу власти."]
my_tokenizer = old_tokenizer.train_new_from_iterator(toy_corpus_ru, 52000)
my_tokenizer.encode('б')
# [128000, 272, 260]
old_tokenizer.encode('б')
# [128000, 10124]
```

Additionally, when I try to save the tokenizer, I receive a file with broken encoding:
<img width="374" alt="image" src="https://github.com/huggingface/transformers/assets/65508302/a1018684-bcc5-4033-9d11-a12ba220b19d">


Is there anything I can do to fix the tokenizer training for the Cyrillic corpus? I would be very grateful for any help.



### Expected behavior

I expect the trained tokenizer to yield one single token for one single alphabet character, considering that all these characters were present in the training corpus.

Example:
```
my_tokenizer.encode('б')
# [128000, 272] # for example. it could be any single number.
```

Actual Behavior:
The encoded tokens for the character 'б' are observed as [128000, 272, 260], indicating that it is represented by multiple tokens instead of a single token.

Additional Observations:
When attempting to save the trained tokenizer, I also encountered issues with file encoding, further indicating potential inconsistencies in the training process.
I expect to see valid symbols in the tokenizer.json file, similar to English symbols.
<img width="255" alt="image" src="https://github.com/huggingface/transformers/assets/65508302/9852bc4a-4892-4f52-b4f8-014b5139692f">


Comments:
cc @itazap 

Thanks for your detailed description and code samples, it is very appreciated! 🤗

The Cyrillic character 'б' being represented by multiple tokens such as ['Ð', '±'] is expected behavior and is based on the way Unicode characters are handled by the tokenizer.

In UTF-8, characters can be 1-4 bytes long, and Cyrillic letters like ‘б’ in UTF-8 is encoded in 2 bytes: (see 'б' = '0xd0 0xb1': [Cyrillic table](https://www.utf8-chartable.de/unicode-utf8-table.pl?start=1024&number=128&names=2&utf8=0x))

When the tokenizer represents these bytes it becomes 2 separate characters in the Latin character set (see  '0xd0 0xb1' and '±' : [Latin table](https://www.utf8-chartable.de/unicode-utf8-table.pl?start=128&number=128&names=-&utf8=0x))

So in the tokenization training process, each byte is considered as a separate token initially, so in your sample, the б character might not appear enough to merge together. (See similar issues:
[254](https://github.com/huggingface/tokenizers/issues/254). [203](https://github.com/huggingface/tokenizers/issues/203), [268](https://github.com/huggingface/tokenizers/issues/268))

You can verify that the weird looking tokenization is working correctly using:

encoded = my_tokenizer.encode('б') # [128000, 272, 260] 
decoded = my_tokenizer.decode(encoded) # 'б' - converts back to Cyrillic representation
print(decoded) 

Let me know if you have more questions or experience issues!


@itazap , Thank you for your quick response!
I'm still confused.
**TL;DR**
Byte encoding for 'б' character is not expected, since it did appear in training corpus for several time. It works as expected for `sentencepiece` lib and for `tokenizers` lib.

1. If I understand correctly, you are talking about byte fallback. But I though it happens if the symbol or word is not presented in the corpus at all! However, the "б" letter appeared in toy corpus for several times...
<img width="1294" alt="image" src="https://github.com/huggingface/transformers/assets/65508302/f2150ac8-064a-4916-a065-1c94f3b561c5">

2. Again, I understand it the way that if my vocab_size is big enough, bpe tree should capture all possible separate words, because the bpe tree depth is not limited. So firstly I got alphabet tokens, then all possible pairs, then all possible words. And somehow it doesn't happen, even though vocab_size is 52000 which is more then enough for the toy corpus. 
`my_tokenizer = old_tokenizer.train_new_from_iterator(toy_corpus_ru, 52000)`


3. There is an example code for sentencepiece in this [Colab notebook with examples of unexpected behavior](https://colab.research.google.com/drive/1OTd3ys8TMVcXTRKOy2JW5v2pKL-a9kVo?usp=sharing) .  And it works as expected – 'б' is encoded with single token – 40.  Same applies for tokenizers.Tokenizer. (it is also in the notebook). How come that it works differently in transformers?
<img width="884" alt="image" src="https://github.com/huggingface/transformers/assets/65508302/ed4e3701-48f7-4853-ab58-ca6b5f7c6a3a">

Thanks in advance for your help. 




Hey @Anna-Pinewood ! 

`transformers` uses `tokenizers` as a backend, when you do call `train_from_iterator`.  The example you shared last seems to indicate that `tokenizer.train_from_iterator` works as expected when the `pre_tokenizer` is `Whitespace`. 

Llama3 uses `byte_level` representation, and thus you should set `tokenizer.pre_tokenizer = pre_tokenizers.ByteLevel` you will find that the tokens are indeed different from what you expect, (which is what @itazap mentioned!)

Now the reason why this token is split into 2 different tokens is because of this:
```
{
    "type": "Sequence",
    "pretokenizers": [
      {
        "type": "Split",
        "pattern": {
          "Regex": "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"
        },
        "behavior": "Isolated",
        "invert": false
      },
      {
        "type": "ByteLevel",
        "add_prefix_space": false,
        "trim_offsets": true,
        "use_regex": false
      }
    ]
  },
```
you have the `tiktoken` split pattern as well. I removed it and still did not have a single token for the character you want to have as unique. I believe this is inherent to `byteLevel`, the character is actually two characters in bytelevel, and that combination of two is not frequent enough vs other combination. 

This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md) are likely to be ignored.