Sunday's Quick Search algorithm in C#
3/22の実装では日本語が検索できません。お箸の国の人としては寂しい限りなので、Unicode全部検索できる妥当な方法を考えてみます。
まずは素直にskipテーブルを char.MaxValue + 1 取ってみました。ものは試しです。結果は、…100万回ループだといつまでも終わりませんでした。やっぱり無茶でした。
じゃあ、テーブルサイズを256のままにして、charの下位バイトだけのテーブルに丸めてしまえばどうでしょう。ジャンプする回数は減るけど、なかなか妥当そうな気がしてきます。英数字だけを検索するならわずかに遅くなる程度でしょう。
public static int IndexOfSundayQuickSearch( string text, string pattern )
{
if ( text == null ) throw new ArgumentNullException( "text" );
if ( pattern == null ) throw new ArgumentNullException( "pattern" );
if ( pattern == string.Empty ) return 0;
if ( text.Length < pattern.Length ) return -1;if ( pattern.Length == 1 )
{
for ( int n = 0; n < text.Length; n++ )
{
if ( text[ n ] == pattern[ 0 ] )
{
return n;
}
}
return -1;
}// skipテーブル作成
int[] skipTable = new int[ 256 ];
for ( int k = 0; k < skipTable.Length; k++ )
{
skipTable[ k ] = pattern.Length + 1;
}
for ( int k = 0; k < pattern.Length; k++ )
{
int lower = pattern[ k ] & 0xff;
skipTable[ lower ] = pattern.Length - k;
}int i = 0; // 比較開始先頭位置
int max = text.Length - pattern.Length;
#if DEBUG
int count = 0;
try
{
#endif
// 比較終了点の文字の次に文字がある場合
// 例) ABCDE - text
// EF - pattern
while ( i < max )
{
for ( int j = 0; j < pattern.Length; j++ )
{
#if DEBUG
count++;
#endif
if ( text[ i + j ] != pattern[ j ] )
{
goto NEXT;
}
}
return i;NEXT:
int lower = text[ i + pattern.Length ] & 0xff;
i += skipTable[ lower ];
}// textの最後の文字の位置と、patternの最後の文字の位置が同じ場合
// 例) ABCDE - text
// EF - pattern
if ( i == max )
{
for ( int j = 0; j < pattern.Length; j++ )
{
#if DEBUG
count++;
#endif
if ( text[ i + j ] != pattern[ j ] )
{
return -1;
}
}
return i;
}return -1;
#if DEBUG
}
finally
{
Console.WriteLine( "compare : {0}", count );
}
#endif
}
変更はskipテーブルを作るところと、テーブルを読むところだけ。
DEBUGで囲んで比較回数を表示するようにしてあります。力任せのIndexOfBruteForceにも同様に入れて比較するとおもしろいです。
Testクラスも変更して日本語を検索してみます。
青空文庫から賢者の贈り物を落としてきてUTF-8のtxtにして実行ファイルと同じディレクトリに置きます。ついでに読むｗ ちなみに訳者は結城さんでした。置いてあるのも正確には結城さんのサイトです。
private const int testLoopMax = 100000;private string text;
private string pattern;public Test()
{
text = File.ReadAllText( "賢者の贈り物.txt" );
pattern = "最もすばらしい宝物";
}
前回のコードの text, pattern を消して、コンパイル＆実行。
デバッグ版で比較回数を見ると、力任せ:6610回、QuickSearch:721回でした。これはすごい差！
10万回ループでの実行時間はこうなりました。比較処理は3つに絞りました。
IndexOfInvariantCultureOrdinal: 6601, Time: 1398ms
IndexOfBruteForce: 6601, Time: 1446ms
IndexOfSundayQuickSearch: 6601, Time: 522msはえぇぇ。
この例は早いほうの例なのかもしれないけど、これは使えますね！数日かけて遊んだかいがあったってもんです。宝物ゲットした〜。
