ほんとにときどきですが、*や?を使用したワイルドカード検索をしたくなるときってありませんか？
JavaやPerlなどですと、正規表現があるのでそれで代替できますね。
C++などでもboostでは正規表現があるのでそれで代替できます。
ですので、ここではお遊びでワイルドカード検索を作ってみようと思います
（文字コードの指定やマッチした文字列の取得など、ちょっと高機能を目指します！）
【ワイルドカード検索のシリーズ記事】
このシリーズでは以下のような記事を予定しています。
この記事は一番目の「ワイルドカード検索をする」です。
・ワイルドカード検索をする
・WildSearchを"ac*c"などの文字列から自動で作成する
・部分一致のワイルドカード検索をする
・*や?にマッチした文字列をコールバックを使用して取得する
・Antパスマッチを実装する
※このブログのコードについて記述した以下の記事も先だってお読みください。
・サンプルについて
【おまけ】
この記事はシリーズになっています。
記事1つに1つのソースが記載されています。
記事1つずつコードをコピーし、コンパイルして動作を見ながら読んでもらえると
うれしいです。
ですが、コードを何回もコピーしていくのが大変な人のために以下のような
ズルをできるものを用意しました。
・ワイルドカード検索すべてのコードをまとめたもの
もしもコピーが大変でしたらこれをご利用ください。
【前座】
実はワイルドカード検索は作るまでもなく、googleで検索すると以下のようなリンクが見つかります。
便利な世の中です
ワイルドだろぉ～
（半年後には死語になっていそうですね・・・（笑）ちなみに自分はマイルドに生きたいです）
ワイルドカード('*', '?')を使って文字列を比較する
おそらくこれでうまくいくと思います。
ですが、このブログはC++のブログですので、せっかくなのでクラスを使って実装してみましょう
ワイルドカード検索をクラスで実装することを通して、
クラスを使用するとコード量が多くなっても分かりやすく、機能拡張もしやすいことを見ていけたらと思います。
【ロジック】
クラスで実装すると言っても、やり方は上記のリンクとほぼ同じです。
ワイルドカードでのポイントは*と?の検索の仕方です。
まずは、検索文字（例："ab*5*c"）をワイルドカードと文字列に分解します。
＜分解＞
・"ab"
・"*"
・"5"
・"*"
・"c"
＜検索対象文字列の例＞
"ab1234567c"
次に検索の仕方を考えます。
まず、分解した検索文字の先頭"ab"が、検索対象文字列"ab1234567c"の先頭にマッチするかを
調べます。いきなりマッチしますね。
"ab"にマッチしたらそれ以降の（"*5*c"）がマッチすればよさそうです。
つまり、検索対象文字列の先頭を"1"の位置にずらして"1234567c"と、"*5*c"がマッチするかという検索をします。
今度は、"*5*c"をどうやってマッチしたとみなすのかが問題になります。
これも簡単で、"1234567c"が"5*c"とマッチするかを調べます。
マッチしないので、検索対象文字列の位置を1文字ずらしてマッチするかを調べます。
つまり、"234567c"が"5*c"とマッチするかを調べます。
こうしていくと、5回目くらいでマッチすることが分かります。
こうして、分解したワイルドカードを1つずつ順番に調べていけば良いことが分かるかと思います。
このやり方をクラスにするというお遊びです。
【クラスの簡単な説明】
もっと短くしようとしたのですが、結局コードが長くなってしまったので
最初にクラスの説明を書いておこうと思います。
登場するクラスはたったの3種類です。
コードは長いですが、このうちのどれを表しているのかだけ意識していれば
それほど難しくないかと思います。
＜登場するクラス＞
・ワイルドが見つかったときに呼ばれるコールバッククラス
・検索対象文字列を表すクラス
・分解したワイルドカード検索を表すクラス
※コールバッククラスは今回の記事では活躍しません。
では前置きが長くなりましたが、サンプルを見ていきましょう。
サンプルでは、"ab*c"というワイルドカードマッチを行っています。
ちなみに以前の記事のサンプルも使用して、文字コードも考慮した作りになっています。
【サンプル】
先立って、以下のコードをコピーして作っておいてください。
・code.hpp、code.cppファイル
・MCharIterator.hpp、MCharIterator.cppファイル
【出力】
pattern: abc, true
pattern: abdddc, true
pattern: ac, false
pattern: abcd, false
--------------------------------
Process exited with return value 0
【説明】
一応、パターンマッチが正しく行われているようですね。
まずmainを見てみましょう。
どうやってワイルドカードの"ab*c"を指定しているのでしょうね。
見てみると、予想したのと違う記述が見えますよね
＜再掲＞
実はこれがワイルドカード"ab*c"の表現です。
コード量は多いですが、"ab", "*", "c",終端文字 の順番になっていて
直観的には理解しやすいと思います。
つまり、1つのクラスが1つの分解したワイルドカードの表現になっています。
ここではクラスを使うと、直観とコード上の表現が合うことを見てもらうために
わざとこのようなサンプルにしました
。
でももし、"ab*c"という文字列から上記のWildSearchを作ることができれば
手間が減りそうです。
これは以降の記事で見ていきます。
＜WildSearchクラスについて＞
このクラスがワイルド検索の主役です。
簡単に説明しておきます。
WildSearchクラスはワイルドカード検索用の仮想関数search()を持っていて
派生クラスがその実装を行っています。
このやり方は、こちらも参照ください。
コンストラクタの引数ですが、以下のものがあります。
const int num ⇒番号をつけられるようになっています
const WildSearch* next ⇒次のワイルド検索クラスを設定します
const MCharVector& exclude ⇒*,?で除外する文字を指定します
※番号はクラスの実体を識別するためにつけていますが、今回のサンプルでは
役に立ちません。番号はコールバッククラスに渡されます。
excludeは、ワイルドカード*,?で除外する文字を指定します。
例えば"\n"を指定すれば、改行が*や?にマッチしなくなります。
＜SearchPointerクラスについて＞
検索対象文字列を設定してワイルドカードクラスに渡すためのクラスです。
文字コードやコールバックも指定できます。
文字の終端位置を各ワイルドカードクラスで知る必要があるのですが、
毎回strlenなどで調べると遅くなので、このクラス内に保持しています。
【まとめと次の記事へのフリ】
慣れてしまえばこのやり方でもコードが書けないこともないと思います。
このように、ワイルドカードに限らずクラスを使うと複雑な表現も理解しやすいものになります。
もちろん、最初のリンクのコードを使用する方がコード量は少ないですが、
おそらくワイルドカードなので偶然あそこまでコード量が少なくなったと思います。
これがもっと複雑なものであればコード量がもっと多かったと思います。
また、機能拡張などを行う場合に、コードを入れた時に動作が予想しずらいです。
クラスを使うとその中で処理が閉じるのでコードを追記しやすいし、影響が予想しやすくなります。
ですので、このようなクラスを作ることも設計の検討に入れると面白いと思います
。
この後の記事では以下のようなものを予定しています。
・ワイルドカード検索をする
・WildSearchを"ac*c"などの文字列から自動で作成する
・部分一致のワイルドカード検索をする
・*や?にマッチした文字列をコールバックを使用して取得する
・Antパスマッチを実装する
・おまけ：ワイルドカード検索すべてのコードをまとめたもの
ご興味あればぜひ！
またまた長い記事になってしまいすみませんでした。
飽きずに読めま・・・・、せんでしたよね？やっぱり。
でもお付き合いいただきありがとうございました。
JavaやPerlなどですと、正規表現があるのでそれで代替できますね。
C++などでもboostでは正規表現があるのでそれで代替できます。
ですので、ここではお遊びでワイルドカード検索を作ってみようと思います
（文字コードの指定やマッチした文字列の取得など、ちょっと高機能を目指します！）
【ワイルドカード検索のシリーズ記事】
このシリーズでは以下のような記事を予定しています。
この記事は一番目の「ワイルドカード検索をする」です。
・ワイルドカード検索をする
・WildSearchを"ac*c"などの文字列から自動で作成する
・部分一致のワイルドカード検索をする
・*や?にマッチした文字列をコールバックを使用して取得する
・Antパスマッチを実装する
※このブログのコードについて記述した以下の記事も先だってお読みください。
・サンプルについて
【おまけ】
この記事はシリーズになっています。
記事1つに1つのソースが記載されています。
記事1つずつコードをコピーし、コンパイルして動作を見ながら読んでもらえると
うれしいです。
ですが、コードを何回もコピーしていくのが大変な人のために以下のような
ズルをできるものを用意しました。
・ワイルドカード検索すべてのコードをまとめたもの
もしもコピーが大変でしたらこれをご利用ください。
【前座】
実はワイルドカード検索は作るまでもなく、googleで検索すると以下のようなリンクが見つかります。
便利な世の中です
ワイルドだろぉ～
（半年後には死語になっていそうですね・・・（笑）ちなみに自分はマイルドに生きたいです）
ワイルドカード('*', '?')を使って文字列を比較する
おそらくこれでうまくいくと思います。
ですが、このブログはC++のブログですので、せっかくなのでクラスを使って実装してみましょう
ワイルドカード検索をクラスで実装することを通して、
クラスを使用するとコード量が多くなっても分かりやすく、機能拡張もしやすいことを見ていけたらと思います。
【ロジック】
クラスで実装すると言っても、やり方は上記のリンクとほぼ同じです。
ワイルドカードでのポイントは*と?の検索の仕方です。
まずは、検索文字（例："ab*5*c"）をワイルドカードと文字列に分解します。
＜分解＞
・"ab"
・"*"
・"5"
・"*"
・"c"
＜検索対象文字列の例＞
"ab1234567c"
次に検索の仕方を考えます。
まず、分解した検索文字の先頭"ab"が、検索対象文字列"ab1234567c"の先頭にマッチするかを
調べます。いきなりマッチしますね。
"ab"にマッチしたらそれ以降の（"*5*c"）がマッチすればよさそうです。
つまり、検索対象文字列の先頭を"1"の位置にずらして"1234567c"と、"*5*c"がマッチするかという検索をします。
今度は、"*5*c"をどうやってマッチしたとみなすのかが問題になります。
これも簡単で、"1234567c"が"5*c"とマッチするかを調べます。
マッチしないので、検索対象文字列の位置を1文字ずらしてマッチするかを調べます。
つまり、"234567c"が"5*c"とマッチするかを調べます。
こうしていくと、5回目くらいでマッチすることが分かります。
こうして、分解したワイルドカードを1つずつ順番に調べていけば良いことが分かるかと思います。
このやり方をクラスにするというお遊びです。
【クラスの簡単な説明】
もっと短くしようとしたのですが、結局コードが長くなってしまったので
最初にクラスの説明を書いておこうと思います。
登場するクラスはたったの3種類です。
コードは長いですが、このうちのどれを表しているのかだけ意識していれば
それほど難しくないかと思います。
＜登場するクラス＞
・ワイルドが見つかったときに呼ばれるコールバッククラス
・検索対象文字列を表すクラス
・分解したワイルドカード検索を表すクラス
※コールバッククラスは今回の記事では活躍しません。
では前置きが長くなりましたが、サンプルを見ていきましょう。
サンプルでは、"ab*c"というワイルドカードマッチを行っています。
ちなみに以前の記事のサンプルも使用して、文字コードも考慮した作りになっています。
【サンプル】
先立って、以下のコードをコピーして作っておいてください。
・code.hpp、code.cppファイル
・MCharIterator.hpp、MCharIterator.cppファイル
#include <iostream>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <boost/utility.hpp>
#include <boost/scoped_ptr.hpp>
#include "code.hpp"
namespace nana{
//検索コールバッククラス------------------------------------------------
///や?にマッチした時にコールバックされる基底クラス。
class MatchCallback{
public:
virtual ~MatchCallback(){};
///
virtual void send(const int num, const char* pos, const int len){};
};
/**
<pre>
検索対象文字の開始位置と、現在の位置、終端位置を保持するホルダークラス。
また、何か見つかったときに報告ができるコールバッククラスも保持する。
</pre>
*/
struct SearchPointer{
public:
/**
コンストラクタ
@param str [in]検査対象文字列
@param charSet [in]文字コード
@param callback [in]コールバック (deleteは各自で行うこと)
*/
SearchPointer(const char* str, const CharSet* pcharSet, MatchCallback* pcallback =NULL)
: startPos(str), curPos(str), endPos(str + strlen(str))
, callback(pcallback), charSet(pcharSet)
{
if(callback == NULL) this->callback=&dummyMatchCallback;
};
///マッチした時のコールバック
MatchCallback* callback;
///現在の位置
const char* curPos;
///開始位置
const char* const startPos;
///終端位置
const char* const endPos;
///文字コード
const CharSet* const charSet;
///コールバックがNULLのときに代入する
static MatchCallback dummyMatchCallback;
};
///文字の配列
typedef vector<FixedMChar> MCharVector;
//-------------------------------------------------
//ワイルド検索クラス
//-------------------------------------------------
namespace wild{
///配列内に存在するか？
inline const bool exists(const MCharVector& vec, const MChar& mchar){
if(vec.empty()) return false;
return find(vec.begin(), vec.end(), mchar) != vec. end();
};
/**
<pre>
ワイルドカードの検索基底クラス。
</pre>
@note 代入は不可
*/
class WildSearch : noncopyable{
public:
WildSearch(const int& num, const WildSearch* next, const int& kind)
: m_num(num), m_pwildSearch(next), m_kind(kind) {};
virtual ~WildSearch(){};
///検索する。見つかった場合true。
virtual const bool search(SearchPointer& p) const =0;
const WildSearch& next() const { return *m_pwildSearch; };
const int& num() const { return m_num; };
const int& kind() const { return m_kind; };
protected:
///検索と通知(検索に成功すると通知する）
const bool nextSearchAndSend(SearchPointer& p, const char* start, const char* cur, const int size) const{
p.curPos = start;
if(!this->next().search(p)) return false;
p.callback->send(this->num(), cur, size);
return true;
};
private:
///次の検索
scoped_ptr<const WildSearch> m_pwildSearch;
///ワイルドの番号
const int m_num;
///検索種別
const int m_kind;
};
///文字列の終端を検索するクラス。
class TerminatorSearch : public WildSearch{
public:
enum{NUM=-2, KIND=5};
TerminatorSearch()
: WildSearch(NUM, NULL, KIND) {};
///
virtual const bool search(SearchPointer& p) const{
//終了位置ならtrue
if(p.curPos >= p.endPos){
p.callback->send(this->num(), p.curPos, 0);
return true;
}
return false;
};
};
///アスタリスクの検索クラス
class AstaSearch : public WildSearch{
public:
enum{KIND=1};
///
AstaSearch(const int& num, const WildSearch* next, const MCharVector& exclude)
: m_exclude(exclude), WildSearch(num, next, KIND) {};
///
virtual const bool search(SearchPointer& p) const{
const char* cur = p.curPos;
const char* calcEndPos = p.endPos;
//検索開始
MChar i(p.curPos, p.charSet);
for(; i.pos() < calcEndPos; ++i){
//除外される文字だった場合
if(exists(m_exclude, i)){
return this->nextSearchAndSend(p, i.pos(), cur, i.pos() - cur);
}
//現在の位置から次の検索を行う
if(this->nextSearchAndSend(p, i.pos(), cur, i.pos() - cur)){
return true;
}
}
return false;
};
private:
const MCharVector m_exclude;
};
///?の検索クラス
class QuestionSearch : public WildSearch{
public:
enum{KIND=2};
//
QuestionSearch(const int num, const WildSearch* next, const MCharVector& exclude)
: m_exclude(exclude), WildSearch(num, next, KIND) {};
virtual ~QuestionSearch(){}
//
const bool search(SearchPointer& p) const{
const char* cur = p.curPos;
MChar m(cur, p.charSet);
const char* next_pos = cur+m.size();
if(next_pos > p.endPos) return false;
//除外される文字だった場合
if(exists(m_exclude, m)){
return false;
}
//次の文字以降が一致するか？
return this->nextSearchAndSend(p, next_pos, cur, m.size());
};
private:
const MCharVector m_exclude;
};
///固定文字列の検索クラス
class OnlyStrSearch : public WildSearch{
public:
enum{NUM=-3, KIND=3};
OnlyStrSearch(const int num, const string& str, const WildSearch* next)
: m_str(str), WildSearch(num, next, KIND) { };
///
const bool search(SearchPointer& p) const{
const char* cur = p.curPos;
if(cur > p.endPos - m_str.size()) return false;
//文字列が一致するか？
if(strncmp(p.curPos, m_str.data(), m_str.size()) ==0){
//次の検索を行う
return this->nextSearchAndSend(p, cur + m_str.size(), cur, m_str.size());
}
return false;
};
private:
const string m_str;
};
}; //namespace wild{
}; //namesapce nana{
//使用サンプルコード開始-------------------------------------
using namespace nana::wild;
using namespace nana;
///static変数の初期化
MatchCallback nana::SearchPointer::dummyMatchCallback;
//ワイルド検索
void search(const scoped_ptr<WildSearch>& pattern, const char* str){
SearchPointer p(str, getCharSet("sjis"));
cout << "pattern: " << str << ", ";
if(pattern->search(p)){
cout << "true" << endl;
}else{
cout << "false" << endl;
}
}
//------------------------------
int main(int argc, char *argv[]) {
MCharVector excludeVec;
//"ab*c"
scoped_ptr<WildSearch> pattern(
new OnlyStrSearch(-3, string("ab"), //ab
new AstaSearch(1, //*
new OnlyStrSearch(-3, string("c"), new TerminatorSearch()) //c
,excludeVec
)
)
);
//テスト
search(pattern, "abc");
search(pattern, "abdddc");
search(pattern, "ac");
search(pattern, "abcd");
system("PAUSE");
return EXIT_SUCCESS;
};
【出力】
pattern: abc, true
pattern: abdddc, true
pattern: ac, false
pattern: abcd, false
--------------------------------
Process exited with return value 0
【説明】
一応、パターンマッチが正しく行われているようですね。
まずmainを見てみましょう。
どうやってワイルドカードの"ab*c"を指定しているのでしょうね。
見てみると、予想したのと違う記述が見えますよね
＜再掲＞
//"ab*c"
scoped_ptr<WildSearch> pattern(
new OnlyStrSearch(-3, string("ab"), //ab
new AstaSearch(1, //*
new OnlyStrSearch(-3, string("c"), new TerminatorSearch()) //c
,excludeVec
)
)
);
実はこれがワイルドカード"ab*c"の表現です。
コード量は多いですが、"ab", "*", "c",終端文字 の順番になっていて
直観的には理解しやすいと思います。
つまり、1つのクラスが1つの分解したワイルドカードの表現になっています。
ここではクラスを使うと、直観とコード上の表現が合うことを見てもらうために
わざとこのようなサンプルにしました
。でももし、"ab*c"という文字列から上記のWildSearchを作ることができれば
手間が減りそうです。
これは以降の記事で見ていきます。
＜WildSearchクラスについて＞
このクラスがワイルド検索の主役です。
簡単に説明しておきます。
WildSearchクラスはワイルドカード検索用の仮想関数search()を持っていて
派生クラスがその実装を行っています。
このやり方は、こちらも参照ください。
コンストラクタの引数ですが、以下のものがあります。
const int num ⇒番号をつけられるようになっています
const WildSearch* next ⇒次のワイルド検索クラスを設定します
const MCharVector& exclude ⇒*,?で除外する文字を指定します
※番号はクラスの実体を識別するためにつけていますが、今回のサンプルでは
役に立ちません。番号はコールバッククラスに渡されます。
excludeは、ワイルドカード*,?で除外する文字を指定します。
例えば"\n"を指定すれば、改行が*や?にマッチしなくなります。
＜SearchPointerクラスについて＞
検索対象文字列を設定してワイルドカードクラスに渡すためのクラスです。
文字コードやコールバックも指定できます。
文字の終端位置を各ワイルドカードクラスで知る必要があるのですが、
毎回strlenなどで調べると遅くなので、このクラス内に保持しています。
【まとめと次の記事へのフリ】
慣れてしまえばこのやり方でもコードが書けないこともないと思います。
このように、ワイルドカードに限らずクラスを使うと複雑な表現も理解しやすいものになります。
もちろん、最初のリンクのコードを使用する方がコード量は少ないですが、
おそらくワイルドカードなので偶然あそこまでコード量が少なくなったと思います。
これがもっと複雑なものであればコード量がもっと多かったと思います。
また、機能拡張などを行う場合に、コードを入れた時に動作が予想しずらいです。
クラスを使うとその中で処理が閉じるのでコードを追記しやすいし、影響が予想しやすくなります。
ですので、このようなクラスを作ることも設計の検討に入れると面白いと思います
。この後の記事では以下のようなものを予定しています。
・ワイルドカード検索をする
・WildSearchを"ac*c"などの文字列から自動で作成する
・部分一致のワイルドカード検索をする
・*や?にマッチした文字列をコールバックを使用して取得する
・Antパスマッチを実装する
・おまけ：ワイルドカード検索すべてのコードをまとめたもの
ご興味あればぜひ！
またまた長い記事になってしまいすみませんでした。
飽きずに読めま・・・・、せんでしたよね？やっぱり。
でもお付き合いいただきありがとうございました。