다항식과 FFT

다항식의 표현(1) 다항식 계수 표현(coefficient representation) 계수-지수 표현 f(x) = a0 + a1x1 + a2x2 + … an-1xn-1 계수(coefficient), 지수(exponent), 차수(degree) 다항식의 차수 상한(degree-bound) 계수 표현(coefficient representation) 계수 벡터로 다항식을 표현 float a[n]; // xi의 계수를 a[i]에 저장 계수-지수 표현 지수 및 계수로 구성된 구조체로 항(term)을 표현 Term poly[# of terms]; // 다항식: array of terms

다항식의 표현(2) 점 값에 의한 표현(point value representation) 서로 다른 n개의 x 값에 대하여 아래의 순서쌍들의 집합으로 다항식을 표현 {(x0, y0), {(x1, y1), …, {(xn-1, yn-1)}, where yk = f(xk) n개의 순서쌍으로 표현된 다항식은 유일함 Vandermonde 행렬 V에 대한 V-1이 유일하게 존재

다항식에 대한 연산 식의 값 계산 다항식의 덧셈 다항식의 곱셈 1개의 x 값에 대한 식의 값 계산 일반 알고리즘: O(n2) Horner 알고리즘: O(n) f(x) = a0 + x*(a1 + … + x*(an-2 + x*(an-1))…) n개의 x 값에 대한 식의 값 계산: O(n2) 다항식의 덧셈 기본 알고리즘: O(n) 다항식의 곱셈 계수 표현: O(n2) FFT을 적용한 알고리즘: O(n log n)

Point-wise Multiplication FFT를 적용한 다항식 곱셈 입력 다항식 A, B 출력 다항식 C 일반 알고리즘 O(n2) 계수 표현 n개의 점에 대한 식의 값 계산 O(n log n) 보간법에 의한 계수 계산 O(n log n) Point-wise Multiplication O(n) 점값 표현 {(xk , C(xk)|C(xk) = A(xk) * B(xk)}

복소수 근 ω의 특성 방정식 xn = 1의 복소수 근 ω의 특성 n개의 근: ω의 특성과 관련한 정리

DFT Discrete Fourier Transformation의 정의 DFT의 행렬 표현: y = Vn a

FFT FFT(Fast Fourier Transformation)란? 알고리즘 정의: 복소수 근의 특성을 활용하여 DFTn(a)를 O(n log n) 시간 안에 계산하는 방법 다항식 A(x)를 A[0](x)와 A[1](x)로 분할 A[0](x) = a0 + a2x + a4x2 + … + an-2xn/2-1 A[1](x) = a1 + a3x + a6x2 + … + an-1xn/2-1 A(x) = A[0](x2) + xA[1](x2) A[0](x)와 A[1](x)의 값을 아래 점에서 계산하여 결합 알고리즘 Recursive FFT Iterative FFT

RecursiveFFT 알고리즘(1) // a: 다항식의 계수 벡터 RecursiveFFT(a) { n = length of a; // n = 2k if (n == 1) return a; // 방정식 xn =1의 복소수 근의 값을 설정 ROOT = exp(2 * PHI * imgUNIT / n); // imgUNIT = 허수 단위 i OMEGA = 1; // 계수 벡터 a를 분할하고, 각각에 대한 DFTn/2(a)를 계산 a0[] = { a[0], a[2], …, a[n-2] }; a1[] = { a[1], a[3], …, a[n-1] }; y0[] = RecursiveFFT(a0); y1[] = RecursiveFFT*a1);

RecursiveFFT 알고리즘(2) // 2개의 DFTn/2(a)를 결합 for (k = 0; k <= n/2 -1; k++) { y[k] = y0[k] + OMEGA * y1[k]; y[k+n/2] = y0[k] – OMEGA * y1[k]; OMEGA = OMEGA * ROOT; } return y; ※ FFT의 수행 시간 T(n) = 2 * T(n/2) + O(n) = O(n log n)

보간법 기본 개념 알고리즘 점값에 의한 다항식 표현을 계수형으로 변환 DFT의 행렬 표현 식으로부터 계산 DFT: y = Vn a 보간법: a = Vn-1 y 알고리즘 FFT 알고리즘을 일부 수정하여 적용 aj 값 계산 식

String Matching

String Matching? 문제의 정의 대표적인 알고리즘 주어진 조건 Text String(텍스트 문자열): A[1..n] Pattern String(패턴 문자열): P[1..m] m《 n -> P[]는 A[]에 비해서 현저히 짧다. 문제: 텍스트 문자열이 패턴 문자열을 포함하고 있는가? 대표적인 알고리즘 원시적인 matching 방법 Automata를 이용한 matching Rabin-Karp 알고리즘 KMP 알고리즘 Boyer-Moore 알고리즘

원시적인 Matching 방법 ▣ 기본 아이디어: 텍스트의 처음부터 패턴과 비교 -> O(mn) 1단계: P[1..m]과 A[1..m]을 비교 2단계: P[1..m]과 A[2..m+1]을 비교 ... ※ 전체 비교 회수: (n-m+1)번 A[] b o y c a t s r p P[] s o a r s o a r s o a r s o a r

원시적인 매칭 알고리즘 // n: length of text A, m: length of pattern P naiveMatching(A, P) { for (i = 1; i <= n-m+1; i++) { if (P[1..m] = A[i..i+m-1) { A[i]에서 매칭이 발견되었음을 기록한다; }

Automata를 이용한 Matching 문제 해결 절차를 상태간의 이동(전이)으로 표현 A = (Q, q0, F, Σ, δ) Q : 상태들의 집합 q0 : 초기 상태 F: 목적이 달성된 상태의 집합 Σ: 입력 가능한 문자들의 집합 δ: 상태 전이 함수. 2차원 배열로 표현 ▣ Pattern “ababaca”를 찾는 오토마타 1 3 2 5 4 6 7 a c b

Automata를 이용한 매칭 알고리즘 // n: length of text A, f: final state FA_Matcher(A, δ, f) { q = 0; for (i = 1; i <= n; i++) { q = δ(q, A[i]); if (q = f) { A[i-m+1]에서 매칭이 발견되었음을 기록한다; } 수행 시간: O(n) 상태전이함수 준비시간: O(|Σ|∙m) 전체수행시간: O(n + |Σ|∙m)

Rabin-Karp 알고리즘 기본 개념 문자열 패턴을 수치로 바꾸어 문자열 비교를 수치 비교로 전환시켜 매칭하는 방법 문자 집합 Σ의 크기에 따라 몇 진수를 쓸 것인지를 결정 영어 알파벳 대소문자: 52진수, ASCII 문서: 128진수, ... 패턴 P[1..m]을 d 진수로 변환한 값 p의 계산 P[1]*dm-1 + P[2]*dm-2 + ... + P[m-1]*d1 + P[m] A[i..i+m-1]에 대응하는 ai의 계산 ai = A[i]*dm-1 + A[i+1]*dm-2 + ... + A[i+m-2]*d1 + A[i+m-1] ai = d*(ai-1 – dm-1*A[i-1]) + A[i+m-1]

수치화를 이용한 매칭 알고리즘 // n: length of text A, m: length of pattern P, d: 진수 basicRabinKarp(A, P, d) { p = 0; a[i] = 0; for (i = 1; i <= m; i++) { p = d*p + P[i]; // P[]의 수치 값 계산 a[1] = d*a[1] + A[i]; // a[1]의 수치 값 계산 } for (i = 1; i <= n-m+1; i++) { if (i != 1) a[i] = d*(a[i-1] – dm-1*A[i-1]) + A[i+m-1]; if (p = a[i]) A[i]에서 매칭이 발견되었음을 기록한다; 전체수행시간: O(n)

수치화를 이용한 알고리즘의 개선 문제점 해결 방안 문자 집합 Σ의 크기와 m의 길이에 따라 ai가 매우 큰 수가 될 수 있다. 이 경우에 컴퓨터 레지스터의 용량을 초과하여, overflow가 발생할 가능성이 매우 높다. 해결 방안 컴퓨터 레지스터가 감당할 수 있는 범위에서 충분히 큰 소수(prime number) q를 선정 ai 대신에 bi = ai mod q 를 사용 실제로는 매칭이 되지 않았는데도 mod q 연산으로 인하여 우연히 p = bi가 되는 경우가 발생할 수 있음 q 값을 충분히 크게 잡음으로써 발생할 확률을 0에 가깝게 만듬

수치화를 이용한 매칭 알고리즘 // n: length of text A, m: length of pattern P, d: 진수, q: 충분히 큰 소수. RabinKarp(A, P, d, q) { p = 0; b[i] = 0; for (i = 1; i <= m; i++) { p = (d*p + P[i]) % q; // P[]의 수치 값 계산 b[1] = (d*b[1] + A[i]) % q; // a[1]의 수치 값 계산 } h = (dm-1) % q; for (i = 1; i <= n-m+1; i++) { if (i != 1) b[i] =(d*(b[i-1] – h*A[i-1]) + A[i+m-1]) % q; if (p == b[i] && P[1..m] == A[i..i+m-1]) A[i]에서 매칭이 발견되었음을 기록한다; O(m) T(n) = O(n+km), k: 매치 발생 회수

KMP 알고리즘(1) 기본 개념 Knuth, Morris, Pratt이 만든 알고리즘 핵심 아이디어 오토마타를 사용한 알고리즘과 유사한 발상 어느 지점에서 매칭이 성공하지 못했어도, 그 지점을 기준으로 몇 개의 부분 문자열이 찾으려는 패턴 문자열의 앞 부분과 일치한다면 그 정보를 활용 패턴의 각 위치에 대해서 매칭에 실패했을 때 돌아갈 곳을 알려주는 일차원 배열(π[])을 준비 이를 이용해서 텍스트 문자열을 훑어 나간다

배열 π의 생성 P[] a b c d w z π[] 1 2 3 4 a b c d w z 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 P[] a b c d w z 1 2 3 4 5 6 7 8 9 10 π[] 1 2 3 4 a b c d w z

KMP 알고리즘의 수행 예 A[] . a b c d 패턴 문자열의 구조로부터 이미 매치되었음을 알고 있으므로, 비교하지 않고 건너 뜀 P[] a b c d w z a b c d w z π[8] = 4 이므로, 매치가 실패한 위치의 텍스트 문자와 P[4]를 비교

KMP 알고리즘(1) // n: length of text A, m: length of pattern P. KMP(A, P) { preprocessing(P); i = 1; j = 1; // 텍스트 문자열 포인터 & 패턴 문자열 포인터 while (i <= n) { if (j == 0 or A[i] == P[j]) { i++; j++; } else j = π[j]; if (j == m+1) { A[i-m]에서 매치되었음을 알림; j = π[j]; } T(n) ≤ 2n = O(n)

KMP 알고리즘(2) preprocessing(P) { j = 1; k = 0; π[1] = 0; while (j <= m) { if (k == 0 or P[j] == P[k]) { j++; k++; π[j] = k; } else k = π[k];

Boyer-Moore 알고리즘 핵심 아이디어 마지막 문자부터 역순으로 비교하며, 매치될 가능성이 없을 때에는 일부 문자를 점프 A[1..m]가 P[1..m]을 비교하는 경우 A[m]이 P[1..m]에 존재하지 않을 경우 A[2], ..., A[m-1]로 시작하는 문자열은 P[1..m]과 매치될 가능성이 없다. 따라서 텍스트 문자열에서 m개의 문자를 건너 뛰고, A[m+1..2m]과 P[1..m]을 비교하면 된다. A[m]이 P[1..m]에 존재하는 경우 P[1..m]의 몇 번째 문자인가에 따라 2칸 이상 점프할 기회가 있음 2개의 version simple version: Boyer-Moore-Horspool 알고리즘 full version: Boyer-Moore 알고리즘

Jump 수행 예 A[] . b t i g e r P[] t i g e r b를 활용, 5칸 점프 t i g e r A[] .

Boyer-Moore-Horspool 알고리즘 // n: length of text A, m: length of pattern P. BoyerMooreHorspool(A, P) { computeJump(P, jump); i = 1; while (i <= n-m+1) { j = m; // j: 패턴 문자열을 위한 포인터(끝에서부터 이동) k = i+m-1; // k: 텍스트 문자열을 위한 포인터(＂) while (j > 0 and P[j] == A[k]) { j--;, k--; } if (j == 0 ) A[i] 위치에서 매치되었음을 알림; i = i + jump[[A[i+m-1]]; // 마지막 문자로부터 jump 위치 결정 } O(m) O(m) 최악의 경우: O(mn), 최선의 경우: O(n/m) 실제의 경우: O(n) 보다 더 작은 시간 소요

완전한 Boyer-Moore 알고리즘 2가지 Heuristics 불일치 문자 휴리스틱(Bad-Character Heuristics) j가 m보다 r번째 왼쪽에서 불일치한 경우 텍스트에서 (jump[A[k]] – r)만큼 점프 가능 일치 접미부 휴리스틱(Good-Suffix Heuristics) P[j] (j >0)에서 불일치한 경우: P[m] ~ P[j+1] 까지는 일치. P[1..m]의 다른 부분에서 P[j+1..m]과 일치하는 부분 문자열이 없으면, 한꺼번에 점프 가능 P[1..m]의 다른 부분에서 P[j+1..m]과 일치하는 부분 문자열이 있으면, 그 부분이 A[i..i+m-1]과 나란해지도록 점프 가능 불일치 문자 휴리스틱과 일치 접미부 휴리스틱에 의한 점프 중에서 큰 것을 선택하여 점프