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 "utils/sentencepiece/double_array_trie.h"
18 #include "utils/base/logging.h"
19
20 namespace libtextclassifier3 {
21
GatherPrefixMatches(StringPiece input,const std::function<void (TrieMatch)> & update_fn) const22 bool DoubleArrayTrie::GatherPrefixMatches(
23 StringPiece input, const std::function<void(TrieMatch)>& update_fn) const {
24 uint32 pos = 0;
25 if (nodes_length_ == 0) {
26 TC3_LOG(WARNING) << "Trie is empty. Skipping.";
27 return true;
28 }
29 pos = offset(0);
30 for (int i = 0; i < input.size(); i++) {
31 if (input[i] == 0) {
32 break;
33 }
34 pos ^= static_cast<unsigned char>(input[i]);
35 // We exhausted the trie, no more matches possible.
36 if (pos < 0 || pos >= nodes_length_) {
37 break;
38 }
39 if (label(pos) != input[i]) {
40 break;
41 }
42 const bool node_has_leaf = has_leaf(pos);
43 pos ^= offset(pos);
44 if (pos < 0 || pos > nodes_length_) {
45 TC3_LOG(ERROR) << "Out-of-bounds trie search position.";
46 return false;
47 }
48 if (node_has_leaf) {
49 update_fn(TrieMatch(/*id=*/value(pos), /*match_length=*/i + 1));
50 }
51 }
52 return true;
53 }
54
FindAllPrefixMatches(StringPiece input,std::vector<TrieMatch> * matches) const55 bool DoubleArrayTrie::FindAllPrefixMatches(
56 StringPiece input, std::vector<TrieMatch>* matches) const {
57 return GatherPrefixMatches(
58 input, [matches](const TrieMatch match) { matches->push_back(match); });
59 }
60
LongestPrefixMatch(StringPiece input,TrieMatch * longest_match) const61 bool DoubleArrayTrie::LongestPrefixMatch(StringPiece input,
62 TrieMatch* longest_match) const {
63 *longest_match = TrieMatch();
64 return GatherPrefixMatches(input, [longest_match](const TrieMatch match) {
65 *longest_match = match;
66 });
67 }
68
69 } // namespace libtextclassifier3
70