'컴퓨터 과학!/Algorithms'에 해당되는 글 9건

  1. 2004.11.16 kd-tree (16)
  2. 2004.11.07 9. Text Processing (3)
  3. 2004.11.06 Greedy Algorithm
  4. 2004.11.06 Dynamic Programming (1)
  5. 2004.11.04 9. Text Processing (2)
  6. 2004.11.03 9. Text Processing (1)
  7. 2004.09.30 Disjoint set
  8. 2004.09.12 기억해 두자아-
  9. 2004.09.02 첫 숙제 -ㅇ-
이건 지난 학기 FS 시간에 배운 것인데,
이번에 알고리즘 시간에 나와서
한 번 복습!



⊙ Introduction
여기에서 다루는 kd-tree는 공간 DB로, 기존의 문자 DB와는 다르다. key 값 매칭 문제이고, 굉장히 큰 양을 공간 기반으로 검색한다. 공간 기반 검색이란, range로 표현된 질의를 검색한다는 것이다. Spatial data는 points, lines, polygons 등을 포함하고 있따.
Spatial data를 효율적으로 지원하기 위해서는, 다음과 같은 특징적 어려움을 알아야 한다.
① First, spatial data are latge in quantity, complex in structures and relationships
② Second, the retrieval process employs complex spatial operators like intersection, adjacency, and containment
③ Third, it is difficult to define a spatial ordering, so conventional techniques cannot be employed for spatial operations
→ spatial indices 필요!

(1) kd-tree : Binary-tree based indexing
kd-tree는 multi-attribute data index를 binary search하는 tree로, k는 표현될 데이터 공간의 차원을 가리킨다. 각 depth에서, 어떤 branch로 갈 것인가를 결정하는 데에 다른 attribute이 사용된다. 예를 들어, 2-d (x,y) tree에서는 짝수 depth에서 x 좌표가 branch 기준이라면, 홀수 depth에서는 y 좌표가 branch 방향의 기준이 된다. 마지막으로, 이 tree는 꼭 균형을 이룰 필요는 없다.

A가 제일 먼저 들어간 것을 알 수 있다. 즉, 최초의 분리자는 root이다.



① Principle
Node는 각각의 실제 data point를 나타내고, 검색 방향의 지표가 된다. (left, right 두 개의 child가 있다.→ 현재 노드 값 보다 작은가? 큰가?)
한 Node는 5개의 field로 구성되어 있다. LOSON(작은 값을 가진 left 자식), HISON(큰 값을 가진 right 자식), 좌표(x,y,...), NAME(해당 노드에 대한 정보. 포인터가 들어갈 수도 있다.), DISC(좌표 이름을 가리킨다. 즉, 이 노드는 x를 기준으로 했느냐 y를 기준으로 했느냐. 등. ).

② Insertion
Binary search tree에서의 insertion 방법과 유사하다. 다른 점이 있다면, 앞에서 설명 했듯이, depth마다 비교하는 attribute가 다르다는 것이다. tree의 bottom에 도달하면, 거기에 새 node를 넣는다.

매우 쉽다;



③ Search
Search 역시 매우 straightforward하다. 흐흐 BST 처럼 찾아 내려가면 된다. 여기에서 역시, 다른점은 depth마다 비교 기준의 attribute이 다르다는 점 뿐. 참 그리고, 질의가, 조건 질의가 가능하다는 것이 또 하나 틀린데, 예를 들어, 'Y>20인 점들을 찾아라' 라든지, '(75,15)에 가까운 점들을 찾아라' 등이 가능하다는 것이다.
Region Search는 Euclidean distance를 이용하여 구할 수있다. node (a,b) 근처 거리 d안에 있는 점들을 다 구하라는 질의가 들어오면, 우선 (a-d) ≤ x ≤ (a+d), (b-d) ≤ y ≤ (b+d) 안의 점들을 다 구한다. 그런데 이렇게 구한 점은, 반지름 d인 원 안에 있는 점이 아니라, 한 변이 2d인 정사각형 안에 들어오는 점이므로, 점들을 구한 다음에 range안에 들어오는 게 맞는지 확인이 필요하다.

Search 결과 Miami를 찾았다!



