文献

J-GLOBAL ID：201702284345082125   整理番号：17A1370030

Path Decompositionを用いたメモリ効率の良い動的キーワード辞書の実装法

著者 (4件)： 神田峻介 (徳島大 大学院先端技術科学教育部) ,  神田峻介 (日本学術振興会) ,  森田和宏 (徳島大 大学院先端技術科学教育部) ,  泓田正雄 (徳島大 大学院先端技術科学教育部)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 212(DE2017 13-23)  ページ： 87-92  発行年： 2017年09月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： キーワード辞書とは文字列をキーとする連想配列であり,文字列集合を保管するためのデータ構造として古くから用いられている。一方で近年,このキーワード辞書を用いて大規模な文字列データを主記憶で管理するといった実例が数多く報告されており,メモリ効率の良い実装が求められている。現在のところ,静的用途に限定すれば数多くの実装が高いメモリ効率を達成している。しかし,それらに比べて既存の動的な実装は遥かに多くのメモリを消費する。そこで本稿では,Path Decompositionを用いたメモリ効率の良い動的キーワード辞書の実装法を提案する。Path Decompositionとは本来,キャッシュフレンドリーなTrie辞書を実装するために用いられる技法であるが,本提案では省メモリな動的辞書を実現するためにこの技法を用いる。大規模な現実のデータセットを用いた実験により,提案手法は既存の最もメモリ効率の良い実装と比べ,最大で2.8倍もコンパクトに動的辞書を実現できることを示す。(著者抄録)

シソーラス用語： キーワード ,  *辞書 ,  文字列 ,  データ ,  主メモリ ,  実装 ,  *効率 ,  木構造 ,  登録
準シソーラス用語： *メモリ効率 ,  大規模データ ,  *キーワード辞書

分類 (2件)： 自然語処理  (JE06000L) ,  その他の情報処理  (JE15050M)

引用文献 (22件)：

• Mart?nez-Prieto, M. A., Brisaboa, N., C?novas, R., Claude, F. and Navarro, G.: Practical compressed string dictionaries, Information Systems, Vol. 56,, pp. 73-108 (2016).
• Mavlyutov, R., Wylot, M. and Cudre-Mauroux, P.: A Comparison of Data Structures to Manage URIs on the Web of Data, Proc. 12th ESWC, pp. 137-151 (2015).
• Knuth, D. E.: The art of computer programming, 3: sorting and searching, Addison Wesley, Redwood City, CA, USA, 2nd edition (1998).
• Kanda, S., Morita, K. and Fuketa, M.: Practical string dictionary compression using string dictionary encoding, Proc. 3rd Innovate-Data (to appear).
• Kanda, S., Morita, K. and Fuketa, M.: Compressed double-array tries for string dictionaries supporting fast lookup, Knowledge and Information Systems, Vol. 51, No. 3, pp. 1023-1042 (2017).

タイトルに関連する用語 (4件)： メモリ効率 ,  キーワード ,  辞書 ,  実装