部分文字列の一致を検出

質問

２つの文字列がありstring1とstring2とします。
やりたいことは、string1の中のある部分文字列がstring2の部分文字列と一致する場合、真を返す関数を作りたいのです。関数プロトタイプのイメージはこんな感じです。

bool CheckPartialMatch(char* string1, char* string2, int minChars);
[機能]
string1とstring2の部分文字列（minChars文字数以上）の一致の有無を調査する。
大文字と小文字の区別はしない。
[パラメータ]
string1:比較元のNULL終端文字列
string2:比較先のNULL終端文字
minChars:最小一致文字数

例として下記のようなケースを考えます。
string1="BananaAppleOrange"
string2="LemonPineappleKiwi"

minChars=4の場合、上記例では"appl"の４文字が一致しますのでtrueが返ることになります。
上記例では、minChars<=5ならtrue, minChars>=6ならfalseとなります。
部分一致が１か所でも見つかれば、その時点で以降の調査を打ち切ります。
何か所一致したとか、一致した位置といった情報は返しません。（位置情報は追加コストなしで返せるでしょうが、今回は必要ありません）

もちろん、ベタにstring1の１文字目から順に逐一string2と比較すれば実現できるのですが、それでは時間がかかります。
実際には、この処理をあるフォルダ内の全ファイル名に対して行いたいと思っています。
例えばファイル数が100とすると、組み合わせの数は100*(100-1)/2で4950となります。
仮に１ペアのチェックの所要時間が10msとしても、トータルで約50秒かかることになります。
1000ファイルともなると優に１時間を超える所要時間となり、現実的ではありません。
メモリを食い尽くすような処理ではないので放っておけば終わるのでしょうが、本当は数千のファイルに対してこの処理を行いたいと思っています。

以上を高速に処理する手段やアルゴリズムはないでしょうか？
boostなど外部のライブラリを使用した方が早いのであれば、それをご提案頂いても構いません。
実際の使用環境ではminCharsが４程度、比較文字列は平均して２０文字程度（２バイト文字含む）を想定しています。

処理時間を低減するため、対象文字を英数字('A-Z'、'a-z'、'0-9')のみに限定することもオプションとして考慮したいと思っています。ファイル名ですので、実際には文字列内に２バイト文字や記号類も混じっています。
あらかじめ全ての入力文字列に対して英字を小文字に変換しておくとか、英数字以外の文字を（連続する場合はまとめて）代替文字（"@"等）に置換しておけば少しは負荷軽減になるかとは思いますが、効果のほどは不明です。

回答No.11

maru_yoshi_ · ベストアンサー

> 文字コードをUNICODEにしても、サロゲートペアがあるので問題ないとは言えないでしょう。
なるほど。部分文字列の切り出し時に注意が必要ですね。

実際にどの程度の時間がかかるのか、試しにプログラムしてみました。
20-29文字の乱数文字列を複数作成、部分文字列の比較を総当たりで判定。
部分文字列の判定は strstr を使用した力技。
ただし、文字列の切り出しを少しだけ工夫。

OS:Windows7 Home(64ビット) SP1, コンパイラ:VC2012 update 3
部分文字列長（minChars=4）
文字列数 1000=> 1737ms
文字列数 2000=>10004ms
文字列数 3000=>13189ms
文字列数 4000=>36628ms
実行時間が文字列数の二乗に比例していない理由は不明。
誤差にしても1000,3000の場合が短すぎる。
（プログラムが間違っている？）
文字列数1000で2秒以下なので、力技で十分では？
このプログラムを再利用するには、unicode対応（char=>wchar_t、サロゲートペアの処理）が必要です。

プログラムは以下の通り。

#include "stdafx.h"
#include <cstdio>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>

#pragma warning(disable:4996)

using namespace std;

const size_t FileNameLengthBase = 20; // ファイル名の長さ（ベース）
const size_t FileNameLengthRand = 10;
const size_t FileCount = 1000;
const size_t MinChars = 4; // 比較に用いる部分文字列の長さ

void init(vector<string>& names)
{
srand(0);
for (vector<string>::iterator it = names.begin(); it != names.end(); ++it)
{
size_t n = rand() % FileNameLengthRand + FileNameLengthBase;
for (size_t i = 0; i < n; ++i)
{
it->push_back(char('a' + rand() % 26));
}
}
}