④ Deletion
앞에 insert나 search는 BST와 비슷하여 쉬웠지만, deletion은 좀 더 복잡하다. 각 depth마다, DISC가 달라서, 원래 tree의 root는 DISC가 x 지만, subtree의 root는 y가 될 수도 있기 때문에, 모든 subtree가 kd-tree가 아니다. 그래서 그냥 마구 삭제해 버리면 문제가 생긴다.
kd-tree로 부터 (a,b) 노드를 삭제한다고 할 때, (a,b)의 두 subtree가 empty tree이면 그냥 삭제하면 되고, 아니면 (a,b)의 subtree들 중에서 가장 적절한 대체 노드 (c,d)를 찾아서, replace시킨다. 이 (c,d)는 recursive하게 다시 삭제되는 것이다. 그렇다면, 이 대체 노드는 어떻게 찾는 것일까? 오른쪽 subtree에서 가장 작은 값을 가진 노드나, 왼쪽 subtree에서 가장 큰 값을 고르면 된다. 그러면 다음의 예를 보자.

사실 이것도 찬찬히 보면 매우 쉽다. 그죠?



⑤ 장단점
kd-tree는 partial matching search에 유용하지만, empty space가 없고, point search와 region search가 다 가능하다. 하지만, 균형이 심~하게 안맞으면 performance가 안좋다. kd-tree는 메모리 기반 index이다. File 기반에서는... 안좋다.
Posted by 스니

댓글을 달아 주세요

  1. 쳇, 공부쟁이!

    2004.11.16 09:13 [ ADDR : EDIT/ DEL : REPLY ]
  2. 치앙수

    이거 뭐에요 -_-a;

    2004.11.16 18:42 [ ADDR : EDIT/ DEL : REPLY ]
  3. 스니스니

    지난 학기 FS 시간에 했다던 kd-tree야. 으흐흐흐 잘 읽어봉. 쉬움.

    2004.11.16 19:09 [ ADDR : EDIT/ DEL : REPLY ]
  4. Michelle

    요거 찾아 들어왔슴다. 꼭꼭씹어서 이해되었구요... ^^
    혹 제가 모르는거 있음 물어도 되나요?
    많이 도와주세요~~~

    2006.09.25 00:11 [ ADDR : EDIT/ DEL : REPLY ]
  5. 아.. 저도 많이 부족하지만...
    제가 아는 것이라면야.. ^^

    2006.09.25 18:39 [ ADDR : EDIT/ DEL : REPLY ]
  6. 비케이러브

    알고리즘에 대한 기초가 많이 부족한 탓인지 아무리 읽어봐도 잘 이해가 가질 않네요..이 알고리즘으로 image serach 프로그램을 만들어야 하는데 어떻게 공부를 해야 할까요?쫌 가르쳐 주세요

    2006.11.14 15:36 [ ADDR : EDIT/ DEL : REPLY ]
  7. ㅇㅇ

    퍼가염..

    2007.04.10 11:11 [ ADDR : EDIT/ DEL : REPLY ]
  8. Kurt

    허헛~! 구글에서 k-d tree 치니까 세 번째로 뜨는구랴~~

    2007.10.11 23:13 [ ADDR : EDIT/ DEL : REPLY ]
  9. 스니스니

    한때 잠깐 열심히 할려던 시절이 있었지 -ㅅ-;;

    2007.10.20 17:17 [ ADDR : EDIT/ DEL : REPLY ]
  10. 재밌게 잘 써 놓으셔서 퍼갑니다. 스크랩이나 트랙백으로 가져가고 싶었는데, 서비스업체가 달라서 안되네요.. 암튼 잘 보고 갑니다^^

    2007.11.09 19:14 [ ADDR : EDIT/ DEL : REPLY ]
  11. 스니스니

    네ㅡ 얼마든지요! : )

    2007.11.16 13:29 [ ADDR : EDIT/ DEL : REPLY ]
  12. 아아아악 누나~~~!! 잘 지내죠? 흐윽 ㅠ
    알고리즘 분석 셤이 낼이라 kd-tree 검색하다가 익숙한 스니스니 보고 ㅋㅋ

    역시 사발의 천재계보군요 흐음흐음...이런 정리를!
    잘 참고하고 가요~~^^

    2009.10.22 20:16 [ ADDR : EDIT/ DEL : REPLY ]
  13. 근데 deletion 할때 그림에서는 오른쪽 subtree이던 왼쪽 subtree이던 minimum 값만 찾아서 교체해주네요. 누나 글이랑 달라서 어느쪽이 맞는건가 해서요 ㅠ_ㅠ

    2009.10.22 20:35 [ ADDR : EDIT/ DEL : REPLY ]
    • 그래, 그러고 보니 설명과 그림에 약간 문제가 있구나.
      너무 오래전에 작성한 글이라 다시 읽어보고 다음과 같은 결론을 내렸다.
      1. 자료구조라는 것은 정해진 규칙을 '유지'하고 있도록 만드는 것이 주 목적이다. 이 규칙은 검색을 용이하게 하며, 따라서 이 규칙을 지키도록 삽입과 삭제 작업을 해 주어야 한다.
      2. kd-tree의 규칙은 각 레벨마다 기준 좌표(DISC)가 다른 BST이다. 따라서 left subtree의 x-DISC에 해당하는 노드의 x값은 parent의 x값보다 모두 작아야 하며, right subtree의 x-DISC에 해당하는 노드의 x값은 parent의 x값보다 모두 커야한다. y도 마찬가지이다.
      3. 따라서, right subtree의 min, left subtree의 max로 target을 교체하여 삭제하는 것이 기본적으로 생각할 수 있는 방법이다. (C노드를 E노드로 교체)
      4. 그러나, 그림에서는 left subtree의 min으로 교체하고 그 subtree를 target의 right subtree로 만들어주었다. 이것은, 구현의 특징이라고 할 수 있는데, 이 방법에서는 left subtree의 max냐 right subtree의 min이냐 고민하기 전에, 무조건 right subtree의 min을 구해서 삭제하고, right subtree가 empty일 때에만 left subtree에서 교체할 값을 찾는 방법을 사용하기 때문인 것 같다. (C노드를 D노드로 교체한 후, D의 left subtree를 right subtree로 바꾸어주었다.)
      이렇게 한 이유는 아마도, 트리가 균형을 이룰 필요는 없으므로, 교체할 값을 빠르게 찾고 검색 또한 빨라지게 하기 위한 방법이 아닐까 싶다.

      2009.10.23 01:37 신고 [ ADDR : EDIT/ DEL ]
  14. 12

    잘 보고 갑니다 ^^ 스크랩 해갈게요

    2010.02.02 18:41 [ ADDR : EDIT/ DEL : REPLY ]
  15. 회사에서 일하다가 12년 전의 누나 블로그를 보고 가네요^^ 12년 전의 누나와 지금의 누나에게 감사를 표합니다~!! 잘 지내시죠?

    2016.08.05 07:47 신고 [ ADDR : EDIT/ DEL : REPLY ]

