Download presentation
Presentation is loading. Please wait.
1
８．文字列処理 ８．１ Ｃ＃の文字列 Ｃ＃では， “ABCD”のように文字列を２重引用符で挟んで指定します。ASCIIコード体系のとき，以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \0 1 1 1 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’
2
文字列の内部表現 文字列の内部形式を 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); 文字列の内部表現
3
文字列の内部表現 Clickイベントハンドラ実行結果
private void button1_Click(object sender, System.EventArgs e) { strDump("文字列string"); }
4
配列による文字列 文字リテラルは，本来， その内容を自由に書き換えて使うものではありません。
ですから，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)); }
5
８．２ 文字列の基本操作 （１）文字列の長さ 文字列の最後はナル文字です。 ですから，ナル文字を検索することで
８．２ 文字列の基本操作 （１）文字列の長さ 文字列の最後はナル文字です。 ですから，ナル文字を検索することで 文字列の長さを求めることができます。。 ナル文字 A B C D \0 private int str_len(char[] ch) { int i=0; while(ch[i] != '\0')i++; return i; }
6
配列の大きさと文字列の長さ 文字列を格納するための配列のサイズと 文字列の長さは必ずしも一致しません。 配列の大きさと文字列の長さの違いを
以下のプログラムで確認してみましょう。 （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 }
7
（２）文字列からの文字の探索 文字列から任意の文字を探索する手続きは次のようになります。
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; }
8
文字探索のメソッド（Ｃのｓｔｒｃｈｒ，ｓｔｒｒｃｈｒに相当）
(a) String．IndexOf 特定の文字が文字列内で最初に出現する位置を返却。先頭は0，指定した文字が見 つからない場合，–1 を返す。大文字と小文字は区別される。 string S = ”Peter Piper picked a peck"; MessageBox.Show(S.IndexOf(’p')); この例では8 と表示される。 （ｂ）String.LastIndexOf 指定した文字列が文字列内で最後に出現する位置を返却。先頭は0，指定した文字 が見つからない場合，-1を返す。大文字と小文字は区別される。 MessageBox.Show(S.LastIndexOf(’p')); この例では21 と表示される。
9
（３）文字列の比較 文字列S1,S2を比較し， 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());
10
Ｃ＃の文字列比較メソッド 文字列比較のメソッドは用意されていますので， 通常は，わざわざプログラムを作る必要はありません。
たとえば，String.Compare メソッドでは， 2 つの文字列を比較します。 このメソッドでは，以下の結果を返却します。 (a) 引数１が引数２より大きいとき，正の整数 (b) 引数１が引数２より小さいとき，負の整数 (c) 引数１と引数２が等しいとき０ この他，CompareOrdinal ，CompareTo，Equals，StartsWith ， EndsWith などがあります。詳しくはＣ＃のマニュアルやヘルプを参照してください。
11
８．３ 文字列探索 （１）文字列探索とは 文字列探索（string searching）とは，
８．３ 文字列探索 （１）文字列探索とは 文字列探索（string searching）とは， ある文字列の中に，別の文字列が含まれているかどうか， 含まれている場合は，その位置を示すこと。 探索される側の文字列：テキスト（text） 探し出すための文字列：パターン（pattern）
12
（２）力まかせ法（単純法，素朴法） 力まかせ法（brute forth method）の手順 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10 (a) P E T E R P I P E R \0 P I P \0 ３文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (b) P E T E R P I P E R \0 P I P \0 １文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (c) P E T E R P I P E R \0 P I P \0 １文字目が一致しない
13
力まかせ法の手順２ 力まかせ法（brute forth method）の手順 1 2 3 4 5 6 7 8 9 10 P E T E R
1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (d) P I P \0 １文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (e) P E T E R P I P E R \0 P I P \0 １文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (f) P E T E R P I P E R \0 P I P \0 全文字一致
14
力まかせ法のプログラム 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();
15
（３）ＫＭＰ法 力まかせ法では，不一致文字があると， パターンを移動して再びパターンの先頭から照合する。 それまでの照合結果が捨てられる。
パターンの特徴を活かし，そこまでの照合結果を有効活用する D. E. KnuthとV. R. Pratt，J. H. Morris が ほぼ同時期に考案した方法。 Knuth-Pratt-Morris 法，略してＫＭＰ法と呼ばれる。
16
KMP法の考え方 ［例］パターン移動の際，何文字目から照合を再開するかを事前に決めておく。 1 2 3 4 5 6 7 8 9 10 (a)
1 2 3 4 5 6 7 8 9 10 (a) P S E A S E R P E R \0 S E A S E R \0 1文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (b) P S E A S E D P E R \0 S E A S E R \0 6文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (c) P S E A S E R P E R \0 （３文字目から照合） S E A S E R \0
17
照合再開位置（１） (a) １文字目で不一致 1 2 3 4 5 6 7 8 9 10 P ? ? ? ? ? ? ? ? ? ? S E
1 2 3 4 5 6 7 8 9 10 P ? ? ? ? ? ? ? ? ? ? S E A S E R \0 1文字目が一致しない 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 P ? ? ? ? ? ? ? ? ? ? S E A S E R \0
18
照合再開位置（２） (b) ２文字目で不一致 1 2 3 4 5 6 7 8 9 10 S X ? ? ? ? ? ? ? ? ? S E
1 2 3 4 5 6 7 8 9 10 S X ? ? ? ? ? ? ? ? ? S E A S E R \0 ２文字目が一致しない １文字ずらして 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S X ? ? ? ? ? ? ? ? ? S E A S E R \0
19
照合再開位置（３） (c) ３文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E X ? ? ? ? ? ? ? ? S E
1 2 3 4 5 6 7 8 9 10 S E X ? ? ? ? ? ? ? ? S E A S E R \0 ３文字目が一致しない ２文字ずらして 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E X ? ? ? ? ? ? ? ? S E A S E R \0
20
照合再開位置（４） (d) ４文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E A X ? ? ? ? ? ? ? S E
1 2 3 4 5 6 7 8 9 10 S E A X ? ? ? ? ? ? ? S E A S E R \0 ４文字目が一致しない ３文字ずらして 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E A X ? ? ? ? ? ? ? S E A S E R \0
21
照合再開位置（５） (e) ５文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E A S X ? ? ? ? ? ? S E
1 2 3 4 5 6 7 8 9 10 S E A S X ? ? ? ? ? ? S E A S E R \0 ５文字目が一致しない ３文字ずらして ２文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E A S X ? ? ? ? ? ? S E A S E R \0
22
照合再開位置（６） (f) ６文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E A S E X ? ? ? ? ? S E
1 2 3 4 5 6 7 8 9 10 S E A S E X ? ? ? ? ? S E A S E R \0 ６文字目が一致しない ３文字ずらして ３文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E A S E X ? ? ? ? ? S E A S E R \0
23
照合再開位置の設定（１） パターン同士を１文字ずつずらしながら照合する S E A S E R S E A S E R S E A S E
０ ０ S E A S E R S E A S E R S E A S E R ０ ０ ０ S E A S E R S E A S E R S E A S E R ０ ０ ０ １
24
照合再開位置の設定（２） パターン同士を１文字ずつずらしながら照合する S E A S E R S E A S E R S E A S E
０ ０ ０ １ ２ S E A S E R S E A S E R S E A S E R ０ ０ ０ １ ２ ０
25
KMP法のプログラム（１） 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; }
26
ＫＭＰ法のプログラム（２） private void button3_Click(object sender, System.EventArgs e) { string 文字列 = textBox1.Text; string パターン = textBox2.Text; label5.Text=KMP法(文字列, パターン).ToString(); }
27
（４）ＢＭ法 照合をパターンの末尾から行う方法。 一致しない文字を見つけた場合， 事前に用意した表により移動量を決める。
R. S. BoyerとJ. S. Moore によるアルゴリズム Boyer-Moore 法，略してＢＭ法と呼ばれる。
28
BM法の考え方（１） ［例］パターンの後から照合し，ずらしてみよう。 1 2 3 4 5 6 7 8 9 10 P E T E R P I
1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) P I P R \0 不一致 (b) P I P R \0 １文字ずらしても不一致 (c) P I P R \0 ２文字ずらしても不一致 (d) P I P R \0 ３文字ずらしても不一致 パターン中にない文字をテキスト中に見つけたら， そこまでの文字は，すべてスキップできる。
29
BM法の考え方（２） ［例］一致している場合，１文字前に戻る 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E
1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) P I P E \0 一致 (b) P I P E \0 不一致 (c) P I P E \0 １文字ずらしても不一致 (d) P I P E \0 ２文字ずらしても不一致 ３文字ずれることになる。
30
BM法の考え方（３） ［例］一致している場合 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a)
1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) P I P E \0 一致 P I P E \0 (b) 一致 P I P E \0 (c) 一致 P I P E \0 一致 (d)
31
スキップテーブル （各文字に出会ったときずらす量）
最初，以下の表を作成しておく。 パターン文字数をN，パターンの最後に出現する位置の添え字をＫとする。 ■パターン中にない場合 Ｎ ■パターン中にある場合 Ｎ－Ｋ－１ K 1 2 3 P I P E 2 1 （Eのときは，一致の処理） A B C D E F G H I J K L M 4 4 4 4 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
32
BM法のプログラム（１） 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;
33
BM法のプログラム（2） private void button4_Click(object sender, System.EventArgs e) { string 文字列 = textBox1.Text; string パターン = textBox2.Text; label5.Text=BM法(文字列, パターン).ToString(); }
Similar presentations
