- 著者
-
伝住 周平
有村 博紀
定兼 邦彦
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers (ISSN:09135693)
- 巻号頁・発行日
- vol.97, no.12, pp.1080-1085, 2014-12
大規模な文字列データの操作は,文字列処理の分野で最も重要な課題の一つである.本稿では,文字列集合をコンパクトに圧縮し様々な操作を可能とする系列二分決定グラフ(系列BDD,SeqBDD)を紹介し,関連するパターン照合技術について紹介する.この系列BDDは,文字列データに拡張したZDDの一種であるが,同時に,従来から自然言語処理や文字列処理分野で研究されてきたトライや,有限オートマトン,接尾辞グラフなどのテキスト索引のためのデータ構造とも密接な関連を持つ.これら既存のデータ構造との関係や,近年発展が著しい簡潔データ構造と関連した話題についても述べる.