NDLI: Efficient lossless compression of trees and graphs

Content Provider	IEEE Xplore Digital Library
Author	Shenfeng Chen Reif, J.H.
Copyright Year	1996
Description	Author affiliation: Dept. of Comput. Sci., Duke Univ., Durham, NC, USA (Shenfeng Chen; Reif, J.H.)
Abstract	Summary form only given, as follows. Data compression algorithms have been widely used in many areas to meet the demand of storage and transfer of large size data. Most of the data compression algorithms regard the input as a sequence of binary numbers and represent the compressed data also as a binary sequence. However, in many areas such as programming languages (e.g. LISP and C) and compiler design, it is more desirable to have a compression algorithm which compresses a data structure while keeping a similar structure of the original data in the compressed form. In addition to reducing storage space, such compression also has the benefit of efficiently executing various operations (e.g. searching) in the compressed form. We study the problem of compressing a non-binary data structure (e.g. tree, undirected and directed graphs) in an efficient way while keeping a similar structure in the compressed form. To date, there has been no proven optimal algorithm for this problem. We use the idea of building LZW tree in LZW compression to compress a binary tree generated by a stationary ergodic source. The tree is parsed into subtrees using breadth first search and an optimal dictionary is constructed with each index pointing to a distinct subtree. We replace the parsed subtrees by dictionary indices to formed the compressed tree. We also extend our tree compression algorithm to compress undirected and directed acyclic graphs.
File Size	52192
File Format	PDF
ISBN	0818673583
ISSN	10680314
DOI	10.1109/DCC.1996.488356
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-03-31
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Tree graphs Data compression Compression algorithms Dictionaries Binary sequences Computer languages Algorithm design and analysis Data structures Tree data structures Buildings
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Compressed by the suffix tree

Grouping algorithm for lossless data compression

An algorithm for tree structure compression

Efficient Lossless Compression of Trees and Graphs (1996)

Binary search tree visualization algorithm

Faster uniquely represented dictionaries

On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression

Sparsification-a technique for speeding up dynamic graph algorithms

Efficient parallel algorithms for tree-related problems using the parentheses matching strategy

Efficient lossless compression of trees and graphs

Similar Documents

Compressed by the suffix tree

Grouping algorithm for lossless data compression

An algorithm for tree structure compression

Efficient Lossless Compression of Trees and Graphs (1996)

Binary search tree visualization algorithm

Faster uniquely represented dictionaries

On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression

Sparsification-a technique for speeding up dynamic graph algorithms

Efficient parallel algorithms for tree-related problems using the parentheses matching strategy

Efficient lossless compression of trees and graphs