이전글 https://yonghwankim-dev.tistory.com/313 [알고리즘][압축] 압축(Compression) #3 Huffman Tree 생성 이전글 https://yonghwankim-dev.tistory.com/306 [알고리즘][압축] 압축(Compression) #2 Huffman Method with Run-Length Encoding 1. Huffman Method with Run-Length Encoding 파일을 구성하는 각각의 run들을.. yonghwankim-dev.tistory.com 이전글에서 문자열을 압축하기 위한 Huffman Tree를 생성하였습니다. 이번 글에서는 생성한 Huffman Tree에 Codeword를 부여하도록 하겠습니다. 문자열 "AAABAA..

이전글 https://yonghwankim-dev.tistory.com/306 [알고리즘][압축] 압축(Compression) #2 Huffman Method with Run-Length Encoding 1. Huffman Method with Run-Length Encoding 파일을 구성하는 각각의 run들을 하나의 super-symbol로 봅니다. super-symbol들에 대해서 Huffman coding을 적용합니다. 예를 들어 문자열 AAABAACCAABA은 5개의 sup.. yonghwankim-dev.tistory.com 이전글에서 문자열 "AAABAACCAABA"에서 Run을 탐색하고 배열 리스트 runs에 저장하였습니다. 배열 리스트 runs에 Run들은 다음과 같이 저장되었습니다. 0..

1. Huffman Method with Run-Length Encoding 파일을 구성하는 각각의 run들을 하나의 super-symbol로 봅니다. super-symbol들에 대해서 Huffman coding을 적용합니다. 예를 들어 문자열 AAABAACCAABA은 5개의 super-symbol들 AAA, B, AA, CC, A로 구성되며, 각 super-symbol의 등장횟수는 아래와 같습니다. symbol A C A B A run length 3 2 1 1 2 frequency 1 1 1 2 2 Prefix Code 이진트리 생성 과정 AAABAACCAABA은 1100110111100100으로 인코딩됩니다. 2. 제 1단계 : Run과 Frequency 찾기 압축할 파일을 처음부터 끝까지 읽어서 ..

학습목표 1. Huffman Coding에 대해서 학습 2. Prefix Code에 대해서 학습 3. Huffman Coding 수행과정에 대해서 학습 4. Run-Length Encoding에 대해서 학습 1. Huffman Coding이란 무엇인가? 허프만 코딩은 입력 파일의 문자 빈도수를 가지고 최소힙을 이용하여 파일을 압축하는 과정입니다. 예를 들어 6개의 문자 a, b, c, d, e, f로 이루어진 파일이 있다고 가정합니다. 문자의 총 개수는 100,000개이고 각 문자의 등장 횟수는 다음과 같습니다. 위 그림에 따른 Fixed-length code 방식의 필요 비트 수 각각의 문자를 표현하기 위해서 3비트가 필요하며, 파일의 길이는 300,000 bit가 됩니다. 위 그림에 따른 Variab..

학습목표 1. Knapsack Problem에 대하여 학습 2. Knapsack Problem 순환식 정의 3. Java언어 기반 코드 구현 1. Knapsack Problem Knapsack Problem은 n개의 아이템과 배낭이 존재한다고 가정할때 배낭의 용량을 초과하지 않으면서 아이템의 가격이 최대가 되는 아이템들을 탐색하는 문제입니다. 예를 들어 아래 그림과 같이 아이템의 무게(w)와 가격(v)의 표가 있을 때 배낭에 넣을 수 있고 가격이 최대가 되는 아이템 조합은 3번과 4번 아이템입니다. 2. Knapsack 순환식 OPT(i, w) : 배낭 용량이 w일 때 아이템 1,2,...,i로 얻을 수 있는 최대 이득 경우 1 : 아이템 i를 선택하지 않은 경우 OPT(i, w) = OPT(i-1, w..

학습목표 1. Longest Common Subsequence가 무엇인지 학습 2. Longest Common Subsequence의 순환식을 정의 3. Longest Common Subsequence의 수행과정을 학습 4. Java언어 기반 Longest Common Subsequence 동적계획법 구현 1. Longest Common Subsequence 문제 는 문자열 의 부분수열(Subsequence)입니다. 는 문자열 와 의 공통 부분수열(Common Subsequence)입니다. 최장 공통 부분수열(Longest Common Subsequence, LCS)은 공통 부분수열(Common Subsequence)들 중 가장 긴 것을 의미합니다. 예를 들어 는 와 의 LCS입니다. 2. Longest..