(PDF:219KB)文字列検索

8 文字列検索
8.1 力まかせ探索 (brute force search)
例
Most professional programmers love junk food.
program
program
program
program
...
program
program
C 言語によるアルゴリズム
i=0; j=0;
do {
if a[i] == p[j]
then { i++, j++ }
else { i = i-j+2; j = 1 }
while ((j >= M) || (i >= N));
8.2 時間計算量 (time complexity)
アルゴリズムの性能
高速性、省メモリ、了解性
高速性
データの大きさ
N に対する計算時間 T (N ) の増え方を考慮
計算時間の見積もり
アルゴリズムの中核となる処理の回数
例) 文字列探索では、文字同士の比較回数
O
O
計算量のオーダー (ビッグオー)( notation)、ランダウ記号
例) ( 2 ) 「 の 2 乗のオーダー」
ON
O(f (N ))
N
c N
正の定数 、 0 が存在して、
N > N0 に対して、T (N ) cf (N )
多項式時間、指数時間、対数時間
8.3 力まかせ探索の高速化
クヌース・モリス・プラット法
O (N + M )
4
professional programmers love junk food.
program
4 文字目で失敗したときには、
program
ここまでパタンをずらして、次は 4 文字目とパタンの 1 文字目から
1 調べればよい。
ポイントは、失敗したときにパタンをどれだけ右にずらせるか？ということである。
4
professional programmers love junk food.
program -->
program
3 文字目までのずらし（1 文字分右へ）
3
1
program
2
program
1
2 文字目までのずらし（2 文字分右へ）
1 文字目までのずらし（3 文字分右へ）
1 文字目までずらせれば、非常によい。しかし、パタンの中に、同じ部分パタンが
出てくる場合にはこのようには行かない。
そのようなパタンの例として proproteins とすると、
7
proprogrammers love junk food.
proproteins
proproteins ここまでずらしてはいけない。
1
proproteins ここまでしかずらせない。
4
なぜならは、7 文字目で g と t とを比較をした段階では、そこから続く文字列が
rammers love junk food. であることは、まだ不明であり、4 文字目からの文字列が
proproteins を含んだ
proproproteins ...
である可能性があるからだ。実際に、その場合を考えると
7
proproproteins ...
proproteins
^
でも 7 文字目で失敗し、上と同じようにパタンの 1 文字目までずらすと
見落としてしまうので、4 文字目までだけずらして、
7
proproproteins ...
proproteins ×
1
proproteins ○
4
このように、文字不一致の場合に、どこまでパタンをずらせるかを調べて、探
索する方法がクヌース・モリス・プラット法である。
8.4 ラビン・カーブ法
ハッシュ関数というものを用いたラビン・カーブ法。
8.4.1 ハッシュ関数
例) 名前（キー）から内線番号を検索する電話帳
行
0
1
2
3
4
5
6
名前
ARAI
ITAO
OOZONO
KIMURA
TOMIYAMA
DOHI
HIGUCHI
内線番号
6490
6461
6490
6455
6454
6480
6449
ハッシュ関数とハッシュ値
例) キーの文字コードの和をある値 (S
り良い方法ではない)
= 10
とする) で割った余り (これはあま
h(ARAI)=(65 + 82 + 65 + 73) mod 10 = 285 mod 10 = 5
ハッシュ値を行番号とする電話帳
2
行
名前
0
1
2
3
4
5
6
7
8
9
{
ITAO
DOHI
HIGUCHI
OOZONO
ARAI
{
KIMURA
{
TOMIYAMA
内線番号
6461
6480
6449
6490
6490
6455
6454
テーブルの大きさは S
= 10。
データ追加時の衝突処理
衝突：新しいデータ (例：SUZUKI) に対する h = h(SUZUKI)=
に埋まっている時
衝突処理：衝突した時には、
1 行目がすで
(h + ci) mod S (i = 1; 2; 3; : : :) 番目の行があいて
いるかどうか探し、空いていれば、そこに挿入する。
= 3 とすると、1 + 1 2 3 = 4; 1 + 3 2 2 = 7 行目は埋まっているので、
1 + 3 2 3 = 10 = 0 mod 10 となり 0 行目に入れる。
例）c
行
0
1
2
3
4
5
6
7
8
9
名前
SUZUKI
ITAO 6481
DOHI
HIGUCHI
OOZONO
ARAI
{
KIMURA
{
TOMIYAMA
内線番号
6490
6480
6449
6460
6470
6455
6454
衝突の少ないハッシュ関数の設計が大事。S を次のように設定。
{ S を大きくする。
{ S は素数にする。
8.4.2 ハッシュ関数による文字列検索
長さ M の文字パターン p をテキスト a から検索する場合
{ パターン文字列のハッシュ関数値 hp
{ テキスト a の i 番目から長さ M の連続する部分文字列に対するハッシュ
関数値 hi
この両者をを比較。関数値が一致していることが文字列一致の必要条件。一致
しているときは、文字列を照合。
Most
h1 = h(Most
h2 = h(ost
h3 = h(st
h4 = h(t
professional programmers love junk food.
pr)
pro)
prof)
profe)
ハッシュ関数の漸化計算
3
M の文字列 c = c0c1 c2 :::cM 01 を d 進数 M 桁の数 x
と考え、それを大きな素数 q で割った余りをハッシュ値とする。
x = c0 dM 01 + c1dM 02 + ::: + cM 02d1 + cM 01 mod q
テキスト a の i 番目から長さ M の部分文字列 a[i::i + M 0 1] のハッシュ
{ 関数として、長さ
{
関数
{
{
hi = h(a[i::i + M 0 1]) = (aidM 01 + ai+1dM 02 + 1 1 1 + ai+M 01) mod q
(a[n::m] は文字列 a の第 n 番目から第 m 番目までの部分文字列を表す。)
ハッシュ関数 hi+1 を hi から計算する漸化式
hi+1 = h(a[i + 1::i + M ]) = (hi 0 aidM 01) 3 d + ai+M
C 言語によるアルゴリズム
/* Rabin-Karp Text Search */
#include <stdio.h>
#include <string.h>
#define q 1299689
#define d 128
void main(void){
char a[128] = "Precision Engineering is precise."; /* text */
char p[16] = "se.";
/* search string */
int N, M;
int h1, h2, dM, i;
N = strlen(a);
M = strlen(p);
}
dM=1; for(i=1;i<M;i++) dM = d*dM % q;
h1=0; for(i=0;i<M;i++) h1 = (h1*d + p[i]) % q;
h2=0; for(i=0;i<M;i++) h2 = (h2*d + a[i]) % q;
i = 0;
while (i <= (N-M)) {
if (h1 == h2)
if (!strncmp(p, &a[i], M)) break;
h2 = (h2 - a[i]*dM + d*q) % q;
/* d*q は剰余計算が正の範囲で行われるように加えてある */
h2 = (h2*d + a[i+M]) % q;
i++;
}
if (i <= N-M) printf("Found. %d %s\n", i, &a[i]);
else printf("Not found. %d\n",i);
4
8.5 パターン照合
8.5.1 正規表現 (regular expression)
文字列のパターンを指定して、それに合ったものを検索する (パターン照合)。
例) Unix のコマンド
foo.c など c で終わる名前のファイルの一覧
> ls *c
Unix
システムの辞書から行頭が a で行末が tion で終わる単語を探す。
> look . | grep '^a.*tion$'
ablution
abolition
absolution
absorption
abstention
acclamation
accreditation
...
正規表現：パターン照合を行うためのパターンを記述する言語
記号
意味
^
行頭
$
行末
.
任意の 1 文字 (ワイルドキャラクタ)
[chars]
かっこ内の文字のどれか
r*
r
についてゼロ回以上の繰り返し
例)
abc
abc
a.c
aac abc acc : : :
a*c
c ac aac aaac : : :
[abc]c
ac bc cc
8.5.2 オートマトン (automaton)
正規表現のパターン照合を行うには、オートマトンという考え方を使う。
オートマトン
決められた規則に従って、「状態 (state)」を遷移しながら処理を行うメカニズ
ム（状態機械）。特に、ここでは、外部からの入力によって、状態が変化する
ような仕組みを考える。
例) 自動販売機 10 円玉だけ入り、30 円でアメが 1 個出る。
10 円玉
入力:
出力:
アメ
状態:
投入された金額
初期状態:
オートマトンが最初に入力を受付ける状態
状態遷移 (state transition)
5
10
0
10
10
なし
10
20
なし
30
あめ
なし
10
図 1: 自動販売機を表すオートマトン
有向グラフ
オートマトンは図 1 のようなグラフ構造で表現。
状態を節、遷移を向きのついた辺 (有向辺)。辺には入力のラベルがつく。
有限 (nite) オートマトン (FA: Finite Automaton)
有限性：状態の数が有限個
決定性：入力に対して (停止も含めて) 唯一の遷移先が決まる。
非決定性：複数個ある。
8.5.3 FA によるパターン照合
FA：照合パターンに応じて FA を作る（作り方は後述）。
入力: 照合したい文字列を先頭から 1 文字ずつ入力
状態遷移: 初期状態から始めて、入力文字にしたがって遷移（入力があったら
必ず遷移しなければならない。遷移先がなければ停止。）
停止: 遷移できないとき、または、入力が尽きたとき
受理状態 (accept)：
（それまでの入力文字列に対して）パターン照合が行われた
ことを表す状態
受理：文字列が尽きたときに受理状態にあれば、その文字列は「受理された」
といい、照合が行われたことを表す。
却下 (reject): 受理状態に到達せずに停止したとき
例) abc を照合する FA
s0
a
b
s1
s2
c
s3
受理状態
初期状態
例) ab*c を照合する FA
s0
a
s1
c
s2
受理状態
初期状態
b
例) can で終わる文字列を受理する非決定性 FA
6
s0
c
a
s1
n
s2
s3
受理状態
Λ (全ての文字の集合)
入力 c に対して、s1 に遷移してもよいし、Λで s0 に遷移してもよいことに注意。
非決定性の場合の処理
複数の可能な遷移の内のどれが受理に至る遷移かは、文字列が尽きるまで分か
らないので、すべての可能な遷移を行ってみる必要がある。
例) 似て非なる決定性 FA
s0
c
a
s1
n
s2
s3
受理状態
Λ-c
Λ-a
Λ-n
ただし、3
0 c は、c 以外の全ての文字を表す。
「任意の正規表現に対して、それを受理する FA が存在する。」
パターン照合のプログラム
正規表現から、FA を生成し、それをシミュレーションすればよい。
8.5.4 正規表現から有限オートマトンの生成
簡略版正規表現
記号
文字
' 文字'
(P)
j
PQ
P Q
P*
意味
その文字自身
その文字自身 '(' (
"'
'
'*'
正規表現 P
正規表現 P と Q をつないだもの (連結, concatination)
P または Q (選択, union)
P の 0 回以上の繰り返し (閉包, closure)
!
!
!3
結合の優先度
3 > 連結 > 選択 j
例) ajb 3 c = (a)j(b 3 c) = (a)j((b3)c)
閉包
" 遷移
ε
s1
c
s2
c
s3
s4
状態 s1 に来たら、次の文字を読み込む前に、無条件に s2 へ遷移してもよいし、
遷移しなくてもよい。（非決定性となる。）" 遷移の前後の状態に、同じラベル
をもつ遷移がある場合に意味がある。逆に、ない場合は、この " 遷移は無意味。
遷移を削除して状態を統合可能。
7
例）a 3 bjac
a
s2
ε
b
s4
s1
a
c
s3
変換規則
正規表現からオートマトンへ変換するための基本規則
P:正規表現
N(P):それに対するオートマトン
規則(1)
文字c
規則(2)
連結 PQ
c
PQ
N(P),N(Q)
N(P)
N(Q)
ε
規則(3)
選択
P|Q
P|Q
N(P),N(Q)
N(P)
ε
ε
ε
ε
N(Q)
規則(4)
閉包
P*
P*
N(P)
ε
N(P)
ε
ε
8
具体例 ab 3 cjd
正規表現を結合の優先度に従って、木構造 (tree) に変換
ab*c|d
規則3 (viii)
ab*c
d
規則1 (vii)
規則2 (vi)
規則2(iv)
規則1(iii)
ab*
c
a
規則1 (v)
b* 規則4 (ii)
b 規則1 (i)
木構造に従って、ボトムアップに変換規則を適用し FA を構成してゆく。
(i) 規則(1)
b
b
(ii) 規則 (4)
b*
N(P)だと思って、規則 (4)の
これを規則(4)の
をこれで置き換える。
ε
N(P)
ε
b
ε
(iii) 規則(1)
a
a
9
(iv) 規則 2
PQ をそれぞれ、上の二つだと思って、規則 2 の N(P),N(Q) を置き換える。
ε
N(P)
ε
a
ε
b
ε
(v) 規則
(1) c
c
(vi) 規則
(2)
ε
ε
a
ε
N(P)
b
ε
c
ε
c
ε
(vii) 規則 (1)
d
d
(viii) 規則 (3)
ε
a
N(P)
b
ε
ε
ε
ε
d
ε
10
○ 簡略化
ε
ε
ε
ε
ε
a
c
b
ε
ε
ε
ε
ε
d
ε
ε
a
c
b
ε
ε
ε
ε
ε
d
c
x
○ 簡略化
c
ε
b
y
a
b
a
b
c
a
d
参考文献
アルゴリズム 第 2 巻 探索・文字列・計算幾何、R. セジウィック著、(野下、星、
佐藤、田口訳)、近代科学社、1992
アルゴリズムとデータ構造、石畑清著、岩波講座ソフトウェア科学 3、岩波書
店、1989
11