알고리즘 6주차 강의

 

Huffman Codes: Text Encoding

Encoding과 Decoding. 전자에서 Analog신호를 Digital로 바꿀때 Encoding이라고 한다. 전산에서는 프로그래밍, 부호화를 Encoding이라고 한다. Data를 0과 1의 신호로 바꾸는 것을 의미함. 반대의 과정을 Decoding이라고 부름. 공백도 캐릭터로 처리가 된다. 17byte보다 적게 어떻게 표현하는가

 

Huffman code

12개의 케릭터를 4비트로 표현할 수 있다. 4비트로 충분하다. 이전에 사용했던 17byte에 비해 Compact하게 표현할 수 있게 된다. 2개의 방법 둘 다 fixed layer라고 표현한다. 

 

Huffman Codes

어떤 케릭터는 3bit 어떤 케릭터는 4bit로 사용해서 bit수를 save할 수 있도록 만든다. 이렇게 하는 것을 Huffman code라고 부른다. Variable length라고 부른다. 

 

Prefix codes

Prefix는 무엇인가. 1010이고 10 이면 10이 Prefix가 된다. 앞에 공통된 것을 Prefix라고 부른다. 
i까지 prefix의 관계를 가지고 있는 것이다. 

 

Why Prefix codes

Prefix가 아닌 경우를 살펴보자. prefix 관계에 있는 것들이 존재하므로 prefix code가 아니다. star라는 것을 encoding 하고 decoding을 진행할 때 잘 못 split을 해버리면 잘못된 단어를 가져오게 된다. 그 이유는 Prefix 코드가 아니기 때문이다.

 

Why are Prefix codes Unambiguous

첫 번째 케릭터를 애매하지 않게 설정하는 것이다. Prefix 하다면 명확하게 구분할 수 있다.

 

Prefix code

다른 codeword의 prefix가 아닌 것을 Prefix code라고 부른다. 가장 최소의 메모리를 활용해서 Encoding을 할 수 있다는 것. Decoding을 할 때 하나씩 counting을 하면서 Choice가 하나밖에 없을 때까지 간추리면서 정하는 방법이다. 

 

Decoding/encoding tree

Frequency는 발생한 케릭터의 빈도수이다. 모음보다 자음이 더 나올 수 있기 때문에 a의 숫자가 더 많이 존재한다. a : 3bit x 45,000 ... 이렇게 계산이 된다. 

 

Cost of encoding a file

frequency와 각각 비트에 해당하는 것을 곱하게 된다.

 

Huffman Code

데이터를 압축할 수 있고 Prefix를 최소가 되도록 만들 수 있다. 

 

Huffman's Algorithm

Character의 개수 C를 n에 넣고 각각의 C를 Priority Queue에 넣는다. Extract Min 하면 맨 처음 f 그 다음 e가 나온다. 왜 Greedy인가. 해당 순간에 가장 Frequ 가 가장 적은 것을 선택해서 진행하기 때문이다. 시간 복잡도는 nlgn에 해당한다. 케릭터 개수가 몇 개 인지에 해당하는 것은 세타 N 이라고 할 수 있다. 2번 줄은 Priority Queue이므로 빅오 nlgn 더 정확하게 하면 세터 N이라고 표현할 수 있다. loop는 세타 N만큼 돌아간다. 각각의 Extract Min은 height에 해당하는 빅오 lgn에 해당하는 만큼 걸린다. 덧셈은 세타 1이고 Insert는 lgn에 해당한다. lgn이 n만큼 돌아가므로 nlgn이 Running time에 해당한다고 할 수 있다. f와 g를 Extract하게 되고 더해서 다시 Insert하게 된다. 

 

---

 

 

The Knapsack Problem
도둑이 가방에 제일 비싼 물건을 어떤 것을 넣어야 하는지와 같은 느낌

 

The Knapsack Problem
2가지 버전이 존재한다. 1번 째의 경우 물건을 나눌 수 없는 경우이고 2 번째의 경우 일부만을 가져올 수 있는 경우를 의미한다.
1번은 DP로 풀 수 있고 2번은 Greedy로도 풀 수 있다. 1번은 Greedy 방법으로 푸는 것이 불가하다.
둘다 optimal substructure property가 존재한다. 

 

