著者

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

出版者

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

雑誌

研究報告情報基礎とアクセス技術(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.