Patricia Trieの実装する上での基礎事項 - Topics Related to Computers and NLP
※Javaコードの実装が追いついていないので、実装でき次第追記しておきます。 Trieは辞書を参照する等で非常に便利なデータ構造なので、ちょっとメモしておく。今回はこのTrieの一種であるPatiricia Trieのお話。 基数木とも呼ばれているが、僕は基本的にPatricia trie（パトリシアトライ、パトリシア木）と呼んでいる。Trieのノードもしくはエッジが文字列に対応する事によって、余計なノードを確保せずにすむのでメモリの節約になる。 実装する上（自分はJavaを想定）での注意点を列挙した。基本的なことであるが「問題を細分化して、自分の理解可能なレベルにまで落とすこと」は非常に重要なことであるので、やってみた。 Trieからの変更点 最もナイーブな実装である「アルファベットの数だけ、配列を確保する」とメモリを浪費してしまう 何も考えずに分岐点に256個のポインターを配列として並
Patricia Trie Template Class
This article introduces a template class-based approach to construct and query Patricia tries. The article includes source code and a demo application. Download source files - 11.8 Kb Download demo project - 13.9 Kb Introduction While working for a company that produced software development tools, I had to write an application that encapsulated an entire file system within a single file. Part of t
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