Fractional knapsack problem
Theif가 가장 큰 값을 가진, per pound 당 가장 큰 것을 가진 것을 가져온다. 그랬는데도 가져올 수 있으면 다음 것을 넣게 된다.

 

0-1 Knapsack Problem
knapsack의 capacity는 W만큼 감당할 수 있다고 하고 S의 set으로 구성되어있다. 각각의 Item 들은 Index와 Value가 존재한다.

 

W라는 값에 해당하는 것들은 Integer로 가정한다. Weight을 20까지 감당할 수 있다고 가정한다.

 

 

Brute force approach
n개의 아이템이 있다면 2^n개의 아이템들이 존재한다. 각각의 경우에 대해서 Benefit Value가 얼마인가를 계산하게 된다. 모든 경우가 가능성이 없지 않으므로 모두 계산을 해야한다. 감당하지 못하는 W의 경우 제외를 하게 된다. W 안에서 이익이 가장 큰 것을 취하게 된다. Total Value가 최대치이고 그것의 무게는 감당할 수 있는 W보다 작거나 같은 경우에 해당한다. 세터 2^n이라고 표현할 수 있다. 이 경우 굉장히 느린 알고리즘이라고 할 수 있다.

 

0-1 Knapsack Problem
fractional knapsack은 Greedy가 통한다. DP를 하기 위해서 Subproblem을 잘 정의해야 한다. Optimal Substructure를 유지시킬 수 있는 SubProblem을 잘 정의해야 한다. Optimal Substructure를 갖지 못하는 경우를 아래처럼 확인할 수 있다. n개 중에서 1번 부터 k번 까지 정의할 수 있는 것을 보게 된다. 전체 1부터 N까지 중 k를 가져오도록 정의하는 것을 의미한다.

 

Dynamic Programming
N개의 아이템 중 k개에 해당하는 아이템들을 subProblem으로 정의하면 옳지 않음을 볼 수 있다.

 

Dynamic Programming
4개를 집어 넣더라도 Weight이 14밖에 되지 않고 4개의 아이템의 weight와 value를 이렇게 가져가게 된다. S5를 생각하게 되면 S4를 이용하고 5번째 Weight를 사용하려고 하면 4번을 선택하지 않고 5번을 고르게 된다. S5 는 S4를 이용하지 않고 풀었다. 그러므로 Optimal Substructure가 있다고 할 수 없다. 이렇게 된 경우 Sub Problem을 제대로 작성하지 못한 경우에 해당한다. 다른 경우로 Define을 하고 풀이를 진행해야 한다. 

 

Dynamic Programming
Fractional Knapsap은 자를 수 있으므로 Greedy로 풀 수 있고 0-1은 DP로 풀어야 한다. 그렇다면 어떻게 Optimal SubStructure를 가지도록 어떻게 구성을 해야 하는가.

 

Defining a program
S4는 S5의 Part가 아니다. flaw, 결함이 있다는 것. SubProblem을 할 때 하나의 파라미터 W를 두게 된다. Weight를 모두 포함해서 두 개의 파라미터로 정의하고자 한다. B[k,w],에서 B는 Benefit에 해당한다. 1부터 k에 해당하는 아이템과 w는 각 아이템에 해당하는 Weight에 해당한다. 

 

Recursive Formula for subproblems
B[k,W]는 최종 Solution이 된다. 이것의 SubProblem은 어떻게 정의 되냐하면 B[k-1,w]가 된다. 또는 B[k,w-1]도 SubProblem이 될 수 있다. k번째 아이템을 knapsack에 넣는 것이 좋은가 좋지 않은가를 판별해야 한다. 첫 번째 식의 경우 넣으려는 weight의 합이 W보다 큰 경우이므로 못집어 넣기 때문에 이전 Subproblem을 취하면 된다. 만약 k번째 아이템을 집어넣을 수 있다고 하면 Benefit의 최대값을 계산해야 한다. k-1번째의 아이템을 비교해서 

Pseudocode