日本語
日本語
素朴なアルゴリズムは、テキストの特定のパターン文字列の検索によく使用される基本的で直感的な文字列マッチング方法です。アルゴリズムは、テキストとパターンの文字列をテキストの最初の文字から1つずつ比較して、一致する位置またはテキストの終わりが見つかったかどうかを判断します。
以下は、PHPを使用して実装されたナイーブストリングマッチングアルゴリズムのサンプルコードです。
function naive_search($text, $pattern) {
$n = strlen($text);
$m = strlen($pattern);
for ($i = 0; $i <= $n - $m; $i++) {
$j = 0;
while ($j < $m && $text[$i + $j] == $pattern[$j]) {
$j++;
}
if ($j == $m) {
return $i;
}
}
return -1;
}
関数は2つの文字列パラメーターを受け入れ、$テキストは検索するテキスト、$パターンは一致する必要があるパターン文字列です。アルゴリズムは、二重層ループを介して文字ごとにテキストとパターンの文字を比較します。試合が成功すると、最初の発生位置を返し、一致しない場合は-1を返します。
関数では、変数$ nと$ mは、それぞれテキストとパターンの長さを表します。外側のループは、テキストのスキャン範囲を制御して、残りの部分がパターンの長さと一致するのに十分であることを確認します。内側のループは、マッチが不一致であるか、試合が完了することがわかったまで、テキストとパターンの文字をキャラクターと比較します。試合が成功したときに開始インデックスを返します。そうしないと、ループが終了すると-1が返されます。
ナイーブアルゴリズムは、テキストにサブストリングが存在するかどうかを検出するなど、単純な文字列検索によく使用されます。サンプルコードは次のとおりです。
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // 出力 7
この例では、$テキストはターゲット文字列であり、$パターンは見つかります。関数の戻り値は、サブストリングが最初に表示される位置のインデックスです。
単純な文字列検索に加えて、素朴なアルゴリズムは、正規表現ベースの検索などのパターンマッチングタスクを支援することもできます。次の例は、HTMLコードですべてのリンクを見つける方法を示しています。
$html = "<html><body><a href='http://example.com'>Example</a></body></html>";
$pattern = "<a href='(.*?)'>(.*?)</a>";
preg_match_all("/$pattern/s", $html, $matches);
print_r($matches); // 出力匹配结果
この例では、正規表現パターンを使用して、HTMLのすべてのリンクを見つけ、一致する配列の結果を返します。
ナイーブアルゴリズムの時間の複雑さはO（nm）です。ここで、nはテキストの長さ、mはパターンの長さです。パフォーマンスは高度なアルゴリズムのパフォーマンスほど良くありませんが、その構造はシンプルで理解しやすく実装できます。短いモード文字列検索の場合、パフォーマンスは許容されます。ただし、モード文字列の長さが増加すると、効率が大幅に低下するため、通常、より効率的な文字列検索アルゴリズムが実際のアプリケーションで選択されます。
最も基本的な文字列マッチングアルゴリズムとして、ナイーブアルゴリズムには、シンプルで直感的な実装の利点があり、基本的なパターン検索タスクに適しています。テキストとパターンを文字ごとに比較して、明確なプロセスを実現します。効率の点での制限にもかかわらず、多くの実用的なアプリケーション、特に短いモード文字列を扱うシナリオにとっては依然として実用的な価値があります。
