NDLI: An Efficient Algorithm For The Inverse ST Problem

Content Provider	IEEE Xplore Digital Library
Author	Ge Nong Sen Zhang
Copyright Year	2007
Description	Author affiliation: Comput. Sci. Dept., Sun Yat-Sen Univ., Guangzhou (Ge Nong)
Abstract	Summary form given only. The Schindler transform (ST) can speed up the block sorting phase of the Burrows-Wheeler transform (BWT) by limiting the context sorting to the first k (k E [0, N], where N is the length of the text) positions only. Under the ST's partial sorting scheme, if two rows share the exactly same k-order context, they may not be ordered alphabetically; instead, the relative order between them in the original matrix is preserved in the transformed matrix. A major tradeoff for the ST to achieve the speedup gain over the BWT is that the inverse ST appears to be more complicated than the inverse BWT. To deal with the existence of identical k-order contexts, Schindler suggested a hash based approach in which the text retrieval has to rely on the hash table based context lookup, which in turn has to rely on the complete retrieval of all the k-order contexts. An improved solution proposed by Yokoo uses no hash table; however, it still needs to restore all the k-order contexts, which clearly requires O(kN) for both the time and the space complexities. Recently, Nong and Zhang had proposed an auxiliary vector based framework, which is different from any possible k-order context retrieval based approaches formerly suggested by others, but similar to that used for the inverse BWT. This framework relies on two size-N vectors $T_{k}$ and $C_{k}$ (details are omitted due to space limit) to correctly retrieve the true immediate preceding character for a given character, which allows the original text to be recovered directly from the transformed text without statically restoring the complete fc-order contexts. As a consequence, this framework requires only O(N) space. However, its running time remains to be O(kN), for it has to visit each column of the fc-order context matrix to obtain $T_{k}$ and $C_{k.}$ Since $T_{k}$ and $C_{k}$ can be deduced from the context switch vector D (the data structure indicating whether each pair of two neighbor rows in the context matrix are the same or not) in linear time, the more efficient the D can be calculated, the faster the ST can be inverted. If two k-order contexts are different, either their first halves are different already, or their second halves are different; furthermore, the second half of the k-order context matrix can be deduced from its first half due to the rotating scheme in ST. Based on this observation, we proposed a dynamic programming approach to quickly calculate D by doubling the steps to reach the fcth column in comparing the fc-order contexts. This "doubling technique" based algorithm requires only O(Nlogk) time to calculate D, thus resulting in an O(N log k) time complexity algorithm to invert ST. The space complexity of the algorithm remains to be O(N). This new algorithm can be used to build efficient compression solutions based on the ST.
Starting Page	397
Ending Page	397
File Size	69065
Page Count	1
File Format	PDF
ISBN	0769527914
ISSN	10680314
DOI	10.1109/DCC.2007.11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-03-27
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Data compression Sorting Switches Sun Partial response channels Educational institutions Vectors Data structures Dynamic programming
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