Xpack : a grammar-based XML document compression

Abstract

Most data that are stored and interchanged on the Web are represented as XML documents. Normally, the size of the XML documents is large with respect to the size of the required information contained in them due to the replication of tags. In XML documents, the same tag is used to describe different data items of the same type. To reduce the effect of the replication, methods for the compression of the XML documents have been developed. In this thesis, we introduce a grammar-based compression technique for semantically lossless compression of XML documents. This technique is developed in the context of the XPACK system, which supports both compression and decompression of XML documents. The XPACK system consists of three main steps: 1) the derivation of grammar rules from the analysis of document structures, 2) the document compression using the grammar rules, and 3) the document decompression. In experimental testing, our compression technique was found to compress an XML document to a size 74% to 96% smaller than its original size. This technique provides a better compression performance than GZIP or XMILL.

ข้อมูลที่ถูกจัดเก็บและถูกใช้ในการแลกเปลี่ยนกันบนเว็บส่วนใหญ่นิยมแสดงในรูปแบบของเอกสาร XML แต่ปัญหาของการใช้งานเอกสาร XML คือเอกสาร XML โดยทั่วไปมีขนาดใหญ่เมื่อเทียบกับขนาดของข้อมูลจริงในเอกสารเนื่องจากมีการใช้แท็กที่ซ้ำกันในการอธิบายข้อมูลประเภทเดียวกันที่มีรายละเอียดต่างกัน เพื่อที่จะลดผลกระทบของการใช้แท็กที่ซ้ำกัน การบีบอัดเอกสาร XML จึงได้ถูกพัฒนาขึ้น วิทยานิพนธ์นี้ ได้นำเสนอวิธีการเชิงไวยากรณ์ในการบีบอัดเอกสาร XML ผ่านรูปแบบของระบบ XPACK ซึ่งรองรับการบีบอัดและการขยายเอกสาร XML ระบบ XPACK ประกอบด้วย 3 ส่วนหลัก คือ 1) การกำหนดกฎไวยากรณ์จากการวิเคราะห์โครงสร้างของเอกสาร XML 2) ขั้นตอนการบีบอัด เอกสารโดยใช้กฎไวยากรณ์ และ 3) การขยายข้อมูลเอกสาร จากผลการทดลองการบีบอัดเอกสาร XML พบว่าวิธีการเชิงไวยากรณ์สามารถทำการบีบอัดเอกสาร XML ให้มีขนาดเล็กลงถึง 74%-96% เมื่อเทียบกับขนาดเอกสารก่อนการบีบอัด นอกจากนั้น ยังสามารถบีบอัดเอกสารได้มีประสิทธิภาพดีกว่าเมื่อเทียบกับ GZIP และ XMILL