使用素数压缩

Question

我想我已经找到了一种方法，可以使用素数进行无损压缩，或者反复使用其他方法。

0-255范围内有54个素数，当我们在字节数组中有素数时，我们可以使用该数的素数索引来存储它，使用6位而不是8位，对吗？

我们需要为每个字节创建一个映射，我们可以存储压缩的数字，并将其html" target="_blank">添加到数据数组中。

起初，这似乎可行，但会略微增加文件大小，但对于LZ4或Huffman之类的算法，会将文件减少为可重新压缩的结构。

索引0-53对应于素数2-251，但有6位的未使用数字。(54-63). 这10个数字也可以用来存储10个不同的非素数，最高频率为6位。所以我们要压缩更多的数字。如果该比率超过50%，我们将能够成功执行压缩。

此外，这种方法可以创造一个重新压缩压缩数字的机会。你认为如果我们在4或8字节的数据块而不是一个字节中创建一个uint和ulong数据类型的方法，我们可以将压缩数据的映射缩小到更小的大小，对吗？

有203280221个小于2^32的素数。这意味着我们可以为每个素数存储28位而不是32位。

通过查看数据数组中素数的比率，我们可以确定是否可以执行有效的压缩。

我认为这种方法不是一种有效的压缩方法，而是一种允许对压缩文件进行重新压缩的数据交换方法。

我想问你知道我们可以用素数做的其他方法吗？因为获得素数非常容易，尤其是对于2^32以下的数字。我们需要在方法中加入素数方法。

Answer 1

你们误会了。我说的是压缩随机数据。如果你把一个文件分成4字节的数据块，每个4字节的数字中10个中有1个是素数。你还应该使用位图来确定每个数字是否是素数。使用位图会明显增加文件的大小，但我认为它可以压缩到32/80以上。因为它有太多的0位。

你可能会说，“这是一个非常有趣的压缩算法。”因为它更压缩大小正在使用其他压缩算法。但是拥有重复压缩过程的能力难道不重要吗？请忽略这种有趣的情况。

一步一步地。首先，让我分享一下我们需要的主要助手代码。

