echodict/llama.cpp
version https://git-lfs.github.com/spec/v1 oid sha256:cfc44b7ba25614df70e6b65e3341cae0310163bd32fd31a6b928a542df433faf size 30786
0479
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 regex_exprs = {357 "\\p{N}",358 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",359 };360 break;361 case LLAMA_VOCAB_PRE_TYPE_GPT2:362 case LLAMA_VOCAB_PRE_TYPE_MPT:363 case LLAMA_VOCAB_PRE_TYPE_OLMO:364 case LLAMA_VOCAB_PRE_TYPE_JAIS:365 case LLAMA_VOCAB_PRE_TYPE_TRILLION:366 case LLAMA_VOCAB_PRE_TYPE_GRANITE_DOCLING:367 regex_exprs = {368 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",369 };370 break;371 case LLAMA_VOCAB_PRE_TYPE_STABLELM2:372 case LLAMA_VOCAB_PRE_TYPE_QWEN2:373 case LLAMA_VOCAB_PRE_TYPE_HUNYUAN:374 case LLAMA_VOCAB_PRE_TYPE_SOLAR_OPEN:375 regex_exprs = {376 // original regex from tokenizer.json377 // "(?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+"378 "(?:'[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+",379 };380 break;381 case LLAMA_VOCAB_PRE_TYPE_QWEN35:382 regex_exprs = {383 // original regex from tokenizer.json384 // "(?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+"385 "(?:'[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+",386 };387 break;388 case LLAMA_VOCAB_PRE_TYPE_PORO:389 case LLAMA_VOCAB_PRE_TYPE_BLOOM:390 case LLAMA_VOCAB_PRE_TYPE_GPT3_FINNISH:391 regex_exprs = {392 " ?[^(\\s|.,!?…。，、।۔،)]+",393 };394 break;395 case LLAMA_VOCAB_PRE_TYPE_CHATGLM4:396 regex_exprs = {397 "(?:'[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+",398 };399 break;400 case LLAMA_VOCAB_PRE_TYPE_VIKING:401 regex_exprs = {402 " ?[^(\\s|.,!?…。，、।۔،)]+",403 "\\p{N}",404 };405 break;406 case LLAMA_VOCAB_PRE_TYPE_TEKKEN:407 // original regex from tokenizer.json408 // "[^\\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+"409 regex_exprs = {410 "[^\\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+",411 };412 break;413 case LLAMA_VOCAB_PRE_TYPE_CHAMELEON:414 // Note: in theory, the special token (sentinel and image token) regex_exprs below415 // are unnecessary, as they are split in `tokenizer_st_partition` anyway.416 // However, since the upstream pre-tokenizer uses them, they are also417 // included here (see https://huggingface.co/facebook/chameleon-7b).418 regex_exprs = {419 "<sentinel:[0-9]+>", // Sentinel tokens420 "(IMGIMG)((A|B|C|D|E|F|G|H|I){1,4})Z", // Image tokens421 "([\\t\\n]| | )", // directly from tokenizer.json422 "\\p{N}", // Individual digits423 "[\\p{P}!-/:-@\\[-`{-~]", // Punctuation, Isolated424 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",425 };426 break;427 case LLAMA_VOCAB_PRE_TYPE_GPT4O:428 case LLAMA_VOCAB_PRE_TYPE_MINIMAX_M2:429 regex_exprs = {430 // original regex from tokenizer.json431 // "[^\\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+",432 "[^\\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+",433 };434 break;435 case LLAMA_VOCAB_PRE_TYPE_TINY_AYA:436 regex_exprs = {437 // original regex from tokenizer.json: "\\d{1,3}(?=(?:\\d{3})*\\b)"438 "\\d{1,3}(?=(?:\\d{3})*\\b)",439 // 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+"440 "[^\\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+",441 };442 break;443 case LLAMA_VOCAB_PRE_TYPE_KIMI_K2:444 regex_exprs = {445 // K2 trigger pattern - this will activate the custom K2 handler in unicode.cpp446 // The custom handler implements all K2 patterns with proper Han character exclusion447 "\\p{Han}+",448 };449 break;450 case LLAMA_VOCAB_PRE_TYPE_SUPERBPE:451 regex_exprs = {452 "\\p{N}+",453 "(?=(\\d{3})+(?!\\d))",454 };455 break;456 case LLAMA_VOCAB_PRE_TYPE_BAILINGMOE:457 regex_exprs = {458 // original regex from tokenizer.json459 // "'(?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+"460 // FIXME? Changed possessive quantifiers (?+ and ++) to greedy to avoid errors and imatrix hanging (tried atomic grouping but it's not supported?)461 "'(?:[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+",462 };463 break;464 case LLAMA_VOCAB_PRE_TYPE_SEED_CODER:465 regex_exprs = {466 // original regex from tokenizer.json467 // "(?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+"468 "(?:'[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+",469 };470 break;471 case LLAMA_VOCAB_PRE_TYPE_GROK_2:472 regex_exprs = {473 // original regex from tokenizer.json474 // "(?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+"475 "(?:'[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+",476 };477 break;478 case LLAMA_VOCAB_PRE_TYPE_AFMOE:479 regex_exprs = {480 // Digit handling - uses custom implementation in unicode.cpp481 // Groups digits with leading 1-2 based on total length modulo 3482 "\\p{AFMoE_digits}",483 // CJK and Asian scripts (using direct Unicode literals)484 "[一-鿿㐀-䶿豈--ゟ゠-ヿ･-ﾟ⼀-เ--ក-က-႟ꩠ-ꩿꧠ-가-ᄀ-ᇿ]+",485 // Main BPE pattern486 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][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+",487 };488 break;489 case LLAMA_VOCAB_PRE_TYPE_EXAONE_MOE:490 regex_exprs = {491 // original regex from tokenizer.json492 // "(?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+"493 "(?:'[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+",494 };495 break;496 case LLAMA_VOCAB_PRE_TYPE_GEMMA4:497 // Gemma4 uses SPM-style BPE: spaces are replaced with ▁ by the498 // normalizer, then BPE merges run on the whole text without499 // word-level pre-splitting. We only need to split on newlines500 // since BPE merge lookup asserts no newlines in tokens.501 regex_exprs = {502 "[^\\n]+|[\\n]+",503 };504 byte_encode = false; // uses raw UTF-8, not GPT-2 byte encoding505 break;506 default:507 // default regex for BPE tokenization pre-processing508 regex_exprs = {509 "[\\p{P}\\$\\+<=>\\^~\\|]+",510 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",511 "\\p{N}+",512 "[0-9][0-9][0-9]",513 };514 break;515 }516 }517 518 std::vector<std::string> regex_exprs;519 bool byte_encode = true; // GPT-2 byte encoding; false for SPM-style BPE (raw UTF-8)520};521 522struct llm_tokenizer_bpe_session {523 llm_tokenizer_bpe_session(const llama_vocab & vocab, const llm_tokenizer_bpe & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}524 525 static void append(const llama_token token_id, std::vector<llama_token> & output) {526 output.push_back(token_id);527 }528 529 bool append_bos(std::vector<llama_token> & output) const {530 if (vocab.get_add_bos()) {531 GGML_ASSERT(vocab.token_bos() != LLAMA_TOKEN_NULL);532 output.push_back(vocab.token_bos());533 return true;534 }535 return false;536 }537 538 bool append_eos(std::vector<llama_token> & output) const {539 if (vocab.get_add_eos()) {540 GGML_ASSERT(vocab.token_eos() != LLAMA_TOKEN_NULL);541 output.push_back(vocab.token_eos());542 return true;543 }544 return false;545 }546 547 void check_double_bos_eos(const std::vector<llama_token> & output) const {548 if (vocab.get_add_bos() && output.size() >= 2 && output[1] == vocab.token_bos()) {549 LLAMA_LOG_WARN(550 "%s: Added a BOS token to the prompt as specified by the model but the prompt "551 "also starts with a BOS token. So now the final prompt starts with 2 BOS tokens. "552 "Are you sure this is what you want?\n", __FUNCTION__);553 }554 if (vocab.get_add_eos() && output.size() >= 2 && *(output.end()-2) == vocab.token_eos()) {555 LLAMA_LOG_WARN(556 "%s: Added a EOS token to the prompt as specified by the model but the prompt "557 "also ends with a EOS token. So now the final prompt ends with 2 EOS tokens. "558 "Are you sure this is what you want?\n", __FUNCTION__);559 }560 }561 562 void tokenize(const std::string & text, std::vector<llama_token> & output) {563 int final_prev_index = -1;564 const auto word_collection = unicode_regex_split(text, tokenizer.regex_exprs, tokenizer.byte_encode);565 566 symbols_final.clear();567 auto tok_pre = vocab.get_pre_type();568 569 for (const auto & word : word_collection) {570 work_queue = llm_bigram_bpe::queue();571 symbols.clear();572 573 int index = 0;574 size_t offset = 0;575 576 //if (vocab.tokenizer_ignore_merges && vocab.token_to_id.find(word) != vocab.token_to_id.end()) {577 if (vocab.get_ignore_merges() && vocab.text_to_token(word) != LLAMA_TOKEN_NULL) {578 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});579 offset = word.size();580 } else if (tok_pre == LLAMA_VOCAB_PRE_TYPE_GEMMA4 && word.find_first_not_of('\n') == std::string::npos) {581 // fix for gemma 4, ref: https://github.com/ggml-org/llama.cpp/pull/21343582 auto tok = vocab.text_to_token(word);583 if (tok != LLAMA_TOKEN_NULL) {584 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});585 offset = word.size();586 }587 }588 589 while (offset < word.size()) {590 llm_symbol sym;591 size_t char_len = std::min(word.size() - offset, (size_t) unicode_len_utf8(word[offset]));592 sym.text = word.c_str() + offset;593 sym.n = char_len;594 offset += sym.n;595 sym.prev = index - 1;596 sym.next = offset == word.size() ? -1 : index + 1;597 index++;598 symbols.emplace_back(sym);599 }600 for (int i = 1; i < (int) symbols.size(); ++i) {601 add_new_bigram(i - 1, i);602 }603 604 // build token(s)605 while (!work_queue.empty()) {606 auto bigram = work_queue.pop_move();607 608 auto & left_symbol = symbols[bigram.left];609 auto & right_symbol = symbols[bigram.right];610 611 if (left_symbol.n == 0 || right_symbol.n == 0) {612 continue;613 }614 std::string left_token = std::string(left_symbol.text, left_symbol.n);615 std::string right_token = std::string(right_symbol.text, right_symbol.n);616 if (left_token + right_token != bigram.text) {617 continue; // Skip this bigram if it's outdated618 }619 620 // merge the right sym into the left one621 left_symbol.n += right_symbol.n;622 right_symbol.n = 0;623 624 // remove the right sym from the chain625 left_symbol.next = right_symbol.next;626 if (right_symbol.next >= 0) {627 symbols[right_symbol.next].prev = bigram.left;628 }629 630 add_new_bigram(left_symbol.prev, bigram.left); // left side of current symbol631 add_new_bigram(bigram.left, left_symbol.next); // right side of current symbol632 }633 634 // add the finished tokens to the final list keeping correct order for next and prev635 for (auto & sym : symbols) {636 if (sym.n > 0) {637 sym.prev = final_prev_index;638 sym.next = -1;639 if (final_prev_index != -1) {640 symbols_final[final_prev_index].next = symbols_final.size();641 }642 symbols_final.emplace_back(sym);643 final_prev_index = symbols_final.size() - 1;644 }645 }646 }647 648 symbols = symbols_final;649 650 if (!symbols.empty()) {651 for (int i = 0; i != -1; i = symbols[i].next) {652 auto & symbol = symbols[i];653 if (symbol.n == 0) {654 continue;655 }656 657 const std::string str = std::string(symbol.text, symbol.n);658 const auto token = vocab.text_to_token(str);659 660 if (token == LLAMA_TOKEN_NULL) {661 for (auto j = str.begin(); j != str.end(); ++j) {662 llama_token token_multibyte = LLAMA_TOKEN_NULL;663 if (tokenizer.byte_encode) {664 std::string byte_str(1, *j);665 token_multibyte = vocab.text_to_token(byte_str);666 } else {667 // For non-byte-encoded BPE (e.g. gemma-4), byte tokens use <0xXX> format668 static const char * hex = "0123456789ABCDEF";669 const uint8_t ch = (uint8_t)*j;670 const char buf[7] = { '<', '0', 'x', hex[ch >> 4], hex[ch & 15], '>', 0 };671 token_multibyte = vocab.text_to_token(buf);672 }673 if (token_multibyte != LLAMA_TOKEN_NULL) {674 output.push_back(token_multibyte);675 }676 }677 } else {678 output.push_back(token);679 }680 }681 }682 }683 684private:685 void add_new_bigram(int left, int right) {686 if (left == -1 || right == -1) {687 return;688 }689 std::string left_token = std::string(symbols[left].text, symbols[left].n);690 std::string right_token = std::string(symbols[right].text, symbols[right].n);691 692 int rank_found = -1;693 694 rank_found = vocab.find_bpe_rank(left_token, right_token);695 696 if (rank_found < 0) {697 return;698 }699 700 llm_bigram_bpe bigram;701 702 bigram.left = left;703 bigram.right = right;704 bigram.text = left_token + right_token;705 bigram.size = left_token.size() + right_token.size();706 bigram.rank = rank_found;707 708 work_queue.push(bigram);709 }710 711 const llama_vocab & vocab;712 const llm_tokenizer_bpe & tokenizer;713 714 std::vector<llm_symbol> symbols;715 std::vector<llm_symbol> symbols_final;716 llm_bigram_bpe::queue work_queue;717};718 719//720// WPM tokenizer721//722 723struct llm_tokenizer_wpm : llm_tokenizer {724 llm_tokenizer_wpm(const llama_vocab & /*vocab*/) {}725};726 727struct llm_tokenizer_wpm_session {728 llm_tokenizer_wpm_session(const llama_vocab & vocab) : vocab(vocab) {}729 730 void tokenize(const std::string & text, std::vector<llama_token> & output) {731 // normalize and split by whitespace732 std::vector<std::string> words = preprocess(text);733 // bos token prepended already734 735 // find the longest tokens that form the words736 for (const std::string & word : words) {737 // skip empty words738 if (word.size() == 0) {739 continue;740 }741 742 // prepend phantom space743 const std::string word1 = "\xe2\x96\x81" + word;744 const int n = word1.size();745 746 const size_t current_tokens = output.size();747 748 // we're at the start of a new word749 // move through character position in word750 for (int i = 0; i < n; ++i) {751 // loop through possible match length752 bool match = false;753 for (int j = std::min(n, i + vocab.max_token_len() + 1); j > i; j--) {754 auto id = vocab.text_to_token(word1.substr(i, j - i));755 if (id != LLAMA_TOKEN_NULL) {756 output.push_back(id);757 match = true;758 i = j - 1;759 break;760 }761 }762 763 if (!match) { // discard all764 output.resize(current_tokens);765 break; // and discard next tokens766 }767 }768 769 // we didn't find any matches for this word770 if (current_tokens == output.size()) {771 output.push_back(vocab.token_unk());772 }773 }774 }775 776 // TODO: reduce string copies by using cpts_offs array777 static std::vector<std::string> preprocess(const std::string & text) {778 const std::vector<uint32_t> cpts_nfd = unicode_cpts_normalize_nfd(unicode_cpts_from_utf8(text));779 std::vector<std::string> words(1, "");780 781 for (const uint32_t cpt : cpts_nfd) {782 const auto flags = unicode_cpt_flags_from_cpt(cpt);783 784 if (flags.is_whitespace) {785 if (words.back().size()) { // finish previous word if any786 words.emplace_back();787 }788 continue;789 }790 791 assert (!flags.is_separator);792 if (cpt == 0 || cpt == 0xFFFD || flags.is_control) {793 continue;794 }795 796 const std::string s = unicode_cpt_to_utf8(unicode_tolower(cpt));797 if (flags.is_punctuation || ( cpt < 0x7F && flags.is_symbol ) || is_chinese_char(cpt)) {798 if (words.back().size()) { // finish previous word if any799 words.emplace_back();800 }801 words.back() = s; // single char word802 words.emplace_back(); // start a new word803 } else {804 words.back() += s; // append char to word805 }806 }807 808 if (!words.back().size()) {809 words.pop_back();810 }811 812 return words;813 }814 815 static bool is_chinese_char(uint32_t cpt) {816 return817 (cpt >= 0x04E00 && cpt <= 0x09FFF) ||818 (cpt >= 0x03400 && cpt <= 0x04DBF) ||819 (cpt >= 0x20000 && cpt <= 0x2A6DF) ||820 (cpt >= 0x2A700 && cpt <= 0x2B73F) ||821 (cpt >= 0x2B740 && cpt <= 0x2B81F) ||822 (cpt >= 0x2B920 && cpt <= 0x2CEAF) || // this should be 0x2B820 but in hf rust code it is 0x2B920823 (cpt >= 0x0F900 && cpt <= 0x0FAFF) ||824 (cpt >= 0x2F800 && cpt <= 0x2FA1F);825 //(cpt >= 0x3000 && cpt <= 0x303F) ||826 //(cpt >= 0xFF00 && cpt <= 0xFFEF);827 }828 829private:830 const llama_vocab & vocab;831 // currently unused832 // const llm_tokenizer_wpm * wpm_tokenizer;833};834 835//836// UGM tokenizer837//838 839struct llm_tokenizer_ugm : llm_tokenizer {840 llm_tokenizer_ugm(const llama_vocab & vocab, const std::vector<char> & precompiled_charsmap) {841 if (precompiled_charsmap.size() > 0) {842 size_t charsmap_offset = 0;843 844 // First four bytes of precompiled_charsmap contains length of binary845 // blob containing XOR-compressed compact double array (XCDA) entries846 uint32_t xcda_blob_size = *(const uint32_t *) &precompiled_charsmap[0];847 charsmap_offset += sizeof(xcda_blob_size);848 if (xcda_blob_size + charsmap_offset >= precompiled_charsmap.size()) {849 throw std::runtime_error("Index out of array bounds in precompiled charsmap!");850 }851 852 // Next xcda_blob_size bytes contain entries of XOR-compressed compact853 // double array (XCDA). Each entry is bit-packed into a 32-bit integer.854 xcda_array = (const uint32_t *) &precompiled_charsmap[charsmap_offset];855 xcda_array_size = xcda_blob_size / sizeof(uint32_t);856 charsmap_offset += xcda_blob_size;857 858 // Remaining bytes of precompiled charsmap contain null-terminated859 // replacement strings for prefixes matched by the XCDA.860 prefix_replacements = &precompiled_charsmap[charsmap_offset];861 prefix_replacements_size = precompiled_charsmap.size() - charsmap_offset;862 }863 864 for (uint32_t id = 0; id < vocab.n_tokens(); ++id) {865 const auto & token_data = vocab.get_token_data(id);866 867 if (vocab.is_normal(id)) {868 min_score = std::min<float>(min_score, token_data.score);869 max_score = std::max<float>(max_score, token_data.score);870 }871 872 if (vocab.is_normal(id) ||873 vocab.is_user_defined(id) ||874 vocab.is_unused(id)) {875 token_matcher.insert(token_data.text.data(), token_data.text.size(), id);876 }877 878 if (vocab.is_user_defined(id)) {879 user_defined_token_matcher.insert(token_data.text.data(), token_data.text.size());880 }881 }882 883 unknown_token_score = min_score - unknown_token_score_penalty;884 }885 886 // escaped space symbol - U+2581 (Lower One Eighth Block)887 const std::string escaped_space = "\xE2\x96\x81";888 889 const char * prefix_replacements = NULL;890 size_t prefix_replacements_size = 0;891 892 const uint32_t * xcda_array = NULL;893 size_t xcda_array_size = 0;894 895 struct naive_trie user_defined_token_matcher;896 897 float min_score = FLT_MAX;898 float max_score = -FLT_MAX;899 900 float unknown_token_score_penalty = 10.0;901 float unknown_token_score;902 903 struct naive_trie token_matcher;904};905 906struct llm_tokenizer_ugm_session {907 llm_tokenizer_ugm_session(const llama_vocab & vocab, const llm_tokenizer_ugm & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}908 909 /* This implementation is based on SentencePiece optimized Viterbi algorithm for910 * unigram language models. The general idea is to:911 * - move along the input sequence in steps of one UTF code point,912 * - at each step find all possible tokenizations of the prefix by913 * traversing the tokens trie,914 * - for each tokenization store the best one so far (by higher score)915 * - use the position in sequence after given token as an index to store916 * results917 * - if there was no valid tokenization of the current UTF code point918 * then use unknown token with additional score penalty919 * After processing the whole sequence we backtrack from the end to get920 * the best tokenization.921 */922 void tokenize(const std::string & text, std::vector<llama_token> & output) {923 // get current size of output (for reversal later)924 size_t output_size = output.size();925 926 // normalize the input first927 std::string normalized;928 normalize(text, &normalized);929 size_t input_len = normalized.size();930 if (input_len == 0) {931 return;932 }933 934 // initialize score_sum to -FLT_MAX so it will be always lower than sums of token scores935 std::vector<struct best_tokenization> tokenization_results(input_len + 1, {vocab.token_unk(), 0, -DBL_MAX});936 // at the beginning tokenization score is zero937 tokenization_results[0] = { vocab.token_unk(), 0, 0 };938 939 for (size_t input_offset = 0; input_offset < input_len;) {940 size_t prefix_offset = input_offset;941 // calculate how many code units are in the currently processed UTF code point942 size_t n_utf8_code_units = std::min<size_t>(unicode_len_utf8(normalized[input_offset]), input_len - input_offset);943 944 // traverse the token matcher trie to find a matching token945 bool single_codepoint_token_found = false;946 const struct best_tokenization & current_best = tokenization_results[input_offset];947 const struct naive_trie * node = tokenizer.token_matcher.traverse(normalized[prefix_offset++]);948 949 while (prefix_offset <= input_len && node != NULL) {950 // check if we found valid token in prefix951 if (node->has_value) {952 // check if it corresponds to the whole UTF code point953 if (prefix_offset - input_offset == n_utf8_code_units) {954 single_codepoint_token_found = true;955 }956 llama_token token_id = node->value;957 const auto & token_data = vocab.get_token_data(token_id);958 959 // we set the user-defined token scores to 0 to make them more likely to be selected960 // (normal token scores are log probabilities, so they are negative)961 // score type is double here to make tokenization results exactly962 // the same as in the HF tokenizer using SentencePiece963 const double token_score = vocab.is_user_defined(token_id) ? 0.0 : token_data.score;964 const double challenger_score = current_best.score_sum + token_score;965 struct best_tokenization & current_champ = tokenization_results[prefix_offset];966 if (challenger_score > current_champ.score_sum) {967 struct best_tokenization challenger = { token_id, input_offset, challenger_score };968 current_champ = challenger;969 }970 }971 node = node->traverse(normalized[prefix_offset++]);972 }973 974 // if we didn't find a valid token corresponding to the whole UTF code point975 // then use unknown token as the tokenization of this UTF code point976 if (!single_codepoint_token_found) {977 const double challenger_score = current_best.score_sum + tokenizer.unknown_token_score;978 prefix_offset = input_offset + n_utf8_code_units;979 struct best_tokenization & current_champ = tokenization_results[prefix_offset];980 if (challenger_score > current_champ.score_sum) {981 struct best_tokenization challenger = { vocab.token_unk(), input_offset, challenger_score };982 current_champ = challenger;983 }984 }985 986 // move to the next UTF code point987 input_offset += n_utf8_code_units;988 }989 990 // now backtrack from the end to gather token ids of the best tokenization991 // merge sequences of consecutive unknown tokens into single unknown tokens992 bool is_prev_unknown = false;993 for (struct best_tokenization & tokenization = tokenization_results[input_len]; ; tokenization = tokenization_results[tokenization.input_offset]) {994 bool is_unknown = tokenization.token_id == vocab.token_unk();995 if (!(is_prev_unknown && is_unknown)) {996 output.push_back(tokenization.token_id);997 }998 if (tokenization.input_offset == 0) {999 break;1000 }1001 is_prev_unknown = is_unknown;1002 }1003 1004 // reverse the output since we added tokens starting from the end of the input1005 std::reverse(output.begin() + output_size, output.end());1006 }1007 1008private:1009 1010 // helper structure for returning normalization results1011 struct normalization_result {1012 const char * normalized;1013 size_t normalized_len;1014 size_t consumed_input;1015 };1016 1017 void normalize(const std::string& input, std::string * normalized) {1018 normalized->clear();1019 normalized->reserve(input.size() * 3);1020 1021 const std::string space = vocab.get_escape_whitespaces() ? tokenizer.escaped_space : " ";1022 1023 const bool shall_prepend_space = !vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();1024 const bool shall_append_space = vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();1025 const bool shall_merge_spaces = vocab.get_remove_extra_whitespaces();1026 1027 bool is_space_prepended = false;1028 bool processing_non_ws = false;1029 1030 size_t input_len = input.size();1031 1032 for (size_t input_offset = 0; input_offset < input_len; ) {1033 auto norm_res = normalize_prefix(input, input_offset);1034 for (size_t i = 0; i < norm_res.normalized_len; i++) {1035 char c = norm_res.normalized[i];1036 if (c != ' ') {1037 if (!processing_non_ws) {1038 processing_non_ws = true;1039 if ((shall_prepend_space && !is_space_prepended) || shall_merge_spaces) {1040 normalized->append(space);1041 is_space_prepended = true;1042 }1043 }1044 normalized->push_back(c);1045 } else {1046 if (processing_non_ws) {1047 processing_non_ws = false;1048 }1049 if (!shall_merge_spaces) {1050 normalized->append(space);1051 }1052 }1053 }1054 1055 input_offset += norm_res.consumed_input;1056 }1057 1058 if (shall_append_space) {1059 normalized->append(space);1060 }1061 }1062 1063 /*1064 * This structure is a view wrapper for XOR-compressed double array (XCDA)1065 * See Shunsuke Kanda (2018). Space- and Time-Efficient String Dictionaries.1066 * Each bit-packed entry contains:1067 * - BASE array value in bits 10-301068 * - LCHECK array value in bits 0-71069 * - LEAF array value in bit 91070 * Entries containing indexes of replacement sequences have set bit 311071 */1072 struct xcda_array_view {1073 public:1074 xcda_array_view(const uint32_t * xcda_array, size_t xcda_array_size) : xcda_array(xcda_array), xcda_array_size(xcda_array_size) {1075 }1076 uint32_t get_base(size_t index) {1077 uint32_t packed_node = get_node(index);1078 return (packed_node >> 10) << ((packed_node & (1U << 9)) >> 6);1079 }1080 uint32_t get_lcheck(size_t index) {1081 uint32_t packed_node = get_node(index);1082 return packed_node & ((1U << 31) | 0xff);1083 }1084 bool get_leaf(size_t index) {1085 uint32_t packed_node = get_node(index);1086 return (packed_node >> 8) & 1;1087 }1088 uint32_t get_value(size_t index) {1089 uint32_t packed_node = get_node(index);1090 return packed_node & ((1U << 31) - 1);1091 }1092 private:1093 uint32_t get_node(size_t index) {1094 if (index >= xcda_array_size) {1095 throw std::runtime_error("Index out of array bounds in XCDA array!");1096 }1097 return xcda_array[index];1098 }1099 const uint32_t * xcda_array;1100 size_t xcda_array_size;1101 };1102 1103 // this structure stores the best tokenization so far at input_offset1104 struct best_tokenization {1105 llama_token token_id;1106 size_t input_offset;1107 double score_sum;1108 };1109 1110 struct normalization_result normalize_prefix(const std::string & input, size_t input_offset) {1111 if (input_offset == input.size()) {1112 return { &input[input_offset], 0, 0 };1113 }1114 1115 // if input prefix matches some user-defined token return this token as normalization result1116 auto user_defined_token_match =1117 tokenizer.user_defined_token_matcher.get_longest_prefix(&input[input_offset], input.size() - input_offset);1118 if (user_defined_token_match.second > 0) {1119 return { &input[input_offset], user_defined_token_match.second, user_defined_token_match.second };1120 }1121 1122 size_t longest_prefix_length = 0;1123 size_t longest_prefix_offset = 0;1124 1125 if (tokenizer.xcda_array_size > 0) {1126 struct xcda_array_view xcda_view(tokenizer.xcda_array, tokenizer.xcda_array_size);1127 1128 // Find the longest normalized sequence matching the input prefix by walking1129 // the XOR-compressed compact double array (XCDA) starting from the root node1130 // We find the index of the next node by calculating BASE[s] ^ c where s is1131 // the index of the previous node and c is a numerical character value1132 uint32_t node_index = 0;1133 // get BASE of the root node1134 node_index = xcda_view.get_base(node_index);1135 for (size_t prefix_offset = input_offset; prefix_offset < input.size(); prefix_offset++) {1136 unsigned char c = input[prefix_offset];1137 if (c == 0) {1138 break;1139 }1140 node_index ^= c;1141 // if value of LCHECK is not c it means that this is not a child of1142 // the previous node, so we stop matching1143 if (xcda_view.get_lcheck(node_index) != c) {1144 break;1145 }1146 bool is_leaf = xcda_view.get_leaf(node_index);1147 // get BASE of the current node1148 node_index ^= xcda_view.get_base(node_index);1149 // if LEAF of the current node is true, it means that its BASE points to the node1150 // containing index of replacement sequence for currently matched input prefix1151 if (is_leaf)1152 {1153 longest_prefix_length = prefix_offset - input_offset + 1;1154 // get index of replacement sequence for currently matched input prefix1155 longest_prefix_offset = xcda_view.get_value(node_index);1156 }1157 }1158 }1159 1160 if (longest_prefix_length > 0) {1161 // we have a match, so return the replacement sequence1162 if (longest_prefix_offset >= tokenizer.prefix_replacements_size) {1163 throw std::runtime_error("Index out of array bounds in precompiled charsmap!");1164 }1165 const char * prefix_replacement = &(tokenizer.prefix_replacements)[longest_prefix_offset];1166 return { prefix_replacement, strlen(prefix_replacement), longest_prefix_length };1167 }1168 1169 // check if the input prefix contains a valid sequence of UTF-8 code units1170 try {1171 // if yes, return this sequence unmodified1172 size_t prefix_offset = input_offset;1173 unicode_cpt_from_utf8(input, prefix_offset);1174 return { &input[input_offset], prefix_offset - input_offset, prefix_offset - input_offset };1175 } catch (std::invalid_argument & /*ex*/) {1176 // if no, consume 1 byte and return U+FFFD - REPLACEMENT CHARACTER1177 return { "\xEF\xBF\xBD", 3, 1 };1178 }1179 }1180 1181 const llama_vocab & vocab;1182 const llm_tokenizer_ugm & tokenizer;1183};1184 1185//1186// RWKV tokenizer1187//1188 1189static std::vector<uint8_t> llama_unescape_rwkv_token(const std::string & escaped) {1190 std::vector<uint8_t> output;1191 output.reserve(escaped.size());1192 1193 // Parser state1194 bool escaping = false;1195 uint8_t hex_remaining = 0;1196 uint8_t hex_acc = 0;1197 1198 // Step through characters, performing parsing1199 for (const char & c : escaped) {1200 // If we're parsing a hex code, interpret the next character