著者

森田 和宏 泓田 正雄 大野 将樹 青江 順一

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.42, no.9, pp.2229-2238, 2001-09-15

被引用文献数

5

---

トライ構造はキーの表記文字単位に構成された木構造を用いて検索するキー検索技法の1つであり,自然言語辞書を中心として広く用いられている.このトライ構造を実現するデータ構造として高速性とコンパクト性を満足するダブル配列法があるが,この手法は,キーの更新が頻繁に生じない検索法として確立しているため,動的検索法に比べて追加時間は高速であるとはいえず,また削除で生じる不要なノードや未使用要素により記憶量に無駄が生じていた.本論文ではこれらの問題を解決し,ダブル配列を動的検索法として確立するため,未使用要素を連結することで追加処理を高速化する手法,削除時に生じる不要ノードの削除と未使用要素の詰め直しによる圧縮法を提案する.10万語の辞書データに対する実験結果により,追加速度については約1 600倍高速となることが,また大量の削除が起こった場合でも50%以上の空間使用率を維持することが分かった.In many information retrieval applications,it is necessary to be able to adopt a trie search for looking at the input character by character.As a fast and compact data structure for a trie, a double-array is presented.However, the insertion time isn't faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequent updating.Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion.This paper presents a fast insertion algorithm by linking empty elements to find inserting positions quickly and a compression algorithm by reallocating empty elements for each deletion.From the simulation results for 100 thousands keys,it turned out that the presented method for insertion is about 1,600 times faster than the original method,and that the presented method for space efficiency keeps the activity ratio more than 50%.

著者

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

出版者

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

雑誌

研究報告情報基礎とアクセス技術(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%でトライを表現可能なことが実験により確認されている.

著者

矢田 晋 大野 将樹 森田 和宏 泓田 正雄 吉成 友子 青江 順一

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.6, pp.1894-1902, 2006-06-15

被引用文献数

3

---

接頭辞ダブル配列はトライを高速かつコンパクトに実現するデータ構造である.しかし,キーの削除によって配列中に未使用の要素が蓄積し,空間効率が低下するという欠点がある.また,更新時間が未使用要素の数に依存するため,削除による空間効率の低下は更新時間の悪化にもつながる.本稿では,未使用要素を増加させることなく接頭辞ダブル配列からキーを削除する手法を提案する.EDR電子化辞書の日英単語各10 万件に対する実験により,提案法は従来法と比べて約17?460 倍高速であり,高い空間効率を維持することが実証された.Minimal Prefix (MP) double-array represents a trie with two advantages 窶髏 a fast retrieval and a compact dictionary. However, a key deletion produces empty elements and degrades the space efficiency of MP double-array. In addition, the deletion speed of MP double-array is degraded by the key deletion because the deletion time depends on the number of empty elements. This paper presents an efficient deletion method for MP double-array. The method dynamically removes keys from MP double-array without increasing empty elements. From experimental results for the key set which consists of 100,000 keys, it turned out that the presented method is about 17窶骭460 times faster than the conventional method and maintains high space efficiency.

著者

大野 将樹 森田 和宏 泓田 正雄 青江 順一

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.44, no.5, pp.1311-1320, 2003-05-15

被引用文献数

4

---

トライ法は自然言語処理システムの辞書を中心として広く用いられているキー検索技法であり,トライを実現するデータ構造に検索の高速性と記憶量のコンパクト性をあわせ持つダブル配列構造がある.ダブル配列構造の欠点は,キーの削除によって生じる未使用要素により空間効率が低下する点である.これに対し森田らはダブル配列を詰め直すことにより未使用要素を除去するキー削除法を提案した.しかし,この手法はすべての未使用要素を除去できないため高い空間効率を維持できず,また削除コストが未使用要素数に依存するので,削除を連続するほど削除速度が低下するという問題がある.本論文では,トライの節のうち兄弟を持たない節が多くの割合を占めること,また,これらの節の遷移は容易に変更できるという特徴を利用し,削除を連続した場合でも空間使用率と削除速度を低下させない効率的なキー削除法を提案する.EDR日英単語辞書,WordNet英単語辞書,日本の郵便番号リスト,各5万件に対する実験より,提案法は削除を連続した場合でもきわめて高い空間使用率を維持することが,また,森田らの削除法より約50?200倍高速に削除できることが実証された.A trie is a well known method for various dictionaries, such as spelling check and morphological analysis. A double-array structure is an efficient data structure combining fast access of a matrix form with compactness of a list form. The drawback of the double-array is that the space efficiency becomes worse by empty elements produced in key deletion. Therefore, Morita presented a key deletion method eliminating empty elements. However, the space efficiency of this method is low for high frequent deletion. Further, the deletion takes a lot of time because the cost depends on the number of empty elements. In this paper, a fast and compact deletion method is presented by using a property of nodes having no brothers. From simulation results for 50,000 keys, it turned out that the presented method is faster 50 to 200 times than Morita's method and keeps high space efficiency.