配列を用いた反辞書の線形構築法

摘要

反辞書とは，一般的な辞書とは異なり，入力系列上で未出現の記号列を集めた辞書である.Crochemoreらが提案した反辞書法で用いられ，同期符号や不整脈検出などにも応用が提案されている.しかし，反辞書の構築は，計算量が線形とはいえ係数が大きく，膨大な記憶量と計算時間を必要とする.本論文では，より効率的に反辞書を構築できる，配列を用いる手法を提案した.計算機実験では，従来の接尾辞木を用いた手法と比較して，計算時間が約20分の1，記憶量が約2.5分の1であることがわかった.