Brunobkr/llama.cpp_AlgMor24_github
ΩFFFΣLLIa • llama.cpp • AlgMor24 ██████╗ ███████╗███████╗███████╗██╗ ██╗ ██╗ █████╗ ██╔═══██╗██╔════╝██╔════╝██╔════╝██║ ██║ ██║██╔══██╗ ██║ ██║█████╗ █████╗ █████╗ ██║ ██║ ██║███████║ ██║ ██║██╔══╝ ██╔══╝ ██╔══╝ ██║ ██║ ██║██╔══██║ ╚██████╔╝██║ ██║ ███████╗███████╗███████╗██║██║ ██║ ╚═════╝ ╚═╝ ╚═╝ ╚══════╝╚══════╝╚══════╝╚═╝╚═╝ ╚═╝ High-Performance LLM / VLM Inference & Autonomous Agentic Ecosystem… See the full description on the dataset page: https://huggingface.co/datasets/Brunobkr/llama.cpp_AlgMor24_github.
03.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 <forward_list>18#include <limits>19#include <map>20#include <queue>21#include <set>22#include <unordered_map>23 24//25// helpers26//27 28struct naive_trie {29 naive_trie() : has_value(false), value(0) {30 }31 void insert(const char * key, size_t len, int32_t value = 0) {32 if (len == 0) {33 this->has_value = true;34 this->value = value;35 return;36 }37 char c = key[0];38 auto res = children.find(c);39 if (res != children.end()) {40 res->second.insert(key + 1, len - 1, value);41 } else {42 auto res = children.insert(std::make_pair(c, naive_trie()));43 res.first->second.insert(key + 1, len - 1, value);44 }45 }46 std::pair<const char *, size_t> get_longest_prefix(const char * key, size_t len, size_t offset = 0) const {47 if (len == 0 || offset == len) {48 return std::make_pair(key, offset);49 }50 char c = key[offset];51 auto res = children.find(c);52 if (res != children.end()) {53 return res->second.get_longest_prefix(key, len, offset + 1);54 }55 56 return std::make_pair(key, offset);57 }58 const struct naive_trie * traverse(const char c) const {59 auto res = children.find(c);60 if (res != children.end()) {61 return &res->second;62 }63 64 return NULL;65 }66 std::map<char, struct naive_trie> children;67 bool has_value;68 llama_token value;69};70 71//72// tokenizers73//74 75struct llm_tokenizer {76 llm_tokenizer() {}77 virtual ~llm_tokenizer() = default;78};79 80struct llm_symbol {81 using index = int;82 index prev;83 index next;84 const char * text;85 size_t n;86};87 88static_assert(std::is_trivially_copyable<llm_symbol>::value, "llm_symbol is not trivially copyable");89 90//91// SPM tokenizer92// original implementation:93// https://github.com/ggml-org/llama.cpp/commit/074bea2eb1f1349a0118239c4152914aecaa1be494//95 96struct llm_bigram_spm {97 struct comparator {98 bool operator()(llm_bigram_spm & l, llm_bigram_spm & r) {99 return (l.score < r.score) || (l.score == r.score && l.left > r.left);100 }101 };102 using queue_storage = std::vector<llm_bigram_spm>;103 using queue = std::priority_queue<llm_bigram_spm, queue_storage, comparator>;104 llm_symbol::index left;105 llm_symbol::index right;106 float score;107 size_t size;108};109 110struct llm_tokenizer_spm : llm_tokenizer {111 llm_tokenizer_spm(const llama_vocab & /*vocab*/) {}112};113 114struct llm_tokenizer_spm_session {115 llm_tokenizer_spm_session(const llama_vocab & vocab) : vocab(vocab) {}116 117 void tokenize(const std::string & text, std::vector<llama_token> & output) {118 // split string into utf8 chars119 int index = 0;120 size_t offs = 0;121 while (offs < text.size()) {122 llm_symbol sym;123 size_t len = unicode_len_utf8(text[offs]);124 sym.text = text.c_str() + offs;125 sym.n = std::min(len, text.size() - offs);126 offs += sym.n;127 sym.prev = index - 1;128 sym.next = offs == text.size() ? -1 : index + 1;129 index++;130 symbols.emplace_back(sym);131 }132 133 // seed the work queue with all possible 2-character tokens.134 for (int i = 1; i < (int) symbols.size(); ++i) {135 try_add_bigram(i - 1, i);136 }137 138 // keep substituting the highest frequency pairs for as long as we can.139 while (!work_queue.empty()) {140 auto bigram = work_queue.top();141 work_queue.pop();142 143 auto & left_sym = symbols[bigram.left];144 auto & right_sym = symbols[bigram.right];145 146 // if one of the symbols already got merged, skip it.147 if (left_sym.n == 0 || right_sym.n == 0 ||148 left_sym.n + right_sym.n != bigram.size) {149 continue;150 }151 152 // merge the right sym into the left one153 left_sym.n += right_sym.n;154 right_sym.n = 0;155 156 //LLAMA_LOG_INFO("left = '%*s' size = %zu\n", (int) left_sym.n, left_sym.text, bigram.size);157 158 // remove the right sym from the chain159 left_sym.next = right_sym.next;160 if (right_sym.next >= 0) {161 symbols[right_sym.next].prev = bigram.left;162 }163 164 // find more substitutions165 try_add_bigram(left_sym.prev, bigram.left);166 try_add_bigram(bigram.left, left_sym.next);167 }168 169 for (int i = 0; i != -1; i = symbols[i].next) {170 auto & symbol = symbols[i];171 resegment(symbol, output);172 }173 }174 175private:176 void resegment(llm_symbol & symbol, std::vector<llama_token> & output) {177 auto text = std::string(symbol.text, symbol.n);178 auto token = vocab.text_to_token(text);179 180 // Do we need to support is_unused?181 if (token != LLAMA_TOKEN_NULL) {182 output.push_back(token);183 return;184 }185 186 const auto p = rev_merge.find(text);187 188 if (p == rev_merge.end()) {189 // output any symbols that did not form tokens as bytes.190 output.reserve(output.size() + symbol.n);191 for (int j = 0; j < (int)symbol.n; ++j) {192 llama_token id = vocab.byte_to_token(symbol.text[j]);193 output.push_back(id);194 }195 return;196 }197 198 resegment(symbols[p->second.first], output);199 resegment(symbols[p->second.second], output);200 }201 202 void try_add_bigram(int left, int right) {203 if (left == -1 || right == -1) {204 return;205 }206 const std::string text = std::string(symbols[left].text, symbols[left].n + symbols[right].n);207 auto token = vocab.text_to_token(text);208 209 if (token == LLAMA_TOKEN_NULL) {210 return;211 }212 213 if (static_cast<uint32_t>(token) >= vocab.n_tokens()) {214 return;215 }216 217 const auto & tok_data = vocab.get_token_data(token);218 219 llm_bigram_spm bigram;220 bigram.left = left;221 bigram.right = right;222 bigram.score = tok_data.score;223 bigram.size = text.size();224 225 work_queue.push(bigram);226 227 // Do we need to support is_unused?228 rev_merge[text] = std::make_pair(left, right);229 }230 231 const llama_vocab & vocab;232 // currently unused233 // const llm_tokenizer_spm * spm_tokenizer;234 235 std::vector<llm_symbol> symbols;236 llm_bigram_spm::queue work_queue;237 std::map<std::string, std::pair<int, int>> rev_merge;238};239 240//241// BPE tokenizer242// adapted from https://github.com/cmp-nct/ggllm.cpp [MIT License]243// tried to simplify unicode stuff, so most likely does not work 100% correctly!244//245 246// TODO: there are a lot of common parts between spm and bpe tokenizers, should be refactored and reused247 248template<typename T, typename Container = std::vector<T>, typename Compare = std::less<typename Container::value_type>>249class llama_priority_queue : public std::priority_queue<T, Container, Compare> {250public:251 using std::priority_queue<T, Container, Compare>::priority_queue;252 253 T pop_move() {254 T item = std::move(this->c.front());255 std::pop_heap(this->c.begin(), this->c.end(), this->comp);256 this->c.pop_back();257 return item;258 }259 260 void pop() = delete;261};262 263struct llm_bigram_bpe {264 struct comparator {265 bool operator()(const llm_bigram_bpe & l, const llm_bigram_bpe & r) const {266 return l.rank > r.rank || (l.rank == r.rank && l.left > r.left);267 }268 };269 270 using queue_storage = std::vector<llm_bigram_bpe>;271 using queue = llama_priority_queue<llm_bigram_bpe, queue_storage, comparator>;272 llm_symbol::index left;273 llm_symbol::index right;274 std::string text;275 int rank;276 size_t size;277};278 279struct llm_tokenizer_bpe : llm_tokenizer {280 llm_tokenizer_bpe(const llama_vocab & vocab) {281 GGML_ASSERT(vocab.get_type() == LLAMA_VOCAB_TYPE_BPE);282 switch (vocab.get_pre_type()) {283 case LLAMA_VOCAB_PRE_TYPE_LLAMA3:284 regex_exprs = {285 // original regex from tokenizer.json286 //"(?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+",287 288 // adapted: https://github.com/ggml-org/llama.cpp/pull/6920#issuecomment-2080233989289 "(?:'[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+",290 };291 break;292 case LLAMA_VOCAB_PRE_TYPE_JAIS2:293 regex_exprs = {294 // original regex from tokenizer.json295 //"(?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}",296 297 // adapted: same as llama3 but with cascading whitespace pattern298 "(?:'[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}",299 };300 break;301 case LLAMA_VOCAB_PRE_TYPE_DBRX:302 case LLAMA_VOCAB_PRE_TYPE_SMAUG:303 regex_exprs = {304 // same as llama3305 "(?:'[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+",306 };307 break;308 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK_LLM:309 regex_exprs = {310 "[\r\n]",311 "\\s?[A-Za-zµÀ-ÖØ-öø-ƺƼ-ƿDŽ-ʓʕ-ʯͰ-ͳͶͷͻ-ͽͿΆΈ-ΊΌΎ-ΡΣ-ϵϷ-ҁҊ-ԯԱ-ՖႠ-ჅᎠ-Ᏽᏸ-ᏽᲐ-ᲺᲽ-Ჿᴀ-ᴫᵫ-ᵷᵹ-ᶚḀ-ἕἘ-Ἕἠ-ὅὈ-Ὅὐ-ὗὙὛὝὟ-ώᾀ-ᾴᾶ-ᾼιῂ-ῄῆ-ῌῐ-ΐῖ-Ίῠ-Ῥῲ-ῴῶ-ῼℂℇℊ-ℓℕℙ-ℝℤΩℨK-ℭℯ-ℴℹℼ-ℿⅅ-ⅉⅎↃↄⰀ-ⱻⱾ-ⳤⳫ-ⳮⳲⳳꙀ-ꙭꚀ-ꚛꜢ-ꝯꝱ-ꞇꞋ-ꞎꭰ-ꮿff-stﬓ-ﬗＡ-Ｚａ-ｚ𐐀-𐑏𐒰-𐓓𐓘-𐓻𐲀-𐲲𐳀-𐳲𑢠-𑣟𞤀-𞥃]+",312 "\\s?[!-/:-~！-／：-～‘-‟ -。]+",313 "\\s+$",314 "[一-龥ࠀ-一가-]+",315 "\\p{N}+",316 };317 break;318 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK3_LLM:319 case LLAMA_VOCAB_PRE_TYPE_HUNYUAN_DENSE:320 case LLAMA_VOCAB_PRE_TYPE_JOYAI_LLM:321 regex_exprs = {322 "\\p{N}{1,3}",323 "[一-龥-ゟ゠-ヿ]+",324 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][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+",325 };326 break;327 case LLAMA_VOCAB_PRE_TYPE_YOUTU:328 regex_exprs = {329 "[가-힣ㄱ-ㆎ]+|[！…“”‘’—：；，、-〿︰-﹏]+|[ㄅ-ㄯ]+|[一-龥-ゟ゠-ヿ]+",330 "[^\\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+",331 };332 break;333 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK_CODER:334 regex_exprs = {335 "[\r\n]",336 "\\s?\\p{L}+",337 "\\s?\\p{P}+",338 "[一-龥ࠀ-一가-]+",339 "\\p{N}",340 };341 break;342 case LLAMA_VOCAB_PRE_TYPE_FALCON:343 regex_exprs = {344 "[\\p{P}\\$\\+<=>\\^~\\|`]+",345 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",346 "[0-9][0-9][0-9]",347 };348 break;349 case LLAMA_VOCAB_PRE_TYPE_STARCODER:350 case LLAMA_VOCAB_PRE_TYPE_REFACT:351 case LLAMA_VOCAB_PRE_TYPE_COMMAND_R:352 case LLAMA_VOCAB_PRE_TYPE_SMOLLM:353 case LLAMA_VOCAB_PRE_TYPE_CODESHELL:354 case LLAMA_VOCAB_PRE_TYPE_EXAONE:355 case LLAMA_VOCAB_PRE_TYPE_MINERVA:356 case LLAMA_VOCAB_PRE_TYPE_MELLUM2:357 regex_exprs = {358 "\\p{N}",359 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",360 };361 break;362 case LLAMA_VOCAB_PRE_TYPE_GPT2:363 case LLAMA_VOCAB_PRE_TYPE_MPT:364 case LLAMA_VOCAB_PRE_TYPE_OLMO:365 case LLAMA_VOCAB_PRE_TYPE_JAIS:366 case LLAMA_VOCAB_PRE_TYPE_TRILLION:367 case LLAMA_VOCAB_PRE_TYPE_GRANITE_DOCLING:368 regex_exprs = {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_STABLELM2:373 case LLAMA_VOCAB_PRE_TYPE_QWEN2:374 case LLAMA_VOCAB_PRE_TYPE_HUNYUAN:375 case LLAMA_VOCAB_PRE_TYPE_SOLAR_OPEN:376 regex_exprs = {377 // original regex from tokenizer.json378 // "(?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+"379 "(?:'[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+",380 };381 break;382 case LLAMA_VOCAB_PRE_TYPE_QWEN35:383 regex_exprs = {384 // original regex from tokenizer.json385 // "(?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+"386 "(?:'[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+",387 };388 break;389 case LLAMA_VOCAB_PRE_TYPE_PORO:390 case LLAMA_VOCAB_PRE_TYPE_BLOOM:391 case LLAMA_VOCAB_PRE_TYPE_GPT3_FINNISH:392 regex_exprs = {393 " ?[^(\\s|.,!?…。，、।۔،)]+",394 };395 break;396 case LLAMA_VOCAB_PRE_TYPE_CHATGLM4:397 regex_exprs = {398 "(?:'[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+",399 };400 break;401 case LLAMA_VOCAB_PRE_TYPE_VIKING:402 regex_exprs = {403 " ?[^(\\s|.,!?…。，、।۔،)]+",404 "\\p{N}",405 };406 break;407 case LLAMA_VOCAB_PRE_TYPE_TEKKEN:408 // original regex from tokenizer.json409 // "[^\\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+"410 regex_exprs = {411 "[^\\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+",412 };413 break;414 case LLAMA_VOCAB_PRE_TYPE_CHAMELEON:415 // Note: in theory, the special token (sentinel and image token) regex_exprs below416 // are unnecessary, as they are split in `tokenizer_st_partition` anyway.417 // However, since the upstream pre-tokenizer uses them, they are also418 // included here (see https://huggingface.co/facebook/chameleon-7b).419 regex_exprs = {420 "<sentinel:[0-9]+>", // Sentinel tokens421 "(IMGIMG)((A|B|C|D|E|F|G|H|I){1,4})Z", // Image tokens422 "([\\t\\n]| | )", // directly from tokenizer.json423 "\\p{N}", // Individual digits424 "[\\p{P}!-/:-@\\[-`{-~]", // Punctuation, Isolated425 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",426 };427 break;428 case LLAMA_VOCAB_PRE_TYPE_GPT4O:429 case LLAMA_VOCAB_PRE_TYPE_MINIMAX_M2:430 regex_exprs = {431 // original regex from tokenizer.json432 // "[^\\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+",433 "[^\\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+",434 };435 break;436 case LLAMA_VOCAB_PRE_TYPE_GRANITE_EMB_MULTI:437 // Same lookaheads as GPT4O but with \p{M} added so combining marks438 // (diacritics) attach to their base letters. Avoids excessive439 // backtracking on scripts that use them heavily (Bengali, Hindi,440 // Telugu, Thai, ...). See PR #22716 for benchmarks.441 regex_exprs = {442 "[^\\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+",443 };444 break;445 case LLAMA_VOCAB_PRE_TYPE_TINY_AYA:446 regex_exprs = {447 // original regex from tokenizer.json: "\\d{1,3}(?=(?:\\d{3})*\\b)"448 "\\d{1,3}(?=(?:\\d{3})*\\b)",449 // 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+"450 "[^\\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+",451 };452 break;453 case LLAMA_VOCAB_PRE_TYPE_KIMI_K2:454 regex_exprs = {455 // K2 trigger pattern - this will activate the custom K2 handler in unicode.cpp456 // The custom handler implements all K2 patterns with proper Han character exclusion457 "\\p{Han}+",458 };459 break;460 case LLAMA_VOCAB_PRE_TYPE_SUPERBPE:461 regex_exprs = {462 "\\p{N}+",463 "(?=(\\d{3})+(?!\\d))",464 };465 break;466 case LLAMA_VOCAB_PRE_TYPE_BAILINGMOE:467 regex_exprs = {468 // original regex from tokenizer.json469 // "'(?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+"470 // FIXME? Changed possessive quantifiers (?+ and ++) to greedy to avoid errors and imatrix hanging (tried atomic grouping but it's not supported?)471 "'(?:[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+",472 };473 break;474 case LLAMA_VOCAB_PRE_TYPE_SEED_CODER:475 regex_exprs = {476 // original regex from tokenizer.json477 // "(?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+"478 "(?:'[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+",479 };480 break;481 case LLAMA_VOCAB_PRE_TYPE_GROK_2:482 regex_exprs = {483 // original regex from tokenizer.json484 // "(?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+"485 "(?:'[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+",486 };487 break;488 case LLAMA_VOCAB_PRE_TYPE_AFMOE:489 regex_exprs = {490 // Digit handling - uses custom implementation in unicode.cpp491 // Groups digits with leading 1-2 based on total length modulo 3492 "\\p{AFMoE_digits}",493 // CJK and Asian scripts (using direct Unicode literals)494 "[一-鿿㐀-䶿豈--ゟ゠-ヿ･-ﾟ⼀-เ--ក-က-႟ꩠ-ꩿꧠ-가-ᄀ-ᇿ]+",495 // Main BPE pattern496 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][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+",497 };498 break;499 case LLAMA_VOCAB_PRE_TYPE_LAGUNA:500 regex_exprs = {501 "[^\\n]+|[\\n]+",502 "(?:'[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+",503 };504 break;505 case LLAMA_VOCAB_PRE_TYPE_EXAONE_MOE:506 regex_exprs = {507 // original regex from tokenizer.json508 // "(?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+"509 "(?:'[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+",510 };511 break;512 case LLAMA_VOCAB_PRE_TYPE_GEMMA4:513 // Gemma4 uses SPM-style BPE: spaces are replaced with ▁ by the514 // normalizer, then BPE merges run on the whole text without515 // word-level pre-splitting. We only need to split on newlines516 // since BPE merge lookup asserts no newlines in tokens.517 regex_exprs = {518 "[^\\n]+|[\\n]+",519 };520 byte_encode = false; // uses raw UTF-8, not GPT-2 byte encoding521 break;522 case LLAMA_VOCAB_PRE_TYPE_SARVAM_MOE:523 // Sarvam uses SPM-style BPE (same shape as Gemma4): spaces replaced with U+2581524 // by the normalizer, BPE merges over the whole text on raw UTF-8.525 regex_exprs = {526 "[^\\n]+|[\\n]+",527 };528 byte_encode = false;529 break;530 case LLAMA_VOCAB_PRE_TYPE_MINICPM5:531 regex_exprs = {532 // original regex from tokenizer.json (openbmb/MiniCPM5-1B)533 "\\p{N}{1,3}",534 // "(?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+"535 "(?:'[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+",536 };537 break;538 case LLAMA_VOCAB_PRE_TYPE_WHITESPACE:539 // whitespace pre-tokenizer (jinaai/jina-embeddings-v2-base-zh)540 regex_exprs = {541 "\\S+",542 };543 byte_encode = false;544 break;545 default:546 // default regex for BPE tokenization pre-processing547 regex_exprs = {548 "[\\p{P}\\$\\+<=>\\^~\\|]+",549 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",550 "\\p{N}+",551 "[0-9][0-9][0-9]",552 };553 break;554 }555 }556 557 std::vector<std::string> regex_exprs;558 bool byte_encode = true; // GPT-2 byte encoding; false for SPM-style BPE (raw UTF-8)559};560 561struct llm_tokenizer_bpe_session {562 llm_tokenizer_bpe_session(const llama_vocab & vocab, const llm_tokenizer_bpe & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}563 564 virtual ~llm_tokenizer_bpe_session() = default;565 566 static void append(const llama_token token_id, std::vector<llama_token> & output) {567 output.push_back(token_id);568 }569 570 bool append_bos(std::vector<llama_token> & output) const {571 if (vocab.get_add_bos()) {572 GGML_ASSERT(vocab.token_bos() != LLAMA_TOKEN_NULL);573 output.push_back(vocab.token_bos());574 return true;575 }576 return false;577 }578 579 bool append_eos(std::vector<llama_token> & output) const {580 if (vocab.get_add_eos()) {581 GGML_ASSERT(vocab.token_eos() != LLAMA_TOKEN_NULL);582 output.push_back(vocab.token_eos());583 return true;584 }585 return false;586 }587 588 void check_double_bos_eos(const std::vector<llama_token> & output) const {589 if (vocab.get_add_bos() && output.size() >= 2 && output[1] == vocab.token_bos()) {590 LLAMA_LOG_WARN(591 "%s: Added a BOS token to the prompt as specified by the model but the prompt "592 "also starts with a BOS token. So now the final prompt starts with 2 BOS tokens. "593 "Are you sure this is what you want?\n", __FUNCTION__);594 }595 if (vocab.get_add_eos() && output.size() >= 2 && *(output.end()-2) == vocab.token_eos()) {596 LLAMA_LOG_WARN(597 "%s: Added a EOS token to the prompt as specified by the model but the prompt "598 "also ends with a EOS token. So now the final prompt ends with 2 EOS tokens. "599 "Are you sure this is what you want?\n", __FUNCTION__);600 }601 }602 603 virtual void tokenize(const std::string & text, std::vector<llama_token> & output) {604 int final_prev_index = -1;605 const auto word_collection = unicode_regex_split(text, tokenizer.regex_exprs, tokenizer.byte_encode);606 607 symbols_final.clear();608 auto tok_pre = vocab.get_pre_type();609 610 for (const auto & word : word_collection) {611 work_queue = llm_bigram_bpe::queue();612 symbols.clear();613 614 int index = 0;615 size_t offset = 0;616 617 //if (vocab.tokenizer_ignore_merges && vocab.token_to_id.find(word) != vocab.token_to_id.end()) {618 if (vocab.get_ignore_merges() && vocab.text_to_token(word) != LLAMA_TOKEN_NULL) {619 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});620 offset = word.size();621 } else if (tok_pre == LLAMA_VOCAB_PRE_TYPE_GEMMA4 && word.find_first_not_of('\n') == std::string::npos) {622 // fix for gemma 4, ref: https://github.com/ggml-org/llama.cpp/pull/21343623 auto tok = vocab.text_to_token(word);624 if (tok != LLAMA_TOKEN_NULL) {625 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});626 offset = word.size();627 }628 }629 630 while (offset < word.size()) {631 llm_symbol sym;632 size_t char_len = std::min(word.size() - offset, (size_t) unicode_len_utf8(word[offset]));633 sym.text = word.c_str() + offset;634 sym.n = char_len;635 offset += sym.n;636 sym.prev = index - 1;637 sym.next = offset == word.size() ? -1 : index + 1;638 index++;639 symbols.emplace_back(sym);640 }641 for (int i = 1; i < (int) symbols.size(); ++i) {642 add_new_bigram(i - 1, i);643 }644 645 // build token(s)646 while (!work_queue.empty()) {647 auto bigram = work_queue.pop_move();648 649 auto & left_symbol = symbols[bigram.left];650 auto & right_symbol = symbols[bigram.right];651 652 if (left_symbol.n == 0 || right_symbol.n == 0) {653 continue;654 }655 std::string left_token = std::string(left_symbol.text, left_symbol.n);656 std::string right_token = std::string(right_symbol.text, right_symbol.n);657 if (left_token + right_token != bigram.text) {658 continue; // Skip this bigram if it's outdated659 }660 661 // merge the right sym into the left one662 left_symbol.n += right_symbol.n;663 right_symbol.n = 0;664 665 // remove the right sym from the chain666 left_symbol.next = right_symbol.next;667 if (right_symbol.next >= 0) {668 symbols[right_symbol.next].prev = bigram.left;669 }670 671 add_new_bigram(left_symbol.prev, bigram.left); // left side of current symbol672 add_new_bigram(bigram.left, left_symbol.next); // right side of current symbol673 }674 675 // add the finished tokens to the final list keeping correct order for next and prev676 for (auto & sym : symbols) {677 if (sym.n > 0) {678 sym.prev = final_prev_index;679 sym.next = -1;680 if (final_prev_index != -1) {681 symbols_final[final_prev_index].next = symbols_final.size();682 }683 symbols_final.emplace_back(sym);684 final_prev_index = symbols_final.size() - 1;685 }686 }687 }688 689 symbols = symbols_final;690 691 if (!symbols.empty()) {692 for (int i = 0; i != -1; i = symbols[i].next) {693 auto & symbol = symbols[i];694 if (symbol.n == 0) {695 continue;696 }697 698 const std::string str = std::string(symbol.text, symbol.n);699 const auto token = vocab.text_to_token(str);700 701 if (token == LLAMA_TOKEN_NULL) {702 for (auto j = str.begin(); j != str.end(); ++j) {703 llama_token token_multibyte = LLAMA_TOKEN_NULL;704 if (tokenizer.byte_encode) {705 std::string byte_str(1, *j);706 token_multibyte = vocab.text_to_token(byte_str);707 } else {708 // For non-byte-encoded BPE (e.g. gemma-4), byte tokens use <0xXX> format709 static const char * hex = "0123456789ABCDEF";710 const uint8_t ch = (uint8_t)*j;711 const char buf[7] = { '<', '0', 'x', hex[ch >> 4], hex[ch & 15], '>', 0 };712 token_multibyte = vocab.text_to_token(buf);713 }714 if (token_multibyte != LLAMA_TOKEN_NULL) {715 output.push_back(token_multibyte);716 }717 }718 } else {719 output.push_back(token);720 }721 }722 }723 }724 725private:726 void add_new_bigram(int left, int right) {727 if (left == -1 || right == -1) {728 return;729 }730 std::string left_token = std::string(symbols[left].text, symbols[left].n);731 std::string right_token = std::string(symbols[right].text, symbols[right].n);732 733 int rank_found = -1;734 735 rank_found = vocab.find_bpe_rank(left_token, right_token);736 737 if (rank_found < 0) {738 return;739 }740 741 llm_bigram_bpe bigram;742 743 bigram.left = left;744 bigram.right = right;745 bigram.text = left_token + right_token;746 bigram.size = left_token.size() + right_token.size();747 bigram.rank = rank_found;748 749 work_queue.push(bigram);750 }751 752 const llama_vocab & vocab;753 const llm_tokenizer_bpe & tokenizer;754 755 std::vector<llm_symbol> symbols;756 std::vector<llm_symbol> symbols_final;757 llm_bigram_bpe::queue work_queue;758};759 760//761// WPM tokenizer762//763 764struct llm_tokenizer_wpm : llm_tokenizer {765 llm_tokenizer_wpm(const llama_vocab & /*vocab*/) {}766};767 768struct llm_tokenizer_wpm_session {769 llm_tokenizer_wpm_session(const llama_vocab & vocab) : vocab(vocab) {}770 771 void tokenize(const std::string & text, std::vector<llama_token> & output) {772 // normalize and split by whitespace773 std::vector<std::string> words = preprocess(text, vocab.get_normalizer_opts());774 // bos token prepended already775 776 // find the longest tokens that form the words777 for (const std::string & word : words) {778 // skip empty words779 if (word.size() == 0) {780 continue;781 }782 783 // prepend phantom space784 const std::string word1 = "\xe2\x96\x81" + word;785 const int n = word1.size();786 787 const size_t current_tokens = output.size();788 789 // we're at the start of a new word790 // move through character position in word791 for (int i = 0; i < n; ++i) {792 // loop through possible match length793 bool match = false;794 for (int j = std::min(n, i + vocab.max_token_len() + 1); j > i; j--) {795 auto id = vocab.text_to_token(word1.substr(i, j - i));796 if (id != LLAMA_TOKEN_NULL) {797 output.push_back(id);798 match = true;799 i = j - 1;800 break;801 }802 }803 804 if (!match) { // discard all805 output.resize(current_tokens);806 break; // and discard next tokens807 }808 }809 810 // we didn't find any matches for this word811 if (current_tokens == output.size()) {812 output.push_back(vocab.token_unk());813 }814 }815 }816 817 // TODO: reduce string copies by using cpts_offs array818 static std::vector<std::string> preprocess(const std::string & text, const llama_vocab::normalizer_options & normalizer_opts) {819 std::vector<uint32_t> cpts = unicode_cpts_from_utf8(text);820 if (normalizer_opts.strip_accents) {821 cpts = unicode_cpts_normalize_nfd(cpts);822 }823 std::vector<std::string> words(1, "");824 825 for (const uint32_t cpt : cpts) {826 const auto flags = unicode_cpt_flags_from_cpt(cpt);827 828 if (flags.is_whitespace) {829 if (words.back().size()) { // finish previous word if any830 words.emplace_back();831 }832 continue;833 }834 835 assert (!flags.is_separator);836 if (cpt == 0 || cpt == 0xFFFD || flags.is_control) {837 continue;838 }839 840 if (normalizer_opts.strip_accents && flags.is_accent_mark) {841 continue;842 }843 844 const std::string s = unicode_cpt_to_utf8(normalizer_opts.lowercase ? unicode_tolower(cpt) : cpt);845 if (flags.is_punctuation || ( cpt < 0x7F && flags.is_symbol ) || is_chinese_char(cpt)) {846 if (words.back().size()) { // finish previous word if any847 words.emplace_back();848 }849 words.back() = s; // single char word850 words.emplace_back(); // start a new word851 } else {852 words.back() += s; // append char to word853 }854 }855 856 if (!words.back().size()) {857 words.pop_back();858 }859 860 return words;861 }862 863 static bool is_chinese_char(uint32_t cpt) {864 return865 (cpt >= 0x04E00 && cpt <= 0x09FFF) ||866 (cpt >= 0x03400 && cpt <= 0x04DBF) ||867 (cpt >= 0x20000 && cpt <= 0x2A6DF) ||868 (cpt >= 0x2A700 && cpt <= 0x2B73F) ||869 (cpt >= 0x2B740 && cpt <= 0x2B81F) ||870 (cpt >= 0x2B920 && cpt <= 0x2CEAF) || // this should be 0x2B820 but in hf rust code it is 0x2B920871 (cpt >= 0x0F900 && cpt <= 0x0FAFF) ||872 (cpt >= 0x2F800 && cpt <= 0x2FA1F);873 //(cpt >= 0x3000 && cpt <= 0x303F) ||874 //(cpt >= 0xFF00 && cpt <= 0xFFEF);875 }876 877private:878 const llama_vocab & vocab;879 // currently unused880 // const llm_tokenizer_wpm * wpm_tokenizer;881};882 883//884// UGM tokenizer885//886 887struct llm_tokenizer_ugm : llm_tokenizer {888 llm_tokenizer_ugm(const llama_vocab & vocab, const std::vector<char> & precompiled_charsmap) {889 if (precompiled_charsmap.size() > 0) {890 size_t charsmap_offset = 0;891 892 // First four bytes of precompiled_charsmap contains length of binary893 // blob containing XOR-compressed compact double array (XCDA) entries894 uint32_t xcda_blob_size = *(const uint32_t *) &precompiled_charsmap[0];895 charsmap_offset += sizeof(xcda_blob_size);896 897 // Next xcda_blob_size bytes contain entries of XOR-compressed compact898 // double array (XCDA). Each entry is bit-packed into a 32-bit integer.899 xcda_array = (const uint32_t *) &precompiled_charsmap[charsmap_offset];900 xcda_array_size = xcda_blob_size / sizeof(uint32_t);901 charsmap_offset += xcda_blob_size;902 903 // Remaining bytes of precompiled charsmap contain null-terminated904 // replacement strings for prefixes matched by the XCDA.905 prefix_replacements = &precompiled_charsmap[charsmap_offset];906 prefix_replacements_size = precompiled_charsmap.size() - charsmap_offset;907 }908 909 for (uint32_t id = 0; id < vocab.n_tokens(); ++id) {910 const auto & token_data = vocab.get_token_data(id);911 912 if (vocab.is_normal(id)) {913 min_score = std::min<float>(min_score, token_data.score);914 max_score = std::max<float>(max_score, token_data.score);915 }916 917 if (vocab.is_normal(id) ||918 vocab.is_user_defined(id) ||919 vocab.is_unused(id)) {920 token_matcher.insert(token_data.text.data(), token_data.text.size(), id);921 }922 923 if (vocab.is_user_defined(id)) {924 user_defined_token_matcher.insert(token_data.text.data(), token_data.text.size());925 }926 }927 928 unknown_token_score = min_score - unknown_token_score_penalty;929 }930 931 // escaped space symbol - U+2581 (Lower One Eighth Block)932 const std::string escaped_space = "\xE2\x96\x81";933 934 const char * prefix_replacements = NULL;935 size_t prefix_replacements_size = 0;936 937 const uint32_t * xcda_array = NULL;938 size_t xcda_array_size = 0;939 940 struct naive_trie user_defined_token_matcher;941 942 float min_score = FLT_MAX;943 float max_score = -FLT_MAX;944 945 float unknown_token_score_penalty = 10.0;946 float unknown_token_score;947 948 struct naive_trie token_matcher;949};950 951struct llm_tokenizer_ugm_session {952 llm_tokenizer_ugm_session(const llama_vocab & vocab, const llm_tokenizer_ugm & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}953 954 /* This implementation is based on SentencePiece optimized Viterbi algorithm for955 * unigram language models. The general idea is to:956 * - move along the input sequence in steps of one UTF code point,957 * - at each step find all possible tokenizations of the prefix by958 * traversing the tokens trie,959 * - for each tokenization store the best one so far (by higher score)960 * - use the position in sequence after given token as an index to store961 * results962 * - if there was no valid tokenization of the current UTF code point963 * then use unknown token with additional score penalty964 * After processing the whole sequence we backtrack from the end to get965 * the best tokenization.966 */967 void tokenize(const std::string & text, std::vector<llama_token> & output) {968 // get current size of output (for reversal later)969 size_t output_size = output.size();970 971 // normalize the input first972 std::string normalized;973 normalize(text, &normalized);974 size_t input_len = normalized.size();975 if (input_len == 0) {976 return;977 }978 979 // initialize score_sum to -FLT_MAX so it will be always lower than sums of token scores980 std::vector<struct best_tokenization> tokenization_results(input_len + 1, {vocab.token_unk(), 0, -DBL_MAX});981 // at the beginning tokenization score is zero982 tokenization_results[0] = { vocab.token_unk(), 0, 0 };983 984 for (size_t input_offset = 0; input_offset < input_len;) {985 size_t prefix_offset = input_offset;986 // calculate how many code units are in the currently processed UTF code point987 size_t n_utf8_code_units = std::min<size_t>(unicode_len_utf8(normalized[input_offset]), input_len - input_offset);988 989 // traverse the token matcher trie to find a matching token990 bool single_codepoint_token_found = false;991 const struct best_tokenization & current_best = tokenization_results[input_offset];992 const struct naive_trie * node = tokenizer.token_matcher.traverse(normalized[prefix_offset++]);993 994 while (prefix_offset <= input_len && node != NULL) {995 // check if we found valid token in prefix996 if (node->has_value) {997 // check if it corresponds to the whole UTF code point998 if (prefix_offset - input_offset == n_utf8_code_units) {999 single_codepoint_token_found = true;1000 }1001 llama_token token_id = node->value;1002 const auto & token_data = vocab.get_token_data(token_id);1003 1004 // we set the user-defined token scores to 0 to make them more likely to be selected1005 // (normal token scores are log probabilities, so they are negative)1006 // score type is double here to make tokenization results exactly1007 // the same as in the HF tokenizer using SentencePiece1008 const double token_score = vocab.is_user_defined(token_id) ? 0.0 : token_data.score;1009 const double challenger_score = current_best.score_sum + token_score;1010 struct best_tokenization & current_champ = tokenization_results[prefix_offset];1011 if (challenger_score > current_champ.score_sum) {1012 struct best_tokenization challenger = { token_id, input_offset, challenger_score };1013 current_champ = challenger;1014 }1015 }1016 node = node->traverse(normalized[prefix_offset++]);1017 }1018 1019 // if we didn't find a valid token corresponding to the whole UTF code point1020 // then use unknown token as the tokenization of this UTF code point1021 if (!single_codepoint_token_found) {1022 const double challenger_score = current_best.score_sum + tokenizer.unknown_token_score;1023 prefix_offset = input_offset + n_utf8_code_units;1024 struct best_tokenization & current_champ = tokenization_results[prefix_offset];1025 if (challenger_score > current_champ.score_sum) {1026 struct best_tokenization challenger = { vocab.token_unk(), input_offset, challenger_score };1027 current_champ = challenger;1028 }1029 }1030 1031 // move to the next UTF code point1032 input_offset += n_utf8_code_units;1033 }1034 1035 // now backtrack from the end to gather token ids of the best tokenization1036 // merge sequences of consecutive unknown tokens into single unknown tokens1037 bool is_prev_unknown = false;1038 for (struct best_tokenization & tokenization = tokenization_results[input_len]; ; tokenization = tokenization_results[tokenization.input_offset]) {1039 bool is_unknown = tokenization.token_id == vocab.token_unk();1040 if (!(is_prev_unknown && is_unknown)) {1041 output.push_back(tokenization.token_id);1042 }1043 if (tokenization.input_offset == 0) {1044 break;1045 }1046 is_prev_unknown = is_unknown;1047 }1048 1049 // reverse the output since we added tokens starting from the end of the input1050 std::reverse(output.begin() + output_size, output.end());1051 }1052 1053private:1054 1055 // helper structure for returning normalization results1056 struct normalization_result {1057 const char * normalized;1058 size_t normalized_len;1059 size_t consumed_input;1060 };1061 1062 void normalize(const std::string& input, std::string * normalized) {1063 normalized->clear();1064 normalized->reserve(input.size() * 3);1065 1066 const std::string space = vocab.get_escape_whitespaces() ? tokenizer.escaped_space : " ";1067 1068 const bool shall_prepend_space = !vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();1069 const bool shall_append_space = vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();1070 const bool shall_merge_spaces = vocab.get_remove_extra_whitespaces();1071 1072 bool is_space_prepended = false;1073 bool processing_non_ws = false;1074 1075 size_t input_len = input.size();1076 1077 for (size_t input_offset = 0; input_offset < input_len; ) {1078 auto norm_res = normalize_prefix(input, input_offset);1079 for (size_t i = 0; i < norm_res.normalized_len; i++) {1080 char c = norm_res.normalized[i];1081 if (c != ' ') {1082 if (!processing_non_ws) {1083 processing_non_ws = true;1084 if ((shall_prepend_space && !is_space_prepended) || shall_merge_spaces) {1085 normalized->append(space);1086 is_space_prepended = true;1087 }1088 }1089 normalized->push_back(c);1090 } else {1091 if (processing_non_ws) {1092 processing_non_ws = false;1093 }1094 if (!shall_merge_spaces) {1095 normalized->append(space);1096 }1097 }1098 }1099 1100 input_offset += norm_res.consumed_input;1101 }1102 1103 if (shall_append_space) {1104 normalized->append(space);1105 }1106 }1107 1108 /*1109 * This structure is a view wrapper for XOR-compressed double array (XCDA)1110 * See Shunsuke Kanda (2018). Space- and Time-Efficient String Dictionaries.1111 * Each bit-packed entry contains:1112 * - BASE array value in bits 10-301113 * - LCHECK array value in bits 0-71114 * - LEAF array value in bit 91115 * Entries containing indexes of replacement sequences have set bit 311116 */1117 struct xcda_array_view {1118 public:1119 xcda_array_view(const uint32_t * xcda_array, size_t xcda_array_size) : xcda_array(xcda_array), xcda_array_size(xcda_array_size) {1120 }1121 uint32_t get_base(size_t index) {1122 uint32_t packed_node = get_node(index);1123 return (packed_node >> 10) << ((packed_node & (1U << 9)) >> 6);1124 }1125 uint32_t get_lcheck(size_t index) {1126 uint32_t packed_node = get_node(index);1127 return packed_node & ((1U << 31) | 0xff);1128 }1129 bool get_leaf(size_t index) {1130 uint32_t packed_node = get_node(index);1131 return (packed_node >> 8) & 1;1132 }1133 uint32_t get_value(size_t index) {1134 uint32_t packed_node = get_node(index);1135 return packed_node & ((1U << 31) - 1);1136 }1137 private:1138 uint32_t get_node(size_t index) {1139 if (index >= xcda_array_size) {1140 throw std::runtime_error("Index out of array bounds in XCDA array!");1141 }1142 return xcda_array[index];1143 }1144 const uint32_t * xcda_array;1145 size_t xcda_array_size;1146 };1147 1148 // this structure stores the best tokenization so far at input_offset1149 struct best_tokenization {1150 llama_token token_id;1151 size_t input_offset;1152 double score_sum;1153 };1154 1155 struct normalization_result normalize_prefix(const std::string & input, size_t input_offset) {1156 if (input_offset == input.size()) {1157 return { &input[input_offset], 0, 0 };1158 }1159 1160 // if input prefix matches some user-defined token return this token as normalization result1161 auto user_defined_token_match =1162 tokenizer.user_defined_token_matcher.get_longest_prefix(&input[input_offset], input.size() - input_offset);1163 if (user_defined_token_match.second > 0) {1164 return { &input[input_offset], user_defined_token_match.second, user_defined_token_match.second };1165 }1166 1167 size_t longest_prefix_length = 0;1168 size_t longest_prefix_offset = 0;1169 1170 if (tokenizer.xcda_array_size > 0) {1171 struct xcda_array_view xcda_view(tokenizer.xcda_array, tokenizer.xcda_array_size);1172 1173 // Find the longest normalized sequence matching the input prefix by walking1174 // the XOR-compressed compact double array (XCDA) starting from the root node1175 // We find the index of the next node by calculating BASE[s] ^ c where s is1176 // the index of the previous node and c is a numerical character value1177 uint32_t node_index = 0;1178 // get BASE of the root node1179 node_index = xcda_view.get_base(node_index);1180 for (size_t prefix_offset = input_offset; prefix_offset < input.size(); prefix_offset++) {1181 unsigned char c = input[prefix_offset];1182 if (c == 0) {1183 break;1184 }1185 node_index ^= c;1186 // if value of LCHECK is not c it means that this is not a child of1187 // the previous node, so we stop matching1188 if (xcda_view.get_lcheck(node_index) != c) {1189 break;1190 }1191 bool is_leaf = xcda_view.get_leaf(node_index);1192 // get BASE of the current node1193 node_index ^= xcda_view.get_base(node_index);1194 // if LEAF of the current node is true, it means that its BASE points to the node1195 // containing index of replacement sequence for currently matched input prefix1196 if (is_leaf)1197 {1198 longest_prefix_length = prefix_offset - input_offset + 1;1199 // get index of replacement sequence for currently matched input prefix1200 longest_prefix_offset = xcda_view.get_value(node_index);