C#による アルゴリズムとデータ構造

8.文字列処理
8.1 C#の文字列
C#では, “ABCD”のように文字列を2重引用符で挟んで指定
します。ASCIIコード体系のとき,以下のような内部形式となり
ます。
0 1 0 0 0 0 0 1
文字 ‘A’
0
0
文字 ‘B’
0 1 0 0 0 0 1 1
文字 ‘C’
0
1
0
0
0
1
0
0
文字 ‘D’
0
0
0
0
0
0
0
0
ナル文字
‘\0’
ナル文字
A B C D \0
1
0
0
0
0
1
文字列の内部形式を
listBox1に表示するプログラム
文字列の内部表現
private string binaryScaleString(long V)
{
long VV=V;string S="";
for(int i=0;i<16;i++, VV /=2 )
S = ((VV % 2 ==0) ? "0" : "1") + S;
return S;
}
private void strDump(string S)
{
listBox1.Items.Clear();
for(int i=0;i<S.Length;i++)
{
long V=(long)S[i];
string X = V.ToString("X");
string B = binaryScaleString(V);
if(X.Length==2) X = " " + X;
listBox1.Items.Add(S[i].ToString() + "\t" + X + "\t" + B);
}
}
文字列の内部表現 Clickイベントハンドラ実行結果
private void button1_Click(object sender, System.EventArgs e)
{
strDump("文字列string");
}
配列による文字列
文字リテラルは,本来,
その内容を自由に書き換えて使うものではありません。
ですから,C#では,stringはRead Only とみなされており,
陽に代入は許されません.
自由に入れ替える処理を記述するためには,
次のようにchar型の配列として宣言します。
なお,char型配列をstringとして扱うには,
以下の例のようにCharToString関数を使います(C, C++との違い)。
private void button2_Click(object sender, System.EventArgs e)
{
char[] CH =new char[10];
CH[0]='文';CH[1]='字';CH[2]='列';
CH[3]='s' ;CH[4]='t' ;CH[5]='r' ;
CH[6]=’i' ;CH[7]='n' ;CH[8]='g';CH[9]='\0';
strDump(CharToString(CH));
}
8.2 文字列の基本操作
(1)文字列の長さ
文字列の最後はナル文字です。
ですから,ナル文字を検索することで
文字列の長さを求めることができます。。
ナル文字
A B C D \0
private int str_len(char[] ch)
{
int i=0;
while(ch[i] != '\0')i++;
return i;
}
配列の大きさと文字列の長さ
文字列を格納するための配列のサイズと
文字列の長さは必ずしも一致しません。
配列の大きさと文字列の長さの違いを
以下のプログラムで確認してみましょう。
(C++,C の strlen 関数は,次のように,文字列.Lengthと書きます)
private void button3_Click(object sender, System.EventArgs e)
{
char[] CH =new char[12];
CH[0]='文';CH[1]='字';CH[2]='列';
CH[3]='s' ;CH[4]='t' ;CH[5]='r' ;
CH[6]='i'; CH[7]='n' ;CH[8]='g';CH[9]='\0';
MessageBox.Show(CH.Length.ToString());
// 配列のサイズ=12
MessageBox.Show(str_len(CH).ToString()); // 文字列の長さ=9
MessageBox.Show(CharToString(CH).Length.ToString());
// 文字列の長さ=9
}
(2)文字列からの文字の探索
文字列から任意の文字を探索する手続きは次のようになります。
private int 文字探索(string X, char C)
{
int i=0;
while (i < X.Length && X[i] !=C)i++;
if(i < X.Length) return i;
return -1;
}
文字探索のメソッド(Cのstrchr,strrchrに相当)
(a) String.IndexOf
特定の文字が文字列内で最初に出現する位置を返却。先頭は0,指定した文字が見
つからない場合,–1 を返す。大文字と小文字は区別される。
string S = ”Peter Piper picked a peck";
MessageBox.Show(S.IndexOf(’p'));
この例では8 と表示される。
(b)String.LastIndexOf
指定した文字列が文字列内で最後に出現する位置を返却。先頭は0,指定した文字
が見つからない場合,-1を返す。大文字と小文字は区別される。
string S = ”Peter Piper picked a peck";
MessageBox.Show(S.LastIndexOf(’p'));
この例では21 と表示される。
文字列S1,S2を比較し,
(3)文字列の比較
S1が大きければ正の整数値,
小さければ負の整数値,
等しければ0を返却する関数の処理を以下に示します。
private int str_cmp(string S1, string S2)
{
int i=0;
while(i<S1.Length && i<S2.Length && S1[i]==S2[i]) i++;
if
(i== S1.Length && i== S2.Length) return 0;
else if(I < S1.Length && I < S2.Length)
return ((int)S1[i]-(int)S2[i]);
else if(i<S1.Length) return 1;
else return -1;
}
private void button5_Click(object sender, System.EventArgs e)
{
string S1
= textBox1.Text;
string S2
= textBox2.Text;
MessageBox.Show(str_cmp(S1,S2).ToString());
}
C#の文字列比較メソッド
文字列比較のメソッドは用意されていますので,
通常は,わざわざプログラムを作る必要はありません。
たとえば,String.Compare メソッドでは,
2 つの文字列を比較します。
このメソッドでは,以下の結果を返却します。
(a) 引数1が引数2より大きいとき,正の整数
(b) 引数1が引数2より小さいとき,負の整数
(c) 引数1と引数2が等しいとき0
この他,CompareOrdinal ,CompareTo,Equals,StartsWith , EndsWith
などがあります。詳しくはC#のマニュアルやヘルプを参照してください。
8.3 文字列探索
(1)文字列探索とは
文字列探索(string searching)とは,
ある文字列の中に,別の文字列が含まれているかどうか,
含まれている場合は,その位置を示すこと。
探索される側の文字列:テキスト(text)
探し出すための文字列:パターン(pattern)
(2)力まかせ法(単純法,素朴法)
力まかせ法(brute forth method)の手順
(a)
(b)
(c)
0
P
1
E
2
T
3
E
4
R
P
I
P
\0
3文字目が一致しない
0
P
1
E
2
T
3
E
4
R
P
I
P
\0
1
E
2
T
3
E
4
R
5
P
P
I
P
\0
0
P
5
P
5
P
6
I
6
I
7
P
7
P
8
E
9
R
10
\0
8
E
9
R
10
\0
9
R
10
\0
1文字目が一致しない
6
I
7
P
8
E
1文字目が一致しない
力まかせ法の手順2
力まかせ法(brute forth method)の手順
(d)
(e)
(f)
0
P
0
P
0
P
1
E
1
E
1
E
2
T
2
T
2
T
3
E
4
R
5
P
6
I
P
I
P
\0
3
E
4
R
5
P
6
I
7
P
P
I
P
\0
4
R
5
P
6
I
7
P
8
E
P
I
P
\0
3
E
7
P
8
E
9
R
10
\0
1文字目が一致しない
8
E
9
R
10
\0
1文字目が一致しない
9
R
10
\0
全文字一致
力まかせ法のプログラム
private int 力まかせ法(string 文字列, string パターン)
{
int P1=0; int P2=0;
while(P1<文字列.Length && P2<パターン.Length)
{
if(文字列[P1] == パターン[P2]){ P1++; P2++;}
else
{ P1 = P1 - P2 + 1; P2 = 0; }
}
if(P2==パターン.Length) return(P1 - P2);
return -1;
}
private void button2_Click(object sender, System.EventArgs e)
{
string 文字列
= textBox1.Text;
string パターン = textBox2.Text;
label5.Text=力まかせ法(文字列, パターン).ToString();
}
(3)KMP法
力まかせ法では,不一致文字があると,
パターンを移動して再びパターンの先頭から照合する。
それまでの照合結果が捨てられる。
パターンの特徴を活かし,そこまでの照合結果を有効活用する
D. E. KnuthとV. R. Pratt,J. H. Morris が
ほぼ同時期に考案した方法。
Knuth-Pratt-Morris 法,略してKMP法と呼ばれる。
KMP法の考え方
[例]パターン移動の際,何文字目から照合を再開するかを事前に決めておく。
(a)
(b)
(c)
0
P
1
S
2
E
3
A
4
S
5
E
6
R
7
P
S
E
A
S
E
R
\0
1文字目が一致しない
0
P
1
S
2
E
3
A
4
S
5
E
6
D
7
P
8
E
S
E
A
S
E
R
\0
6文字目が一致しない
1
S
2
E
3
A
4
S
5
E
6
R
7
P
8
E
9
R
10
\0
S
E
A
S
E
R
\0
0
P
(3文字目から照合)
8
E
9
R
9
R
10
\0
10
\0
照合再開位置(1)
(a) 1文字目で不一致
0
P
1
?
2
?
3
?
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
1文字目が一致しない
1文字目から照合を開始
0
P
1
?
2
?
3
?
4
?
5
?
6
?
7
?
S
E
A
S
E
R
\0
8
?
9
?
10
?
照合再開位置(2)
(b) 2文字目で不一致
0
S
1
X
2
?
3
?
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
2文字目が一致しない
1文字ずらして
1文字目から照合を開始
0
S
1
X
2
?
3
?
4
?
5
?
6
?
7
?
S
E
A
S
E
R
\0
8
?
9
?
10
?
照合再開位置(3)
(c) 3文字目で不一致
0
S
1
E
2
X
3
?
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
3文字目が一致しない
2文字ずらして
1文字目から照合を開始
0
S
1
E
2
X
3
?
4
?
5
?
6
?
7
?
8
?
S
E
A
S
E
R
\0
9
?
10
?
照合再開位置(4)
(d) 4文字目で不一致
0
S
1
E
2
A
3
X
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
4文字目が一致しない
3文字ずらして
1文字目から照合を開始
0
S
1
E
2
A
3
X
4
?
5
?
6
?
7
?
8
?
9
?
S
E
A
S
E
R
\0
10
?
照合再開位置(5)
(e) 5文字目で不一致
0
S
1
E
2
A
3
S
4
X
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
5文字目が一致しない
3文字ずらして
2文字目から照合を開始
0
S
1
E
2
A
3
S
4
X
5
?
6
?
7
?
8
?
9
?
S
E
A
S
E
R
\0
10
?
照合再開位置(6)
(f) 6文字目で不一致
0
S
1
E
2
A
3
S
4
E
5
X
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
6文字目が一致しない
3文字ずらして
3文字目から照合を開始
0
S
1
E
2
A
3
S
4
E
5
X
6
?
7
?
8
?
9
?
S
E
A
S
E
R
\0
10
?
照合再開位置の設定(1)
パターン同士を1文字ずつずらしながら照合する
S
S
S
E
A
S
E
R
S
E
A
S
E
E
A
S
E
R
S
E
A
S
E
A
S
E
R
S
E
A
R
E
S
S
E
A
S
E
R
0
0
S
E
A
S
E
R
0
0
0
S
E
A
S
E
R
0
0
0
1
R
E
R
照合再開位置の設定(2)
パターン同士を1文字ずつずらしながら照合する
S
S
E
E
A
A
S
E
R
S
E
A
S
E
S
E
R
S
E
A
S
E
R
0
0
0
1
2
S
E
R
S
E
A
S
E
R
0
0
0
1
2
0
R
S
E
A
KMP法のプログラム(1)
private int KMP法(string 文字列, string パターン)
{
int P1=1; int P2=0; int[] skip=new int[256];
skip[P1]=0;
while (P1<パターン.Length)
{
if(パターン[P1]==パターン[P2]) skip[++P1]=++P2;
else if(P2==0) skip[++P1]=P2;
else P2=skip[P2];
}
P1=P2=0;
while(P1<文字列.Length && P2<パターン.Length)
{
if(文字列[P1] == パターン[P2]){ P1++; P2++;}
else if(P2 == 0) P1++;
else P2=skip[P2];
}
if(P2==パターン.Length) return(P1 - P2);
return -1;
}
KMP法のプログラム(2)
private void button3_Click(object sender, System.EventArgs e)
{
string 文字列
= textBox1.Text;
string パターン = textBox2.Text;
label5.Text=KMP法(文字列, パターン).ToString();
}
(4)BM法
照合をパターンの末尾から行う方法。
一致しない文字を見つけた場合,
事前に用意した表により移動量を決める。
R. S. BoyerとJ. S. Moore によるアルゴリズム
Boyer-Moore 法,略してBM法と呼ばれる。
BM法の考え方(1)
[例]パターンの後から照合し,ずらしてみよう。
(a)
(b)
(c)
(d)
0
P
1
E
2
T
3
E
4
R
5
P
6
I
P
I
P
R
\0
P
I
P
R
\0
P
I
P
R
\0
P
I
P
R
7
P
8
E
9
R
10
\0
不一致
1文字ずらしても不一致
2文字ずらしても不一致
\0
パターン中にない文字をテキスト中に見つけたら,
そこまでの文字は,すべてスキップできる。
3文字ずらしても不一致
BM法の考え方(2)
[例]一致している場合,1文字前に戻る
0
P
1
E
2
T
3
E
4
R
(a)
P
I
P
E
\0
(b)
P
I
P
E
\0
P
I
P
E
\0
P
I
P
E
(c)
(d)
3文字ずれることになる。
5
P
6
I
7
P
8
E
9
R
10
\0
一致
不一致
1文字ずらしても不一致
\0
2文字ずらしても不一致
BM法の考え方(3)
[例]一致している場合
0
P
5
P
6
I
7
P
8
E
9
R
10
\0
(a)
P
I
P
E
\0
一致
(b)
P
I
P
E
\0
一致
(c)
P
I
P
E
\0
一致
P
I
P
E
\0
一致
(d)
1
E
2
T
3
E
4
R
スキップテーブル
(各文字に出会ったときずらす量)
最初,以下の表を作成しておく。
パターン文字数をN,パターンの最後に出現する位置の添え字をKとする。
■パターン中にない場合 N
■パターン中にある場合 N-K-1
K
0
P
1
I
2
P
3
E
2
1
0
(Eのときは,一致の処理)
A
B
C
D
E
F
G
H
I
J
K
L
M
4
4
4
4
0
4
4
4
2
4
4
4
4
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
4
4
1
4
4
4
4
4
4
4
4
4
4
BM法のプログラム(1)
private int BM法(string 文字列, string パターン)
{
int P1=0; int P2=0;
int txtLen =
文字列.Length;
int patLen = パターン.Length;
int[] skip=new int[char.MaxValue+1];
for(P1 =0; P1 <= char.MaxValue; P1++) skip[P1]=patLen;
for(P1 =0; P1 <= patLen - 1;P1++) skip[パターン[P1]]=patLen - P1 -1;
// このとき,P1= patLen-1であることに注意
while(P1<文字列.Length)
{
P2=patLen - 1;
while(文字列[P1] == パターン[P2])
{
if (P2==0) return(P1);
P1--; P2--;
}
P1 += skip[文字列[P1]];
}
return -1;
}
BM法のプログラム(2)
private void button4_Click(object sender, System.EventArgs e)
{
string 文字列
= textBox1.Text;
string パターン = textBox2.Text;
label5.Text=BM法(文字列, パターン).ToString();
}