KBaba7/llama.cpp
0
1#include "llama-vocab.h"2 3#include "llama-impl.h"4#include "llama-model-loader.h"5 6#include "unicode.h"7 8#include <algorithm>9#include <cassert>10#include <cfloat>11#include <climits>12#include <cstdarg>13#include <cstring>14#include <forward_list>15#include <map>16#include <queue>17#include <set>18#include <unordered_map>19 20//21// helpers22//23 24struct naive_trie {25 naive_trie() : has_value(false), value(0) {26 }27 void insert(const char * key, size_t len, int32_t value = 0) {28 if (len == 0) {29 this->has_value = true;30 this->value = value;31 return;32 }33 char c = key[0];34 auto res = children.find(c);35 if (res != children.end()) {36 res->second.insert(key + 1, len - 1, value);37 } else {38 auto res = children.insert(std::make_pair(c, naive_trie()));39 res.first->second.insert(key + 1, len - 1, value);40 }41 }42 std::pair<const char *, size_t> get_longest_prefix(const char * key, size_t len, size_t offset = 0) const {43 if (len == 0 || offset == len) {44 return std::make_pair(key, offset);45 }46 char c = key[offset];47 auto res = children.find(c);48 if (res != children.end()) {49 return res->second.get_longest_prefix(key, len, offset + 1);50 }51 52 return std::make_pair(key, offset);53 }54 const struct naive_trie * traverse(const char c) const {55 auto res = children.find(c);56 if (res != children.end()) {57 return &res->second;58 }59 60 return NULL;61 }62 std::map<char, struct naive_trie> children;63 bool has_value;64 llama_token value;65};66 67//68// tokenizers69//70 71struct llm_tokenizer {72 llm_tokenizer() {}73 virtual ~llm_tokenizer() = default;74};75 76struct llm_symbol {77 using index = int;78 index prev;79 index next;80 const char * text;81 size_t n;82};83 84static_assert(std::is_trivially_copyable<llm_symbol>::value, "llm_symbol is not trivially copyable");85 86//87// SPM tokenizer88// original implementation:89// https://github.com/ggerganov/llama.cpp/commit/074bea2eb1f1349a0118239c4152914aecaa1be490//91 92struct llm_bigram_spm {93 struct comparator {94 bool operator()(llm_bigram_spm & l, llm_bigram_spm & r) {95 return (l.score < r.score) || (l.score == r.score && l.left > r.left);96 }97 };98 using queue_storage = std::vector<llm_bigram_spm>;99 using queue = std::priority_queue<llm_bigram_spm, queue_storage, comparator>;100 llm_symbol::index left;101 llm_symbol::index right;102 float score;103 size_t size;104};105 106struct llm_tokenizer_spm : llm_tokenizer {107 llm_tokenizer_spm(const llama_vocab & /*vocab*/) {}108};109 110struct llm_tokenizer_spm_session {111 llm_tokenizer_spm_session(const llama_vocab & vocab) : vocab(vocab) {}112 113 void tokenize(const std::string & text, std::vector<llama_token> & output) {114 // split string into utf8 chars115 int index = 0;116 size_t offs = 0;117 while (offs < text.size()) {118 llm_symbol sym;119 size_t len = unicode_len_utf8(text[offs]);120 sym.text = text.c_str() + offs;121 sym.n = std::min(len, text.size() - offs);122 offs += sym.n;123 sym.prev = index - 1;124 sym.next = offs == text.size() ? -1 : index + 1;125 index++;126 symbols.emplace_back(sym);127 }128 129 // seed the work queue with all possible 2-character tokens.130 for (int i = 1; i < (int) symbols.size(); ++i) {131 try_add_bigram(i - 1, i);132 }133 134 // keep substituting the highest frequency pairs for as long as we can.135 while (!work_queue.empty()) {136 auto bigram = work_queue.top();137 work_queue.pop();138 139 auto & left_sym = symbols[bigram.left];140 auto & right_sym = symbols[bigram.right];141 142 // if one of the symbols already got merged, skip it.143 if (left_sym.n == 0 || right_sym.n == 0 ||144 left_sym.n + right_sym.n != bigram.size) {145 continue;146 }147 148 // merge the right sym into the left one149 left_sym.n += right_sym.n;150 right_sym.n = 0;151 152 //LLAMA_LOG_INFO("left = '%*s' size = %zu\n", (int) left_sym.n, left_sym.text, bigram.size);153 154 // remove the right sym from the chain155 left_sym.next = right_sym.next;156 if (right_sym.next >= 0) {157 symbols[right_sym.next].prev = bigram.left;158 }159 160 // find more substitutions161 try_add_bigram(left_sym.prev, bigram.left);162 try_add_bigram(bigram.left, left_sym.next);163 }164 165 for (int i = 0; i != -1; i = symbols[i].next) {166 auto & symbol = symbols[i];167 resegment(symbol, output);168 }169 }170 171private:172 void resegment(llm_symbol & symbol, std::vector<llama_token> & output) {173 auto text = std::string(symbol.text, symbol.n);174 auto token = vocab.text_to_token(text);175 176 // Do we need to support is_unused?177 if (token != LLAMA_TOKEN_NULL) {178 output.push_back(token);179 return;180 }181 182 const auto p = rev_merge.find(text);183 184 if (p == rev_merge.end()) {185 // output any symbols that did not form tokens as bytes.186 output.reserve(output.size() + symbol.n);187 for (int j = 0; j < (int)symbol.n; ++j) {188 llama_token id = vocab.byte_to_token(symbol.text[j]);189 output.push_back(id);190 }191 return;192 }193 194 resegment(symbols[p->second.first], output);195 resegment(symbols[p->second.second], output);196 }197 198 void try_add_bigram(int left, int right) {199 if (left == -1 || right == -1) {200 return;201 }202 const std::string text = std::string(symbols[left].text, symbols[left].n + symbols[right].n);203 auto token = vocab.text_to_token(text);204 205 if (token == LLAMA_TOKEN_NULL) {206 return;207 }208 209 if (static_cast<uint32_t>(token) >= vocab.n_tokens()) {210 return;211 }212 213 const auto & tok_data = vocab.get_token_data(token);214 215 llm_bigram_spm bigram;216 bigram.left = left;217 bigram.right = right;218 bigram.score = tok_data.score;219 bigram.size = text.size();220 221 work_queue.push(bigram);222 223 // Do we need to support is_unused?224 rev_merge[text] = std::make_pair(left, right);225 }226 227 const llama_vocab & vocab;228 // currently unused229 // const llm_tokenizer_spm * spm_tokenizer;230 231 std::vector<llm_symbol> symbols;232 llm_bigram_spm::queue work_queue;233 std::map<std::string, std::pair<int, int>> rev_merge;234};235 236//237// BPE tokenizer238// adapted from https://github.com/cmp-nct/ggllm.cpp [MIT License]239// tried to simplify unicode stuff, so most likely does not work 100% correctly!240//241 242// TODO: there are a lot of common parts between spm and bpe tokenizers, should be refactored and reused243 244template<typename T, typename Container = std::vector<T>, typename Compare = std::less<typename Container::value_type>>245class llama_priority_queue : public std::priority_queue<T, Container, Compare> {246public:247 using std::priority_queue<T, Container, Compare>::priority_queue;248 249 T pop_move() {250 T item = std::move(this->c.front());251 std::pop_heap(this->c.begin(), this->c.end(), this->comp);252 this->c.pop_back();253 return item;254 }255 256 void pop() = delete;257};258 259struct llm_bigram_bpe {260 struct comparator {261 bool operator()(const llm_bigram_bpe & l, const llm_bigram_bpe & r) const {262 return l.rank > r.rank || (l.rank == r.rank && l.left > r.left);263 }264 };265 266 using queue_storage = std::vector<llm_bigram_bpe>;267 using queue = llama_priority_queue<llm_bigram_bpe, queue_storage, comparator>;268 llm_symbol::index left;269 llm_symbol::index right;270 std::string text;271 int rank;272 size_t size;273};274 275struct llm_tokenizer_bpe : llm_tokenizer {276 llm_tokenizer_bpe(const llama_vocab & vocab) {277 GGML_ASSERT(vocab.get_type() == LLAMA_VOCAB_TYPE_BPE);278 switch (vocab.get_pre_type()) {279 case LLAMA_VOCAB_PRE_TYPE_LLAMA3:280 regex_exprs = {281 // original regex from tokenizer.json282 //"(?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+",283 284 // adapted: https://github.com/ggerganov/llama.cpp/pull/6920#issuecomment-2080233989285 "(?:'[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+",286 };287 break;288 case LLAMA_VOCAB_PRE_TYPE_DBRX:289 case LLAMA_VOCAB_PRE_TYPE_SMAUG:290 regex_exprs = {291 // same as llama3292 "(?:'[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+",293 };294 break;295 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK_LLM:296 regex_exprs = {297 "[\r\n]",298 "\\s?[A-Za-zµÀ-ÖØ-öø-ƺƼ-ƿDŽ-ʓʕ-ʯͰ-ͳͶͷͻ-ͽͿΆΈ-ΊΌΎ-ΡΣ-ϵϷ-ҁҊ-ԯԱ-ՖႠ-ჅᎠ-Ᏽᏸ-ᏽᲐ-ᲺᲽ-Ჿᴀ-ᴫᵫ-ᵷᵹ-ᶚḀ-ἕἘ-Ἕἠ-ὅὈ-Ὅὐ-ὗὙὛὝὟ-ώᾀ-ᾴᾶ-ᾼιῂ-ῄῆ-ῌῐ-ΐῖ-Ίῠ-Ῥῲ-ῴῶ-ῼℂℇℊ-ℓℕℙ-ℝℤΩℨK-ℭℯ-ℴℹℼ-ℿⅅ-ⅉⅎↃↄⰀ-ⱻⱾ-ⳤⳫ-ⳮⳲⳳꙀ-ꙭꚀ-ꚛꜢ-ꝯꝱ-ꞇꞋ-ꞎꭰ-ꮿff-stﬓ-ﬗＡ-Ｚａ-ｚ𐐀-𐑏𐒰-𐓓𐓘-𐓻𐲀-𐲲𐳀-𐳲𑢠-𑣟𞤀-𞥃]+",299 "\\s?[!-/:-~！-／：-～‘-‟ -。]+",300 "\\s+$",301 "[一-龥ࠀ-一가-]+",302 "\\p{N}+",303 };304 break;305 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK3_LLM:306 regex_exprs = {307 "\\p{N}{1,3}",308 "[一-龥-ゟ゠-ヿ]+",309 "[!\"#$%&'()*+,\\-./:;<=>?@\\[\\\\\\]^_`{|}~][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+",310 };311 break;312 case LLAMA_VOCAB_PRE_TYPE_DEEPSEEK_CODER:313 regex_exprs = {314 "[\r\n]",315 "\\s?\\p{L}+",316 "\\s?\\p{P}+",317 "[一-龥ࠀ-一가-]+",318 "\\p{N}",319 };320 break;321 case LLAMA_VOCAB_PRE_TYPE_FALCON:322 regex_exprs = {323 "[\\p{P}\\$\\+<=>\\^~\\|`]+",324 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",325 "[0-9][0-9][0-9]",326 };327 break;328 case LLAMA_VOCAB_PRE_TYPE_STARCODER:329 case LLAMA_VOCAB_PRE_TYPE_REFACT:330 case LLAMA_VOCAB_PRE_TYPE_COMMAND_R:331 case LLAMA_VOCAB_PRE_TYPE_SMOLLM:332 case LLAMA_VOCAB_PRE_TYPE_CODESHELL:333 case LLAMA_VOCAB_PRE_TYPE_EXAONE:334 case LLAMA_VOCAB_PRE_TYPE_MINERVA:335 regex_exprs = {336 "\\p{N}",337 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",338 };339 break;340 case LLAMA_VOCAB_PRE_TYPE_GPT2:341 case LLAMA_VOCAB_PRE_TYPE_MPT:342 case LLAMA_VOCAB_PRE_TYPE_OLMO:343 case LLAMA_VOCAB_PRE_TYPE_JAIS:344 regex_exprs = {345 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",346 };347 break;348 case LLAMA_VOCAB_PRE_TYPE_STABLELM2:349 case LLAMA_VOCAB_PRE_TYPE_QWEN2:350 regex_exprs = {351 // original regex from tokenizer.json352 // "(?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+"353 "(?:'[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+",354 };355 break;356 case LLAMA_VOCAB_PRE_TYPE_PORO:357 case LLAMA_VOCAB_PRE_TYPE_BLOOM:358 case LLAMA_VOCAB_PRE_TYPE_GPT3_FINNISH:359 regex_exprs = {360 " ?[^(\\s|.,!?…。，、।۔،)]+",361 };362 break;363 case LLAMA_VOCAB_PRE_TYPE_CHATGLM4:364 regex_exprs = {365 "(?:'[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+",366 };367 break;368 case LLAMA_VOCAB_PRE_TYPE_VIKING:369 regex_exprs = {370 " ?[^(\\s|.,!?…。，、।۔،)]+",371 "\\p{N}",372 };373 break;374 case LLAMA_VOCAB_PRE_TYPE_TEKKEN:375 // original regex from tokenizer.json376 // "[^\\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+"377 regex_exprs = {378 "[^\\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+",379 };380 break;381 case LLAMA_VOCAB_PRE_TYPE_CHAMELEON:382 // Note: in theory, the special token (sentinel and image token) regex_exprs below383 // are unnecessary, as they are split in `tokenizer_st_partition` anyway.384 // However, since the upstream pre-tokenizer uses them, they are also385 // included here (see https://huggingface.co/facebook/chameleon-7b).386 regex_exprs = {387 "<sentinel:[0-9]+>", // Sentinel tokens388 "(IMGIMG)((A|B|C|D|E|F|G|H|I){1,4})Z", // Image tokens389 "([\\t\\n]| | )", // directly from tokenizer.json390 "\\p{N}", // Individual digits391 "[\\p{P}!-/:-@\\[-`{-~]", // Punctuation, Isolated392 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",393 };394 break;395 default:396 // default regex for BPE tokenization pre-processing397 regex_exprs = {398 "[\\p{P}\\$\\+<=>\\^~\\|]+",399 "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)",400 "\\p{N}+",401 "[0-9][0-9][0-9]",402 };403 break;404 }405 }406 407 std::vector<std::string> regex_exprs;408};409 410struct llm_tokenizer_bpe_session {411 llm_tokenizer_bpe_session(const llama_vocab & vocab, const llm_tokenizer_bpe & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}412 413 static void append(const llama_token token_id, std::vector<llama_token> & output) {414 output.push_back(token_id);415 }416 417 bool append_bos(std::vector<llama_token> & output) const {418 if (vocab.get_add_bos()) {419 GGML_ASSERT(vocab.token_bos() != LLAMA_TOKEN_NULL);420 output.push_back(vocab.token_bos());421 return true;422 }423 return false;424 }425 426 bool append_eos(std::vector<llama_token> & output) const {427 if (vocab.get_add_eos()) {428 GGML_ASSERT(vocab.token_eos() != LLAMA_TOKEN_NULL);429 output.push_back(vocab.token_eos());430 return true;431 }432 return false;433 }434 435 void check_double_bos_eos(const std::vector<llama_token> & output) const {436 if (vocab.get_add_bos() && output.size() >= 2 && output[1] == vocab.token_bos()) {437 LLAMA_LOG_WARN(438 "%s: Added a BOS token to the prompt as specified by the model but the prompt "439 "also starts with a BOS token. So now the final prompt starts with 2 BOS tokens. "440 "Are you sure this is what you want?\n", __FUNCTION__);441 }442 if (vocab.get_add_eos() && output.size() >= 2 && *(output.end()-2) == vocab.token_eos()) {443 LLAMA_LOG_WARN(444 "%s: Added a EOS token to the prompt as specified by the model but the prompt "445 "also ends with a EOS token. So now the final prompt ends with 2 EOS tokens. "446 "Are you sure this is what you want?\n", __FUNCTION__);447 }448 }449 450 void tokenize(const std::string & text, std::vector<llama_token> & output) {451 int final_prev_index = -1;452 const auto word_collection = unicode_regex_split(text, tokenizer.regex_exprs);453 454 symbols_final.clear();455 456 for (const auto & word : word_collection) {457 work_queue = llm_bigram_bpe::queue();458 symbols.clear();459 460 int index = 0;461 size_t offset = 0;462 463 //if (vocab.tokenizer_ignore_merges && vocab.token_to_id.find(word) != vocab.token_to_id.end()) {464 if (vocab.get_ignore_merges() && vocab.text_to_token(word) != LLAMA_TOKEN_NULL) {465 symbols.emplace_back(llm_symbol{-1, -1, word.c_str(), word.size()});466 offset = word.size();467 }468 469 while (offset < word.size()) {470 llm_symbol sym;471 size_t char_len = std::min(word.size() - offset, (size_t) unicode_len_utf8(word[offset]));472 sym.text = word.c_str() + offset;473 sym.n = char_len;474 offset += sym.n;475 sym.prev = index - 1;476 sym.next = offset == word.size() ? -1 : index + 1;477 index++;478 symbols.emplace_back(sym);479 }480 for (int i = 1; i < (int) symbols.size(); ++i) {481 add_new_bigram(i - 1, i);482 }483 484 // build token(s)485 while (!work_queue.empty()) {486 auto bigram = work_queue.pop_move();487 488 auto & left_symbol = symbols[bigram.left];489 auto & right_symbol = symbols[bigram.right];490 491 if (left_symbol.n == 0 || right_symbol.n == 0) {492 continue;493 }494 std::string left_token = std::string(left_symbol.text, left_symbol.n);495 std::string right_token = std::string(right_symbol.text, right_symbol.n);496 if (left_token + right_token != bigram.text) {497 continue; // Skip this bigram if it's outdated498 }499 500 // merge the right sym into the left one501 left_symbol.n += right_symbol.n;502 right_symbol.n = 0;503 504 // remove the right sym from the chain505 left_symbol.next = right_symbol.next;506 if (right_symbol.next >= 0) {507 symbols[right_symbol.next].prev = bigram.left;508 }509 510 add_new_bigram(left_symbol.prev, bigram.left); // left side of current symbol511 add_new_bigram(bigram.left, left_symbol.next); // right side of current symbol512 }513 514 // add the finished tokens to the final list keeping correct order for next and prev515 for (auto & sym : symbols) {516 if (sym.n > 0) {517 sym.prev = final_prev_index;518 sym.next = -1;519 if (final_prev_index != -1) {520 symbols_final[final_prev_index].next = symbols_final.size();521 }522 symbols_final.emplace_back(sym);523 final_prev_index = symbols_final.size() - 1;524 }525 }526 }527 528 symbols = symbols_final;529 530 if (!symbols.empty()) {531 for (int i = 0; i != -1; i = symbols[i].next) {532 auto & symbol = symbols[i];533 if (symbol.n == 0) {534 continue;535 }536 537 const std::string str = std::string(symbol.text, symbol.n);538 const auto token = vocab.text_to_token(str);539 540 if (token == LLAMA_TOKEN_NULL) {541 for (auto j = str.begin(); j != str.end(); ++j) {542 std::string byte_str(1, *j);543 auto token_multibyte = vocab.text_to_token(byte_str);544 if (token_multibyte != LLAMA_TOKEN_NULL) {545 output.push_back(token_multibyte);546 }547 }548 } else {549 output.push_back(token);550 }551 }552 }553 }554 555private:556 void add_new_bigram(int left, int right) {557 if (left == -1 || right == -1) {558 return;559 }560 std::string left_token = std::string(symbols[left].text, symbols[left].n);561 std::string right_token = std::string(symbols[right].text, symbols[right].n);562 563 int rank_found = -1;564 565 rank_found = vocab.find_bpe_rank(left_token, right_token);566 567 if (rank_found < 0) {568 return;569 }570 571 llm_bigram_bpe bigram;572 573 bigram.left = left;574 bigram.right = right;575 bigram.text = left_token + right_token;576 bigram.size = left_token.size() + right_token.size();577 bigram.rank = rank_found;578 579 work_queue.push(bigram);580 }581 582 const llama_vocab & vocab;583 const llm_tokenizer_bpe & tokenizer;584 585 std::vector<llm_symbol> symbols;586 std::vector<llm_symbol> symbols_final;587 llm_bigram_bpe::queue work_queue;588};589 590//591// WPM tokenizer592//593 594struct llm_tokenizer_wpm : llm_tokenizer {595 llm_tokenizer_wpm(const llama_vocab & /*vocab*/) {}596};597 598struct llm_tokenizer_wpm_session {599 llm_tokenizer_wpm_session(const llama_vocab & vocab) : vocab(vocab) {}600 601 void tokenize(const std::string & text, std::vector<llama_token> & output) {602 // normalize and split by whitespace603 std::vector<std::string> words = preprocess(text);604 // bos token prepended already605 606 // find the longest tokens that form the words607 for (const std::string & word : words) {608 // skip empty words609 if (word.size() == 0) {610 continue;611 }612 613 // prepend phantom space614 const std::string word1 = "\xe2\x96\x81" + word;615 const int n = word1.size();616 617 const size_t current_tokens = output.size();618 619 // we're at the start of a new word620 // move through character position in word621 for (int i = 0; i < n; ++i) {622 // loop through possible match length623 bool match = false;624 for (int j = std::min(n, i + vocab.max_token_len() + 1); j > i; j--) {625 auto id = vocab.text_to_token(word1.substr(i, j - i));626 if (id != LLAMA_TOKEN_NULL) {627 output.push_back(id);628 match = true;629 i = j - 1;630 break;631 }632 }633 634 if (!match) { // discard all635 output.resize(current_tokens);636 break; // and discard next tokens637 }638 }639 640 // we didn't find any matches for this word641 if (current_tokens == output.size()) {642 output.push_back(vocab.token_unk());643 }644 }645 }646 647 // TODO: reduce string copies by using cpts_offs array648 static std::vector<std::string> preprocess(const std::string & text) {649 const std::vector<uint32_t> cpts_nfd = unicode_cpts_normalize_nfd(unicode_cpts_from_utf8(text));650 std::vector<std::string> words(1, "");651 652 for (const uint32_t cpt : cpts_nfd) {653 const auto flags = unicode_cpt_flags_from_cpt(cpt);654 655 if (flags.is_whitespace) {656 if (words.back().size()) { // finish previous word if any657 words.emplace_back();658 }659 continue;660 }661 662 assert (!flags.is_separator);663 if (cpt == 0 || cpt == 0xFFFD || flags.is_control) {664 continue;665 }666 667 const std::string s = unicode_cpt_to_utf8(unicode_tolower(cpt));668 if (flags.is_punctuation || ( cpt < 0x7F && flags.is_symbol ) || is_chinese_char(cpt)) {669 if (words.back().size()) { // finish previous word if any670 words.emplace_back();671 }672 words.back() = s; // single char word673 words.emplace_back(); // start a new word674 } else {675 words.back() += s; // append char to word676 }677 }678 679 if (!words.back().size()) {680 words.pop_back();681 }682 683 return words;684 }685 686 static bool is_chinese_char(uint32_t cpt) {687 return688 (cpt >= 0x04E00 && cpt <= 0x09FFF) ||689 (cpt >= 0x03400 && cpt <= 0x04DBF) ||690 (cpt >= 0x20000 && cpt <= 0x2A6DF) ||691 (cpt >= 0x2A700 && cpt <= 0x2B73F) ||692 (cpt >= 0x2B740 && cpt <= 0x2B81F) ||693 (cpt >= 0x2B920 && cpt <= 0x2CEAF) || // this should be 0x2B820 but in hf rust code it is 0x2B920694 (cpt >= 0x0F900 && cpt <= 0x0FAFF) ||695 (cpt >= 0x2F800 && cpt <= 0x2FA1F);696 //(cpt >= 0x3000 && cpt <= 0x303F) ||697 //(cpt >= 0xFF00 && cpt <= 0xFFEF);698 }699 700private:701 const llama_vocab & vocab;702 // currently unused703 // const llm_tokenizer_wpm * wpm_tokenizer;704};705 706//707// UGM tokenizer708//709 710struct llm_tokenizer_ugm : llm_tokenizer {711 llm_tokenizer_ugm(const llama_vocab & vocab, const std::vector<char> & precompiled_charsmap) {712 if (precompiled_charsmap.size() > 0) {713 size_t charsmap_offset = 0;714 715 // First four bytes of precompiled_charsmap contains length of binary716 // blob containing XOR-compressed compact double array (XCDA) entries717 uint32_t xcda_blob_size = *(const uint32_t *) &precompiled_charsmap[0];718 charsmap_offset += sizeof(xcda_blob_size);719 if (xcda_blob_size + charsmap_offset >= precompiled_charsmap.size()) {720 throw std::runtime_error("Index out of array bounds in precompiled charsmap!");721 }722 723 // Next xcda_blob_size bytes contain entries of XOR-compressed compact724 // double array (XCDA). Each entry is bit-packed into a 32-bit integer.725 xcda_array = (const uint32_t *) &precompiled_charsmap[charsmap_offset];726 xcda_array_size = xcda_blob_size / sizeof(uint32_t);727 charsmap_offset += xcda_blob_size;728 729 // Remaining bytes of precompiled charsmap contain null-terminated730 // replacement strings for prefixes matched by the XCDA.731 prefix_replacements = &precompiled_charsmap[charsmap_offset];732 prefix_replacements_size = precompiled_charsmap.size() - charsmap_offset;733 }734 735 for (uint32_t id = 0; id < vocab.n_tokens(); ++id) {736 const auto & token_data = vocab.get_token_data(id);737 738 if (vocab.is_normal(id)) {739 min_score = std::min<float>(min_score, token_data.score);740 max_score = std::max<float>(max_score, token_data.score);741 }742 743 if (vocab.is_normal(id) ||744 vocab.is_user_defined(id) ||745 vocab.is_unused(id)) {746 token_matcher.insert(token_data.text.data(), token_data.text.size(), id);747 }748 749 if (vocab.is_user_defined(id)) {750 user_defined_token_matcher.insert(token_data.text.data(), token_data.text.size());751 }752 }753 754 unknown_token_score = min_score - unknown_token_score_penalty;755 }756 757 // escaped space symbol - U+2581 (Lower One Eighth Block)758 const std::string escaped_space = "\xE2\x96\x81";759 760 const char * prefix_replacements = NULL;761 size_t prefix_replacements_size = 0;762 763 const uint32_t * xcda_array = NULL;764 size_t xcda_array_size = 0;765 766 struct naive_trie user_defined_token_matcher;767 768 float min_score = FLT_MAX;769 float max_score = -FLT_MAX;770 771 float unknown_token_score_penalty = 10.0;772 float unknown_token_score;773 774 struct naive_trie token_matcher;775};776 777struct llm_tokenizer_ugm_session {778 llm_tokenizer_ugm_session(const llama_vocab & vocab, const llm_tokenizer_ugm & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}779 780 /* This implementation is based on SentencePiece optimized Viterbi algorithm for781 * unigram language models. The general idea is to:782 * - move along the input sequence in steps of one UTF code point,783 * - at each step find all possible tokenizations of the prefix by784 * traversing the tokens trie,785 * - for each tokenization store the best one so far (by higher score)786 * - use the position in sequence after given token as an index to store787 * results788 * - if there was no valid tokenization of the current UTF code point789 * then use unknown token with additional score penalty790 * After processing the whole sequence we backtrack from the end to get791 * the best tokenization.792 */793 void tokenize(const std::string & text, std::vector<llama_token> & output) {794 // get current size of output (for reversal later)795 size_t output_size = output.size();796 797 // normalize the input first798 std::string normalized;799 normalize(text, &normalized);800 size_t input_len = normalized.size();801 if (input_len == 0) {802 return;803 }804 805 // initialize score_sum to -FLT_MAX so it will be always lower than sums of token scores806 std::vector<struct best_tokenization> tokenization_results(input_len + 1, {vocab.token_unk(), 0, -FLT_MAX});807 // at the beginning tokenization score is zero808 tokenization_results[0] = { vocab.token_unk(), 0, 0 };809 810 for (size_t input_offset = 0; input_offset < input_len;) {811 size_t prefix_offset = input_offset;812 // calculate how many code units are in the currently processed UTF code point813 size_t n_utf8_code_units = std::min<size_t>(unicode_len_utf8(normalized[input_offset]), input_len - input_offset);814 815 // traverse the token matcher trie to find a matching token816 bool single_codepoint_token_found = false;817 const struct best_tokenization & current_best = tokenization_results[input_offset];818 const struct naive_trie * node = tokenizer.token_matcher.traverse(normalized[prefix_offset++]);819 820 while (prefix_offset <= input_len && node != NULL) {821 // check if we found valid token in prefix822 if (node->has_value) {823 // check if it corresponds to the whole UTF code point824 if (prefix_offset - input_offset == n_utf8_code_units) {825 single_codepoint_token_found = true;826 }827 llama_token token_id = node->value;828 const auto & token_data = vocab.get_token_data(token_id);829 830 // we set the user-defined token scores to 0 to make them more likely to be selected831 // (normal token scores are log probabilities, so they are negative)832 // score type is double here to make tokenization results exactly833 // the same as in the HF tokenizer using SentencePiece834 const double token_score = vocab.is_user_defined(token_id) ? 0.0 : token_data.score;835 const double challenger_score = current_best.score_sum + token_score;836 struct best_tokenization & current_champ = tokenization_results[prefix_offset];837 if (challenger_score > current_champ.score_sum) {838 struct best_tokenization challenger = { token_id, input_offset, (float) challenger_score };839 current_champ = challenger;840 }841 }842 node = node->traverse(normalized[prefix_offset++]);843 }844 845 // if we didn't find a valid token corresponding to the whole UTF code point846 // then use unknown token as the tokenization of this UTF code point847 if (!single_codepoint_token_found) {848 const double challenger_score = current_best.score_sum + tokenizer.unknown_token_score;849 prefix_offset = input_offset + n_utf8_code_units;850 struct best_tokenization & current_champ = tokenization_results[prefix_offset];851 if (challenger_score > current_champ.score_sum) {852 struct best_tokenization challenger = { vocab.token_unk(), input_offset, (float) challenger_score };853 current_champ = challenger;854 }855 }856 857 // move to the next UTF code point858 input_offset += n_utf8_code_units;859 }860 861 // now backtrack from the end to gather token ids of the best tokenization862 // merge sequences of consecutive unknown tokens into single unknown tokens863 bool is_prev_unknown = false;864 for (struct best_tokenization & tokenization = tokenization_results[input_len]; ; tokenization = tokenization_results[tokenization.input_offset]) {865 bool is_unknown = tokenization.token_id == vocab.token_unk();866 if (!(is_prev_unknown && is_unknown)) {867 output.push_back(tokenization.token_id);868 }869 if (tokenization.input_offset == 0) {870 break;871 }872 is_prev_unknown = is_unknown;873 }874 875 // reverse the output since we added tokens starting from the end of the input876 std::reverse(output.begin() + output_size, output.end());877 }878 879private:880 881 // helper structure for returning normalization results882 struct normalization_result {883 const char * normalized;884 size_t normalized_len;885 size_t consumed_input;886 };887 888 void normalize(const std::string& input, std::string * normalized) {889 normalized->clear();890 normalized->reserve(input.size() * 3);891 892 const std::string space = vocab.get_escape_whitespaces() ? tokenizer.escaped_space : " ";893 894 const bool shall_prepend_space = !vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();895 const bool shall_append_space = vocab.get_treat_whitespace_as_suffix() && vocab.get_add_space_prefix();896 const bool shall_merge_spaces = vocab.get_remove_extra_whitespaces();897 898 bool is_space_prepended = false;899 bool processing_non_ws = false;900 901 size_t input_len = input.size();902 903 for (size_t input_offset = 0; input_offset < input_len; ) {904 auto norm_res = normalize_prefix(input, input_offset);905 for (size_t i = 0; i < norm_res.normalized_len; i++) {906 char c = norm_res.normalized[i];907 if (c != ' ') {908 if (!processing_non_ws) {909 processing_non_ws = true;910 if ((shall_prepend_space && !is_space_prepended) || shall_merge_spaces) {911 normalized->append(space);912 is_space_prepended = true;913 }914 }915 normalized->push_back(c);916 } else {917 if (processing_non_ws) {918 processing_non_ws = false;919 }920 if (!shall_merge_spaces) {921 normalized->append(space);922 }923 }924 }925 926 input_offset += norm_res.consumed_input;927 }928 929 if (shall_append_space) {930 normalized->append(space);931 }932 }933 934 /*935 * This structure is a view wrapper for XOR-compressed double array (XCDA)936 * See Shunsuke Kanda (2018). Space- and Time-Efficient String Dictionaries.937 * Each bit-packed entry contains:938 * - BASE array value in bits 10-30939 * - LCHECK array value in bits 0-7940 * - LEAF array value in bit 9941 * Entries containing indexes of replacement sequences have set bit 31942 */943 struct xcda_array_view {944 public:945 xcda_array_view(const uint32_t * xcda_array, size_t xcda_array_size) : xcda_array(xcda_array), xcda_array_size(xcda_array_size) {946 }947 uint32_t get_base(size_t index) {948 uint32_t packed_node = get_node(index);949 return (packed_node >> 10) << ((packed_node & (1U << 9)) >> 6);950 }951 uint32_t get_lcheck(size_t index) {952 uint32_t packed_node = get_node(index);953 return packed_node & ((1U << 31) | 0xff);954 }955 bool get_leaf(size_t index) {956 uint32_t packed_node = get_node(index);957 return (packed_node >> 8) & 1;958 }959 uint32_t get_value(size_t index) {960 uint32_t packed_node = get_node(index);961 return packed_node & ((1U << 31) - 1);962 }963 private:964 uint32_t get_node(size_t index) {965 if (index > xcda_array_size) {966 throw std::runtime_error("Index out of array bounds in XCDA array!");967 }968 return xcda_array[index];969 }970 const uint32_t * xcda_array;971 size_t xcda_array_size;972 };973 974 // this structure stores the best tokenization so far at input_offset975 struct best_tokenization {976 llama_token token_id;977 size_t input_offset;978 float score_sum;979 };980 981 struct normalization_result normalize_prefix(const std::string & input, size_t input_offset) {982 if (input_offset == input.size()) {983 return { &input[input_offset], 0, 0 };984 }985 986 // if input prefix matches some user-defined token return this token as normalization result987 auto user_defined_token_match =988 tokenizer.user_defined_token_matcher.get_longest_prefix(&input[input_offset], input.size() - input_offset);989 if (user_defined_token_match.second > 0) {990 return { &input[input_offset], user_defined_token_match.second, user_defined_token_match.second };991 }992 993 size_t longest_prefix_length = 0;994 size_t longest_prefix_offset = 0;995 996 if (tokenizer.xcda_array_size > 0) {997 struct xcda_array_view xcda_view(tokenizer.xcda_array, tokenizer.xcda_array_size);998 999 // Find the longest normalized sequence matching the input prefix by walking1000 // the XOR-compressed compact double array (XCDA) starting from the root node1001 // We find the index of the next node by calculating BASE[s] ^ c where s is1002 // the index of the previous node and c is a numerical character value1003 uint32_t node_index = 0;1004 // get BASE of the root node1005 node_index = xcda_view.get_base(node_index);1006 for (size_t prefix_offset = input_offset; prefix_offset < input.size(); prefix_offset++) {1007 unsigned char c = input[prefix_offset];1008 if (c == 0) {1009 break;1010 }1011 node_index ^= c;1012 // if value of LCHECK is not c it means that this is not a child of1013 // the previous node, so we stop matching1014 if (xcda_view.get_lcheck(node_index) != c) {1015 break;1016 }1017 bool is_leaf = xcda_view.get_leaf(node_index);1018 // get BASE of the current node1019 node_index ^= xcda_view.get_base(node_index);1020 // if LEAF of the current node is true, it means that its BASE points to the node1021 // containing index of replacement sequence for currently matched input prefix1022 if (is_leaf)1023 {1024 longest_prefix_length = prefix_offset - input_offset + 1;1025 // get index of replacement sequence for currently matched input prefix1026 longest_prefix_offset = xcda_view.get_value(node_index);1027 }1028 }1029 }1030 1031 if (longest_prefix_length > 0) {1032 // we have a match, so return the replacement sequence1033 if (longest_prefix_offset >= tokenizer.prefix_replacements_size) {1034 throw std::runtime_error("Index out of array bounds in precompiled charsmap!");1035 }1036 const char * prefix_replacement = &(tokenizer.prefix_replacements)[longest_prefix_offset];1037 return { prefix_replacement, strlen(prefix_replacement), longest_prefix_length };1038 }1039 1040 // check if the input prefix contains a valid sequence of UTF-8 code units1041 try {1042 // if yes, return this sequence unmodified1043 size_t prefix_offset = input_offset;1044 unicode_cpt_from_utf8(input, prefix_offset);1045 return { &input[input_offset], prefix_offset - input_offset, prefix_offset - input_offset };1046 } catch (std::invalid_argument & /*ex*/) {1047 // if no, consume 1 byte and return U+FFFD - REPLACEMENT CHARACTER1048 return { "\xEF\xBF\xBD", 3, 1 };1049 }1050 }1051 1052 const llama_vocab & vocab;1053 const llm_tokenizer_ugm & tokenizer;1054};1055 1056//1057// RWKV tokenizer1058//1059 1060static std::vector<uint8_t> llama_unescape_rwkv_token(const std::string & escaped) {1061 std::vector<uint8_t> output;1062 output.reserve(escaped.size());1063 1064 // Parser state1065 bool escaping = false;1066 uint8_t hex_remaining = 0;1067 uint8_t hex_acc = 0;1068 1069 // Step through characters, performing parsing1070 for (const char & c : escaped) {1071 // If we're parsing a hex code, interpret the next character1072 if (hex_remaining != 0) {1073 uint8_t value = (c >= 'a') ? (c - 'a' + 10) : (c - '0');1074 hex_acc = (hex_acc << 4) + value;1075 1076 hex_remaining -= 1;1077 if (hex_remaining == 0) {1078 output.push_back(hex_acc);1079 hex_acc = 0;1080 }1081 1082 continue;1083 }1084 1085 // If we got an escape character, interpret it1086 if (escaping) {1087 if (c == 't') {1088 output.push_back('\t');1089 } else if (c == 'n') {1090 output.push_back('\n');1091 } else if (c == 'r') {1092 output.push_back('\r');1093 } else if (c == 'x') {1094 hex_remaining = 2;1095 } else {1096 output.push_back(c);1097 }1098 1099 escaping = false;1100 continue;1101 }1102 1103 if (c == '\\') {1104 escaping = true;1105 continue;1106 }1107 1108 output.push_back(c);1109 }1110 1111 return output;1112}1113 1114struct llm_tokenizer_rwkv : llm_tokenizer {1115 llm_tokenizer_rwkv(const llama_vocab & vocab) {1116 // RWKV supports arbitrary byte tokens, but the vocab struct only supports string tokens.1117 // For now, we decode the vocab here into the lookup we'll use for tokenization.1118 1119 // build trie1120 for (uint32_t id = 0; id < vocab.n_tokens(); ++id) {1121 const auto & data = vocab.get_token_data(id);1122 const auto text = llama_unescape_rwkv_token(data.text);1123 token_matcher.insert((const char *) text.data(), text.size(), id);1124 }1125 }1126 1127 struct naive_trie token_matcher;1128};1129 1130struct llm_tokenizer_rwkv_session {1131 llm_tokenizer_rwkv_session(const llama_vocab & vocab, const llm_tokenizer_rwkv & tokenizer) : vocab(vocab), tokenizer(tokenizer) {}1132 1133 void tokenize(const std::string & text, std::vector<llama_token> & output) {1134 uint32_t position = 0;1135 while (position < text.size()) {1136 const struct naive_trie * node = tokenizer.token_matcher.traverse(text[position]);1137 if (node == NULL) {1138 // no matching token found, add unknown token1139 output.push_back(vocab.token_unk());1140 position += 1;1141 continue;1142 }1143 1144 // traverse the trie to find the longest matching token1145 uint32_t token_id = 0;1146 uint32_t token_length = 0;1147 while (node != NULL) {1148 if (node->has_value) {1149 token_id = node->value;1150 token_length = position + 1;1151 }1152 node = node->traverse(text[++position]);1153 }1154 1155 // add the longest matching token1156 output.push_back(token_id);1157 position = token_length;1158 }1159 }1160 1161private:1162 const llama_vocab & vocab;1163 const llm_tokenizer_rwkv & tokenizer;1164};1165 1166//1167// impl1168//1169 1170typedef enum FRAGMENT_BUFFER_VARIANT_TYPE {1171 FRAGMENT_BUFFER_VARIANT_TYPE_TOKEN,1172 FRAGMENT_BUFFER_VARIANT_TYPE_RAW_TEXT1173} FRAGMENT_BUFFER_VARIANT_TYPE;1174 1175struct fragment_buffer_variant {1176 fragment_buffer_variant(llama_token _token)1177 :1178 type(FRAGMENT_BUFFER_VARIANT_TYPE_TOKEN),1179 token(_token),1180 raw_text(_dummy),1181 offset(0),1182 length(0) {}1183 1184 fragment_buffer_variant(const std::string & _raw_text, int64_t _offset, int64_t _length)1185 :1186 type(FRAGMENT_BUFFER_VARIANT_TYPE_RAW_TEXT),1187 token((llama_token) - 1),1188 raw_text(_raw_text),1189 offset(_offset),1190 length(_length){1191 GGML_ASSERT(_offset >= 0);1192 GGML_ASSERT(_length >= 1);1193 GGML_ASSERT(offset + length <= raw_text.length());1194 }1195 1196 const FRAGMENT_BUFFER_VARIANT_TYPE type;1197 const llama_token token;1198 const std::string _dummy;1199 const std::string & raw_text;1200 const uint64_t offset;