commit 25b997d798dbe08d2b2dbd9414ed3747e1918889
author Noriyuki Takahashi <noriyukit@google.com> Sat Jan 31 09:02:05 2015 +0000
committer Yohei Yukawa <yukawa@google.com> Sat Jan 31 09:02:05 2015 +0000
tree c2c9c1e493e1e41255dc6ef93cdf68b8a2b5e382
parent b782c5af17f7fe17f4024098959e20c99381bf14

Refactor LOUDS trie by introducing a new API set for traversal

Louds::Node structure is introduced to represent the position in the tree during traversal.  Three basic movements are implemented: 1) go to the first child, 2) go to the next sibling, and 3) go to the parent.  This new design brings a few benefits:
* Intermediate traversal state can be saved (e.g., incremental search can be implemented).
* Similar pieces of code in ExactSearcher, PrefixSearcher and PredictiveSearcher are factored out, so new code looks more concise and intuitive.
* New APIs take StringPiece instead of const char*.

Using the new APIs, LoudsTrie::HasKey is introduced, which is a faster modification of LoudsTrie::ExactSearch to test the existence of key, where one Rank1 operation is saved compared to ExactSearch.  This is nice because HasKey is called more often than before, e.g., from LanguageAwareRewriter.

Also, in LoudsTrie::Reverse, which is renamed to LoudsTrie::RestoreKeyString, one Rank0 operation is eliminated in the loop of key string reconstruction.  Namely, N operations are saved for keys of length N.

Benchmark shows no performance regression.  Also, this is just a code refactoring, no behavior change is intended.

BUG=none
TEST=unittest,benchmark

git-svn-id: https://mozc.googlecode.com/svn/trunk@524 a6090854-d499-a067-5803-1114d4e51264