9.3 Text Compression
Text compression은 low-bandwidth channel 이나 fixed-capacity storage device 등에서 중요한 문제이다. ASCII(16bits)나 Unicode system(16bits)에서는 fixed length binary string을 사용하는데 반해, Huffman code는 frequency가 클 수록 더 짧은 길이의 code를 부여하는 variable length encoding 방법을 사용하여 space를 줄인다.
이런 variable length code를 사용하기 위해서는, 이것은 prefix code여야한다. Prefix code란, 'no code word in our encoding is a prefix of another code word in its encoding'이다. 사실, 뜻은 prefix-free code이다. 이 때문에 code word 길이는 길어질 수 있지만, 그래도 fixed length를 사용하는 것 보다는 공간이 절약된다. 특히나, 인간이 사용하는 언어와 같이 frequency들 간의 차이가 큰 경우 더욱 효율적이다.

1) The Huffman Coding Algorithm
⊙ Huffman tree 만들기
root를 single-binary tree로 시작하여, frequency가 낮은 것부터 merge한다.

Huffman code algorithm and its construction


d개의 distinct char가 있고, text 길이가 n이라 하면, 두 binary tree를 merge하는 while-loop 동작은 d-1번 수행되고, priority queue 유지하는데 O(logd)걸리므로, 이 Huffman tree를 만드는 데 걸리는 시간은 O(n + dlogd)가 된다.

2)The Greedy Method Revisited
Huffman's Algorithm은 일종의 Greedy method이다. ...
Posted by 스니

댓글을 달아 주세요

⊙ 동전 바꾸기!
이건 Greedy Algorithm을 설명하기 위해서 가장 많이 사용되는 예제인데, 1000원을 동전으로 바꿀 때, 가장 적은 수의 동전으로 바꿀 수 있는 경우는? 당연히, 500원짜리 2개이다. 900원을 동전으로 표현하면, 500원짜리 1개와 100원짜리 4개가 될 것이다. 여기에서는 Greedy algorithm을 사용하여, 가장 큰 동전부터 뽑아내면 된다.
⊙ Suffix Dictionary
Prefix Dictionary와 반대되는 개념으로, 각각의 phrase들의 suffix가 dictionary 내의 다른 phrase를 이루고 있는 dictionary이다.
Suffix Dictionary를 이용한 encoding 방법의 예를 들어보자. ∑={a,b,c}인 D={abc, bc, c, a, b, d, dac, ac}라는 suffix dictionary가 있고, 이것들은 각각 {0,1,2,3,4,5,6,7}로 encoding한다. 이때, D에 있는 모든 phrase들의 suffix는 다른 phrase의 suffix라는 것을 알 수 있다.
그러면 이 때, T=abcabdaccd 라는 입력값이 주어졌을 때, 가장 짧은 codeword를 얻을 수 있는 방법은? 정답은 바로, Greedy Algorithm을 이용하는 것이다. 단, 여기에서는 모든 codeword가 같은 수의 bit를 가진다는 것이다. 여기에서는 총 8개가 필요하므로, 3bit면 되겠다. 저 T를 가장 짧게 encoding하면, O=034625이다. (prefix와는 경우가 다르다. prefix에서는 greedy algorithm을 적용할 수 없다.)
Posted by 스니

