日本語
日本語
ナイーブアルゴリズムは、主にパターン検索に使用される基本的で一般的に使用される文字列マッチング方法です。核となるアイデアは、テキスト文字列の開始位置から開始し、文字で文字ごとにテキスト文字列の文字とパターン文字列が同じかどうかを比較することです。一致する場合は、正確な一致したサブストリングまたはテキストトラバーサルが見つかるまで、後続の文字を比較し続けます。
以下は、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 $に値を割り当てます。外側のループは、テキスト文字列の最初の文字とループの最初の文字から最大$ nm $に始まり、その後の比較がテキストの長さを超えないようにします。
内部ループは、テキストとパターンの文字列を文字ごとに比較するために使用され、$ j $は一致すると増加します。 $ j $が$ m $に等しい場合、完全な一致が見つかり、一致開始位置が返されます。
トラバーサルの終了時に一致が見つからない場合、関数は-1を返します。
素朴なアルゴリズムは、主に、テキストに指定されたサブストリングが含まれているかどうかを見つけるなど、基本的な文字列マッチングの問題で使用されます。例は次のとおりです。
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // 出力 7
この例では、この関数は、テキスト内のサブストリング「世界」の位置を正常に見つけ、7は戻り値です。
基本的な文字列マッチングに加えて、正規表現マッチング、HTMLタグ検索、その他のシナリオなど、パターン検索では素朴なアルゴリズムも使用できます。次の例は、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); // 出力匹配结果
この例では、正規表現とPHPビルトイン関数を使用して、HTMLでリンクタグを抽出し、パターン検索の実際のアプリケーションを示しています。
ナイーブアルゴリズムの時間の複雑さは$ o（nm）$です。ここで、$ n $はテキストの長さ、$ m $はパターン長です。その効率は比較的低いですが、そのシンプルで直感的な実装により、短いモード文字列ではパフォーマンスが許容されます。より長いパターン文字列を扱う場合、パフォーマンスを改善するために、より効率的なマッチングアルゴリズムを考慮する必要があります。
素朴なアルゴリズムは、基本的なパターン検索メカニズムの開始と理解に適した、シンプルで効果的な文字列マッチング方法です。この記事では、アルゴリズムの原則、コード実装、アプリケーションシナリオをPHPの例を通じて詳細に説明し、読者が文字列のマッチングをマスターする実用的なリファレンスを提供します。アルゴリズムにはパフォーマンスの制限がありますが、理解と実装の容易さにより、一部のシナリオでは依然として役立ちます。