bool IsPartialMatch(const char* const str1, const char* const str2, size_t minChars)
{
bool bResult = false;
size_t len = strlen(str2);
char* temp = new char[len + 1]; // 比較文字列用のバッファを準備
strcpy(temp, str2);
char* last = temp + len; // 比較文字列の最後へのポインタ
char* pos = last - minChars; // 比較文字列の最後のパターンへのポインタ
for (; temp <= pos; --pos) // 比較文字列の後ろから比較を行う
{
const char* result = strstr(str1, pos);
if (result != nullptr)
{
bResult = true;
break;
}
*(--last) = 0; // 比較パターンの文字列を終端
}
delete [] temp;
return bResult;
}

// 文字列が一致した位置を取得する
// 復帰値：文字列が一致した文字列１の位置
// 文字列が一致していない場合、戻り値は０を返す
size_t GetPartialMatchPosition
( const char* const str1
, const char* const str2
, size_t minChars
, size_t& nPos // 文字列２の一致した位置（出力）
)
{
size_t nResult = 0;
size_t len = strlen(str2);
char* temp = new char[len + 1]; // 比較文字列用のバッファを準備
strcpy(temp, str2);
char* last = temp + len; // 比較文字列の最後へのポインタ
char* pos = last - minChars; // 比較文字列の最後のパターンへのポインタ
for (; temp < pos; --pos) // 比較文字列の後ろから比較を行う
{
const char* pResult = strstr(str1, pos);
if (pResult != nullptr)
{
nResult = pResult - str1;
nPos = pos - temp;
break;
}
*(--last) = 0; // 比較パターンの文字列を終端
}
delete [] temp;
return nResult;
}

int _tmain(int /*argc*/, _TCHAR* /*argv[]*/)
{
vector<string> FileNames(FileCount);
init(FileNames);
int n1(0), n2(0);

clock_t start = clock();

size_t MatchCount = 0;
for (vector<string>::const_iterator i = FileNames.cbegin(); i != FileNames.cend(); ++i)
{
n2 = n1 + 1;
for (vector<string>::const_iterator j = i + 1; j != FileNames.cend(); ++j)
{
if (IsPartialMatch(i->c_str(), j->c_str(), MinChars))
{
// size_t pos2 = 0;
// size_t pos1 = GetPartialMatchPosition(i->c_str(), j->c_str(), MinChars, pos2);
// cout << "\"" << *i << "\":" << pos1 << "\t\"" << *j << "\":" << pos2 << endl;
++MatchCount;
}
++n2;
}
++n1;
}
clock_t end = clock();
cout << "実行時間:" << end-start << "ms" << endl;
cout << "一致した数:" << MatchCount << endl;

IsPartialMatch(FileNames[340].c_str(), FileNames[755].c_str(), MinChars);

return 0;
}

自作の高速化（10倍以上）したプログラムですが、やはり文字列数に依存します。
興味があれば公開してもいいですが。...

お礼

提示頂いたプログラムを私の環境（Win7 x64/Core i7/16GB）で実行してみたところ、下記のような数字が出ました。概ね文字列数の２乗に比例しているようです。
文字列数 1000=>174ms
文字列数 2000=>622ms
文字列数 3000=>1430ms
文字列数 4000=>2550ms
文字列数 10000=>15768ms

上記コードでは、実行ごとに毎回同じ乱数が生成されます。たまたまその乱数のパターンによってそのような結果になったのではないでしょうか？

回答No.10

trapezium

#1 です

たぶん現状で移植性と実装のしやすさを考慮するなら、char32_t (UTF-32) 使うのがいいかとは思います。それ以下の Unicode では多バイト文字同様の面倒さが残ります。(別に固定長で表現できれば UTF-32 (32bit) でなくともいい)

さきの wchar_t のテストルーチンの件も、事前に多バイト文字データからワイド文字データ (UTF-32) に変換しています。

回答No.9

m-take0220

文字コードをUNICODEにしても、サロゲートペアがあるので問題ないとは言えないでしょう。

お礼

恥ずかしながらサロゲートペアなる言葉を初めて知りました。実際どのような問題があり、解決するためには何が必要でしょうか？アルゴリズムそのものに手を入れる必要がありますか？

回答No.8

maru_yoshi_