댓글을 달아 주세요

Dynamic Programming(이하 DP)은 어떤 고정된 조건이 주어졌을 때, 그 조건에 부합됨과 동시에 결과값이 최대 또는 최소가 되게하는 최적화 문제(Optimization problem)에 대한 해답을 주는 알고리즘이다. 그러나 모든 최적화 문제에 DP를 적용할 수 있는 것은 아니다. 다음과 조건을 만족할 때에만 사용 가능하다.
1. Optimal Substructure를 가질 때 : 최종적인 최적값이 그 하부에서의 최저값을 포함하고 있는 경우.
2. Overlapping Subproblems가 있을 때 : 자기 반복적인 (recursive) 알고리즘의 경우, 이미 한 번 풀어놓은 문제를 다시 풀어야 하는 경우가 생긴다. 이 때, 계산을 다시 하기 보다는 적당한 기억 장소에 결과값들을 저장해 놓고, 단순히 참조해서 사용한다.
( 밑에 보면 z[] 배열을 볼 수 있는데, 그것이 바로 요것!)
→ "Solve problem for input size 1...i-1, and use it for solving problem with input size i; then iterate."

⊙ 계단을 오르는 문제로 Dynamic Programming을 이해해보자.
총 n개의 계단이 있을 때,
T(n): n개의 계단을 오르는 총 방법의 수.
T(n-1): n-1 계단까지 오르는 방법의 수 (1칸 남은 상태)
T(n-2): n-2 계단까지 오르는 방법의 수 (2칸 남은 상태)

그리고 계단은 보통 한 번에 한칸, 두칸씩 오르기도 한다. (지식인은 급하면 세 칸씩도 오르더라만은... 나에겐 불가능이므로 제외!)
그러면, 내가 지금 n개의 계단을 올랐다면, 그것은 n-1번째 계단에서 한 칸 오른 것이거나, n-2번째 계단에서 두 칸 올라서 도달한 것이다. 그래서,
T(n) = T(n-1) + T(n-2) : recurrence equation (점화식 -ㅇ-)
가 성립한다. 그리고 다음과 같이 표현된다.
T(n) = ( ((√5)+1 )/2 )ⁿ

이것이 바로, DP의 fundamental intuition 이다. 대충 어떤 것인지 느낌이 오시는지? ^^

⊙ Prefix Dictionary
: 이것은, Dictionary 속에서 특정 phrase(여기에서는 encoding의 대상이 되는 문자들의 단위라고 생각하면 된다.)의 앞머리가, 같은 dictionary에 있는 다른 phrase이기도 하다는 것이다. 이는 tree 구조로 표현이 가능하며, 그림으로 나타내면 다음과 같다.

Prefix Dictionary


이 prefix dictionary의 전제는, ∑ = {A, B} 이며 최대 두 문자까지 encoding이 가능하다는 것이다. 또한 이것은 prefix code 이다.

이제, 본격적인 encoding 작업을 해보자.
입력 문자열이 AABABBAA일 때, 어떻게 하면 가장 짧은 encoding이 가능할까? (A는 0, B는 1로 나타내면 8개로 가능하다~ 할 수 있겠지만.... -.- 이건 간단한 예이고, general한 과정으로 풀어보자..흐흐)
이것은, 앞의 계단 문제와 매우 흡사하다. phrase를 encoding할 때, '이번에 encoding할 문자를 한 문자로 볼 것이냐, 이전것과 함께 두 문자로 불 것이냐?'는 것은 한 칸씩 오를 것이냐, 두 칸씩 오를 것이냐와 같다. 그래서 총 문자열 수는 총 계단수와 같다.

다음의 DP 알고리즘을 살펴보자.
z[1:n] : z[i]에는 i번째 까지 parsing했을 때 가능한 최소의 길이를 담아둔다.

z[0] ← 0
for i ← 0 to n
z[i] = ∞
for j ← i-1 down to 1
z[i] ← MIN(z[i], z[j] + length of codeword of input[j+1:i])

이것은, 길이 k인 phrase를 사용하게 되는 DP 알고리즘으로, O(kn) =O(n)이다.

