takawitter/trie4j — pull request #5 by hiroshi-manabe (2014-04-29 13:11:58+00:00)
Title: Add an interface which enables obtaining the ids for the keys.

trie の典型的なユースケースの一つとして、「キーと何かしらの値を関連付けたい」ということがあります。
現在のコードでは MapTrie というインターフェイスがあり、それを実装した MapDoubleArray を使うことによって、そのような場合に対応が可能です。

ただ、速度よりもメモリ使用量の少なさを優先して LOUDS を使いたい場合、現状ではキーと値の関連付けができません。
ここで、連続した内部IDをキーと関連付けることができれば、ユーザ側でキーに対応するIDを取得して配列のインデックスに使うなどの方法で、任意のオブジェクトとの関連付けが可能です。
たとえば marisa-trie では、そのような内部IDを取得することができるようになっています。

このプルリクエストでは、キーとIDのペアを取得するための IdTrie というインターフェイスを追加し、AbstractTailLOUDSTrie にそれを実装させることで、TailLOUDSTrie と TailLOUDSPPTrie で使えるようにしています。
内部IDは、葉となるかどうかのフラグである term を SuccinctBitVector としても持ち、ノードIDによってrank1()を行った結果から1を引くことによって求めています。
また、コードの重複を防ぐため、内部IDを取得しない既存のメソッドから新しく追加したノードIDを取得するメソッドを呼ぶようにしています。
このことによってメモリ・速度上のオーバーヘッドが生じますが、私としてはキーとIDを関連付けられるメリットが上回ると考えています。
（もちろん考え方が異なることもあると思います。その場合は取り下げます）

ご検討をお願いします。