文字列探索アルゴリズム

本講義では,文字列処理の代表例である文字列検索のアルゴリズムについて紹介します.(教科書8章:)

1.文字列からの文字探索

線形探索を利用することで、実現可能です。



2文字列から文字列を探索する

2-1.単純法,力任せ法

プログラミングにおいては文字列の検索をすることがしばしばです.例えば,

  • Wordの文書の中で,あるキーワード(文字列)を検索する
  • ウェブページの中で,あるキーワード(文字列)を検 索する

といったように,文書(文字列)の中の文字列を探すことがよくあるでしょう.このアルゴリズムも基本的には,前回と同様に文字列に対する「線形 探索」で実現できます.違いは,探す対象が文字でなく文字列なので,1文字ずつ検索していくという点だけです.

例えば,"This is an apple"という文字列から "apple" という文字列を探してみることを考えます."This is an apple"という文字列は,下記のような1次元配列に格納されていると考えます.

T
h
i
s
i
s
a
n

a
p
p
l
e
.

探索の手順

  1. aを探す
  2. aが見つかったら,その位置の右隣がpであるか調べる.
  3. もしpであったらその右隣 がpであるか調べる(そうであれば,pple探し続ける)
  4. もし,違っていたら,またaを探す

例) 

aを前から探す....見つかる!
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

その右隣はpか?...NO!...またaを探す.
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

aを発見!
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

その右隣はpか?...YES!
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

その右隣はpか?...YES!
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

その右隣はlか?...YES!
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

その右隣はeか?...YES!
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

終了!



2-2.Boyer-Moore法

単純法より高速に行えるアルゴリズムの1つ.そこ考え方のポイントは2つ.

  • パターンの末尾からマッチングを図る
  • 不一致の場合,事前に設定した「移動ルール」に基づいて次の検索場所を決定 する

移動ルールの決定方法(スキップテーブルの作成)

パターン文字列(探したい文字列)の長さをnとする.1文字ずつ検査していき,パターンマッチングに失敗したときに,以下の点を考慮した移 動ルールを決める.

  • マッチング対象の文字がパターンにない文字の場合 ・・・ n文字移動する
  • マッチング対象の文字がパターンにあ る場合 ・・・  n-k-1文字移動する
本講義では教科書のプログラムに準拠し、簡略化して説明します。例えば「ABDG」というパターンについては以下のようなテーブルになります。

 A その他
 3

「ALFDW」であれば、以下のようになります。

 Aその他 
 4 3 2 1 5 5


ワードが重複する場合は、右端の数が優先されます。例えば、ABACの場合は、Aという数が重複していますが以下のようにします。

 A B A C
 3

              ↓

 A B A C
 11 

つまり実質的には、以下のテーブルになります。


 A B C その他
 1 4



BM法では,この考え方を前提にして検索効率を上げる工夫を取り入れていきます.

BMアルゴリズムの概要

配列txt(長さy)に対して,配列pat(長さx)の文字列があるかどうかの検索を行う

  1. まず,tt=x-1を着眼点とする.
  2. pt=x-1とする
  3. txt[tt]とpat[pt]を 比較し,同じであれば tt--,pt-- とし,比較を続ける
  4. 異なれば,移動ルール(スキップテーブル)にしたがって,着眼点を移動す る.(以降,2-4繰り返し)

着眼点というのは、現在比較している場所です。

「現在比較している場所から移動ルールに従って移動した位置に、パターン配列を移動させるということです。
この意味を十分理解しましょう。


例えば,"This is an apple"という文字列から "apple" という文字列を探してみることを考えます."This is an apple"という文字列は,下記のような1次元配列に格納されていると考えます.

T
h
i
s
i
s
a
n

a
p
p
l
e
.

探索の手順

スキップテーブルは以下のようになります。

 aその他 
 4 3→2 2 1 5


eを探す....





↓ 












 a p p l e            
T
h
i
s
i
s
a
n
a
p
p
l
e
.

違う(パターンにないので)のでカーソルを5つ移動.eかどうか?....

















T
h
i
s
i
s
a
n
a
p
p
l
e
.
      a p l e       

違うのでカーソルを5つ移動.eかどうか?....  

















T
h
i
s
i
s
a
n
a
p
p
l
e
.
           a p p l e  

違うのでカーソルを1つ移動(違うがlという文字がキーワードに存在するため).

eかどうか?....
















T
h
i
s
i
s
a
n
a
p
p
l
e
.
            a p p l e 

eであるので,その左がlかどうか...
















T
h
i
s
i
s
a
n
a
p
p
l
e
.

lであるので,その左がpかどうか...
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

pであるので,その左がpかどうか...
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

pであるので,その左がaかどうか...
















T
h
i
s
i
s
a
n

a
p
p
l
e
.

すべて対応したので検索成功.

Comments