著者

神田 峻介 森田 和宏 泓田 正雄 青江 順一

出版者

一般社団法人情報処理学会

雑誌

研究報告情報基礎とアクセス技術(IFAT)

巻号頁・発行日

vol.2014, no.11, pp.1-6, 2014-07-25

---

トライ法とはキー検索を実現する手法のひとつであり,自然言語処理などにおいて幅広く活用されている.トライ法を実現するデータ構造としては,ダブル配列や LOUDS などがあげられる.ダブル配列は,トライのノード間の遷移を O(1) で実現する高速性を備えたデータ構造であるが,簡潔データ構造である LOUDS と比べ,記憶量は大きい.LOUDS は,ビットベクトルによりトライを表現するため,コンパクト性に優れたデータ構造であるが,ダブル配列に対し検索速度は劣る.本稿では,近似直線との差分値を用いたダブル配列の圧縮法を提案する.また,Wikipedia 日英タイトル各 20 万語~100 万語に対する実験により,提案手法は従来のダブル配列と比べて,記憶量を約 60%に圧縮し,且つ LOUDS より約 12 倍高速に検索がおこなえることが実証された.A trie is one of the method for key search algorithm and utilized in natural language processing and so on. It is represented by a double array and LOUDS. The double array provides fast retrieval at time complexty of O(1), but its space usage is larger than that of LOUDS. LOUDS is a succinct data structure using bit-vector. Its space usage is extremely compact, but its retrieval speed is not so fast. This paper presents a compression method of the double array using approximate straight lines. From simulation results for 200,000~1,000,000 keys, it turned out that the space usage of the presented method becomes about 60% compared with the double array and its retrieval speed is about twelve times faster than that of LOUDS.

著者

神田 峻介 泓田 正雄 森田 和宏 青江 順一

雑誌

研究報告情報基礎とアクセス技術(IFAT) (ISSN:21888884)

巻号頁・発行日

vol.2015-IFAT-119, no.10, pp.1-6, 2015-07-29

---

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