3

我有一个大型理论字符串（104 个字符长）数据库生成程序，它返回以 PB 为单位的结果。我没有那么多的计算能力，所以我想从数据库中过滤出低复杂度的字符串。

我的语法是英文字母表的修改形式，没有数字字符。我阅读了有关Kolmogorov 复杂性以及理论上不可能计算的内容，但我只需要使用压缩的 C# 中的一些基本内容。

使用这两个链接

我想出了这个：

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
}

我的第一个元素是：

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！

并且它压缩到13 个字符的完成大小，但是这个其他聊天集

mlcllltlgvalvcgvpamdipqtkqdellplagtwhsmamatnnislmatlkaplrvhitsllptpednleivlhrwennscvekkvlgektenpkkfkinytvaneatlldtdydnflflclqdtttpiqsmmcqylarvlveddeimqgfirafrplprhlwylldlkqmeepcrf

也评估为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 回答