| #include <algorithm>
|
| #include <cctype>
|
| #include <cstdint>
|
| #include <cstdio>
|
| #include <fstream>
|
| #include <iostream>
|
| #include <iterator>
|
| #include <mutex>
|
| #include <optional>
|
| #include <sstream>
|
| #include <stdexcept>
|
| #include <string>
|
| #include <unordered_map>
|
| #include <unordered_set>
|
| #include <vector>
|
|
|
| #ifdef _OPENMP
|
| #include <omp.h>
|
| #else
|
| inline int omp_get_max_threads(){ return 1; }
|
| #endif
|
|
|
| extern unsigned char dictionary_json[];
|
| extern unsigned int dictionary_json_len;
|
|
|
| using namespace std;
|
|
|
| static inline bool is_space(char c){ return isspace(static_cast<unsigned char>(c)) != 0; }
|
| static inline char to_low(char c){ return static_cast<char>(tolower(static_cast<unsigned char>(c))); }
|
|
|
| struct DictionaryEntry {
|
| string pos;
|
| string word;
|
| vector<string> definitions;
|
| };
|
|
|
| static vector<DictionaryEntry> global_dictionary_entries;
|
| static unordered_map<string, vector<string>> global_def_tokens_cache;
|
| static unordered_map<string, vector<string>> global_pos_cache;
|
|
|
| static inline bool is_word_char_for_key(char c){
|
| unsigned char uc = static_cast<unsigned char>(c);
|
| return isalnum(uc) != 0 || c == '\'' || c == '-';
|
| }
|
|
|
| static string normalize_dictionary_key(const string &s){
|
| size_t b = 0, e = s.size();
|
| while (b < e && !is_word_char_for_key(s[b])) ++b;
|
| while (e > b && !is_word_char_for_key(s[e - 1])) --e;
|
|
|
| string out;
|
| out.reserve(e - b);
|
| for (size_t i = b; i < e; ++i) out.push_back(to_low(s[i]));
|
| return out;
|
| }
|
|
|
| static string normalize_pos_tag(const string &s){
|
| string out;
|
| out.reserve(s.size());
|
| for (char c : s){
|
| unsigned char uc = static_cast<unsigned char>(c);
|
| if (isalpha(uc) != 0) out.push_back(to_low(c));
|
| }
|
| return out;
|
| }
|
|
|
| enum class PosClass {
|
| Unknown,
|
| Noun,
|
| Verb,
|
| Adj,
|
| Adv,
|
| Pron,
|
| Prep,
|
| Conj,
|
| Det,
|
| Num,
|
| Interj
|
| };
|
|
|
| static PosClass pos_class_from_tag(const string &tag){
|
| if (tag == "n" || tag == "noun") return PosClass::Noun;
|
| if (tag == "v" || tag == "verb" || tag == "part" || tag == "participle" || tag == "p") return PosClass::Verb;
|
| if (tag == "a" || tag == "adj" || tag == "adjective") return PosClass::Adj;
|
| if (tag == "adv" || tag == "adverb") return PosClass::Adv;
|
| if (tag == "pron" || tag == "pronoun") return PosClass::Pron;
|
| if (tag == "prep" || tag == "preposition") return PosClass::Prep;
|
| if (tag == "conj" || tag == "conjunction") return PosClass::Conj;
|
| if (tag == "art" || tag == "article" || tag == "det" || tag == "determiner") return PosClass::Det;
|
| if (tag == "num" || tag == "number") return PosClass::Num;
|
| if (tag == "interj" || tag == "interjection") return PosClass::Interj;
|
| return PosClass::Unknown;
|
| }
|
|
|
| static bool has_pos_class(const vector<string> &tags, PosClass cls){
|
| for (const auto &t : tags){
|
| if (pos_class_from_tag(t) == cls) return true;
|
| }
|
| return false;
|
| }
|
|
|
| static const vector<string> &dictionary_pos_for_token(const string &surface){
|
| static const vector<string> empty;
|
| auto key = normalize_dictionary_key(surface);
|
| if (key.empty()) return empty;
|
|
|
| auto it = global_pos_cache.find(key);
|
| return (it == global_pos_cache.end()) ? empty : it->second;
|
| }
|
|
|
| static bool first_alpha_is_upper(const string &s){
|
| for (char c : s){
|
| unsigned char uc = static_cast<unsigned char>(c);
|
| if (isalpha(uc) != 0) return isupper(uc) != 0;
|
| }
|
| return false;
|
| }
|
|
|
| static bool first_alpha_is_lower(const string &s){
|
| for (char c : s){
|
| unsigned char uc = static_cast<unsigned char>(c);
|
| if (isalpha(uc) != 0) return islower(uc) != 0;
|
| }
|
| return false;
|
| }
|
|
|
| static bool is_sentence_boundary_token(const string &s){
|
| if (s.empty()) return false;
|
| char c = s.back();
|
| return c == '.' || c == '!' || c == '?';
|
| }
|
|
|
| static bool is_open_punct_token(const string &s){
|
| return s == "(" || s == "[" || s == "{" || s == "\"" || s == "'";
|
| }
|
|
|
| static bool is_punctuation_only_token(const string &s){
|
| if (s.empty()) return false;
|
| for (char c : s){
|
| unsigned char uc = static_cast<unsigned char>(c);
|
| if (isalnum(uc) != 0) return false;
|
| }
|
| return true;
|
| }
|
|
|
| static string to_lower_ascii(string s) {
|
| transform(s.begin(), s.end(), s.begin(),
|
| [](unsigned char c) { return static_cast<char>(tolower(c)); });
|
| return s;
|
| }
|
|
|
| static bool is_common_determiner(const string &s) {
|
| static const unordered_set<string> words = {
|
| "a", "an", "the", "this", "that", "these", "those",
|
| "my", "your", "his", "her", "its", "our", "their",
|
| "all", "some", "any", "each", "every", "either", "neither",
|
| "no", "many", "much", "more", "most", "few", "fewer", "less",
|
| "little", "several", "both", "another", "other", "such",
|
| "own", "same", "certain", "what", "which", "whose",
|
| "whatever", "whichever", "enough", "various", "particular"
|
| };
|
|
|
| return words.find(to_lower_ascii(s)) != words.end();
|
| }
|
|
|
| static bool is_common_preposition(const string &s) {
|
| static const unordered_set<string> words = {
|
| "of", "in", "on", "at", "by", "for", "from", "with",
|
| "into", "onto", "about", "over", "under", "after", "before",
|
| "between", "through", "during", "without", "within", "across",
|
| "against", "among", "around", "as", "like", "per", "via",
|
| "toward", "towards", "upon", "beneath", "beside", "besides",
|
| "beyond", "inside", "outside", "near", "past", "since",
|
| "until", "till", "up", "down", "off", "out", "underneath",
|
| "amid", "amidst", "despite", "except", "regarding", "concerning",
|
| "throughout", "amongst", "opposite", "along", "behind", "ahead",
|
| "above", "below", "plus", "minus"
|
| };
|
|
|
| return words.find(to_lower_ascii(s)) != words.end();
|
| }
|
|
|
| static bool is_common_aux_or_modal(const string &s) {
|
| static const unordered_set<string> words = {
|
| "to", "be", "am", "is", "are", "was", "were", "been", "being",
|
| "have", "has", "had", "do", "does", "did",
|
| "can", "could", "may", "might", "must", "shall", "should", "will",
|
| "would", "ought", "need", "dare", "used",
|
| "cannot", "can't", "won't", "wouldn't", "shouldn't", "couldn't",
|
| "mustn't", "mayn't", "mightn't", "shan't"
|
| };
|
|
|
| return words.find(to_lower_ascii(s)) != words.end();
|
| }
|
|
|
| static bool begins_with_vowel_sound(const string &s){
|
| if (s.empty()) return false;
|
|
|
| const string t = to_lower_ascii(s);
|
|
|
| static const unordered_set<string> vowel_sound_exceptions = {
|
| "hour", "hours", "honest", "honesty", "honor", "honour", "honorable", "honourable",
|
| "heir", "heiress", "herb", "herbal", "herbalist", "homage", "hono(u)rary"
|
| };
|
|
|
| static const unordered_set<string> consonant_sound_prefixes = {
|
| "uni", "univ", "unit", "use", "user", "euro", "eu", "one", "once", "ouija",
|
| "ufo", "ut", "uk", "ubiq", "ewe", "eul", "eup", "x", "y"
|
| };
|
|
|
| for (const auto &w : vowel_sound_exceptions) {
|
| if (t.rfind(w, 0) == 0) {
|
| return true;
|
| }
|
| }
|
|
|
| for (const auto &p : consonant_sound_prefixes) {
|
| if (t.rfind(p, 0) == 0) {
|
| return false;
|
| }
|
| }
|
|
|
| char c = t[0];
|
| return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
|
| }
|
|
|
| static double english_rule_bonus(const string &context_tok, const string &cand){
|
| const string ctx_key = normalize_dictionary_key(context_tok);
|
| const string cand_key = normalize_dictionary_key(cand);
|
|
|
| const auto &ctx_tags = dictionary_pos_for_token(context_tok);
|
| const auto &cand_tags = dictionary_pos_for_token(cand);
|
|
|
| const bool sentence_start = context_tok.empty() || is_sentence_boundary_token(context_tok) || is_open_punct_token(context_tok);
|
|
|
| const bool cand_nounish = has_pos_class(cand_tags, PosClass::Noun) ||
|
| has_pos_class(cand_tags, PosClass::Adj) ||
|
| has_pos_class(cand_tags, PosClass::Pron) ||
|
| has_pos_class(cand_tags, PosClass::Num);
|
|
|
| const bool cand_verbish = has_pos_class(cand_tags, PosClass::Verb);
|
| const bool cand_advish = has_pos_class(cand_tags, PosClass::Adv);
|
| const bool cand_prepish = has_pos_class(cand_tags, PosClass::Prep);
|
| const bool cand_detish = has_pos_class(cand_tags, PosClass::Det);
|
|
|
| double bonus = 0.0;
|
|
|
| if (!cand_key.empty()){
|
| if (sentence_start){
|
| bonus += first_alpha_is_upper(cand) ? 0.22 : -0.08;
|
| } else if (first_alpha_is_upper(cand)){
|
| bonus -= 0.03;
|
| }
|
| }
|
|
|
| if (ctx_key == "a" || ctx_key == "an"){
|
| const bool vowel = begins_with_vowel_sound(cand_key.empty() ? cand : cand_key);
|
| bonus += ((ctx_key == "an") == vowel) ? 0.28 : -0.18;
|
| }
|
|
|
| const bool ctx_det = has_pos_class(ctx_tags, PosClass::Det) || is_common_determiner(ctx_key);
|
| const bool ctx_prep = has_pos_class(ctx_tags, PosClass::Prep) || is_common_preposition(ctx_key);
|
| const bool ctx_aux = is_common_aux_or_modal(ctx_key);
|
|
|
| if (ctx_det){
|
| if (cand_nounish) bonus += 0.20;
|
| if (cand_verbish || cand_advish || cand_prepish) bonus -= 0.08;
|
| }
|
|
|
| if (ctx_prep){
|
| if (cand_nounish) bonus += 0.16;
|
| if (cand_verbish) bonus -= 0.06;
|
| }
|
|
|
| if (ctx_aux){
|
| if (cand_verbish) bonus += 0.18;
|
| if (cand_detish) bonus -= 0.04;
|
| }
|
|
|
| if (has_pos_class(ctx_tags, PosClass::Pron) || has_pos_class(ctx_tags, PosClass::Noun)){
|
| if (cand_verbish) bonus += 0.05;
|
| }
|
|
|
| if (!context_tok.empty() && (context_tok.back() == ',' || context_tok.back() == ';' || context_tok.back() == ':')){
|
| if (!cand.empty() && first_alpha_is_lower(cand)) bonus += 0.04;
|
| }
|
|
|
| if (is_punctuation_only_token(cand)){
|
| if (sentence_start) bonus -= 0.05;
|
| else if (!context_tok.empty() && isalnum(static_cast<unsigned char>(context_tok.back())) != 0) bonus += 0.03;
|
| }
|
|
|
| if (is_sentence_boundary_token(cand)) bonus += 0.06;
|
|
|
| return bonus;
|
| }
|
|
|
| static vector<string> tokenize_whitespace(const string &s){
|
| istringstream iss(s);
|
| vector<string> out;
|
| string t;
|
| while (iss >> t) out.push_back(t);
|
| return out;
|
| }
|
|
|
|
|
| static inline bool check_dictionary(const string &word) {
|
| return !dictionary_pos_for_token(word).empty();
|
| }
|
|
|
|
|
|
|
|
|
| static optional<string> get_valid_base_form(const string &word) {
|
| if (word.empty()) return nullopt;
|
|
|
|
|
| if (check_dictionary(word)) {
|
| return word;
|
| }
|
|
|
|
|
| if (word.length() > 3 && word.substr(word.length() - 3) == "ing") {
|
|
|
| string base1 = word.substr(0, word.length() - 3);
|
| if (check_dictionary(base1)) return base1;
|
|
|
|
|
| string base2 = base1 + "e";
|
| if (check_dictionary(base2)) return base2;
|
|
|
|
|
| if (base1.length() >= 2 && base1.back() == base1[base1.length() - 2]) {
|
| string base3 = base1.substr(0, base1.length() - 1);
|
| if (check_dictionary(base3)) return base3;
|
| }
|
| }
|
|
|
|
|
| if (word.length() > 2 && word.substr(word.length() - 2) == "ed") {
|
|
|
| string base1 = word.substr(0, word.length() - 1);
|
| if (check_dictionary(base1)) return base1;
|
|
|
|
|
| string base2 = word.substr(0, word.length() - 2);
|
| if (check_dictionary(base2)) return base2;
|
|
|
|
|
| if (base2.length() >= 2 && base2.back() == base2[base2.length() - 2]) {
|
| string base3 = base2.substr(0, base2.length() - 1);
|
| if (check_dictionary(base3)) return base3;
|
| }
|
| }
|
|
|
|
|
| if (word.length() > 3 && word.substr(word.length() - 3) == "est") {
|
|
|
| string base1 = word.substr(0, word.length() - 2);
|
| if (check_dictionary(base1)) return base1;
|
|
|
|
|
| string base2 = word.substr(0, word.length() - 3);
|
| if (check_dictionary(base2)) return base2;
|
|
|
|
|
| if (word.length() > 4 && word.substr(word.length() - 4) == "iest") {
|
| string base_y = word.substr(0, word.length() - 4) + "y";
|
| if (check_dictionary(base_y)) return base_y;
|
| }
|
|
|
|
|
| if (base2.length() >= 2 && base2.back() == base2[base2.length() - 2]) {
|
| string base3 = base2.substr(0, base2.length() - 1);
|
| if (check_dictionary(base3)) return base3;
|
| }
|
| }
|
|
|
|
|
| if (word.length() > 2 && word.substr(word.length() - 2) == "er") {
|
|
|
| string base1 = word.substr(0, word.length() - 1);
|
| if (check_dictionary(base1)) return base1;
|
|
|
|
|
| string base2 = word.substr(0, word.length() - 2);
|
| if (check_dictionary(base2)) return base2;
|
|
|
|
|
| if (word.length() > 3 && word.substr(word.length() - 3) == "ier") {
|
| string base_y = word.substr(0, word.length() - 3) + "y";
|
| if (check_dictionary(base_y)) return base_y;
|
| }
|
|
|
|
|
| if (base2.length() >= 2 && base2.back() == base2[base2.length() - 2]) {
|
| string base3 = base2.substr(0, base2.length() - 1);
|
| if (check_dictionary(base3)) return base3;
|
| }
|
| }
|
|
|
|
|
| if (word.length() > 2 && word.substr(word.length() - 2) == "ly") {
|
|
|
| string base1 = word.substr(0, word.length() - 2);
|
| if (check_dictionary(base1)) return base1;
|
|
|
|
|
| if (word.length() > 3 && word.substr(word.length() - 3) == "ily") {
|
| string base2 = word.substr(0, word.length() - 3) + "y";
|
| if (check_dictionary(base2)) return base2;
|
| }
|
|
|
|
|
| if (word.length() > 4 && word.substr(word.length() - 4) == "ally") {
|
| string base3 = word.substr(0, word.length() - 4);
|
| if (check_dictionary(base3)) return base3;
|
|
|
| string base4 = base3 + "al";
|
| if (check_dictionary(base4)) return base4;
|
| }
|
|
|
|
|
| if (word.back() == 'y' && word.length() > 2 && word[word.length() - 2] == 'l') {
|
| string base5 = word.substr(0, word.length() - 1) + "e";
|
| if (check_dictionary(base5)) return base5;
|
| }
|
| }
|
|
|
|
|
| if (word.length() > 4 && word.substr(word.length() - 4) == "ness") {
|
|
|
| string base1 = word.substr(0, word.length() - 4);
|
| if (check_dictionary(base1)) return base1;
|
|
|
|
|
| if (base1.length() > 1 && base1.back() == 'i') {
|
| string base2 = base1.substr(0, base1.length() - 1) + "y";
|
| if (check_dictionary(base2)) return base2;
|
| }
|
| }
|
|
|
|
|
| if (word.length() > 4 && word.substr(word.length() - 4) == "ment") {
|
|
|
| string base1 = word.substr(0, word.length() - 4);
|
| if (check_dictionary(base1)) return base1;
|
| }
|
|
|
|
|
| if (word.length() > 3 && word.substr(word.length() - 3) == "ies") {
|
| string base = word.substr(0, word.length() - 3) + "y";
|
| if (check_dictionary(base)) return base;
|
| }
|
|
|
|
|
| if (word.length() > 3 && word.substr(word.length() - 3) == "ves") {
|
| string base1 = word.substr(0, word.length() - 3) + "f";
|
| if (check_dictionary(base1)) return base1;
|
|
|
| string base2 = word.substr(0, word.length() - 3) + "fe";
|
| if (check_dictionary(base2)) return base2;
|
| }
|
|
|
|
|
| if (word.length() > 2 && word.substr(word.length() - 2) == "es") {
|
| string base = word.substr(0, word.length() - 2);
|
| if (check_dictionary(base)) return base;
|
| }
|
|
|
|
|
| if (word.length() > 1 && word.back() == 's' && word[word.length() - 2] != 's') {
|
| string base = word.substr(0, word.length() - 1);
|
| if (check_dictionary(base)) return base;
|
| }
|
|
|
|
|
| return nullopt;
|
| }
|
|
|
|
|
| static const char* const ones[] = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
|
| "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen",
|
| "seventeen", "eighteen", "nineteen"};
|
| static const char* const tens[] = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
|
| static const char* const scales[] = {"", "thousand", "million", "billion", "trillion", "quadrillion",
|
| "quintillion", "sextillion", "septillion", "octillion", "nonillion",
|
| "decillion", "undecillion", "duodecillion", "tredecillion",
|
| "quattuordecillion", "quindecillion", "sexdecillion", "septendecillion",
|
| "octodecillion", "novemdecillion", "vigintillion", "googol"};
|
|
|
| static vector<string> digit_to_words(const string& input_s) {
|
| vector<string> words;
|
| if (input_s.empty()) return words;
|
|
|
|
|
| string int_part = input_s;
|
| string frac_part = "";
|
| size_t dot_pos = input_s.find('.');
|
| if (dot_pos != string::npos) {
|
| int_part = input_s.substr(0, dot_pos);
|
| frac_part = input_s.substr(dot_pos + 1);
|
| }
|
|
|
|
|
| string s;
|
| for (char c : int_part) {
|
| if (isdigit(static_cast<unsigned char>(c))) {
|
| s.push_back(c);
|
| }
|
| }
|
|
|
|
|
| if (s.empty()) {
|
|
|
| bool has_frac_digits = false;
|
| for (char c : frac_part) {
|
| if (isdigit(static_cast<unsigned char>(c))) has_frac_digits = true;
|
| }
|
| if (!has_frac_digits) return words;
|
| words.push_back("zero");
|
| } else {
|
| size_t first_non_zero = s.find_first_not_of('0');
|
| if (first_non_zero == string::npos) {
|
| words.push_back("zero");
|
| } else {
|
| string num = s.substr(first_non_zero);
|
|
|
|
|
| if (num.length() > 69) {
|
| for (char c : num) {
|
| words.push_back(ones[c - '0']);
|
| }
|
| } else {
|
| int scale_idx = 0;
|
| while (!num.empty()) {
|
| int chunk_len = min<int>(3, num.length());
|
| string chunk_str = num.substr(num.length() - chunk_len);
|
| num = num.substr(0, num.length() - chunk_len);
|
|
|
| int chunk = stoi(chunk_str);
|
| if (chunk > 0) {
|
| vector<string> chunk_words;
|
| int h = chunk / 100;
|
| int remainder = chunk % 100;
|
|
|
| if (h > 0) {
|
| chunk_words.push_back(ones[h]);
|
| chunk_words.push_back("hundred");
|
| }
|
|
|
| if (remainder > 0) {
|
| if (remainder < 20) {
|
| chunk_words.push_back(ones[remainder]);
|
| } else {
|
| chunk_words.push_back(tens[remainder / 10]);
|
| if (remainder % 10 > 0) {
|
| chunk_words.push_back(ones[remainder % 10]);
|
| }
|
| }
|
| }
|
|
|
| if (scale_idx > 0 && scale_idx < static_cast<int>(sizeof(scales)/sizeof(scales[0]))) {
|
| chunk_words.push_back(scales[scale_idx]);
|
| }
|
|
|
| words.insert(words.begin(), chunk_words.begin(), chunk_words.end());
|
| }
|
| scale_idx++;
|
| }
|
| }
|
| }
|
| }
|
|
|
|
|
| if (!frac_part.empty()) {
|
| bool has_frac_digits = false;
|
| for (char c : frac_part) {
|
| if (isdigit(static_cast<unsigned char>(c))) has_frac_digits = true;
|
| }
|
| if (has_frac_digits) {
|
| words.push_back("point");
|
| for (char c : frac_part) {
|
| if (isdigit(static_cast<unsigned char>(c))) {
|
| words.push_back(ones[c - '0']);
|
| }
|
| }
|
| }
|
| }
|
|
|
| return words;
|
| }
|
|
|
| static vector<string> tokenize_others(const string &s) {
|
| if (check_dictionary(s)) {
|
| string lower_s;
|
| lower_s.reserve(s.size());
|
| for (char c : s) {
|
| lower_s.push_back(to_low(c));
|
| }
|
| return { lower_s };
|
| }
|
|
|
|
|
| auto is_num_char = [](unsigned char c) {
|
| return isdigit(c) != 0 || c == ',' || c == '.';
|
| };
|
| bool is_all_digits = !s.empty() && all_of(s.begin(), s.end(), is_num_char) &&
|
| any_of(s.begin(), s.end(), [](unsigned char c) { return isdigit(c) != 0; });
|
|
|
| if (is_all_digits) {
|
| return digit_to_words(s);
|
| }
|
|
|
| vector<string> out;
|
| string cur;
|
|
|
| auto flush = [&]() {
|
| if (!cur.empty()) {
|
|
|
| bool cur_all_digits = all_of(cur.begin(), cur.end(), [](unsigned char c) {
|
| return isdigit(c) != 0 || c == ',' || c == '.';
|
| });
|
| bool has_digits = any_of(cur.begin(), cur.end(), [](unsigned char c) {
|
| return isdigit(c) != 0;
|
| });
|
|
|
| if (cur_all_digits && has_digits) {
|
| auto words = digit_to_words(cur);
|
| out.insert(out.end(), words.begin(), words.end());
|
| } else {
|
| auto valid_base = get_valid_base_form(cur);
|
| if (valid_base.has_value()) {
|
| out.push_back(valid_base.value());
|
| }
|
| }
|
| cur.clear();
|
| }
|
| };
|
|
|
| for (size_t i = 0; i < s.size(); ++i) {
|
| unsigned char uc = static_cast<unsigned char>(s[i]);
|
| char ch = static_cast<char>(uc);
|
|
|
|
|
| if (ispunct(uc) || (isprint(uc) && !isalnum(uc) && !isspace(uc))) {
|
|
|
|
|
| if ((ch == ',' || ch == '.') &&
|
| !cur.empty() &&
|
| (isdigit(static_cast<unsigned char>(cur.back())) != 0 || cur.back() == ',' || cur.back() == '.') &&
|
| (i + 1 < s.size()) && isdigit(static_cast<unsigned char>(s[i+1])) != 0) {
|
| cur.push_back(ch);
|
| continue;
|
| }
|
|
|
| flush();
|
| string sym(1, ch);
|
|
|
|
|
| if (i + 1 < s.size()) {
|
| unsigned char nxt_uc = static_cast<unsigned char>(s[i+1]);
|
| if (ispunct(nxt_uc) || (isprint(nxt_uc) && !isalnum(nxt_uc) && !isspace(nxt_uc))) {
|
| string sym2 = sym + static_cast<char>(nxt_uc);
|
| if (check_dictionary(sym2)) {
|
| out.push_back(sym2);
|
| ++i;
|
| continue;
|
| }
|
| }
|
| }
|
| if (check_dictionary(sym)) {
|
| out.push_back(sym);
|
| }
|
| continue;
|
| }
|
|
|
| if (isspace(uc)) {
|
| flush();
|
| continue;
|
| }
|
|
|
| const bool is_upper = isupper(uc) != 0;
|
| bool camel_boundary = false;
|
| if (is_upper && !cur.empty()) {
|
| unsigned char prev = static_cast<unsigned char>(s[i - 1]);
|
| const bool prev_lower_or_digit = (islower(prev) != 0) || (isdigit(prev) != 0);
|
| const bool prev_upper = isupper(prev) != 0;
|
| const bool next_lower = (i + 1 < s.size()) && (islower(static_cast<unsigned char>(s[i + 1])) != 0);
|
| camel_boundary = prev_lower_or_digit || (prev_upper && next_lower);
|
| }
|
|
|
| bool digit_boundary = false;
|
| if (!cur.empty()) {
|
| unsigned char prev = static_cast<unsigned char>(s[i - 1]);
|
| bool prev_digit = (isdigit(prev) != 0) || prev == ',' || prev == '.';
|
| bool curr_digit = isdigit(uc) != 0;
|
| if (prev_digit != curr_digit) {
|
| digit_boundary = true;
|
| }
|
| }
|
|
|
| if (camel_boundary || digit_boundary) {
|
| flush();
|
| }
|
|
|
| if (isalnum(uc) != 0) {
|
| cur.push_back(static_cast<char>(tolower(uc)));
|
| } else {
|
| flush();
|
| }
|
| }
|
| flush();
|
| return out;
|
| }
|
|
|
| using StrPtr = const string*;
|
| using TokenId = uint32_t;
|
| static constexpr TokenId TOKEN_ID_INVALID = 0xFFFFFFFFu;
|
|
|
| static inline size_t popcount_u64(uint64_t x){
|
| #if defined(_MSC_VER)
|
| return static_cast<size_t>(__popcnt64(x));
|
| #else
|
| return static_cast<size_t>(__builtin_popcountll(static_cast<unsigned long long>(x)));
|
| #endif
|
| }
|
|
|
| struct StringInterner {
|
| unordered_set<string> pool;
|
| unordered_map<string, TokenId> id_by_string;
|
| vector<const string*> string_by_id;
|
| mutable mutex m;
|
|
|
| const string* intern(const string &s){
|
| lock_guard<mutex> lk(m);
|
|
|
| auto [it, inserted] = pool.emplace(s);
|
| if (inserted){
|
| const TokenId id = static_cast<TokenId>(string_by_id.size());
|
| id_by_string.emplace(*it, id);
|
| string_by_id.push_back(&*it);
|
| }
|
|
|
| return &*it;
|
| }
|
|
|
| TokenId id_of(const string &s) const {
|
| lock_guard<mutex> lk(m);
|
|
|
| auto it = id_by_string.find(s);
|
| return (it == id_by_string.end()) ? TOKEN_ID_INVALID : it->second;
|
| }
|
|
|
| TokenId id_of(const string *p) const {
|
| return p ? id_of(*p) : TOKEN_ID_INVALID;
|
| }
|
|
|
| const string* ptr_from_id(TokenId id) const {
|
| lock_guard<mutex> lk(m);
|
|
|
| return (id < string_by_id.size()) ? string_by_id[(size_t)id] : nullptr;
|
| }
|
|
|
| size_t size() const {
|
| lock_guard<mutex> lk(m);
|
| return string_by_id.size();
|
| }
|
| };
|
|
|
| static inline void bitset_set(uint64_t *bits, size_t words, TokenId id){
|
| if (id == TOKEN_ID_INVALID) return;
|
| const size_t idx = static_cast<size_t>(id >> 6);
|
| if (idx >= words) return;
|
| bits[idx] |= (1ULL << (id & 63u));
|
| }
|
|
|
| static inline size_t bitset_count(const uint64_t *bits, size_t words){
|
| size_t total = 0;
|
| for (size_t i = 0; i < words; ++i) total += popcount_u64(bits[i]);
|
| return total;
|
| }
|
|
|
| static inline size_t bitset_intersection_count(const uint64_t *a, const uint64_t *b, size_t words){
|
| size_t total = 0;
|
| for (size_t i = 0; i < words; ++i) total += popcount_u64(a[i] & b[i]);
|
| return total;
|
| }
|
|
|
| static void build_def_tokens_cache(){
|
| global_def_tokens_cache.clear();
|
| global_pos_cache.clear();
|
|
|
| const int num_entries = static_cast<int>(global_dictionary_entries.size());
|
|
|
| #pragma omp parallel
|
| {
|
| unordered_map<string, vector<string>> local_def_cache;
|
| unordered_map<string, vector<string>> local_pos_cache;
|
|
|
| #pragma omp for schedule(guided) nowait
|
| for (int i = 0; i < num_entries; ++i){
|
| const auto &entry = global_dictionary_entries[i];
|
|
|
| vector<string> all_def_toks;
|
| for (const auto &def : entry.definitions){
|
| auto toks = tokenize_others(def);
|
| all_def_toks.insert(all_def_toks.end(), toks.begin(), toks.end());
|
| }
|
|
|
| string pos = normalize_pos_tag(entry.pos);
|
|
|
| vector<string> sub_words;
|
| string current_sub;
|
| for (char c : entry.word) {
|
| if (c == ';' || c == ',') {
|
| if (!current_sub.empty()) {
|
| sub_words.push_back(current_sub);
|
| current_sub.clear();
|
| }
|
| } else {
|
| current_sub.push_back(c);
|
| }
|
| }
|
| if (!current_sub.empty()) sub_words.push_back(current_sub);
|
|
|
| for (size_t j = 0; j < sub_words.size(); ++j) {
|
| const string key = normalize_dictionary_key(sub_words[j]);
|
| if (key.empty()) continue;
|
|
|
| if (!pos.empty()) {
|
| if (j == sub_words.size() - 1) {
|
| local_pos_cache[key].push_back(move(pos));
|
| } else {
|
| local_pos_cache[key].push_back(pos);
|
| }
|
| }
|
| auto &defs = local_def_cache[key];
|
| defs.insert(defs.end(), all_def_toks.begin(), all_def_toks.end());
|
| }
|
| }
|
|
|
| #pragma omp critical
|
| {
|
| for (auto &pr : local_def_cache) {
|
| auto &vec = global_def_tokens_cache[pr.first];
|
| vec.insert(vec.end(), make_move_iterator(pr.second.begin()), make_move_iterator(pr.second.end()));
|
| }
|
| for (auto &pr : local_pos_cache) {
|
| auto &vec = global_pos_cache[pr.first];
|
| vec.insert(vec.end(), make_move_iterator(pr.second.begin()), make_move_iterator(pr.second.end()));
|
| }
|
| }
|
| }
|
|
|
|
|
| vector<string> def_keys;
|
| def_keys.reserve(global_def_tokens_cache.size());
|
| for (const auto &pr : global_def_tokens_cache) def_keys.push_back(pr.first);
|
|
|
| #pragma omp parallel for schedule(dynamic)
|
| for (ptrdiff_t i = 0; i < static_cast<ptrdiff_t>(def_keys.size()); ++i){
|
| auto &v = global_def_tokens_cache[def_keys[i]];
|
| sort(v.begin(), v.end());
|
| v.erase(unique(v.begin(), v.end()), v.end());
|
| }
|
|
|
| vector<string> pos_keys;
|
| pos_keys.reserve(global_pos_cache.size());
|
| for (const auto &pr : global_pos_cache) pos_keys.push_back(pr.first);
|
|
|
| #pragma omp parallel for schedule(dynamic)
|
| for (ptrdiff_t i = 0; i < static_cast<ptrdiff_t>(pos_keys.size()); ++i){
|
| auto &v = global_pos_cache[pos_keys[i]];
|
| sort(v.begin(), v.end());
|
| v.erase(unique(v.begin(), v.end()), v.end());
|
| }
|
| }
|
|
|
| struct PtrHash { size_t operator()(StrPtr p) const noexcept { return hash<StrPtr>()(p); } };
|
| struct PtrEq { bool operator()(StrPtr a, StrPtr b) const noexcept { return a == b; } };
|
|
|
| using NextSet = vector<StrPtr>;
|
|
|
| struct NgramHash {
|
| size_t operator()(const vector<StrPtr>& v) const noexcept {
|
| size_t seed = v.size();
|
| for(auto& p : v) {
|
| seed ^= hash<StrPtr>()(p) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
|
| }
|
| return seed;
|
| }
|
| };
|
|
|
| struct KnowledgeBase {
|
| StringInterner interner;
|
|
|
| unordered_map<vector<StrPtr>, NextSet, NgramHash> next;
|
| mutable mutex m;
|
|
|
| unordered_map<StrPtr, vector<StrPtr>, PtrHash, PtrEq> def_index;
|
| mutable mutex def_m;
|
| int def_depth = 0;
|
|
|
| void add_ngram(const vector<StrPtr>& ctx, StrPtr v){
|
| for (auto p : ctx) ensure_def_for_interned(p);
|
| ensure_def_for_interned(v);
|
|
|
| lock_guard<mutex> lk(m);
|
| auto &vec = next[ctx];
|
| for (auto p : vec) if (p == v) return;
|
| vec.push_back(v);
|
| }
|
|
|
| void set_def_depth(int D){
|
| lock_guard<mutex> lk(def_m);
|
| if (D != def_depth){
|
| def_index.clear();
|
| def_depth = D;
|
| }
|
| }
|
|
|
| void ensure_def_for_interned(StrPtr wp){
|
| if (wp == nullptr || def_depth <= 0) return;
|
|
|
| {
|
| lock_guard<mutex> lk(def_m);
|
| if (def_index.find(wp) != def_index.end()) return;
|
| }
|
|
|
| unordered_set<StrPtr, PtrHash, PtrEq> acc;
|
| vector<StrPtr> frontier;
|
|
|
| const string start_key = normalize_dictionary_key(*wp);
|
| if (!start_key.empty()){
|
| auto it_def = global_def_tokens_cache.find(start_key);
|
| if (it_def != global_def_tokens_cache.end()){
|
| for (const auto &tok : it_def->second){
|
| StrPtr tp = interner.intern(tok);
|
| if (acc.insert(tp).second) frontier.push_back(tp);
|
| }
|
| }
|
| }
|
|
|
| for (int depth = 1; depth < def_depth && !frontier.empty(); ++depth){
|
| vector<StrPtr> next_frontier;
|
|
|
| for (StrPtr w : frontier){
|
| const string key = normalize_dictionary_key(*w);
|
| if (key.empty()) continue;
|
|
|
| auto it2 = global_def_tokens_cache.find(key);
|
| if (it2 == global_def_tokens_cache.end()) continue;
|
|
|
| for (const auto &tok : it2->second){
|
| StrPtr tp = interner.intern(tok);
|
| if (acc.insert(tp).second) next_frontier.push_back(tp);
|
| }
|
| }
|
|
|
| frontier.swap(next_frontier);
|
| }
|
|
|
| vector<StrPtr> out;
|
| out.reserve(acc.size());
|
| for (StrPtr p : acc) out.push_back(p);
|
|
|
| {
|
| lock_guard<mutex> lk(def_m);
|
| def_index.emplace(wp, move(out));
|
| }
|
| }
|
|
|
| optional<NextSet> lookup_ngram(const vector<StrPtr>& ctx) const {
|
| lock_guard<mutex> lk(m);
|
| auto it = next.find(ctx);
|
| if (it == next.end()) return nullopt;
|
| return it->second;
|
| }
|
| };
|
|
|
| static void learn_tokens_ngram(KnowledgeBase &kb, const vector<string>& tokens, int n_gram_size) {
|
| vector<StrPtr> window;
|
| for (const auto& tok : tokens) {
|
| StrPtr tp = kb.interner.intern(tok);
|
| for (size_t j = 0; j < window.size(); ++j) {
|
| vector<StrPtr> ctx(window.begin() + j, window.end());
|
| kb.add_ngram(ctx, tp);
|
| }
|
| window.push_back(tp);
|
| if (window.size() > static_cast<size_t>(n_gram_size)) window.erase(window.begin());
|
| }
|
| }
|
|
|
| static vector<StrPtr>
|
| intern_tokens(KnowledgeBase &kb, const vector<string> &tokens)
|
| {
|
| vector<StrPtr> out;
|
| out.reserve(tokens.size());
|
| for (const auto &t : tokens) out.push_back(kb.interner.intern(t));
|
| return out;
|
| }
|
|
|
| static inline bool json_valid_index(size_t i, size_t n){ return i < n; }
|
|
|
| static string parse_quoted_string(const string &text, size_t &i){
|
| string out;
|
| if (!json_valid_index(i, text.size()) || text[i] != '"') throw runtime_error("expected '\"'");
|
| ++i;
|
| while (json_valid_index(i, text.size())){
|
| char c = text[i++];
|
| if (c == '"') break;
|
| if (c == '\\'){
|
| if (!json_valid_index(i, text.size())) break;
|
| char e = text[i++];
|
| if (e=='n') out.push_back('\n');
|
| else if (e=='t') out.push_back('\t');
|
| else out.push_back(e);
|
| } else out.push_back(c);
|
| }
|
| return out;
|
| }
|
|
|
| static void skip_spaces(const string &s, size_t &i){
|
| while (json_valid_index(i, s.size()) && is_space(s[i])) ++i;
|
| }
|
|
|
| static void skip_json_value(const string &s, size_t &i);
|
|
|
| static vector<string> parse_json_string_array(const string &text, size_t &i){
|
| vector<string> out;
|
| if (!json_valid_index(i, text.size()) || text[i] != '[') return out;
|
|
|
| ++i;
|
| while (true){
|
| skip_spaces(text, i);
|
| if (!json_valid_index(i, text.size())) break;
|
| if (text[i] == ']'){ ++i; break; }
|
|
|
| if (text[i] == '"') out.push_back(parse_quoted_string(text, i));
|
| else skip_json_value(text, i);
|
|
|
| skip_spaces(text, i);
|
| if (json_valid_index(i, text.size()) && text[i] == ','){ ++i; continue; }
|
| if (json_valid_index(i, text.size()) && text[i] == ']'){ ++i; break; }
|
| }
|
|
|
| return out;
|
| }
|
|
|
| static void skip_json_value(const string &s, size_t &i){
|
| skip_spaces(s, i);
|
| if (!json_valid_index(i, s.size())) return;
|
|
|
| if (s[i] == '"'){
|
| (void)parse_quoted_string(s, i);
|
| return;
|
| }
|
|
|
| if (s[i] == '['){
|
| ++i;
|
| while (json_valid_index(i, s.size())){
|
| skip_spaces(s, i);
|
| if (!json_valid_index(i, s.size())) break;
|
| if (s[i] == ']'){ ++i; break; }
|
| skip_json_value(s, i);
|
| skip_spaces(s, i);
|
| if (json_valid_index(i, s.size()) && s[i] == ','){ ++i; continue; }
|
| if (json_valid_index(i, s.size()) && s[i] == ']'){ ++i; break; }
|
| }
|
| return;
|
| }
|
|
|
| if (s[i] == '{'){
|
| ++i;
|
| while (json_valid_index(i, s.size())){
|
| skip_spaces(s, i);
|
| if (!json_valid_index(i, s.size())) break;
|
| if (s[i] == '}'){ ++i; break; }
|
| if (s[i] == '"'){
|
| (void)parse_quoted_string(s, i);
|
| skip_spaces(s, i);
|
| if (json_valid_index(i, s.size()) && s[i] == ':') ++i;
|
| skip_json_value(s, i);
|
| skip_spaces(s, i);
|
| if (json_valid_index(i, s.size()) && s[i] == ','){ ++i; continue; }
|
| if (json_valid_index(i, s.size()) && s[i] == '}'){ ++i; break; }
|
| } else {
|
| ++i;
|
| }
|
| }
|
| return;
|
| }
|
|
|
| while (json_valid_index(i, s.size())){
|
| char c = s[i];
|
| if (c == ',' || c == ']' || c == '}' || is_space(c)) break;
|
| ++i;
|
| }
|
| }
|
|
|
| static vector<DictionaryEntry> parse_dictionary_json(){
|
| vector<DictionaryEntry> dictionary;
|
| if (dictionary_json_len == 0) return dictionary;
|
|
|
| string text;
|
| text.reserve(dictionary_json_len);
|
| for (unsigned int b = 0; b < dictionary_json_len; ++b){
|
| text.push_back(static_cast<char>(dictionary_json[b]));
|
| }
|
|
|
| size_t i = 0;
|
| skip_spaces(text, i);
|
| if (!json_valid_index(i, text.size()) || text[i] != '[') return dictionary;
|
| ++i;
|
|
|
| while (true){
|
| skip_spaces(text, i);
|
| if (!json_valid_index(i, text.size())) break;
|
| if (text[i] == ']'){ ++i; break; }
|
| if (text[i] != '{'){
|
| skip_json_value(text, i);
|
| skip_spaces(text, i);
|
| if (json_valid_index(i, text.size()) && text[i] == ','){ ++i; continue; }
|
| if (json_valid_index(i, text.size()) && text[i] == ']'){ ++i; break; }
|
| continue;
|
| }
|
|
|
| ++i;
|
| DictionaryEntry entry;
|
|
|
| while (true){
|
| skip_spaces(text, i);
|
| if (!json_valid_index(i, text.size())) break;
|
| if (text[i] == '}'){ ++i; break; }
|
|
|
| string field = parse_quoted_string(text, i);
|
| skip_spaces(text, i);
|
| if (!json_valid_index(i, text.size()) || text[i] != ':') break;
|
| ++i;
|
| skip_spaces(text, i);
|
|
|
| if (field == "word"){
|
| entry.word = parse_quoted_string(text, i);
|
| } else if (field == "pos"){
|
| entry.pos = parse_quoted_string(text, i);
|
| } else if (field == "definitions"){
|
| entry.definitions = parse_json_string_array(text, i);
|
| } else {
|
| skip_json_value(text, i);
|
| }
|
|
|
| skip_spaces(text, i);
|
| if (json_valid_index(i, text.size()) && text[i] == ','){ ++i; continue; }
|
| if (json_valid_index(i, text.size()) && text[i] == '}'){ ++i; break; }
|
| }
|
|
|
| if (!entry.word.empty()) dictionary.push_back(move(entry));
|
|
|
| skip_spaces(text, i);
|
| if (json_valid_index(i, text.size()) && text[i] == ','){ ++i; continue; }
|
| if (json_valid_index(i, text.size()) && text[i] == ']'){ ++i; break; }
|
| }
|
|
|
| return dictionary;
|
| }
|
|
|
| static string best_candidate_by_similarity(
|
| const NextSet &cands,
|
| const vector<StrPtr> &prompt_ptrs,
|
| const vector<StrPtr> &resp_ptrs,
|
| const unordered_map<StrPtr, vector<StrPtr>, PtrHash, PtrEq> &def_index,
|
| const StringInterner &interner,
|
| const unordered_map<string,int> &recent_counts,
|
| double repeat_penalty,
|
| const string &context_tok)
|
| {
|
| if (cands.empty()) return string();
|
| if (cands.size() == 1) return *cands[0];
|
|
|
| const size_t words = max<size_t>(1, (interner.size() + 63u) / 64u);
|
|
|
| vector<uint64_t> agg_words(words, 0ULL);
|
|
|
| auto add_token_and_defs = [&](StrPtr t){
|
| if (!t) return;
|
|
|
|
|
| TokenId tid = interner.id_of(t);
|
| if (tid != TOKEN_ID_INVALID) bitset_set(agg_words.data(), words, tid);
|
|
|
| auto it = def_index.find(t);
|
| if (it != def_index.end()){
|
| for (StrPtr d : it->second){
|
| TokenId did = interner.id_of(d);
|
| if (did != TOKEN_ID_INVALID) bitset_set(agg_words.data(), words, did);
|
| }
|
| }
|
|
|
|
|
| vector<string> sub_tokens = tokenize_others(*t);
|
| for (const string& sub_tok : sub_tokens) {
|
|
|
|
|
| TokenId sub_tid = interner.id_of(sub_tok);
|
|
|
| if (sub_tid != TOKEN_ID_INVALID) {
|
|
|
| bitset_set(agg_words.data(), words, sub_tid);
|
|
|
|
|
| StrPtr sub_ptr = interner.ptr_from_id(sub_tid);
|
| if (sub_ptr) {
|
| auto sub_it = def_index.find(sub_ptr);
|
| if (sub_it != def_index.end()) {
|
|
|
| for (StrPtr d : sub_it->second) {
|
| TokenId did = interner.id_of(d);
|
| if (did != TOKEN_ID_INVALID) bitset_set(agg_words.data(), words, did);
|
| }
|
| }
|
| }
|
| }
|
| }
|
| };
|
|
|
| for (StrPtr t : prompt_ptrs) add_token_and_defs(t);
|
| for (StrPtr t : resp_ptrs) add_token_and_defs(t);
|
|
|
| const size_t agg_count = bitset_count(agg_words.data(), words);
|
|
|
| const size_t M = cands.size();
|
| vector<uint64_t> cand_words(M * words, 0ULL);
|
| vector<size_t> cand_counts(M, 0);
|
|
|
| for (size_t i = 0; i < M; ++i){
|
| uint64_t *row = cand_words.data() + i * words;
|
| const StrPtr cand = cands[i];
|
|
|
|
|
| TokenId cid = interner.id_of(cand);
|
| if (cid != TOKEN_ID_INVALID) bitset_set(row, words, cid);
|
|
|
|
|
| auto it = def_index.find(cand);
|
| if (it != def_index.end()){
|
| for (StrPtr d : it->second){
|
| TokenId did = interner.id_of(d);
|
| if (did != TOKEN_ID_INVALID) bitset_set(row, words, did);
|
| }
|
| }
|
|
|
|
|
| vector<string> sub_tokens = tokenize_others(*cand);
|
| for (const string& sub_tok : sub_tokens) {
|
|
|
|
|
| TokenId sub_tid = interner.id_of(sub_tok);
|
|
|
| if (sub_tid != TOKEN_ID_INVALID) {
|
|
|
| bitset_set(row, words, sub_tid);
|
|
|
|
|
| StrPtr sub_ptr = interner.ptr_from_id(sub_tid);
|
| if (sub_ptr) {
|
| auto sub_it = def_index.find(sub_ptr);
|
| if (sub_it != def_index.end()) {
|
|
|
| for (StrPtr d : sub_it->second) {
|
| TokenId did = interner.id_of(d);
|
| if (did != TOKEN_ID_INVALID) bitset_set(row, words, did);
|
| }
|
| }
|
| }
|
| }
|
| }
|
|
|
|
|
| cand_counts[i] = bitset_count(row, words);
|
| }
|
|
|
| vector<double> scores(M, 0.0);
|
|
|
| #if defined(_OPENMP) && defined(CHATIPC_ENABLE_OMP_TARGET)
|
| const bool use_target = (omp_get_num_devices() > 0) && (M >= 256);
|
| #else
|
| const bool use_target = false;
|
| #endif
|
|
|
| if (use_target){
|
| uint64_t *agg_ptr = agg_words.data();
|
| uint64_t *cand_ptr = cand_words.data();
|
| size_t *count_ptr = cand_counts.data();
|
| double *score_ptr = scores.data();
|
| const size_t cand_words_total = cand_words.size();
|
|
|
| #pragma omp target data map(to: agg_ptr[0:words], cand_ptr[0:cand_words_total], count_ptr[0:M]) map(from: score_ptr[0:M])
|
| {
|
| #pragma omp target teams distribute parallel for
|
| for (ptrdiff_t i = 0; i < static_cast<ptrdiff_t>(M); ++i){
|
| const uint64_t *row = cand_ptr + static_cast<size_t>(i) * words;
|
|
|
| size_t inter = 0;
|
| for (size_t w = 0; w < words; ++w){
|
| inter += popcount_u64(agg_ptr[w] & row[w]);
|
| }
|
|
|
| const size_t uni = agg_count + count_ptr[(size_t)i] - inter;
|
| score_ptr[(size_t)i] = uni ? static_cast<double>(inter) / static_cast<double>(uni) : 0.0;
|
| }
|
| }
|
| } else {
|
| #ifdef _OPENMP
|
| #pragma omp parallel for schedule(static)
|
| #endif
|
| for (ptrdiff_t i = 0; i < static_cast<ptrdiff_t>(M); ++i){
|
| const uint64_t *row = cand_words.data() + static_cast<size_t>(i) * words;
|
|
|
| const size_t inter = bitset_intersection_count(agg_words.data(), row, words);
|
| const size_t uni = agg_count + cand_counts[(size_t)i] - inter;
|
| scores[(size_t)i] = uni ? static_cast<double>(inter) / static_cast<double>(uni) : 0.0;
|
| }
|
| }
|
|
|
| double best = -1e9;
|
| string best_tok;
|
|
|
| for (size_t i = 0; i < M; ++i){
|
| const string &tok = *cands[i];
|
| const string tok_key = normalize_dictionary_key(tok);
|
| const string count_key = tok_key.empty() ? tok : tok_key;
|
|
|
| auto rc_it = recent_counts.find(count_key);
|
| const int cnt = (rc_it == recent_counts.end()) ? 0 : rc_it->second;
|
|
|
| const double adjusted =
|
| scores[i] +
|
| english_rule_bonus(context_tok, tok) -
|
| repeat_penalty * static_cast<double>(cnt);
|
|
|
| if (adjusted > best || (adjusted == best && tok < best_tok)){
|
| best = adjusted;
|
| best_tok = tok;
|
| }
|
| }
|
|
|
| return best_tok;
|
| }
|
|
|
| static vector<string> construct_response(KnowledgeBase &kb,
|
| const vector<string> &prompt_toks,
|
| size_t response_maxlen,
|
| double repeat_penalty,
|
| int n_gram_size,
|
| bool allow_path_loops)
|
| {
|
| vector<string> resp;
|
| if (prompt_toks.empty() || response_maxlen == 0) return resp;
|
|
|
| auto prompt_ptrs = intern_tokens(kb, prompt_toks);
|
| vector<StrPtr> resp_ptrs;
|
| unordered_map<string, int> recent_counts;
|
|
|
|
|
| vector<StrPtr> context = prompt_ptrs;
|
|
|
| auto would_create_2_cycle = [&](const string &cand) -> bool {
|
| if (resp.size() < 3) return false;
|
| return normalize_dictionary_key(cand) == normalize_dictionary_key(resp[resp.size() - 2]) &&
|
| normalize_dictionary_key(resp.back()) == normalize_dictionary_key(resp[resp.size() - 3]);
|
| };
|
|
|
| for (size_t step = 0; step < response_maxlen; ++step){
|
| NextSet candidates;
|
| bool found = false;
|
| string context_tok;
|
|
|
| int current_n = min(static_cast<int>(context.size()), n_gram_size);
|
| while (current_n > 0) {
|
| vector<StrPtr> search_ctx(context.end() - current_n, context.end());
|
| auto opt = kb.lookup_ngram(search_ctx);
|
| if (opt && !opt->empty()) {
|
| candidates = *opt;
|
| found = true;
|
| context_tok = *search_ctx.back();
|
| break;
|
| }
|
| current_n--;
|
| }
|
|
|
| if (!found || candidates.empty()) break;
|
|
|
| if (candidates.size() == 1){
|
| string only = *candidates[0];
|
| string only_key = normalize_dictionary_key(only);
|
| if (!allow_path_loops && recent_counts[only_key.empty() ? only : only_key] > 0) break;
|
|
|
| resp.push_back(only);
|
| StrPtr ptr = kb.interner.intern(only);
|
| resp_ptrs.push_back(ptr);
|
| context.push_back(ptr);
|
| recent_counts[only_key.empty() ? only : only_key] += 1;
|
| cout << only << ' ' << flush;
|
| continue;
|
| }
|
|
|
| string chosen = best_candidate_by_similarity(
|
| candidates, prompt_ptrs, resp_ptrs, kb.def_index, kb.interner,
|
| recent_counts, repeat_penalty, context_tok
|
| );
|
|
|
| if (chosen.empty()) break;
|
| if (!allow_path_loops && would_create_2_cycle(chosen)) break;
|
|
|
| resp.push_back(chosen);
|
| StrPtr chosen_ptr = kb.interner.intern(chosen);
|
| resp_ptrs.push_back(chosen_ptr);
|
| context.push_back(chosen_ptr);
|
|
|
| string chosen_key = normalize_dictionary_key(chosen);
|
| recent_counts[chosen_key.empty() ? chosen : chosen_key] += 1;
|
|
|
| cout << chosen << ' ' << flush;
|
| }
|
|
|
| return resp;
|
| }
|
|
|
| static void learn_from_file(KnowledgeBase &kb, const string &fname, int n_gram_size){
|
| ifstream ifs(fname);
|
| if (!ifs) return;
|
| vector<string> tokens;
|
| string tok;
|
| while (ifs >> tok) tokens.push_back(tok);
|
| learn_tokens_ngram(kb, tokens, n_gram_size);
|
| }
|
|
|
| static void learn_files_parallel(KnowledgeBase &kb, const vector<string> &files, int n_gram_size){
|
| #pragma omp parallel for schedule(dynamic)
|
| for (ptrdiff_t i=0;i<static_cast<ptrdiff_t>(files.size());++i){
|
| learn_from_file(kb, files[(size_t)i], n_gram_size);
|
| }
|
| }
|
|
|
| static constexpr uint64_t KB_MAGIC = 0x434850434B535641ULL;
|
| static constexpr uint64_t KB_VERSION = 2ULL;
|
|
|
| static void write_u64(ostream &os, uint64_t v) {
|
| do {
|
| unsigned char byte = v & 0x7F;
|
| v >>= 7;
|
| if (v != 0) byte |= 0x80;
|
| os.put(static_cast<char>(byte));
|
| } while (v != 0);
|
| if (!os) throw runtime_error("write_u64 failed");
|
| }
|
|
|
| static uint64_t read_u64(istream &is) {
|
| uint64_t v = 0;
|
| unsigned int shift = 0;
|
| unsigned char byte;
|
| do {
|
| if (!is.read(reinterpret_cast<char*>(&byte), 1)) {
|
| throw runtime_error("read_u64 failed");
|
| }
|
| v |= (static_cast<uint64_t>(byte & 0x7F) << shift);
|
| shift += 7;
|
| } while (byte & 0x80);
|
| return v;
|
| }
|
|
|
| static void write_string(ostream &os, const string &s){
|
| write_u64(os, static_cast<uint64_t>(s.size()));
|
| if (!s.empty()){
|
| os.write(s.data(), static_cast<streamsize>(s.size()));
|
| if(!os) throw runtime_error("write_string failed");
|
| }
|
| }
|
|
|
| static string read_string(istream &is){
|
| uint64_t n = read_u64(is);
|
|
|
|
|
| string s;
|
| s.resize(static_cast<size_t>(n));
|
|
|
| if (n != 0){
|
| is.read(&s[0], static_cast<streamsize>(n));
|
| if(!is) throw runtime_error("read_string failed");
|
| }
|
| return s;
|
| }
|
|
|
| static void save_kb_binary(const KnowledgeBase &kb, const string &fname){
|
| const string temp = fname + ".tmp";
|
|
|
| {
|
| ofstream ofs(temp.c_str(), ios::binary | ios::trunc);
|
| if (!ofs) throw runtime_error("cannot open temp save file");
|
|
|
| vector<string> pool;
|
| pool.reserve(kb.interner.pool.size());
|
| for (const auto &s : kb.interner.pool) pool.push_back(s);
|
|
|
| sort(pool.begin(), pool.end());
|
|
|
| unordered_map<string, uint64_t> id;
|
| id.reserve(pool.size());
|
| for (uint64_t i = 0; i < static_cast<uint64_t>(pool.size()); ++i){
|
| id.emplace(pool[(size_t)i], i);
|
| }
|
|
|
| write_u64(ofs, KB_MAGIC);
|
| write_u64(ofs, KB_VERSION);
|
| write_u64(ofs, static_cast<uint64_t>(kb.def_depth));
|
|
|
| write_u64(ofs, static_cast<uint64_t>(pool.size()));
|
| for (const auto &s : pool) write_string(ofs, s);
|
|
|
| write_u64(ofs, static_cast<uint64_t>(kb.next.size()));
|
| for (const auto &pr : kb.next){
|
| write_u64(ofs, static_cast<uint64_t>(pr.first.size()));
|
| for (StrPtr ctx_tok : pr.first){
|
| write_u64(ofs, id.at(*ctx_tok));
|
| }
|
| write_u64(ofs, static_cast<uint64_t>(pr.second.size()));
|
| for (StrPtr nxt : pr.second){
|
| write_u64(ofs, id.at(*nxt));
|
| }
|
| }
|
|
|
| write_u64(ofs, static_cast<uint64_t>(kb.def_index.size()));
|
| for (const auto &pr : kb.def_index){
|
| write_u64(ofs, id.at(*pr.first));
|
| write_u64(ofs, static_cast<uint64_t>(pr.second.size()));
|
| for (StrPtr tok : pr.second){
|
| write_u64(ofs, id.at(*tok));
|
| }
|
| }
|
|
|
| ofs.flush();
|
| if (!ofs) throw runtime_error("failed while writing temp save file");
|
| }
|
|
|
| remove(fname.c_str());
|
| if (rename(temp.c_str(), fname.c_str()) != 0){
|
| remove(temp.c_str());
|
| throw runtime_error("failed to commit save file");
|
| }
|
| }
|
|
|
| static void load_kb_binary(KnowledgeBase &kb, const string &fname, int cli_def_depth){
|
| ifstream ifs(fname, ios::binary);
|
| if (!ifs) throw runtime_error("cannot open load file");
|
|
|
| const uint64_t magic = read_u64(ifs);
|
| if (magic != KB_MAGIC) throw runtime_error("bad save file magic");
|
|
|
| const uint64_t version = read_u64(ifs);
|
| if (version != KB_VERSION) throw runtime_error("unsupported save file version");
|
|
|
| const uint64_t file_def_depth = read_u64(ifs);
|
|
|
| const uint64_t N = read_u64(ifs);
|
|
|
|
|
| vector<string> strings;
|
| strings.reserve(static_cast<size_t>(N));
|
|
|
| for (uint64_t i = 0; i < N; ++i){
|
| strings.push_back(read_string(ifs));
|
| }
|
|
|
| kb.interner.pool.clear();
|
| kb.interner.pool.reserve(static_cast<size_t>(N));
|
|
|
| vector<StrPtr> ptrs;
|
| ptrs.reserve(static_cast<size_t>(N));
|
| for (const auto &s : strings){
|
| ptrs.push_back(kb.interner.intern(s));
|
| }
|
|
|
|
|
| const uint64_t E = read_u64(ifs);
|
|
|
|
|
| {
|
| lock_guard<mutex> lk(kb.m);
|
| kb.next.clear();
|
| kb.next.reserve(static_cast<size_t>(E));
|
| }
|
|
|
| for (uint64_t i = 0; i < E; ++i){
|
| const uint64_t ctx_size = read_u64(ifs);
|
|
|
|
|
| vector<StrPtr> ctx;
|
| ctx.reserve(static_cast<size_t>(ctx_size));
|
| for(uint64_t c = 0; c < ctx_size; ++c) {
|
| const uint64_t c_idx = read_u64(ifs);
|
| if (c_idx >= ptrs.size()) throw runtime_error("save file is corrupted: bad context key");
|
| ctx.push_back(ptrs[(size_t)c_idx]);
|
| }
|
|
|
| const uint64_t M = read_u64(ifs);
|
|
|
|
|
| NextSet vec;
|
| vec.reserve(static_cast<size_t>(M));
|
|
|
| for (uint64_t j = 0; j < M; ++j){
|
| const uint64_t v_idx = read_u64(ifs);
|
| if (v_idx >= ptrs.size()) throw runtime_error("save file is corrupted: bad graph value");
|
| vec.push_back(ptrs[(size_t)v_idx]);
|
| }
|
|
|
| {
|
| lock_guard<mutex> lk(kb.m);
|
| kb.next.emplace(move(ctx), move(vec));
|
| }
|
| }
|
|
|
|
|
| const uint64_t K = read_u64(ifs);
|
|
|
|
|
| {
|
| lock_guard<mutex> lk(kb.def_m);
|
| kb.def_index.clear();
|
| kb.def_index.reserve(static_cast<size_t>(K));
|
| kb.def_depth = static_cast<int>(file_def_depth);
|
| }
|
|
|
| for (uint64_t i = 0; i < K; ++i){
|
| const uint64_t key_idx = read_u64(ifs);
|
| const uint64_t M = read_u64(ifs);
|
|
|
| if (key_idx >= ptrs.size()) throw runtime_error("save file is corrupted: bad def key");
|
|
|
|
|
| vector<StrPtr> toks;
|
| toks.reserve(static_cast<size_t>(M));
|
|
|
| for (uint64_t j = 0; j < M; ++j){
|
| const uint64_t v_idx = read_u64(ifs);
|
| if (v_idx >= ptrs.size()) throw runtime_error("save file is corrupted: bad def value");
|
| toks.push_back(ptrs[(size_t)v_idx]);
|
| }
|
|
|
| {
|
| lock_guard<mutex> lk(kb.def_m);
|
| kb.def_index.emplace(ptrs[(size_t)key_idx], move(toks));
|
| }
|
| }
|
|
|
| if (cli_def_depth != static_cast<int>(file_def_depth)){
|
| kb.set_def_depth(cli_def_depth);
|
|
|
| vector<StrPtr> targets;
|
| targets.reserve(ptrs.size() + kb.next.size() * 2);
|
|
|
| unordered_set<StrPtr, PtrHash, PtrEq> seen;
|
| seen.reserve(ptrs.size() + kb.next.size() * 2);
|
|
|
| for (StrPtr p : ptrs){
|
| if (seen.insert(p).second) targets.push_back(p);
|
| }
|
|
|
| {
|
| lock_guard<mutex> lk(kb.m);
|
| for (const auto &pr : kb.next){
|
| for (StrPtr ctx_element : pr.first) {
|
| if (seen.insert(ctx_element).second) {
|
| targets.push_back(ctx_element);
|
| }
|
| }
|
|
|
| for (StrPtr v : pr.second){
|
| if (seen.insert(v).second) {
|
| targets.push_back(v);
|
| }
|
| }
|
| }
|
| }
|
|
|
| #pragma omp parallel for schedule(dynamic)
|
| for (ptrdiff_t i = 0; i < static_cast<ptrdiff_t>(targets.size()); ++i){
|
| kb.ensure_def_for_interned(targets[(size_t)i]);
|
| }
|
| }
|
| }
|
|
|
| static void print_kb_info(const string &fname) {
|
| ifstream ifs(fname, ios::binary);
|
| if (!ifs) {
|
| cerr << "Error: cannot open knowledge-base file " << fname << "\n";
|
| return;
|
| }
|
|
|
| cout << "Reckoning knowledge-base " << fname << " info. ";
|
|
|
| try {
|
| const uint64_t magic = read_u64(ifs);
|
| if (magic != KB_MAGIC) throw runtime_error("bad save file magic");
|
|
|
| const uint64_t version = read_u64(ifs);
|
| if (version != KB_VERSION) throw runtime_error("unsupported save file version");
|
|
|
| const uint64_t file_def_depth = read_u64(ifs);
|
|
|
| const uint64_t N = read_u64(ifs);
|
|
|
|
|
|
|
| for (uint64_t i = 0; i < N; ++i){
|
| uint64_t len = read_u64(ifs);
|
|
|
| if (len > 0) ifs.seekg(static_cast<streamoff>(len), ios_base::cur);
|
| }
|
|
|
| const uint64_t E = read_u64(ifs);
|
|
|
|
|
| uint64_t max_ngram = 0;
|
| for (uint64_t i = 0; i < E; ++i){
|
| const uint64_t ctx_size = read_u64(ifs);
|
|
|
|
|
| if (ctx_size > max_ngram) max_ngram = ctx_size;
|
|
|
|
|
| for(uint64_t c = 0; c < ctx_size; ++c) {
|
| read_u64(ifs);
|
| }
|
|
|
| const uint64_t M = read_u64(ifs);
|
|
|
|
|
|
|
| for(uint64_t j = 0; j < M; ++j){
|
| read_u64(ifs);
|
| }
|
| }
|
|
|
| cout << "The " << fname << " dictionary depth is " << file_def_depth << " and " << fname << " n-gram max size is " << max_ngram << "\n";
|
|
|
| } catch (const exception &e) {
|
| cerr << "Error reading knowledge-base info: " << e.what() << "\n";
|
| }
|
| }
|
|
|
| static void print_commands(const char *p){
|
| cout << p << " command-line interface options:\n";
|
| cout << " --response-max-length N Set maximum number of token(s) in a response. Default number is 500\n";
|
| cout << " --save-kb FILE Save the knowledge-base graph to a binary file.\n";
|
| cout << " --load-kb FILE Load a previously saved knowledge-base graph from a binary file.\n";
|
| cout << " --info-kb FILE Show the dictionary-depth and n-gram max size of a knowledge-base file.\n";
|
| cout << " --static-kb Disable learning prompt(s) and response(s) during interactive session.\n";
|
| cout << " --dictionary-depth D Set depth of definition expansion used during learning. Default depth is 3\n";
|
| cout << " --n-gram-max-size N Set maximum size of the n-gram where N is the size. Default size is 3\n";
|
| cout << " --learn f1 f2 ... Learn from text file(s) to update the knowledge-base graph.\n";
|
| cout << " --repeat-penalty P Set penalty for repeated tokens in response. Default penalty is 0.7 (higher penalty reduce repetition).\n";
|
| cout << " --allow-path-loops Allow finite loops when the knowledge-base graph contains a circular single-path reference.\n";
|
| cout << " --activate-agi Activate the Artificial General Intelligence (AGI) features.\n";
|
| cout << " --help Show " << p << " command-line interface options.\n";
|
| }
|
|
|
| int main(int argc, char **argv){
|
| size_t response_maxlen = 500;
|
| string savefile;
|
| string load_kb;
|
| int def_depth = 3;
|
| int n_gram_size = 3;
|
| double repeat_penalty = 0.7;
|
| vector<string> learn_files;
|
| bool learn_chat = true;
|
| bool allow_path_loops = false;
|
|
|
| for (int i=1;i<argc;++i){
|
| string a = argv[i];
|
| if (a=="--help"){ print_commands(argv[0]); return 0; }
|
| if (a=="--response-max-length" && i+1<argc){ response_maxlen = stoul(argv[++i]); continue; }
|
| if (a=="--save-kb" && i+1<argc){ savefile = argv[++i]; continue; }
|
| if (a=="--load-kb" && i+1<argc){ load_kb = argv[++i]; continue; }
|
| if (a=="--info-kb" && i+1<argc){ print_kb_info(argv[++i]); return 0; }
|
| if (a=="--static-kb"){ learn_chat = false; continue; }
|
| if (a=="--dictionary-depth" && i+1<argc){ def_depth = stoi(argv[++i]); continue; }
|
| if (a=="--n-gram-max-size" && i+1<argc){ n_gram_size = max(1, stoi(argv[++i])); continue; }
|
| if (a=="--learn"){ while(i+1<argc && argv[i+1][0] != '-') learn_files.push_back(argv[++i]); continue; }
|
| if (a=="--repeat-penalty" && i+1<argc){ repeat_penalty = stod(argv[++i]); continue; }
|
| if (a=="--allow-path-loops") { allow_path_loops = true; continue; }
|
| if (a=="--activate-agi"){
|
| cerr << "AGI subscription fee is $1,000 CAD per month. To pay the fee, contact Caleb Nwokocha via email cnwokocha@proton.me\n";
|
| return 0;
|
| }
|
|
|
| cerr << "Error: Unknown or incomplete command-line option '" << a << "'\n";
|
| print_commands(argv[0]);
|
| return 1;
|
| }
|
|
|
| KnowledgeBase kb;
|
|
|
| global_dictionary_entries = parse_dictionary_json();
|
| build_def_tokens_cache();
|
| kb.set_def_depth(def_depth);
|
|
|
| if (!load_kb.empty()){
|
| try { print_kb_info(load_kb);
|
| cerr << "Loading knowledge base " << load_kb << " using values from " << argv[0] << " command-line interface options: --dictionary-depth " <<
|
| def_depth << ", --n-gram-max-size " << n_gram_size << ", --response-max-length " << response_maxlen <<
|
| ", and --repeat-penalty " << repeat_penalty << "\n";
|
| cerr << "To change the value(s), use " << argv[0] << " command-line interface option(s).\n";
|
| load_kb_binary(kb, load_kb, def_depth); cerr << "Loaded knowledge base: " << load_kb << "\n"; }
|
| catch (const exception &e){ cerr << "Error: " << e.what() << "\n"; }
|
| }
|
|
|
| if (!learn_files.empty()){
|
| cerr << "Learning from file/s (" << learn_files.size() << ") using threads=" << omp_get_max_threads() << "\n";
|
| learn_files_parallel(kb, learn_files, n_gram_size);
|
| }
|
|
|
| string line;
|
| cout << "Ready. Enter prompts.\n";
|
| while (cout << "> " , getline(cin, line)){
|
| if (line.empty()){ cout << "\n"; continue; }
|
| auto prompt_toks = tokenize_whitespace(line);
|
| if (learn_chat) {learn_tokens_ngram(kb, prompt_toks, n_gram_size);}
|
| auto resp = construct_response(kb, prompt_toks, response_maxlen, repeat_penalty, n_gram_size, allow_path_loops);
|
| cout << "\n";
|
| if (!resp.empty() && learn_chat){learn_tokens_ngram(kb, resp, n_gram_size);}
|
| if (!savefile.empty()){
|
| try { cerr << "Saving knowledge base: " << savefile << "\n";
|
| save_kb_binary(kb, savefile); cerr << "Saved knowledge base: " << savefile << "\n"; }
|
| catch (const exception &e){ cerr << "Error: " << e.what() << "\n"; }
|
| }
|
| }
|
|
|
| return 0;
|
| }
|
|
|
