Implementierung von Rabin-Karp-Algorithmus mit PHP

Question

Hi Ich schreibe eine PHP-Klasse, Rabin-Karp-Algorithmus zu implementieren. Ich habe Probleme mit dem Re-Hashing-Teil. Dieser Code enthält keinen übereinstimmenden Teil der Zeichen. Ich musste aufhören, da es aufgrund des Problems mit dem Hashing nie zu Hash-Codes passte. Jemand bitte hilf mir es herauszufinden.

<?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"); 
?> 

Vielen Dank.

Answer 1

Der Wert trugen zum Hash durch das Zeichen (c für Kürze) Sie entfernen, ist

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

da ein Zeichen ord(c) beiträgt, wenn er zuerst das Fenster Anpassung eintritt, und der Hash - daher seine auch Beitrag - wird mit für jeden der length(pattern)-1 Zeichen multipliziert, die das passende Fenster betreten, bis c schließlich es verlässt.

Aber Sie subtrahieren 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; 

Zusätzlich ist bei der Berechnung die Variable $txtHash verwenden, die Sie auf 0 gesetzt haben, die $this->previousHash sein sollte, und Sie müssen den Text Lageinkrement .

Grundsätzlich

$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; 

ist, was Sie zu tun haben.

Aber es sei denn, das Muster ist sehr kurz, pow($this->radix,strlen($this->pattern)-1) überlaufen, so dass Sie pow($this-radix, strlen($this->pattern)-1) mit einem modularen Exponentiationsfunktion

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; 
} 

(dies kann noch Überlauf, wenn $modulus ersetzen müssen, dass $this->prime hier ist, ist zu groß). Die entsprechende Codezeile wird

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

Dann haben Sie eine potenziell große Ineffizienz

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

Wenn die Zeichenfolge lang wird, die Verkettung und die Aufspaltung viel Zeit in Anspruch nehmen (nicht sicher, wie PHP implementiert Strings und String-Operationen, aber sie sind wahrscheinlich nicht konstante Zeit). Sie sollten wahrscheinlich nur den relevanten Teil der Zeichenkette behalten, d. H. Das erste Zeichen nach der Neuberechnung des Hashes löschen.