본문 바로가기

Computer125

[Algorithm] Huffman Huffman 부호화의 기본 개념은 각 단위 정보를 표현하는 비트 수를 단위 정보 들의 출현 빈도를 기반으로 할당하는 것임 빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, 빈도가 낮은 정보는 비트 수를 많이 사용하여 표현해서 전체 데이터의 표현에 필요한 비트의 양을 줄임 대표적인 가변 길이 코드이며, 영상 압축에 많이 사용됨허프만(Huffman) 압축기법허프만 압축기법은 1954년 허프만에 의해 제안된 압축 방식으로 오늘날에도 널리 이용되고 있다. 이 기법은 정보원 데이터내의 각 문자에 대한 발생빈도를 조사해 자주 나타나는 문자에는 보다 짧은 부호어를, 그리고 잘 나타나지 않는 문자에는 더 긴 부호어를 할당함으로써, 전체 압축후 부호어의 길이를 원래의 정보원 길이보다 더 축소시킬 수 있는 통계적 .. 2006. 10. 13.
Static on Java- Speed Test Static으로 선언된 메소드와 일반 메소드의 비교. 어느 정도의 속도차이를 내는지 알아보았다. 테스트 조건1. 10억 번 루프를 돌려 수행 시간을 얻는다.2. 1번을 10번 수행하여 평균을 얻는다. 결과 단위 milli-Second -- 동일 클래스 상에서 속도 체크(함수로 호출) --Normal 은 동일 클래스의 static이 아닌 변수를 1씩 증가 시키는 함수를 루프 시킨 결과.Static 는 동일 클래스의 static 변수를 1씩 증가 시키는 static 함수를 루프 시킨 결과.-- 동기화 고려된 메소드 ---Normal은 동기화로 선언한 일반 메소드를 호출.Static는 동기화로 선언한 static 메소드를 호출.-- 외부 클래스에서의 비교 값 --Normal은 인스턴스 생성 후 그 인스턴스의 .. 2006. 10. 9.
[Data Structure2] Binary Tree (Linked List) 링크드리스트를 이용한 이진트리. 재귀호출 : 노드 추가시, 전/중/후 위 순회시. 속도 : 1만번 add() 함수 호출 결과 평균 47m/s. 1만개의 노드 전/중/후 방문. 모두 1m/s 이하.(출력 시간 제외) 단점 : 노드의 갯수가 한정량 이상(본 시스템 환경 상 1000만개) 발생시 Heap Space Overflow Exception 발생. Heap Space를 증가시켜주면 되지만, 적당한 해결책 아닌 듯 함. //######################################################// //----------------------------------------------// //######################################.. 2006. 10. 9.
[Data Structure2] Max Heap (for int array) 최대히프를 구현해 보았다. 트리의 배열 표현에 대한 선행 지식이 있어야한다. //################################################################### // //---------------------------------------------------- // //구성 : 최초 배열 사이즈는 1이다. 인덱스 0에는 헤더값이 저장된다. ###############// //단점 : 배열의 요소가 하나 추가될 때 마다 배열 크기를 늘리기위한 연산이 수행된다## // // add()함수를 1만번 호출해 본 결과 평균 380m/s가 소요되었다.#############// // deleteMax()함 함수의 호출 결과과 역시 비슷한 시.. 2006. 10. 9.