문자열 매칭

원시적인 매칭

이렇게 하나씩 맞춰보는 것

 

-원시적인 매칭이 비효율적인 예

 

오토마타를 이용한 매칭

-ababaca를 체크하는 오토마타

순서 대로 맞게 들어오면 단계가 올라간다.

이것을 만드는 것이 어렵다.

 

위 그림을 S/W 구현

 

라빈-카프 알고리즘

문자열 패턴을 수치로 바꾸어 문자열의 비교를 수치 비교로 대신한다.

 

-수치화

여기서는 문자가 5개라 5진수를 사용한다.

그리고 문자를 인덱스 번호처럼 대응 시킨다. 그리고 5진수라 5^n이렇게 해준다. n은 1씩 감소한다.

 

-수치화를 이용한 매칭의 예

eeaab를 찾는데 eeaab를 수치화하면 3001이다. 따라서 앞부터 수치화해서 3001가 나오는 것을 찾는다.

a2부터는 a1의 값에서 a1의 맨 앞 수를 빼고 추가되는 것을 더해주면 된다.

그리고 차수가 높아지니까 그 전꺼의 맨 앞을 빼고 진수를 곱해준다.

 

-문제점

문자 집합과 크기에 따라서 수가 매우 커질 수 있다. 

=> 오버플로우 발생 가능

 

따라서 적당한 수로 나눠준다.

 

보이어-무어 알고리즘

이 알고리즘은 텍스트 문자를 다 보지 않아도 된다.

발상의 전환: 패턴의 오른쪽부터 비교한다.

 

오른쪽부터 비교한다. 따라서 tiger에 b는 절대 있을 수 없어서 바로 b 다음부터 비교한다.