728x90
반응형
🐶 find, findIndex, filter 등의 method는 어떤 원리일까? 에서 출발한다.
🟣 완전 탐색
무차별 문자열 검색이라고도 한다.
그림처럼 문자열 및 배열에서 찾으려는 패턴을 하나하나 대조해가며 찾아간다.
👍 장점
- 구현하기 쉽다.
- text, pattern 의 사전처리 및 가공이 필요없다.
👎 단점
- 매우 느리다.
- 비효율적이다.
🟢 Rabin-karp Algorithm
Hashing을 통해 문자열에서 찾으려는 패턴과 일치하는지 찾아주는 알고리즘이다.
패턴의 hash코드와 문자열의 hash코드를 비교하여 hash 코드가 같을땐 실제로 같은지 확인 ( hash가 값이 달라도 중복이 될 수 있기 때문에 - hash글 참고)
여기까지만 보면 위의 완전탐색보다 훨씬 까다로운 것 같은데 여기서 확인해야할 부분이 하나 있다.
Rabin-karp의 hash 함수를 알아야하는데 각 자리의 해당하는 문자를 ASCII 코드로 변환하여 2의 n제곱으로 각 문자의 해당하는 값을 더하여 계산한다.
만약 4자리 글자를 찾는데 문자열이 adece 위와 같다면, 찾는 과정은 아래와 같다.
- 1. 처음 4자리 (adec) 를 해싱한다. -> 97*2^3 + 100*2^2 + 101*2^1 + 99*2^0 = 1477
- 2. hash값이 일치하지 않을 경우 한 칸을 옮겨 4자리(dece)를 해싱한다. -> (1477 - 97*2^3) * 2 + 101*2^0 = 1503
hash 화 하는 알고리즘을 알고 있기 때문에 dece는 adec에서 a를 제외하고 e를 더한값이라는 것을 알 수 있다.
이는 무차별 완전 탐색보다 연산이 간단해진다는 이야기이다.
👍 장점
- 완전탐색보단 빠르지만 사실상 비슷비슷하다.
- 구현하기 쉬우며, 해싱 기능을 보완할수록 진가가 드러날 수 있다.
👎 단점
- 느린편에 속하는 방법이다.
- 연산함수가 있기에 추가 메모리가 필요하다.
🟡 KMP ( knuth-Morris-Pratt)
abcdefghabciiiiaaa 라는 문자열에서 abciiii 라는 패턴을 찾는다고 했을때
abciiii 이면 abc까지는 같았지만 문자열의 d부터 틀렸다는 것을 알게된다. 따라서 같았던 부분을 제외한 다음 index부터 탐색해 나가는 방법이다.
🔵🟠
728x90
반응형