Natural language insensitive short textual string compression

Cornel Constantinescu; Jennifer Q. Trelewicz; Ronald B. Arps

doi:10.1117/12.507758

28 January 2004 Natural language insensitive short textual string compression

Cornel Constantinescu, Jennifer Q. Trelewicz, Ronald B. Arps

Proceedings Volume 5208, Mathematics of Data/Image Coding, Compression, and Encryption VI, with Applications; (2004) https://doi.org/10.1117/12.507758
Event: Optical Science and Technology, SPIE's 48th Annual Meeting, 2003, San Diego, California, United States

Abstract

There are applications (such as Internet search engines) where short textual strings, for example abstracts or pieces of Web pages, need to be compressed independently of each other. The usual adaptive compression algorithms perform poorly on these short strings due to the lack of necessary data to learn. In this manuscript, we introduce a compression algorithm targeting short text strings; e.g., containing a few hundred symbols. We also target natural language insensitivity, to facilitate its robust compression and fast implementation. The algorithm is based on the following findings. Applying the move-to-front transform (MTFT) after the Burrows-Wheeler transform (BWT) brings the short textual strings to a "normalized form" where the distribution of the resulting "ranks" has a shape similar over the set of natural language strings. This facilitates the use of a static coding method with few variations, which we call shortBWT, where no on-line learning is needed, to encode the ranks. Finally, for short strings, shortBWT runs very fast because the strings fit into the cache of most current computers. The introduction for this paper will review the mathematical bases of BWT and MTF, it will also review our recently published metric for rapidly pre-characterizing the compressibility of such short textual strings when using these transforms.

Citation Download Citation

Cornel Constantinescu, Jennifer Q. Trelewicz, and Ronald B. Arps "Natural language insensitive short textual string compression", Proc. SPIE 5208, Mathematics of Data/Image Coding, Compression, and Encryption VI, with Applications, (28 January 2004); https://doi.org/10.1117/12.507758

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available