文献

J-GLOBAL ID：201502215846252025   整理番号：15A1076961

トライにおける逆方向遷移可能かつコンパクトな配列構造

A Compact Array Structure with Reverse Traversal in a Trie

著者 (4件)： 神田峻介 (徳島大 大学院先端技術科学教育部) ,  泓田正雄 (徳島大 大学院先端技術科学教育部) ,  森田和宏 (徳島大 大学院先端技術科学教育部) ,  青江順一 (徳島大 大学院先端技術科学教育部)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 177(DE2015 12-19)  ページ： 55-60  発行年： 2015年07月29日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： トライと呼ばれる順序木を効率的に表現するデータ構造として,高速な検索を提供するダブル配列がある。また,データの大規模化に伴いコンパクト性が重視される背景に応じて,様々なダブル配列の圧縮表現が提案されてきた。しかし,これらの圧縮表現は,トライにおける順方向の遷移(親から子)のみを提供し,逆方向の遷移(子から親)を提供していないため,結果としてダブル配列における逆引きや動的更新を犠牲にしている。本論文では,逆方向遷移を可能としたコンパクトな配列構造を提案する。記憶量について,ダブル配列の約36%でトライを表現可能なことが実験により確認されている。(著者抄録)

シソーラス用語： *情報検索 ,  データ ,  *ツリー構造 ,  配列 ,  木探索 ,  圧縮 ,  データ更新 ,  逆方向 ,  状態 ,  データ圧縮
準シソーラス用語： *ダブル配列 ,  遷移 ,  大規模データ

分類 (2件)： データベースシステム  (JD03030U) ,  計算機網  (JC03000K)

引用文献 (10件)：

• Fredkin, E.: Trie Memory, Commun. ACM, Vol. 3, No. 9, pp. 490-499 (1960).
• Aoe, J.: An efficient digital search algorithm by using a double-array structure, IEEE Transactions on Software Engineering, Vol. 15, No. 9, pp. 1066-1077 (1989).
• 矢田 晋,森田和宏,泓田正雄,平石亘,青江順一:ダブル配列におけるキャッシュの効率化,第5回情報科学技術フォーラム講演論文集(FIT2006), pp.71-72(2006).
• 森田和宏,望月久稔,山川善弘,青江順一:トライ構造を用いた共起情報の効率的検索アルゴリズム.情報処理学会論文誌,Vol.39, No.9, pp.2563-2571(1998).
• Fuketa, M., Kitagawa, H., Ogawa, T., Morita, K. and Aoe, J.: Compression of double array structures for fixed length keywords, Information Processing & Management, Vol. 50, No. 5, pp. 796-806 (2014).

タイトルに関連する用語 (1件)： 遷移