Refactor SystemDictionary::PrefixSearch using LoudsTrie::Node APIs
This CL re-implements prefix search without LoudsTrie::Callback, which simplifies code because the nested callback of DictionaryInterface::Callback and LoudsTrie::Callback was removed.
Also, some performance improvements are implemented.
- Instead of decoding the prefix using Codec::DecodeKey, only its length is decoded by Codec::GetDecodeKeyLength and the decoded prefix is obtained from the original user input. This is faster because we can avoid UCS4 to UTF8 conversion and string construction.
- Lazy decoding of LoudsTrie's key ID. In the previous implementation, key IDs were always decoded due to the restriction of LoudsTrie::Callback. However, key ID is first used when starting decoding token array elements. Thus, when performing culling based on key strings, we can skip decoding of key ID.
- Optimization for the case where key expansion is not performed (e.g., predictor calls LookupPrefix without expansion). In the previous implementation, this case was implemented by passing the default KeyExpansionTable. However, since recursive traversal over LoudsTrie is far complicated than the normal traversal, it's worth optimizing the code for non-expanding cases.
Roughly 10% time reduction is observed in converter_benchmark with several corpora. Note that this is just a code refactoring, no user-visible behavior change is intended.
BUG=none
TEST=unittest,benchmark
git-svn-id: https://mozc.googlecode.com/svn/trunk@525 a6090854-d499-a067-5803-1114d4e51264
diff --git a/src/dictionary/system/system_dictionary.cc b/src/dictionary/system/system_dictionary.cc
index 9f1c415..311bfd1 100644
--- a/src/dictionary/system/system_dictionary.cc
+++ b/src/dictionary/system/system_dictionary.cc
@@ -71,6 +71,7 @@
namespace dictionary {
using mozc::storage::louds::BitVectorBasedArray;
+using mozc::storage::louds::ExpandedKey;
using mozc::storage::louds::KeyExpansionTable;
using mozc::storage::louds::LoudsTrie;
@@ -317,6 +318,12 @@
DISALLOW_COPY_AND_ASSIGN(TokenDecodeIterator);
};
+inline const uint8 *GetTokenArrayPtr(const BitVectorBasedArray &token_array,
+ int key_id) {
+ size_t length = 0;
+ return reinterpret_cast<const uint8*>(token_array.Get(key_id, &length));
+}
+
// Iterator for scanning token array.
// This iterator does not return actual token info but returns
// id data and the position only.
@@ -352,9 +359,7 @@
offset_(0),
tokens_offset_(0),
index_(0) {
- size_t dummy_length = 0;
- encoded_tokens_ptr_ =
- reinterpret_cast<const uint8*>(token_array->Get(0, &dummy_length));
+ encoded_tokens_ptr_ = GetTokenArrayPtr(*token_array, 0);
NextInternal();
}
@@ -697,9 +702,7 @@
// true.
// Get the block of tokens for this key.
- size_t length = 0; // unused
- const uint8 *encoded_tokens_ptr = reinterpret_cast<const uint8*>(
- token_array_->Get(key_id, &length));
+ const uint8 *encoded_tokens_ptr = GetTokenArrayPtr(*token_array_, key_id);
// Check tokens.
for (TokenDecodeIterator iter(
@@ -715,27 +718,6 @@
namespace {
-// Converts a value of SystemDictionary::Callback::ResultType to the
-// corresponding value of LoudsTrie::Callback::ResultType.
-inline LoudsTrie::Callback::ResultType ConvertResultType(
- const SystemDictionary::Callback::ResultType result) {
- switch (result) {
- case SystemDictionary::Callback::TRAVERSE_DONE: {
- return LoudsTrie::Callback::SEARCH_DONE;
- }
- case SystemDictionary::Callback::TRAVERSE_NEXT_KEY: {
- return LoudsTrie::Callback::SEARCH_CONTINUE;
- }
- case SystemDictionary::Callback::TRAVERSE_CULL: {
- return LoudsTrie::Callback::SEARCH_CULL;
- }
- default: {
- DLOG(FATAL) << "Enum value " << result << " cannot be converted";
- return LoudsTrie::Callback::SEARCH_DONE; // dummy
- }
- }
-}
-
// Collects short keys preferentially.
class ShortKeyCollector : public LoudsTrie::Callback {
public:
@@ -927,9 +909,8 @@
break;
}
- size_t dummy_length = 0;
- const uint8 *encoded_tokens_ptr = reinterpret_cast<const uint8*>(
- token_array_->Get(entry.key_id, &dummy_length));
+ const uint8 *encoded_tokens_ptr =
+ GetTokenArrayPtr(*token_array_, entry.key_id);
for (TokenDecodeIterator iter(codec_, value_trie_.get(),
frequent_pos_, actual_key,
encoded_tokens_ptr);
@@ -951,82 +932,85 @@
namespace {
-// A general purpose traverser for prefix search over the system dictionary.
-class PrefixTraverser : public LoudsTrie::Callback {
- public:
- PrefixTraverser(const BitVectorBasedArray *token_array,
- const LoudsTrie *value_trie,
- const SystemDictionaryCodecInterface *codec,
- const uint32 *frequent_pos,
- StringPiece original_encoded_key,
- SystemDictionary::Callback *callback)
- : token_array_(token_array),
- value_trie_(value_trie),
- codec_(codec),
- frequent_pos_(frequent_pos),
- original_encoded_key_(original_encoded_key),
- callback_(callback) {
- }
+// An implementation of prefix search without key expansion. Runs |callback|
+// for prefixes of |encoded_key| in |key_trie|.
+// Args:
+// key_trie, value_trie, token_array, codec, frequent_pos:
+// Members in SystemDictionary.
+// key:
+// The head address of the original key before applying codec.
+// encoded_key:
+// The encoded |key|.
+// callback:
+// A callback function to be called.
+// token_filter:
+// A functor of signature bool(const TokenInfo &). Only tokens for which
+// this functor returns true are passed to callback function.
+template <typename Func>
+void RunCallbackOnEachPrefix(const LoudsTrie *key_trie,
+ const LoudsTrie *value_trie,
+ const BitVectorBasedArray *token_array,
+ const SystemDictionaryCodecInterface *codec,
+ const uint32 *frequent_pos,
+ const char *key,
+ StringPiece encoded_key,
+ DictionaryInterface::Callback *callback,
+ Func token_filter) {
+ typedef DictionaryInterface::Callback Callback;
+ LoudsTrie::Node node;
+ for (StringPiece::size_type i = 0; i < encoded_key.size(); ) {
+ if (!key_trie->MoveToChildByLabel(encoded_key[i], &node)) {
+ return;
+ }
+ ++i; // Increment here for next loop and |encoded_prefix| defined below.
+ if (!key_trie->IsTerminalNode(node)) {
+ continue;
+ }
+ const StringPiece encoded_prefix(encoded_key, 0, i);
+ const StringPiece prefix(key, codec->GetDecodedKeyLength(encoded_prefix));
- virtual ResultType Run(const char *trie_key,
- size_t trie_key_len, int key_id) {
- string key, actual_key;
- SystemDictionary::Callback::ResultType result = RunOnKeyAndOnActualKey(
- trie_key, trie_key_len, key_id, &key, &actual_key);
- if (result != SystemDictionary::Callback::TRAVERSE_CONTINUE) {
- return ConvertResultType(result);
+ switch (callback->OnKey(prefix)) {
+ case Callback::TRAVERSE_DONE:
+ case Callback::TRAVERSE_CULL:
+ return;
+ case Callback::TRAVERSE_NEXT_KEY:
+ continue;
+ default:
+ break;
}
- // Decode tokens and call back OnToken() for each token.
- size_t dummy_length = 0;
- const uint8 *encoded_tokens_ptr = reinterpret_cast<const uint8*>(
- token_array_->Get(key_id, &dummy_length));
- for (TokenDecodeIterator iter(
- codec_, value_trie_, frequent_pos_,
- actual_key, encoded_tokens_ptr);
+ switch (callback->OnActualKey(prefix, prefix, false)) {
+ case Callback::TRAVERSE_DONE:
+ case Callback::TRAVERSE_CULL:
+ return;
+ case Callback::TRAVERSE_NEXT_KEY:
+ continue;
+ default:
+ break;
+ }
+
+ const int key_id = key_trie->GetKeyIdOfTerminalNode(node);
+ for (TokenDecodeIterator iter(codec, value_trie, frequent_pos, prefix,
+ GetTokenArrayPtr(*token_array, key_id));
!iter.Done(); iter.Next()) {
const TokenInfo &token_info = iter.Get();
- result = callback_->OnToken(key, actual_key, *token_info.token);
- if (result != SystemDictionary::Callback::TRAVERSE_CONTINUE) {
- return ConvertResultType(result);
+ if (!token_filter(token_info)) {
+ continue;
+ }
+ const Callback::ResultType res =
+ callback->OnToken(prefix, prefix, *token_info.token);
+ if (res == Callback::TRAVERSE_DONE || res == Callback::TRAVERSE_CULL) {
+ return;
+ }
+ if (res == Callback::TRAVERSE_NEXT_KEY) {
+ break;
}
}
- return SEARCH_CONTINUE;
}
+}
- protected:
- SystemDictionary::Callback::ResultType RunOnKeyAndOnActualKey(
- const char *trie_key, size_t trie_key_len, int key_id,
- string *key, string *actual_key) {
- // Decode key and call back OnKey().
- const StringPiece encoded_key =
- original_encoded_key_.substr(0, trie_key_len);
- codec_->DecodeKey(encoded_key, key);
- SystemDictionary::Callback::ResultType result = callback_->OnKey(*key);
- if (result != SystemDictionary::Callback::TRAVERSE_CONTINUE) {
- return result;
- }
-
- // Decode actual key (expanded key) and call back OnActualKey(). To check
- // if the actual key is expanded, compare the keys in encoded domain for
- // performance (this is guaranteed as codec is a bijection).
- const StringPiece encoded_actual_key(trie_key, trie_key_len);
- actual_key->reserve(key->size());
- codec_->DecodeKey(encoded_actual_key, actual_key);
- const bool is_expanded = encoded_actual_key != encoded_key;
- DCHECK_EQ(is_expanded, *key != *actual_key);
- return callback_->OnActualKey(*key, *actual_key, is_expanded);
- }
-
- const BitVectorBasedArray *token_array_;
- const LoudsTrie *value_trie_;
- const SystemDictionaryCodecInterface *codec_;
- const uint32 *frequent_pos_;
- const StringPiece original_encoded_key_;
- SystemDictionary::Callback *callback_;
-
- private:
- DISALLOW_COPY_AND_ASSIGN(PrefixTraverser);
+struct SelectAllTokens {
+ bool operator()(const TokenInfo &token_info) const { return true; }
};
class ReverseLookupCallbackWrapper : public DictionaryInterface::Callback {
@@ -1046,18 +1030,136 @@
} // namespace
+// Recursive implemention of depth-first prefix search with key expansion.
+// Input parameters:
+// key:
+// The head address of the original key before applying codec.
+// encoded_key:
+// The encoded |key|.
+// table:
+// Key expansion table.
+// callback:
+// A callback function to be called.
+// Parameters for recursion:
+// node:
+// Stores the current location in |key_trie_|.
+// key_pos:
+// Depth of node, i.e., encoded_key.substr(0, key_pos) is the current prefix
+// for search.
+// is_expanded:
+// true is stored if the current node is reached by key expansion.
+// actual_key_buffer:
+// Buffer for storing actually used characters to reach this node, i.e.,
+// StringPiece(actual_key_buffer, key_pos) is the matched prefix using key
+// expansion.
+// actual_prefix:
+// A reused string for decoded actual key. This is just for performance
+// purpose.
+DictionaryInterface::Callback::ResultType
+SystemDictionary::LookupPrefixWithKeyExpansionImpl(
+ const char *key,
+ StringPiece encoded_key,
+ const KeyExpansionTable &table,
+ Callback *callback,
+ LoudsTrie::Node node,
+ StringPiece::size_type key_pos,
+ bool is_expanded,
+ char *actual_key_buffer,
+ string *actual_prefix) const {
+ // This do-block handles a terminal node and callback. do-block is used to
+ // break the block and continue to the subsequent traversal phase.
+ do {
+ if (!key_trie_->IsTerminalNode(node)) {
+ break;
+ }
+
+ const StringPiece encoded_prefix(encoded_key, 0, key_pos);
+ const StringPiece prefix(key, codec_->GetDecodedKeyLength(encoded_prefix));
+ Callback::ResultType result = callback->OnKey(prefix);
+ if (result == Callback::TRAVERSE_DONE ||
+ result == Callback::TRAVERSE_CULL) {
+ return result;
+ }
+ if (result == Callback::TRAVERSE_NEXT_KEY) {
+ break; // Go to the traversal phase.
+ }
+
+ const StringPiece encoded_actual_prefix(actual_key_buffer, key_pos);
+ actual_prefix->clear();
+ codec_->DecodeKey(encoded_actual_prefix, actual_prefix);
+ result = callback->OnActualKey(prefix, *actual_prefix, is_expanded);
+ if (result == Callback::TRAVERSE_DONE ||
+ result == Callback::TRAVERSE_CULL) {
+ return result;
+ }
+ if (result == Callback::TRAVERSE_NEXT_KEY) {
+ break; // Go to the traversal phase.
+ }
+
+ const int key_id = key_trie_->GetKeyIdOfTerminalNode(node);
+ for (TokenDecodeIterator iter(codec_, value_trie_.get(), frequent_pos_,
+ *actual_prefix,
+ GetTokenArrayPtr(*token_array_, key_id));
+ !iter.Done(); iter.Next()) {
+ const TokenInfo &token_info = iter.Get();
+ result = callback->OnToken(prefix, *actual_prefix, *token_info.token);
+ if (result == Callback::TRAVERSE_DONE ||
+ result == Callback::TRAVERSE_CULL) {
+ return result;
+ }
+ if (result == Callback::TRAVERSE_NEXT_KEY) {
+ break; // Go to the traversal phase.
+ }
+ }
+ } while (false);
+
+ // Traversal phase.
+ if (key_pos == encoded_key.size()) {
+ return Callback::TRAVERSE_CONTINUE;
+ }
+ const char current_char = encoded_key[key_pos];
+ const ExpandedKey &chars = table.ExpandKey(current_char);
+ for (key_trie_->MoveToFirstChild(&node); key_trie_->IsValidNode(node);
+ key_trie_->MoveToNextSibling(&node)) {
+ const char c = key_trie_->GetEdgeLabelToParentNode(node);
+ if (!chars.IsHit(c)) {
+ continue;
+ }
+ actual_key_buffer[key_pos] = c;
+ const Callback::ResultType result = LookupPrefixWithKeyExpansionImpl(
+ key, encoded_key, table, callback, node, key_pos + 1,
+ is_expanded || c != current_char,
+ actual_key_buffer, actual_prefix);
+ if (result == Callback::TRAVERSE_DONE) {
+ return Callback::TRAVERSE_DONE;
+ }
+ }
+
+ return Callback::TRAVERSE_CONTINUE;
+}
+
void SystemDictionary::LookupPrefix(
StringPiece key,
bool use_kana_modifier_insensitive_lookup,
Callback *callback) const {
- string original_encoded_key;
- codec_->EncodeKey(key, &original_encoded_key);
- PrefixTraverser traverser(token_array_.get(), value_trie_.get(), codec_,
- frequent_pos_, original_encoded_key, callback);
- const KeyExpansionTable &table = use_kana_modifier_insensitive_lookup ?
- hiragana_expansion_table_ : KeyExpansionTable::GetDefaultInstance();
- key_trie_->PrefixSearchWithKeyExpansion(
- original_encoded_key, table, &traverser);
+ string encoded_key;
+ codec_->EncodeKey(key, &encoded_key);
+
+ if (!use_kana_modifier_insensitive_lookup) {
+ RunCallbackOnEachPrefix(key_trie_.get(), value_trie_.get(),
+ token_array_.get(), codec_, frequent_pos_,
+ key.data(), encoded_key, callback,
+ SelectAllTokens());
+ return;
+ }
+
+ char actual_key_buffer[LoudsTrie::kMaxDepth + 1];
+ string actual_prefix;
+ actual_prefix.reserve(key.size() * 3);
+ LookupPrefixWithKeyExpansionImpl(key.data(), encoded_key,
+ hiragana_expansion_table_, callback,
+ LoudsTrie::Node(), 0, false,
+ actual_key_buffer, &actual_prefix);
}
void SystemDictionary::LookupExact(StringPiece key, Callback *callback) const {
@@ -1072,14 +1174,9 @@
return;
}
- // Get the block of tokens for this key.
- size_t dummy_length = 0;
- const uint8 *encoded_tokens_ptr = reinterpret_cast<const uint8*>(
- token_array_->Get(key_id, &dummy_length));
-
// Callback on each token.
- for (TokenDecodeIterator iter(
- codec_, value_trie_.get(), frequent_pos_, key, encoded_tokens_ptr);
+ for (TokenDecodeIterator iter(codec_, value_trie_.get(), frequent_pos_, key,
+ GetTokenArrayPtr(*token_array_, key_id));
!iter.Done(); iter.Next()) {
if (callback->OnToken(key, key, *iter.Get().token) !=
Callback::TRAVERSE_CONTINUE) {
@@ -1100,38 +1197,24 @@
namespace {
-// Collects all the IDs of louds trie whose keys match lookup query. The limit
-// parameter can be used to restrict the maximum number of lookup.
-class IdCollector : public LoudsTrie::Callback {
+class AddKeyIdsToSet {
public:
- IdCollector() : limit_(numeric_limits<int>::max()) {
- }
+ explicit AddKeyIdsToSet(set<int> *output) : output_(output) {}
- explicit IdCollector(int limit) : limit_(limit) {
- }
-
- // Called back on each key found. Inserts the key id to |id_set_| up to
- // |limit_|.
- virtual ResultType Run(const char *key, size_t key_len, int key_id) {
- if (limit_ <= 0) {
- return SEARCH_DONE;
- }
- id_set_.insert(key_id);
- --limit_;
- return SEARCH_CONTINUE;
- }
-
- const set<int> &id_set() const {
- return id_set_;
+ void operator()(StringPiece key, size_t prefix_len,
+ const LoudsTrie &trie, LoudsTrie::Node node) {
+ output_->insert(trie.GetKeyIdOfTerminalNode(node));
}
private:
- int limit_;
- set<int> id_set_;
-
- DISALLOW_COPY_AND_ASSIGN(IdCollector);
+ set<int> *output_;
};
+inline void AddKeyIdsOfAllPrefixes(const LoudsTrie &trie, StringPiece key,
+ set<int> *key_ids) {
+ trie.PrefixSearch(key, AddKeyIdsToSet(key_ids));
+}
+
} // namespace
void SystemDictionary::PopulateReverseLookupCache(
@@ -1148,18 +1231,20 @@
allocator->mutable_data()->get<ReverseLookupCache>(kReverseLookupCache);
DCHECK(cache) << "can't get cache data.";
- IdCollector id_collector;
- int pos = 0;
// Iterate each suffix and collect IDs of all substrings.
+ set<int> id_set;
+ int pos = 0;
+ string lookup_key;
+ lookup_key.reserve(str.size());
while (pos < str.size()) {
const StringPiece suffix(str, pos);
- string lookup_key;
+ lookup_key.clear();
codec_->EncodeValue(suffix, &lookup_key);
- value_trie_->PrefixSearch(lookup_key, &id_collector);
+ AddKeyIdsOfAllPrefixes(*value_trie_, lookup_key, &id_set);
pos += Util::OneCharLen(suffix.data());
}
// Collect tokens for all IDs.
- ScanTokens(id_collector.id_set(), &cache->results);
+ ScanTokens(id_set, &cache->results);
}
void SystemDictionary::ClearReverseLookupCache(
@@ -1169,73 +1254,44 @@
namespace {
-// A traverser for prefix search over T13N entries.
-class T13nPrefixTraverser : public PrefixTraverser {
+class FilterTokenForRegisterReverseLookupTokensForT13N {
public:
- T13nPrefixTraverser(const BitVectorBasedArray *token_array,
- const LoudsTrie *value_trie,
- const SystemDictionaryCodecInterface *codec,
- const uint32 *frequent_pos,
- StringPiece original_encoded_key,
- SystemDictionary::Callback *callback)
- : PrefixTraverser(token_array, value_trie, codec, frequent_pos,
- original_encoded_key, callback) {}
+ FilterTokenForRegisterReverseLookupTokensForT13N() {
+ tmp_str_.reserve(LoudsTrie::kMaxDepth * 3);
+ }
- virtual ResultType Run(const char *trie_key,
- size_t trie_key_len, int key_id) {
- string key, actual_key;
- SystemDictionary::Callback::ResultType result = RunOnKeyAndOnActualKey(
- trie_key, trie_key_len, key_id, &key, &actual_key);
- if (result != SystemDictionary::Callback::TRAVERSE_CONTINUE) {
- return ConvertResultType(result);
+ bool operator()(const TokenInfo &token_info) {
+ // Skip spelling corrections.
+ if (token_info.token->attributes & Token::SPELLING_CORRECTION) {
+ return false;
}
-
- // Decode tokens and call back OnToken() for each T13N token.
- size_t dummy_length = 0;
- const uint8 *encoded_tokens_ptr = reinterpret_cast<const uint8*>(
- token_array_->Get(key_id, &dummy_length));
- for (TokenDecodeIterator iter(
- codec_, value_trie_, frequent_pos_,
- actual_key, encoded_tokens_ptr);
- !iter.Done(); iter.Next()) {
- const TokenInfo &token_info = iter.Get();
- // Skip spelling corrections.
- if (token_info.token->attributes & Token::SPELLING_CORRECTION) {
- continue;
- }
- if (token_info.value_type != TokenInfo::AS_IS_HIRAGANA &&
- token_info.value_type != TokenInfo::AS_IS_KATAKANA) {
- // SAME_AS_PREV_VALUE may be t13n token.
- string hiragana;
- Util::KatakanaToHiragana(token_info.token->value, &hiragana);
- if (token_info.token->key != hiragana) {
- continue;
- }
- }
- result = callback_->OnToken(key, actual_key, *token_info.token);
- if (result != SystemDictionary::Callback::TRAVERSE_CONTINUE) {
- return ConvertResultType(result);
+ if (token_info.value_type != TokenInfo::AS_IS_HIRAGANA &&
+ token_info.value_type != TokenInfo::AS_IS_KATAKANA) {
+ // SAME_AS_PREV_VALUE may be t13n token.
+ tmp_str_.clear();
+ Util::KatakanaToHiragana(token_info.token->value, &tmp_str_);
+ if (token_info.token->key != tmp_str_) {
+ return false;
}
}
- return SEARCH_CONTINUE;
+ return true;
}
private:
- DISALLOW_COPY_AND_ASSIGN(T13nPrefixTraverser);
+ string tmp_str_;
};
} // namespace
void SystemDictionary::RegisterReverseLookupTokensForT13N(
StringPiece value, Callback *callback) const {
- string hiragana, original_encoded_key;
- Util::KatakanaToHiragana(value, &hiragana);
- codec_->EncodeKey(hiragana, &original_encoded_key);
- T13nPrefixTraverser traverser(token_array_.get(), value_trie_.get(), codec_,
- frequent_pos_, original_encoded_key, callback);
- key_trie_->PrefixSearchWithKeyExpansion(
- original_encoded_key, KeyExpansionTable::GetDefaultInstance(),
- &traverser);
+ string hiragana_value, encoded_key;
+ Util::KatakanaToHiragana(value, &hiragana_value);
+ codec_->EncodeKey(hiragana_value, &encoded_key);
+ RunCallbackOnEachPrefix(key_trie_.get(), value_trie_.get(),
+ token_array_.get(), codec_, frequent_pos_,
+ hiragana_value.data(), encoded_key, callback,
+ FilterTokenForRegisterReverseLookupTokensForT13N());
}
void SystemDictionary::RegisterReverseLookupTokensForValue(
@@ -1244,9 +1300,8 @@
string lookup_key;
codec_->EncodeValue(value, &lookup_key);
- IdCollector id_collector;
- value_trie_->PrefixSearch(lookup_key, &id_collector);
- const set<int> &id_set = id_collector.id_set();
+ set<int> id_set;
+ AddKeyIdsOfAllPrefixes(*value_trie_, lookup_key, &id_set);
const bool has_cache = (allocator != NULL &&
allocator->data().has(kReverseLookupCache));
@@ -1291,9 +1346,7 @@
const set<int> &id_set,
const multimap<int, ReverseLookupResult> &reverse_results,
Callback *callback) const {
- size_t dummy_length = 0;
- const uint8 *encoded_tokens_ptr =
- reinterpret_cast<const uint8*>(token_array_->Get(0, &dummy_length));
+ const uint8 *encoded_tokens_ptr = GetTokenArrayPtr(*token_array_, 0);
char buffer[LoudsTrie::kMaxDepth + 1];
for (set<int>::const_iterator set_itr = id_set.begin();
set_itr != id_set.end();
diff --git a/src/dictionary/system/system_dictionary.h b/src/dictionary/system/system_dictionary.h
index dc12e05..98dea2c 100644
--- a/src/dictionary/system/system_dictionary.h
+++ b/src/dictionary/system/system_dictionary.h
@@ -216,6 +216,17 @@
void InitReverseLookupIndex();
+ Callback::ResultType LookupPrefixWithKeyExpansionImpl(
+ const char *key,
+ StringPiece encoded_key,
+ const storage::louds::KeyExpansionTable &table,
+ Callback *callback,
+ storage::louds::LoudsTrie::Node node,
+ StringPiece::size_type key_pos,
+ bool is_expanded,
+ char *actual_key_buffer,
+ string *actual_prefix) const;
+
scoped_ptr<storage::louds::LoudsTrie> key_trie_;
scoped_ptr<storage::louds::LoudsTrie> value_trie_;
scoped_ptr<storage::louds::BitVectorBasedArray> token_array_;
diff --git a/src/mozc_version_template.txt b/src/mozc_version_template.txt
index 447058a..2d27f45 100644
--- a/src/mozc_version_template.txt
+++ b/src/mozc_version_template.txt
@@ -1,6 +1,6 @@
MAJOR=2
MINOR=16
-BUILD=2041
+BUILD=2042
REVISION=102
# NACL_DICTIONARY_VERSION is the target version of the system dictionary to be
# downloaded by NaCl Mozc.
diff --git a/src/storage/louds/louds.h b/src/storage/louds/louds.h
index 74c8d9e..57eb3e7 100644
--- a/src/storage/louds/louds.h
+++ b/src/storage/louds/louds.h
@@ -68,6 +68,11 @@
// Default instance represents the root node (not the super-root).
Node() : edge_index_(0), node_id_(1) {}
Node(const Node &n) : edge_index_(n.edge_index_), node_id_(n.node_id_) {}
+ Node& operator=(const Node &n) {
+ edge_index_ = n.edge_index_;
+ node_id_ = n.node_id_;
+ return *this;
+ }
int node_id() const { return node_id_; }
diff --git a/src/storage/louds/louds_trie.cc b/src/storage/louds/louds_trie.cc
index 2417157..ea9c939 100644
--- a/src/storage/louds/louds_trie.cc
+++ b/src/storage/louds/louds_trie.cc
@@ -92,16 +92,21 @@
edge_character_ = nullptr;
}
+bool LoudsTrie::MoveToChildByLabel(char label, Node *node) const {
+ MoveToFirstChild(node);
+ while (IsValidNode(*node)) {
+ if (GetEdgeLabelToParentNode(*node) == label) {
+ return true;
+ }
+ MoveToNextSibling(node);
+ }
+ return false;
+}
+
bool LoudsTrie::Traverse(StringPiece key, Node *node) const {
for (auto iter = key.begin(); iter != key.end(); ++iter) {
- // Check all the children to find an edge with label |*iter|.
- for (louds_.MoveToFirstChild(node); ; louds_.MoveToNextSibling(node)) {
- if (!louds_.IsValidNode(*node)) {
- return false;
- }
- if (GetEdgeLabelToParentNode(*node) == *iter) {
- break;
- }
+ if (!MoveToChildByLabel(*iter, node)) {
+ return false;
}
}
return true;
@@ -117,64 +122,6 @@
namespace {
-// Recursively traverses the trie in DFS order and runs |callback| at terminal
-// nodes. Returns true if traversal is done to exit recursion.
-bool PrefixSearchWithKeyExpansionImpl(
- const LoudsTrie &trie,
- StringPiece key,
- const KeyExpansionTable &key_expansion_table,
- LoudsTrie::Callback *callback,
- LoudsTrie::Node node,
- char *key_buffer,
- StringPiece::size_type key_len) {
- if (trie.IsTerminalNode(node)) {
- const LoudsTrie::Callback::ResultType result =
- callback->Run(key_buffer, key_len, trie.GetKeyIdOfTerminalNode(node));
- switch (result) {
- case LoudsTrie::Callback::SEARCH_DONE:
- return true;
- case LoudsTrie::Callback::SEARCH_CULL:
- return false;
- default:
- break;
- }
- }
-
- if (key_len == key.size()) {
- return false;
- }
-
- const char target_char = key[key_len];
- const ExpandedKey &chars = key_expansion_table.ExpandKey(target_char);
- for (trie.MoveToFirstChild(&node); trie.IsValidNode(node);
- trie.MoveToNextSibling(&node)) {
- const char c = trie.GetEdgeLabelToParentNode(node);
- if (chars.IsHit(c)) {
- key_buffer[key_len] = c;
- if (PrefixSearchWithKeyExpansionImpl(trie, key, key_expansion_table,
- callback, node,
- key_buffer, key_len + 1)) {
- return true;
- }
- }
- }
- return false;
-}
-
-} // namespace
-
-void LoudsTrie::PrefixSearchWithKeyExpansion(
- StringPiece key, const KeyExpansionTable &key_expansion_table,
- Callback *callback) const {
- char key_buffer[kMaxDepth + 1];
- PrefixSearchWithKeyExpansionImpl(*this, key, key_expansion_table,
- callback,
- Node(), // Root
- key_buffer, 0);
-}
-
-namespace {
-
// Traverses the subtree rooted at |node| in DFS order and runs |callback| at
// each terminal node. Returns true if traversal should be stopped.
bool TraverseSubTree(
diff --git a/src/storage/louds/louds_trie.h b/src/storage/louds/louds_trie.h
index bf0f66f..5d8551b 100644
--- a/src/storage/louds/louds_trie.h
+++ b/src/storage/louds/louds_trie.h
@@ -46,7 +46,7 @@
static const size_t kMaxDepth = 256;
// This class stores a traversal state.
- using Node = Louds::Node;
+ typedef Louds::Node Node;
// Interface which is called back when the result is found.
class Callback {
@@ -96,7 +96,7 @@
// Returns true if |node| is a terminal node.
bool IsTerminalNode(const Node &node) const {
- return terminal_bit_vector_.Get(node.node_id() - 1);
+ return terminal_bit_vector_.Get(node.node_id() - 1) != 0;
}
// Returns the label of the edge from |node|'s parent (predecessor) to |node|.
@@ -145,6 +145,10 @@
return node;
}
+ // Moves |node| to its child connected by the edge with |label|. If there's
+ // no edge having |label|, |node| becomes invalid and false is returned.
+ bool MoveToChildByLabel(char label, Node *node) const;
+
// Traverses a trie for |key|, starting from |node|, and modifies |node| to
// the destination terminal node. Here, |node| is not necessarily the root.
// Returns false if there's no node reachable by |key|.
@@ -164,6 +168,33 @@
// method, which is more efficient.
int ExactSearch(StringPiece key) const;
+ // Runs a functor for the prefixes of |key| that exist in the trie.
+ // |callback| needs to have the following signature:
+ //
+ // void(StringPiece key, StringPiece::size_type prefix_len,
+ // const LoudsTrie &trie, LoudsTrie::Node node)
+ //
+ // where
+ // key: The original input key (i.e., the same as the input |key|).
+ // prefix_len: The length of prefix, i.e., key.substr(0, prefix_len)
+ // is the matched prefix.
+ // trie: This trie.
+ // node: The location information, from which key ID can be recovered by
+ // LoudsTrie::GetKeyIdOfTerminalNode() method.
+ template <typename Func>
+ void PrefixSearch(StringPiece key, Func callback) const {
+ Node node;
+ for (StringPiece::size_type i = 0; i < key.size(); ) {
+ if (!MoveToChildByLabel(key[i], &node)) {
+ return;
+ }
+ ++i; // Increment here for next loop and call |callback|.
+ if (IsTerminalNode(node)) {
+ callback(key, i, *this, node);
+ }
+ }
+ }
+
// TODO(noriyukit): The following search methods rely on Callback. However,
// this results in the nested callback to implement SystemDictionary's lookup
// methods (i.e., inside implementations of DictionaryInterface::Callback,
@@ -173,17 +204,6 @@
// directly in system_dictionary.cc using more generic APIs defined above.
// Searches the trie structure, and invokes callback->Run when for each word
- // which is a prefix of the key is found.
- void PrefixSearch(StringPiece key, Callback *callback) const {
- PrefixSearchWithKeyExpansion(
- key, KeyExpansionTable::GetDefaultInstance(), callback);
- }
-
- void PrefixSearchWithKeyExpansion(
- StringPiece key, const KeyExpansionTable &key_expansion_table,
- Callback *callback) const;
-
- // Searches the trie structure, and invokes callback->Run when for each word
// which begins with key is found.
void PredictiveSearch(StringPiece key, Callback *callback) const {
PredictiveSearchWithKeyExpansion(
diff --git a/src/storage/louds/louds_trie_test.cc b/src/storage/louds/louds_trie_test.cc
index 6735063..213e61c 100644
--- a/src/storage/louds/louds_trie_test.cc
+++ b/src/storage/louds/louds_trie_test.cc
@@ -31,6 +31,7 @@
#include <limits>
#include <string>
+#include <vector>
#include "base/port.h"
#include "storage/louds/key_expansion_table.h"
@@ -96,6 +97,37 @@
DISALLOW_COPY_AND_ASSIGN(TestCallback);
};
+class RecordCallbackArgs {
+ public:
+ struct CallbackArgs {
+ StringPiece key;
+ size_t prefix_len;
+ const LoudsTrie *trie;
+ LoudsTrie::Node node;
+ };
+
+ explicit RecordCallbackArgs(vector<CallbackArgs> *output) : output_(output) {}
+
+ void operator()(StringPiece key, size_t prefix_len,
+ const LoudsTrie &trie, LoudsTrie::Node node) {
+ CallbackArgs args;
+ args.key = key;
+ args.prefix_len = prefix_len;
+ args.trie = ≜
+ args.node = node;
+ output_->push_back(args);
+ }
+
+ private:
+ vector<CallbackArgs> *output_;
+};
+
+LoudsTrie::Node Traverse(const LoudsTrie &trie, StringPiece key) {
+ LoudsTrie::Node node;
+ trie.Traverse(key, &node);
+ return node;
+}
+
TEST_F(LoudsTrieTest, NodeBasedApis) {
// Create the following trie (* stands for non-terminal nodes):
//
@@ -147,6 +179,11 @@
EXPECT_EQ("a", trie.RestoreKeyString(0, buf));
{
LoudsTrie::Node node;
+ EXPECT_TRUE(trie.MoveToChildByLabel('a', &node));
+ EXPECT_EQ(node_a, node);
+ }
+ {
+ LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("a", &node));
EXPECT_EQ(node_a, node);
}
@@ -158,6 +195,11 @@
EXPECT_EQ('b', trie.GetEdgeLabelToParentNode(node_b));
{
LoudsTrie::Node node;
+ EXPECT_TRUE(trie.MoveToChildByLabel('b', &node));
+ EXPECT_EQ(node_b, node);
+ }
+ {
+ LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("b", &node));
EXPECT_EQ(node_b, node);
}
@@ -174,6 +216,11 @@
EXPECT_EQ(node_aa, trie.GetTerminalNodeFromKeyId(1));
EXPECT_EQ("aa", trie.RestoreKeyString(1, buf));
{
+ LoudsTrie::Node node = node_a;
+ EXPECT_TRUE(trie.MoveToChildByLabel('a', &node));
+ EXPECT_EQ(node_aa, node);
+ }
+ {
LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("aa", &node));
EXPECT_EQ(node_aa, node);
@@ -191,6 +238,11 @@
EXPECT_EQ(node_ab, trie.GetTerminalNodeFromKeyId(2));
EXPECT_EQ("ab", trie.RestoreKeyString(2, buf));
{
+ LoudsTrie::Node node = node_a;
+ EXPECT_TRUE(trie.MoveToChildByLabel('b', &node));
+ EXPECT_EQ(node_ab, node);
+ }
+ {
LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("ab", &node));
EXPECT_EQ(node_ab, node);
@@ -208,6 +260,11 @@
EXPECT_EQ(node_bd, trie.GetTerminalNodeFromKeyId(3));
EXPECT_EQ("bd", trie.RestoreKeyString(3, buf));
{
+ LoudsTrie::Node node = node_b;
+ EXPECT_TRUE(trie.MoveToChildByLabel('d', &node));
+ EXPECT_EQ(node_bd, node);
+ }
+ {
LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("bd", &node));
EXPECT_EQ(node_bd, node);
@@ -223,6 +280,11 @@
EXPECT_FALSE(trie.IsTerminalNode(node_abc));
EXPECT_EQ('c', trie.GetEdgeLabelToParentNode(node_abc));
{
+ LoudsTrie::Node node = node_ab;
+ EXPECT_TRUE(trie.MoveToChildByLabel('c', &node));
+ EXPECT_EQ(node_abc, node);
+ }
+ {
LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("abc", &node));
EXPECT_EQ(node_abc, node);
@@ -237,6 +299,11 @@
EXPECT_EQ(node_abd, trie.GetTerminalNodeFromKeyId(4));
EXPECT_EQ("abd", trie.RestoreKeyString(4, buf));
{
+ LoudsTrie::Node node = node_ab;
+ EXPECT_TRUE(trie.MoveToChildByLabel('d', &node));
+ EXPECT_EQ(node_abd, node);
+ }
+ {
LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("abd", &node));
EXPECT_EQ(node_abd, node);
@@ -255,6 +322,11 @@
EXPECT_EQ(node_abcd, trie.GetTerminalNodeFromKeyId(5));
EXPECT_EQ("abcd", trie.RestoreKeyString(5, buf));
{
+ LoudsTrie::Node node = node_abc;
+ EXPECT_TRUE(trie.MoveToChildByLabel('d', &node));
+ EXPECT_EQ(node_abcd, node);
+ }
+ {
LoudsTrie::Node node;
EXPECT_TRUE(trie.Traverse("abcd", &node));
EXPECT_EQ(node_abcd, node);
@@ -264,10 +336,19 @@
EXPECT_FALSE(trie.IsValidNode(trie.MoveToFirstChild(node_abcd)));
EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(node_abcd)));
+ // Try moving to non-existing nodes by a label.
+ {
+ LoudsTrie::Node node;
+ EXPECT_FALSE(trie.MoveToChildByLabel('x', &node));
+ EXPECT_FALSE(trie.IsValidNode(node));
+ }
+
// Traverse for some non-existing keys.
- LoudsTrie::Node node;
- EXPECT_FALSE(trie.Traverse("x", &node));
- EXPECT_FALSE(trie.Traverse("xyz", &node));
+ {
+ LoudsTrie::Node node;
+ EXPECT_FALSE(trie.Traverse("x", &node));
+ EXPECT_FALSE(trie.Traverse("xyz", &node));
+ }
}
TEST_F(LoudsTrieTest, HasKey) {
@@ -347,160 +428,68 @@
builder.Add("ebd");
builder.Add("\x01\xFF");
builder.Add("\x01\xFF\xFF");
-
builder.Build();
LoudsTrie trie;
trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
{
- TestCallback callback;
- callback.AddExpectation(
- "ab", 2, builder.GetId("ab"), LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation(
- "abc", 3, builder.GetId("abc"), LoudsTrie::Callback::SEARCH_CONTINUE);
+ const StringPiece kKey = "abc";
+ vector<RecordCallbackArgs::CallbackArgs> actual;
+ trie.PrefixSearch(kKey, RecordCallbackArgs(&actual));
- trie.PrefixSearch("abc", &callback);
- EXPECT_EQ(2, callback.num_invoked());
+ ASSERT_EQ(2, actual.size());
+
+ // "ab"
+ EXPECT_EQ(kKey, actual[0].key);
+ EXPECT_EQ(2, actual[0].prefix_len);
+ EXPECT_EQ(&trie, actual[0].trie);
+ EXPECT_EQ(Traverse(trie, "ab"), actual[0].node);
+
+ // "abc"
+ EXPECT_EQ(kKey, actual[1].key);
+ EXPECT_EQ(3, actual[1].prefix_len);
+ EXPECT_EQ(&trie, actual[1].trie);
+ EXPECT_EQ(Traverse(trie, "abc"), actual[1].node);
}
-
{
- TestCallback callback;
- callback.AddExpectation(
- "ab", 2, builder.GetId("ab"), LoudsTrie::Callback::SEARCH_CONTINUE);
+ const StringPiece kKey = "abxxxxxxx";
+ vector<RecordCallbackArgs::CallbackArgs> actual;
+ trie.PrefixSearch(kKey, RecordCallbackArgs(&actual));
- trie.PrefixSearch("abxxxxxxx", &callback);
- EXPECT_EQ(1, callback.num_invoked());
+ ASSERT_EQ(1, actual.size());
+
+ // "ab"
+ EXPECT_EQ(kKey, actual[0].key);
+ EXPECT_EQ(2, actual[0].prefix_len);
+ EXPECT_EQ(&trie, actual[0].trie);
+ EXPECT_EQ(Traverse(trie, "ab"), actual[0].node);
}
-
{
- // Make sure that non-ascii characters can be found, too.
- TestCallback callback;
- callback.AddExpectation("\x01\xFF", 2, builder.GetId("\x01\xFF"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("\x01\xFF\xFF", 3, builder.GetId("\x01\xFF\xFF"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
+ // Make sure that it works for non-ascii characters too.
+ const StringPiece kKey = "\x01\xFF\xFF";
+ vector<RecordCallbackArgs::CallbackArgs> actual;
+ trie.PrefixSearch(kKey, RecordCallbackArgs(&actual));
- trie.PrefixSearch("\x01\xFF\xFF", &callback);
- EXPECT_EQ(2, callback.num_invoked());
+ ASSERT_EQ(2, actual.size());
+
+ // "\x01\xFF"
+ EXPECT_EQ(kKey, actual[0].key);
+ EXPECT_EQ(2, actual[0].prefix_len);
+ EXPECT_EQ(&trie, actual[0].trie);
+ EXPECT_EQ(Traverse(trie, "\x01\xFF"), actual[0].node);
+
+ // "\x01\xFF\xFF"
+ EXPECT_EQ(kKey, actual[1].key);
+ EXPECT_EQ(3, actual[1].prefix_len);
+ EXPECT_EQ(&trie, actual[1].trie);
+ EXPECT_EQ(Traverse(trie, "\x01\xFF\xFF"), actual[1].node);
}
-
- trie.Close();
-}
-
-TEST_F(LoudsTrieTest, PrefixSearchWithLimit) {
- LoudsTrieBuilder builder;
- builder.Add("aa");
- builder.Add("ab");
- builder.Add("abc");
- builder.Add("abcd");
- builder.Add("abcde");
- builder.Add("abcdef");
- builder.Add("abd");
- builder.Add("ebd");
-
- builder.Build();
-
- LoudsTrie trie;
- trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
-
{
- TestCallback callback;
- callback.AddExpectation("ab", 2, builder.GetId("ab"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("abc", 3, builder.GetId("abc"),
- LoudsTrie::Callback::SEARCH_DONE);
-
- trie.PrefixSearch("abcdef", &callback);
- EXPECT_EQ(2, callback.num_invoked());
+ vector<RecordCallbackArgs::CallbackArgs> actual;
+ trie.PrefixSearch("xyz", RecordCallbackArgs(&actual));
+ EXPECT_TRUE(actual.empty());
}
-
- {
- TestCallback callback;
- callback.AddExpectation("ab", 2, builder.GetId("ab"),
- LoudsTrie::Callback::SEARCH_DONE);
-
- trie.PrefixSearch("abdxxx", &callback);
- EXPECT_EQ(1, callback.num_invoked());
- }
-
- trie.Close();
-}
-
-TEST_F(LoudsTrieTest, PrefixSearchWithKeyExpansion) {
- LoudsTrieBuilder builder;
- builder.Add("abc");
- builder.Add("adc");
- builder.Add("cbc");
- builder.Add("ddc");
-
- builder.Build();
- LoudsTrie trie;
- trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
-
- KeyExpansionTable key_expansion_table;
- key_expansion_table.Add('b', "d");
-
- {
- TestCallback callback;
- callback.AddExpectation("abc", 3, builder.GetId("abc"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("adc", 3, builder.GetId("adc"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
-
- trie.PrefixSearchWithKeyExpansion("abc", key_expansion_table, &callback);
- EXPECT_EQ(2, callback.num_invoked());
- }
-
- {
- TestCallback callback;
- callback.AddExpectation("adc", 3, builder.GetId("adc"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- trie.PrefixSearchWithKeyExpansion("adc", key_expansion_table, &callback);
- EXPECT_EQ(1, callback.num_invoked());
- }
-
- trie.Close();
-}
-
-TEST_F(LoudsTrieTest, PrefixSearchCulling) {
- LoudsTrieBuilder builder;
- builder.Add("a");
- builder.Add("ab");
- builder.Add("abc");
- builder.Add("abcd");
- builder.Add("ae");
- builder.Add("aec");
- builder.Add("aecd");
-
- builder.Build();
- LoudsTrie trie;
- trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
-
- KeyExpansionTable key_expansion_table;
- key_expansion_table.Add('b', "e");
-
- {
- TestCallback callback;
- callback.AddExpectation("a", 1, builder.GetId("a"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("ab", 2, builder.GetId("ab"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("abc", 3, builder.GetId("abc"),
- LoudsTrie::Callback::SEARCH_CULL);
- // No callback for abcd, but ones for ae... should be found.
- callback.AddExpectation("ae", 2, builder.GetId("ae"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("aec", 3, builder.GetId("aec"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
- callback.AddExpectation("aecd", 4, builder.GetId("aecd"),
- LoudsTrie::Callback::SEARCH_CONTINUE);
-
- trie.PrefixSearchWithKeyExpansion("abcd", key_expansion_table, &callback);
- EXPECT_EQ(6, callback.num_invoked());
- }
-
- trie.Close();
}
TEST_F(LoudsTrieTest, PredictiveSearch) {
