728x90 반응형 알고리즘12 rabin-karp 이번에는 hashing을 활용한 문자열 매칭 알고리즘인 라빈-카프(rabin-karp)에 대해 알아보고자 합니다. 라빈-카프 알고리즘의 시간복잡도는 O(N)으로 지금까지 진행하였던 왠만한 문자열 매칭 알고리즘보다 빠르다는 장점이 있습니다.그치만, 여러 가지 다양한 부분에서 문제점이 있어 실제 서비스에서는 사용하기 어렵다는 단점이 있습니다. 장점 - 시간이 빠르다단점 - hashing 값이 충돌이 날 수 있다. - overflow가 발생할 수 있다. "abbaba"라는 문자열에 "aba"라는 문자가 포함되어 있는지 확인하는 방법을 예시로 들어보겠습니다.hashing을 사용하기 때문에, 자리수마다의 문자의 아스키 코드 넘버에 특정 값을 곱하여 하나의 숫자 단위로 표현합니다.2를 활용하여 예시를 들면 pat.. 2024. 7. 11. A Fast StringSearching Algorithm 리뷰 해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다. 보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사합니다. 단, 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용하여 오른쪽 끝부터 비교하여 문자열 매칭을 진행합니다. 다음과 같이 "EAT A APPLE"의 문장에 "APPLE"이라는 단어가 있는지 체크하는 과정을 거친다고 가정해보겠습니다.APPLE의 맨 뒤 단어인 E와 같은 위치에 있는 단어는 A로 서로 다르다는 것을 인식하였습니다.이후, A라는 단어가 찾고자 하는 APPLE 이라는 단어에 포함되어 있는지 확인하고, 포함되어 있다면 해당 위치로 이동을 시킵니다.위치로 이동결과, APPLE이라는 단어를 찾.. 2024. 6. 16. Efficient String Matching : An Aid to Bibliographic Search 리뷰 이번엔 Efficient String Matching : An Aid to Bibliographic Search이라는 논문에 대해 리뷰해볼까 합니다. 해당 논문은 유명한 문자열 매칭 알고리즘인 "아호코라식"에 대한 논문입니다. 아호 코라식 알고리즘에 대해 이해하기에 앞서 kmp와 trie 알고리즘에 대해 어느 정도 알고계시면 이해하기 쉽습니다. KMP "ABAABC"라는 문자열에 "ABC"라는 단어가 부분 문자열로 존재하는지 체크하는 과정을 단순 반복문을 통하여 진행하게 되면, 맨 앞에 단어부터 해당 형식으로 진행하게 됩니다. kmp 알고리즘을 활용하게 된다면, 해당 형식처럼 진행을 하게 됩니다. kmp는 기존 문자열 매칭방식과 다르게 fail function이라는 실패 함수를 활용하게 됩니다. "ABC.. 2024. 4. 23. 트리를 활용한 문자열 비교 알고리즘 해당 알고리즘은 결정적 유한 오토마타를 학습하면서 떠오른 아이디어로 개발하였습니다. https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EC%A0%81_%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84 결정적 유한 상태 기계 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. --> ko.wikipedia.org 기존 map을 활용하여 중복을 제거하고, containsKey로 해당 문자열을 포함하고 있는지 체크하는 방식이 아닌, 트리를 활용하여 중복도 제거하고, 부분 문자열이 아닌 특정 문자열이 있는지 체크하는 알고리즘 입니다. 기존의 트리를 생각한다면 이런방식의 무방향 트리나, 방향이 있는 트리를 .. 2023. 8. 17. 이전 1 2 3 다음 728x90 반응형