findPrimes（）和saveToFile（）方法如何在这些代码中更有效？目前，在我的Core i7上可以在大约23分钟内找到最高2^32的质数，并保存在512MB中。然后，您可以从文件中加载质数以供直接使用，而无需重新计算。

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace PrimeNumbers {
    public static class PrimeHelper {
        public static IEnumerable<long> FindPrimes (long limit) {
            return (new Primes (limit));
        }

        public static IEnumerable<long> FindPrimes (long start, long end) {
            return FindPrimes (end).Where (pn => pn >= start);
        }

        public static bool IsPrime (this long number) {
            if (number < 2)
                return false;
            else if (number < 4)
                return true;

            var limit = (Int32) System.Math.Sqrt (number) + 1;
            var foundPrimes = new Primes (limit);

            return foundPrimes.IsPrime (number);
        }

        public static bool IsPrime (this int number) {
            return IsPrime (Convert.ToInt64 (number));
        }

        public static bool IsPrime (this short number) {
            return IsPrime (Convert.ToInt64 (number));
        }

        public static bool IsPrime (this byte number) {
            return IsPrime (Convert.ToInt64 (number));
        }

        public static bool IsPrime (this uint number) {
            return IsPrime (Convert.ToInt64 (number));
        }

        public static bool IsPrime (this ushort number) {
            return IsPrime (Convert.ToInt64 (number));
        }

        public static bool IsPrime (this sbyte number) {
            return IsPrime (Convert.ToInt64 (number));
        }
    }

    public class Primes : IEnumerable<long>, IDisposable {
        private long limit;
        private MyBitArray numbers;

        public Primes (long limit) {
            startTime = DateTime.Now;
            calculateTime = startTime - startTime;
            this.limit = limit + 1;
            try { findPrimes (); } catch (Exception e) { Console.WriteLine (e.Message); /*Overflows or Out of Memory*/ }

            calculateTime = DateTime.Now - startTime;
        }

        public Primes (MyBitArray bitArray) {
            this.numbers = bitArray;
            this.limit = bitArray.Limit;
        }

        private void findPrimes () {
            /*
            The Sieve Algorithm
            http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
            */
            numbers = new MyBitArray (limit, true);
            for (long i = 2; i < limit; i++)
                if (numbers[i])
                    for (long j = i * 2; j < limit; j += i)
                        numbers[j] = false;
        }

        public IEnumerator<long> GetEnumerator () {
            for (long i = 2; i < limit; i++)
                if (numbers[i])
                    yield return i;
        }

        IEnumerator IEnumerable.GetEnumerator () {
            return GetEnumerator ();
        }

        // Extended big long number for quickly calculation
        public bool IsDivisible (long number) {
            var sqrt = System.Math.Sqrt (number);
            foreach (var prime in this) {
                if (number % prime == 0) {
                    DivisibleBy = prime;
                    return true;
                }

                if (prime > sqrt)
                    return false;
            }

            return false;
        }

        // For big long number
        public bool IsPrime (long number) {
            return number < limit ?
                this.SingleOrDefault (n => n == number) != 0 :
                !IsDivisible (number);
        }

        public void Dispose () {
            numbers.Dispose ();
        }

        public void SaveToFile (string fileName, SaveOptions saveOptions) {
            int elementSize = 8;

            if ((this.limit - 1L) <= Convert.ToInt64 (byte.MaxValue))
                elementSize = 1;
            else if ((this.limit - 1L) <= Convert.ToInt64 (ushort.MaxValue))
                elementSize = 2;
            else if ((this.limit - 1L) <= Convert.ToInt64 (uint.MaxValue))
                elementSize = 4;

            switch (saveOptions) {
                case SaveOptions.TextFile:
                    saveToTextFile (fileName);
                    break;
                case SaveOptions.BinaryAllNumbersBitArray:
                    saveToFile (fileName, this.Numbers.Bytes);
                    break;
                case SaveOptions.BinaryPrimeList:
                    saveToFile (fileName, this, elementSize);
                    break;
                case SaveOptions.BinaryAllNumbersAndPrimeIndex:
                    saveToFileOnlyIndex (fileName, this, elementSize);
                    break;
                case SaveOptions.All:
                    saveToFile (Path.Combine (Path.GetDirectoryName (fileName), Path.GetFileNameWithoutExtension (fileName) + "_BinaryAllNumbersBitArray.bin"), this.Numbers.Bytes);
                    saveToFile (Path.Combine (Path.GetDirectoryName (fileName), Path.GetFileNameWithoutExtension (fileName) + "_BinaryPrimeList.bin"), this, elementSize);
                    saveToFileOnlyIndex (Path.Combine (Path.GetDirectoryName (fileName), Path.GetFileNameWithoutExtension (fileName) + "_BinaryAllNumbersPrimeIndex.bin"), this, elementSize);
                    saveToTextFile (Path.Combine (Path.GetDirectoryName (fileName), Path.GetFileNameWithoutExtension (fileName) + "_TextFile.txt"));
                    break;

            }
        }

        protected void saveToFile (string fileName, byte[] data) {
            Console.WriteLine ("Saving numbers bits if is prime bit 1 else bit 0...");
            using (MemoryStream mstream = new MemoryStream (data)) {
                ProgressCallback callback = (long position, long total) => { };
                copy (mstream, fileName, callback);
            }
        }

        protected void saveToFile (string fileName, Primes primes, int elementSize = 4) {
            Console.WriteLine ("Saving primes. Element size: {0}...", elementSize);
            using (FileStream file = File.OpenWrite (fileName)) {
                long writed = 0;
                foreach (var prime in primes) {
                    byte[] data = new byte[elementSize];

                    if (elementSize == 8) {
                        data = BitConverter.GetBytes (Convert.ToUInt64 (prime));
                    } else if (elementSize == 4) {
                        data = BitConverter.GetBytes (Convert.ToUInt32 (prime));
                    } else if (elementSize == 2) {
                        data = BitConverter.GetBytes (Convert.ToUInt16 (prime));
                    } else if (elementSize == 1) {
                        data = BitConverter.GetBytes (Convert.ToByte (prime));
                    }

                    file.Write (data, 0, elementSize);
                    writed++;

                    if (writed == 536870912L) {
                        file.Flush (true);
                        writed = 0;
                    }
                }
                file.Close ();
            }
        }

        protected void saveToFileOnlyIndex (string fileName, Primes primes, int elementSize = 4) {
            Console.WriteLine ("Saving all numbers prime indexes if not prime index is -1. Element size: {0}...", elementSize);
            using (FileStream file = File.OpenWrite (fileName)) {
                int index = 0;
                long writed = 0;
                long length = Convert.ToInt64 (uint.MaxValue) + 1L;
                for (long i = 0; i < length; i++) {
                    byte[] data = new byte[elementSize];

                    if (elementSize == 8) {
                        if (primes.Numbers[i]) {
                            index++;
                            data = BitConverter.GetBytes (Convert.ToInt64 (index));
                        } else {
                            data = BitConverter.GetBytes (Convert.ToInt32 (-1));
                        }
                    } else if (elementSize == 4) {
                        if (primes.Numbers[i]) {
                            index++;
                            data = BitConverter.GetBytes (Convert.ToInt32 (index));
                        } else {
                            data = BitConverter.GetBytes (Convert.ToInt32 (-1));
                        }
                    } else if (elementSize == 2) {
                        if (primes.Numbers[i]) {
                            index++;
                            data = BitConverter.GetBytes (Convert.ToInt16 (index));
                        } else {
                            data = BitConverter.GetBytes (Convert.ToInt16 (-1));
                        }
                    } else if (elementSize == 1) {
                        if (primes.Numbers[i]) {
                            index++;
                            data = BitConverter.GetBytes (Convert.ToSByte (index));
                        } else {
                            data = BitConverter.GetBytes (Convert.ToSByte (-1));
                        }
                    }

                    file.Write (data, 0, elementSize);
                    writed++;

                    if (writed == 536870912L) {
                        file.Flush (true);
                        writed = 0;
                    }
                }
                file.Close ();
            }
        }

        public delegate void ProgressCallback (long position, long total);
        protected void copy (Stream inputStream, string outputFile, ProgressCallback progressCallback) {
            using (var outputStream = File.OpenWrite (outputFile)) {
                int writed = 0;
                const int bufferSize = 65536;
                while (inputStream.Position < inputStream.Length) {
                    byte[] data = new byte[bufferSize];
                    int amountRead = inputStream.Read (data, 0, bufferSize);
                    outputStream.Write (data, 0, amountRead);

                    writed++;

                    if (progressCallback != null)
                        progressCallback (inputStream.Position, inputStream.Length);

                    if (writed == 32768) {
                        outputStream.Flush (true);
                        writed = 0;
                    }
                }
                outputStream.Flush (true);
            }
        }

        protected void saveToTextFile (string fileName) {
            Console.WriteLine ("Saving primes to text file...");
            using (System.IO.StreamWriter file =
                new System.IO.StreamWriter (fileName)) {
                long writed = 0;
                foreach (var prime in this) {
                    file.WriteLine (prime.ToString ());

                    if (writed == 536870912L) {
                        file.Flush ();
                        writed = 0;
                    }
                }

                file.Close ();
            }
        }

        private static DateTime startTime;
        private static TimeSpan calculateTime;
        public TimeSpan CalculateTime { get { return calculateTime; } }
        public long DivisibleBy { get; set; }
        public long Length { get { return limit; } }
        public MyBitArray Numbers { get { return numbers; } }
    }

    public class MyBitArray : IDisposable {
        byte[] bytes;
        public MyBitArray (long limit, bool defaultValue = false) {
            long byteCount = Convert.ToInt64 ((limit >> 3) + 1);
            this.bytes = new byte[byteCount];
            for (long i = 0; i < byteCount; i++) {
                bytes[i] = (defaultValue == true ? (byte) 0xFF : (byte) 0x00);
            }
            this.limit = limit;
        }

        public MyBitArray (long limit, byte[] bytes) {
            this.limit = limit;
            this.bytes = bytes;
        }

        public bool this [long index] {
            get {
                return getValue (index);
            }
            set {
                setValue (index, value);
            }
        }

        bool getValue (long index) {
            if (index < 8) {
                return getBit (bytes[0], (byte) index);
            }

            long byteIndex = (index & 7) == 0 ? ((index >> 3) - 1) : index >> 3;
            byte bitIndex = (byte) (index & 7);
            return getBit (bytes[byteIndex], bitIndex);
        }
        void setValue (long index, bool value) {
            if (index < 8) {
                bytes[0] = setBit (bytes[0], (byte) index, value);
                return;
            }

            long byteIndex = (index & 7) == 0 ? (index >> 3) - 1 : index >> 3;
            byte bitIndex = (byte) (index & 7);

            bool old = getBit (bytes[byteIndex], bitIndex);

            bytes[byteIndex] = setBit (bytes[byteIndex], bitIndex, value);
        }

        bool getBit (byte byt, byte index) {
            return ((byt & (1 << index)) >> index) == 1;
        }

        byte setBit (byte byt, byte index, bool value) {
            return (byte) ((byt & ~(1 << index)) + (value ? 1 << index : 0));
        }

        public void Dispose () {
            GC.Collect (2, GCCollectionMode.Optimized);
        }

        private long limit;
        public long Limit { get { return limit; } }
        public byte[] Bytes { get { return this.bytes; } }
    }

    public enum SaveOptions {
        All,
        TextFile,
        BinaryAllNumbersBitArray,
        BinaryPrimeList,
        BinaryAllNumbersAndPrimeIndex
    }
}

