著者

成澤 和志 稲永 俊介 坂内 英夫 竹田 正幸

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.24, pp.63-70, 2007-04-19

被引用文献数

1

---

本論文では,Blumerらによって提案された同値関係による同値類を計算する問題を考える.Blumerらはコンパクト有向無閉路文字列グラフ(CDAWG)と呼ばれる索引構造を定義するために同値類を利用した.同値類は本質的に等しく出現する冗長な部分文字列を集めた集合であるため,テキスト解析において有用である.本論文では,接尾辞配列を用いて同値類を計算するアルゴリズムを提案する.提案アルゴリズムでは,接尾辞木および接尾辞リンク木の巡回を模倣するため接尾辞配列の他に2つの補助配列を使用するが,これら以外のデータ構造を必要としない.このアルゴリズムは入力文字列に対して,線形時間および線形領域で動作する.本論文では,提案アルゴリズムと接尾辞木およびコンパクト有向無閉路文字列を用いたアルゴリズムとの計算時間・計算領域を計算機実験によって比較する.