Boyer-Moore-Horspool検索法(BMH法)
BM法で検索しているときにこちらのページでBMH法っていう、BM法の改良があることを知りました。読んでみると実に簡単です。なんでこれでうまく行くのよ？ってのも絵を描いて実際に試してみればすぐうまく行くことがわかりました。正式にはBoyer-Moore-Horspool検索法と呼ばれてるようです。
BM法のテーブルをいじくって考えてみるのは、遊びのプログラミングとしてはメンドーそうだけど、BMH法を実装してみるなら実に簡単そうなので書いてみました。後からそのページの上のほうにダウンロードリンクがあることに気づいた…。
C#のたくさんあるIndexOfともパフォーマンスを比較してみます。
.NET2.0で string.Contains( pattern ); ってのもあるけど、IndexOfがあればアダプターとして作れるので今回は触れません。Stopwatchクラスが追加になっているのに気づいたから今回使っています。
肝のテーブルについては256個のエントリーにしてます(つまりこのままでは日本語などの検索には使えないということ)。しかもintなのででかいですけど。
using System;
using System.Collections.Generic;namespace Search
{
public static class StringSearch
{
public static int IndexOf( string text, string pattern )
{
return text.IndexOf( pattern );
}public static int IndexOfOrdinal( string text, string pattern )
{
return text.IndexOf( pattern, StringComparison.Ordinal );
}public static int IndexOfInvariantCulture( string text, string pattern )
{
return text.IndexOf( pattern, StringComparison.InvariantCulture );
}public static int IndexOfInvariantCulture2( string text, string pattern )
{
return System.Globalization.CultureInfo.InvariantCulture.CompareInfo.IndexOf( text, pattern );
}public static int IndexOfInvariantCultureOrdinal( string text, string pattern )
{
return System.Globalization.CultureInfo.InvariantCulture.CompareInfo.IndexOf(
text, pattern, System.Globalization.CompareOptions.Ordinal );
}public static int IndexOfBruteForce( string text, string pattern )
{
if ( text == null ) throw new ArgumentNullException( "text" );
if ( pattern == null ) throw new ArgumentNullException( "pattern" );
if ( pattern == string.Empty ) return 0;for ( int i = 0; i <= ( text.Length - pattern.Length ); i++ )
{
for ( int j = 0; j < pattern.Length; j++ )
{
if ( text[ i + j ] != pattern[ j ] )
{
goto NEXT;
}
}
return i;NEXT:
;
}
return -1;
}// charの範囲0-255のみ対応。256-65535はNG。
public static int IndexOfBMH( 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++ )
{
skipTable[ pattern[ k ] ] = pattern.Length - k;
}int i = 0; // 比較開始先頭位置
int max = text.Length - pattern.Length;// 比較終了点の文字の次に文字がある場合
// 例) ABCDE - text
// EF - pattern
while ( i < max )
{
for ( int j = 0; j < pattern.Length; j++ )
{
if ( text[ i + j ] != pattern[ j ] )
{
goto NEXT;
}
}
return i;NEXT:
i += skipTable[ text[ i + pattern.Length ] ];
}// textの最後の文字の位置と、patternの最後の文字の位置が同じ場合
// 例) ABCDE - text
// EF - pattern
if ( i == max )
{
for ( int j = 0; j < pattern.Length; j++ )
{
if ( text[ i + j ] != pattern[ j ] )
{
return -1;
}
}
return i;
}return -1;
}public static int IndexOfBMHHash( 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 hash作成
Dictionary<char, int> hash = new Dictionary<char, int>( pattern.Length );
for ( int k = 0; k < pattern.Length; k++ )
{
hash[ pattern[ k ] ] = pattern.Length - k;
}int i = 0; // 比較開始先頭位置
int max = text.Length - pattern.Length;
int distance = pattern.Length + 1;// 比較終了点の文字の次に文字がある場合
// 例) ABCDE - text
// EF - pattern
while ( i < max )
{
for ( int j = 0; j < pattern.Length; j++ )
{
if ( text[ i + j ] != pattern[ j ] )
{
goto NEXT;
}
}
return i;NEXT:
if ( !hash.TryGetValue( text[ i + pattern.Length ], out distance ) )
distance = pattern.Length + 1;
i += distance;
}// textの最後の文字の位置と、patternの最後の文字の位置が同じ場合
// 例) ABCDE - text
// EF - pattern
if ( i == max )
{
for ( int j = 0; j < pattern.Length; j++ )
{
if ( text[ i + j ] != pattern[ j ] )
{
return -1;
}
}
return i;
}return -1;
}
}
}
動かすほうのソースはこちら。
using System;
using System.Diagnostics;namespace Search
{
class Program
{
static void Main()
{
Test test = new Test();
test.Do();
Console.ReadLine();
}
}class Test
{
#if DEBUG
private const int testLoopMax = 1;
#else
private const int testLoopMax = 1000000;
#endifpublic Test() { }
public void Do()
{
DoTest( StringSearch.IndexOf );
DoTest( StringSearch.IndexOfOrdinal );
DoTest( StringSearch.IndexOfInvariantCulture );
DoTest( StringSearch.IndexOfInvariantCulture2 );
DoTest( StringSearch.IndexOfInvariantCultureOrdinal );
DoTest( StringSearch.IndexOfBruteForce );
DoTest( StringSearch.IndexOfBMH );
DoTest( StringSearch.IndexOfBMHHash );
}private delegate int IndexOfDelegate( string text, string pattern );
private void DoTest( IndexOfDelegate method )
{
int result = 0;
Stopwatch sw = new Stopwatch();sw.Start();
for ( int i = 0; i < testLoopMax; i++ )
{
result = method( text, pattern );
}
sw.Stop();
Console.WriteLine( "{0,30}: {1}, Time: {2,5}ms", method.Method.Name, result, sw.ElapsedMilliseconds );
}//private string text = "abcabbbbb";
//private string pattern = "abbbb";private string text = "When I have fears that I may cease to be" + Environment.NewLine +
"Before my pen has gleaned my teeming brain," + Environment.NewLine +
"Before high-piled books, in charactery," + Environment.NewLine +
"Hold like rich garners the full ripened grain;" + Environment.NewLine +
"When I behold, upon the night's starred face," + Environment.NewLine +
"Huge cloudy symbols of a high romance," + Environment.NewLine +
"And think that I may never live to trace" + Environment.NewLine +
"Their shadows, with the magic hand of chance;" + Environment.NewLine +
"And when I feel, fair creature of an hour," + Environment.NewLine +
"That I shall never look upon thee more," + Environment.NewLine +
"Never have relish in the fairy power" + Environment.NewLine +
"Of unreflecting love; then on the shore" + Environment.NewLine +
"Of the wide world I stand alone, and think" + Environment.NewLine +
"Till love and fame to nothingness do sink.";//private string pattern = "love";
private string pattern = "nothingness";
//private string pattern = "happy";
}
}
nothingnessを検索した場合の実行結果はこうなりました。
IndexOf: 583, Time: 14761ms
IndexOfOrdinal: 583, Time: 1651ms
IndexOfInvariantCulture: 583, Time: 1667ms
IndexOfInvariantCulture2: 583, Time: 1663ms
IndexOfInvariantCultureOrdinal: 583, Time: 1643ms
IndexOfBruteForce: 583, Time: 1511ms
IndexOfBMH: 583, Time: 1255ms
IndexOfBMHHash: 583, Time: 4530msIndexOfが10倍も遅いのは以前書いたとおり、高度な比較をやってるから。
IndexOfBruteForceは標準ライブラリより若干早い。
IndexOfBMHはこのくらいの長さの文章でも早いねぇ。
IndexOfBMHHashはテーブルをハッシュにしてみたけど、ひどい結果になったｗ ハッシュも自前で実装すればどうなるんだろう…？
一方、loveを検索した場合はこうなりました。
IndexOf: 492, Time: 12760ms
IndexOfOrdinal: 492, Time: 1352ms
IndexOfInvariantCulture: 492, Time: 1339ms
IndexOfInvariantCulture2: 492, Time: 1295ms
IndexOfInvariantCultureOrdinal: 492, Time: 1298ms
IndexOfBruteForce: 492, Time: 1210ms
IndexOfBMH: 492, Time: 1522ms
IndexOfBMHHash: 492, Time: 6426msIndexOfBMHが単純検索に負けます。検索語が長ければ長いほど、比較しないで済む文字数が増えるので、検索語の文字数でBMHか単純検索か振り分けてやればよさそうですね。
最悪の場合の検証とか、どういう場合にBMHにしてどういう場合に普通に検索するかとか、そういった考察は省略。
(追記) IndexOfBMH と IndexOfBMHHash のバグを直しました。範囲チェックが甘かったのと、飛ばしすぎていました。ついでに入力値のチェックも追加。
範囲チェックがわりと面倒で似たようなブロックが２箇所出てくる変なソースになってしまいました。もっとよい実装があれば教えてください。
