함수 프로그래밍에서 슬라이딩 윈도우 일치

Question

텍스트 파일에서 단어를 일치시키기 위해 슬라이딩 윈도우 알고리즘을 구현하려고합니다. 나는 절차 적 배경에서 왔고 Erlang과 같은 기능 언어로 이것을 수행하려는 나의 첫 시도는 시간 O (n^2) (또는 그 이상)를 요구하는 것으로 보인다. 어떻게 이것을 기능적 언어로 할 수 있을까요?

-module(test). 
-export([readText/1,patternCount/2,main/0]). 

readText(FileName) -> 
    {ok,File} = file:read_file(FileName), 
    unicode:characters_to_list(File). 

patternCount(Text,Pattern) -> 
    patternCount_(Text,Pattern,string:len(Pattern),0). 

patternCount_(Text,Pattern,PatternLength,Count) -> 
    case string:len(Text) < PatternLength of 
     true -> Count; 
     false -> 
      case string:equal(string:substr(Text,1,PatternLength),Pattern) of 
       true -> 
        patternCount_(string:substr(Text,2),Pattern,PatternLength,Count+1); 
       false -> 
        patternCount_(string:substr(Text,2),Pattern,PatternLength,Count) 
      end 
    end. 

main() -> 
    test:patternCount(test:readText("file.txt"),"hello"). 

Answer 1

이 알고리즘을 기능적 언어로 구현하는 방법에 대해 질문을 많이하지만, 언어를 사용하는 것이 가장 바람직합니다. 내 대답은 따라서 Erlang에 중점을두고 예제 코드를 제공합니다.

먼저 patternCount과 patternCount_ 기능을 별도로 보유 할 필요가 없습니다. 대신, 당신은 단지 다른 arities뿐만 아니라 같은 arity의 여러 절과 함께 여러 개의 patternCount 기능을 가질 수 있습니다.

patternCount(Text,Pattern) -> 
    patternCount(Text,Pattern,length(Pattern),0). 

patternCount(Text,Pattern,PatternLength,Count) -> 
    case length(Text) < PatternLength of 
     true -> Count; 
     false -> 
      case string:equal(string:substr(Text,1,PatternLength),Pattern) of 
       true -> 
        patternCount(string:substr(Text,2),Pattern,PatternLength,Count+1); 
       false -> 
        patternCount(string:substr(Text,2),Pattern,PatternLength,Count) 
      end 
    end. 

다음으로, patternCount/4 기능의 멀티 레벨 들여 쓰기는 "코드 냄새"입니다 : 첫째, 계정에 그것을 적용하려면 기능을 다시, 또한 length/1 내장 함수와 string:len/1에 전화를 대체 할 수 더 잘할 수 있음을 나타냅니다. 의 여러 조항에 해당 기능을 분할하자

patternCount(Text,Pattern,PatternLength,Count) when length(Text) < PatternLength -> 
    Count; 
patternCount(Text,Pattern,PatternLength,Count) -> 
    case string:equal(string:substr(Text,1,PatternLength),Pattern) of 
     true -> 
      patternCount(string:substr(Text,2),Pattern,PatternLength,Count+1); 
     false -> 
      patternCount(string:substr(Text,2),Pattern,PatternLength,Count) 
    end. 

첫 번째 절은 두 번째 절은 일치를 찾는 동안 더 이상 일치, 수 없음을 감지 가드를 사용합니다. 이제 Erlang의 내장 매칭을 사용하기 위해 두 번째 절을 리팩터링 해 봅시다. 원래 코드와 마찬가지로 입력 텍스트를 한 번에 한 요소 씩 앞당기기를 원하지만 일치 검색도 원합니다. 우리는 지금 우리가 사용할 수 있도록 두 번째와 세 번째 인수로 Pattern을 전달합니다,

patternCount(_Text,[]) -> 0; 
patternCount(Text,Pattern) -> 
    patternCount(Text,Pattern,Pattern,length(Pattern),0). 

patternCount(Text,_Pattern,_Pattern,PatternLength,Count) when length(Text) < PatternLength -> 
    Count; 
patternCount(Text,[],Pattern,PatternLength,Count) -> 
    patternCount(Text,Pattern,Pattern,PatternLength,Count+1); 
patternCount([C|TextTail],[C|PatternTail],Pattern,PatternLength,Count) -> 
    patternCount(TextTail,PatternTail,Pattern,PatternLength,Count); 
patternCount([_|TextTail],_,Pattern,PatternLength,Count) -> 
    patternCount(TextTail,Pattern,Pattern,PatternLength,Count). 

먼저 바닥 네 개의 조항에 새 인수를 추가 참고 :이처럼 우리의 기능 헤드의 일치를 수행 할 수 그 중 하나는 매칭을위한 것이고, 그 중 하나는 원래의 패턴을 유지하는 것이다. 맨 위에 새 절을 추가하여 빈 Pattern을 확인하고이 경우 0을 반환합니다.

하단 세 개의 patternCount/5 절에만 초점을 맞추어 봅시다. 이 절은 런타임에 순서대로했지만,의는 먼저 다음 세 가지 조항의 두 번째에서 세 가지의 다음 먼저 세 번째 절을 보자됩니다, 우리가 쓰는이 세 조항의 두 번째에서