지금 우리가 예로 보고 있는 것은, k=2이다. encoding해보자.
Input : AABABBAA
1. 제일 먼저 A가 등장했으므로, 10으로 encoding하고, z[0] = 2.
2. 그 다음 A가 나오면, 그냥 A로 parsing하면 10으로, z[1]= z[0]+2=4이고, 앞의 A와 함께 AA로 parsing하면 11로, z[1]=2가 되므로, z[1]=2가 된다.
3. 다음 문자는 B로, 그냥 B로 parsing하면 0000으로, z[2] = 2+4=6이 되고, 앞의 문자와 함께 AB로 parsing하면 z[2] = z[0] + 2 = 4가 되므로, z[2]=4이다.
4. 이런 식으로 반복하면, z[] = {2,2,4,5,6,9,9,11}로, 최소값이 들어가서, 전체 encoding의 길이는 11이 된다.

만약 k=3이라면, z[5]를 계산하기 위해서 z[4], z[3], z[2]까지 거슬러 올라가 보게 될 것이다.

여기에서 우리는, DP에서 z[n]이 매우 중요한 역할을 하고 있다는 것을 알 수 있다. 이것은 DP의 큰 특징 중에 하나이다.

⊙ Knapsack Problem (0-1 Knapsack Problem)
아주 간단한 예로, Knapsack Problem에 대해 이해해보자.
▪ knapsack의 크기가 50일 때, 어떤 물건들은 넣어야 가장 이익일까?
물건 1 : 부피 10, 가격 60만원 // 단위 부피 : 6만원
물건 2 : 부피 20, 가격 100만원 // 단위 부피 : 5만원
물건 3 : 부피 30, 가격 120만원 // 단위 부피 : 4만원
단위 부피로 생각해보면, 물건 1, 2를 챙겨야 겠지만(160만원), 사실 물건 2,3을 챙겨야 한다 (220만원). 이건 그냥 딱 봐도 알겠는데, 문제는! 물건이 무지무지 많으면 어쩌냐는 것이다! 이럴 때, DP를 사용한다. :)

1. A[1:n] 배열을 정의한다. 이것은 바로 knapsack이다. 1≤j≤n이라고 했을 때, 각 단계의 j에는 1 만큼 해당되는 부피의 물건을 넣을 수 있게된다. 그리고 j단계에서의 최대 이익값을 담고 있는 변수 maxBenefit(j)=0으로 초기화한다.
2. 전체 물건들의 집합을 S라고 했을 때, j를 하나씩 증가시키면서 그 때 knapsack A에 들어갈 수 있는 최대 가치의 물건 s를 넣는다.
3. 현재 j=i이고, s의 크기가 k였다고 가정하자. 그러면 j=i에서 j=i-k까지 물건 s로 채우고, 나머지는 j=i-k=1 단계 때의 물건들로 채워준다. 그리고 새롭게 갱신되는 maxBenefit(i)값 (= maxBenefit(i-k-1) + k의 가치)을 maxBenefit(i-1)과 비교해서 더 커졌다면 S=S-{s}로 만든 뒤, A의 상태를 저장한다. 이 때, maxBenefit(i-1)에 비하여 총합 가치가 커진 것이 아니라면, 이번 step은 차라리 빈 공간으로 둔다.
4. 2단계를 j=n이 될 때 까지 반복한다.

KnapSack Problem


이렇게 DP를 사용하게 되면, j=i-k=1 번째의 최적화 답을 가져오는데 걸리는 시간은 O(1)이므로, n을 Knapsack크기, m을 물건의 개수라 하면, running time은 O(nm)이 되고, n과 m이 비슷할 때에는 O(n²)으로 polynomial time이 된다.

⊙Matrix-chain Multiplication
행렬의 곱을 어떤 순서로 행하면 가장 빠르게 할 수 있는가에 대한 문제인데, 앞의 3가지 예제외는 달리, 복잡하므로 따로 다루어야 겠다. (언제 할 지는 모르겠다. -.- )

⊙ Dynamic Programming VS Greedy Algorithm
DP에서는 모든 것이 정수라는 가정하에서 이루어졌다. 그런데, 정수가 아니라면? 예를 들어, Knapsack에서, 물건을 나눌 수 있다면 어떻게 할 것인가? (우유나 금가루 같은것들.) 이것은 바로 fractional knapsack problem으로, Greedy algorithm에 속한다. Greedy algorithm은 말 그대로, '탐욕적인 알고리즘'이다..;;


출처 : http://vorlon.eecs.cwru.edu/~kxm73/ : 덮옹님 홈페이지. 므흣.
Posted by 스니

