FLOTT—A Fast, Low Memory T-TransformAlgorithm for Measuring String Complexity

Author

Rebenich, N. ; Speidel, Ulrich ; Neville, Stephen ; Gulliver, T.A.

Author_Institution

Dept. of Electr. & Comput. Eng., Univ. of Victoria, Victoria, BC, Canada

Volume

63

Issue

4

fYear

2014

fDate

Apr-14

Firstpage

917

Lastpage

926

Abstract

This paper presents flott, a fast, low memory T-transform algorithm which can be used to compute the string complexity measure T-complexity. The algorithm uses approximately one third of the memory of its predecessor while reducing the running time by about 20 percent. The flott implementation has the same worst-case memory requirements as state of the art suffix tree construction algorithms. A suffix tree can be used to efficiently compute the Lempel-Ziv production complexity, which is another measure of string complexity. The C-implementation of flott is available as Open Source software.

Keywords

computational complexity; data compression; public domain software; text analysis; tree data structures; trees (mathematics); FLOTT implementation; Lempel-Ziv production complexity; T-complexity; fast low memory T-transform algorithm; open source software; string complexity measurement; suffix tree construction algorithms; worst-case memory requirements; Aggregates; Algorithm design and analysis; Arrays; Complexity theory; Memory management; Time measurement; Coding theory; algorithms for data and knowledge management; computation of transforms; information filtering; information theory; text analysis;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.2013.29

Filename

6463379