情報化社会の進展に伴って、情報検索の重要性はますます増大している。文字列の探索は文書処理にとってもっとも基本的な操作であるが、この効率はシステム全体の効率に影響するので、現在でも各所で研究が行なわれている。文字列検索手法としては、索引表をあらかじめ構築しておくインデックス検索手法が一般的であるが、この手法で任意の語彙の検索をしようとすると多大な記憶容量が必要となる。長尾・森の方法はインデックス検索手法と比べれば記憶容量が少なくて済むが、それでも元のテキストの2.5倍の付加的な記憶容量を必要とする。全文検索法のうち部分走査法は高速ではあるが、前処理時間と余分の記憶容量を必要とし、かつFalse Drop(誤検出)を防ぐには全走査法との併用が避けられない。すなわち、全文検索法の中の全走査法が文字列検索のもっとも基本的で柔軟な手法であると言うことができる。

　従来の全文検索アルゴリズムの中では、探索したい文字列が1つの場合、Boyer-Mooreの方法(BM法)がもっとも効率が良いと言われている。しかし、同時に複数個の文字列を探索したい場合には、BM法では文字列の数の繰り返しが必要となるため、途端に効率が劣化してしまう。複数個の文字列の同時探索の場合には効率の良い方法として、Aho-Corasickの方法(AC法)が知られている。この手法のprobe rate(テキスト1文字当たりの照合回数)は常に1になる。BM法の「パターンの右端からのテキストの逆向きの照合」というアイデアと、複数パターンの同時探索を可能とするためのAC法の「有限オートマトン上の状態遷移」という考え方を結合することによって、複数文字列を同時に効率良く検索できることを示す。

　提案するアルゴリズム(FAST法)では、図1のようにAC法とは逆向きにパターン照合機械(有限オートマトン)を作成する。(図1で破線はfailure動作を示す。)つまり、各パターンの右端を揃えてテキストの上に並べ右端から左へ照合を行なうわけである。どれかのパターンと照合が成功している間は図1のパターン照合機械上の状態遷移によってその情報を保持することができる。照合に失敗した場合には、検索漏れが生じない範囲でパターン群をテキスト上で移動させて、照合を再開すればよい。問題は、探索漏れを生じない移動距離をいかにして求めるかにある。

図1 FAST法におけるパターン照合機械

　このためには図2に示す2つの場合を考慮すればよいことがわかる。すなわちパターンとの照合に失敗したときそれまでの適合文字列と失敗したときの文字(ai)が別のパターンの部分文字列である場合(a)と、それまでの適合文字列の一部が別のパターンのsuffixになっている場合(b)である。パターン群の最大移動距離を厳密に定義すれば、(ただし、パターンの長さをmとし、パターンの長さをm²とする。)

　となる。

図2 パターン群シフト量の計算

　上述の動作を正確に実現するアルゴリズムを考案し、その正当性(停止性、健全性、完全性:パターンは漏れなく検出すること)を厳密に証明した。実は、FAST法はBM法と違って、失敗した位置までの情報を用いるので、パターンが1つだけの場合でもBM法よりも効率が良い。マルコフ過程を基に効率を求めるための連立方程式が導けることを示し、FAST法の効率について数学的に検討した。そして、文字種(q)がパターンの長さ(m),パターン数(k)に対して十分大きい(q≫mk)ときにはprobe rateが1/m+(m+1)k/2mqで近似できることを示した。

　FAST法の効率は文字種の数q、パターン長m、パターン数kの組み合わせによって大きく変化する。そこでq,m,kをいろいろに変えて、FAST法による文字列照合の実験を行なった。実験には一様乱数で発生された1Mバイトのテキストを3種、パターンを16種使用した。qとmの組み合わせに対して、kを変化させて効率(probe rate)を測定した。その結果、効率の推定式は実験結果と極めて一致することを確認した。近似式(1/m+(m+1)k/2mq)もq>mkの範囲ではよく一致することが分かった。probe rateが1となるkとmの関係をqをパラメータとして求めたところ、qがかなり小さい場合(例えばq＝5)でもパターン長が長くなるにつれAC法より有利となる領域が急速に拡大することがわかった。

　probe rateは必ずしも実際の計算時間を忠実に現しているわけではない。HorspoolはBM法で文字種が多い場合、照合失敗時に文字種による関数だけを用いることによってprobe rateが低下するのにかかわらず実際の計算時間の向上が図れることを示している。そこで、実際の計算時間に対してもAC法との比較を行ない、probe rateによるのとほとんど同様の結果が得られることを確認した。

