cadena de compresión de complejidad

Tengo un gran progtwig de generación de bases de datos de cadenas teóricas (104 caracteres) que devuelve resultados medidos en petabytes. No tengo mucho poder de cómputo, así que me gustaría filtrar las cadenas de baja complejidad de la base de datos.

Mi gramática es una forma modificada del alfabeto inglés sin caracteres numéricos. Leí sobre la complejidad de Kolmogorov y sobre cómo es teóricamente imposible de calcular, pero necesito algo básico en C # usando compresión.

Usando estos dos enlaces

  • ¿Cómo medir la complejidad de una cuerda?
  • Cómo determinar el tamaño de la cuerda y comprimirla

Se me ocurrió esto:

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 } 

mi primer elemento es:

HHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHFHHHFHAAAAHHHFHHFFHHFHHFFHHHHHHFFHAHHHHHHHHHHHHHHHHHHHHHHFHHHHHHHHHHHHHHHHHHHHHHHHHHHHFH

y se comprime a un tamaño final de 13 caracteres, pero este otro conjunto de chatcter

mlcllltlgvalvcgvpamdipqtkqdlelpklagtwhsmamatnnislmatlkaplrvhitsllptpednleivlhrwennscvekkvlgektenpkkkkkkggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg

También se evalúa a 13 . Hay un error pero no sé cómo solucionarlo.

Su error es la siguiente parte en la que convierte la matriz en una cadena:

 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); 

Llamar a Convert.ToString() en una matriz devolverá algunos resultados de depuración, en este caso la cadena System.Byte[] . (Vea el siguiente ejemplo en ideone .)

Debe comparar las longitudes de la matriz de bytes comprimidos y sin comprimir directamente:

 int startsize = raw.Length; int finishsize = zipped.Length; 

Aquí hay un código que usé

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

Y la clase que lo implementa.

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

Así es como puedes usarlo.

 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 } } 

Alguna información adicional que encontré útil.

Puede intentar usar LZMA, LZMA2 o PPMD ​​desde la biblioteca 7zip . Esos son relativamente fáciles de configurar y, si tiene una interfaz, puede implementar varios algoritmos de compresión. Encontré que esos algoritmos realizan una compresión mucho mejor que GZip, pero si pones una relación de compresión en una escala, esto realmente no importa.

Si necesita un valor normalizado, por ejemplo, de 0 a 1, primero deberá calcular la relación de compresión para todas las secuencias. Esto se debe a que no puede estar seguro de cuál es la relación de compresión máxima posible.

Claro, eso funcionará. Mientras esté comparando tamaños, realmente no importa qué algoritmo de compresión utilice. Su principal preocupación es controlar la cantidad de potencia de procesamiento que está utilizando para comprimir las cuerdas.