著者

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

出版者

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

雑誌

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

著者

大野将樹 岡村亮一 獅々堀正幹 沼尾雅之

出版者

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

雑誌

研究報告音楽情報科学(MUS)

巻号頁・発行日

vol.2013, no.35, pp.1-6, 2013-08-24

---

本稿では,音楽的・音響的に違和感の少ないメドレー曲を自動的に生成する手法を提案する.メドレー曲を構成する楽曲断片間の連結の妥当性に関する指標として,局所的接続と大局的接続がある.本研究では,局所的接続と大局的接続に対する個人の嗜好をシステムに反映することによって,違和感のないメドレーを生成する.7 段階評価による被験者実験により,パーソナライズを実施しなかった場合のメドレー曲は 3.74,提案手法は 5.02 のスコアが得られ,個人の嗜好を反映した提案手法の有効性が示された.

著者

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

出版者

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

雑誌

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