　効率の推定式から多パターン時には効率が単調に減少しないという現象が起きることを発見し、それを実験によっても確認した。これは、ある場所から開始される照合回数はパターン数に対して単調増加となるが、パターン群のシフト量はそうならない(パターン数が増えると反対にシフト量が大きくなる場合がある)からで、この性質を使えばダミーパターンを追加することによって、効率を改善できる場合があることを示した。

　FAST法の欠点は他のアルゴリズムよりメモリーを余計に必要とすることである。文字種とパターンの長さとパターン数の積が小さい場合は問題にはならないが、JIS漢字コードなどの2バイトコードを対象にする場合には利用が困難になる場合も生じる。こういう場合、文字コードを2つの部分コードに分割し、主状態と中間状態という概念を取り入れて誤検出を防ぎ、1回の状態遷移を2回の連続した遷移に置き換える方法("文字符号分割による実現")でメモリを元の約倍に減らすことができることを示した。

　最近、土地利用区分図などのメッシュデータのコンピュータ利用や、デスクトップパブリッシングの発展に伴ない、文字列のような1次元パターンだけでなく、2次元パターンの高速な探索法も求められている。1次元パターンの探索アルゴリズムを2次元に拡張した例としては、BirdやZhu-TadaokaやBaeza-Yatesの仕事がある。FAST法は前述したように複数の1次元パターンを効率良く探索する方法である。これを2次元パターンの探索に拡張できれば、従来の方法よりもっと効率の良い探索が期待できる。

　図3のようなパターンを(2次元の)テキストから探索する問題を考える。PT1,PT2,PT3が3つの2次元のパターンである。このパターン探索に2次元FAST法では2段階の探索を行なう。

　まずパターンを列方向と行方向に分解して考える。すなわちパターンの各行を1次元パターンと見なしてパターン(行パターン)それぞれに固有の記号(行パターン記号:RP記号)を割り当てる。このとき、同じ行パターンには同じRP記号が付くようにする。このRP記号を列方向に並べたものを列パターンと呼ぶことにする。つまり、PT₁の列パターンは(X₁X₂X₃X₄X₅)^t、PT₂の列パターンは(X₆X₇X₈X₉X₇X₈)^t、PT₃の列パターンは(X₁₀X₄X₅)^tとなる。探索の第一段階では行パターンを(通常の)FAST法で探索する。この結果は配列mapに書き込んでおく。列パターンで最後尾となりうる行パターン(例ではX₅かX₈)が見つかれば、mapを対象に列方向にFAST法を用いて列パターンを探索する。列パターンが見つかったときに元の2次元パターンが存在していることがわかる。

図3 2次元パターンの一例

　列パターンのgoto関数の入力は行パターンの出力結果であり、これを用いて列パターン探索を行なうか、何行先にスキップするかを決定することができる。このように2次元FAST法では、行方向にも列方向にも照合の省略が起こるので、非常に効率の良いパターン探索が可能となる。このアルゴリズムは簡単にn次元パターンの探索に拡張することができる。すなわち、(k-1)次元のパターンの出力結果をk次元パターン探索の入力とし、1次元から探索を開始して、順次2、3、…、n次元のパターンを検出していけばよい。

　以上をまとめると、本論文の目的は任意の複数の文字列(パターン)を電子化されているデータから効率よく検索する手法を提供することにあった。効率の良い複数文字列の探索アルゴリズムを提案し、効率の推定、アルゴリズムの正当性の証明、実験による検証を行ない、さらに2次元パターン検索への拡張法について述べた。今後、本研究の概念を生かしながら、様々な情報検索の実際の応用の上で本アルゴリズムの利用を図っていきたいと考えている。

　本論文は「複数文字列の探索に関する研究」と題し、文字列処理やパターン検索でもっとも基本となる文字列の検索に関して、複数パターンの効率的なアルゴリズムであるAho-Corasickの方法のアイデアと、単一パターンでは最も効率が良いと言われているBoyer-Mooreの方法のアイデアを結合することによって、複数パターンに対しても効率的な検索が可能となること、さらにその方法が多次元パターン検索にも拡張可能であることを論じたもので、5章より成る。

