PHP の文字列マッチング アルゴリズムにおける Boyer-Moore アルゴリズムの動作原理と応用シナリオ。

Boyer-Moore アルゴリズムは、テキスト検索、エディタ、コンパイラ、さまざまなパターン マッチング ツールで広く使用されている効率的な文字列マッチング アルゴリズムです。この記事では、Boyer-Moore アルゴリズムがどのように機能するのかを紹介し、具体的なコード例を示します。

1. 動作原理
Boyer-Moore アルゴリズムは、検索対象のテキストの末尾から照合を開始し、パターン文字列とテキスト文字列の文字を逆比較します。これは、悪い文字ルールと良い接尾辞ルールという 2 つのヒューリスティック ルールを利用します。

不正な文字ルール:
文字の不一致が発生すると、アルゴリズムは不正な文字の位置 (パターン文字列の最後の位置) に基づいてパターン文字列を後方にスライドさせ、不正な文字が発生します。整列します。

適切なサフィックス ルール:
文字の不一致が発生した場合、アルゴリズムは、適切なサフィックスが揃うように、適切なサフィックスの出現位置と長さに応じてパターン文字列を後方にスライドさせます。適切なサフィックスは、テキスト文字列と一致するパターン文字列内のサフィックスです。

Boyer-Moore アルゴリズムはパターン文字列を継続的に移動し、一致しない文字をスキップするため、比較の数が大幅に削減され、マッチング効率が向上します。

2. アプリケーション シナリオ
Boyer-Moore アルゴリズムは、他の一般的な文字列一致アルゴリズム (たとえば、これには明らかな利点があります。

たとえば、テキスト処理、検索エンジン、コンパイラでは、キーワード、変数名、または特定の文字列を効率的に検索する必要があります。 Boyer-Moore アルゴリズムは、テキスト内で一致する可能性のある位置を迅速に特定できるため、検索プロセスが高速化されます。

以下は、文字列マッチングに Boyer-Moore アルゴリズムを使用する方法を示す簡単な PHP サンプル コードです:

<?php

function boyerMoore($text, $pattern) {
  $textLength = strlen($text);
  $patternLength = strlen($pattern);
  $lastOccurrence = array();
  
  // 初始化坏字符的位置表
  for ($i = 0; $i < $patternLength; $i++) {
    $lastOccurrence[$pattern[$i]] = $i;
  }
  
  $offset = 0;
  while ($offset <= $textLength - $patternLength) {
    // 从末尾开始匹配
    for ($j = $patternLength - 1; $j >= 0 && $pattern[$j] == $text[$offset + $j]; $j--);
    
    if ($j < 0) {
      // 找到匹配
      return $offset;
    } else {
      // 根据坏字符规则和好后缀规则计算滑动距离
      
      // 坏字符规则
      $badCharDist = $j - $lastOccurrence[$text[$offset + $j]];
      
      // 好后缀规则
      $goodSuffixDist = 0;
      if ($j < $patternLength - 1) {
        $goodSuffixDist = $moveBy = $patternLength - $j;
        for ($k = $j + 1; $k < $patternLength - 1; $k++) {
          if ($pattern[$k] == $pattern[$k - $j - 1]) {
            $goodSuffixDist--;
          }
        }
      }
      
      // 取最大距离
      $offset += max($badCharDist, $goodSuffixDist);
    }
  }
  
  // 未找到匹配
  return -1;
}

// 示例用法

$text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
$pattern = "dolor";

$result = boyerMoore($text, $pattern);
if ($result == -1) {
  echo "未找到匹配的字符串";
} else {
  echo "匹配的字符串位置：".$result;
}

?>

上記のサンプル コードでは、文字列 $text をテキスト文字列にします。 とパターン文字列 $pattern が boyerMoore 関数に渡され、関数は一致する位置を返します。一致する文字列が見つからない場合、戻り結果は -1 です。

概要:
Boyer-Moore アルゴリズムは、不正な文字ルールと適切な接尾辞ルールを適用することにより、効率的な文字列マッチングを実現します。大規模なテキスト検索で優れたパフォーマンスを発揮し、特に長いパターン文字列や大きな文字セットの処理に適しています。実際のアプリケーション シナリオでは、Boyer-Moore アルゴリズムを使用して文字列マッチングを迅速に実行し、検索とマッチングの効率を向上させることができます。

以上がPHP の文字列マッチング アルゴリズムにおける Boyer-Moore アルゴリズムの動作原理と応用シナリオ。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。