Algoritmo de coincidencia de cadenas Rabin Karp

Question

He visto este algoritmo de concordancia de cadenas Rabin Karp en los foros del sitio web y estoy interesado en intentar implementarlo, pero me preguntaba si alguien podría decirme por qué las variables ulong Q y ulong D son 100007 y 256 respectivamente: S? ¿Qué importancia tienen estos valores con ellos?

static void Main(string[] args) 
{ 
    string A = "String that contains a pattern."; 
    string B = "pattern"; 
    ulong siga = 0; 
    ulong sigb = 0; 
    ulong Q = 100007; 
    ulong D = 256; 
    for (int i = 0; i < B.Length; i++) 
    { 
     siga = (siga * D + (ulong)A[i]) % Q; 
     sigb = (sigb * D + (ulong)B[i]) % Q; 
    } 
    if (siga == sigb) 
    { 
     Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length))); 
     return; 
    } 
    ulong pow = 1; 
    for (int k = 1; k <= B.Length - 1; k++) 
     pow = (pow * D) % Q; 

    for (int j = 1; j <= A.Length - B.Length; j++) 
    { 
     siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q; 
     siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q; 
     if (siga == sigb) 
     { 
      if (A.Substring(j, B.Length) == B) 
      { 
       Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j), 
                    A.Substring(j, B.Length), 
                    A.Substring(j + B.Length))); 
       return; 
      } 
     } 
    } 
    Console.WriteLine("Not copied!"); 
} 

Answer 1

El algoritmo usa hash para una comparación rápida de cadenas. Q y D son números mágicos con los que el codificador probablemente llegó con un poco de prueba y error y dan un buen distribution de valores hash para este algoritmo en particular.

Puede ver estos tipos de números mágicos utilizados para hash en muchos lugares. El ejemplo siguiente es la definición descompilado de la función GetHashCode de un .NET 2.0 tipo de cadena:

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] 
public override unsafe int GetHashCode() 
{ 
    char* chrPointer = null; 
    int num1; 
    int num2; 
    fixed (string str = (string)this) 
    { 
     num1 = 352654597; 
     num2 = num1; 
     int* numPointer = chrPointer; 
     for (int i = this.Length; i > 0; i = i - 4) 
     { 
      num1 = (num1 << 5) + num1 + (num1 >> 27)^numPointer; 
      if (i <= 2) 
      { 
       break; 
      } 
      num2 = (num2 << 5) + num2 + (num2 >> 27)^numPointer + (void*)4; 
      numPointer = numPointer + (void*)8; 
     } 
    } 
    return num1 + num2 * 1566083941; 
} 

Aquí es otro ejemplo de un R # generado función de anulación GetHashCode para un tipo de muestra:

public override int GetHashCode() 
    { 
     unchecked 
     { 
      int result = (SomeStrId != null ? SomeStrId.GetHashCode() : 0); 
      result = (result*397)^(Desc != null ? Desc.GetHashCode() : 0); 
      result = (result*397)^(AnotherId != null ? AnotherId.GetHashCode() : 0); 
      return result; 
     } 
    } 

Answer 2

Acerca de los números mágicos La respuesta de Pablo es bastante clara.

En lo que respecta al código, la idea principal de Rabin Karp es realizar una comparación de hash entre una porción deslizante de la cuerda y el patrón.

El hash no se puede calcular cada vez en las subcadenas enteras, de lo contrario la complejidad de cálculo sería cuadrática O(n^2) en lugar de O(n) lineal.

Por lo tanto, se aplica una función rolling hash, como en cada iteración, solo se necesita un carácter para actualizar el valor hash de la subcadena.

tanto, vamos a comentar su código:

for (int i = 0; i < B.Length; i++) 
{ 
    siga = (siga * D + (ulong)A[i]) % Q; 
    sigb = (sigb * D + (ulong)B[i]) % Q; 
} 
if (siga == sigb) 
{ 
    Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length))); 
    return; 
} 

^ Esta pieza calcula el hash del patrón B (sigb), y el código hash de la subcadena inicial de A de la misma longitud de B. En realidad, no es completamente correcto porque el hash puede colisionar¹ por lo tanto, es necesario modificar la instrucción if: if (siga == sigb && A.Substring(0, B.Length) == B).

ulong pow = 1; 
for (int k = 1; k <= B.Length - 1; k++) 
    pow = (pow * D) % Q; 

^ Aquí está computado pow que es necesario llevar a cabo el hash a la rodadura.

for (int j = 1; j <= A.Length - B.Length; j++) 
{ 
    siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q; 
    siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q; 
    if (siga == sigb) 
    { 
     if (A.Substring(j, B.Length) == B) 
     { 
      Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j), 
                   A.Substring(j, B.Length), 
                   A.Substring(j + B.Length))); 
      return; 
     } 
    } 
} 

^ Por último, la cadena restante (es decir, desde el segundo carácter a extremo), se explora la actualización del valor hash de la A subcadena y en comparación con el hash de B (calculado al principio).

Si los dos hash son iguales, la subcadena y el patrón se comparan¹ y si son realmente iguales se devuelve un mensaje.

---

¹ Hash values can collide; por lo tanto, si dos cadenas tienen diferentes valores hash son definitivamente diferentes, pero si los dos hashes son iguales, pueden ser iguales o no.

Answer 3

que tienen un problema en la explicación de la función de cada línea de guión me puede dar explicación de la secuencia de comandos siguiente:

public static int[] RabinKarp(string A, string B) 
    { 
     List<int> retVal = new List<int>(); 
     ulong siga = 0; 
     ulong sigb = 0; 
     ulong Q = 100007; 
     ulong D = 256; 

     for (int i = 0; i < B.Length; ++i) 
     { 
      siga = (siga * D + (ulong)A[i]) % Q; 
      sigb = (sigb * D + (ulong)B[i]) % Q; 
     } 

     if (siga == sigb) 
      retVal.Add(0); 

     ulong pow = 1; 

     for (int k = 1; k <= B.Length - 1; ++k) 
      pow = (pow * D) % Q; 

     for (int j = 1; j <= A.Length - B.Length; ++j) 
     { 
      siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q; 
      siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q; 

      if (siga == sigb) 
      if (A.Substring(j, B.Length) == B) 
       retVal.Add(j); 
     } 

     return retVal.ToArray(); 
    }