Context-sensitive grammar transform: Compression and pattern matching

Shirou Maruyama; Yohei Tanaka; Hiroshi Sakamoto; Masayuki Takeda

doi:10.1007/978-3-540-89097-3_5

Context-sensitive grammar transform: Compression and pattern matching

Shirou Maruyama, Yohei Tanaka, Hiroshi Sakamoto, Masayuki Takeda

Mathematical Informatics

Research output: Contribution to journal › Conference article › peer-review

10 Citations (Scopus)

Abstract

A framework of context-sensitive grammar transform is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching (CPM) algorithm. The compression performance is a match for gzip and Re-Pair. The search speed of our CPM algorithm is almost twice faster than the KMP type CPM algorithm on Byte-Pair-Encoding by Shibata et al. (2000), and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al. (2002), which is regarded as one of the best combinations that allows a practically fast search.

Original language	English
Pages (from-to)	27-38
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5280 LNCS
DOIs	https://doi.org/10.1007/978-3-540-89097-3_5
Publication status	Published - 2008
Event	15th International Symposium on String Processing and Information Retrieval, SPIRE 2008 - Melbourne. VIC, Australia Duration: Nov 10 2008 → Nov 12 2008

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-89097-3_5

Cite this

Context-sensitive grammar transform: Compression and pattern matching. / Maruyama, Shirou; Tanaka, Yohei; Sakamoto, Hiroshi et al.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 5280 LNCS, 2008, p. 27-38.

Research output: Contribution to journal › Conference article › peer-review

@article{8c635563849e4ce9aae66dbf0fc4fcf0,

title = "Context-sensitive grammar transform: Compression and pattern matching",

abstract = "A framework of context-sensitive grammar transform is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching (CPM) algorithm. The compression performance is a match for gzip and Re-Pair. The search speed of our CPM algorithm is almost twice faster than the KMP type CPM algorithm on Byte-Pair-Encoding by Shibata et al. (2000), and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al. (2002), which is regarded as one of the best combinations that allows a practically fast search.",

author = "Shirou Maruyama and Yohei Tanaka and Hiroshi Sakamoto and Masayuki Takeda",

year = "2008",

doi = "10.1007/978-3-540-89097-3_5",

language = "English",

volume = "5280 LNCS",

pages = "27--38",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "15th International Symposium on String Processing and Information Retrieval, SPIRE 2008 ; Conference date: 10-11-2008 Through 12-11-2008",

}

TY - JOUR

T1 - Context-sensitive grammar transform

T2 - 15th International Symposium on String Processing and Information Retrieval, SPIRE 2008

AU - Maruyama, Shirou

AU - Tanaka, Yohei

AU - Sakamoto, Hiroshi

AU - Takeda, Masayuki

PY - 2008

Y1 - 2008

N2 - A framework of context-sensitive grammar transform is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching (CPM) algorithm. The compression performance is a match for gzip and Re-Pair. The search speed of our CPM algorithm is almost twice faster than the KMP type CPM algorithm on Byte-Pair-Encoding by Shibata et al. (2000), and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al. (2002), which is regarded as one of the best combinations that allows a practically fast search.

AB - A framework of context-sensitive grammar transform is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching (CPM) algorithm. The compression performance is a match for gzip and Re-Pair. The search speed of our CPM algorithm is almost twice faster than the KMP type CPM algorithm on Byte-Pair-Encoding by Shibata et al. (2000), and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al. (2002), which is regarded as one of the best combinations that allows a practically fast search.

UR - http://www.scopus.com/inward/record.url?scp=85041120542&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041120542&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89097-3_5

DO - 10.1007/978-3-540-89097-3_5

M3 - Conference article

AN - SCOPUS:85041120542

SN - 0302-9743

VL - 5280 LNCS

SP - 27

EP - 38

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Y2 - 10 November 2008 through 12 November 2008

ER -

Context-sensitive grammar transform: Compression and pattern matching

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this