3

ランレングスエンコーディングについて学習しようとしていますが、オンラインでこの課題を見つけましたが、それはできません。長さ 64 のバイナリ文字列 strg を入力として受け取り、別のバイナリ文字列を出力として返す、compression(strg) という圧縮関数を作成する必要があります。出力バイナリ文字列は、入力文字列のランレングス エンコーディングである必要があります。

圧縮('1010101001010101101010100101010110101010010101011010101001010101')

「1010101001010101*4」

ここに私が持っているものがありますが、これはパターンを見つけません:

from itertools import *

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

これを解決する助けが必要です。

4

3 に答える 3

5

RLEをLempel/Zivスライディングウィンドウ圧縮と混同していると思います。

RLEは、繰り返される文字に対して厳密に機能します： WWWWWWWW=>W8

LZには、説明したとおりにパターンをピックアップするスライディングウィンドウがあります。

David MacKayのサイトには、LZを含むPythonの圧縮コードの例があります

于 2012-10-19T18:42:25.547 に答える
0

詳細な説明を含むこの質問の回答は、次のリンクに記載されています。

ランレングス符号を用いた def compress(S) 関数による画像圧縮

文字列のランレングス エンコーディングとバイナリ圧縮の理解が深まることを願っています。このコーディングは、re および itertools のインポートを使用せずに行われます。

于 2015-09-09T04:58:43.990 に答える
0

これは、部分文字列の最長反復問題の例です。これは、サフィックス ツリーのデータ構造を使用して古典的に解決されます。

短い文字列の場合、正規表現の形式を使用できます。

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

出力を印刷します。これは、中央から完全に対称な文字列に対してのみ機能することに注意してください。これは、このタイプの問題の小さなサブセットです。他のタイプの文字列を圧縮するには、置換された要素がどのように置換されるかの表現文法が必要になります。

于 2012-10-20T01:44:52.530 に答える