Please please help me with a C++ problem!

This is a discussion on Please please help me with a C++ problem! within the C++ Programming forums, part of the General Programming Boards category; Hi there I have a problem with my code and am in a big rush to finish it and will ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    2

    Please please help me with a C++ problem!

    Hi there

    I have a problem with my code and am in a big rush to finish it and will be most grateful if someone could point me in the right direction.

    The problem is suppose you want to compress an array of integers so that it uses less space which I'm showing in the code sample below.

    I have several issues here. First, I don't know if I'm going in the right direction by converting int to char or short that use less space and result in the data being compressed. If I'm wrong here how else can I acheive compression? If I'm right, how can I store the resulting char and/or short and/or integer values togther in memory to use them later?

    Second, How can I use bitwise operations instead of converting small int values to char/short to achieve compression?

    I would really really appreciate if someone could show me some sample code instead of pointing me to numerous pages of algorithms on the web, as I'm very much short in time. I'll be most grateful.

    Many thanks

    The code:

    Code:
    void CompressData()
    {
            int iIndex = 0;
            int iTempValue = 0;
            int iDeltaValue = 0;
            int iOriginalValue = 0;
            char charValue = 0;
            short shortValue = 0;
            const iBufferSize = 10;
     
            int dataBuffer[iBufferSize] = {67082, 67033, 67019, 67149, 67044, 67012, 66984, 66866, 66693, 65223};
     
            // Encode the data using delta encoding
            for (iIndex = 0; iIndex < iBufferSize; iIndex++)
            {
                    iOriginalValue = dataBuffer[iIndex];
                                    
                    iDeltaValue = pDataBuffer[iIndex] - iTempValue;
     
                    dataBuffer[iIndex] = iDeltaValue ;
     
                    iTempValue = iOriginalValue;
     
                    if (IsOneByteValue(iDeltaValue))
                    {
                            charValue = (char) iDeltaValue;
                    }
                    else if (IsTwoByteValue(iDeltaValue))
                    {
                            shortValue = (short) iDeltaValue;
                    }
     
                    // WHAT TO DO HERE? HOW CAN I SAVE ALL OF THE RESULTING CHAR OR SHORT OR INTEGER IN MEMORY SO THAT I CAN USE THEM LATER TO DECOMPRESS?
            }
     
    }
     
    bool IsOneByteValue(int iValue)
    {
            if (iValue < 0)
            {
                    if (iValue >= -128)
                            return true;
            }
            else
            {
                    if (iValue <= 127)
                            return true;
            }
            
            return false;
    }
     
     
    bool IsTwoByteValue(int iValue)
    {
            if (iValue < 0)
            {
                    if (iValue >= -32768)
                            return true;
            }
            else
            {
                    if (iValue <= 65535)
                            return true;
            }
            
            return false;
    }

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Another idea: you could use "run-length encoding". Wikipedia will be able to tell you about it. That's no good unless you array has runs of elements which are the same value, though.

    The way you have it set up, you'd probably have to create some sort of data structure, with a few bits to indicate whether the next field was an absolute value, or a char offset from the previous value, or a short offset. To be honest, it's a *lot* more trouble than it's worth. You're using, what, 10*4 = 40 bytes of memory? Who cares?

    If you have a lot of data that needs to be compressed, I'd use an external compression program for that (or you can make your own Huffman encoding or something, but be warned, it's far from easy). If you have a lot of data that won't all fit into memory, store most of it on disk and only load some of it at a time into memory. But compression schemes such as what you're trying to create probably won't be very useful . . . .

    By the way, this
    Code:
    bool IsOneByteValue(int iValue)
    {
            if (iValue < 0)
            {
                    if (iValue >= -128)
                            return true;
            }
            else
            {
                    if (iValue <= 127)
                            return true;
            }
            
            return false;
    }
    can be written much more concisely as
    Code:
    bool IsOneByteValue(int iValue)
    {
            if (iValue >= -128 && iValue <= 127)
                   return true;
            return false;
    }
    or even
    Code:
    bool IsOneByteValue(int iValue)
    {
            return (iValue >= -128 && iValue <= 127);
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Aug 2009
    Posts
    2
    Quote Originally Posted by dwks View Post
    Another idea: you could use "run-length encoding". Wikipedia will be able to tell you about it. That's no good unless you array has runs of elements which are the same value, though.

    The way you have it set up, you'd probably have to create some sort of data structure, with a few bits to indicate whether the next field was an absolute value, or a char offset from the previous value, or a short offset. To be honest, it's a *lot* more trouble than it's worth. You're using, what, 10*4 = 40 bytes of memory? Who cares?

    If you have a lot of data that needs to be compressed, I'd use an external compression program for that (or you can make your own Huffman encoding or something, but be warned, it's far from easy). If you have a lot of data that won't all fit into memory, store most of it on disk and only load some of it at a time into memory. But compression schemes such as what you're trying to create probably won't be very useful . . . .

    By the way, this
    Code:
    bool IsOneByteValue(int iValue)
    {
            if (iValue < 0)
            {
                    if (iValue >= -128)
                            return true;
            }
            else
            {
                    if (iValue <= 127)
                            return true;
            }
            
            return false;
    }
    can be written much more concisely as
    Code:
    bool IsOneByteValue(int iValue)
    {
            if (iValue >= -128 && iValue <= 127)
                   return true;
            return false;
    }
    or even
    Code:
    bool IsOneByteValue(int iValue)
    {
            return (iValue >= -128 && iValue <= 127);
    }
    Thanks for the comment. I probably did not explain enough. I do need to implement the delta encoding algorithm and no other ones as this is a test for me and a proof of concept. Also amount of original data is not important and one can assume a small amount of data, say, an array of type integet with 30 values in it.

    The change you made in the code works ok as long as the byte value is a signed value between -128 and 127. But it won't work if the byte value is unsinged which could be between 0 and 255.

  4. #4
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    I do need to implement the delta encoding algorithm
    That sounds like an interesting problem. So, your compressed array would start with the first value, and then only deltas to the subsequent values. From looking at your code, I assume that you intend to have a variable number of bytes for each delta so that a small delta is stored in 1 byte, and a larger one stored in 2 or three bytes. Is that correct?

    If so, you'd need some indication about how many bytes the next delta consumes, so you'd need to come up with an encoding scheme and make an assumption about the largest delta possible. Say the largest delta was between -16384 and 16383. You could fit that into fifteen bits or 2 bytes with 1 bit left over for encoding the length of the delta.

    As you read the most significant byte of the delta you'd check the most significant bit. If it is a 0, the delta fits in the single byte. If it is a 1, the delta takes up 2 bytes.

    In this way, a 1 byte delta really has only 7 usable bits, and a 2 byte delta has 15. A function like IsOneByteValue would return true if the argument is >= -64 and <= +63.

    With such a narrow range for a 1 byte delta, you might be justified in fixing your deltas to 2 bytes but if you can guarantee that the delta fits in 15 bits, the variable length encoding will give better compression.

    I hope that gets you started in thinking about different ways to interpret the problem. Let me know how it goes.
    Last edited by Zlatko; 08-24-2009 at 09:33 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 05:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21