Answer 2

一种高效实用的32位素数压缩方法是使用简单的8位字节存储连续素数之间减半的差值（并在需要时从稀薄的空气中提取素数2）。通过一点索引魔术，这提供了超快的“解压”——即，当需要在素数范围上迭代时，它是一种理想的表示形式，因为它比普通素数使用更少的内存。

低于2^32的203280220奇数素数需要相应的字节数，即小于194 MB的位。字节大小减半的差异的可用性扩展到304599508537（大约2^38），但从那以后，有必要发明一种方案来编码大于510的偶然间隙。然而，当存储间隙索引而不是将间隙宽度减半时，该方案几乎可以永远持续下去（参见Prime gap article@Wikipedia）。

这些连续差异块可以使用常用的zlib stile压缩或类似压缩进行进一步压缩，在这种情况下，压缩效果比压缩压缩的仅占优势的位图或mod 30轮子时更好。这可以用作磁盘上的压缩表示。

然而，请注意，一个mod 30轮子只需要136 MB，而且它是可直接索引的，就像满足素性查询一样。提取（解码）素数范围比delta编码的素数慢很多，但仍然比重新筛选素数快。因此，使用mod 30 wheel存储素数是“压缩”素数的最有效方法之一，可以使素数直接可用。

混合形式也可以非常成功。例如，当从mod 30轮解码质数时，您可以直接以增量编码形式存储它们，而无需将它们具体化为数字向量。这可以被视为一种重新压缩的形式。mod 30轮将是磁盘和主存储器格式，增量编码将是某些查询结果的交换格式。

