画布{最大宽度：100%；边距：3px auto；显示：块；}细胞自动机是相当酷的东西玩。有很多很多的变体，比如康威的《生命游戏》（Game of Life）、阿贝尔（Abelian）的沙堆（Abelian Sandpilles）、兰顿的循环（Loops）和布莱恩的大脑（Brian's Brain），但在这篇博文中，我将只谈最简单的细胞自动机：一维细胞自动机自动售货机最简单的一维元胞自动机称为基本元胞自动机。它们对一系列的细胞起作用，每个细胞都有两种可能的状态：开和关，或者1和0。从初始序列开始，根据简单规则计算下一个序列：单元的下一个状态只取决于单元本身及其两个的当前状态邻居。为了例如，这里有一个叫做"规则22"的基本元胞自动机：在这个自动机中，一个单元是"开"的，如果在上一代中，正好是其中的一个三个电池是开着的，否则就是"关"。规则可以使用由stephenwolfram引入的Wolfram代码来描述。在基本元胞自动机的情况下，给定单元及其相邻单元只有8=23个可能的配置，并且对于每个配置，对于最终的新状态只有两个选项，因此有256=28个不同的基本CA，并且可以使用8位数字来描述它们。因此，上面图表的规则可以用二进制数00010110来描述，或者用十进制表示法：22。网络研讨会你可以将一维细胞自动机（CA）的演化绘制为二维图像，从顶部的一些初始单元格行开始，然后在其下方的行中绘制越来越多的代。对于规则22，如果在第一行中仅从一个黑色单元格开始，则在512代之后将得到以下图像：有趣的是，得到的图像看起来很像Sierpinski三角形。事实上，一些基本的CA看起来像这样。这是分形的一个最简单的例子：图像在不同的秤。压缩CA-images您可能会认为，一个由如此简单的规则生成的具有如此多重复结构的图像必须压缩得非常好。确实如此。但这取决于形象格式.As一个JPEG，上面的图像压缩得不是很好：它重79KB，质量为90，这甚至不是无损的。即使在可能的最低质量下，它仍然是16KB，并且在这个质量设置下，压缩伪影相当多坏：作为但是，图像只有3.4kb，这是无损的。因此，选择正确的格式确实非常重要。如果你使用的是Cloudinary，你不必担心这个问题：只要使用f_auto，qu auto（阅读更多），你就会自动获得最合适的图像格式和质量设置，在这种情况下，这将是一个无损的巴布亚新几内亚在这个例子中，PNG的性能非常好，因为图像中有很多精确的重复。PNG是基于DEFLATE算法的，它用反向引用替换这些精确的副本，节省了大量的数据字节。但是，并不是所有的细胞自动机都能产生如此容易压缩、重复的模式。规则30例如，规则30从单个黑色单元格开始生成以下图像：这张图片重215kb，质量为90jpeg，作为PNG，它仍然是24kb，而Sierpinski三角形图像（规则22）的相同尺寸为3.4kb，这是相当大的跳吧。那个规则30创建的模式很有趣：在左边它是重复的，但是在右边，它变得更加混乱。三角形结构出现了，但它们的位置似乎是随机的。有趣的是，在自然界中，似乎有一些过程会导致类似的图案，比如在这种Conus纺织的海蜗牛壳上：（图片版权（c）2005 Richard Ling，CC-BY-SA 3.0）如果我们可以学习规则呢？PNG对于重复的图像表现得很好，比如规则22，因为它"看到"了重复，并对其进行了有效的编码。但它并没有"看到"元胞自动机的基本规则，所以如果这些规则导致混乱的突发行为，它就会陷入麻烦。GIF和无损WebP也是如此好吧。但是如果我告诉你有一种图像格式，它基本上可以"学习规则"，并很好地压缩图像，而不管这些规则实际上会导致什么结果呢？好吧，FLIF的疯狂熵编码就可以做到这一点。它可以构造一个与基本CA规则完全对应的MANIAC树，确保8个规则配置中的每一个都对应于算术编码器的不同上下文。然后在这些上下文中的概率将迅速收敛到非常接近0或1的值，并且编码的比特将接近于零成本。为例如，rule22图像作为PNG文件是3.4kb，而FLIF文件只有83个字节。规则30的图像是24 KB的PNG格式，而作为飞入事实上，上面的两个CA图像（如果启用了javascript）实际上是FLIF文件，在浏览器中使用一个名为PolyFLIF的javascript polyfill进行解码编码器：flif-NX1选项-N使编码器使用格式的非交错变体，因此编码是自上而下的，就像自动机的进化一样。默认情况下是进行隔行扫描，这意味着编码器无法"看到"结构，因为它正在对图像中的所有像素进行编码，从而导致更糟糕的压缩效果。选项-X1就不那么重要了；它允许算术编码器使用更多的极端机会（1/4096，而不是默认的2/4096），使比特的"接近零"成本更加接近零。大一点更大的imagesHere是22号规则图像文件大小的动画图，有越来越多的行，使用不同的图像压缩格式。注意：这里的y轴是对数！绘图规则22如果你想要一个更极端的例子，这里有一个FLIF文件，其中包含一个5000万像素的rule30进化（5000行）图像。以下是特定图像的文件大小：飞行2686字节巴布亚新几内亚2001971字节无损WebP1967008字节有损WebP，默认质量14240092字节有损WebP，最低质量5985102字节JPEG，质量9020300915字节JPEG，最低质量4243508字节令人惊讶的是，有损格式在这张图片上的表现有多差，不是吗？还有一点很有趣，PNG和无损WebP非常接近，如果你知道它们基于相似的熵编码方法，这并不奇怪，但仍然如此。然而，对我来说（作为FLIF的作者），上表最好的地方是FLIF比其他任何东西都高出几个数量级：）。现在，你当然不应该从这样的事情中得出太多的结论。这是一个非常特殊的图像，因为它代表了FLIF的最佳情况，而它与其他格式的最坏情况非常接近。如果使用PNG或WebP来实现图像转换和压缩效果非常好，但在压缩方面却很差，这并不难飞。更多复杂元胞自动机可以学习所有基本的元胞自动机，但也可以处理一些更复杂的元胞自动机。例如，如果允许单元的下一个状态不仅取决于单元及其相邻单元的当前状态，而且还取决于单元的前一个状态，则可以得到一种稍微不同的元胞自动机，它可以生成如下图像：在这里，我随机初始化了第一行，所以FLIF文件稍微大一些：第一个图像269个字节，第二个图像240个字节。对应的PNG文件是16kb和32kb总KB细胞自动机没有理由只使用两种颜色（或状态）。当使用更多的状态时，由于不同自动机的数量增长很快，所以要简洁地描述规则就变得有点棘手；只有3个状态，如果你只看单元格及其两个邻居，就有76250亿（327）个自动机，并且需要一个27位的三元数来描述他们。去简化事情，你可以看看全细胞自动机，它是这个巨大集合的一个子集。在一个总体CA中，新的状态只依赖于所考虑的当前状态的总和。这迫使某些对称性。例如，配置0,2,1必须产生与配置1,2,0或配置1,1,1相同的新状态。因此，你需要更少的数字来指定一个总体的CA。如果你有三个单元格状态，总和可以是0到6之间的任何值，并且对于这7个配置中的每一个，都有3个可能的新状态，因此7个三元数字就足够了，并且"只有"2187个总体3色自动机。一个其中有1599条规则，这是我最喜欢的极权主义CA。它看起来像这样：从一个"1"单元格开始，规则1599产生了这种复杂的模式，它持续了大约8000行，然后就停止了，只留下了一些重复模式的痕迹，大约700列宽，一直持续下去。这是一个899字节的FLIF文件，它对整个有趣的部分进行了编码，这是一个720x9000的图像，所以我不打算让你的浏览器解码给，拿着看看这个文件大小的动画图：绘图规则1599在这个图中，我将疯狂树学习迭代次数限制为一次。您可以看到，最初文件大小随着图像的增长而增长，而在FLIF完全"弄清楚"游戏规则之前似乎需要一些时间。文件大小实际上是在学习规则的过程中下降的，然后慢慢地又开始增加，以接近零的成本编码额外的像素。在3000行，FLIF文件仍然只有667字节，而WebP和PNG大约是140kb，而有损JPEG接近1结论一由此得出的明显结论是不要对元胞自动机的图像或一般的高度结构化的人工图像使用有损压缩。这不是什么新鲜事，但我认为上面的例子很好地说明了这一点很好。什么希望是新的