■
菊田 昌弘
用語解説: パトリシアツリー(Patricia Tree)
人工知能学会誌, Vol. 11, No. 2, pp. 337-339, November 1996

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
M. Al-Suwaiyel, E. Horowitz
Algorithm for Trie Compaction
ACM Transactions on Database Systems, Vol. 9, No. 2, pp. 243-263, June 1984
■
トライのノードをビット列(e.g. 00011000)と思って、それを いかに最適に重ねあわせるかという話をしている。他の方式 の可能性については議論していない。Greedyに順番に入れ ていくと最適にならない場合があるから最適のものをみつ けるには時間がかかる。(当然)

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
W. Litwin
Trie Hashing
Proceedings of ACM SIGMOD Conference on Management of Data, pp. 19-29, 1981

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
V. K. Vaishnavi, H. P. Kriegel, D. Wood
Optimum Multiway Search Trees
Acta Informatica, Vol. 14, No. 2, pp. 119-133, 1980

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
W. D. Jonge, A. S. Tanenbaum, R. P. Riet
Two Access Methods Using Compact Binary Trees
ieeese, Vol. 13, No. 7, pp. 799-810, July 1987
■
2進木トライを使ったデータベースのインデクス付け。2進 木をコンパクトに表現する手法。

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
F. Ruskey
Generating T-ary Trees Lexicographically
SIAM Journal of Computing, Vol. 7, No. 4, pp. 424-439, November 1978

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
P. Flajolet
On The Performance Evaluation of Extendible Hashing and Trie Searching
Acta Informatica, Vol. 20, No. 4, pp. 345-369, 1983

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
R. Ramesh, A. V. G. Babu, J. P. Kincad
Variable-depth Trie Index Optimization: Theory and Experimental Results
ACM Transactions on Database Systems, Vol. 14, No. 1, pp. 41-74, March 1989
■
トライは場所を食うので(?)、トライとバイナリサーチを 組みあわせた方法を提案している。木の根に近い方はトラ イを使い、葉の方はバイナリサーチを使う。

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
P. Flajolet, R. Sedgewick
Digital Search Trees Revised
SIAM Journal of Computing, Vol. 15, No. 3, pp. 748-767, August 1986

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
J. A. Orenstein
Multidimensional Tries Used For Associative Searching
Information Processing Letters, Vol. 14, No. 4, pp. 150-157, June 1982

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
E. Fredkin
Trie Memory
cacm, Vol. 3, No. 9, pp. 490-500, September 1960
■
Trieの発明?

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Donald R. Morrison
PATRICIA -- Practical Algorithm To Retrieve Information Coded in Alphanumeric
jacm, Vol. 15, No. 4, pp. 514-534, October 1968
■
テキストデータ検索のためのTrieに似たデータ構造

詳細　Wikiページ作成　関連カテゴリ: データ圧縮　トライ構造

■
D. Comer
Analysis of a Heuristic for Full Trie Minimization
ACM Transactions on Database Systems, Vol. 6, No. 3, pp. 513-537, September 1981

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Owen Murphy
A Unifying Framework for Trie Design Heuristics
Information Processing Letters, Vol. 30, pp. 243-249, 1990

詳細　Wikiページ作成　関連カテゴリ: データ圧縮　トライ構造

■
D. Comer
Heuristics for Trie Index Minimization
ACM Transactions on Database Systems, Vol. 6, No. 3, pp. 383-395, September 1979
■
ヒューリスティックスを使ってトライを圧縮する。1)子が ひとつしかないノードは「useless」なので、usefulな attribute(普通は文字)を先に選ぶようにする。2)最も多 くの子に分割するattributeを選ぶ。3)最も多くの葉が選 ばれるようにする。4)最も多くの内部ノードが選ばれるよ うにする、等。どのattributeを調べるかノードに書いて おくO-Trieという方式も提案している。
■
どれもたいしたヒューリスティックスではない。

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Toshiyuki Masui
Keyword Dictionary Compression Using Efficient Trie Implementation
Proceedings of Data Compression Conference, pp. 438, April 1991

詳細　Wikiページ作成　関連カテゴリ: 文字列検索/パタンマッチ　トライ構造