> 実際の検索文字列には２バイト文字が含まれています。
> １バイト文字のみから構成される文字列と比べて性能が劣ることはありますか？
確か文字列は unicode と書いておられたのでは？　文字列比較が char 単位から TCHAR(wchar_t) 単位になるだけでありアルゴリズムによる性能の違いはありません。
問題はシフトJISによる文字列比較であり、２バイト文字の２バイト目の扱いです。　検索パターンの先頭文字がアスキーコードであったとき、被検索文字列中の２バイト文字の２バイト目が一致してしまうことがあります。これを避けるためには文字列比較を工夫する必要がありますが、 unicode であれば問題は無いはずです。

今回の課題は、複数（2～1000程度）のファイル名（約20文字）に対して部分文字列（4文字程度）が一致するかを判定したいとのことですが、実行時間を支配するのはファイル数であり、その計算量はファイル数の二乗に比例し、これを減らすことは困難です。まあ力技でやってもいいのではないかと思います。

プログラムの作成に時間をかけてもいいのであれば、私なら前述した「ラビン-カープ文字列検索アルゴリズム」を応用してみたいです。
まず、各ファイル名について部分文字列のハッシュ値群を作成する（手順１）。
次に、各ファイル名ペアについてハッシュ値群の比較を行い、一致するものがあった場合、そのハッシュ値の元となる部分文字列を比較する（手順２）。
という方法にします。手順１はファイル数に比例する処理時間であり、手順２はファイル数の二乗に比例する処理時間なので、手順２が単純な文字列比較を使用したものより高速ならばこの方法で高速化がはかれます。
手順１で作成するハッシュ値群をソートしておけば、手順２のハッシュ値群の比較では、ソート済の集合から一致するものを探す処理になり、計算量はO(n)になり、効率よく一致判定が可能になります。
ただし、この方法ではひとつひとつのハッシュ値に対して元の部分文字列（元の部分文字列へのリンク）を持っている必要があり、メモリが大量に必要になりそうです。

お礼

詳しいご説明ありがとうございます。ただ自分で実装するのは困難そうです。既に確立したアルゴリズムのようですし、どこかに既成のライブラリがありませんかね？このようなことをやりたい人はそれなりにいると思いますし、フリーのツールもありそうな感じなのですが。

回答No.7

maru_yoshi_

文字列検索のアルゴリズムには「ボイヤー-ムーア文字列検索アルゴリズム」が有名です。
検索パターン文字列長をm、非探索文字列長をnとするとパターンがテキスト内に存在しない場合のボイヤー-ムーア法の最悪ケースは O(n+m) です。パターンがテキスト内に出現する場合の最悪ケースは O(nm) とだそうです。
今回の場合、検索パターン文字列が部分文字列なので、検索パターン文字列全体のサイズをlとすると検索パターンの数kは（l－m＋1）なので計算回数の最悪値はl>>mと仮定するとO(nml)となります。一般にはn>>m.lなのでO(n)と考えます（長い文字列から短い文字列を検索する場合）。
検索パターンが複数ある場合は「ラビン-カープ文字列検索アルゴリズム」が有効です。
上記のように単一のパターンの検索の計算量をO(n)とした場合、検索パターン数をk（=l-m+1）とすると、複数パターンの場合、O(nk)となりますが、このアルゴリズムではO(n+k)となるようです。
以上のように文字列比較の計算量を見積もりましたが、l,nが20程度ではこれらのアルゴリズムを適用するコストのほうが大きくなりそうですね。
アルゴリズムの詳細はwikiくんに聞いてください。

お礼

ご回答ありがとうございます。
なるほど、そのようなアルゴリズムがあったのですか。確かに条件によっては比較回数を大幅に削減出来そうですが、実際の検索文字列には２バイト文字が含まれています。１バイト文字のみから構成される文字列と比べて性能が劣ることはありますか？

回答No.6

m-take0220

＞比較文字数が奇数の場合はちょっと面倒になりそうですね。

バッファを4バイトの倍数にしておけば、何も面倒なことはありません。
例えば5文字比較の場合、バッファは8バイト用意されていて、最初に全体を'\0'で初期化しておけば6～8バイト目はどのバッファでも'\0'なので比較の妨げにはなりません。

お礼

確かにおっしゃるとおりでした。その例ですと、全ての部分文字列に対して３バイト分余分に消費しますが、たとえ部分文字列が１００万個あったとしても3MBに過ぎませんね。GB単位のメモリを積んでいることを考えれば、その程度のオーバーヘッドより比較回数を３分の１に減らす方が効果が高いというわけですね。

回答No.5

trapezium

