3

ペタバイト単位で測定された結果を返す大きな理論上の文字列 (長さ 104 文字) のデータベース生成プログラムがあります。計算能力があまりないので、データベースから複雑度の低い文字列をフィルタリングしたいと思います。

私のグラマーは、数字を含まない英語のアルファベットを変形したものです。コルモゴロフの複雑さと、理論的には計算が不可能であることについて読みましたが、圧縮を使用して C# で基本的なものが必要なだけです。

これらの 2 つのリンクを使用して

私はこれを思いついた：

MemoryStream ms = new MemoryStream();

GZipStream gzip2 = new GZipStream(ms, CompressionMode.Compress, true);

byte[] raw = Encoding.UTF8.GetBytes(element);
gzip2.Write(raw, 0, raw.Length);
gzip2.Close();

byte[] zipped = ms.ToArray(); // as a BLOB
string smallstring = Convert.ToString(zipped); // as a string
// store zipped or base64
byte[] raw2 = Encoding.UTF8.GetBytes(smallstring);
int startsize = raw.Length;
int finishsize = raw2.Length;
double percent = Convert.ToDouble(finishsize) / Convert.ToDouble(startsize);
if (percent > .75)
{
    ///output
}

私の最初の要素は次のとおりです。

HHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHFHHHFH

13文字の仕上がりサイズに圧縮しますが、この他のおしゃべりセット

mlcllltlgvalvcgvpamdipqtkqdlelpklagtwhsmamatnnislmatlkaplrvhitsllptpednleivlhrwennscvekkvlgektenpkkfkinytvaneatlldtdydnflflclqdtttpiqsmmcqylarvlveddeimqgfirafrplprhlwylldlkqmeepcrf

も13に評価されます。バグがありますが、それを修正する方法がわかりません。

4

3 に答える 3

2

あなたのバグは、配列を文字列に変換する次の部分です。

byte[] zipped = ms.ToArray(); // as a BLOB
string smallstring = Convert.ToString(zipped); // as a string
// store zipped or base64
byte[] raw2 = Encoding.UTF8.GetBytes(smallstring);

配列を呼び出すConvert.ToString()と、デバッグ出力 (この場合は string ) が返されますSystem.Byte[]。(次のideoneの例を参照してください。)

圧縮されていないバイト配列と圧縮されたバイト配列の長さを直接比較する必要があります。

int startsize = raw.Length;
int finishsize = zipped.Length;
于 2012-08-24T19:31:04.197 に答える
1

これが私が使用したコードです

/// <summary>
/// Defines an interface to calculate relevant 
/// to the input complexity of a string
/// </summary>
public interface IStringComplexity
{
    double GetCompressionRatio(string input);
    double GetRelevantComplexity(double min, double max, double current);
}

そしてそれを実装するクラス

public class GZipStringComplexity : IStringComplexity
{
    public double GetCompressionRatio(string input)
    {
        if (string.IsNullOrEmpty(input))
            throw new ArgumentNullException();

        byte[] inputBytes = Encoding.UTF8.GetBytes(input);
        byte[] compressed;

        using (MemoryStream outStream = new MemoryStream())
        {
            using (var zipStream = new GZipStream(
                outStream, CompressionMode.Compress))
            {
                using (var memoryStream = new MemoryStream(inputBytes))
                {
                    memoryStream.CopyTo(zipStream);
                }
            }
            compressed = outStream.ToArray();
        }

        return (double)inputBytes.Length / compressed.Length;
    }

    /// <summary>
    /// Returns relevant complexity of a string on a scale [0..1], 
    /// where <value>0</value> has very low complexity
    /// and <value>1</value> has maximum complexity
    /// </summary>
    /// <param name="min">minimum compression ratio observed</param>
    /// <param name="max">maximum compression ratio observed</param>
    /// <param name="current">the value of compression ration
    /// for which complexity is being calculated</param>
    /// <returns>A relative complexity of a string</returns>
    public double GetRelevantComplexity(double min, double max, double current)
    {
        return 1 - current / (max - min);
    }
}

使用方法は次のとおりです

class Program
{
    static void Main(string[] args)
    {
        IStringComplexity c = new GZipStringComplexity();

        string input1 = "HHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHFHHHFH";
        string input2 = "mlcllltlgvalvcgvpamdipqtkqdlelpklagtwhsmamatnnislmatlkaplrvhitsllptpednleivlhrwennscvekkvlgektenpkkfkinytvaneatlldtdydnflflclqdtttpiqsmmcqylarvlveddeimqgfirafrplprhlwylldlkqmeepcrf";
        string inputMax = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

        double ratio1 = c.GetCompressionRatio(input1); //2.9714285714285715
        double ratio2 = c.GetCompressionRatio(input2); //1.3138686131386861
        double ratioMax = c.GetCompressionRatio(inputMax); //7.5

        double complexity1 = c.GetRelevantComplexity(1, ratioMax, ratio1); // ~ 0.54
        double complexity2 = c.GetRelevantComplexity(1, ratioMax, ratio2); // ~ 0.80
    }
}

役立つと思った追加情報。

7zip ライブラリの LZMA、LZMA2、または PPMD​​ を試すことができます。これらは設定が比較的簡単で、インターフェイスがあれば、いくつかの圧縮アルゴリズムを実装できます。これらのアルゴリズムは GZip よりもはるかに優れた圧縮を実行することがわかりましたが、圧縮率をスケールに入れる場合、これは実際には問題ではありません。

たとえば 0 から 1 に正規化された値が必要な場合は、最初にすべてのシーケンスの圧縮率を計算する必要があります。これは、可能な最大圧縮率を確認できないためです。

于 2012-08-24T20:34:53.613 に答える
0

確かに、それはうまくいきます。サイズを比較するだけであれば、どの圧縮アルゴリズムを使用しても問題ありません。あなたの主な関心事は、文字列を圧縮するために使用している処理能力の量を監視することです。

于 2012-08-24T19:01:08.697 に答える