各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区切り('\n')で保持するソート済みのファイルを入力に取り、DoubleArrayを構築する BASE配列とCHECK配列から成る BASE配列: 遷移情報およびキーのIDを保持する配列 BASE[ノード] = 遷移のベースとなるノード => 遷移先ノードは、BASE[ノード] + 遷移文字、で求める BASE[ノード]の値がマイナスの場合は、キーの終端を意味し、そのIDが格納されている => キーのIDは、BASE[ノード] x -1、で求める CHECK配列: 遷移の正当性をチェックするための配列 CHECK[ノー
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く