　第1章は「序論」であり、文字列探索の重要性を述べるとともに、文字列探索手法のうち全文検索手法の全走査法と呼ばれる手法が最も利用価値が高いことを示している。すなわち、インデックス検索手法で任意の語彙の検索をしようとすると多大な記憶容量が必要となること、長尾・森の方法はインデックス検索手法と比べれば記憶容量が少なくて済むが、それでも元のテキストの2.5倍の付加的な記憶容量を必要とすること、部分走査法は前処理時間と付加的な記憶容量を必要とし、かつFalse Drop(誤検出)を防ぐには全走査法と併用せざるを得ず、全走査法が基本的であることを論じ、本研究の目的、必要性、意義を述べて論旨の展開を図っている。

　第2章は「複数文字列の探索手法」と題し、全文検索手法のアルゴリズムについて検討している。まず、従来のアルゴリズムのうち、素朴な方法、Knuth-Morris-Prattの方法、Boyer-Mooreの方法(BM法)、Aho-Corasick(AC法)について簡単に説明を行なった後、AC法とBM法のアイデアを結合することによって、複数パターンを効率良く検索できることを示している。すなわち、AC法の有限オートマトン上の状態遷移という考え方を取り入れて複数パターンの同時探索を可能とし、BM法の「パターンの右端からのテキストの逆向きの照合」というアイデアによって探索効率向上を図っている。提案した方法(FAST法)の考え方とアルゴリズムについても詳述し、他の複数パターン検索法よりも効率が良いことを示し、パターンが1つだけの場合でもBM法よりも効率が良いことを明らかにしている。

　第3章は「FAST法の性質」と題し、第2章で提案したFAST法の効率と正当性について理論的に検討している。すなわち、マルコフ過程を基に効率を求めるための連立方程式が導けることを示し、文字種(q)がパターンの長さ(m)、パターン数(k)に対して十分大きい(q>>mk)ときにはprobe rate(テキスト1文字当たりの照合回数)が1/m+(m+1)k/2mqで近似できることを示している。また、FAST法がAC法より有利となる領域を文字種をパラメータとし、パターン数とパターン長で示して、文字種が少ない場合でもパターン長が大きくなるとFAST法の有利な場合が急激に増えることを示している。アルゴリズムの正当性についても厳密に証明し、誤検出も検索漏れもなく確実に複数パターンを同時に検索できることを明らかにしている。検索実験を行い、probe rateの推定式と実験結果がよく一致すること、実験の探索時間もほぼprobe rateに比例することを示している。さらに多パターン時には探索効率が単調に減少しないという現象が起きることについても推定式と実験の両方から明らかにしている。FAST法の欠点は他の全文検索型アルゴリズムよりメモリーを余計に必要とすることである。文字種とパターンの長さとパターン数の積が小さい場合は問題にはならないが、JIS漢字コードなどの2バイトコードを対象にする場合にはFAST法の利用が困難になる場合も生じる。こういう場合でも、"文字符号分割による実現"などのメモリ節減手段を使うことによってFAST法を利用できることについても示している。

　第4章は、「FAST法の2次元パターン検索への拡張」と題し、2次元パターン探索の従来のアルゴリズムについて概観した後、パターンを列方向と行方向に分解し、行パターンと列パターンという概念を導入することで、FAST法を2次元パターン探索に拡張する方法について述べている。すなわち、2次元パターンを行毎に1次元パターン(行パターン)と見なし、各行パターンを1つの記号で表し、それを列方向に並べたものを(列方向の)1次元パターン(列パターン)と見なし、行パターンをFAST法で検索し、行パターンが検出されると列方向に列パターンをFAST法で検索する方法である。このアルゴリズムについて詳述し、実験によりBirdやZhu-TadaokaやBaeza-Yatesなどの従来手法より効率が良いことを示している。さらに同様な方法でFAST法を一般のn次元パターンの検索に拡張する方法についても示している。

　第5章は「結論」であり、本研究の成果を要約している。

　以上これを要するに、本論文は文字列処理やパターン検索の基礎技術として、Boyer-Mooreの方法とAho-Corasickの方法のアイデアを結合した新しい複数文字列の検索アルゴリズムを考案し、この方法の正当性を証明し、効率の良さを理論的、実験的に明らかにし、さらにn次元パターン検索への拡張法を述べたものであり、電子情報工学上貢献するところが少なくない。

　よって本論文は博士(工学)の学位請求論文として合格と認められる。