增量编码和轮式存储有一个重要的优点：它们的存储需求基本上独立于所表示素数的大小。相反，如果将素数存储为数字，则会得到对数增长的存储需求。一、 64位素数占用的空间是16位素数的四倍。

关于质数轮的解释可以在维基百科文章Wheel Factoriation中找到。

下表显示了当向轮子添加越来越多的素数时所得到的空间减少，这两种素数都是相对于未翻转表示（“比率”）和相对于前一步（“增量”）。“辐条”列给出了每个车轮旋转的潜在主要轴承辐条（残余物）的数量，这让您了解了优化、完全展开实现的复杂性——la Kim Walisch的primesieve。正如你所见，在复杂性爆炸的同时，收益正在迅速减少。

wheel mod 2（也称为概率筛）很重要，因为它几乎不需要任何代码复杂度方面的成本，就能为您带来最大的成功。当操作赔率筛选时，mod 3车轮的大部分速度优势几乎可以通过手动技巧（索引技巧）轻松获得。wheel mod 30很重要，因为它在代码复杂度和加速之间提供了良好的平衡，这使其成为优化实现的理想目标。高达mod 30030的控制盘已在实际实施中使用，但与mod 30控制盘相比，增益实际上可以忽略不计，而增加的复杂性和性能损失则没有。在大学校园中，在特殊项目的背景下，甚至可以看到更高阶的轮子。

金·瓦利什（Kim Walisch）的筛子程序在网络上任何地方都是最快的，原因之一是他实现了mod 30车轮8个可能跨步序列中每个序列的展开版本，每个序列的8个可能阶段中的每个都有特定的回路入口点。所有这些都是用唯一一种语言（C/C）实现的，您可以获得真正名副其实的优化编译器。

对车轮mod 210的48个残基做同样的事情将意味着36倍的代码（！），而位图大小的减少可以忽略不计。但是，mod 210和mod 2310可能是代码生成器（C/C代码或. NET IL）的有前途的目标，如果您有几个月的空闲时间可以燃烧的话。