使用质数进行压缩

Question

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

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

我们需要为每个字节创建一个使用位的映射，我们可以存储要压缩的数字，并将其添加到数据数组中。

这在一开始似乎是可行的，但会略微增加文件大小，但对于LZ4或哈夫曼等算法来说，会将文件压缩为可重新压缩的结构。

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

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

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

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

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

我想问你，我们可以用质数做的其他方法吗？因为获得质数非常容易，特别是对于小于2^32的数字。我们需要在我们的方法中添加质数方法。

Answer 1

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

小于2^32的203,280,220个奇素数需要相应的字节数，即小于194MB。字节大小减半的差异的可用性扩展到304,599,508,537 (大约2^38)，但从那时起，有必要发明一种编码大于510的偶发间隙的方案。然而，当存储间隙指数而不是减半的间隙宽度时，该方案几乎可以永远继续下去(参见Prime gap文章@维基百科)。

这些连续差异的块可以使用通常的zlib-stile压缩或类似方法进一步压缩，在这种情况下，您可以获得比压缩打包的odds-only位图或mod 30轮子更好的压缩效果。这可以用作紧凑的磁盘表示。

然而，请注意，mod 30轮子只需要136MB，并且它是可直接索引的，类似于满足素数查询。提取(解码)素数的范围比增量编码的素数慢得多，但仍然比重新筛选素数快。因此，使用mod 30轮存储素数是“压缩”素数的最有效方法之一，这种方法可以使素数直接可用/可用。

混合表单也可以相当成功。例如，当从mod 30轮解码素数时，您可以直接以增量编码的形式存储它们，而不是将它们物化为数字的向量。这可以看作是一种重新压缩的形式。mod 30轮将是盘上和主存储器格式，增量编码将是某些查询的结果的交换格式。

增量编码和轮式存储共享一个重要的优点:它们的存储需求基本上与所表示的素数的大小无关。相比之下，如果将素数存储为数字，则会得到对数增长的存储需求。即64位素数占用的空间是16位素数的四倍。

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

下表显示了将越来越多的质数添加到轮子上时，相对于无轮表示法(“ratio”)和相对于前一步(“delta”)的空间缩减。“辐条”一栏给出了每轮转动的潜在质数辐条(残留物)的数量，这让您可以像Kim Walisch的primesieve那样对优化的、完全展开的实现的复杂性有一个概念。正如您所看到的，收益正在迅速减少，而复杂性却在爆炸式增长。

​

​

轮子模块2-又名赔率-只有筛子-很重要，因为它给了你最大的冲击，几乎没有代码复杂性的成本。大多数mod 3轮子的速度优势几乎可以在操作只有赔率的筛子时通过巧妙的手法(索引技巧)轻松实现。轮子模块30很重要，因为它在代码复杂性和加速之间提供了很好的平衡，这使得它成为优化实现的理想目标。高达mod 30030的轮子已经在实际实现中使用，但与mod 30轮子相比，增益实际上可以忽略不计，而增加的复杂性和损失的性能则不是。在特殊项目的背景下，甚至在大学校园里也可以看到更高阶的轮子。

Kim Walisch的sieve程序是网络上最快的程序的原因之一是，他实现了mod 30车轮的8个可能的跨步序列中的每一个的展开版本，每个序列的8个可能的阶段中的每一个都有特定的循环入口点。所有这些都是在唯一一种语言(C/C++)中实现的，您可以获得名副其实的优化编译器。

对车轮mod 210的48个残留物做同样的事情将意味着36倍的代码(!)而位图大小的减小可以忽略不计。但是，如果您有几个月的空闲时间，mod 210和mod 2310可能是代码生成器(C/C++代码或.NET IL)的理想目标。

Answer 2

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

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

循序渐进。首先，让我分享一下我们需要的Prime Helper代码。

如何在这些代码中提高findPrimes ()和saveToFile ()方法的效率？目前，在我的核心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
    }
}