-1

圧縮アルゴリズムを考えてみました。私は圧縮理論について少しはしているので、私が思いついたこのスキームでは、圧縮をまったく達成できない可能性があることを認識しています。

現在、文字/数字/記号が連続して繰り返されていない文字列に対してのみ機能します。適切に確立されたら、それをバイナリデータなどに外挿したいと思います。しかし、最初にアルゴリズムは次のとおりです。

4文字しかない場合：a、b、c、d; 文字に対応する行列/配列を作成します。文字が検出されるたびに、対応するインデックスがインクリメントされ、最後に検出された文字のインデックスが常に最大になります。インデックスが元々ゼロだった場合は、インデックスを2つ増やします。元々ゼロではなかった場合は、2+（マトリックスで2番目に大きい要素）ずつインクリメントします。明確にする例：

Array = [a,b,c,d]
Initial state = [0,0,0,0]
Letter = a
New state = [2,0,0,0]
Letter = b
New state = [2,4,0,0]
.
.c
.d
.
New state = [2,4,6,8]
Letter = a
New state = [12,4,6,8] 
//Explanation for the above state: 12 because Largest - Second Largest - 2 = Old value
Letter = d
New state = [12,4,6,22]
and so on...

解凍は、この逆のロジックです。

圧縮の基本的な実装（Python）：

（この関数は非常に初歩的なものであるため、最良の種類のコードではありません...わかっています。コアアルゴリズムが正しくなると、最適化できます。）

def compress(text):
    matrix = [0]*95     #we are concerned with 95 printable chars for now
    for i in text:
        temp = copy.deepcopy(matrix) 
        temp.sort()
        largest = temp[-1]
        if matrix[ord(i)-32] == 0:
            matrix[ord(i)-32] = largest+2
        else:
            matrix[ord(i)-32] = largest+matrix[ord(i)-32]+2
    return matrix

返された行列は、解凍に使用されます。ここで注意が必要な部分があります。

関数から生成された行列の各数値は、長さ50000の文字列に対して10 ** 200のオーダーであるため、この圧縮を実際に呼び出すことはできません。したがって、行列を格納すると、元の文字列を格納するよりも実際に多くのスペースが必要になります。私は知っています...まったく役に立たない。しかし、これをすべて行う前に、行列の数学的特性を使用して、ある種の数学的省略形で効果的に表現できることを望んでいました。私は多くの可能性を試しましたが失敗しました。私が試したいくつかのこと：

  1. 行列のランク。一意ではないため失敗しました。

  2. mod関数を使用して示します。商または剰余が原因で失敗しました

  3. pickleを使用して、各整数をジェネレーターとして格納します。

  4. マトリックスをビットマップファイルとして保存しますが、整数が大きすぎてカラーコードとして保存できません。

アルゴリズムを最適化できることをもう一度繰り返します。たとえば、2を追加する代わりに、1を追加して続行できます。ただし、実際には圧縮されないでください。コードについても同じです。後でマイナーな最適化...最初にメインアルゴリズムを改善したいと思います。

さらに、私のような平凡で怠惰な心のこの製品は、結局、圧縮を達成することができなかった可能性が非常に高いです。その場合は、これがおそらく何に役立つかについて、あなたの助けとアイデアをお願いします。

TL; DR：圧縮アルゴリズムを表すコード化された部分をチェックします。圧縮された結果は、元の文字列よりも長くなります。これは修正できますか？はいの場合、どのように？

PS：私は自分のPCにコード全体を持っています。githubにリポジトリを作成し、しばらくしてからアップロードします。

4

1 に答える 1

3

圧縮は本質的に予測プロセスです。入力内のパターンを探し、それらを使用して、可能性の低い次の文字をより効率的にエンコードします。予測モデルを構築しようとするアルゴリズムには何も表示されません。

于 2012-11-06T12:21:27.797 に答える