効率的な部分文字列一致検出アルゴリズムの実装方法

質問

• string1とstring2の部分文字列一致を効率的に検出するアルゴリズムを実装する方法について解説します。
• 文字列の長さや処理時間を考慮しつつ、部分一致の判定を行うアルゴリズムを提案します。
• 英数字のみを対象として部分一致を判定する場合の処理方法についても考慮しています。

回答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

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