https://stackoverflow.com/questions/2261318
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
古典RLE圧縮アルゴリズムを使用してデータ数を表すのにどのように多くの文字数が表示されるテキストを開発した。例えば:
AAABBAAABBCECE=>3A2B3A2B1C1E1C1E
しかし、上記の例では、このメソッドの結果にもスペースの利用に圧縮します。ようというアイデアを利用する番号を表すのにどのように多くの 部分文字列 記番号が表示され、指定された。例えば:
AAABBAAABBCECE=>2AAABB2CE("AAABB"、そして"CEす。
今、私の質問はどのようにしたら良いですか実施の効率的なアルゴリズムが最小文字数に応じ、最適なRLEこの方法は？総当たり攻撃方法が存在しないもの高速化（ O(長さ2)).も活用して動的計画?
解決
これは、動的プログラミングを介して次 立方二次の時間で行うことができます。
ここではいくつかのPythonコードは次のとおりです。
import sys
import numpy as np
bignum = 10000
S = sys.argv[1] #'AAABBAAABBCECE'
N = len(S)
# length of longest substring match bet s[i:] and s[j:]
maxmatch = np.zeros( (N+1,N+1), dtype=int)
for i in xrange(N-1,-1,-1):
for j in xrange(i+1,N):
if S[i] == S[j]:
maxmatch[i,j] = maxmatch[i+1,j+1]+1
# P[n,k] = cost of encoding first n characters given that last k are a block
P = np.zeros( (N+1,N+1),dtype=int ) + bignum
# Q[n] = cost of encoding first n characters
Q = np.zeros(N+1, dtype=int) + bignum
# base case: no cost for empty string
P[0,0]=0
Q[0]=0
for n in xrange(1,N+1):
for k in xrange(1,n+1):
if n-2*k >= 0:
# s1, s2 = S[n-k:n], S[n-2*k:n-k]
# if s1 == s2:
if maxmatch[n-2*k,n-k] >=k:
# Here we are incrementing the count: C x_1...x_k -> C+1 x_1...x_k
P[n,k] = min(P[n,k], P[n-k,k])
print 'P[%d,%d] = %d' % (n,k,P[n,k])
# Here we are starting a new block: 1 x_1...x_k
P[n,k] = min(P[n,k], Q[n-k] + 1 + k)
print 'P[%d,%d] = %d' % (n,k,P[n,k])
for k in xrange(1,n+1):
Q[n] = min(Q[n], P[n,k])
print
print Q[N]
あなたが道に沿ってあなたの選択肢を覚えることで、実際のエンコーディングを再構築することができます。
私たちはCが大きい場合C + 1を保持するために、余分なバイトを使用する必要がありますということであるマイナーなしわを、取り残されています。あなたは32ビットのint型を使用している場合、これは、このアルゴリズムの実行時間が実行可能である任意のコンテキストで起動しません。あなたは時々、スペースを節約するために短いint型を使用している場合、あなたはそれについて考える必要があります、そしておそらく理論的には、最新のCの大きさに基づいて、あなたのテーブルに別の次元を追加し、これは、ログ（N）の要因を追加するかもしれませんが、私は、これは実際には明らかであろうとは思わない。
編集：あなたは、より簡単なアルゴリズムを考えているのかを見ることができるように@Moronの利益のために、ここではより多くのprint文と同じコードは、次のとおりです。
import sys
import numpy as np
bignum = 10000
S = sys.argv[1] #'AAABBAAABBCECE'
N = len(S)
# length of longest substring match bet s[i:] and s[j:]
maxmatch = np.zeros( (N+1,N+1), dtype=int)
for i in xrange(N-1,-1,-1):
for j in xrange(i+1,N):
if S[i] == S[j]:
maxmatch[i,j] = maxmatch[i+1,j+1]+1
# P[n,k] = cost of encoding first n characters given that last k are a block
P = np.zeros( (N+1,N+1),dtype=int ) + bignum
# Q[n] = cost of encoding first n characters
Q = np.zeros(N+1, dtype=int) + bignum
# base case: no cost for empty string
P[0,0]=0
Q[0]=0
for n in xrange(1,N+1):
for k in xrange(1,n+1):
if n-2*k >= 0:
# s1, s2 = S[n-k:n], S[n-2*k:n-k]
# if s1 == s2:
if maxmatch[n-2*k,n-k] >=k:
# Here we are incrementing the count: C x_1...x_k -> C+1 x_1...x_k
P[n,k] = min(P[n,k], P[n-k,k])
print "P[%d,%d] = %d\t I can encode first %d characters of S in only %d characters if I use my solution for P[%d,%d] with %s's count incremented" % (n\
,k,P[n,k],n,P[n-k,k],n-k,k,S[n-k:n])
# Here we are starting a new block: 1 x_1...x_k
P[n,k] = min(P[n,k], Q[n-k] + 1 + k)
print 'P[%d,%d] = %d\t I can encode first %d characters of S in only %d characters if I use my solution for Q[%d] with a new block 1%s' % (n,k,P[n,k],n,Q[\
n-k]+1+k,n-k,S[n-k:n])
for k in xrange(1,n+1):
Q[n] = min(Q[n], P[n,k])
print
print 'Q[%d] = %d\t I can encode first %d characters of S in only %d characters!' % (n,Q[n],n,Q[n])
print
print Q[N]
ABCDABCDABCDBCDに、その出力の最後の数行はとても似ています
Q[13] = 7 I can encode first 13 characters of S in only 7 characters!
P[14,1] = 9 I can encode first 14 characters of S in only 9 characters if I use my solution for Q[13] with a new block 1C
P[14,2] = 8 I can encode first 14 characters of S in only 8 characters if I use my solution for Q[12] with a new block 1BC
P[14,3] = 13 I can encode first 14 characters of S in only 13 characters if I use my solution for Q[11] with a new block 1DBC
P[14,4] = 13 I can encode first 14 characters of S in only 13 characters if I use my solution for Q[10] with a new block 1CDBC
P[14,5] = 13 I can encode first 14 characters of S in only 13 characters if I use my solution for Q[9] with a new block 1BCDBC
P[14,6] = 12 I can encode first 14 characters of S in only 12 characters if I use my solution for Q[8] with a new block 1ABCDBC
P[14,7] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[7] with a new block 1DABCDBC
P[14,8] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[6] with a new block 1CDABCDBC
P[14,9] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[5] with a new block 1BCDABCDBC
P[14,10] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[4] with a new block 1ABCDABCDBC
P[14,11] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[3] with a new block 1DABCDABCDBC
P[14,12] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[2] with a new block 1CDABCDABCDBC
P[14,13] = 16 I can encode first 14 characters of S in only 16 characters if I use my solution for Q[1] with a new block 1BCDABCDABCDBC
P[14,14] = 15 I can encode first 14 characters of S in only 15 characters if I use my solution for Q[0] with a new block 1ABCDABCDABCDBC
Q[14] = 8 I can encode first 14 characters of S in only 8 characters!
P[15,1] = 10 I can encode first 15 characters of S in only 10 characters if I use my solution for Q[14] with a new block 1D
P[15,2] = 10 I can encode first 15 characters of S in only 10 characters if I use my solution for Q[13] with a new block 1CD
P[15,3] = 11 I can encode first 15 characters of S in only 11 characters if I use my solution for P[12,3] with BCD's count incremented
P[15,3] = 9 I can encode first 15 characters of S in only 9 characters if I use my solution for Q[12] with a new block 1BCD
P[15,4] = 14 I can encode first 15 characters of S in only 14 characters if I use my solution for Q[11] with a new block 1DBCD
P[15,5] = 14 I can encode first 15 characters of S in only 14 characters if I use my solution for Q[10] with a new block 1CDBCD
P[15,6] = 14 I can encode first 15 characters of S in only 14 characters if I use my solution for Q[9] with a new block 1BCDBCD
P[15,7] = 13 I can encode first 15 characters of S in only 13 characters if I use my solution for Q[8] with a new block 1ABCDBCD
P[15,8] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[7] with a new block 1DABCDBCD
P[15,9] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[6] with a new block 1CDABCDBCD
P[15,10] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[5] with a new block 1BCDABCDBCD
P[15,11] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[4] with a new block 1ABCDABCDBCD
P[15,12] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[3] with a new block 1DABCDABCDBCD
P[15,13] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[2] with a new block 1CDABCDABCDBCD
P[15,14] = 17 I can encode first 15 characters of S in only 17 characters if I use my solution for Q[1] with a new block 1BCDABCDABCDBCD
P[15,15] = 16 I can encode first 15 characters of S in only 16 characters if I use my solution for Q[0] with a new block 1ABCDABCDABCDBCD
Q[15] = 9 I can encode first 15 characters of S in only 9 characters!
他のヒント
私はあなたが、溶液中の完全な文字列の長さの半分程度のサブ文字列を持っている可能性があるので、動的プログラミングは、ここで働いうとは思いません。あなたはブルートフォースを使用する必要があるように見えます。
関連する問題については、
RLE圧縮されたデータを符号化するために非常に一般的な方法は、「次のバイトが続くカウントであることを意味する、（申し訳ありませんが、私はその用語が何の略か覚えていない）「DLE」のような特別なバイトを指定することです」ます。
この方法では、配列のみを繰り返してエンコードする必要があります。典型的には、DLEのシンボルは、それが非圧縮データで天然の可能性を最小にするように選択される。
次のようには、あなたのオリジナルたとえば、のは、これはあなたの例をエンコードしますDLEとしてピリオド（ドット）を設定できます：
AAABBAAABBCECE => 3A2B3A2B1C1E1C1E <-- your encoding
AAABBAAABBCECE => .3ABB.3ABBCECE <-- my encoding
あなただけの配列をコードします。カウントはバイトに収まるようにあなたは、255に配列の長さを制限した場合、シーケンスは、このように3バイト、DLE、数、および繰り返すバイトを取ります。これらをデコードすることは非コードされる配列よりもわずかに多くのオーバーヘッドを運ぶので、あなたはおそらく、いずれか3バイトの配列をコードしません。
あなたの簡単な例では、貯蓄がnonexistantですが、メモ帳などのほとんどが白いプログラム、またはブラウザのスクリーンショットを含むビットマップを圧縮しようとした場合、あなたは本物のスペースの節約が表示されます。
あなたは私たちが長さ0の配列をコードしないだろう知っているので、ちょうど、0の数を発し、自然にDLE文字に遭遇する必要がある場合は、、0バイトに続くDLEは、単一のDLEバイトとしてそれをデコードすることを意味しますます。
マッチする部分を見つけることの非常に巧妙な方法は接尾辞木や接尾辞配列を考慮につながる可能性があります。 //en.wikipedia：接尾辞配列と圧縮について考えることは HTTPにあなたを導くこと.ORG /ウィキ/バローズ％E2％80％93Wheeler_transform に。これは、ランレングス符号化をsoupingの最もエレガントな方法かもしれません。
