Haskell의 Knuth-Morris-Pratt 알고리즘

Question

Haskell의 Knuth-Morris-Pratt 알고리즘의 구현을 이해하는 데 어려움이 있습니다.

http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell

은 특히 나는 자동 장치의 구조를 이해하지 않습니다. 나는 "매듭 매듭"방법을 사용하여 그것을 구성한다는 것을 알고 있지만, 내게는 명확하지 않으며, 또한 그것이 왜 올바른 복잡성을 가져야하는지 모릅니다.

내가 알고 싶은 또 다른 사항은이 구현이 Aho-Corasick 알고리즘을 구현하기 위해 쉽게 일반화 될 수 있다고 생각하는지 여부입니다.

답변 해 주셔서 감사합니다.

Answer 1

그래서 여기가 알고리즘이다 : 그 사용

makeTable :: Eq a => [a] -> KMP a 
makeTable xs = table 
    where table = makeTable' xs (const table) 

makeTable' []  failure = KMP True failure 
makeTable' (x:xs) failure = KMP False test 
    where test c = if c == x then success else failure c 
      success = makeTable' xs (next (failure x)) 

,의는 "shoeshop"에 대한 구성 테이블을 살펴 보자 :

makeTable "shoeshop" = table0 

table0 = makeTable' "shoeshop" (const table0) 
     = KMP False test0 

test0 c = if c == 's' then success1 else const table0 c 
     = if c == 's' then success1 else table0 

success1 = makeTable' "hoeshop" (next (const table0 's')) 
     = makeTable' "hoeshop" (next table0) 
     = makeTable' "hoeshop" test0 
     = KMP False test1 

test1 c = if c == 'h' then success2 else test0 c 

success2 = makeTable' "oeshop" (next (test0 'h')) 
     = makeTable' "oeshop" (next table0) 
     = makeTable' "oeshop" test0 
     = makeTable' "oeshop" test0 
     = KMP False test2 

test2 c = if c == 'o' then success3 else test0 c 

success3 = makeTable' "eshop" (next (test0 'o')) 
     = makeTable' "eshop" (next table0) 
     = makeTable' "eshop" test0 
     = KMP False test3 

test3 c = if c == 'e' then success4 else test0 c 

success4 = makeTable' "shop" (next (test0 'e')) 
     = makeTable' "shop" (next table0) 
     = makeTable' "shop" test0 
     = KMP False test4 

test4 c = if c == 's' then success5 else test0 c 

success5 = makeTable' "hop" (next (test0 's')) 
     = makeTable' "hop" (next success1) 
     = makeTable' "hop" test1 
     = KMP False test5 

test5 c = if c == 'h' then success6 else test1 c 

success6 = makeTable' "op" (next (test1 'h')) 
     = makeTable' "op" (next success2) 
     = makeTable' "op" test2 
     = KMP False test6 

test6 c = if c == 'o' then success7 else test2 c 

success7 = makeTable' "p" (next (test2 'o')) 
     = makeTable' "p" (next success3) 
     = makeTable' "p" test3 
     = KMP False test7 

test7 c = if c == 'p' then success8 else test3 c 

success8 = makeTable' "" (next (test3 'p')) 
     = makeTable' "" (next (test0 'p')) 
     = makeTable' "" (next table0) 
     = makeTable' "" test0 
     = KMP True test0 

주 success5은 소비의는 '초기를 되돌아하기 위해 사용하는 방법 패턴의 's'.

이제는 isSubstringOf2 "shoeshop" $ cycle "shoe" 일 때 어떤 일이 발생하는지 살펴보십시오.

은 test7는 'P'를 일치에 실패 할 경우, 그것은 '전자'와 일치하려고 다시 test3로 떨어질 것으로보기 때문에 success4, success5, success6 및 success7 무한히을 통해 그 우리주기.