Реализация алгоритма Рабина-Карпа с PHP - PullRequest
Новая
       29

Реализация алгоритма Рабина-Карпа с PHP

2 голосов
/ 26 марта 2012

Привет! Я пишу PHP-класс для реализации алгоритма Рабина-Карпа.У меня проблема с повторным хэшированием.Этот код не включает в себя соответствующую часть символов.Мне пришлось остановиться, поскольку он никогда не совпадал с хэш-кодами из-за проблемы с повторным хешированием.Кто-нибудь, пожалуйста, помогите мне разобраться.

<?php
 class RabinKarp
 {
    /** 
    * @var String
    */ 
    private $pattern ;
    private $patternHash ;
    private $text ;
    private $previousHash ;

    /** 
    * @var Integer
    */ 
    private $radix ;
    private $prime ;
    private $position ;

    /** 
    * Constructor 
    *
    * @param String $pattern - The pattern
    *
    */ 
    public function __construct($pattern) 
    {
        $this->pattern = $pattern;
        $this->radix = 256;
        $this->prime = 100007;
        $this->previousHash = "";
        $this->position = 0;
        $this->patternHash = $this->generateHash($pattern);
    }

    private function generateHash($key)
    {
        $charArray = str_split($key);
        $hash = 0;
        foreach($charArray as $char)
        {
             $hash = ($this->radix * $hash + ord($char)) % $this->prime;
        }

        return $hash;
    }

    public function search($character)
    {
        $this->text .= $character;
        if(strlen($this->text) < strlen($this->pattern))
        {
            return false;
        }
        else
        {
            $txtHash = 0;
            echo $this->previousHash . "<br/>";
            if(empty($this->previousHash))
            {
                $txtHash = $this->generateHash($this->text);
                $this->previousHash = $txtHash;
                $this->position = 0;
            }
            else
            {
                // The issue is here 
                $charArray = str_split($this->text);
                $txtHash = (($txtHash  + $this->prime) - $this->radix * strlen($this->pattern) * ord($charArray[$this->position]) % $this->prime) % $this->prime;
                $txtHash = ($txtHash * $this->radix + ord($character)) % $this->prime; 

                $this->previousHash = $txtHash;
            }

            if($txtHash == $this->patternHash)
            {
                echo "Hash Match found";
            }
        }

    }

 }

$x = new RabinKarp("ABC");
$x->search("Z");
$x->search("A");
$x->search("B");
$x->search("C");
?>

Спасибо.

1 Ответ

1 голос
/ 26 марта 2012

Значение, добавляемое в хеш с помощью символа (c для краткости), которое вы удаляете, равно 

ord(c) * radix^(length(pattern)-1)

, поскольку символ добавляет ord(c), когда он впервые входит в соответствующее окно, ихэш - следовательно, также его вклад - умножается на radix для каждого из length(pattern)-1 символов, входящих в соответствующее окно, пока c наконец не покинет его.

Но вы вычитаете ord(c) * radix * length(pattern)

$charArray = str_split($this->text);
$txtHash = (($txtHash  + $this->prime)
             - $this->radix * strlen($this->pattern)
             * ord($charArray[$this->position]) % $this->prime)
           % $this->prime;
$txtHash = ($txtHash * $this->radix + ord($character)) % $this->prime;

Кроме того, в расчете вы используете переменную $txtHash, которую вы установили в 0, которая должна быть $this->previousHash, и вы должны увеличить позицию текста.

В принципе, 

$charArray = str_split($this->text);
$txtHash = (($this->previousHash  + $this->prime)
             - pow($this->radix, strlen($this->pattern)-1)
             * ord($charArray[$this->position]) % $this->prime)
           % $this->prime;
$txtHash = ($txtHash * $this->radix + ord($character)) % $this->prime;

$this->previousHash = $txtHash;
$this->position += 1;

- это то, что вам нужно сделать.

Но если шаблон не очень короткий, pow($this->radix,strlen($this->pattern)-1) будет переполнен, поэтому вам придется заменить pow($this-radix, strlen($this->pattern)-1) на модульнуюфункция возведения в степень 

function mod_pow($base,$exponent,$modulus)
{
    $aux = 1;
    while($exponent > 0) {
        if ($exponent % 2 == 1) {
            $aux = ($aux * $base) % $modulus;
        }
        $base = ($base * $base) % $modulus;
        $exponent = $exponent/2;
    }
    return $aux;
}

(она все еще может переполняться, если $modulus, то есть $this->prime здесь, слишком велико).Соответствующая строка кода становится 

$txtHash = (($this->previousHash  + $this->prime)
             - mod_pow($this->radix, strlen($this->pattern)-1, $this->prime)
             * ord($charArray[$this->position]) % $this->prime)
           % $this->prime;

Тогда у вас потенциально огромная неэффективность 

$this->text .= $character;
...
    $charArray = str_split($this->text);

Если строка становится длинной, конкатенация и разбиение могут занять много времени (неуверен, как PHP реализует строки и строковые операции, но они, вероятно, не постоянное время).Вероятно, вам следует оставить только соответствующую часть строки, то есть удалить первый символ после пересчета хеша.

...