文献

J-GLOBAL ID：201402259827069758   整理番号：14A1464297

「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野-2.文字列の圧縮列挙索引技術とパターン照合技術

著者 (3件)： 伝住周平 (北大 大学院情報科学研究科) ,  有村博紀 (北大 大学院情報科学研究科) ,  定兼邦彦 (東大 大学院情報理工学系研究科)
資料名： 電子情報通信学会誌  (Journal of the Institute of Electronics, Information and Communication Engineers)
巻： 97  号： 12  ページ： 1080-1085  発行年： 2014年12月01日 
JST資料番号： F0019A  ISSN： 0913-5693  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 大規模な文字列データの操作は,文字列処理の分野で最も重要な課題の一つである。本稿では,文字列集合をコンパクトに圧縮し様々な操作を可能とする系列二分決定グラフ(系列BDD,SeqBDD)を紹介し,関連するパターン照合技術について紹介する。この系列BDDは,文字列データに拡張したZDDの一種であるが,同時に,従来から自然言語処理や文字列処理分野で研究されてきたトライや,有限オートマトン,接尾辞グラフなどのテキスト索引のためのデータ構造とも密接な関連を持つ。これら既存のデータ構造との関係や,近年発展が著しい簡潔データ構造と関連した話題についても述べる。(著者抄録)

シソーラス用語： *文字列 ,  *データ圧縮 ,  二分決定グラフ ,  パターンマッチング ,  *索引 ,  データ構造
準シソーラス用語： *パターン照合 ,  *系列二分決定グラフ

分類 (2件)： パターン認識  (JE07000S) ,  グラフ理論基礎  (IA02020S)

引用文献 (16件)：

• Wikipedia, “Size of wikipedia,“ July 2014, http://en.wikipedia.org/
• D. Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge, 1997.
• M. Crochemore, C. Hancart, and T. Lecroq, Algorithms on Strings, Cambridge, 2007.
• C.L. Lucchesi and T. Kowaltowski, “Applications of finite automata representing large vocabularies,“ Softw.-Pract. Exp., vol. 23, no. 1, pp. 15-30, 1993.
• A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M.T. Chen, and J.I. Seiferas, “The smallest automaton recognizing the subwords of a text,“ Theor. Comput. Sci., vol. 40, pp. 31-55, 1985.

タイトルに関連する用語 (9件)： フカ ,  シギ ,  アルゴリズム ,  二分決定グラフ ,  離散構造 ,  応用 ,  文字列 ,  索引 ,  パターン照合