¿Qué pasa con mi implementación del algoritmo KMP?

Question

static void Main(string[] args) 
{ 
    string str = "ABC ABCDAB ABCDABCDABDE";//We should add some text here for 
              //the performance tests. 

    string pattern = "ABCDABD"; 


    List<int> shifts = new List<int>(); 

    Stopwatch stopWatch = new Stopwatch(); 

    stopWatch.Start(); 
    NaiveStringMatcher(shifts, str, pattern); 
    stopWatch.Stop(); 
    Trace.WriteLine(String.Format("Naive string matcher {0}", stopWatch.Elapsed)); 

    foreach (int s in shifts) 
    { 
     Trace.WriteLine(s); 
    } 

    shifts.Clear(); 
    stopWatch.Restart(); 

    int[] pi = new int[pattern.Length]; 
    Knuth_Morris_Pratt(shifts, str, pattern, pi); 
    stopWatch.Stop(); 
    Trace.WriteLine(String.Format("Knuth_Morris_Pratt {0}", stopWatch.Elapsed)); 

    foreach (int s in shifts) 
    { 
     Trace.WriteLine(s); 
    } 

    Console.ReadKey(); 
} 

static IList<int> NaiveStringMatcher(List<int> shifts, string text, string pattern) 
{ 
    int lengthText = text.Length; 
    int lengthPattern = pattern.Length; 

    for (int s = 0; s < lengthText - lengthPattern + 1; s++) 
    { 
     if (text[s] == pattern[0]) 
     { 
      int i = 0; 
      while (i < lengthPattern) 
      { 
       if (text[s + i] == pattern[i]) 
        i++; 
       else break; 
      } 
      if (i == lengthPattern) 
      { 
       shifts.Add(s);       
      } 
     } 
    } 

    return shifts; 
} 

static IList<int> Knuth_Morris_Pratt(List<int> shifts, string text, string pattern, int[] pi) 
{ 

    int patternLength = pattern.Length; 
    int textLength = text.Length;    
    //ComputePrefixFunction(pattern, pi); 

    int j; 

    for (int i = 1; i < pi.Length; i++) 
    { 
     j = 0; 
     while ((i < pi.Length) && (pattern[i] == pattern[j])) 
     { 
      j++; 
      pi[i++] = j; 
     } 
    } 

    int matchedSymNum = 0; 

    for (int i = 0; i < textLength; i++) 
    { 
     while (matchedSymNum > 0 && pattern[matchedSymNum] != text[i]) 
      matchedSymNum = pi[matchedSymNum - 1]; 

     if (pattern[matchedSymNum] == text[i]) 
      matchedSymNum++; 

     if (matchedSymNum == patternLength) 
     { 
      shifts.Add(i - patternLength + 1); 
      matchedSymNum = pi[matchedSymNum - 1]; 
     } 

    } 

    return shifts; 
} 

¿Por qué mi implementación del algoritmo KMP funciona más lento que el algoritmo Naive String Matching?

Answer 1

El algoritmo KMP tiene dos fases: primero crea una tabla y luego realiza una búsqueda, dirigida por el contenido de la tabla.

El algoritmo ingenuo tiene una fase: realiza una búsqueda. Hace la búsqueda mucho menos eficiente en el peor de los casos que la fase de búsqueda de KMP.

Si el KMP es más lento que el algoritmo ingenuo, entonces es probablemente porque la construcción de la tabla le lleva más tiempo de lo que se necesita simplemente buscar la cadena ingenuamente en primer lugar. La coincidencia ingeniosa de cadenas suele ser muy rápida en cadenas cortas. Existe una razón por la cual no utilizamos algoritmos de fantasía como KMP dentro de las implementaciones BCL de búsqueda de cadenas. Para cuando configuraste la tabla, podrías haber hecho media docena de búsquedas de cadenas cortas con el algoritmo ingenuo.

KMP sólo es una victoria si tiene enormes cadenas y que está haciendo un montón de búsquedas que le permiten volver a utilizar una tabla ya incorporado. Debes amortizar el enorme costo de construir la tabla haciendo muchas búsquedas usando esa tabla.