■
D. Comer, R. Sethi
Complexity of Trie Index Construction
jacm, Vol. 24, No. 3, pp. 428-440, July 1977

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
W. Burkhard
Hashing and Trie Algorithm for Partial match Retrieval
ACM Transactions on Database Systems, Vol. 11, No. 2, pp. 175-187, June 1976

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Titus D. M. Purdin
Compressing Tries for Storing Dictionaries
Proceedings of the 1990 Symposium on Applied Computing, pp. 336-340, April 1990
■
トライのノードをbitmap representationで表現し、この bitmap representationを圧縮する。英文字26文字のため に4バイト1使用するが、疎な場合のために、最初の3ビッ トを残りのバイトの有無の判定に使用する。次ノードへの ポインタは相対値で表現し、ポインタもやはり同様に圧縮 表現する。
■
ノードの表現方式はビットマップ表現だけである。ノード データの圧縮法はそのまま使えるが、このようなやり方が 最適かどうかは不明である。頻度に依存するであろう。子 供がひとつだけの場合は文字列表現の方がやはり小さくな るはずであり、ふたつの場合はリスト表現と同じ程度であ ろう。(ポインタ×2＋3バイト)

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
青江 順一
ダブル配列による高速ディジタル検索アルゴリズム
電子情報通信学会論文誌 D, Vol. J71-D, No. 9, pp. 1592-1600, September 1988

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
M. Miyakawa, T. Yuba, Y. Sugito, M. Hoshi
Optimum Sequence Trees
SIAM Journal of Computing, Vol. 6, No. 2, pp. 201-234, June 1977

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Jun'ichi Aoe
An Efficient Implementation of String Pattern Matching Machines for a Finite Number of Keywords
SIGIR Forum, Vol. 23, No. 3,4, pp. 22-33, Spring/Summer 1989
■
ある文字列が与えられたキーワードの集合に属するかど うかを効率よく判定するためのデータ構造。コンパイラ、 スペルチェック等に応用できる。基本はAho-Corasick法 Aho_stringmatchであるが、分岐がおこらないこと がはっきりした時点でstrcmpを使うことでデータ構造を小 さくおさえている。また、複数のステートから別のステー トへのマージは起こらないということにしてもデータ構造 を小さくおさえている。
■
状態遷移をプログラムするには普通多数のテーブルが必要 となる。例えばflexでは文字列abcdeを認識するのに状態を 5つ経由しなければならないため6要素のテーブルが2個必要 となっている。これはstrcmpすることにすれば6バイトです む。このようにして一般的なテーブルコンパクションを行 なうことは可能かもしれない。 flexではステート数は最小になるがステート最小がテーブ ル最小に必ずしもならないということだろうか。

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
E. Sussenguth
Use of Trie Structures for Processing FIles
cacm, Vol. 6, No. 5, May 1963

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Jun'ichi Aoe
An Efficient Digital Search Algorithm by Using a Double-Array Structure
IEEE Transactions on Software Engineering, Vol. 15, No. 9, pp. 1066-1077, September 1989

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
B. M. Nicklas, G. Schlageter
Index Structuring in Inverted Data Bases by Tries
Computer Journal, Vol. 20, No. 4, pp. 321-324, November 1977

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
青江 順一
ダブル配列による有限状態機械の効率的インプリメンテーション
電子情報通信学会論文誌 D, Vol. J70-D, No. 4, pp. 653-662, April 1987

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
M. Regnier
On The Average Height of Trees in Digital Search and Dynamic Hashing
Information Processing Letters, Vol. 13, No. 2, pp. 64-66, November 1981

詳細　Wikiページ作成　関連カテゴリ: トライ構造

■
Kurt Maly
Compressed Tries
cacm, Vol. 19, No. 7, pp. 409-415, July 1976
■
C-Trieというデータ構造を提案している。トライのノード は子供のビットマップ表現・終端であるかどうかのフラグ・ 子供がいるかどうかのフラグ・子供のオフセットから構成 される。ノードの子供の位置は、ビットマップから子供の 存在を確認した後オフセットとビット位置から計算する。 あらゆるノードのサイズが同じでなければならないのでか なり無駄が生じるようである。
■
昔はこういう提案でも評価されたのか、という感じ。

詳細　Wikiページ作成　関連カテゴリ: トライ構造