Das deutsche Python-Forum

Code: Alles auswählen

81 0A 0? 0B 81 0C

Code: Alles auswählen

8? 0A 0B .. 0B 0C

Code: Alles auswählen

81 XX 7f YY 81 YY

Code: Alles auswählen

82 XX YY 7f YY

Code: Alles auswählen

def RLE(A):
    optimal = [None] * len(A)
    optimal.append((0, "dummy", 0, [])) # total length of encoded sequence, runtype (0 or 128), number of values, list of values

    for start in range(len(A))[::-1]:
        candidates = []
        # non-identical runs
        for run_length in range(min(len(A) - start, 127)): 
            candidates.append((2 + run_length + optimal[start + run_length + 1][0], 128, run_length + 1, A[start:start+run_length+1]))
        # identical runs
        for run_length in range(1, min(len(A) - start, 127)): 
            if A[start] != A[start + run_length]:
                break
            candidates.append((2 + optimal[start + run_length + 1][0], 0, run_length + 1, A[start:start+1]))
        optimal[start] = min(candidates)
        
    steps = []
    pos = 0
    while pos < len(A):
        length, run_type, run_length, values = optimal[pos]
        steps.append(run_type + run_length)
        steps.extend(values)
        pos += run_length
    return steps

Code: Alles auswählen

>>> RLE([100] + 128*[101])
[130, 100, 101, 127, 101]
>>> RLE([100] + 128*[101] + [100])
[129, 100, 127, 101, 130, 101, 100]
>>> RLE([100] + 128*[101] + [100,100])
[130, 100, 101, 127, 101, 2, 100]

Code: Alles auswählen

from itertools import groupby


def iter_runs(data):
    for value, group in groupby(data):
        yield value, sum(1 for _ in group)


def rle(data):
    result = list()
    # 
    # This list collects bytes that will be encoded as non-runs i.e. prefixed
    # by a count byte with a set bit 7.  Although it can become up to
    # `len(data)` elements in length, this algorithm can be adapted to use
    # at most 127 entries.
    # 
    # It may even be possible to use the result list as buffer for these
    # entries by storing a dummy count byte which will be fixed up when the
    # actual count is determined.
    # 
    non_run = list()

    def copy_non_run():
        """Copy the content of the `non_run` buffer to the result."""
        for i in xrange(0, len(non_run), 127):
            chunk = non_run[i:i + 127]
            result.append(128 | len(chunk))
            result.extend(chunk)

    for value, count in iter_runs(data):
        if count == 1:
            non_run.append(value)
        else:
            # 
            # Check if there is one single value left which cannot be encoded
            # in one (count byte, value) pair.
            # 
            # If the single value does fit into a non-run then append it
            # before the encoded run, otherwise put it into the non-run buffer
            # after encoding the run.
            # 
            one_byte_left = count % 127 == 1
            if one_byte_left:
                if len(non_run) % 127 != 0:
                    non_run.append(value)
                    one_byte_left = False
                count -= 1
            # 
            # Flush the collected non-run bytes so far.
            # 
            copy_non_run()
            non_run = [value] if one_byte_left else []
            # 
            # Encode the run.
            # 
            while count:
                run_count = min(127, count)
                result.extend([run_count, value])
                count -= run_count
    # 
    # Flush the possibly remaining non-run bytes.
    # 
    copy_non_run()
    return result

Code: Alles auswählen

In [2]: rle([0, 1, 1, 0])
Out[2]: [129, 0, 2, 1, 129, 0]

In [3]: RLE([0, 1, 1, 0])
Out[3]: [132, 0, 1, 1, 0]