Computing q-gram non-overlapping frequencies on SLP compressed texts

Keisuke Goto; Hideo Bannai; Shunsuke Inenaga; Masayuki Takeda

doi:10.1007/978-3-642-27660-6_25

Computing q-gram non-overlapping frequencies on SLP compressed texts

Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

Length-q substrings, or q-grams, can represent important characteristics of text data, and determining the frequencies of all q-grams contained in the data is an important problem with many applications in the field of data mining and machine learning. In this paper, we consider the problem of calculating the non-overlapping frequencies of all q-grams in a text given in compressed form, namely, as a straight line program (SLP). We show that the problem can be solved in O(q ² n) time and O(qn) space where n is the size of the SLP. This generalizes and greatly improves previous work (Inenaga & Bannai, 2009) which solved the problem only for q = 2 in O(n ⁴logn) time and O(n ³) space.

Original language	English
Title of host publication	SOFSEM 2012
Subtitle of host publication	Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Pages	301-312
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-27660-6_25
Publication status	Published - 2012
Event	38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012 - Spindleruv Mlyn, Czech Republic Duration: Jan 21 2012 → Jan 27 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7147 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012
Country/Territory	Czech Republic
City	Spindleruv Mlyn
Period	1/21/12 → 1/27/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-27660-6_25

Cite this

Goto, K., Bannai, H., Inenaga, S., & Takeda, M. (2012). Computing q-gram non-overlapping frequencies on SLP compressed texts. In SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (pp. 301-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7147 LNCS). https://doi.org/10.1007/978-3-642-27660-6_25

Computing q-gram non-overlapping frequencies on SLP compressed texts. / Goto, Keisuke; Bannai, Hideo; Inenaga, Shunsuke et al.
SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2012. p. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7147 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Goto, K, Bannai, H, Inenaga, S & Takeda, M 2012, Computing q-gram non-overlapping frequencies on SLP compressed texts. in SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7147 LNCS, pp. 301-312, 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012, Spindleruv Mlyn, Czech Republic, 1/21/12. https://doi.org/10.1007/978-3-642-27660-6_25

Goto K, Bannai H, Inenaga S, Takeda M. Computing q-gram non-overlapping frequencies on SLP compressed texts. In SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2012. p. 301-312. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-27660-6_25

Goto, Keisuke ; Bannai, Hideo ; Inenaga, Shunsuke et al. / Computing q-gram non-overlapping frequencies on SLP compressed texts. SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. 2012. pp. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{281d8b863d1240efb86d4be43fea3d41,

title = "Computing q-gram non-overlapping frequencies on SLP compressed texts",

abstract = "Length-q substrings, or q-grams, can represent important characteristics of text data, and determining the frequencies of all q-grams contained in the data is an important problem with many applications in the field of data mining and machine learning. In this paper, we consider the problem of calculating the non-overlapping frequencies of all q-grams in a text given in compressed form, namely, as a straight line program (SLP). We show that the problem can be solved in O(q 2 n) time and O(qn) space where n is the size of the SLP. This generalizes and greatly improves previous work (Inenaga & Bannai, 2009) which solved the problem only for q = 2 in O(n 4logn) time and O(n 3) space.",

author = "Keisuke Goto and Hideo Bannai and Shunsuke Inenaga and Masayuki Takeda",

note = "Copyright: Copyright 2012 Elsevier B.V., All rights reserved.; 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012 ; Conference date: 21-01-2012 Through 27-01-2012",

year = "2012",

doi = "10.1007/978-3-642-27660-6_25",

language = "English",

isbn = "9783642276590",

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

pages = "301--312",

booktitle = "SOFSEM 2012",

}

TY - GEN

T1 - Computing q-gram non-overlapping frequencies on SLP compressed texts

AU - Goto, Keisuke

AU - Bannai, Hideo

AU - Inenaga, Shunsuke

AU - Takeda, Masayuki

PY - 2012

Y1 - 2012

N2 - Length-q substrings, or q-grams, can represent important characteristics of text data, and determining the frequencies of all q-grams contained in the data is an important problem with many applications in the field of data mining and machine learning. In this paper, we consider the problem of calculating the non-overlapping frequencies of all q-grams in a text given in compressed form, namely, as a straight line program (SLP). We show that the problem can be solved in O(q 2 n) time and O(qn) space where n is the size of the SLP. This generalizes and greatly improves previous work (Inenaga & Bannai, 2009) which solved the problem only for q = 2 in O(n 4logn) time and O(n 3) space.

AB - Length-q substrings, or q-grams, can represent important characteristics of text data, and determining the frequencies of all q-grams contained in the data is an important problem with many applications in the field of data mining and machine learning. In this paper, we consider the problem of calculating the non-overlapping frequencies of all q-grams in a text given in compressed form, namely, as a straight line program (SLP). We show that the problem can be solved in O(q 2 n) time and O(qn) space where n is the size of the SLP. This generalizes and greatly improves previous work (Inenaga & Bannai, 2009) which solved the problem only for q = 2 in O(n 4logn) time and O(n 3) space.

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

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

U2 - 10.1007/978-3-642-27660-6_25

DO - 10.1007/978-3-642-27660-6_25

M3 - Conference contribution

AN - SCOPUS:84856047503

SN - 9783642276590

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

SP - 301

EP - 312

BT - SOFSEM 2012

T2 - 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012

Y2 - 21 January 2012 through 27 January 2012

ER -

Computing q-gram non-overlapping frequencies on SLP compressed texts

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this