char-fork/llama.cpp

git clone https://git.t4t.associates/char-fork/llama.cpp

Aldehir Rojascommon : add support for multiple end sequences in the reasoning budget sampler (#25544)910196f6b

char/aliceai-t5-moe
brancheschar/aliceai-t5-moeall refs →
3.7 KiB123 linesraw
1#include "trie.h"
2
3#include "unicode.h"
4
5#include <deque>
6
7common_trie::match_result common_trie::check_at(std::string_view sv, size_t start_pos) const {
8    size_t current = 0; // Start at root
9    size_t pos = start_pos;
10
11    // LOG_DBG("%s: checking at pos %zu, sv='%s'\n", __func__, start_pos, std::string(sv).c_str());
12
13    while (pos < sv.size()) {
14        auto result = common_parse_utf8_codepoint(sv, pos);
15        if (result.status != utf8_parse_result::SUCCESS) {
16            break;
17        }
18
19        auto it = nodes[current].children.find(result.codepoint);
20        if (it == nodes[current].children.end()) {
21            // Can't continue matching
22            return match_result{match_result::NO_MATCH};
23        }
24
25        current = it->second;
26        pos += result.bytes_consumed;
27
28        // Check if we've matched a complete word
29        if (nodes[current].pattern >= 0) {
30            return match_result{match_result::COMPLETE_MATCH};
31        }
32    }
33
34    // Reached end of input while still in the trie (not at root)
35    if (current != 0) {
36        // We're in the middle of a potential match
37        return match_result{match_result::PARTIAL_MATCH};
38    }
39
40    // Reached end at root (no match)
41    return match_result{match_result::NO_MATCH};
42}
43
44int32_t common_trie::insert(const std::string & word) {
45    std::vector<uint32_t> symbols;
46    size_t pos = 0;
47    while (pos < word.length()) {
48        auto result = common_parse_utf8_codepoint(word, pos);
49        if (result.status != utf8_parse_result::SUCCESS) {
50            break;
51        }
52
53        symbols.push_back(result.codepoint);
54        pos += result.bytes_consumed;
55    }
56    return insert(symbols);
57}
58
59int32_t common_trie::insert(const std::vector<uint32_t> & symbols) {
60    size_t current = 0;
61    for (uint32_t ch : symbols) {
62        auto it = nodes[current].children.find(ch);
63        if (it == nodes[current].children.end()) {
64            size_t child = create_node();
65            nodes[current].children[ch] = child;
66            current = child;
67        } else {
68            current = it->second;
69        }
70    }
71    if (nodes[current].pattern < 0) {
72        nodes[current].pattern = n_patterns++;
73    }
74    return nodes[current].pattern;
75}
76
77common_aho_corasick::common_aho_corasick(common_trie trie) : t(std::move(trie)) {
78    const auto & nodes = t.nodes;
79    const size_t n = nodes.size();
80
81    fail.assign(n, 0);
82    order.reserve(n);
83
84    std::deque<size_t> queue{ 0 };
85    while (!queue.empty()) {
86        size_t u = queue.front();
87        queue.pop_front();
88        order.push_back(u);
89        for (const auto & [ch, v] : nodes[u].children) {
90            if (u != 0) {
91                size_t f = fail[u];
92                while (f && nodes[f].children.find(ch) == nodes[f].children.end()) {
93                    f = fail[f];
94                }
95                auto it = nodes[f].children.find(ch);
96                fail[v] = (it != nodes[f].children.end() && it->second != v) ? it->second : 0;
97            }
98            queue.push_back(v);
99        }
100    }
101
102    // fail[u] points to a strictly shorter suffix, so the first pattern found on
103    // the fail chain (including u itself) is the longest pattern ending at u
104    match.assign(n, -1);
105    for (size_t u : order) {
106        match[u] = nodes[u].pattern >= 0 ? nodes[u].pattern : (u != 0 ? match[fail[u]] : -1);
107    }
108
109    for (const auto & node : nodes) {
110        for (const auto & [ch, v] : node.children) {
111            alphabet.insert(ch);
112        }
113    }
114}
115
116size_t common_aho_corasick::next(size_t state, uint32_t ch) const {
117    const auto & nodes = t.nodes;
118    while (state && nodes[state].children.find(ch) == nodes[state].children.end()) {
119        state = fail[state];
120    }
121    auto it = nodes[state].children.find(ch);
122    return it != nodes[state].children.end() ? it->second : 0;
123}