기본 콘텐츠로 건너뛰기

개발 공부 - [Huffman Coding] 압축 (Compression) - 4

제 3단계
Codeword 부여하기

각각의 런들에게 실제로 코드워드 부여하는 법
: Huffman 트리의 리프 노드에 위치한 run 들에게 이진 codeword 를 부여할 차례이다.

-리마인드-
Prefix Code
: 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드
(codeword란 하나의 문자에 부여된 이진코드를 말함)
-리마인드 끝-

assignCodeword(prefix, node)
만약에 node가 leaf 이면
    prefix 를 node 에 할당한다. (부여한다)

아니면
    assignCodeword(prefix + '0' , node.left);
    assignCodeword(prefix + '1', node.right);


루트 
루트 자식 왼쪽 - 0 | 루트 자식 오른쪽 - 1
루트 자식 왼쪽의 왼쪽 - 00 | 루트 자식 왼쪽의 오른쪽 - 01 
ㄴ 이런 식으로 자식 위치에 따라서 나의 codeword 에 0  이나 1을 추가한다.
루트 자식 오른쪽의 왼쪽 - 10 | 루트 자식 오른쪽의 오른쪽 - 11 
루트 자식 오른쪽의 오른쪽의 왼쪽 - 110 | 루트 자식 오른쪽의 오른쪽 - 111
ㄴ 이런 식으로 추가하라는 수도 코드임

여기서 prefix를 하나의 32비트 정수로 표현한다 (8비트)
하지만 32비트 중에서 하위 몇 비트만이 실제 부여된 codeword이다.
따라서 codeword의 길이를 따로 유지해야 한다.




class Run implements Comparable<Run>{
    public byte symbol;
    public int runLen;
    public int freq;

    //트리의 노드로 사용하기 위해서 왼쪽 자식과 오른쪽 자식 노드 필드를 추가한다.
    //노드에 부여된 코드워드를 저장하기 위한 필드를 아래와 같이 추가한다.

    public int codeword; //부여된 코드워드를 32비트 정수로 저장.
    public int codewordLen; //부여된 코드워드의 길이 - 즉 코드워드의 
                            //하위 코드워드 렝스 비트가 실제 코드워드이다.


}


루트는 코드워드 길이가 nothing 인 거고

루트 - nothting ( = "")
루트 자식 왼쪽 - 0(0000..... 0) | 루트 자식 오른쪽 - 1 (0000......0001) 

이런 식으로 실제 32비트 정수로 저장될 것이다.

요고는 비트 연산으로 코딩해야 할 것인데, 
codeword 구현 할때는 left shift 연산 사용해서 << ← 사용한 뒤에,
0이나 1을 뒤에 붙여주는 식으로 구현해야 함.

0011 1100 을 << 1 하면 0111 1000 으로 한 칸 shift 해서 2배 증가 함
60 -> 120

그래서 0011 1100 을 << 1 + 1 해서 0111 1001 해서 2배 증가 + 1추가 함
↑ 이게 구현하려는 것임 (0 추가 or 1 추가 해서 자식 애들 분기 할 수 있도록 함)




private void assignCodewords (Run p, int codeword, int length){
//assignCodewords(theRoot, 0,0)으로 처음 호출한다.
//codeword는 노드 p에 부여된 codeword
//length는 노드 p에 부여된 codeword의 길이
    
    if(p.left == null && p.right == null){
        p.codeword = codeword;
        p.codewordLen = length;
    }
    else{
        assignCodeword(prefix + '0' , node.left); //이런 식으로 구현 하지는 않음
        assignCodeword(prefix + '1', node.right); //이런 식으로 구현 하지는 않음

        //왼쪽 자식노드에게는 codeword의 뒤에 0을 추가
        //오른쪽 자식노드에게는 1을 추가
    }


}

-------------------------------------------------------------------

public class HuffmanCoding {
    
    //이렇게 함수로 빼서 사용

     public void compressFile(RandomAccessFile fIn) {
         collectRuns(fIn);
         createHuffmanTree();
         assignCodewords(theRoot, 0, 0);
     }

    static public void main (String args[]) {
        HuffmanCoding app = new HuffmanCoding();
        RandomAccessFile fIn;
        
        try {
            fIn = new RandomAccessFile(“sample.txt”,”r");
             app.compressFile(fIn);
            fIn.close();
        } catch (IOException io) {
            System.err.println("Cannot open " + fileName);
        }
    }
}













댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!

운동 정보 - 어메이즈핏 밴드 5 스마트밴드 나이키 런 클럽(NRC = Nike Run Club) 연동

 나이키 런 클럽 쓰려고 산 어메이즈핏 밴드5 인데 연동이 영 어려워서 찾아보고 써봤다. 1. Zepp 앱은 연동이 되어 있어야 한다. 2.  Zepp 앱 -> 프로필 -> 내 기기 -> Amazfit Band 5 3. 검색 가능 : 켜짐 활동 심박수 공유 : 켜짐 연결 제한 : 꺼짐 (기본) 백그라운드에서 실행 : 제외로 등록 4. NRC(나이키 런 클럽) 앱 -> 설정 -> 러닝 설정 -> 기기 5. 심박수 표시 -> 블루투스에서 AmazFit Band 5 누르고 NRC 즐기면 된다! * 안드로이드 이용자입니다.