- 著者
-
松原 渉
篠原 歩
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.110, no.12, pp.39-45, 2010-04-15
移調を許したマッチングとは,与えられたテキストとパタンに対して,任意のオフセットを許した移調パタンの出現を発見する問題であり,例として音楽検索が挙げられる.本研究では,移調を一般に文字の置き換え関数としてとらえ,任意の置換が与えられたとき,すべてのパタンを検出する問題について取り組む.入力のテキストとパタンは,文法圧縮の一種である直線的プログラム(SLP)で与えられるものとし,文字列を陽に展開することなく処理を完了する効率の良いアルゴリズムを与える.