파이썬 압축 실행 길이 인코딩

Question

나는 런 길이 인코딩에 대해 배우려고 노력하고 있으며, 내가 할 수없는 온라인 챌린지를 발견했다. 압축으로 길이가 64 인 이진 문자열 strg를 입력으로 사용하고 다른 이진 문자열을 출력으로 반환하는 압축 함수 (strg)를 작성해야합니다. 출력 바이너리 문자열은 입력 문자열의 런 길이 인코딩이어야합니다. 여기

압축 ('1010101001010101101010100101010110101010010101011010101001010101')

'1010101001010101 * 4'

내가 무슨이지만,이 패턴을 발견하지 않습니다

from itertools import * 

def compression(strg): 
    return [(len(list(group)),name) for name, group in groupby(strg)] 

이 문제를 해결하는 데 도움이 필요합니다.

Answer 1

저는 REL과 Lempel/Ziv 슬라이딩 윈도우 압축을 병합한다고 생각합니다.

RLE는 엄격하게 반복되는 문자에서 작동 : WWWWWWWW =>W8

LZ은 당신이 설명대로 패턴을 데리러 슬라이딩 윈도우를 가지고있다.

데이비드 맥케이의 site는 LZ

Answer 2

이것은 longest repeated substring problem의 예를 포함하여, 파이썬 예를 압축 코드를 가지고있다. 이는 데이터 구조가 suffix tree 인 것으로 고전적으로 해결되었습니다.

짧은 문자열의 경우, 정규식의 양식을 사용할 수 있습니다

import re 

s1='1010101001010101101010100101010110101010010101011010101001010101' 

i=2 
l=s1 
j=len(l)/2 
while i<len(s1): 
    m=re.search('^(.{'+str(j)+'})\\1$',l) 
    if m: 
     l=m.group(1) 
     i,j=i+1,len(l)/2 
     continue 
    else: 
     print '{0} * {1} = {2}'.format(l,i,s1) 
     break 

당신의 출력을 인쇄합니다. 이것은 중간에서 완전히 대칭 인 문자열에 대해서만 작동합니다 -이 유형의 문제의 작은 하위 집합입니다. 다른 유형의 문자열을 압축하려면 대체 된 요소가 대체되는 방법에 대한 표현 문법이 필요합니다. 상세한 설명이 질문의

Answer 3

대답은 다음 링크에서 제공됩니다 :

Image compression by def compress(S) function using run-length codig

그것이 문자열과 바이너리 압축 실행 길이 인코딩의 이해를 취소 바랍니다. 이 코드는 re 및 itertools 가져 오기를 사용하지 않고 수행됩니다.