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

KMP 알고리즘의 구현이 Naive String Matching 알고리즘보다 느린 이유는 무엇입니까?

Answer 1

KMP 알고리즘은 두 단계로 구성됩니다. 먼저 테이블을 작성한 다음 테이블의 내용에 따라 검색을 수행합니다.

순진 알고리즘은 검색을 수행하는 한 단계가 있습니다. 이 검색은 KMP 검색 단계보다 최악의 경우 보다 훨씬 효율적으로 검색하지 않습니다.

KMP가 순진 알고리즘보다 느린 경우 일 것입니다. 테이블을 작성하면 처음부터 순진하게 문자열을 검색하는 것보다 시간이 많이 걸리기 때문입니다. 순진한 문자열 일치는 보통 매우 짧은 문자열에 빠릅니다. 문자열 검색의 BCL 구현에서 KMP와 같은 멋진 바지 알고리즘을 사용하지 않는 이유가 있습니다. 테이블을 설정할 때까지 순진한 알고리즘으로 짧은 문자열 검색을 할 수있었습니다. 당신이 엄청난 문자열이 있고 많은 당신은 이미 만들어진 테이블을 다시 사용할 수 있도록 검색을하고 있다면

KMP는 승리이다. 테이블을 사용하여 많은 검색을 수행하여 테이블을 구축하는 데 드는 막대한 비용을 상각해야합니다.

또한 단순한 알고리즘은 기괴하고 가능성이없는 시나리오에서만 성능이 좋지 않습니다. 대부분의 사람들은 "버킹엄 궁전, 런던, 영국"과 같은 문자열에서 "런던"과 같은 단어를 검색하고 "BANAN BANBAN BANBANANA BANAN BANAN BANANAN BANANANANANANANANANAN ..."과 같은 문자열에서 "BANANANANANANA"와 같은 문자열을 검색하지 않습니다. 순진 검색 알고리즘은 첫 번째 문제에 대해 최적이고 후자의 문제에 대해 매우 차선책입니다. 후자가 아니라 전자를 위해 최적화하는 것이 이치에 맞습니다.

또 다른 방법 : 검색된 문자열의 길이가 w이고 검색된 문자열의 길이가 n 인 경우 KMP는 O (n) + O (w)입니다. Naive 알고리즘은 최악의 경우 O (nw), 최상의 경우 O (n + w)입니다. 그러나 그것은 "일정한 요인"에 관해서는 아무것도 말하지 않습니다! KMP 알고리즘의 상수 인자는 순진 알고리즘의 상수 인자보다 훨씬 큽니다. n의 값은 엄청나게 커야하며, KMP 알고리즘이 놀랍도록 빠르고 순진한 알고리즘을 이기기 위해서는 준 최적 부분 일치의 수가 너무 많아야합니다.

알고리즘의 복잡성 문제를 다루고 있습니다. 귀하의 방법론 또한 그리 좋지 않으며 결과가 설명 될 수도 있습니다. 코드를 처음 실행할 때 시간을 기억하십시오. 지터가 IL을 어셈블리 코드로 jit해야합니다. 경우에 따라 방법을 실행하는 것보다 시간이 오래 걸릴 수 있습니다.. 루프에서 수십만 번 코드를 실행해야하고, 첫 번째 결과를 무시하고 나머지 시간의 평균을 취해야합니다.

실제로 무슨 일이 일어나고 있는지 알고 싶다면 프로파일 러를 사용하여 핫스팟이 무엇인지 판단해야합니다. 다시 말하지만, jit 시간에 왜곡되지 않은 결과를 얻고 싶다면 코드가 실행되는 위치가 아닌 실행 후 작업을 측정해야합니다.

Answer 2

예제가 너무 작고 KMP가 역 추적을 피하는 패턴을 충분히 반복하지 않습니다.

KMP는 경우에 따라 정상 검색보다 느려질 수 있습니다.

Answer 3

간단한 KMPSubstringSearch 구현. 순진 함수가 온다 최초의 솔루션이기 때문에, 처음에 올바른 보이는 기능입니다 @minitech

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 
*/