著者

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

出版者

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

雑誌

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

著者

蔵満 琢麻 望月 久稔

出版者

情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.2, no.2, pp.96-109, 2009-06-29

---

自然言語処理における辞書構造として,トライ法が広く用いられているが,日本語のように分かち書きされていない言語のテキストからキーワードを検出するためには,解析対象となるテキストのあらゆる位置から探索する必要がある.より高速に形態素解析を行うため,複数のキーワードをテキストから線形時間で検出する AC 法を用いる手法が提案されているが,AC 法はトライ法よりも使用する記憶領域が大きい.本論文では,AC マシンにおける遷移のうち,多分岐の節点における遷移をダブル配列に,1 方向分岐の節点における遷移をダブル配列と異なる配列にそれぞれ定義することで,照合時に必要な記憶領域を抑制し,高速性とコンパクト性をあわせ持つ AC マシンを実現する手法を提案する.日本語形態素 40 万語を登録した実験で,提案手法はトライを用いた辞書システム Darts とほぼ同等の記憶領域で対象テキストを 60~87% の時間で照合した.Trie structure is used widely, such as dictionary for natural language processing. However, it is not so effective using a trie structure for the morphological analysis of languages without explicit word boundaries like Japanese because we have to perform dictionary lookup for all possible substrings of the text. This paper proposes an efficient dictionary structure that is Aho-Corasick Machine using Double-array defining multi-way branch and different arrays defining oneway branch. Our experiments show that the matching time of the proposal machine decreased to about 60%-87% against other structures.

著者

蔵満 琢麻 松浦 寛生 望月久稔

出版者

情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.1, no.2, pp.1-14, 2008-09-30

---

パターン照合は文書処理やアンチウイルスなどのソフトウエアに用いられ,メモリ消費量が小さく,照合速度が高速なアルゴリズムが求められる.AC 法は複数パターンの照合に有効な手法で,AC マシンと呼ばれる一種の有限オートマトンを登録パターン集合から構築し,対象データを線形時間で照合する手法である.本論文では,ダブル配列を用いて遷移先関数を拡張した AC マシンを提案し,他手法との比較実験によりその有効性を示す.また提案マシンの応用例として,アンチウイルスソフト ClamAntiVirus に提案マシンを実装する.実験の結果,提案マシンは他手法よりも小さい記憶領域でデータ構造を実現し,対象データを高速に照合した.また,提案マシンを実装した ClamAntiVirus は,システムの稼働時間を 72%,照合時に必要な記憶領域を 70% にできることを示した.Pattern matching is used for word processing and software such as antivirus. It is important to high-speed response and compact memory. Aho-Corasick algorithm is an efficient multiple pattern matching algorithm. In this paper, we present a multiple pattern matching machine with a double-array structure. It has the transition function extended. And also, we implement the proposal machine to ClamAntiVirus as an applied example. Our experiments show that the operation time decreased to 72% and required storage area decreased to 70%.

著者

鵜久森 将隆 島野 達雄 望月 久稔

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第70回, no.人工知能と認知科学, pp.509-510, 2008-03-13

著者

中村 康正 望月久稔

出版者

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

雑誌

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

巻号頁・発行日

vol.2005, no.94, pp.117-122, 2005-09-30

---

トライ法は,自然言語処理システムの辞書情報構築を中心に広く用いられている.このトライ法のデータ構造として,青江らが提案したダブル配列法がある.ダブル配列法は高速性とコンパクト性をあわせもっており有効なデータ構造であるが,動的検索法に比べデータの更新処理が高速であるとはいえない.そこで現在では未使用要素を単方向リストとして連結する手法が知られているが,トライ木の希点を追加および削除する際に大きなコストを必要とする.そこで本論文では,未使用要素を双方向リストとして連結することにより追加処理を高速化し,さらに削除時間を抑えるアルゴリズムを提案する.10万語の辞書データに対する実験を行った結果,追加速度は単方向リストよりも約1.5倍,削除時間は未使用要素リストを用いない従来法と同等となることが判った.A trie is used widely, such as dictionary information construction of natural language processing system. As a data structure of trie, there is the double-array structure which Aoe and others proposed. A double-array structure is an efficient data structure combining fast access with compactness. However, the updating processing is not faster than other dynamic retrieval methods. Then, although the technique of connecting empty elements as linked list is known now, big cost is needed in the node of a trie tree is inserted and deleted. In this paper, we presents a fast insertion algorithm by connecting empty elements as doubly list and reduction algorithm of deletion time. From the simulation results for 100 thousands keys, it turned out that the presented method for insertion is about 1.5 times faster than the linked list method, and deletion time is equivalent to original method which is not used 1Inked list.