C#ではワイルドカードを使用して文字列検索をするためのクラスが無いようなので作ってみました。 次のようにして使うことができます。
var m = new WildCardMatcher("test_*.html");
if(m.IsMatch(filename) )
{
なんたら
}
使用できるワイルドカードの記号は次の2つです。
- ? : 何でもいいので1文字。
- * : 長さ不問の文字列。長さ0でもよい。
コードはこんな風になりました。
- データURIスキームでのコード配布。 特定のブラウザでのみダウンロード可。 拡張子zipで保存してください。 → WildCardMatcher.zip
- データURIスキームについての説明はこちら → 前の投稿「色んなデータをデータURIスキームで埋め込んでみる」
// WildCardMatcher.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Text.RegularExpressions;
namespace WildCardMatcherTest
{
// ◆?と*のワイルドカードを使った文字列のマッチングを行う。
// エスケープ文字はないので?と*を検出することはできない。
// ◆コマンドプロンプトのワイルドカードとの違いは以下の通り。
// ・?は必ず1文字必要。
// (コマンドプロンプトのワイルドカードは、末尾が?の場合文字列が途切れていてもマッチする。)
// ◆パターンを設定したインスタンスをあらかじめ用意して
// ループ内などでIsMatchしたときのみ正規表現より高速に動作する可能性がある。
// (パターンの設定時に正規表現を使用しているので、
// こういう使い方をしない場合はこのクラスではなく正規表現を使った方がよい。)
// ◆スレッドアンセーフ。
// ◆不正なUTF-8シーケンスに関してはノーチェック。
// 普通は気にしなくてもよいが、厳密さが必要な場合はあらかじめstring.Normalizeした
// 文字列を使用すること。
// (現在の.net frameworkの仕様ではstringの内部はUSC-2である。
// このクラスでは内部的にUSC-2からUTF-8への変換をして文字列の比較をしている。
// 今の仕様のままなら、USC-2からUTF-8への変換では不正なシーケンスは
// 生成されないので考慮しなくてもいい。
// しかし、万が一string内部の型が何らかの事情でUTF-8に変更された場合は
// セキュリティホールになりうる。
// string内部の型がUTF-8の場合は、呼び出し側で不正なシーケンスを
// 除去しなければならない。)
public class WildCardMatcher
{
private static readonly Part PartSkip1 = new Part("?");
private static readonly Part PartSkipCharacters = new Part("*");
private Part[] _parts;
public WildCardMatcher()
{
}
public WildCardMatcher(string pattern)
{
Pattern = pattern;
}
private string _pattern;
public string Pattern
{
get
{
return _pattern;
}
set
{
if(value == null)
throw new ArgumentNullException();
/*if(value.Length == 0)
throw new ArgumentException("Argument is empty.");*/
_pattern = value;
_parts = CreateParts(ArrangePattern(value));
}
}
public bool IsMatch(string input)
{
if (input == null)
throw new ArgumentNullException();
if (_pattern == null)
throw new NullReferenceException("Pattern is null.");
int inputLen = input.Length;
int partsLen = _parts.Length;
if (inputLen == 0)
return partsLen == 0 || (partsLen == 1 && _parts[0] == PartSkipCharacters);
if (partsLen == 0)
return false;
byte[] inputBytes = Encoding.UTF8.GetBytes(input);
return IsMatchSubcontract(inputBytes, 0, inputBytes.Length, 0, partsLen);
}
private bool IsMatchSubcontract(byte[] input, int inputIndex, int inputLen, int partsIndex, int partsLen)
{
for (; partsIndex < partsLen; partsIndex++)
{
Part part = _parts[partsIndex];
if (part == PartSkip1)
{
if (inputLen <= inputIndex)
{
return false;
}
byte c = input[inputIndex];
if ( (c & (byte)0x80) == 0)
{
inputIndex++;
}
else if ((c & (byte)0xe0) == 0xc0)
{
inputIndex += 2;
if (inputLen < inputIndex) { return false; }
}
else if ((c & (byte)0xf0) == 0xe0)
{
inputIndex += 3;
if (inputLen < inputIndex) { return false; }
}
else if ((c & (byte)0xf8) == 0xf0)
{
inputIndex += 4;
if (inputLen < inputIndex) { return false; }
}
else if ((c & (byte)0xfc) == 0xf8) // 不正なbyte数だが一応
{
inputIndex += 5;
if (inputLen < inputIndex) { return false; }
}
else if ((c & (byte)0xfe) == 0xfc) // 不正なbyte数だが一応
{
inputIndex += 6;
if (inputLen < inputIndex) { return false; }
}
else
{
throw new EncoderFallbackException("utf-8の1文字は1～6byteでなければならない");
}
}
else if (part == PartSkipCharacters)
{
partsIndex++;
if (partsIndex == partsLen) // 最後が*で終了
{
return true;
}
part = _parts[partsIndex];
while(true)
{
inputIndex = part.IndexOf(input, inputIndex);
if (inputIndex < 0)
{
return false;
}
if (IsMatchSubcontract(input, inputIndex + part.TextBytesLength, inputLen, partsIndex + 1, partsLen))
{
return true;
}
inputIndex = part.SkipToNextStartPoint(input, inputIndex);
}
}
else
{
if(!part.StartsSubbytesWith(input, inputIndex))
{
return false;
}
inputIndex += part.TextBytesLength;
}
}
return inputLen == inputIndex;
}
private string ArrangePattern(string pattern)
{
Regex r = new Regex(@"[\*\?]{2,}");
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < pattern.Length)
{
Match m = r.Match(pattern, i);
if (!m.Success)
{
sb.Append(pattern.Substring(i));
break;
}
sb.Append(pattern.Substring(i, m.Index - i));
string t = m.Value;
if (t.Contains("?"))
{
if (t.Contains("*")) // ?と*が混ざっている場合、?は前にまとめて*は1つにする。
{
foreach (char c in t)
{
if (c == '?')
{
sb.Append('?');
}
}
sb.Append('*');
}
else // ?だけが連なっている場合
{
sb.Append(t);
}
}
else // *だけが連なっている場合、1つにまとめる。
{
sb.Append('*');
}
i = m.Index + m.Length;
}
return sb.ToString();
}
private Part[] CreateParts(string pattern)
{
Debug.Assert(pattern != null);
List<Part> parts = new List<Part>();
int i = 0;
while (i < pattern.Length)
{
if (pattern[i] == '?')
{
parts.Add(PartSkip1);
i++;
}
else if (pattern[i] == '*')
{
parts.Add(PartSkipCharacters);
i++;
}
else
{
int len = FindWildCardCharacter(pattern, i);
parts.Add(new Part(pattern.Substring(i, len)));
i += len;
}
}
return parts.ToArray();
}
// indexから数えて何文字目に*または?があるかを返す。
// 注意!! 無ければ終端までの文字数を返す。
// indexの範囲チェック無し。patternの文字数の範囲に収まるという前提。
private int FindWildCardCharacter(string pattern, int index)
{
Debug.Assert(0 <= index && index < pattern.Length);
int len = 0;
while (index < pattern.Length)
{
char c = pattern[index];
if (c == '?' || c == '*')
{
break;
}
index++;
len++;
}
return len;
}
private class Part
{
private readonly byte[] _textBytes;
public byte[] TextBytes
{
get
{
return _textBytes;
}
}
private readonly int _textBytesLength;
public int TextBytesLength
{
get
{
return _textBytesLength;
}
}
#if DEBUG
private readonly string _text;
public string Text
{
get
{
return _text;
}
}
#endif
// BM法での文字列探索用テーブル
private readonly int[] _skipTable;
public Part(string text)
{
Debug.Assert(text != null);
_textBytes = Encoding.UTF8.GetBytes(text);
_textBytesLength = _textBytes.Length;
#if DEBUG
_text = text;
#endif
_skipTable = new int[256];
CreateSkipTable();
}
// BM法を使用してinputのbyte列の中から、何番目に_textBytesと同じbyte列があるかを探して返す。
// 無ければ-1を返す。
public int IndexOf(byte[] input, int startIndex)
{
int inputLen = input.Length;
int i = startIndex + _textBytesLength - 1;
while (i < inputLen)
{
int j = _textBytesLength - 1;
while (input[i] == _textBytes[j])
{
if (j == 0)
{
return i;
}
i--;
j--;
}
i += Math.Max(_skipTable[input[i]], _textBytesLength - j);
}
return -1;
}
// 次のマッチング開始位置を返す。
// (*text のマッチングに失敗した場合に使用)
public int SkipToNextStartPoint(byte[] input, int index)
{
return index + _skipTable[input[index]];
}
// inputのbyte列が_textBytesと同じ値で始まっているかをチェック。
public bool StartsSubbytesWith(byte[] input, int startIndex)
{
Debug.Assert(0 < _textBytesLength);
int inputIndex = startIndex + _textBytesLength - 1;
if (input.Length <= inputIndex)
return false;
for (int textIndex = _textBytesLength - 1; 0 <= textIndex; textIndex--)
{
if (input[inputIndex] != _textBytes[textIndex])
{
return false;
}
inputIndex--;
}
return true;
}
private void CreateSkipTable()
{
for (int i = 0; i < _skipTable.Length; i++)
_skipTable[i] = _textBytesLength;
for (int j = 0; j < _textBytesLength - 1; j++)
_skipTable[_textBytes[j]] = _textBytesLength - j - 1;
}
}
}
}
同等のことはSystem.Text.RegularExpressions.Regexでも実現することができます。
- WildCardMatcherのパターン : "abc*def?ghi"
- Regexのパターン : "abc.*def.ghi"
というわけで性能について言及しなければなりません。
手前味噌な適当なテストデータで確認したところ、「"test_*.html"」のような短い文字列に対してマッチングをした場合、Regexの方が時間がかかりませんでした。 ファイル名やホスト名などのマッチングに使用するつもりで作ったので、そういうデータでRegexに負けてるなら作った意味がありません。
50文字以上のパターンに対して使うと、WildCardMatcherの方がRegexよりも優位になるようです。 文字数が多くなればRegexの数十倍の速さでマッチングできるケースも。
でもそんな文字列に対して使うアテが全く無いんですよね。 「数十倍の速さ」のタイムが出たときとか、「数千文字のランダム文字列を10万件マッチングしたときの平均値」みたいな状況でした。 これをどう生かせと? このクラスを作った結果、頭の体操で終わってしまったようです。 無念。
まぁ、「おとなしくRegexを使っておきなさい」というところでしょうか? 一応、酷い性能っていうわけでは無さそうなので用途によっては使えるかもしれませんね?
以下、コードで何をやってるかザックリと説明します。 とはいえ無念がいっぱいなのでまともに説明する気力はありません。 「コードを読むヒントくらいにはなるかなぁ」っていう程度で失礼。 まず、Patternプロパティへのパターンの設定から。
Patternが設定されたら、ArrangePatternメソッドで?*の記号の整理を、CreatePartsメソッドでPartの分解をします。 ArrangePatternメソッドでは?と*が1箇所に固まっていたら?を前に出します。 例えば、「abc*def?*???**ghi?jkl」みたいなパターンが有った場合、「?*???**」の部分では?の数だけ、最低4文字はマッチしなくてはなりません。 そこで?4つを前に出します。 *はいくつあっても同じなので1つに整理。 「abc*def?*???**ghi?jkl」は「abc*def????*ghi?jkl」となります。
次に、CreatePartsメソッドで
- ワイルドカード記号「?」
- ワイルドカード記号「*」
- テキストの塊
のPartに分解します。 「test*pattern?」なら
- テキストの塊「test」
- ワイルドカード記号「*」
- テキストの塊「pattern」
- ワイルドカード記号「?」
という順番のPartになります。 テキストの塊はutf-8のbyte配列でPartクラスに収めます。 utf-8にするのは、テキストの塊の検索にBM法を使っているためです。 テキストの塊のPartを作るときにBM法のテーブルも作ります。
BM法については、ちょっと古い本ですがコチラを参考にしました。
- 定本 Cプログラマのためのアルゴリズムとデータ構造(ISBN-10 : 4797304952)
BM法の説明についてはこちらのページにも書いてあります。 (というか、本と全く同じ内容なんだけど、著作権とかってどうなってるんでしょう?)
- KOSAKA's website - 文字列検索(BM法)
BM法は前もって文字を構成する配列1要素分のサイズのテーブルを作らなければなりません。 stringをそのまま使うと1要素はchar型でテーブルサイズは65536になってしまいます。 テキストの塊がどんなに小さくてもです。 それはあまり効率がいいとは言えません。 そこで、utf-8に変換してから比較することで1要素をbyte型に、テーブルのサイズを256にしました。 utf-8は1文字に複数byte使う場合、1byte目と2byte目以降ではbitの並びが違うので文字境界と異なる個所でマッチしてしまうことがありません。 これはBM法と相性がいいところです。 (wikipediaによると、Shift_JISで「\:0x5c」を検索すると「表:0x95 0x5c」の2バイト目にマッチしてしまうような事があるけど、utf-8ではそれが無い。)
ちょと横道にそれたけど、ここまででPartの分解ができたのでPatternプロパティの設定は終わりです。 以下、IsMatchでのマッチングの説明。
IsMatchに文字列「input」が渡されたらutf-8に変換して、分解済みのPartを使ってPatternを探します。 今inputのどこを見ているかはinputIndexに、今どのPartをマッチングしているかはpartsIndexに入っています。 細々と説明しても仕方がないのでザックリと、今マッチングしているPartが次の場合何をするかだけ書きましょう。
- ワイルドカード記号「?」のPart
- ワイルドカード記号「*」のPart
- テキストの塊のPart
?のPartの場合、inputIndexを見てまだ文字が残っているなら1文字進めます。 inputはutf-8になっているので1文字が1byteとは限りません。 1文字が複数byteで表現されている場合、最初のbyteの上位bitを見れば文字数が分かります。 それを見て1文字分inputIndexを進めています。 文字が残ってない場合はfalseを返しているけど、これはwindowsのワイルドカードとは違う動作のようです。 trueにしたらwindowsのワイルドカードと同じになるかもしれないけど、チェックとか使用確認とかが面倒なので割愛。
*のPartの場合、*で終わっているのか、パターンの途中で*が出てきているのかで処理が違います。 *で終わる場合、input側がどうであれマッチするのでtrueを返して終了です。 パターンの途中で*が出てくる場合、次のテキストの塊とセットで考えます。 (ArrangePatternメソッドでの整理の結果、*の次は必ずテキスト。)
*とテキストの組があったら、inputの中で次にテキストが出てくる場所をBM法で探します。 テキストがなければ当然falseを返します。 テキストが見つかっても以降のパターンが全部マッチする保障はありません。 とりあえず、今見つかったテキストの位置を記憶して、再帰で以降のパターンがマッチするか調べます。 再帰呼び出し先でもマッチしたらtrueを返します。 再帰呼び出し先がダメなら、記憶しておいたテキスト位置より後にマッチするテキストが無いか探します。 このとき、次のテキストを探し始める位置はBM法のテーブルを流用することでちょっとだけ効率化しています。
テキストの塊のPartの場合はただ単に同じbyte列かを比較するだけです。 ただし、*とテキストの組は必ずセットでマッチングされるので、テキストの塊だけをマッチングするのはパターンの先頭にあった場合か?の後にあったときだけになります。
条件によっては↑に書いたように途中で判定が出てreturnすることもありますが、Part全部をマッチングしてしまうケースもあります。 分解済みのPartを全部マッチングした場合、inputが残っていなかったらマッチング成功です。 trueを返します。 inputが残っていたら、inputは「パターン+余分な文字列」という事になります。 マッチング失敗なのでfalseを返します。
説明は、こんな感じかなぁ。 うん、読み返してみても自分しか分からないような雰囲気の文章になってますね。 半年後に自分が読んで分からない自信もあります。 「コードを読むヒントくらいには」って言っておきながら天然ミスリードになってますね。 でも以上。
でお買い物
