Как реализовать поиск Бойера-Мура для потоков

Question

Как бы я go о реализации Бойера-Мура поиска для потоков? Я понимаю, как реализовать это для данной строки, где мы знаем длину всей строки. Однако, что если мы не имеем представления о размере строки (, т.е. это поток байтов произвольной длины ).

Я пытаюсь реализовать это в PHP, поэтому любой код в PHP было бы полезно.

Вот реализация поиска Бойера-Мура, который у меня есть в PHP:

function BoyerMooreSearch($haystack, $needle) {
    $needleLen = strlen($needle);
    $haystackLen = strlen($haystack);
    $table = computeSkipTable($needle);

    for ($i = $needleLen - 1; $i < $haystackLen;) { 
        $t = $i;

        for ($j = $needleLen - 1; $needle[$j] == $haystack[$i]; $j--, $i--) { 
            if($j == 0) {
                return $i;
            }
        }

        $i = $t;

        if(array_key_exists($haystack[$i], $table)) {
            $i = $i + max($table[$haystack[$i]], 1);
        } else {
            $i += $needleLen;
        }
    }
    return false;
}

function computeSkipTable($string) {
    $len = strlen($string);
    $table = [];

    for ($i=0; $i < $len; $i++) { 
        $table[$string[$i]] = $len - $i - 1; 
    }

    return $table;
}

Это прекрасно работает, если мы дадим ему строку сена, такую ​​как "barfoobazquix" и строка иглы типа "foo", она вернет 3, как и ожидалось. Однако, что если входной стог сена был потоком, разделенным на 4 байта. Первый блок будет "barf", который не будет соответствовать, второй будет "ooba", который также не будет соответствовать, и так далее ...

В этом сценарии мы никогда не сможем найдите подстроку "foo" в любом из буферизованных фрагментов потока с текущей реализацией. Я изо всех сил стараюсь адаптировать текущую реализацию так, чтобы она работала, даже если строка поиска была разбита на несколько частей.

Answer 1

Обратите внимание, что вы когда-либо используете только $needleLen самые последние символы из потока. Таким образом, вы можете поддерживать скользящее окно, состоящее из $needleLen символов, и перемещать его по мере необходимости. Кроме того, $haystackLen теперь неизвестно и должно быть заменено проверками EOF.

Приведенный ниже код неэффективен, поскольку для скольжения окна всегда требуется O(n) независимо от того, скольким оно будет: n символов или просто 1. Чтобы достичь оптимальной сложности скольжения, $window должен быть реализован в виде кольцевого буфера символов.

// sample call
var_dump(BoyerMooreSearch(STDIN, 'foo'));

function BoyerMooreSearch($resource, $needle) {
    $needleLen = strlen($needle);
    $table = computeSkipTable($needle);

    // build the first window
    if (($window = buildWindow($resource, $needleLen)) === false) {
        // special case: the text is shorter than the pattern
        return false;
    }

    $i = 0;
    while (true) {
        // check for a match
        $j = $needleLen - 1;
        while ($j >= 0 && $needle[$j] == $window[$j]) {
            $j--;
        }
        if ($j < 0) {
            return $i;
        }

        // determine slide distance
        $t = $i;
        $last = substr($window, -1);
        if (array_key_exists($last, $table)) {
            $i = $i + max($table[$last], 1);
        } else {
            $i += $needleLen;
        }

        // slide the window
        if (($window = slideWindow($window, $resource, $i - $t)) === false) {
            return false;
        }
    }

    return false;
}

/**
 * Initializes the sliding window to length $len.
 *
 * @return string A string of length $len or false if the $resource contains
 * less than $len characters.
 */
function buildWindow ($resource, $len) {
    $result = '';
    while ($len--) {
        $result .= fgetc($resource);
    }
    return feof($resource) ? false : $result;
}

/**
 * Slides $window by $count positions into $resource.
 *
 * @return string The new window or false on EOF.
 */
function slideWindow(&$window, $resource, $count) {
    $window = substr($window, $count) // discard the first $count chars
        . fread($resource, $count);   // and read $count new chars
    return feof($resource) ? false : $window;
}