スタッフBLOG

おはようございます。
最近、運動不足を解消しようと思ってランニングを始めたのですが
筋肉痛に負けて挫けてしまいそうな本日の当番。
プログラマーのS.Kです。


さて今回のブログでは『文字列比較』について書こうと思います。

基本的に文字列が一致しているかどうかを判定する場合、
文字を1文字ずつ比較して一致しているか確認する必要があります。
その為、少ない回数の比較であればすぐに終わるのですが
比較対象が多くなってくると予想以上に重くなる可能性があります。

なので場合によっては文字列の比較方法を工夫してやる必要があります。
比較時の工夫の方法にも色々あると思いますが、
簡単なものとしては下記のようなやり方があります。

・先頭等の一部の文字が一致しているかではじく
・文字数が一致しているかではじく

今挙げたものを実際に記述すると下記のようになります。
bool CompareString(const char* p1, const char* p2)
{
　　//先頭の文字比較
　　if( p1[0] != p2[0] )return false;

　　//文字数の比較
　　int len1 = strlen(p1);
　　int len2 = strlen(p2);
　　if( len1 != len2 )return false;

　　//末尾の文字比較
　　if( p1[len1 - 1] != p2[len2 - 1] )return false;

　　//真ん中の文字比較
　　if( p1[len1 >> 1] != p2[len2 >> 1] )return false;

　　//文字列比較
　　return strcmp(p1, p2) == 0;
}

とっていた形で高速化を図る事が出来ます。
これでも似たような文字列が多い場合には遅くなってしまいますが、
単純に比較するよりはだいぶ早くなります。

また上記以外の高速化の手段としてハッシュ値を使用する方法があります。
内容としては事前にハッシュ値を算出しておき
文字列比較時にハッシュが一致しているかどうかで判定するというものです。

実装の例としては下記のようになります。
※ハッシュ値を算出するHash関数があるものと仮定します。
struct StringHash
{
　　char*　pText;
　　int　　iHash;
};

bool CompareString(const StringHash& str1, const StringHash& str2)
{
　　//ハッシュ値の比較
　　if( str1.iHash != str2.iHash )return false;
　　//文字列比較
　　return strcmp(str1, str2) == 0;
}

とっていた形で高速化を図る事が出来ます。
ただしハッシュ値の計算方法によっては衝突が多数発生する事があるので
あまり効果が得られない可能性もあります。
又、ハッシュ値の計算自体に負荷が掛かってしまう可能性もあります。

上記の対処としては以下のような対処が考えられます。
・CRC32等の衝突する可能性が比較的に低い方法でハッシュ値を計算する
・事前に計算済みのハッシュ値をデータ等に含めておく

このように文字列比較にも色々な高速化の手段があります。
今回挙げた内容以外にも色々な方法があると思うので
気になった方は色々と調べてみてはいかがでしょうか。