Dame
出典: やる気向上作戦
目次 |
何ですかこれは？
効率的なTrieの実装方法であるDouble-ArrayのC++ライブラリ。
割合 http://citeseer.ist.psu.edu/aoe92efficient.html に忠実に作っています。
ヘッダライブラリなので、includeするだけで使えます。多分プラットフォーム非依存。 なお、以下の拡張を実装しています。
- TAIL
- G-link
できること
- std::set<std::string> 的動作 (完全互換ではありません）
- Common prefix search
- Longest prefix match
使い方
#include <iostream>
#include "dame.h"
dame::DoubleArrayTrie trie;
trie.insert("bachelor");
trie.insert("jar");
trie.insert("badge");
trie.insert("baby");
// babyを検索
dame::DoubleArrayTrie::iterator it = trie.find("baby");
if (it != trie.end()) {
std::cout << "baby found!" << std::endl;
}
// "ba"で始まる全てのキーを探索
dame::DoubleArrayTrie::iterator endit;
it = trie.findPrefixedBy("ba", endit);
while (it != endit) {
std::cout << *it << std::endl;
++it;
}
// "bachelorism"の最長prefixを探索
it = trie.findLongestPrefixOf("bachelorism");
if (it != trie.end()) {
std::cout << *it << std::endl;
}
バグ
バグ？あー、うん、有るんじゃないかな。多分。
ライセンス
Public Domain
ダウンロード
履歴
- 2006/5/30 ver. 1.3
- iteratorが、キー以外を指さないようにした。DoubleArrayTrieElementからvalueメンバを削除。代わりにTAILの先頭に詰めるようにした。
- 2006/5/29 ver. 1.2
- iteratorを引数にとるinsert(), erase()を追加。
- charとarray_index_tのマッピングを行うクラスを切り出し、テンプレート引数で与えるようにした。
- 2006/5/28 ver. 1.1
- 空文字列も挿入できるように仕様を変更。
- reserve()追加。
- find(), insert(), erase()がconst std::string&を引数にとることができるようにした。
- std::setとの整合性のため、insert()がstd::pair<iterator,bool>を返すよう変更。
- 2006/5/27 ver. 1.0
- iterator実装。プレフィックスサーチ実装。
- 2006/5/26 ver. 0.1
- G-link実装。衝突解決のバグを修正。
- 2006/5/24 Public Release