> 上記は説明のためにcharと書きましたが、実際は文字列はUnicodeで扱っています。char->TCHARと読み替えてください。

MS depend でしたか。
単純に次のロジックで、試しに適当な文字データで 1000000 くらい回してみましたが、ペア当り数 us というところです。MS でも同じでしょう。

int
wcscheck(wchar_t *s1, int l1, wchar_t *s2, int l2, int n)
{
int i, j, k;

for (i = 0; i <= l2 - n; i++) {
for (j = 0; j <= l1 - n; j++) {
for (k = 0; k < n && s2[i+k] == s1[j+k]; k++)
;
if (k == n)
return j;
}
}
return -1;
}

お礼

TCHARはMS独自の型でしたか。C++はMS以外の世界を知らないもので。
そんな簡潔に書けるんですね。恥ずかしながら無駄に長い40行程度のロジックを書いてしまいました。まあやろうとしていることは同じです。アルゴリズムはライブラリに頼りすぎて自分で書くということを長らくしてこなかったツケが出ています。こんな単純な標準関数がWin32APIやATLに用意されていないんですかね。色々とググってみてもそれらしい物がありませんでした。

回答No.4

m-take0220

私が処理するとしたら、ファイル名ごとに比較用データを持つクラスを作成します。
そのクラスが持つデータとして、

1. 比較文字数で細分化した部分文字列データ
(例)
4文字比較するなら、1文字目から4文字目の部分文字列、2文字目から5文字目の部分文字列、...
部分文字列作成時に、大文字小文字の変換やマルチバイト文字を途中で分断しないような処理をしておく。

2. 部分文字列の先頭文字によるテーブル
先頭文字ごとのテーブルを作成して、部分文字列を比較する際に総当たりしなくて済むようにする。
(例)
'B'から始まる部分文字列は1番目のみ、'A'から始まる部分文字列は2番目、4番目...
'D'から始まる部分文字列はない、といった情報テーブル

こういった前処理を行ったデータを比較すれば、結構早くなると思います。
が、それでもまだ遅い場合は、ちょっとトリッキーなことをします。

3. 部分文字列を格納するバッファを4バイトの倍数で確保するようにし、最初に'\0'で初期化しておく
なぜこのようなことをするかというと、比較を文字列ではなくlongで行うためです。
最近のほとんどのCPUは4バイトのデータを1命令で比較できます。文字列として比較する場合は、終端文字の検出が必要なため、1バイトごとに比較するしかないですが、前準備をしておけば、4バイトごとに比較が可能になり、その方が高速に比較できる可能性があります。

お礼

ご回答ありがとうございます。
部分文字列をあらかじめインデックス化しておくのですね。その処理に要する追加コストを上回る効率化が実現出来れば良いのですが。一度試してみて結果を報告します。

文字列を４バイト単位に区切ってlong型で比較するという発想はありませんでした。CPUのメカニズムに精通していないと分かりませんね。Unicodeであればlong１つ分で２文字になりますか。比較文字数が奇数の場合はちょっと面倒になりそうですね。知的好奇心が湧いてきたので、こちらも一度試してみることにします。

回答No.3

trapezium

#1 ですが補足として、

高速化としては char * だと multi-byte で面倒なので、事前に wchar_t や char32_t などの内部表現に変換しておく、同時に英小文字を大文字に変換しておく (全角も含むのか?) など処理しておけばやりやすいでしょう。

後は処理量によってはスレッド化すれば。

お礼

ご回答ありがとうございます。
上記は説明のためにcharと書きましたが、実際は文字列はUnicodeで扱っています。char->TCHARと読み替えてください。
おっしゃるとおり、事前準備により効率化出来ないか検討してみます。

回答No.2

titokani

比較対象の文字列が平均２０文字程度ということですから、私も力技で十分なのではと思います。

各文字が最初に出現する位置を覚えておく（メモリは使いますが）とかの方法も考えられますが、比較対象の文字数がもっと大きくないと、効果は薄いように思えます。

お礼

ご回答ありがとうございます。
もう少し事前準備を頑張ってみることにします。

回答No.1

trapezium

> 仮に１ペアのチェックの所要時間が10msとしても、トータルで約50秒かかることになります。

どんな環境なのか知りませんが、今時だと ms レベルは掛からないでしょう。
multi-lang をどう処理するかにも依るとは思いますが、普通に力技で実装してみて -pg でも付けて計測してみたらどうですか？