第25回 プログラミングについて 『文字検索（ワイルドカード）』
『文字検索（ワイルドカード）』
今回は文字検索について考えてみましょう。といってもここでは、ある文字列が別の文字列と一致するか否かを判断することに焦点をしぼります。
検索したい文字列をここでは検索文字列、検索される文字列を被検索文字列と呼ぶことにします。また文字列には２バイト文字は含まないこととします。
もっとも単純な文字列の検索は、検索文字列にワイルドカードなどの特別な文字を含まないものを検索する場合で、被検索文字列を先頭から１文字づつ調べていく方法です。いろいろと表現の方法はありますが、例えば次のようになります。
char *search(text,search)
char *text; /* 被検索文字列 */
char *search; /* 検索文字列 */
{
char *t,*s;
while(*text){
t=text;
s=search;
while(*t && *s){
if(*t!=*s)break;
t++;
s++;
}
if(!*t && !*s)return text;
text++;
}
return (char *)0;
}
少し変形して、それぞれの文字列の長さも考慮するようにしてループの回数を減らす方法も考えられますので工夫してみて下さい。被検索文字列が単純な文字列の場合にはＢｏｙｅｒ－Ｍｏｏｒｅ法といって効率の良いアルゴリズムがありますので書籍などで調べてみて下さい。
これで話が終わってしまうのではなく、実は今回はワイルドカードを使った文字列の検索について考えるのが本題です。通常ワイルドカードといえばＤＯＳのコマンドなどでディレクトリの内容を表示するときに使う？や＊の記号のことです。？は任意の１文字と一致し、＊は任意の複数文字（０文字以上）に一致することを表しています。そもそもワイルドカードや正規表現などといったものが考えられたのは、できる限り少ない検索文字列で多くの文字列を検索したいといった願望が根源になっています。
いま次のような検索文字列をワイルドカードを使って表現したとします。
abc?def
この表現では、abc という文字列が先頭にあって次の１文字はどんなものでもよく、その次に def がある文字列を意味しています。ここでもし abc??def という文字列を探したいときには検索文字列としてはワイルドカードは使えませんので、ワイルドカードとしての ? の文字の意味を通常の文字の意味として解釈させる方法が必要になります。ＦＯＲＴＲＡＮ流でいけば ? が連続していれば通常の文字として解釈するようにもできますし、Ｃ言語流でいけばバックスラッシュをその前に指定すれば通常の文字として解釈するようにもできます。これはあくまでも好みの問題かも知れません。
ＦＯＲＴＲＡＮ流では abc????def を abc??def と解釈、
Ｃ言語流では abc\?\?def を abc??def と解釈する。
通常、実際にワイルドカードを使って文字列の照合を行なうときにはこのように特別な解釈を行なわせるための文字が検索文字列に存在している可能性がありますので、この検索文字列を別の形式に整形しておきます。ここでは検索文字列をＣ言語流で表現す
るとし、１文字のワイルドカードを１（０ｘ０１）、０文字以上のワイルドカードを２
（０ｘ０２）として別の形式に置き換えることにし、その翻訳関数を作ってみましょう。
#define WILD_ONE 1
#define WILD_MANY 2
trans_wild(from,to)
char *from;
char *to;
{
while(*from){
if(*from=='\\'){ from++; *to++ = *from; }
else if(*from=='?' ){ *to++ = WILD_ONE; }
else if(*from=='*' ){ *to++ = WILD_MANY; }
else { *to++ = *from; }
from++;
}
*to='\0';
}
この例では \ 文字があったときには無条件に次の文字を通常文字として解釈していますが、実際には \ の文字の後に何も文字が指定されていないこともありますので、このチェックが必要です。また * 文字が連続しているときには２つ以上は意味がありませんので連続しているときには１つにしておいた方が照合する関数を作ときには楽になります。
最初の search の例に１文字のワイルドカードを扱えるように機能を追加してみましょう。定数 WILD_ONE と WILD_MANY は定義されているとします。
char *search(text,search)
char *text; /* 被検索文字列 */
char *search; /* 検索文字列 */
{
char *t,*s;
while(*text){
t=text;
s=search;
while(*t && *s){
if(*s!=WILD_ONE && *t!=*s)break;
t++;
s++;
}
if(!*t && !*s)return text;
text++;
}
return (char *)0;
}
以外と簡単に改修することができました。問題は０文字以上のワイルドカードです。
いま検索文字列を０文字以上のワイルドカードを使って次のように表現したとします。
abc*def
この表現では、
abc123def
abc123de123def
などが一致することは理解できるかと思います。次に、
abc*def*ghi
という検索文字列のときには、
abc123def123ghi
abc123de123def123gh123ghi
などが一致します。０文字以上のワイルドカードで文字列の照合を行なうときに面倒なのは、最初の abc*def の検索文字列で abc123de123def などの文字列を照合するときに 123 の後の de1 と def の照合で一致していないとあきらめないようにすることなのです。この場合の動作をわかりやすく表現すると、
検索文字列 被検索文字列
a a 一致した！
b b 一致した！
c c 一致した！
*d 1 d とは一致しないから次の文字を調べよう。
*d 2 d とは一致しないから次の文字を調べよう。
*d 3 d とは一致しないから次の文字を調べよう。
*d d 一致した！
e e 一致した！
f 1 一致ししていないからこれは違う！
といった具合です。本当に希望するのは、
検索文字列 被検索文字列
a a 一致した！
b b 一致した！
c c 一致した！
*d 1 d とは一致しないから次の文字を調べよう。
*d 2 d とは一致しないから次の文字を調べよう。
*d 3 d とは一致しないから次の文字を調べよう。
*d d 一致した！
e e 一致した！
f 1 一致ししていないからまた *d からやり直しだ。
*d 1 d とは一致しないから次の文字を調べよう。
*d 2 d とは一致しないから次の文字を調べよう。
*d 3 d とは一致しないから次の文字を調べよう。
*d d 一致した！
e e 一致した！
f f 一致した！ この被文字列はバッチリ一致する！
という動作です。また 検索文字列が abc*def*ghi のときでは *ghi の部分で一致していないからといって *def から照合を行なうと abc123de123def123gh123ghi が一致しなくなるのでどこから再照合を行なうかも大切な要素になります。
次に０文字以上に一致する検索機能をもった関数を考えてみますが、話を簡単にするために検索ではなく、被検索文字列の先頭から検索文字が一致するか否かを検査する関数を作ってみましょう。ただし検索文字列が abc のとき被検索文字列が abcdefg でもabc の部分が一致しているので一致するとします。
ここでも定数 WILD_ONE と WILD_MANY は定義されているとします。まじめに作ると結構面倒なものになってしまうのですが、再帰呼びだしを使うと非常にスッキリと表現できます。
match_wild(wild,string)
char *wild;
char *string;
{
while(*string && *wild){
if(*wild==WILD_MANY){
if(match_wild(wild+1,string))return 1;
}
else{
if(*wild!=WILD_ONE && *string!=*wild)break;
wild++;
}
string++;
}
if(!*wild)return 1;
if(*wild==WILD_MANY && !*(wild+1))return 1;
return 0;
}
もし被検索文字列全体と一致するようにするには、この関数の最後の部分を次のようにします。
if(!*wild && !*string)return 1;
if(*wild=='*' && !*(wild+1) && !*string)return 1;
return 0;
この例では０文字以上のワイルドカードのときには、それ以降の文字の照合は自分自身にゆだねることで非常に単純明快に表現しています。もし再帰呼びだしを使用しないとなれば、先程にも説明したように検索文字列の再照合の位置を把握するようにしたり、再照合が可能か否かのチェックが必要になりますので、かなり複雑になってしまいます（実際に私もその方法で以前作ったことがありますが、正常に動作するようになるまで苦労しました）。
多分ワイルドカードでの照合の関数を作らなければならないときには、参考になると思いますので記憶にとどめておいて下さい。今後、正規表現についても触れる予定ですので楽しみにしていて下さい。
それではまた次回。
