2

Given the type of bitstrings in Haskell:

data Bits = O Bits | I Bits | Nil

Are there compression algorithms that have satisfactory results (specially when it comes to repeated substrings), that are very small and simple to implement as idiomatic recursive Haskell functions? Ideally, the algorithm would operate on bitstrings, not lists of characters; thus, it should identify repeated substrings of arbitrary lengths and positions. I'm asking for references (i.e., names/citations); no need to post the complete code.

Improve this question
5
  • 1
    To whoever voted to close: note that I'm not asking for software or library recommendations, I'm asking to name algorithms. Is that against the guidelines? Commented Oct 7, 2021 at 20:06
  • I think the question is a bit opinion-based: what does it mean for an algorithm to be "simple" and "idiomatic", and what are "satisfactory results"? Commented Oct 7, 2021 at 21:04
  • Also, do you mean consecutive repetitions or duplicated substrings in general? Commented Oct 7, 2021 at 21:26
  • @Noughtmare I mean an algorithm that can perhaps be implemented in a few recursive functions without many dependencies using mostly pattern-matching. But how else can I define that? If I just ask for a compression algorithm in general, there are many that I can easily find on Google, so this question wouldn't be needed. But I really need one that can be implemented in a few lines of normal Haskell. And I mean duplicated substrings in general, basically I want it to be able to detect repeated words and compress them. Commented Oct 8, 2021 at 1:04
  • Run-length encoding is very easy to define, and works well if you have long repeating strings. (en.wikipedia.org/wiki/Run-length_encoding) Commented Oct 8, 2021 at 2:02
Related questions
3
Compression - Bit
7
Compression algorithm for a bit stream
1
Compressing/hashing a bit vector of any length to a defined length
Load 7 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.