### Fast string sorting using order-preserving compressionFast string sorting using order-preserving compression

Access Restriction
Subscribed

 Author Lpez-Ortiz, Alejandro ♦ Mirzazadeh, Mehdi ♦ Safari, Mohammad Ali ♦ Sheikhattar, Hossein Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Order-preserving compression ♦ Sorting ♦ Unit-cost RAM ♦ Word-RAM Abstract We give experimental evidence for the benefits of order-preserving compression in sorting algorithms. While, in general, any algorithm might benefit from compressed data because of reduced paging requirements, we identified two natural candidates that would further benefit from order-preserving compression, namely string-oriented sorting algorithms and word-RAM algorithms for keys of bounded length. The word-RAM model has some of the fastest known sorting algorithms in practice. These algorithms are designed for keys of bounded length, usually 32 or 64 bits, which limits their direct applicability for strings. One possibility is to use an order-preserving compression scheme, so that a bounded-key-length algorithm can be applied. For the case of standard algorithms, we took what is considered to be the among the fastest nonword RAM string sorting algorithms, Fast MKQSort, and measured its performance on compressed data. The Fast MKQSort algorithm of Bentley and Sedgewick is optimized to handle text strings. Our experiments show that order-compression techniques results in savings of approximately 15% over the same algorithm on noncompressed data. For the word-RAM, we modified Andersson's sorting algorithm to handle variable-length keys. The resulting algorithm is faster than the standard Unix sort by a factor of $1.5\textit{X}.$ Last, we used an order-preserving scheme that is within a constant additive term of the optimal Hu--Tucker, but requires linear time rather than $\textit{O}(\textit{m}log$ $\textit{m}),$ where $\textit{m}$ = |Σ| is the size of the alphabet. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 10

#### Open content in new tab

Source: ACM Digital Library