Week 4 of Data structures - Searching patterns
이번 강의에서는 hash function과 hash table을 잘 활용하기 위한 pattern을 찾아내는 알고리즘에 대해 알아보았다.
text T로부터 pattern P가 발견된 모든 경우를 찾는 방법에 대해 알아본다.
Substring Notation의 정의는 string S의 substring을 S[i..j]로 표기하며 i는 시작인덱스, j는 종료인덱스가 된다.
이에 대한 Input은 string T와 pattern P가 되며 Output은 T 내에 존재하는 P의 모든 시작인덱스들이다.
퀴즈를 보면 바로 알 수 있는데 P = ab, T = abcababa 일 때 substring에 대한 결과는 i = 0, 3, 5가 된다. (T = 'ab'c'ab''ab'a)
이제 Naive algorithm에 대해 알아보자면 i의 범위는 0 ~ lTl - lPl가 된다.
AreEqual의 함수는 위와 같은 구조를 가진다.
FindPatternNaive의 구조는 위와 같으며 아까 본 예시와 같이 T내에 있는 값이 P와 같다면 그 시작인덱스를 result에 추가한다.
Naive algorithm의 running time은 O(lTllPl)이다. 이는 매번 AreEqual을 호출할 때마다 O(lPl)의 시간이 소요되며 이후 lTl-lPl+1번의 AreEqual이 호출되므로 O(lTllPl)의 시간이 걸린다.
하지만 않좋은 예시를 보여주며 T가 P에 비해 굉장히 길이가 길때, 그리고 T와 P의 글자가 하나만 다른 상황이라면 굉장히 비효율적으로 돌아가는 것을 보여준다.
위의 불편함을 해결하기 위한 Rabin-Karp's algorithm을 소개하며 기본적인 인자는 같다.
이 알고리즘에서는 확률에 대한 개념을 도입하며 polynomial hash family를 Pp로써 활용한다.
RabinKarp pseudo code를 보면 여전히 T, P를 파라메터로 사용하고 p는 아주 큰 소수, x는 1~p-1의 랜덤값으로써 인자를 쓴다. for문에서 hash value를 비교하며 다를 경우 계속진행하고 같을 경우에는 collision이 진행된 것인지 AreEqual을 통해 확인한다.
False alarms이라는 개념이 존재하는데 이는 P가 T[i..i+lPl-1]과 비교할 때 다를 경우를 말한다고 하며 이에 대한 확률은 위와 같다고 한다.
AreEqual을 고려하지 안았을 때의 running time이고,
실제 running time은 위와 같은 형태를 띈다.
running time이 굉장히 복잡하기에 이를 개선시키고자 위와 같은 형태의 hash function을 채택하여 연속적인 substring을 유사하게 처리하는 방법을 쓴다.
바로 예시를 들어보면 T는 01213이며 lPl = 3이라고 할 때
h("cbd") = 2 + x + 3x^2
h("bcb") = 1 + 2x + x^2
처럼 위의 식과 아래식의 중간 겹치는 값들은 *x만큼 차이가 나게 한 것을 볼 수 있다.
위의 식을 H[2], 아래식을 H[1]이라고 보고 H[1]은 xH[2] + 1 - 3x^3으로 정리되는 것을 알 수 있다.
그렇다면 h("abc")의 수식은 어떻게 되는지 묻는 문제인데 H[0]를 보면 0, 1, 2로 구성되어 있으므로 1번인 것을 쉽게 캐치할 수 있다.
이를 일반화하여 표현하면 위와 같은 형태를 띄는 것을 알 수 있으며,
PrecomputeHashes에서는 일련의 과정을 정의하고 있다.
Precomputing H의 시간 복잡도는 위와 같으며,
이렇게 개선된 RabinKarp 알고리즘의 코드는 위와 같이 좀 더 복잡한 모습을 보인다.
향상된 running time은 이렇게 되고,
결론적으로 hash table에서 굉장히 유용하게 쓰일 수 있는 알고리즘이라고 알려준다. amotized cost는 O(1)으로 상당히 개선된 것을 강조한다.
이번 강의에서는 hash function과 hash table을 잘 활용하기 위한 pattern을 찾아내는 알고리즘에 대해 알아보았다.
text T로부터 pattern P가 발견된 모든 경우를 찾는 방법에 대해 알아본다.
Substring Notation의 정의는 string S의 substring을 S[i..j]로 표기하며 i는 시작인덱스, j는 종료인덱스가 된다.
이에 대한 Input은 string T와 pattern P가 되며 Output은 T 내에 존재하는 P의 모든 시작인덱스들이다.
퀴즈를 보면 바로 알 수 있는데 P = ab, T = abcababa 일 때 substring에 대한 결과는 i = 0, 3, 5가 된다. (T = 'ab'c'ab''ab'a)
이제 Naive algorithm에 대해 알아보자면 i의 범위는 0 ~ lTl - lPl가 된다.
AreEqual의 함수는 위와 같은 구조를 가진다.
FindPatternNaive의 구조는 위와 같으며 아까 본 예시와 같이 T내에 있는 값이 P와 같다면 그 시작인덱스를 result에 추가한다.
Naive algorithm의 running time은 O(lTllPl)이다. 이는 매번 AreEqual을 호출할 때마다 O(lPl)의 시간이 소요되며 이후 lTl-lPl+1번의 AreEqual이 호출되므로 O(lTllPl)의 시간이 걸린다.
하지만 않좋은 예시를 보여주며 T가 P에 비해 굉장히 길이가 길때, 그리고 T와 P의 글자가 하나만 다른 상황이라면 굉장히 비효율적으로 돌아가는 것을 보여준다.
위의 불편함을 해결하기 위한 Rabin-Karp's algorithm을 소개하며 기본적인 인자는 같다.
이 알고리즘에서는 확률에 대한 개념을 도입하며 polynomial hash family를 Pp로써 활용한다.
RabinKarp pseudo code를 보면 여전히 T, P를 파라메터로 사용하고 p는 아주 큰 소수, x는 1~p-1의 랜덤값으로써 인자를 쓴다. for문에서 hash value를 비교하며 다를 경우 계속진행하고 같을 경우에는 collision이 진행된 것인지 AreEqual을 통해 확인한다.
False alarms이라는 개념이 존재하는데 이는 P가 T[i..i+lPl-1]과 비교할 때 다를 경우를 말한다고 하며 이에 대한 확률은 위와 같다고 한다.
AreEqual을 고려하지 안았을 때의 running time이고,
실제 running time은 위와 같은 형태를 띈다.
running time이 굉장히 복잡하기에 이를 개선시키고자 위와 같은 형태의 hash function을 채택하여 연속적인 substring을 유사하게 처리하는 방법을 쓴다.
바로 예시를 들어보면 T는 01213이며 lPl = 3이라고 할 때
h("cbd") = 2 + x + 3x^2
h("bcb") = 1 + 2x + x^2
처럼 위의 식과 아래식의 중간 겹치는 값들은 *x만큼 차이가 나게 한 것을 볼 수 있다.
위의 식을 H[2], 아래식을 H[1]이라고 보고 H[1]은 xH[2] + 1 - 3x^3으로 정리되는 것을 알 수 있다.
그렇다면 h("abc")의 수식은 어떻게 되는지 묻는 문제인데 H[0]를 보면 0, 1, 2로 구성되어 있으므로 1번인 것을 쉽게 캐치할 수 있다.
이를 일반화하여 표현하면 위와 같은 형태를 띄는 것을 알 수 있으며,
PrecomputeHashes에서는 일련의 과정을 정의하고 있다.
Precomputing H의 시간 복잡도는 위와 같으며,
이렇게 개선된 RabinKarp 알고리즘의 코드는 위와 같이 좀 더 복잡한 모습을 보인다.
향상된 running time은 이렇게 되고,
결론적으로 hash table에서 굉장히 유용하게 쓰일 수 있는 알고리즘이라고 알려준다. amotized cost는 O(1)으로 상당히 개선된 것을 강조한다.
댓글
댓글 쓰기