Skip to main content

2013 | OriginalPaper | Buchkapitel

Fully-Online Grammar Compression

verfasst von : Shirou Maruyama, Yasuo Tabei, Hiroshi Sakamoto, Kunihiko Sadakane

Erschienen in: String Processing and Information Retrieval

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

We present a fully-online algorithm for constructing straight-line programs (SLPs). A naive array representation of an SLP with

n

variables on an alphabet of size

σ

requires

$2n\lg(n+\sigma)$

bits. As already shown in [Tabei et al., CPM’13], in offline setting, this size can be reduced to

$ n\lg(n+\sigma) + 2n + o(n)$

, which is asymptotically equal to the information-theoretic lower bound. Our algorithm achieves the same size in online setting, i.e., characters of an input string are given one by one to update the current SLP. With an auxiliary position array of size

$n\lg(N/n) + 3n + o(n)$

bits, our representation supports substring extractions in

O

((

m

 + 

h

)

t

) time where

N

is the length of the input string,

m

is the length of a substring extracted,

$h = O(\lg N)$

is the height of the SLP,

t

 = 

O

(1) in offline case, and

$t=O(\lg n/\lg\lg n)$

in online case. The working space is bounded by

$(1+\alpha)n\lg(n+\sigma)+n(3+\lg(\alpha n))$

bits depending on a constant

α

 ∈ (0,1], which is a load factor of hash tables. We compared our algorithm to LZend in experiments using real world repetitive texts.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Fully-Online Grammar Compression
verfasst von
Shirou Maruyama
Yasuo Tabei
Hiroshi Sakamoto
Kunihiko Sadakane
Copyright-Jahr
2013
Verlag
Springer International Publishing
DOI
https://doi.org/10.1007/978-3-319-02432-5_25

Neuer Inhalt