New Source Coding Methods

[sagetrac-jan-wabbersen]

This ticket enhances the currently implemented Huffman module by generalizing it to a q-nary Huffman and implementing a faster decoding method. In addition, some parts of it were rewritten and moved to new modules, which also form the basis for the newly implemented data compression schemes Shannon, Shannon-Fano and Shannon-Fano-Elias.

The implementation is meant for teaching purposes; all schemes provide a verbose output showing the encoding process in detail.

CC: @sagetrac-dlucas @johanrosenkilde

Component: coding theory

Keywords: huffman, shannon, shannon-fano, shannon, fano-elias, data compression, prefix coding, encoding

Author: Jan Wabbersen

Branch/Commit: public/18315_source_coding @ 1210852

Reviewer: Varenyam bakshi

Issue created by migration from https://trac.sagemath.org/ticket/18315

[sagetrac-jan-wabbersen]

Branch: u/jan.wabbersen/source_coding

[sagetrac-jan-wabbersen]

Commit: b5fb39f

[sagetrac-jan-wabbersen]

New commits:

b5fb39f

Restructured and extended the existing Huffman module. Added initial versions of the additional data compression schemes Shannon, Shannon-Fano, and Shannon-Fano-Elias.

[sagetrac-jan-wabbersen]

Changed keywords from none to huffman, shannon, shannon-fano, shannon, fano-elias, data compression, prefix coding, encoding

[sagetrac-jan-wabbersen]

Author: Jan Wabbersen

[videlec]

comment:3

Hello,

Your branch does not apply anymore. It might be related to the recent changes introduced by David and Johan that are now in copy.

Vincent

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b2108ae

Started making the code also compatible with Python 3.

[sagetrac-git]

Changed commit from b5fb39f to b2108ae

[sagetrac-jan-wabbersen]

comment:5

Hi Vincent,

someone started to make the current huffman also compatible with Python 3. I did now at least the same changes, but it is also not completely compatible by now.

Quick question: Is it necessary to merge the branch with the current version of Sage (for the automerging to succeed)?

Jan

[videlec]

comment:6

Quick answer: yes.

If you modify a file that is also modified by some commits in the current beta then there are some merge conflict.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a89b99e

Merged with current Sage version.

[sagetrac-git]

Changed commit from b2108ae to a89b99e

[sagetrac-jan-wabbersen]

comment:8

Ok, thanks!

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0531147

Merge remote-tracking branch 'origin/master' into t/18315/source_coding

[sagetrac-git]

Changed commit from a89b99e to 0531147

[sagetrac-git]

Changed commit from 0531147 to dc2f31a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

dc2f31a

Merged with current Sage version.

[koffie]

comment:12

Merge conflict with sage 8.1.beta3 needs to be resolved.

[embray]

comment:15

I might go ahead and clean this up a bit more, and incorporate #26026 into it.

[varenyamBakshi]

Reviewer: gh-varenyamBakshi

[varenyamBakshi]

Changed reviewer from gh-varenyamBakshi to Varenyam bakshi

[fchapoton]

comment:18

the branch is red, this does not make sense to switch to positive review

[mkoeppe]

comment:19

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:21

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:22

Setting a new milestone for this ticket based on a cursory review.