Y también, el algoritmo ingenuo solo tiene un mal rendimiento en escenarios extraños e improbables. La mayoría de las personas busca palabras como "Londres" en cadenas como "Buckingham Palace, London, England", y no busca cadenas como "BANANANANANANA" en cadenas como "BANAN BANAN BANBANANA BANAN BANAN BANANAN BANANANANANANANANAN ...". El algoritmo de búsqueda ingenuo es óptimo para el primer problema y altamente subóptimo para el último problema; pero tiene sentido optimizar para el primero, no para el segundo.

Otra forma de expresarlo: si la cadena buscada es de longitud w y la cadena buscada es de longitud n, entonces KMP es O (n) + O (w). El algoritmo Naive es el peor caso O (nw), el mejor caso O (n + w). ¡Pero eso no dice nada sobre el "factor constante"! El factor constante del algoritmo KMP es mucho más grande que el factor constante del algoritmo ingenuo. El valor de n tiene que ser muy grande, y el número de coincidencias parciales subóptimas tiene que ser muy grande, para que el algoritmo KMP gane sobre el algoritmo ingenuo extremadamente rápido.

Que se ocupa de los problemas de complejidad algorítmica. Su metodología tampoco es muy buena, y eso podría explicar sus resultados. Recuerde, la primera vez que ejecuta el código, la fluctuación de fase debe jit la IL en el código de ensamblaje. Eso puede tomar más tiempo que ejecutar el método en algunos casos. Realmente debería ejecutar el código unos cientos de miles de veces en un ciclo, descartando el primer resultado y tomando un promedio de los tiempos del resto.

Si realmente quieres saber qué está pasando, debes usar un generador de perfiles para determinar cuál es el punto caliente. De nuevo, asegúrese de estar midiendo la ejecución posterior al jit, no la ejecución donde se juntó el código, si desea obtener resultados que no estén sesgados por el tiempo de jit.

Answer 2

Su ejemplo es demasiado pequeño y no tiene suficientes repeticiones del patrón donde KMP evita el retroceso.

En algunos casos, KMP puede ser más lento que la búsqueda normal.

Answer 3

Implementación simple de KMPSubstringSearch.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/KMPSubstringSearch.cs

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace AlgorithmsMadeEasy 
{ 
    class KMPSubstringSearch 
    { 
     public void KMPSubstringSearchMethod() 
     { 
      string text = System.Console.ReadLine(); 
      char[] sText = text.ToCharArray(); 

      string pattern = System.Console.ReadLine(); 
      char[] sPattern = pattern.ToCharArray(); 

      int forwardPointer = 1; 
      int backwardPointer = 0; 

      int[] tempStorage = new int[sPattern.Length]; 
      tempStorage[0] = 0; 

      while (forwardPointer < sPattern.Length) 
      { 
       if (sPattern[forwardPointer].Equals(sPattern[backwardPointer])) 
       { 
        tempStorage[forwardPointer] = backwardPointer + 1; 
        forwardPointer++; 
        backwardPointer++; 
       } 
       else 
       { 
        if (backwardPointer == 0) 
        { 
         tempStorage[forwardPointer] = 0; 
         forwardPointer++; 
        } 
        else 
        { 
         int temp = tempStorage[backwardPointer]; 
         backwardPointer = temp; 
        } 

       } 
      } 

      int pointer = 0; 
      int successPoints = sPattern.Length; 
      bool success = false; 
      for (int i = 0; i < sText.Length; i++) 
      { 
       if (sText[i].Equals(sPattern[pointer])) 
       { 
        pointer++; 
       } 
       else 
       { 
        if (pointer != 0) 
        { 
         int tempPointer = pointer - 1; 
         pointer = tempStorage[tempPointer]; 
         i--; 
        } 
       } 

       if (successPoints == pointer) 
       { 
        success = true; 
       } 
      } 

      if (success) 
      { 
       System.Console.WriteLine("TRUE"); 
      } 
      else 
      { 
       System.Console.WriteLine("FALSE"); 
      } 
      System.Console.Read(); 
     } 
    } 
} 

/* 
* Sample Input 
abxabcabcaby 
abcaby 
*/