A Fast Algorithm for the Largest Area First Parsing of Real Strings

Katanić, Ivan; Ristov, Strahil; Rosenzweig, Martin (2020) A Fast Algorithm for the Largest Area First Parsing of Real Strings. IEEE access, 8 . pp. 141990-142002. ISSN 2169-3536

Preview

PDF - Published Version - article
Available under License Creative Commons Attribution.
Download (6MB) | Preview

Official URL: https://ieeexplore.ieee.org/document/9154361

Abstract

The largest area first parsing of a string often leads to the best results in grammar compression for a variety of input data. However, the fastest existing algorithm has Θ(N2logN) time complexity, which makes it impractical for real-life applications. We present a new largest area first parsing method that has O(N3) complexity in the improbable worst case but works in the quasilinear time for most practical purposes. This result is based on the fact that in the real data, the sum of all depths of an LCP-interval tree, over all of the positions in a suffix array of an input string, is only larger than the size of the input by a small factor α . We present the analysis of the algorithm in terms of α , and the experimental results confirm that our method is practical even for genome sized inputs. We provide the C ++ 11 code for the implementation of our method. Additionally, we show that by a combination of the previous and new algorithms, the worst-case complexity of the largest area first parsing is improved by a factor of N−−√3 .

Item Type:

Article

Uncontrolled Keywords:

greedy grammar compression ; largest area first parsing ; dynamic text indexing ; enhanced suffix array

Subjects:

TECHNICAL SCIENCES > Computing

Divisions:

Division of Electronics

Projects:

Project title	Project leader	Project code	Project type
Napredne metode i tehnologije u znanosti o podatcima i kooperativnim sustavima	UNSPECIFIED	UNSPECIFIED	EK
Napredni deterministički i hibridni algoritmi na nizovima, sljedovima i stablima s primjenama u tehničkim znanostima i znanostima o životu	Ristov, Strahil	IP-2018-01-7317	HRZZ

Depositing User:

Strahil Ristov

Date Deposited:

25 Nov 2021 09:10

URI:

http://fulir.irb.hr/id/eprint/6773

DOI:

10.1109/access.2020.3013676