1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "actions/ngram-model.h"
18
19 #include <algorithm>
20
21 #include "actions/feature-processor.h"
22 #include "utils/hash/farmhash.h"
23 #include "utils/strings/stringpiece.h"
24
25 namespace libtextclassifier3 {
26 namespace {
27
28 // An iterator to iterate over the initial tokens of the n-grams of a model.
29 class FirstTokenIterator
30 : public std::iterator<std::random_access_iterator_tag,
31 /*value_type=*/uint32, /*difference_type=*/ptrdiff_t,
32 /*pointer=*/const uint32*,
33 /*reference=*/uint32&> {
34 public:
FirstTokenIterator(const NGramLinearRegressionModel * model,int index)35 explicit FirstTokenIterator(const NGramLinearRegressionModel* model,
36 int index)
37 : model_(model), index_(index) {}
38
operator ++()39 FirstTokenIterator& operator++() {
40 index_++;
41 return *this;
42 }
operator +=(ptrdiff_t dist)43 FirstTokenIterator& operator+=(ptrdiff_t dist) {
44 index_ += dist;
45 return *this;
46 }
operator -(const FirstTokenIterator & other_it) const47 ptrdiff_t operator-(const FirstTokenIterator& other_it) const {
48 return index_ - other_it.index_;
49 }
operator *() const50 uint32 operator*() const {
51 const uint32 token_offset = (*model_->ngram_start_offsets())[index_];
52 return (*model_->hashed_ngram_tokens())[token_offset];
53 }
index() const54 int index() const { return index_; }
55
56 private:
57 const NGramLinearRegressionModel* model_;
58 int index_;
59 };
60
61 } // anonymous namespace
62
Create(const NGramLinearRegressionModel * model,const Tokenizer * tokenizer,const UniLib * unilib)63 std::unique_ptr<NGramModel> NGramModel::Create(
64 const NGramLinearRegressionModel* model, const Tokenizer* tokenizer,
65 const UniLib* unilib) {
66 if (model == nullptr) {
67 return nullptr;
68 }
69 if (tokenizer == nullptr && model->tokenizer_options() == nullptr) {
70 TC3_LOG(ERROR) << "No tokenizer options specified.";
71 return nullptr;
72 }
73 return std::unique_ptr<NGramModel>(new NGramModel(model, tokenizer, unilib));
74 }
75
NGramModel(const NGramLinearRegressionModel * model,const Tokenizer * tokenizer,const UniLib * unilib)76 NGramModel::NGramModel(const NGramLinearRegressionModel* model,
77 const Tokenizer* tokenizer, const UniLib* unilib)
78 : model_(model) {
79 // Create new tokenizer if options are specified, reuse feature processor
80 // tokenizer otherwise.
81 if (model->tokenizer_options() != nullptr) {
82 owned_tokenizer_ = CreateTokenizer(model->tokenizer_options(), unilib);
83 tokenizer_ = owned_tokenizer_.get();
84 } else {
85 tokenizer_ = tokenizer;
86 }
87 }
88
89 // Returns whether a given n-gram matches the token stream.
IsNGramMatch(const uint32 * tokens,size_t num_tokens,const uint32 * ngram_tokens,size_t num_ngram_tokens,int max_skips) const90 bool NGramModel::IsNGramMatch(const uint32* tokens, size_t num_tokens,
91 const uint32* ngram_tokens,
92 size_t num_ngram_tokens, int max_skips) const {
93 int token_idx = 0, ngram_token_idx = 0, skip_remain = 0;
94 for (; token_idx < num_tokens && ngram_token_idx < num_ngram_tokens;) {
95 if (tokens[token_idx] == ngram_tokens[ngram_token_idx]) {
96 // Token matches. Advance both and reset the skip budget.
97 ++token_idx;
98 ++ngram_token_idx;
99 skip_remain = max_skips;
100 } else if (skip_remain > 0) {
101 // No match, but we have skips left, so just advance over the token.
102 ++token_idx;
103 skip_remain--;
104 } else {
105 // No match and we're out of skips. Reject.
106 return false;
107 }
108 }
109 return ngram_token_idx == num_ngram_tokens;
110 }
111
112 // Calculates the total number of skip-grams that can be created for a stream
113 // with the given number of tokens.
GetNumSkipGrams(int num_tokens,int max_ngram_length,int max_skips)114 uint64 NGramModel::GetNumSkipGrams(int num_tokens, int max_ngram_length,
115 int max_skips) {
116 // Start with unigrams.
117 uint64 total = num_tokens;
118 for (int ngram_len = 2;
119 ngram_len <= max_ngram_length && ngram_len <= num_tokens; ++ngram_len) {
120 // We can easily compute the expected length of the n-gram (with skips),
121 // but it doesn't account for the fact that they may be longer than the
122 // input and should be pruned.
123 // Instead, we iterate over the distribution of effective n-gram lengths
124 // and add each length individually.
125 const int num_gaps = ngram_len - 1;
126 const int len_min = ngram_len;
127 const int len_max = ngram_len + num_gaps * max_skips;
128 const int len_mid = (len_max + len_min) / 2;
129 for (int len_i = len_min; len_i <= len_max; ++len_i) {
130 if (len_i > num_tokens) continue;
131 const int num_configs_of_len_i =
132 len_i <= len_mid ? len_i - len_min + 1 : len_max - len_i + 1;
133 const int num_start_offsets = num_tokens - len_i + 1;
134 total += num_configs_of_len_i * num_start_offsets;
135 }
136 }
137 return total;
138 }
139
GetFirstTokenMatches(uint32 token_hash) const140 std::pair<int, int> NGramModel::GetFirstTokenMatches(uint32 token_hash) const {
141 const int num_ngrams = model_->ngram_weights()->size();
142 const auto start_it = FirstTokenIterator(model_, 0);
143 const auto end_it = FirstTokenIterator(model_, num_ngrams);
144 const int start = std::lower_bound(start_it, end_it, token_hash).index();
145 const int end = std::upper_bound(start_it, end_it, token_hash).index();
146 return std::make_pair(start, end);
147 }
148
Eval(const UnicodeText & text,float * score) const149 bool NGramModel::Eval(const UnicodeText& text, float* score) const {
150 const std::vector<Token> raw_tokens = tokenizer_->Tokenize(text);
151
152 // If we have no tokens, then just bail early.
153 if (raw_tokens.empty()) {
154 if (score != nullptr) {
155 *score = model_->default_token_weight();
156 }
157 return false;
158 }
159
160 // Hash the tokens.
161 std::vector<uint32> tokens;
162 tokens.reserve(raw_tokens.size());
163 for (const Token& raw_token : raw_tokens) {
164 tokens.push_back(tc3farmhash::Fingerprint32(raw_token.value.data(),
165 raw_token.value.length()));
166 }
167
168 // Calculate the total number of skip-grams that can be generated for the
169 // input text.
170 const uint64 num_candidates = GetNumSkipGrams(
171 tokens.size(), model_->max_denom_ngram_length(), model_->max_skips());
172
173 // For each token, see whether it denotes the start of an n-gram in the model.
174 int num_matches = 0;
175 float weight_matches = 0.f;
176 for (size_t start_i = 0; start_i < tokens.size(); ++start_i) {
177 const std::pair<int, int> ngram_range =
178 GetFirstTokenMatches(tokens[start_i]);
179 for (int ngram_idx = ngram_range.first; ngram_idx < ngram_range.second;
180 ++ngram_idx) {
181 const uint16 ngram_tokens_begin =
182 (*model_->ngram_start_offsets())[ngram_idx];
183 const uint16 ngram_tokens_end =
184 (*model_->ngram_start_offsets())[ngram_idx + 1];
185 if (IsNGramMatch(
186 /*tokens=*/tokens.data() + start_i,
187 /*num_tokens=*/tokens.size() - start_i,
188 /*ngram_tokens=*/model_->hashed_ngram_tokens()->data() +
189 ngram_tokens_begin,
190 /*num_ngram_tokens=*/ngram_tokens_end - ngram_tokens_begin,
191 /*max_skips=*/model_->max_skips())) {
192 ++num_matches;
193 weight_matches += (*model_->ngram_weights())[ngram_idx];
194 }
195 }
196 }
197
198 // Calculate the score.
199 const int num_misses = num_candidates - num_matches;
200 const float internal_score =
201 (weight_matches + (model_->default_token_weight() * num_misses)) /
202 num_candidates;
203 if (score != nullptr) {
204 *score = internal_score;
205 }
206 return internal_score > model_->threshold();
207 }
208
209 } // namespace libtextclassifier3
210