research-article

Full-text search on multi-byte encoded documents

Authors:

Raymond K. Wong,

Nicole LamAuthors Info & Claims

DocEng '12: Proceedings of the 2012 ACM symposium on Document engineering

Pages 227 - 236

https://doi.org/10.1145/2361354.2361404

Published: 04 September 2012 Publication History

Abstract

The Burrows Wheeler transform (BWT) has become popular in text compression, full-text search, XML representation, and DNA sequence matching. It is very efficient to perform a full-text search on BWT encoded text using backward search. This paper aims to study different approaches for applying BWT on multi-byte encoded (e.g. UTF-16) text documents. While previous work has studied BWT on word-based models, and BWT can be applied directly on multi-byte encodings (by treating the document as single-byte coded), there has been no extensive study on how to utilize BWT on multi-byte encoded documents for efficient full-text search. Therefore, in this paper, we propose several ways to efficiently backward search multi-byte text documents. We demonstrate our findings using Chinese text documents. Our experiment results show that our extensions to the standard BWT method offer faster search performance and use less runtime memory.

References

[1]

A. Andersson, N. Larsson, and K. Swanson. Suffix trees on words. Algorithmica, 23(3):246--260, 1999.

[2]

M. Burrows and D. Wheeler. A block-sorting lossless data compression algorithm. Technical report, Digital Equipment Corporation, Palo Alto, CA, 1994.

[3]

P. Ferragina, F. Luccio, G. Manzini, and S. Muthukrishnan. Compressing and searching XML data via two zips. In WWW 2006, Edinburgh, Scotland, 2006. ACM.

Digital Library

[4]

P. Ferragina and G. Manzini. Opportunistic data structures with applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS '00, pages 390--398, Washington, DC, USA, 2000. IEEE Computer Society.

Digital Library

[5]

P. Ferragina and G. Manzini. Indexing compressed text. J. ACM, 52(4):552--581, July 2005.

Digital Library

[6]

W. B. Frakes and R. A. Baeza-Yates, editors. Information Retrieval: Data Structures & Algorithms. Prentice-Hall, 1992.

Digital Library

[7]

S. Inenaga and M. Takeda. On-line linear-time construction of word suffix trees. In in Proc. 17th Ann. Symp. on Combinatorial Pattern Matching (CPM'06), pages 60--71. Springer-Verlag, 2006.

Digital Library

[8]

R. Y. K. Isal, A. Moffat, and A. C. Ngai. Enhanced word-based block-sorting text compression. In ACSC '02 Proceedings of the twenty-fifth Australasian conference on Computer Science. ACS, 2002.

Digital Library

[9]

J. Karkkainen and E. Ukkonen. Sparse suffix trees. In J.-Y. Cai and C. Wong, editors, Computing and Combinatorics, volume 1090 of Lecture Notes in Computer Science, pages 219--230. Springer Berlin / Heidelberg, 1996.

Digital Library

[10]

H. Li and R. Durbin. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics, 26(5):589--595, 2010.

Digital Library

[11]

V. Makinen and G. Navarro. Succinct suffix arrays based on run-length encoding. Nordic J. of Computing, 12(1):40--66, Mar. 2005.

Digital Library

[12]

U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. SIAM J. Computing, 22(5):935--948, 1993.

Digital Library

[13]

E. McCreight. A space-economical suffix tree construction algorithm. J. ACM, 23(2):262--272, 1976.

Digital Library

[14]

G. H. Ong and S. Y. Huang. A data compression scheme for Chinese text files using Huffman coding and a two-level dictionary. Information Sciences, 84(1-2):85--99, 1995.

Digital Library

[15]

K. Sadakane. A modified Burrows-Wheeler transformation for case-insensitive search with application to suffix array compression. In DCC: Data Compression Conference. IEEE Computer Society, 1999.

Digital Library

[16]

K. Sadakane. Unifying Text Search and Compression: Suffix Sorting, Block Sorting and Suffix Arrays. PhD thesis, The University of Tokyo, 2000.

[17]

I. Witten, A. Moffat, and T. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, San Francisco, CA, 1999.

Digital Library

[18]

S. Yoshida, T. Morihara, H. Yahagi, and N. Satoh. Application of a word-based text compression method to Japanese and Chinese texts. In Data Compression Conference, DCC '99. IEEE, 1999.

Digital Library

Cited By

Zhang BTian JDi SYu XSwany MTao DCappello FGallivan KNikolopoulos DBeivide RGallopoulos E(2023)GPULZ: Optimizing LZSS Lossless Compression for Multi-byte Data on Modern GPUsProceedings of the 37th International Conference on Supercomputing10.1145/3577193.3593706(348-359)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3577193.3593706
Chotnithi PTakasu ASablatnig RHassan T(2016)Frequent Multi-Byte Character Subtring Extraction using a Succinct Data StructureProceedings of the 2016 ACM Symposium on Document Engineering10.1145/2960811.2967161(103-106)Online publication date: 13-Sep-2016
https://dl.acm.org/doi/10.1145/2960811.2967161

Index Terms

Full-text search on multi-byte encoded documents
1. Applied computing
  1. Document management and text processing
2. Information systems
  1. Information retrieval
    1. Information retrieval query processing

Recommendations

Waveform and image compression using the Burrows Wheeler transform and the wavelet transform
ICIP '97: Proceedings of the 1997 International Conference on Image Processing (ICIP '97) 3-Volume Set-Volume 1 - Volume 1

Recently, the Burrows Wheeler transform (BWT) has been proposed for text compression. The BWT based compression algorithm performs close to the best algorithm known today on a set of standard text files, and it has less complexity. In this paper we ...
Double-byte text compression
A Full-Text Search System for Images of Hand-Written Cursive Documents
ICFHR '10: Proceedings of the 2010 12th International Conference on Frontiers in Handwriting Recognition

We propose a full-text search technique for image-scanned documents that does not recognize individual characters. The system is as fast as a full-text search of machine-readable documents. Such a system is important when working with historical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DocEng '12: Proceedings of the 2012 ACM symposium on Document engineering

September 2012

256 pages

ISBN:9781450311168

DOI:10.1145/2361354

General Chair:
Cyril Concolato
Telecom ParisTech, France
,
Program Chair:
Patrick Schmitz
University of California, Berkeley, USA

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

In-Cooperation

SIGDOC: ACM Special Interest Group for Design of Communications

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 September 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DocEng '12

Sponsor:

SIGWEB

DocEng '12: ACM Symposium on Document Engineering

September 4 - 7, 2012

Paris, France

Acceptance Rates

Overall Acceptance Rate 194 of 564 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang BTian JDi SYu XSwany MTao DCappello FGallivan KNikolopoulos DBeivide RGallopoulos E(2023)GPULZ: Optimizing LZSS Lossless Compression for Multi-byte Data on Modern GPUsProceedings of the 37th International Conference on Supercomputing10.1145/3577193.3593706(348-359)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3577193.3593706
Chotnithi PTakasu ASablatnig RHassan T(2016)Frequent Multi-Byte Character Subtring Extraction using a Succinct Data StructureProceedings of the 2016 ACM Symposium on Document Engineering10.1145/2960811.2967161(103-106)Online publication date: 13-Sep-2016
https://dl.acm.org/doi/10.1145/2960811.2967161

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents