13-01 문자열 탐색 알고리즘

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

1.고지식한 탐색(Brute-Force Search)

 1)정의

 -문자열에서 찾고자 하는 패턴을 앞에서부터 검색하는 알고리즘.

 -단순하지만 패턴을 찾기 위해 문자열 길이 x 패턴 길이만큼 검색량이 생길 수 있다.

2.카프-라빈 알고리즘

 1)정의

 -문자열 탐색에서 해시함수를 사용하는 알고리즘

 -패턴의 해시값과 문자열의 해시값을 비교하는 방식.

 -문자열 길이가 m일 때 해시 값을 구하는 함수.

 -만약 이전 해시함수 값을 알고 있다면 아래와 같이 변형이 가능하다.

 

3.KMP 알고리즘

 1)정의

 -문자열에서 찾을려는 패턴과 문자열을 비교하면서 생기는 정보를 바탕으로 검색 효율을 높이는 알고리즘

 -접두사와 접미사의 개념을 활용하여 실패함수 테이블을 만들고, 테이블을 활용하여 반복되는 문자열을 건너뛰면서 패턴을 찾는 알고리즘.

2)작동 과정

 -접두부는 문자열에서 머리부분 접미부는 꼬리부분.

 -접두부와 접미부가 일치하는 한 쌍을 경계라고 한다.

-본문과 패턴 모두 경계를 가지고 있고 일치하는 경계를 찾는다.

-탐색할 때 본문과 패턴이 일치하지 않았다면 일치하는 경계에서 패턴의 접두사 부분을 접미사 부분이동시켜 다시 탐색하는 것 반복한다.

4.보이드 무어 알고리즘

 1)정의

 -패턴의 오른쪽부터 비교하여 텍스트 문자를 모두 비교하지 않아도 탐색이 가능한 알고리즘.

 2)나쁜 문자 이동

 -보이드 무어 알고리즘의 문자열 이동 방법

 -패턴의 오른쪽 부분부터 검사하여 본문 문자열과 패턴 사이의 매치되지 않은 문자를 나쁜문자라고 뜻하고 이 문자를 이동하는 것을 말한다.

 3)착한 접미부 이동

 -보이드 무어 알고리즘의 문자열 이동 방법.

 -패턴의 오른쪽 부분부터 검사하여 일치하는 부분을 착한 접미부라고 뜻한다.

 -착한 접미부 이동이 사용할 때는 두가지 경우가 있다

 -첫번째 경우로 불일치가 발생한 상황에서 본문의 착한 접미부의 동일한 문자열이 패턴의 나머지 부분이

  존재할 때

 -첫번째 경우가 존재하지 않을 때 두번째 경우로 '착한 접미부의 접미부'가 패턴의 접미부와 일치하는지 확인하고 '착한 접미부의 접미부'와 일치하는 패턴의 접두부가 동일한 위치에 놓이도록  이동시킨다.