최근의 스마트폰, 임베디드시스템 등의 정보통신 단말기는 데이터의 송 수신 및 분산처리 등의 업무를 수행하기 위하여 데이터의 크기를 축소시키는 압축률 향상이 매우 크게 대두되어졌다. 일반적으로 텍스트의 압축에는 LZW(Lempel Ziv Welch)알고리즘을 활용하고 있다. 그러나 LZW알고리즘은 1Byte 조합형 텍스트(알파벳 등)의 압축에는 효율적이나 2Byte 완성형 텍스트(한글 등)에 압축률이 현저하게 저하되는 단점을 가지고 있다. 이를 극복하기 위하여 본 논문에서는 2Byte 전위 필드(prefix)와 반복 계수를 위한 1Byte 후위 필드(suffix)를 사용하는 확장된 ELZW(EBCDIC Lempel Ziv Welch)알고리즘을 제안한다. 제안 알고리즘은 압축률 증가를 위해 압축사전을 구성하여, 알파벳, 한글, 포인터에 따라 각각 서로 다른 비트 스트링으로 적절하게 패킹된다. 제안하는 알고리즘의 성능분석을 위하여 각 140,355byte의 영문, 한글, 한영혼용 텍스트를 비교 실험하였고, 실험결과 제안한 ELZW알고리즘의 압축률은 기존의 1Byte 방식의 LZW 알고리즘보다 5.22% 더 우수하고, 2Byte LZW 알고리즘 보다 8.96% 더 우수함을 보였다.
최근의 스마트폰, 임베디드시스템 등의 정보통신 단말기는 데이터의 송 수신 및 분산처리 등의 업무를 수행하기 위하여 데이터의 크기를 축소시키는 압축률 향상이 매우 크게 대두되어졌다. 일반적으로 텍스트의 압축에는 LZW(Lempel Ziv Welch)알고리즘을 활용하고 있다. 그러나 LZW알고리즘은 1Byte 조합형 텍스트(알파벳 등)의 압축에는 효율적이나 2Byte 완성형 텍스트(한글 등)에 압축률이 현저하게 저하되는 단점을 가지고 있다. 이를 극복하기 위하여 본 논문에서는 2Byte 전위 필드(prefix)와 반복 계수를 위한 1Byte 후위 필드(suffix)를 사용하는 확장된 ELZW(EBCDIC Lempel Ziv Welch)알고리즘을 제안한다. 제안 알고리즘은 압축률 증가를 위해 압축사전을 구성하여, 알파벳, 한글, 포인터에 따라 각각 서로 다른 비트 스트링으로 적절하게 패킹된다. 제안하는 알고리즘의 성능분석을 위하여 각 140,355byte의 영문, 한글, 한영혼용 텍스트를 비교 실험하였고, 실험결과 제안한 ELZW알고리즘의 압축률은 기존의 1Byte 방식의 LZW 알고리즘보다 5.22% 더 우수하고, 2Byte LZW 알고리즘 보다 8.96% 더 우수함을 보였다.
This paper Extended ELZW(EBCDIC Lempel Ziv Welch) algorithm uses 2 byte prefix field for pointer of a table and 1 byte suffix field for repeat counter. where, a prefix field uses a pointer(index) of compression table and a suffix field uses a counter of overlapping or recursion text data in compress...
This paper Extended ELZW(EBCDIC Lempel Ziv Welch) algorithm uses 2 byte prefix field for pointer of a table and 1 byte suffix field for repeat counter. where, a prefix field uses a pointer(index) of compression table and a suffix field uses a counter of overlapping or recursion text data in compression table. To increase compression ratio, after construction of compression table, table data are properly packed as different bit string in accordance with a alphabet, Hangeul, and pointer respectively. Therefore, proposed ELZW algorithm is superior to 1byte LZW algorithm as 5.22 percent and superior to 2byte LZW algorithm as 8.96 percent.
This paper Extended ELZW(EBCDIC Lempel Ziv Welch) algorithm uses 2 byte prefix field for pointer of a table and 1 byte suffix field for repeat counter. where, a prefix field uses a pointer(index) of compression table and a suffix field uses a counter of overlapping or recursion text data in compression table. To increase compression ratio, after construction of compression table, table data are properly packed as different bit string in accordance with a alphabet, Hangeul, and pointer respectively. Therefore, proposed ELZW algorithm is superior to 1byte LZW algorithm as 5.22 percent and superior to 2byte LZW algorithm as 8.96 percent.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 본 논문에서는 2바이트 한글과 1바이트 영문을 압축하는데 있어서 기존의 LZW계열의 압축 알고리즘인 LZW1과 2바이트 한글과 1바이트 영문을 효과적으로 압축할 수 있는 LZW2 알고리즘에 대하여 분석하고, 한글과 영문 혼용 텍스트의 압축에 적합하도록 새로운 ELZW(EBCDIC Lempel Ziv Welch) 알고리즘을 제안한다.
따라서 이러한 불필요한 비트열을 압축 테이블에서 압축 파일로 데이터를 출력할 때 제거하는 것이 바람직하다. 따라서 본 논문에서는 압축 테이블에서 불필요한 비트를 삭제하는 프로그램을 추가하여 우수한 압축률을 갖도록 하였다.
따라서 본 논문에서는 [표 8]과 같은 알고리즘을 통해 압축 테이블에 저장된 데이터 중에서 실제 불필요한 데이터를 제거하여 압축 파일에 출력할 수 있도록 하는 방법을 사용하고 있다.
따라서, 본 논문에서는 기존의 LZW1과 LZW2에서 갖는 단점을 해결하기 위해서 압축 테이블의 suffix에 다음 문자를 입력하는 것이 아니라 압축 테이블 내의 반복되는 문자의 수를 계산하는 계수를 사용함으로써 다음과 같은 결과를 얻을 수 있다.
제안 방법
이 알고리즘은 2바이트 한글을 효과적으로 압축하기 위해서 초기 압축 테이블의 상위 영역에 2바이트 한글의 부호를 초기화시키는 방법을 사용하는 것이다.
따라서 본 논문에서는 한글과 영문을 효과적으로 압축하기 위해서 LZW1과 LZW2의 장점만을 취하였으며, 압축 테이블의 prefix는 한글과 영문을 위한 포인터로서 2바이트 할당하고, suffix는 1바이트로 할당하여 압축 테이블의 각 원소의 바이트 크기를 줄였다.
제안한 ELZW 알고리즘에서는 2바이트 한글과 ASCII 문자를 효과적으로 압축할 수 있도록 앞서 기술된 LZW1처럼 압축 테이블의 prefix인 상위 2바이트는 ASCII 문자와 2바이트 한글의 각 주소를 표현할 수 있도록 2바이트 포인터를 사용하며, 압축 테이블의 suffix인 하위 1바이트 계수로 사용한다. suffix는 입력 파일로부터 읽어 들인 문자가 이미 등록되어 있을 때 읽어 들인 문자열과 압축 테이블 내부에 등록되어 있는 문자와 연속적으로 일치하는 문자들의 수를 세는 계수 부분으로 사용한다.
본 논문에서 제시한 압축 테이블로부터 불필요한 비트열을 제거하는 알고리즘을 문자열 “ABC 한글 한글a 한글과 ABC 한글 한글a”를 사용하여 생성된 압축 테이블에 적용하여 압축 파일을 출력하면 다음 [표 9]와 같은 결과를 얻을 수 있다.
(2) 압축 테이블의 하위 suffix는 압축 테이블 내의 반복되는 문자의 계수로 사용함으로써 기존의 LZW1 이나 LZW2 에 비하여 전체적인 압축 파일의 크기를 증가시키는 문제점을 제거하였다.
이론/모형
한글 텍스트 파일을 압축하기 위한 LZW 압축 알고리즘은 입력 데이터를 이진 코드화하여 문자열로 나누기 위해 greedy 파싱 알고리즘을 사용한다. 압축을 수행하기 위한 기억 장소 내의 문자열 테이블의 각 원소는 2바이트로 구성된 상위 포인터(p)와 1바이트로 구성된 하위 문자(c)로 구성된다.
성능/효과
(1) 압축 테이블의 상위 prefix에만 영문 또는 한글의 주소를 입력함으로써 LZW2에서 한글이 상위 바이트와 하위 바이트로 나누어지는 문제점을 해결하여 압축 효율을 증가시켰다.
(3) 초기화 테이블 이후의 등록된 문자가 오직 하나만 일치한 경우 해당 주소를 사용하지 않고 초기화된 주소를 압축 테이블에 등록함으로써 압축 파일의 생성시 주소의 크기를 줄였다.
(4) 압축 테이블에 저장된 데이터 중에서 불필요한 비트열을 제거하는 알고리즘을 추가하므로써 최종적인 압축률을 증가시켰다.
본 논문에서 제안한 ELZW 알고리즘은 기존의 파일 압축에 비하여 압축률이 더 우수하다는 것을 얻을 수 있었다. 이는 제안한 알고리즘의 압축 테이블의 suffix는 1바이트만 사용하기 때문에 컴퓨터 내부의 주기억 장소를 절약할 수 있다.
본 논문에서 제안한 ELZW 알고리즘은 기존의 파일 압축에 비하여 압축률이 더 우수하다는 것을 얻을 수 있었다. 이는 제안한 알고리즘의 압축 테이블의 suffix는 1바이트만 사용하기 때문에 컴퓨터 내부의 주기억 장소를 절약할 수 있다. 또한 보다 효과적인 압축률을 얻기 위해 압축 파일 생성 시 압축 테이블에서 압축 파일로 데이터를 출력할 때 불필요한 비트를 제거하여 패킹하는 것이 좋다.
또한 보다 효과적인 압축률을 얻기 위해 압축 파일 생성 시 압축 테이블에서 압축 파일로 데이터를 출력할 때 불필요한 비트를 제거하여 패킹하는 것이 좋다. 실제로 한글/영문 혼용 파일의 경우 상용화되어 있는 LZW1 압축 프로그램보다 5.22% 정도, LZW2의 압축 프로그램보다는 8.96% 정도의 압축률이 증가함을 보였다.
후속연구
앞으로의 연구 과제는 한글/영문 혼용 텍스트 파일뿐만 아니라 영문, 한글 등 단일 문자 파일을 압축하는데 더욱 향상된 압축률을 갖을 수 있는 알고리즘으로의 개발이 요구된다.
질의응답
핵심어
질문
논문에서 추출한 답변
LZW알고리즘의 단점은?
일반적으로 텍스트의 압축에는 LZW(Lempel Ziv Welch)알고리즘을 활용하고 있다. 그러나 LZW알고리즘은 1Byte 조합형 텍스트(알파벳 등)의 압축에는 효율적이나 2Byte 완성형 텍스트(한글 등)에 압축률이 현저하게 저하되는 단점을 가지고 있다. 이를 극복하기 위하여 본 논문에서는 2Byte 전위 필드(prefix)와 반복 계수를 위한 1Byte 후위 필드(suffix)를 사용하는 확장된 ELZW(EBCDIC Lempel Ziv Welch)알고리즘을 제안한다.
LZW알고리즘의 단점을 보완하기 위한 방안은?
그러나 LZW알고리즘은 1Byte 조합형 텍스트(알파벳 등)의 압축에는 효율적이나 2Byte 완성형 텍스트(한글 등)에 압축률이 현저하게 저하되는 단점을 가지고 있다. 이를 극복하기 위하여 본 논문에서는 2Byte 전위 필드(prefix)와 반복 계수를 위한 1Byte 후위 필드(suffix)를 사용하는 확장된 ELZW(EBCDIC Lempel Ziv Welch)알고리즘을 제안한다. 제안 알고리즘은 압축률 증가를 위해 압축사전을 구성하여, 알파벳, 한글, 포인터에 따라 각각 서로 다른 비트 스트링으로 적절하게 패킹된다.
일반적으로 텍스트의 압축에 사용되는 것은?
최근의 스마트폰, 임베디드시스템 등의 정보통신 단말기는 데이터의 송 수신 및 분산처리 등의 업무를 수행하기 위하여 데이터의 크기를 축소시키는 압축률 향상이 매우 크게 대두되어졌다. 일반적으로 텍스트의 압축에는 LZW(Lempel Ziv Welch)알고리즘을 활용하고 있다. 그러나 LZW알고리즘은 1Byte 조합형 텍스트(알파벳 등)의 압축에는 효율적이나 2Byte 완성형 텍스트(한글 등)에 압축률이 현저하게 저하되는 단점을 가지고 있다.
참고문헌 (8)
정진욱, “리얼 타임 환경에서 압축 코딩과 암호 코딩의 결합”, 한국정보과학회논문지, 제17권, 제6호, 1990.
한승조, “완성형 한글을 위한 압축 코딩과 암호화 방법”, 한국정보과학회논문지, 제20권, 제9호, 1993.
신광철, 한상용, “LZW 알고리즘의 초기 사전 확장을 통한 효과적인 Hyper-Text 문서 압축”, 한국정보과학회논문지, 제29권, 제1호, p.689, 2002.
H. K. Reghbati, “An Overview of Data Copression Techiques,” Computer, Vol.14, No.4, pp.71-76, 1981(4),
W. H. Lenug, “Inducing Codes Form Exaples,” DCC '91, Data Compression Conference, pp.267-276, 1991(4).
M. Pechura, “File Archival Techiques Using Data Compression,” Comm.ACM, Vol.25, No.9, pp.605-609, 1982(9).
M. B. Lin, “A Hardware Architecture for the LZW Compression and Decompression Algorithms Based on Parallel Dictionaries,” Journal of VLSI signal processing systems for signal, image, and video technology, Vol.26, No.3 pp.369-381, 2004.
김대영, 이성열, 이혜영, “모바일 시스템을 위한 연결 데이터 압축 알고리즘”, 컴퓨터그래픽스학회논문지, 제14권, 제1호, pp.27-33, 2008.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.