Chulalongkorn University Theses and Dissertations (Chula ETD)

การปรับปรุงการเข้ารหัสเลขคณิตด้วยการจัดกลุ่มความน่าจะเป็นสำหรับเอกสารภาษาอังกฤษ

Other Title (Parallel Title in Other Language of ETD)

An improvement of arithmetic coding using probability clustering for English document

Year (A.D.)

2010

Document Type

Thesis

First Advisor

อรรถสิทธิ์ สุรฤกษ์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2010.1567

Abstract

การเข้ารหัสเลขคณิต (arithmetic coding) เป็นการเข้ารหัสแบบพิจารณาบริบทที่มีประสิทธิภาพด้านค่าอัตราส่วนการบีบอัด (compression ratio: CR) สูงวิธีหนึ่ง อีกทั้งยังเป็นการเข้ารหัสหรือการบีบอัดที่ไม่มีการสูญเสีย (lossless compression) จึงได้รับความนิยมในการบีบอัดไฟล์ข้อมูลที่เป็นทั้งตัวหนังสือ และรูปภาพ การปรับปรุงค่าอัตราส่วนการบีบอัดได้มีการค้นคว้าและวิจัยด้วยวิธีการต่างๆ เช่น การแปลงข้อมูลนำเข้าให้อยู่ในรูปที่เหมาะสม (preprocessing transformation) การประมาณค่าความน่าจะเป็นของสัญลักษณ์ด้วยฟังก์ชันการกระจายของเกาส์ การใช้ต้นแบบที่ปรับเปลี่ยนค่าความน่าจะเป็นได้ และ การใช้ทฤษฎีของเบย์ เป็นต้น ซึ่งค่าความน่าจะเป็นเริ่มต้นที่ได้ยังไม่มีความเหมาะสม สามารถปรับปรุงค่าความน่าจะเป็นเริ่มต้นนั้น เพื่อเพิ่มค่าความสามารถในการบีบอัดได้ งานวิจัยนี้ได้นำเสนอเทคนิคในการเพิ่มค่าอัตราส่วนการบีบอัดของการเข้ารหัสเลขคณิตส่วนเพิ่มขึ้นที่สามารถปรับเปลี่ยนค่าความน่าจะเป็นได้ (Incremental Adaptive Arithmetic Coding: IAAC) ในหลายเทคนิคด้วยกัน คือ การประมาณค่าความน่าจะเป็นเริ่มต้นของสัญลักษณ์ด้วยการจัดกลุ่มความน่าจะเป็น (probability clustering) การประมาณค่าความน่าจะเป็นเริ่มต้นของสัญลักษณ์ด้วยการกระจายแบบไวบูลล์ (Weibull distribution) การลดความแตกต่างของค่าความน่าจะเป็นของสัญลักษณ์ (gap reducing) ที่มีความถี่สูงสุดและความถี่ต่ำสุดให้น้อยลง และการลดทอนสัญลักษณ์ที่ไม่ปรากฏ (elimination of unused symbols) รวมถึงการพิจารณาการแบ่งไฟล์ออกเป็นส่วนๆ (file partitioning) เมื่อพบว่าค่าอัตราส่วนการบีบอัดในขณะนั้นมีค่าคงที่หรือมีค่าลดลง ผลการทดลองเมื่อนำเทคนิคที่นำเสนอไปเข้ารหัสกับไฟล์ในคลังข้อมูลแคลการี คลังข้อมูลแคนเทอเบอร์รีขนาดใหญ่ และไฟล์นิทานภาษาอังกฤษนั้น ให้ผลการปรับปรุงค่าอัตราส่วนการบีบอัดที่ดีขึ้นที่ดีที่สุดสำหรับคลังข้อมูลแคลการีเพิ่มขึ้นถึง 3.8404% และไฟล์นิทานภาษาอังกฤษเพิ่มขึ้นถึง 1.2840% เมื่อเทียบกับการเข้ารหัสเลขคณิตส่วนเพิ่มขึ้นที่สามารถปรับเปลี่ยนค่าความน่าจะเป็นได้ที่กำหนดให้ความน่าจะเป็นเริ่มต้นของแต่ละสัญลักษณ์เท่ากัน

Other Abstract (Other language abstract of ETD)

Arithmetic coding, a very effective lossless encoding algorithm, which basically rely on each probability of symbol. This approach achieves a good compression ratio (CR) as compare to other approaches. Recently, many researchers have studied and proposed various techniques in order to increase the compression ratio such as the preprocessing transformation the input with strings substitution algorithms, m-ary transformation, the estimation of probability of symbol with a specific distribution, adaptive model and Bayes theorem. Such those estimated probability of symbols may improper and thus can be improved in order to gain an increment of compression ratio. In this thesis, the compression ratio improvement techniques of incremental adaptive arithmetic coding are proposed. First, the probability of symbol clustering and Weibull distribution are employed to generate initial probability of symbols. Second, the gap reducing technique which intends to reduce the gap between the highest and the lowest probability of symbols, the elimination of unused symbols and the file partition techniques. The experiments were conducted to study and to evaluate the effectiveness of the proposed techniques on standard corpus (e.g. Calgary and Canterbury). Ordinary English novels are also included in the experiment. From the results, the proposed techniques have a good performance as compare to incremental adaptive arithmetic coding with the equally initial probability of symbols. The maximum compression ratio increment was noticed in Calgary corpus at 3.8404% and in English novels at 1.2840%

Link to Full Text

Share

COinS