none
Console application and rle decompression RRS feed

All replies

  • Hi,

    The basic idea of RLE compression algorithm is to divide data into two cases according to linear sequence: one is continuous repeated data blocks, the other is continuous non-repeated data blocks. For continuous repeated data, RLE algorithm usually uses two bytes to represent the original continuous multi-byte repeated data.

    If the original data has 5 bytes of continuous data:
    [data] [data] [data] [data] [data] [data]

    The compressed data contains two bytes of block number and [data], in which [data] is stored only once, saving storage space:
    [5] [data]

    It should be noted that the general RLE algorithm uses the insertion of a long attribute byte to store the repeated times of continuous data, so the maximum value that can be expressed is 255 bytes. If the same continuous data exceeds 255 bytes, it will be disconnected from 255 bytes, and the number of 256 bytes and the number after 256 bytes will be equal. New data processing.

    What you want is the effect shown in the picture below? If so, You can try my code.

    Imports System.Text
    
    Module Module1
        Sub Main()
            Dim str As String = "bewoooofbbbb2222225555bbbeiwofnnnnnnnnnnnnnfnewpfjqepf"
            Dim originalData As Byte() = Encoding.[Default].GetBytes(str)
            Dim originalDataSize As Integer = str.Length
            Dim compressedData As Byte() = New Byte(originalDataSize * (257 \ 256)) {}
            Dim compressedDataSize As Integer = Compress(originalData, compressedData, CUInt(originalDataSize))
            Console.WriteLine(Encoding.[Default].GetString(compressedData))
            Dim decompressedData As Byte() = New Byte(originalDataSize - 1) {}
            Decompress(compressedData, decompressedData, CUInt(compressedDataSize))
            Console.ReadKey()
        End Sub
        Private Sub encodeRepetition(output As Byte(), ByRef outputPosition As UInteger, marker As Byte, symbol As Byte, count As UInteger)
            Dim index As UInteger = outputPosition
    
            If count <= 3 Then
                If symbol = marker Then
                    output(index) = marker
                    index += 1
                    output(index) = CByte(count - 1)
                    index += 1
                Else
                    For i As UInteger = 0 To count - 1
                        output(index) = symbol
                        index += 1
                    Next
                End If
            Else
                output(index) = marker
                index += 1
                count -= 1
    
                If count >= 128 Then
                    output(index) = CByte((count >> 8) Or &H80)
                    index += 1
                End If
    
                output(index) = CByte(count And &HFF)
                index += 1
                output(index) = symbol
                index += 1
            End If
    
            outputPosition = index
        End Sub
    
        Private Sub encodeNonRepetition(output As Byte(), ByRef outputPosition As UInteger, marker As Byte, symbol As Byte)
            Dim index As UInteger = outputPosition
    
            If symbol = marker Then
                output(index) = marker
                index += 1
                output(index) = 0
                index += 1
            Else
                output(index) = symbol
                index += 1
            End If
    
            outputPosition = index
        End Sub
    
        Public Function Compress(input As Byte(), ByRef output As Byte(), inputSize As UInteger) As Integer
            Dim byte1 As Byte, byte2 As Byte, marker As Byte
            Dim i As UInteger, inputPosition As UInteger, outputPosition As UInteger, count As UInteger
            Dim histogram As UInteger() = New UInteger(255) {}
    
            If inputSize < 1 Then
                Return 0
            End If
    
            For i = 0 To 255
                histogram(i) = 0
            Next
    
            For i = 0 To inputSize - 1
                histogram(input(i)) += 1
            Next
    
            marker = 0
    
            For i = 1 To 255
                If histogram(i) < histogram(marker) Then
                    marker = CByte(i)
                End If
            Next
    
            output(0) = marker
            outputPosition = 1
    
            byte1 = input(0)
            inputPosition = 1
            count = 1
    
            If inputSize >= 2 Then
                byte2 = input(inputPosition)
                inputPosition += 1
                count = 2
    
                Do
                    If byte1 = byte2 Then
                        While (inputPosition < inputSize) AndAlso (byte1 = byte2) AndAlso (count < 32768)
                            byte2 = input(inputPosition)
                            inputPosition += 1
                            count += 1
                        End While
    
                        If byte1 = byte2 Then
                            encodeRepetition(output, outputPosition, marker, byte1, count)
    
                            If inputPosition < inputSize Then
                                byte1 = input(inputPosition)
                                inputPosition += 1
                                count = 1
                            Else
                                count = 0
                            End If
                        Else
                            encodeRepetition(output, outputPosition, marker, byte1, count - 1)
                            byte1 = byte2
                            count = 1
                        End If
                    Else
                        encodeNonRepetition(output, outputPosition, marker, byte1)
                        byte1 = byte2
                        count = 1
                    End If
                    If inputPosition < inputSize Then
                        byte2 = input(inputPosition)
                        inputPosition += 1
                        count = 2
                    End If
                Loop While (inputPosition < inputSize) OrElse (count >= 2)
            End If
    
            If count = 1 Then
                encodeNonRepetition(output, outputPosition, marker, byte1)
            End If
    
            Return CInt(outputPosition)
        End Function
    
        Public Sub Decompress(input As Byte(), output As Byte(), inputSize As UInteger)
            Dim marker As Byte, symbol As Byte
            Dim i As UInteger, inputPosition As UInteger, outputPosition As UInteger, count As UInteger
    
            If inputSize < 1 Then
                Return
            End If
    
            inputPosition = 0
            marker = input(inputPosition)
            inputPosition += 1
            outputPosition = 0
    
            Do
                symbol = input(inputPosition)
                inputPosition += 1
    
                If symbol = marker Then
                    count = input(inputPosition)
                    inputPosition += 1
    
                    If count <= 2 Then
                        For i = 0 To count
                            output(outputPosition) = marker
                            outputPosition += 1
                        Next
                    Else
                        If Convert.ToBoolean(count And &H80) Then
                            count = ((count And &H7F) << 8) + input(inputPosition)
                            inputPosition += 1
                        End If
    
                        symbol = input(inputPosition)
                        inputPosition += 1
    
                        For i = 0 To count
                            output(outputPosition) = symbol
                            outputPosition += 1
                        Next
                    End If
                Else
                    output(outputPosition) = symbol
                    outputPosition += 1
                End If
            Loop While inputPosition < inputSize
    
            Console.WriteLine(Encoding.[Default].GetString(output))
        End Sub
    End Module
    

    Hope I can help you.

    Best Regards,

    Julie


    MSDN Community Support Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Wednesday, September 25, 2019 7:24 AM
    Moderator