Hackage :: [Package]

sequitur: Grammar-based compression algorithms SEQUITUR

[ bsd3, compression, formal-languages, language, library, natural-language-processing, nlp, text ] [ Propose Tags ] [ Report a vulnerability ]

Modules

[Index] [Quick Jump]

Flags

Manual Flags

NameDescriptionDefault
build-example-programs

Build example programs

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0, 0.2.0.0
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5), clock (>=0.8.3 && <0.9), containers (>=0.6.4.1 && <0.8), hashable (>=1.3.0.0 && <1.5), hashtables (>=1.2.4.2 && <1.4), optparse-applicative (>=0.16.1.0 && <0.19), primitive (>=0.7.3.0 && <0.10), sequitur, text (>=1.2.4.1 && <2.2) [details]
License BSD-3-Clause
Copyright Copyright (c) 2024 Masahiro Sakai
Author Masahiro Sakai
Maintainer masahiro.sakai@gmail.com
Revised Revision 1 made by MasahiroSakai at 2024-10-24T23:35:10Z
Category Formal Languages, Language, Natural Language Processing, NLP, Text, Compression
Home page https://github.com/msakai/haskell-sequitur#readme
Bug tracker https://github.com/msakai/haskell-sequitur/issues
Source repo head: git clone https://github.com/msakai/haskell-sequitur
Uploaded by MasahiroSakai at 2024-07-28T14:57:34Z
Distributions NixOS:0.2.0.0
Executables sequitur-demo
Downloads 59 total (0 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-07-28 [all 1 reports]

Readme for sequitur-0.2.0.0

[back to package description]

Haskell implementation of SEQUITUR algorithm

Hackage: Hackage

Dev: build Coverage Status

About SEQUITUR

SEQUITUR is a linear-time, online algorithm for producing a context-free grammar from an input sequence. The resulting grammar is a compact representation of the original sequence and can be used for data compression.

Example:

  • Input string: abcabcabcabcabc

  • Resulting grammar

    • S → AAB
    • A → BB
    • B → abc

SEQUITUR consumes input symbols one-by-one and appends each symbol at the end of the grammar's start production (S in the above example), then substitutes repeating patterns in the given sequence with new rules. SEQUITUR maintains two invariants:

  • Digram Uniqueness: SEQUITUR ensures that no digram (a.k.a. bigram) occurs more than once in the grammar. If a digram (e.g. ab) occurs twice, SEQUITUR introduces a fresh non-terminal symbol (e.g. M) and a rule (e.g. M → ab) and replaces original occurrences with the newly introduced non-terminals. One exception is the cases where two occurrences overlap.

  • Rule Utility: If a non-terminal symbol occurs only once, SEQUITUR removes the associated rule and substitutes the occurrence with the right-hand side of the rule.

Usage

ghci> import Language.Grammar.Sequitur
ghci> encode "baaabacaa"
Grammar {unGrammar = fromList [(0,[NonTerminal 1,NonTerminal 2,NonTerminal 1,Terminal 'c',NonTerminal 2]),(1,[Terminal 'b',Terminal 'a']),(2,[Terminal 'a',Terminal 'a'])]}

The output represents the following grammar:

0 → 1 2 1 c 2
1 → b a
2 → a a

References