댓글을 달아 주세요

  1. 스니스니

    앗. 이런 걸 읽는 분이 계실 줄이야 -ㅇ- 반갑습니다.
    그런데 매우 애석하게도.. 저도 잘 모르겠네요. -_-;;
    그렇게 푼 이유가 있었는데 기억이 안나는건지...
    그냥 그렇게 풀었던건지... -_-;
    알게 되면 다시 올리도록 하죠 .. ^^;;

    2005.01.09 14:13 [ ADDR : EDIT/ DEL : REPLY ]

9.2 Tries
KMP나 BM 알고리즘에서는 search 속도를 높이기 위해 pattern을 preprocess했지만(failure function, last function), Tries에서는 text를 preprocess한다. 따라서, fixed text에 연속된 query들이 있을 때 사용한다. 처음에 text를 preprocessing하는 데 비용은 많이 들지만, 이것은 나중에 계속되는 query 속도를 증가시킴으로 보상된다.
trie 는 'a tree-based data structure for storing strings in order to support fast pattern matching'이다. information을 retrieval 하는데 주로 사용된다고, "retrieval"에서 이름을 따왔다. trie에서 지원하는 주요 query operation들로는, pattern matchingprefix matching이 있다.

1) Standard tries
⊙ S에 대한 standard trie 는 ordered tree T로, 다음과 같은 성질을 가진다.
1. T의 root를 제외한 모든 node에는 ∑의 한 문자가 labeled.
2. ordered tree 이므로, child는 정렬되어있다.
3. root->external path는 S의 string이 된다.
trie에서는, no string in S(∑으로 만들어진 string들의 집합) is a prefix of another string. 밑에 있는 trie 구조를 보면 알겠지만, 한 string이 다른 string의 prefix가 되면, 즉, bil, bill 이란 단어는 함께 S에 있으면 안된다. 이것때문에, S의 string은 unique하게 external node랑 짝을 이루게 되고, 이는 search를 간단하게 만든다. 또한, trie에서는, string들의 common prefix를 간결하게 저장한다.
→ 따라서, standard trie는
▪ 모든 internal node는 최대 d(∑ size)개의 child 가진다.
▪ s(string개수)개의 external을 가진다.
▪ 높이는 가장 긴 string의 길이와 같다.
▪ 전체 node 수는 O(n)이다. n은 total length.

⊙ Search : root에서 내려가면서 string을 찾는다. path가 존재하고, external node에서 끝나면, 해당 string이 존재하는 것이고, running time은 O(dm)이다. (d는 size of ∑이고, m은 size of string이다.) 최대 m+1개(root 1개 포함)의 node를 visit하고, 각 node에서 O(d) 걸린다. 여기에서, dictionary of characters를 hash table이나 lookup table로 구현하면 O(d)를 O(1) 이나 O(logd)가 될 수 있지만, d는 주로 constant이므로, 그냥 간단하게 O(d) approach를 사용한다.
따라서, standard tires는 word matching에 사용된다. word matching은 말 그대로, text에 있는 word를 찾는 것이다. 이는, text에서의 임의의 substring을 찾는 것(앞에서 배웠던 Brute-Force, BM, KMP와 같은)이 아니라, text에서의 한 단어와 정확히 일치하는 단어만 찾는것이다. tire를 사용하면, 길이 m인 단어를 찾는데 걸리는 시간은 역시, O(dm)이다. 이는 간단하게 prefix matching에 사용될 수도 있지만, pattern이 proper suffix이거나 두 단어로 span했을 때에는 효율적으로 수행되지 못한다.

Word matching and prefix matching with a standard trie



⊙ Standard Trie 만들기
Standard trie를 만드는 것은, 아주 직관적이다. 그냥 S에 있는 string들을 trie T에 한 번에 하나씩 넣어주면 되는데, prefix-free이므로, 한 word를 넣을때, root부터 탐색을 하다보면, 한 internal node에서 멈추게 된다. 그러면 pattern의 그 다음 char부터는 child node를 만들어가면서 insert 해주면 된다. 역시, 한 단어를 insert하는데 걸리는 시간은 O(dm)이다. 따라서, S에 속한 string들의 총 길이가 n이라하면, trie하나를 만드는 데 걸리는 시간은 O(dn)이 된다.

⊙ Performance
전체 노드 수의 worst-case는, 모든 string이 다른 string과 common prefix를 가지지 않을 때이다. 이 때에는, 모든 internal node는 1개의 child node를 가지게 되기 때문이다.


