記事にあるすべての Trie 実装を確認するのはしんどいので、代表的な感じのものを適当にピックアップしてみました。
- Tx ... 岡野原さんによる簡潔データ構造を利用した Trie の実装。
- prefixSearch() ... prefix search。Trie に格納されている文字列の中で、対象文字列の接頭辞としてもっとも長く一致する文字列を探し出す。common prefix search で列挙される文字列のうち、長さが最長のものと同じ。
- commonPrefixSearch() ... common prefix search。Trie に格納されている文字列より、対象文字列の接頭辞にあたる文字列をすべて列挙する。結果は一括して求められる。
- predictiveSearch() ... predictive search。Trie に格納されている文字列より、対象文字列が接頭辞となる文字列をすべて列挙する。結果は一括して求められる。
- expandSearch() ... common prefix search + predictive search。Trie に格納されている文字列より、対象文字列を接頭辞とする文字列、または対象文字列の接頭辞にあたる文字列を列挙する。結果は一括して求められる。
- UX ... Tx と同じく岡野原さんによるプロダクト。さらに簡潔。だいたい Tx と同じ API 構成。この命名は、"Tx" の１つ先（t -> u）を行く、という意味が込められているのかな？
- prefixSearch() ... prefix search。
- commonPrefixSearch() ... common prefix search。
- predictiveSearch() ... predictive search。
- sumire-tries ... やたさんによる、簡潔データ構造を含む各種 Trie の実装。Trie 木構造のノードレベルでの走査（traversal）ができるのが特徴。
- TrieBase#find() ... exact match。Trie に格納されている文字列より、対象文字列に完全一致する文字列を探し出す。
- TrieBase#follow() ... Trie・ノードの走査。指定されたノードから始まり、対象文字列に合致する Trie 上の経路（ノード）を辿る。
- TrieBase#find_child() ... Trie・ノードの走査。あるノードより指定された文字を辿った先にある子ノードを求める。
- TrieBase#child() ... Trie・ノードの走査。指定のノードの先にある子ノードのうち、最初の子ノードを求める。
- TrieBase#sibling() ... Trie・ノードの走査。指定のノードの、次の兄弟ノードを求める。
- class CompleterBase ... predictive search。Iterator パターンで、文字列を順次列挙する。
- marisa-trie ... やたさんによる、簡潔データ構造を利用した Trie の実装。UX の手法をさらに発展させたものっぽい。
- lookup() ... exact match。sumire-tries では find() でしたが、marisa-trie では同名メソッドは別の機能を提供しているようです。
- find() ... common prefix search。一括して列挙する。
- find_first()/find_last() ... prefix search。
- find_callback() ... common prefix search。１つずつ、コールバック関数を呼び出して列挙する。
- predict() ... predictive search。一括して列挙する。
- predict_callback() ... predictive search。１つずつ、コールバック関数を呼び出して列挙する。
- Darts ... MeCab 開発者の工藤さんによる Double Array Trie の実装。MeCab でも利用されています。
- exactMatchSearch() ... exact match。
- commonPrefixSearch() ... common prefix search。一括して列挙する。
- Doar ... Igo/Gomoku の開発者 sile さんによる Double Array Trie の C++ 実装。
- Searcher#search() ... exact match かな？
- Searcher#common_prefix_search() ... common prefix search。１つずつ、コールバック関数を呼び出して列挙する。
- Searcher#children() ... Trie・ノードの走査。子ノードを１つずつ、コールバック関数を呼び出して列挙する。
- jada ... sile さんによる Double Array Trie の Java 実装。
- Trie#search() ... exact match。
- Trie#commonPrefixSearch() ... common prefix search。同メソッドを繰り返し呼び出して、１つずつ列挙する。
こんなところでしょうか。以上より「Trie を使った操作」は、
- exact match
- common prefix search
- predictive search
- prefix search
「Trie の走査を実現する走査」としては、ピックアップした実装ではあまり提供されていませんでしたが、
- あるノードの直下の子ノードを列挙する
この結果を参考に、汎用的に使えそうな Trie の Java 実装について検討を進めてみます。
0 コメント:
コメントを投稿