Opened 6 years ago
Last modified 13 days ago
#18315 needs_work enhancement
New Source Coding Methods
Reported by:  jan.wabbersen  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  coding theory  Keywords:  huffman, shannon, shannonfano, shannon, fanoelias, data compression, prefix coding, encoding 
Cc:  dlucas, jsrn  Merged in:  
Authors:  Jan Wabbersen  Reviewers:  Varenyam bakshi 
Report Upstream:  N/A  Work issues:  
Branch:  public/18315_source_coding (Commits, GitHub, GitLab)  Commit:  1210852874ceda80c99def98aa65c5ebf73614ab 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket enhances the currently implemented Huffman module by generalizing it to a qnary 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, ShannonFano and ShannonFanoElias.
The implementation is meant for teaching purposes; all schemes provide a verbose output showing the encoding process in detail.
Change History (21)
comment:1 Changed 6 years ago by
 Branch set to u/jan.wabbersen/source_coding
comment:2 Changed 6 years ago by
 Commit set to b5fb39ff8ee521e96e064b9f75fa760d65bcb412
 Component changed from PLEASE CHANGE to coding theory
 Description modified (diff)
 Keywords huffman shannon shannonfano shannon fanoelias data compression prefix coding encoding added
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to enhancement
comment:3 Changed 6 years ago by
 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 5 years ago by
 Commit changed from b5fb39ff8ee521e96e064b9f75fa760d65bcb412 to b2108ae2848d22b6af8848c538bfc723f319eeb6
Branch pushed to git repo; I updated commit sha1. New commits:
b2108ae  Started making the code also compatible with Python 3.

comment:5 Changed 5 years ago by
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
comment:6 Changed 5 years ago by
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 5 years ago by
 Commit changed from b2108ae2848d22b6af8848c538bfc723f319eeb6 to a89b99e696f9f82d2157ffa9b1b085a7fdfbcdab
Branch pushed to git repo; I updated commit sha1. New commits:
a89b99e  Merged with current Sage version.

comment:8 Changed 5 years ago by
Ok, thanks!
comment:9 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 5 years ago by
 Commit changed from a89b99e696f9f82d2157ffa9b1b085a7fdfbcdab to 05311475512dd894a41ebdf5961a442f63152b27
Branch pushed to git repo; I updated commit sha1. New commits:
0531147  Merge remotetracking branch 'origin/master' into t/18315/source_coding

comment:11 Changed 5 years ago by
 Commit changed from 05311475512dd894a41ebdf5961a442f63152b27 to dc2f31ac575d66e74002032600bc05344e1240f8
Branch pushed to git repo; I updated commit sha1. New commits:
dc2f31a  Merged with current Sage version.

comment:12 Changed 3 years ago by
Merge conflict with sage 8.1.beta3 needs to be resolved.
comment:13 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:14 Changed 3 years ago by
 Branch changed from u/jan.wabbersen/source_coding to public/18315_source_coding
 Commit changed from dc2f31ac575d66e74002032600bc05344e1240f8 to 1210852874ceda80c99def98aa65c5ebf73614ab
 Milestone changed from sage6.7 to sage8.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:
b5fb39f  Restructured and extended the existing Huffman module. Added initial versions of the additional data compression schemes Shannon, ShannonFano, and ShannonFanoElias.

b2108ae  Started making the code also compatible with Python 3.

a89b99e  Merged with current Sage version.

0531147  Merge remotetracking branch 'origin/master' into t/18315/source_coding

dc2f31a  Merged with current Sage version.

f172cba  Merge branch 'u/jan.wabbersen/source_coding' of git://trac.sagemath.org/sage into 18315_source_coding

6e070ba  Python 3 print function fixes

1210852  Remove implicit relative imports

comment:15 Changed 3 years ago by
I might go ahead and clean this up a bit more, and incorporate #26026 into it.
comment:16 Changed 12 months ago by
 Reviewers set to ghvarenyamBakshi
 Status changed from needs_review to positive_review
comment:17 Changed 12 months ago by
 Reviewers changed from ghvarenyamBakshi to Varenyam bakshi
comment:18 Changed 12 months ago by
 Milestone changed from sage8.4 to sage9.1
 Status changed from positive_review to needs_work
the branch is red, this does not make sense to switch to positive review
comment:19 Changed 11 months ago by
 Milestone changed from sage9.1 to sage9.2
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.
comment:20 Changed 6 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:21 Changed 13 days ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
New commits:
Restructured and extended the existing Huffman module. Added initial versions of the additional data compression schemes Shannon, ShannonFano, and ShannonFanoElias.