[Octave-bug-tracker] [bug #60409] [octave forge] (communications) huffmandeco throws out of memory or dimension too large for Octave's index type error

[Tasos Papastylianou]

URL:
  <https://savannah.gnu.org/bugs/?60409>

                 Summary: [octave forge] (communications) huffmandeco throws
out of memory or dimension too large for Octave's index type error
                 Project: GNU Octave
            Submitted by: tpapastylianou
            Submitted on: Sat 17 Apr 2021 06:01:15 PM UTC
                Category: Octave Forge Package
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Unexpected Error or Warning
                  Status: None
             Assigned to: None
         Originator Name: Tasos Papastylianou
        Originator Email: 
             Open/Closed: Open
                 Release: 6.2.0
         Discussion Lock: Any
        Operating System: Any

    _______________________________________________________

Details:

Please see https://stackoverflow.com/q/67106887/4183191 for context and
details regarding this bug.

In summary, when this algorithm was last changed in 2011 in the repository
(https://sourceforge.net/p/octave/communications/ci/83aeb09e7255c3953ac11b56299dab426831b419/),
it was changed from a brute-force algorithm to a tree-based one; however,
under certain conditions, this seems to result in really large theoretical
trees, which exceed Octave's indexing capacity, resulting in a 'dimension too
large' error inside huffmandeco.m

Steps to reproduce:

+verbose+
pkg load communications
rand( 'seed', 0 );   Text  = randi( [0,127], 1, 100 );   Fdata = randi(
[0,127], 1, 30  ); 
for i = 0 : 127;   Nlet = length( find( Text == i ) );   p(i + 1) = Nlet /
length( Text );   end

Symb       = 0 : 127;
Dict       = huffmandict( Symb, p );        % Create dictionary
[ ~, Idx ] = ismember( Fdata, Symb );       % Data indices from data
Compdata   = huffmanenco( Idx, Dict );      % Encode data indices
Dsig       = huffmandeco( Compdata, Dict ); % Decode Huffman code
Symb( Dsig )                                % Indices to symbols
-verbose-

Output:

+verbose+
error: out of memory or dimension too large for Octave's index type
error: called from
    huffmandeco>dict2tree at line 95 column 19
    huffmandeco at line 55 column 8
    testo at line 9 column 12
-verbose-

Incidentally, as a minor aside, the huffman functions also seem to have a
slightly different API from their matlab counterparts, which has also caused
problems to users migrating to Octave. See:
https://stackoverflow.com/q/66929744/4183191

Also, the huffman functions seem to be getting quite a few hits on
stackoverflow lately, not sure why. Perhaps some recently launched nanodegree
that uses them is recommending Octave? We saw a huge number of octave
questions in stackoverflow relating to Andrew Ng's course ever since that
course first went online -- if something analogous is now causing people to
interact with the huffman functions, we might reasonably expect that these
functions will start getting a lot of attention soon ...




    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60409>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/