2024-03-28T20:55:55Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001024562023-04-27T10:00:04Z01164:01165:07638:07639
近似直線を用いたダブル配列の圧縮法A Compression Method of Double Array Structures using Approximate Straight Linesjpnトピック抽出・効率化http://id.nii.ac.jp/1001/00102433/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=102456&item_no=1&attribute_id=1&file_no=1Copyright (c) 2014 by the Information Processing Society of Japan徳島大学徳島大学徳島大学徳島大学神田, 峻介森田, 和宏泓田, 正雄青江, 順一トライ法とはキー検索を実現する手法のひとつであり,自然言語処理などにおいて幅広く活用されている.トライ法を実現するデータ構造としては,ダブル配列や 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.AN10112482研究報告データベースシステム(DBS)2014-DBS-15911162014-07-252014-07-24