1. 을 첫 번째 및 두 번째 인수는 [Head|Tail] 목록 표기법으로, Head은 목록의 첫 번째 요소이고 Tail은 나머지 목록입니다. 두리스트의 머리 부분에 동일한 변수를 사용합니다. 즉, 두리스트의 첫 번째 요소가 동일하면 잠재적 인 일치 항목이 있으므로 patternCount/5은 처음 두 인수로 목록의 꼬리를 반복적으로 호출합니다 . 꼬리를 전달하면 입력 텍스트와 패턴을 한 번에 한 요소 씩 통과하여 요소가 일치하는지 확인할 수 있습니다.

2. 마지막 절에서 처음 두 인수의 머리글이 일치하지 않습니다. 만약 그렇다면 런타임은 두 번째 절을 실행합니다. 이것은 패턴 일치가 실패 했으므로 더 이상 첫 번째 인수의 첫 번째 요소 나 두 번째 인수를 신경 쓰지 않으며 새로운 일치를 찾기 위해 입력 텍스트를 진행해야합니다. 우리가 더 이상 중요하지 않으므로 입력 텍스트의 머리 부분과 두 번째 인수를 _ "do not care"변수로 씁니다.우리는 재귀 적으로 patternCount/5을 호출하여 입력 텍스트의 꼬리를 첫 번째 인수로 전달하고 Pattern을 두 번째 인수로 전달하여 새로운 일치 항목을 찾기 시작할 수 있습니다.

3. 첫 번째 절에서 두 번째 인수는 빈 목록입니다. 즉, 전체 요소 인 Pattern을 요소별로 성공적으로 일치시켜 여기에 도달했음을 의미합니다. 따라서 우리는 patternCount/5을 두 번째 인수로 전체 Pattern을 전달하여 재귀 적으로 호출하여 새로운 일치 항목을 찾기 시작하고 일치 항목 수를 증가시킵니다.

사용해보기!

-module(test). 
-export([read_text/1,pattern_count/2,main/0]). 

read_text(FileName) -> 
    {ok,File} = file:read_file(FileName), 
    unicode:characters_to_list(File). 

pattern_count(_Text,[]) -> 0; 
pattern_count(Text,Pattern) -> 
    pattern_count(Text,Pattern,Pattern,length(Pattern),0). 

pattern_count(Text,_Pattern,_Pattern,PatternLength,Count) 
    when length(Text) < PatternLength -> 
    Count; 
pattern_count(Text,[],Pattern,PatternLength,Count) -> 
    pattern_count(Text,Pattern,Pattern,PatternLength,Count+1); 
pattern_count([C|TextTail],[C|PatternTail],Pattern,PatternLength,Count) -> 
    pattern_count(TextTail,PatternTail,Pattern,PatternLength,Count); 
pattern_count([_|TextTail],_,Pattern,PatternLength,Count) -> 
    pattern_count(TextTail,Pattern,Pattern,PatternLength,Count). 

main() -> 
    pattern_count(read_text("file.txt"),"hello"). 

몇 최종 권고 사항 :

• 요소에 의해 텍스트 요소를 통해 검색에 필요한보다 느린 여기에 전체 수정 된 모듈이다. Boyer-Moore algorithm 및 기타 관련 알고리즘을 살펴보고 더 큰 청크로 텍스트를 전진시키는 방법을 살펴보아야합니다. 예를 들어, Boyer-Moore는 끝 부분 인에서 패턴 일치를 시도합니다. 일치하지 않으면 패턴의 전체 길이만큼 텍스트를 통과 할 수 있기 때문입니다.

• 목록보다는 얼랭 바이너리를 사용하는 것이 좋습니다. 메모리가 더 컴팩트 해지고 they allow for matching more than just their first elements입니다.

  : Text는 이진 입력 텍스트이고 Pattern가 이진 패턴, 그리고 Text의 크기를 가정하여 동일하거나 Pattern의 크기보다 큰 경우, 예를 들어,이 코드는, 전체 패턴을 일치 시키려고

  case Text of 
      <<Pattern:PatternLength/binary, TextTail/binary>> = Text -> 
       patternCount(TextTail,Pattern,PatternLength,Count+1); 
      <<_/binary,TextTail/binary>> -> 
       patternCount(TextTail,Pattern,PatLen,Count) 
  end. 
  

  이 코드 스 니펫은 Pattern 인수가 더 이상 요소별로 작동하지 않아도되므로 patternCount/4을 사용하는 것으로 되돌아갑니다.

• 전체 수정 된 모듈에 표시된 것처럼 동일한 모듈에서 함수를 호출 할 때 모듈 접두어가 필요하지 않습니다. 단순화 된 main/0 기능을 참조하십시오.

• 전체 수정 된 모듈에서 볼 수 있듯이 일반적인 얼랭 스타일은 대소 문자가 같은 함수 이름 인 patternCount을 사용하지 않습니다. 대부분의 Erlang 프로그래머는 pattern_count을 대신 사용합니다.