2) Compressed tries
Standard trie에서의 공간 낭비 때문에 만들어진 것이 compressed trie이다. Standard trie에서, 많은 node들이 child가 1개이고, 이것은 단어 수보다 node 수가 더 많을 수가 있어서 낭비인 것이다. 따라서, compressed tire는 standard trie와 비슷하지만, 모든 internal node는 각각 최소 2개의 child node를 가진다.
Internal node v가 root도 아닌데 child node를 한 개 가지고 있으면 그 node는 redundant하다 하고, 이런 redundant node들의 chain을 하나의 node로 만든다.

Compressed Trie


⊙ Compressed Trie의 특징
▪ 모든 internal node는 2~d개의 child node를 가진다.
▪ s개의 external node를 가진다.
▪ 전체 노드 수는 O(s)이다.

⊙ Compact Representation
Compressed trie가 진짜 장점을 가지기 위해서는, 보조적인 index구조를 가져야 한다. 이 보조적인 index 구조는, 따로 저장할 필요는 없고, primary structure에 이미 저장된 string들의 collection에 구현된다.
예를 들어, S가 S[0], S[1], ..., S[s-1]의 배열이라 하자. 한 노드에 char들을 바로 적지 말고, (i, j, k) 로 적어넣는다. 이것은 S[i][j..k]를 의미하는 것으로, S[i]의 j~k 번째의 substring이라는 의미이다.

Compact Representation




3) Suffix tries
한 String X에 대한 Suffix trie는 X의 모든 suffix들의 compressed tire이다. (suffix tree, position tree라고도 한다.) Trie이기 때문에, 한 suffix가 다른 suffix의 prefix가 되지 않게 하기 위해서, 기존의 ∑에 없던 문자 $를 suffix 뒤에 붙인다. 예를 들어, X가 "amizemize" 라면, 뒤의 mize는 mizemize의 prefix가 될 수 있기 때문이다. 그러나, mize$는 mizemize$의 suffix이기는 하지만 prefix는 아니다.
그리고 compact representation은 더 간단하다. (i,j)로 나타낼 수 있는데, 이것은 X[i..j]를 가리킨다.

Suffix Trie for "minmize" and its compact representation



⊙ Saving Space
string의 길이가 n일 때, 전체 suffix들의 길이의 합은,
1+2+3+...+n = n(n+1)/2
이므로, suffix들을 저장하는데 드는 공간은 O(n²)가 된다. 하지만, implicitly O(n) 의 공간이 사용된다.

⊙ Suffix trie 만들기
전체 suffix들의 길이는 string의 길이를 n이라 할때, O(n²)이다. 따라서, standard trie와 같은 방법으로 만들면 O(dn²)의 시간이 걸린다. 그러나 compact suffix trie는 O(n) 시간안에 만들어지지만, 복잡해서 여기에서는 다루지 않는다.

⊙ Using a Suffix Trie
arbitrary pattern matching을 지원하고, O(dm) 시간 걸린다.
Posted by 스니

댓글을 달아 주세요

1. Strings and Pattern Matching Algorithms
T : text (길이 n)
P : pattern (길이 m)

1) Brute Force Pattern Matching
: 가장 기초적인 방법. text의 처음부터 끝까지 alphabet 하나씩 옮겨가며 비교. 따라서, TC 는 O( (n-m+1)m ) = O(nm) => O(n^2)

Brute-force pattern matching



2) The Boyer-Moore Algorithm
: P와 sizable fraction of T의 비교를 줄여준다.
Brute-Force 알고리즘은 unbounded alphabet에서도 사용 가능하지만, BM 알고리즘은 finite size에서만 가능하다.
=> alphabet이 moderately sized하고 pattern이 상대적으로 길 때 가장 빠르다.

(*) Two heuristics
1. Looking-Glass Heuristic : P의 제일 뒤부터 compare한다.
2. Character-Jump Heuristic : mismatch 일어나면 (T[i] = c),
pattern에서 'c' 포함하면 (역시 backward로 검사) 거기까지 pattern shifting,
pattern에 'c'가 없으면 그 다음까지 pattern 모~두 shifting
=> last occurrence function 만들어 사용.
(*) Last-Occurrence Function
L(c) = P[i]의 가장 큰 인덱스 i (pattern에 포함 안되면 -1)
Pattern을 뒤에서 앞으로 한 번 scan해야하고,
alphabet 전체도 한 번 scan해야하므로 (-1인 것 찾기)
last-Occurrence Function의 TC = O(m+s) // s는 alphabet size

Boyer-Moore pattern matching

