著者

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

出版者

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

雑誌

情報処理学会論文誌 (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.

著者

青江 順一 結束 雅雪

出版者

一般社団法人日本品質管理学会

雑誌

品質 (ISSN:03868230)

巻号頁・発行日

vol.37, no.3, pp.246-251, 2007-07-15

---

NTT Data corporation and Institute of Language Understanding developed "Nazuki". "Nazuki" means "brain" in an ancient Japanese word. It is a new product that can understand senses, topics and intentions from a given text. It differs from keyword based approaches in the current application systems. Innovation by "Nazuki" has just started, and "Nazuki" will be expanded in a wide range of fields. This report describes the history of techniques and business relating to "Nazuki"

著者

森田 和宏 望月久稔 山川 善弘 青江 順一

出版者

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

雑誌

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

巻号頁・発行日

vol.39, no.9, pp.2563-2571, 1998-09-15

---

自然言語辞書に構築される基本語彙は有限であるが,それら基本語の関係を定義することで,膨大な数の関係情報が作り出される.複合語,慣用表現,格関係などもこの関係情報の範疇に属し,これらを基本単語の共起情報と呼ぶ.共起情報を基本単語の並びとして格納すると,記憶効率が非常に悪くなるので,これら関係情報の効率的な記憶検索技法は重要な課題である.本論文では,基本単語からなる共起情報をトライ構造で効率的に記憶検索する手法を提案する.本手法では共起情報を構成する2つの基本単語を1つのトライに登録し,関係情報をトライの葉ノード間のリンク関数で定義する.共起情報の登録による記憶量の増加はこのリンク情報のみとなり,リンク情報もトライに格納する.本手法では,トライのアークを高速にたどる必要があるので,これをO(1)の計算量で実現するダブル配列法を適用する.この結果,共起情報の検索時間は,基本単語数や葉ノード間のリンク数に依存しない一定の計算量となった.約10万語の基本単語に対して,複合語,同音語判定の共起語,格構造辞書などの約100万の関係情報を構築した実験結果より,検索時間は1.2msと一定となること,また記憶量は従来法より1/3に圧縮できることが分かった.Collocational information is very useful for natural language processing systems and it includes compound words,cooccurrency words,verbs and the role of nouns in the case slot,and so on.Collocational information can be constructed by combining basic words infinitely,so it is important to propose a fast and compact structure representing them.This paper presents an efficient data structure by introducing a trie that can define the linkage among leaves.It enables us to decrease the amount of memory required for the same basic words.Theoretical observations show that the worst-case time complexity of retrieving collocational information is a constant,independent of the number of words and linkages.From the simulation results for collocational information,it is shown that the presented method is about 1/3 smaller than that of the competitive methods.

著者

林 淑隆 獅々堀正幹 伊与田 敦 津田 和彦 青江 順一

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.1994, no.104, pp.63-70, 1994-11-17

---

文献検索システムなどにおいて、キーワードをいかに効率良く、かつ正確に抽出するかは重要な課題である。本論文では、日本語文書においてキーワードとなることが多い複合語が、キーワード抽出の際に多大なマッチング処理を要することに着目し、複数キーワードのストリングパターンマッチングマシンの手法を応用した複合語キーワードの効率的な抽出法を提案する。本手法は、形態素解析部と複合語キーワード抽出マシンAC部、複合語キーワード候補マシンAC部からなる。14個の複合語文法構造と10個のキーワード評価ルールを定義し、26文書について実験評価を行った結果、形態素解析部を除く平均抽出速度は16.58ミリ秒、文書1KBあたり6.18ミリ秒の結果が得られ、本手法の有効性を確認した。また、抽出キーワードの選別で必要となる重なり語の抽出は、候補マシンACにより効率的に行えるので、利用者はこのマシンACに対する抽出ルールを決定することで、多種多様なキーワードを決定することが可能となる。Extracting keywords efficiently is an important task in text retrieval systems. In Japanese text, there are many compound words consisting some kinds of characters (Katakana, Kanji, etc.) and the text has no delimiter among words. Therefore, extracting keywords from such a text takes a lot of time. This paper presents a technique of detecting keywords from compound keywords by introducing a set of rules, which are conditions for keywords construction. A string pattern matching machine for a finit number of patterns is applied to matching of the rules and storing keyword candidates. From the simulation results for 26 Japanese text files that the algorithm presented has performed 6.2ms/KB.

著者

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

雑誌

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

著者

青江 順一

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:09135713)

巻号頁・発行日

vol.J71-D, no.9, pp.1592-1600, 1988-09-25

---

キー検索の応用において,あらかじめ基本的キー集合を構築しておき,後に使用者がキーを適宜追加して拡充させる場合が多々ある.このようなキー集合に対するキー検索法を準静的検索法と呼ぶ.本論文ではこの準静的検索法に適したディジタル検索法を確立するために,複数の静的なキーのパターンマッチングに利用されていたデータ構造(ダブル配列と呼ぶ)を拡張する.本拡張法では,ディジタル検索木において分岐なしに終端のノードまで連続する遷移列をダブル配列とは別のデータ構造TAILにストリングとして格納する.そして,このダブル配列とTAILを使ったディジタル検索の検索,追加,削除アルゴリズムを提案する.キーの長さをk;ダブル配列上で冗長に定義される状態番号数をm;入力記号の種類をeとするとき,検索,削除,追加の最悪の計算時間がそれぞれO(k),O(m),O(m・e+e2)となることを示す.また,1,000個以上のキー集合に対する種々の実験結果から,このmはダブル配列に定義されるべき全状態数に対して,1パーセント以下の小さな値となることがわかった.