文献

J-GLOBAL ID：201202256122939989   整理番号：12A1052362

系列二分決定グラフを操作するための豊富な演算体系の構築

Rich Operations for Manipulating Sequence Binary Decision Diagrams

著者 (4件)： 伝住周平 (北大 大学院情報科学研究科) ,  有村博紀 (北大 大学院情報科学研究科) ,  湊真一 (北大 大学院情報科学研究科) ,  湊真一 (JST-ERATO)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 93(COMP2012 12-25)  ページ： 9-16  発行年： 2012年06月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 大規模な文字列データを操作することは文字列処理の分野において重要な課題である。本稿では2009年にLoekitoらによって提案された系列二分決定グラフ(Sequence Binary Decision Diagram)と呼ばれるデータ構造を取り扱う。このデータ構造は多数の文字列を要素として含む文字列集合をコンパクトかつ一意に表現し,演算処理を効率良く行える。しかし,今まで提案された処理系では最小限の基本的な集合演算しか用意されていなかった。本稿では系列二分決定グラフの基本的な構造を示した上で,多様かつ高機能な文字列集合の演算体系を定義し,それらを実現する効率の良いアルゴリズムを提案する。(著者抄録)

シソーラス用語： *二分決定グラフ ,  *文字列 ,  *集合演算 ,  アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (22件)：

• AHO, Alfred V. The Design and Analysis of Computer Algorithms. 1974
• AKERS, S. B. Binary decision diagrams. IEEE Transactions on Computers, C. 1978, 27, 6, 509-516
• AOKI, Hiroshi. An efficient algorithm for constructing a sequence binary decision diagram representing a set of reversed sequences. Proceedings of the 2011 IEEE International Conference on Granular Computing (GrC'2011). 2011, 54-59
• BLUMER, Anselm. The smallest automaton recognizing the subwords of a text. Theoretical Computer Science. 1985, 40, 31-55
• BRYANT, Randal E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers. 1986, 35, 8, 677-691

タイトルに関連する用語 (4件)： 系列 ,  二分決定グラフ ,  体系 ,  構築