Opened 5 years ago

Last modified 16 months ago

#18315 needs_review enhancement

New Source Coding Methods

Reported by: jan.wabbersen Owned by:
Priority: major Milestone: sage-8.4
Component: coding theory Keywords: huffman, shannon, shannon-fano, shannon, fano-elias, data compression, prefix coding, encoding
Cc: dlucas, jsrn Merged in:
Authors: Jan Wabbersen Reviewers:
Report Upstream: N/A Work issues:
Branch: public/18315_source_coding (Commits) Commit: 1210852874ceda80c99def98aa65c5ebf73614ab
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (15)

comment:1 Changed 5 years ago by jan.wabbersen

  • Branch set to u/jan.wabbersen/source_coding

comment:2 Changed 5 years ago by jan.wabbersen

  • Authors set to Jan Wabbersen
  • Commit set to b5fb39ff8ee521e96e064b9f75fa760d65bcb412
  • Component changed from PLEASE CHANGE to coding theory
  • Description modified (diff)
  • Keywords huffman shannon shannon-fano shannon fano-elias data compression prefix coding encoding added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

New commits:

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

comment:3 Changed 4 years ago by vdelecroix

  • Cc dlucas jsrn added
  • Status changed from needs_review to needs_work

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

comment:4 Changed 4 years ago by git

  • Commit changed from b5fb39ff8ee521e96e064b9f75fa760d65bcb412 to b2108ae2848d22b6af8848c538bfc723f319eeb6

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

​b2108aeStarted making the code also compatible with Python 3.

comment:5 Changed 4 years ago by jan.wabbersen

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

Last edited 4 years ago by jan.wabbersen (previous) (diff)

comment:6 Changed 4 years ago by vdelecroix

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.

comment:7 Changed 4 years ago by git

  • Commit changed from b2108ae2848d22b6af8848c538bfc723f319eeb6 to a89b99e696f9f82d2157ffa9b1b085a7fdfbcdab

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

​a89b99eMerged with current Sage version.

comment:8 Changed 4 years ago by jan.wabbersen

Ok, thanks!

comment:9 Changed 4 years ago by jan.wabbersen

  • Status changed from needs_work to needs_review

comment:10 Changed 4 years ago by git

  • Commit changed from a89b99e696f9f82d2157ffa9b1b085a7fdfbcdab to 05311475512dd894a41ebdf5961a442f63152b27

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

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

comment:11 Changed 4 years ago by git

  • Commit changed from 05311475512dd894a41ebdf5961a442f63152b27 to dc2f31ac575d66e74002032600bc05344e1240f8

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

​dc2f31aMerged with current Sage version.

comment:12 Changed 2 years ago by mderickx

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

comment:13 Changed 17 months ago by gh-bryangingechen

  • Status changed from needs_review to needs_work

comment:14 Changed 17 months ago by gh-bryangingechen

  • Branch changed from u/jan.wabbersen/source_coding to public/18315_source_coding
  • Commit changed from dc2f31ac575d66e74002032600bc05344e1240f8 to 1210852874ceda80c99def98aa65c5ebf73614ab
  • Milestone changed from sage-6.7 to sage-8.4
  • Status changed from needs_work to needs_review

I think I've fixed the merge conflicts. I also performed some python 3 fixes for print and relative imports. This should now hopefully be as ready for review as the previous commit was.

New commits:

​b5fb39fRestructured and extended the existing Huffman module. Added initial versions of the additional data compression schemes Shannon, Shannon-Fano, and Shannon-Fano-Elias.
​b2108aeStarted making the code also compatible with Python 3.
​a89b99eMerged with current Sage version.
​0531147Merge remote-tracking branch 'origin/master' into t/18315/source_coding
​dc2f31aMerged with current Sage version.
​f172cbaMerge branch 'u/jan.wabbersen/source_coding' of git://trac.sagemath.org/sage into 18315_source_coding
​6e070baPython 3 print function fixes
​1210852Remove implicit relative imports

comment:15 Changed 16 months ago by embray

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

Note: See TracTickets for help on using tickets.