我将如何实现流的Boyer-Moore Search?我知道如何在给定的字符串中实现这一点,因为我们知道整个字符串的长度。但是,如果我们不知道字符串的大小(即,它是任意长度的字节流),该怎么办。
我正在尝试在PHP中实现此功能,因此PHP中的任何代码都会有所帮助。
这是我在PHP中使用的Boyer-Moore Search的实现:
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"
。我正在努力适应当前的实现,即使将搜索字符串分成多个块也可以正常工作。
注意,您只能使用流中的$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;
}