(case1 은 last occurrence가 j를 pass 한 경우 그냥 한 칸만 shift 하는 것이다.)
worst-case : T = aaaa.....a, P = baaa....a 일 때.
O(nm + s) 가 된다. 거의, Brute-Force 알고리즘이랑 막상막하
그러나, English text와 같은 text에서는 skip이 많이 일어나서 효과적이다. experimental evidence로, 5 문자 pattern string에서는 비교가 0.24번 일어났다.
그리고, 이 것은 simplified된 BM 알고리즘이고, 실제는 다른 shift heuristic(KMP에서 아이디어)을 사용하여, running time은 O(n+m+s)이다.

3) The Knuth-Morris-Pratt Algorithm
: Brute-Force와 BM 알고리즘에서는, match가 실패하면, 그 전에 compare 했던 information을 다 버리고 from scratch로 알고리즘을 수행했다. 그러나 KMP 알고리즘에서는 전에 비교했던 정보를 다 이용하여, O(n+m)의 수행시간을 갖는다. 이것은, worst case에 text와 pattern 전 체를 최소 한 번 읽어들인다는 것이다. 그래서 left-to-right로 pattern을 text와 비교하지만, shift를 더 지능적으로 하기 때문에 Brute-Force 알고리즘 보다는 훨씬 효율적이다. (어떤 경우에서는 BM 보다 못하기 때문에, BM 보다 효율적이라 말할 수는 없다. )

KMP 알고리즘의 핵심은, Failure Function이다. f(j)는 P[1..j]의 suffix인 가장 긴 P의 prefix 길이이다. (convention으로, f(0) = 0 ) 이 Failure Function은 pattern 내에서 repeated substring을 "encodes" 해주기 때문에 매우 중요하다.

Knity-Morris-Pratt pattern matching


i never goes back!

(*) Performance 증명
failure function 계산시간 제외하면, KMP의 running time은 while-loop의 iteration 수에 비례한다. 분석을 위해서 k (= i-j)를 두어 T에서 pattern P가 shift된 total amount 라 하면, k<=n임을 알 수 있다. loop 실행중에는 다음 세 가지 경우 중 하나이다.
case 1: T[i] = P[j] -> i++, k는 그대로 (j++ 이므로)
case 2: T[i] =/= P[j] AND j>0 -> i는 그대로, k는 최대 1증가 (k가 i-j에서 i-f(j-1)이 되고, f(j-1) < j 이기 때문)
case 3: T[i] =/= P[j] AND j = 0 -> i++, k++ (j가 그대로임)
따라서, KMP에서 while-loop의 총 실행 수는 최대 2n 이다.
(*) KMP Failure Function 만들기
여기에 사용된 알고리즘은, KMPMatch 알고리즘과 비슷한, "bootstrapping" 프로세스이다. else if j>0 then 부분에서, f(j-1)을 사용하고 있는데, i>j 이기 때문에 f(j-1)은 항상 정의되어있다.

전체적으로, KMP 알고리즘의 running time = O(n+m) 이다.
(s에 영향을 받지 않는다. )
Posted by 스니

댓글을 달아 주세요

Disjoint set 에서 중요한 operation 은,
1. union : O(1)
2. find : (n)
이다.

union 은 주어진 두 집합의 모든 원소가 동일한 멤버쉽을 갖게 만드는 연산

find 는 집합의 구성가능 원소가 모두 알려져 있는 상태에서, 특정한 원소가 특정한 집합의 멤버쉽을 갖고 있느냐를 알아내는 연산

(출처 : 엠에센을 통한 1:1 지식 검색 서비스 =33 )
Posted by 스니

댓글을 달아 주세요

2001년 DS 시간에 배웠지만, 까먹었던... ( 한 두개냐. -.- )

Theorem
1. An idea that has been demonstrated as true or is assumed to be so demonstrable.
2. Mathematics A proposition that has been or is to be proved on the basis of explicit assumptions.
: 증명 필요. 독립적.

Lemma
1. A subsidiary proposition assumed to be valid and used to demonstrate a principal proposition.
2. A theme, argument, or subject indicated in a title.
3. A word or phrase treated in a glossary or similar listing.
: theorem construct 하는데 필요하다. 보조 정리.

Corollory
1. A proposition that follows with little or no proof required from one already proven.
2. A deduction or an inference.
3. A natural consequence or effect; a result.
: 증명 필요 없음. theorem이랑 lemma에서 증명되어 너무 직관적인 것.
Posted by 스니

댓글을 달아 주세요

R-1.2, R-1.6, R-1.7, R-1.8, R-1.12, R-1.13, R-1.14, R-1.21,

R-1.22, R-1.23, C-1.13, C-1.27, pp. 47-53 in the Text

Due on Sept. 10, 2004.

다음 주 금요일까지군.... 에잇!
담주부터 하면 되겠다. -.-
Posted by 스니

댓글을 달아 주세요