Felipe97/llama-cpp-compiled
01.1k
1#include "llama-vocab.h"2 3#include "ggml.h"4#include "gguf.h"5#include "llama-impl.h"6#include "llama-model-loader.h"7 8#include "unicode.h"9 10#include <algorithm>11#include <cassert>12#include <cctype>13#include <cfloat>14#include <cmath>15#include <cstdarg>16#include <cstring>17#include <cstdlib>18#include <forward_list>19#include <limits>20#include <map>21#include <queue>22#include <set>23#include <unordered_map>24 25//26// helpers27//28 29struct naive_trie {30 naive_trie() : has_value(false), value(0) {31 }32 void insert(const char * key, size_t len, int32_t value = 0) {33 if (len == 0) {34 this->has_value = true;35 this->value = value;36 return;37 }38 char c = key[0];39 auto res = children.find(c);40 if (res != children.end()) {41 res->second.insert(key + 1, len - 1, value);42 } else {43 auto res = children.insert(std::make_pair(c, naive_trie()));44 res.first->second.insert(key + 1, len - 1, value);45 }46 }47 std::pair<const char *, size_t> get_longest_prefix(const char * key, size_t len, size_t offset = 0) const {48 if (len == 0 || offset == len) {49 return std::make_pair(key, offset);50 }51 char c = key[offset];52 auto res = children.find(c);53 if (res != children.end()) {54 return res->second.get_longest_prefix(key, len, offset + 1);55 }56 57 return std::make_pair(key, offset);58 }59 const struct naive_trie * traverse(const char c) const {60 auto res = children.find(c);61 if (res != children.end()) {62 return &res->second;63 }64 65 return NULL;66 }67 std::map<char, struct naive_trie> children;68 bool has_value;69 llama_token value;70};71 72//73// tokenizers74//75 76struct llm_tokenizer {77 llm_tokenizer() {}78 virtual ~llm_tokenizer() = default;79};80 81struct llm_symbol {82 using index = int;83 index prev;84 index next;85 const char * text;86 size_t n;87};88 89static_assert(std::is_trivially_copyable<llm_symbol>::value, "llm_symbol is not trivially copyable");90 91//92// SPM tokenizer93// original implementation:94// https://github.com/ggml-org/llama.cpp/commit/074bea2eb1f1349a0118239c4152914aecaa1be495//96 97struct llm_bigram_spm {98 struct comparator {99 bool operator()(llm_bigram_spm & l, llm_bigram_spm & r) {100 return (l.score < r.score) || (l.score == r.score && l.left > r.left);101 }102 };103 using queue_storage = std::vector<llm_bigram_spm>;104 using queue = std::priority_queue<llm_bigram_spm, queue_storage, comparator>;105 llm_symbol::index left;106 llm_symbol::index right;107 float score;108 size_t size;109};110 111struct llm_tokenizer_spm : llm_tokenizer {112 llm_tokenizer_spm(const llama_vocab & /*vocab*/) {}113};114 115struct llm_tokenizer_spm_session {116 llm_tokenizer_spm_session(const llama_vocab & vocab) : vocab(vocab) {}117 118 void tokenize(const std::string & text, std::vector<llama_token> & output) {119 // split string into utf8 chars120 int index = 0;121 size_t offs = 0;122 while (offs < text.size()) {123 llm_symbol sym;124 size_t len = unicode_len_utf8(text[offs]);125 sym.text = text.c_str() + offs;126 sym.n = std::min(len, text.size() - offs);127 offs += sym.n;128 sym.prev = index - 1;129 sym.next = offs == text.size() ? -1 : index + 1;130 index++;131 symbols.emplace_back(sym);132 }133 134 // seed the work queue with all possible 2-character tokens.135 for (int i = 1; i < (int) symbols.size(); ++i) {136 try_add_bigram(i - 1, i);137 }138 139 // keep substituting the highest frequency pairs for as long as we can.140 while (!work_queue.empty()) {141 auto bigram = work_queue.top();142 work_queue.pop();143 144 auto & left_sym = symbols[bigram.left];145 auto & right_sym = symbols[bigram.right];146 147 // if one of the symbols already got merged, skip it.148 if (left_sym.n == 0 || right_sym.n == 0 ||149 left_sym.n + right_sym.n != bigram.size) {150 continue;151 }152 153 // merge the right sym into the left one154 left_sym.n += right_sym.n;155 right_sym.n = 0;156 157 //LLAMA_LOG_INFO("left = '%*s' size = %zu\n", (int) left_sym.n, left_sym.text, bigram.size);158 159 // remove the right sym from the chain160 left_sym.next = right_sym.next;161 if (right_sym.next >= 0) {162 symbols[right_sym.next].prev = bigram.left;163 }164 165 // find more substitutions166 try_add_bigram(left_sym.prev, bigram.left);167 try_add_bigram(bigram.left, left_sym.next);168 }169 170 for (int i = 0; i != -1; i = symbols[i].next) {171 auto & symbol = symbols[i];172 resegment(symbol, output);173 }174 }175 176private:177 void resegment(llm_symbol & symbol, std::vector<llama_token> & output) {178 auto text = std::string(symbol.text, symbol.n);179 auto token = vocab.text_to_token(text);180 181 // Do we need to support is_unused?182 if (token != LLAMA_TOKEN_NULL) {183 output.push_back(token);184 return;185 }186 187 const auto p = rev_merge.find(text);188 189 if (p == rev_merge.end()) {190 // output any symbols that did not form tokens as bytes.191 output.reserve(output.size() + symbol.n);192 for (int j = 0; j < (int)symbol.n; ++j) {193 llama_token id = vocab.byte_to_token(symbol.text[j]);194 output.push_back(id);195 }196 return;197 }198 199 resegment(symbols[p->second.first], output);200 resegment(symbols[p->second.second], output);201 }202 203 void try_add_bigram(int left, int right) {204 if (left == -1 || right == -1) {205 return;206 }207 const std::string text = std::string(symbols[left].text, symbols[left].n + symbols[right].n);208 auto token = vocab.text_to_token(text);209 210 if (token == LLAMA_TOKEN_NULL) {211 return;212 }213 214 if (static_cast<uint32_t>(token) >= vocab.n_tokens()) {215 return;216 }217 218 const auto & tok_data = vocab.get_token_data(token);219 220 llm_bigram_spm bigram;221 bigram.left = left;222 bigram.right = right;223 bigram.score = tok_data.score;224 bigram.size = text.size();225 226 work_queue.push(bigram);227 228 // Do we need to support is_unused?229 rev_merge[text] = std::make_pair(left, right);230 }231 232 const llama_vocab & vocab;233 // currently unused234 // const llm_tokenizer_spm * spm_tokenizer;235 236 std::vector<llm_symbol> symbols;237 llm_bigram_spm::queue work_queue;238 std::map<std::string, std::pair<int, int>> rev_merge;239};240 241//242// BPE tokenizer243// adapted from https://github.com/cmp-nct/ggllm.cpp [MIT License]244// tried to simplify unicode stuff, so most likely does not work 100% correctly!245//246 247// TODO: there are a lot of common parts between spm and bpe tokenizers, should be refactored and reused248 249template<typename T, typename Container = std::vector<T>, typename Compare = std::less<typename Container::value_type>>250class llama_priority_queue : public std::priority_queue<T, Container, Compare> {251public:252 using std::priority_queue<T, Container, Compare>::priority_queue;253 254 T pop_move() {255 T item = std::move(this->c.front());256 std::pop_heap(this->c.begin(), this->c.end(), this->comp);257 this->c.pop_back();258 return item;259 }260 261 void pop() = delete;262};263 264struct llm_bigram_bpe {265 struct comparator {266 bool operator()(const llm_bigram_bpe & l, const llm_bigram_bpe & r) const {267 return l.rank > r.rank || (l.rank == r.rank && l.left > r.left);268 }269 };270 271 using queue_storage = std::vector<llm_bigram_bpe>;272 using queue = llama_priority_queue<llm_bigram_bpe, queue_storage, comparator>;273 llm_symbol::index left;274 llm_symbol::index right;275 std::string text;276 int rank;277 size_t size;278};279 280struct llm_tokenizer_bpe : llm_tokenizer {281 llm_tokenizer_bpe(const llama_vocab & vocab) {282 GGML_ASSERT(vocab.get_type() == LLAMA_VOCAB_TYPE_BPE);283 switch (vocab.get_pre_type()) {284 case LLAMA_VOCAB_PRE_TYPE_LLAMA3:285 regex_exprs = {286 // original regex from tokenizer.json287 //"(?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+",288 289 // adapted: https://github.com/ggml-org/llama.cpp/pull/6920#issuecomment-2080233989290 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\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+",291 };292 break;293 case LLAMA_VOCAB_PRE_TYPE_JAIS2:294 regex_exprs = {295 // original regex from tokenizer.json296 //"(?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{512}(?!\\S)|\\s{256}(?!\\S)|\\s{128}(?!\\S)|\\s{64}(?!\\S)|\\s{32}(?!\\S)|\\s{16}(?!\\S)|\\s{8}(?!\\S)|\\s{4}(?!\\S)|\\s{1,2}(?!\\S)|\\s{1}",297 298 // adapted: same as llama3 but with cascading whitespace pattern299 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s{512}(?!\\S)|\\s{256}(?!\\S)|\\s{128}(?!\\S)|\\s{64}(?!\\S)|\\s{32}(?!\\S)|\\s{16}(?!\\S)|\\s{8}(?!\\S)|\\s{4}(?!\\S)|\\s{1,2}(?!\\S)|\\s{1}",300 };301 break;302 case LLAMA_VOCAB_PRE_TYPE_DBRX:303 case LLAMA_VOCAB_PRE_TYPE_SMAUG:304 regex_exprs = {305 // same as llama3306 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\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+",307 };308 break;309 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK_LLM:310 regex_exprs = {311 "[\r\n]",312 "\\s?[A-Za-zµÀ-ÖØ-öø-ƺƼ-ƿDŽ-ʓʕ-ʯͰ-ͳͶͷͻ-ͽͿΆΈ-ΊΌΎ-ΡΣ-ϵϷ-ҁҊ-ԯԱ-ՖႠ-ჅᎠ-Ᏽᏸ-ᏽᲐ-ᲺᲽ-Ჿᴀ-ᴫᵫ-ᵷᵹ-ᶚḀ-ἕἘ-Ἕἠ-ὅὈ-Ὅὐ-ὗὙὛὝὟ-ώᾀ-ᾴᾶ-ᾼιῂ-ῄῆ-ῌῐ-ΐῖ-Ίῠ-Ῥῲ-ῴῶ-ῼℂℇℊ-ℓℕℙ-ℝℤΩℨK-ℭℯ-ℴℹℼ-ℿⅅ-ⅉⅎↃↄⰀ-ⱻⱾ-ⳤⳫ-ⳮⳲⳳꙀ-ꙭꚀ-ꚛꜢ-ꝯꝱ-ꞇꞋ-ꞎꭰ-ꮿff-stﬓ-ﬗＡ-Ｚａ-ｚ𐐀-𐑏𐒰-𐓓𐓘-𐓻𐲀-𐲲𐳀-𐳲𑢠-𑣟𞤀-𞥃]+",313 "\\s?[!-/:-~！-／：-～‘-‟ -。]+",314 "\\s+$",315 "[一-龥ࠀ-一가-]+",316 "\\p{N}+",317 };318 break;319 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK3_LLM:320 case LLAMA_VOCAB_PRE_TYPE_HUNYUAN_DENSE:321 case LLAMA_VOCAB_PRE_TYPE_JOYAI_LLM:322 case LLAMA_VOCAB_PRE_TYPE_HY_V4:323 regex_exprs = {324 "\\p{N}{1,3}",325 "[一-龥-ゟ゠-ヿ]+",326 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][A-Za-z]+|[^\r\n\\p{L}\\p{P}\\p{S}]?[\\p{L}\\p{M}]+| ?[\\p{P}\\p{S}]+[\r\n]*|\\s*[\r\n]+|\\s+(?!\\S)|\\s+",327 };328 break;329 case LLAMA_VOCAB_PRE_TYPE_SPARK2_5:330 regex_exprs = {331 "\\p{N}{1,3}",332 "[一-龥-ゟ゠-ヿ]+",333 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][A-Za-z]+|[^\r\n\\p{L}\\p{P}\\p{S}]?[\\p{L}\\p{M}]+| ?[\\p{P}\\p{S}]+|[\r\n]|\\s+(?!\\S)|\\s+",334 "\\p{N}",335 };336 break;337 case LLAMA_VOCAB_PRE_TYPE_YOUTU:338 regex_exprs = {339 "[가-힣ㄱ-ㆎ]+|[！…“”‘’—：；，、-〿︰-﹏]+|[ㄅ-ㄯ]+|[一-龥-ゟ゠-ヿ]+",340 "[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]*[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]+(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]+[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]*(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",341 };342 break;343 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK_CODER:344 regex_exprs = {345 "[\r\n]",346 "\\s?\\p{L}+",347 "\\s?\\p{P}+",348 "[一-龥ࠀ-一가-]+",349 "\\p{N}",350 };351 break;352 case LLAMA_VOCAB_PRE_TYPE_FALCON:353 regex_exprs = {354 "[\\p{P}\\$\\+<=>\\^~\\|`]+",355 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",356 "[0-9][0-9][0-9]",357 };358 break;359 case LLAMA_VOCAB_PRE_TYPE_STARCODER:360 case LLAMA_VOCAB_PRE_TYPE_REFACT:361 case LLAMA_VOCAB_PRE_TYPE_COMMAND_R:362 case LLAMA_VOCAB_PRE_TYPE_SMOLLM:363 case LLAMA_VOCAB_PRE_TYPE_CODESHELL:364 case LLAMA_VOCAB_PRE_TYPE_EXAONE:365 case LLAMA_VOCAB_PRE_TYPE_MINERVA:366 case LLAMA_VOCAB_PRE_TYPE_MELLUM2:367 regex_exprs = {368 "\\p{N}",369 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",370 };371 break;372 case LLAMA_VOCAB_PRE_TYPE_GPT2:373 case LLAMA_VOCAB_PRE_TYPE_MPT:374 case LLAMA_VOCAB_PRE_TYPE_OLMO:375 case LLAMA_VOCAB_PRE_TYPE_JAIS:376 case LLAMA_VOCAB_PRE_TYPE_TRILLION:377 case LLAMA_VOCAB_PRE_TYPE_GRANITE_DOCLING:378 regex_exprs = {379 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",380 };381 break;382 case LLAMA_VOCAB_PRE_TYPE_STABLELM2:383 case LLAMA_VOCAB_PRE_TYPE_QWEN2:384 case LLAMA_VOCAB_PRE_TYPE_HUNYUAN:385 case LLAMA_VOCAB_PRE_TYPE_SOLAR_OPEN:386 regex_exprs = {387 // original regex from tokenizer.json388 // "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"389 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",390 };391 break;392 case LLAMA_VOCAB_PRE_TYPE_QWEN35:393 regex_exprs = {394 // original regex from tokenizer.json395 // "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?[\\p{L}\\p{M}]+|\\p{N}| ?[^\\s\\p{L}\\p{M}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"396 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?[\\p{L}\\p{M}]+|\\p{N}| ?[^\\s\\p{L}\\p{M}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",397 };398 break;399 case LLAMA_VOCAB_PRE_TYPE_PORO:400 case LLAMA_VOCAB_PRE_TYPE_BLOOM:401 case LLAMA_VOCAB_PRE_TYPE_GPT3_FINNISH:402 regex_exprs = {403 " ?[^(\\s|.,!?…。，、।۔،)]+",404 };405 break;406 case LLAMA_VOCAB_PRE_TYPE_CHATGLM4:407 regex_exprs = {408 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\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+",409 };410 break;411 case LLAMA_VOCAB_PRE_TYPE_VIKING:412 regex_exprs = {413 " ?[^(\\s|.,!?…。，、।۔،)]+",414 "\\p{N}",415 };416 break;417 case LLAMA_VOCAB_PRE_TYPE_TEKKEN:418 // original regex from tokenizer.json419 // "[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]*[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]+|[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]+[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]*|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"420 regex_exprs = {421 "[^\\r\\n\\p{L}\\p{N}]?((?=[\\p{L}])([^a-z]))*((?=[\\p{L}])([^A-Z]))+|[^\\r\\n\\p{L}\\p{N}]?((?=[\\p{L}])([^a-z]))+((?=[\\p{L}])([^A-Z]))*|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",422 };423 break;424 case LLAMA_VOCAB_PRE_TYPE_CHAMELEON:425 // Note: in theory, the special token (sentinel and image token) regex_exprs below426 // are unnecessary, as they are split in `tokenizer_st_partition` anyway.427 // However, since the upstream pre-tokenizer uses them, they are also428 // included here (see https://huggingface.co/facebook/chameleon-7b).429 regex_exprs = {430 "<sentinel:[0-9]+>", // Sentinel tokens431 "(IMGIMG)((A|B|C|D|E|F|G|H|I){1,4})Z", // Image tokens432 "([\\t\\n]| | )", // directly from tokenizer.json433 "\\p{N}", // Individual digits434 "[\\p{P}!-/:-@\\[-`{-~]", // Punctuation, Isolated435 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",436 };437 break;438 case LLAMA_VOCAB_PRE_TYPE_GPT4O:439 case LLAMA_VOCAB_PRE_TYPE_MINIMAX_M2:440 regex_exprs = {441 // original regex from tokenizer.json442 // "[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]*[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]+(?i:'s|'t|'re|'ve|'m|'ll|'d)?|[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]+[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]*(?i:'s|'t|'re|'ve|'m|'ll|'d)?|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",443 "[^\\r\\n\\p{L}\\p{N}]?((?=[\\p{L}])([^a-z]))*((?=[\\p{L}])([^A-Z]))+(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|[^\\r\\n\\p{L}\\p{N}]?((?=[\\p{L}])([^a-z]))+((?=[\\p{L}])([^A-Z]))*(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",444 };445 break;446 case LLAMA_VOCAB_PRE_TYPE_GRANITE_EMB_MULTI:447 // Same lookaheads as GPT4O but with \p{M} added so combining marks448 // (diacritics) attach to their base letters. Avoids excessive449 // backtracking on scripts that use them heavily (Bengali, Hindi,450 // Telugu, Thai, ...). See PR #22716 for benchmarks.451 regex_exprs = {452 "[^\\r\\n\\p{L}\\p{N}]?((?=[\\p{L}\\p{M}])([^a-z]))*((?=[\\p{L}\\p{M}])([^A-Z]))+(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|[^\\r\\n\\p{L}\\p{N}]?((?=[\\p{L}\\p{M}])([^a-z]))+((?=[\\p{L}\\p{M}])([^A-Z]))*(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",453 };454 break;455 case LLAMA_VOCAB_PRE_TYPE_TINY_AYA:456 regex_exprs = {457 // original regex from tokenizer.json: "\\d{1,3}(?=(?:\\d{3})*\\b)"458 "\\d{1,3}(?=(?:\\d{3})*\\b)",459 // original regex from tokenizer.json: "[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]*[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]+(?i:'s|'t|'re|'ve|'m|'ll|'d)?|[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]+[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]*(?i:'s|'t|'re|'ve|'m|'ll|'d)?|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"460 "[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]*[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]+(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|[^\\r\\n\\p{L}\\p{N}]?[\\p{Lu}\\p{Lt}\\p{Lm}\\p{Lo}\\p{M}]+[\\p{Ll}\\p{Lm}\\p{Lo}\\p{M}]*(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])?|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",461 };462 break;463 case LLAMA_VOCAB_PRE_TYPE_KIMI_K2:464 regex_exprs = {465 // K2 trigger pattern - this will activate the custom K2 handler in unicode.cpp466 // The custom handler implements all K2 patterns with proper Han character exclusion467 "\\p{Han}+",468 };469 break;470 case LLAMA_VOCAB_PRE_TYPE_SUPERBPE:471 regex_exprs = {472 "\\p{N}+",473 "(?=(\\d{3})+(?!\\d))",474 };475 break;476 case LLAMA_VOCAB_PRE_TYPE_BAILINGMOE:477 regex_exprs = {478 // original regex from tokenizer.json479 // "'(?i:[sdmt]|ll|ve|re)|[^\\r\\n\\p{L}\\p{N}]?+\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]++[\\r\\n]*|\\s*[\\r\\n]|\\s+(?!\\S)|\\s+"480 // FIXME? Changed possessive quantifiers (?+ and ++) to greedy to avoid errors and imatrix hanging (tried atomic grouping but it's not supported?)481 "'(?:[sSdDmMtT]|[lL][lL]|[vV][eE]|[rR][eE])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]|\\s+(?!\\S)|\\s+",482 };483 break;484 case LLAMA_VOCAB_PRE_TYPE_SEED_CODER:485 regex_exprs = {486 // original regex from tokenizer.json487 // "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\r\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1}| ?[^\\s\\p{L}\\p{N}\r\n]+|\\s*[\r\n]+|\\s+(?!\\S)|\\s+"488 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1}| ?[^\\s\\p{L}\\p{N}\\r\\n]+|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",489 };490 break;491 case LLAMA_VOCAB_PRE_TYPE_UFAKZEKA:492 regex_exprs = {493 // Qwen2 pattern without the English contraction group, so Turkish apostrophe suffixes stay attached494 "[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",495 };496 break;497 case LLAMA_VOCAB_PRE_TYPE_GROK_2:498 regex_exprs = {499 // original regex from tokenizer.json500 // "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"501 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",502 };503 break;504 case LLAMA_VOCAB_PRE_TYPE_AFMOE:505 regex_exprs = {506 // Digit handling - uses custom implementation in unicode.cpp507 // Groups digits with leading 1-2 based on total length modulo 3508 "\\p{AFMoE_digits}",509 // CJK and Asian scripts (using direct Unicode literals)510 "[一-鿿㐀-䶿豈--ゟ゠-ヿ･-ﾟ⼀-เ--ក-က-႟ꩠ-ꩿꧠ-가-ᄀ-ᇿ]+",511 // Main BPE pattern512 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][A-Za-z]+|[^\\r\\n\\p{L}\\p{P}\\p{S}]?[\\p{L}\\p{M}]+| ?[\\p{P}\\p{S}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",513 };514 break;515 case LLAMA_VOCAB_PRE_TYPE_LAGUNA:516 regex_exprs = {517 "[^\\n]+|[\\n]+",518 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",519 };520 break;521 case LLAMA_VOCAB_PRE_TYPE_EXAONE_MOE:522 regex_exprs = {523 // original regex from tokenizer.json524 // "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?(?:\\p{L}\\p{M}*(?: \\p{L}\\p{M}*)*)+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]?|\\s*[\\r\\n]|\\s+(?!\\S)|\\s+"525 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?(?:\\p{L}\\p{M}*(?: \\p{L}\\p{M}*)*)+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n/]?|\\s*[\\r\\n]|\\s+(?!\\S)|\\s+",526 };527 break;528 case LLAMA_VOCAB_PRE_TYPE_GEMMA4:529 // Gemma4 uses SPM-style BPE: spaces are replaced with ▁ by the530 // normalizer, then BPE merges run on the whole text without531 // word-level pre-splitting. We only need to split on newlines532 // since BPE merge lookup asserts no newlines in tokens.533 regex_exprs = {534 "[^\\n]+|[\\n]+",535 };536 byte_encode = false; // uses raw UTF-8, not GPT-2 byte encoding537 break;538 case LLAMA_VOCAB_PRE_TYPE_SARVAM_MOE:539 // Sarvam uses SPM-style BPE (same shape as Gemma4): spaces replaced with U+2581540 // by the normalizer, BPE merges over the whole text on raw UTF-8.541 regex_exprs = {542 "[^\\n]+|[\\n]+",543 };544 byte_encode = false;545 break;546 case LLAMA_VOCAB_PRE_TYPE_MINICPM5:547 regex_exprs = {548 // original regex from tokenizer.json (openbmb/MiniCPM5-1B)549 "\\p{N}{1,3}",550 // "(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}+| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+"551 "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}+| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+",552 };553 break;554 case LLAMA_VOCAB_PRE_TYPE_WHITESPACE:555 // whitespace pre-tokenizer (jinaai/jina-embeddings-v2-base-zh)556 regex_exprs = {557 "\\S+",558 };559 byte_encode = false;560 break;561 default:562 // default regex for BPE tokenization pre-processing563 regex_exprs = {564 "[\\p{P}\\$\\+<=>\\^~\\|]+",565 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",566 "\\p{N}+",567 "[0-9][0-9][0-9]",568 };569 break;570 }571 }572 573 std::vector<std::string> regex_exprs;574 bool byte_encode = true; // GPT-2 byte encoding; false for SPM-style BPE (raw UTF-8)575};576 577struct llm_tokenizer_bpe_session {578 llm_tokenizer_bpe_session(const llama_vocab & vocab, const llm_tokenizer_bpe & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}579 580 virtual ~llm_tokenizer_bpe_session() = default;581 582 static void append(const llama_token token_id, std::vector<llama_token> & output) {583 output.push_back(token_id);584 }585 586 bool append_bos(std::vector<llama_token> & output) const {587 if (vocab.get_add_bos()) {588 GGML_ASSERT(vocab.token_bos() != LLAMA_TOKEN_NULL);589 output.push_back(vocab.token_bos());590 return true;591 }592 return false;593 }594 595 bool append_eos(std::vector<llama_token> & output) const {596 if (vocab.get_add_eos()) {597 GGML_ASSERT(vocab.token_eos() != LLAMA_TOKEN_NULL);598 output.push_back(vocab.token_eos());599 return true;600 }601 return false;602 }603 604 void check_double_bos_eos(const std::vector<llama_token> & output) const {605 if (vocab.get_add_bos() && output.size() >= 2 && output[1] == vocab.token_bos()) {606 LLAMA_LOG_WARN(607 "%s: Added a BOS token to the prompt as specified by the model but the prompt "608 "also starts with a BOS token. So now the final prompt starts with 2 BOS tokens. "609 "Are you sure this is what you want?\n", __FUNCTION__);610 }611 if (vocab.get_add_eos() && output.size() >= 2 && *(output.end()-2) == vocab.token_eos()) {612 LLAMA_LOG_WARN(613 "%s: Added a EOS token to the prompt as specified by the model but the prompt "614 "also ends with a EOS token. So now the final prompt ends with 2 EOS tokens. "615 "Are you sure this is what you want?\n", __FUNCTION__);616 }617 }618 619 virtual void tokenize(const std::string & text, std::vector<llama_token> & output) {620 int final_prev_index = -1;621 const auto word_collection = unicode_regex_split(text, tokenizer.regex_exprs, tokenizer.byte_encode);622 623 symbols_final.clear();624 auto tok_pre = vocab.get_pre_type();625 626 for (const auto & word : word_collection) {627 work_queue = llm_bigram_bpe::queue();628 symbols.clear();629 630 int index = 0;631 size_t offset = 0;632 633 //if (vocab.tokenizer_ignore_merges && vocab.token_to_id.find(word) != vocab.token_to_id.end()) {634 if (vocab.get_ignore_merges() && vocab.text_to_token(word) != LLAMA_TOKEN_NULL) {635 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});636 offset = word.size();637 } else if (tok_pre == LLAMA_VOCAB_PRE_TYPE_GEMMA4 && word.find_first_not_of('\n') == std::string::npos) {638 // fix for gemma 4, ref: https://github.com/ggml-org/llama.cpp/pull/21343639 auto tok = vocab.text_to_token(word);640 if (tok != LLAMA_TOKEN_NULL) {641 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});642 offset = word.size();643 }644 }645 646 while (offset < word.size()) {647 llm_symbol sym;648 size_t char_len = std::min(word.size() - offset, (size_t) unicode_len_utf8(word[offset]));649 sym.text = word.c_str() + offset;650 sym.n = char_len;651 offset += sym.n;652 sym.prev = index - 1;653 sym.next = offset == word.size() ? -1 : index + 1;654 index++;655 symbols.emplace_back(sym);656 }657 for (int i = 1; i < (int) symbols.size(); ++i) {658 add_new_bigram(i - 1, i);659 }660 661 // build token(s)662 while (!work_queue.empty()) {663 auto bigram = work_queue.pop_move();664 665 auto & left_symbol = symbols[bigram.left];666 auto & right_symbol = symbols[bigram.right];667 668 if (left_symbol.n == 0 || right_symbol.n == 0) {669 continue;670 }671 std::string left_token = std::string(left_symbol.text, left_symbol.n);672 std::string right_token = std::string(right_symbol.text, right_symbol.n);673 if (left_token + right_token != bigram.text) {674 continue; // Skip this bigram if it's outdated675 }676 677 // merge the right sym into the left one678 left_symbol.n += right_symbol.n;679 right_symbol.n = 0;680 681 // remove the right sym from the chain682 left_symbol.next = right_symbol.next;683 if (right_symbol.next >= 0) {684 symbols[right_symbol.next].prev = bigram.left;685 }686 687 add_new_bigram(left_symbol.prev, bigram.left); // left side of current symbol688 add_new_bigram(bigram.left, left_symbol.next); // right side of current symbol689 }690 691 // add the finished tokens to the final list keeping correct order for next and prev692 for (auto & sym : symbols) {693 if (sym.n > 0) {694 sym.prev = final_prev_index;695 sym.next = -1;696 if (final_prev_index != -1) {697 symbols_final[final_prev_index].next = symbols_final.size();698 }699 symbols_final.emplace_back(sym);700 final_prev_index = symbols_final.size() - 1;701 }702 }703 }704 705 symbols = symbols_final;706 707 if (!symbols.empty()) {708 for (int i = 0; i != -1; i = symbols[i].next) {709 auto & symbol = symbols[i];710 if (symbol.n == 0) {711 continue;712 }713 714 const std::string str = std::string(symbol.text, symbol.n);715 const auto token = vocab.text_to_token(str);716 717 if (token == LLAMA_TOKEN_NULL) {718 for (auto j = str.begin(); j != str.end(); ++j) {719 llama_token token_multibyte = LLAMA_TOKEN_NULL;720 if (tokenizer.byte_encode) {721 std::string byte_str(1, *j);722 token_multibyte = vocab.text_to_token(byte_str);723 } else {724 // For non-byte-encoded BPE (e.g. gemma-4), byte tokens use <0xXX> format725 static const char * hex = "0123456789ABCDEF";726 const uint8_t ch = (uint8_t)*j;727 const char buf[7] = { '<', '0', 'x', hex[ch >> 4], hex[ch & 15], '>', 0 };728 token_multibyte = vocab.text_to_token(buf);729 }730 if (token_multibyte != LLAMA_TOKEN_NULL) {731 output.push_back(token_multibyte);732 }733 }734 } else {735 output.push_back(token);736 }737 }738 }739 }740 741private:742 void add_new_bigram(int left, int right) {743 if (left == -1 || right == -1) {744 return;745 }746 std::string left_token = std::string(symbols[left].text, symbols[left].n);747 std::string right_token = std::string(symbols[right].text, symbols[right].n);748 749 int rank_found = -1;750 751 rank_found = vocab.find_bpe_rank(left_token, right_token);752 753 if (rank_found < 0) {754 return;755 }756 757 llm_bigram_bpe bigram;758 759 bigram.left = left;760 bigram.right = right;761 bigram.text = left_token + right_token;762 bigram.size = left_token.size() + right_token.size();763 bigram.rank = rank_found;764 765 work_queue.push(bigram);766 }767 768 const llama_vocab & vocab;769 const llm_tokenizer_bpe & tokenizer;770 771 std::vector<llm_symbol> symbols;772 std::vector<llm_symbol> symbols_final;773 llm_bigram_bpe::queue work_queue;774};775 776//777// WPM tokenizer778//779 780struct llm_tokenizer_wpm : llm_tokenizer {781 llm_tokenizer_wpm(const llama_vocab & /*vocab*/) {}782};783 784struct llm_tokenizer_wpm_session {785 llm_tokenizer_wpm_session(const llama_vocab & vocab) : vocab(vocab) {}786 787 void tokenize(const std::string & text, std::vector<llama_token> & output) {788 // normalize and split by whitespace789 std::vector<std::string> words = preprocess(text, vocab.get_normalizer_opts());790 // bos token prepended already791 792 // find the longest tokens that form the words793 for (const std::string & word : words) {794 // skip empty words795 if (word.size() == 0) {796 continue;797 }798 799 // prepend phantom space800 const std::string word1 = "\xe2\x96\x81" + word;801 const int n = word1.size();802 803 const size_t current_tokens = output.size();804 805 // we're at the start of a new word806 // move through character position in word807 for (int i = 0; i < n; ++i) {808 // loop through possible match length809 bool match = false;810 for (int j = std::min(n, i + vocab.max_token_len() + 1); j > i; j--) {811 auto id = vocab.text_to_token(word1.substr(i, j - i));812 if (id != LLAMA_TOKEN_NULL) {813 output.push_back(id);814 match = true;815 i = j - 1;816 break;817 }818 }819 820 if (!match) { // discard all821 output.resize(current_tokens);822 break; // and discard next tokens823 }824 }825 826 // we didn't find any matches for this word827 if (current_tokens == output.size()) {828 output.push_back(vocab.token_unk());829 }830 }831 }832 833 // TODO: reduce string copies by using cpts_offs array834 static std::vector<std::string> preprocess(const std::string & text, const llama_vocab::normalizer_options & normalizer_opts) {835 std::vector<uint32_t> cpts = unicode_cpts_from_utf8(text);836 if (normalizer_opts.strip_accents) {837 cpts = unicode_cpts_normalize_nfd(cpts);838 }839 std::vector<std::string> words(1, "");840 841 for (const uint32_t cpt : cpts) {842 const auto flags = unicode_cpt_flags_from_cpt(cpt);843 844 if (flags.is_whitespace) {845 if (words.back().size()) { // finish previous word if any846 words.emplace_back();847 }848 continue;849 }850 851 assert (!flags.is_separator);852 if (cpt == 0 || cpt == 0xFFFD || flags.is_control) {853 continue;854 }855 856 if (normalizer_opts.strip_accents && flags.is_accent_mark) {857 continue;858 }859 860 const std::string s = unicode_cpt_to_utf8(normalizer_opts.lowercase ? unicode_tolower(cpt) : cpt);861 if (flags.is_punctuation || ( cpt < 0x7F && flags.is_symbol ) || is_chinese_char(cpt)) {862 if (words.back().size()) { // finish previous word if any863 words.emplace_back();864 }865 words.back() = s; // single char word866 words.emplace_back(); // start a new word867 } else {868 words.back() += s; // append char to word869 }870 }871 872 if (!words.back().size()) {873 words.pop_back();874 }875 876 return words;877 }878 879 static bool is_chinese_char(uint32_t cpt) {880 return881 (cpt >= 0x04E00 && cpt <= 0x09FFF) ||882 (cpt >= 0x03400 && cpt <= 0x04DBF) ||883 (cpt >= 0x20000 && cpt <= 0x2A6DF) ||884 (cpt >= 0x2A700 && cpt <= 0x2B73F) ||885 (cpt >= 0x2B740 && cpt <= 0x2B81F) ||886 (cpt >= 0x2B920 && cpt <= 0x2CEAF) || // this should be 0x2B820 but in hf rust code it is 0x2B920887 (cpt >= 0x0F900 && cpt <= 0x0FAFF) ||888 (cpt >= 0x2F800 && cpt <= 0x2FA1F);889 //(cpt >= 0x3000 && cpt <= 0x303F) ||890 //(cpt >= 0xFF00 && cpt <= 0xFFEF);891 }892 893private:894 const llama_vocab & vocab;895 // currently unused896 // const llm_tokenizer_wpm * wpm_tokenizer;897};898 899//900// UGM tokenizer901//902 903struct llm_tokenizer_ugm : llm_tokenizer {904 llm_tokenizer_ugm(const llama_vocab & vocab, const std::vector<char> & precompiled_charsmap) {905 if (precompiled_charsmap.size() > 0) {906 size_t charsmap_offset = 0;907 908 // First four bytes of precompiled_charsmap contains length of binary909 // blob containing XOR-compressed compact double array (XCDA) entries910 uint32_t xcda_blob_size = *(const uint32_t *) &precompiled_charsmap[0];911 charsmap_offset += sizeof(xcda_blob_size);912 913 // Next xcda_blob_size bytes contain entries of XOR-compressed compact914 // double array (XCDA). Each entry is bit-packed into a 32-bit integer.915 xcda_array = (const uint32_t *) &precompiled_charsmap[charsmap_offset];916 xcda_array_size = xcda_blob_size / sizeof(uint32_t);917 charsmap_offset += xcda_blob_size;918 919 // Remaining bytes of precompiled charsmap contain null-terminated920 // replacement strings for prefixes matched by the XCDA.921 prefix_replacements = &precompiled_charsmap[charsmap_offset];922 prefix_replacements_size = precompiled_charsmap.size() - charsmap_offset;923 }924 925 for (uint32_t id = 0; id < vocab.n_tokens(); ++id) {926 const auto & token_data = vocab.get_token_data(id);927 928 if (vocab.is_normal(id)) {929 min_score = std::min<float>(min_score, token_data.score);930 max_score = std::max<float>(max_score, token_data.score);931 }932 933 if (vocab.is_normal(id) ||934 vocab.is_user_defined(id) ||935 vocab.is_unused(id)) {936 token_matcher.insert(token_data.text.data(), token_data.text.size(), id);937 }938 939 if (vocab.is_user_defined(id)) {940 user_defined_token_matcher.insert(token_data.text.data(), token_data.text.size());941 }942 }943 944 unknown_token_score = min_score - unknown_token_score_penalty;945 }946 947 // escaped space symbol - U+2581 (Lower One Eighth Block)948 const std::string escaped_space = "\xE2\x96\x81";949 950 const char * prefix_replacements = NULL;951 size_t prefix_replacements_size = 0;952 953 const uint32_t * xcda_array = NULL;954 size_t xcda_array_size = 0;955 956 struct naive_trie user_defined_token_matcher;957 958 float min_score = FLT_MAX;959 float max_score = -FLT_MAX;960 961 float unknown_token_score_penalty = 10.0;962 float unknown_token_score;963 964 struct naive_trie token_matcher;965};966 967struct llm_tokenizer_ugm_session {968 llm_tokenizer_ugm_session(const llama_vocab & vocab, const llm_tokenizer_ugm & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}969 970 /* This implementation is based on SentencePiece optimized Viterbi algorithm for971 * unigram language models. The general idea is to:972 * - move along the input sequence in steps of one UTF code point,973 * - at each step find all possible tokenizations of the prefix by974 * traversing the tokens trie,975 * - for each tokenization store the best one so far (by higher score)976 * - use the position in sequence after given token as an index to store977 * results978 * - if there was no valid tokenization of the current UTF code point979 * then use unknown token with additional score penalty980 * After processing the whole sequence we backtrack from the end to get981 * the best tokenization.982 */983 void tokenize(const std::string & text, std::vector<llama_token> & output) {984 // get current size of output (for reversal later)985 size_t output_size = output.size();986 987 // normalize the input first988 std::string normalized;989 normalize(text, &normalized);990 size_t input_len = normalized.size();991 if (input_len == 0) {992 return;993 }994 995 // initialize score_sum to -FLT_MAX so it will be always lower than sums of token scores996 std::vector<struct best_tokenization> tokenization_results(input_len + 1, {vocab.token_unk(), 0, -DBL_MAX});997 // at the beginning tokenization score is zero998 tokenization_results[0] = { vocab.token_unk(), 0, 0 };999 1000 for (size_t input_offset = 0; input_offset < input_len;) {1001 size_t prefix_offset = input_offset;1002 // calculate how many code units are in the currently processed UTF code point1003 size_t n_utf8_code_units = std::min<size_t>(unicode_len_utf8(normalized[input_offset]), input_len - input_offset);1004 1005 // traverse the token matcher trie to find a matching token1006 bool single_codepoint_token_found = false;1007 const struct best_tokenization & current_best = tokenization_results[input_offset];1008 const struct naive_trie * node = tokenizer.token_matcher.traverse(normalized[prefix_offset++]);1009 1010 while (prefix_offset <= input_len && node != NULL) {1011 // check if we found valid token in prefix1012 if (node->has_value) {1013 // check if it corresponds to the whole UTF code point1014 if (prefix_offset - input_offset == n_utf8_code_units) {1015 single_codepoint_token_found = true;1016 }1017 llama_token token_id = node->value;1018 const auto & token_data = vocab.get_token_data(token_id);1019 1020 // we set the user-defined token scores to 0 to make them more likely to be selected1021 // (normal token scores are log probabilities, so they are negative)1022 // score type is double here to make tokenization results exactly1023 // the same as in the HF tokenizer using SentencePiece1024 const double token_score = vocab.is_user_defined(token_id) ? 0.0 : token_data.score;1025 const double challenger_score = current_best.score_sum + token_score;1026 struct best_tokenization & current_champ = tokenization_results[prefix_offset];1027 if (challenger_score > current_champ.score_sum) {1028 struct best_tokenization challenger = { token_id, input_offset, challenger_score };1029 current_champ = challenger;1030 }1031 }1032 node = node->traverse(normalized[prefix_offset++]);1033 }1034 1035 // if we didn't find a valid token corresponding to the whole UTF code point1036 // then use unknown token as the tokenization of this UTF code point1037 if (!single_codepoint_token_found) {1038 const double challenger_score = current_best.score_sum + tokenizer.unknown_token_score;1039 prefix_offset = input_offset + n_utf8_code_units;1040 struct best_tokenization & current_champ = tokenization_results[prefix_offset];1041 if (challenger_score > current_champ.score_sum) {1042 struct best_tokenization challenger = { vocab.token_unk(), input_offset, challenger_score };1043 current_champ = challenger;1044 }1045 }1046 1047 // move to the next UTF code point1048 input_offset += n_utf8_code_units;1049 }1050 1051 // now backtrack from the end to gather token ids of the best tokenization1052 // merge sequences of consecutive unknown tokens into single unknown tokens1053 bool is_prev_unknown = false;1054 for (struct best_tokenization & tokenization = tokenization_results[input_len]; ; tokenization = tokenization_results[tokenization.input_offset]) {1055 bool is_unknown = tokenization.token_id == vocab.token_unk();1056 if (!(is_prev_unknown && is_unknown)) {1057 output.push_back(tokenization.token_id);1058 }1059 if (tokenization.input_offset == 0) {1060 break;1061 }1062 is_prev_unknown = is_unknown;1063 }1064 1065 // reverse the output since we added tokens starting from the end of the input1066 std::reverse(output.begin() + output_size, output.end());1067 }1068 1069private:1070 1071 // helper structure for returning normalization results1072 struct normalization_result {1073 const char * normalized;1074 size_t normalized_len;1075 size_t consumed_input;1076 };1077 1078 void normalize(const std::string& input, std::string * normalized) {1079 normalized->clear();1080 normalized->reserve(input.size() * 3);1081 1082 const std::string space = vocab.get_escape_whitespaces() ? tokenizer.escaped_space : " ";1083 1084 const bool shall_prepend_space = !vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();1085 const bool shall_append_space = vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();1086 const bool shall_merge_spaces = vocab.get_remove_extra_whitespaces();1087 1088 bool is_space_prepended = false;1089 bool processing_non_ws = false;1090 1091 size_t input_len = input.size();1092 1093 for (size_t input_offset = 0; input_offset < input_len; ) {1094 auto norm_res = normalize_prefix(input, input_offset);1095 for (size_t i = 0; i < norm_res.normalized_len; i++) {1096 char c = norm_res.normalized[i];1097 if (c != ' ') {1098 if (!processing_non_ws) {1099 processing_non_ws = true;1100 if ((shall_prepend_space && !is_space_prepended) || shall_merge_spaces) {1101 normalized->append(space);1102 is_space_prepended = true;1103 }1104 }1105 normalized->push_back(c);1106 } else {1107 if (processing_non_ws) {1108 processing_non_ws = false;1109 }1110 if (!shall_merge_spaces) {1111 normalized->append(space);1112 }1113 }1114 }1115 1116 input_offset += norm_res.consumed_input;1117 }1118 1119 if (shall_append_space) {1120 normalized->append(space);1121 }1122 }1123 1124 /*1125 * This structure is a view wrapper for XOR-compressed double array (XCDA)1126 * See Shunsuke Kanda (2018). Space- and Time-Efficient String Dictionaries.1127 * Each bit-packed entry contains:1128 * - BASE array value in bits 10-301129 * - LCHECK array value in bits 0-71130 * - LEAF array value in bit 91131 * Entries containing indexes of replacement sequences have set bit 311132 */1133 struct xcda_array_view {1134 public:1135 xcda_array_view(const uint32_t * xcda_array, size_t xcda_array_size) : xcda_array(xcda_array), xcda_array_size(xcda_array_size) {1136 }1137 uint32_t get_base(size_t index) {1138 uint32_t packed_node = get_node(index);1139 return (packed_node >> 10) << ((packed_node & (1U << 9)) >> 6);1140 }1141 uint32_t get_lcheck(size_t index) {1142 uint32_t packed_node = get_node(index);1143 return packed_node & ((1U << 31) | 0xff);1144 }1145 bool get_leaf(size_t index) {1146 uint32_t packed_node = get_node(index);1147 return (packed_node >> 8) & 1;1148 }1149 uint32_t get_value(size_t index) {1150 uint32_t packed_node = get_node(index);1151 return packed_node & ((1U << 31) - 1);1152 }1153 private:1154 uint32_t get_node(size_t index) {1155 if (index >= xcda_array_size) {1156 throw std::runtime_error("Index out of array bounds in XCDA array!");1157 }1158 return xcda_array[index];1159 }1160 const uint32_t * xcda_array;1161 size_t xcda_array_size;1162 };1163 1164 // this structure stores the best tokenization so far at input_offset1165 struct best_tokenization {1166 llama_token token_id;1167 size_t input_offset;1168 double score_sum;1169 };1170 1171 struct normalization_result normalize_prefix(const std::string & input, size_t input_offset) {1172 if (input_offset == input.size()) {1173 return { &input[input_offset], 0, 0 };1174 }1175 1176 // if input prefix matches some user-defined token return this token as normalization result1177 auto user_defined_token_match =1178 tokenizer.user_defined_token_matcher.get_longest_prefix(&input[input_offset], input.size() - input_offset);1179 if (user_defined_token_match.second > 0) {1180 return { &input[input_offset], user_defined_token_match.second, user_defined_token_match.second };1181 }1182 1183 size_t longest_prefix_length = 0;1184 size_t longest_prefix_offset = 0;1185 1186 if (tokenizer.xcda_array_size > 0) {1187 struct xcda_array_view xcda_view(tokenizer.xcda_array, tokenizer.xcda_array_size);1188 1189 // Find the longest normalized sequence matching the input prefix by walking1190 // the XOR-compressed compact double array (XCDA) starting from the root node1191 // We find the index of the next node by calculating BASE[s] ^ c where s is1192 // the index of the previous node and c is a numerical character value1193 uint32_t node_index = 0;1194 // get BASE of the root node1195 node_index = xcda_view.get_base(node_index);1196 for (size_t prefix_offset = input_offset; prefix_offset < input.size(); prefix_offset++) {1197 unsigned char c = input[prefix_offset];1198 if (c == 0) {1199 break;1200 }