compression - 线性四叉树是存储网格划分数据最有效的方式吗

Question

假设您有一个 32x32 网格，可以使用以下任何 block 大小随机分割:

32x32、16x16、8x8、4x4

网格被分割的次数以及分割的方式是随机确定的。

从视觉上看，它可能看起来像这样:

这种类型的数据可以使用 quad tree 来表示。

我的问题是:

如果我尝试使用尽可能少的字节来表示上图，线性四叉树是否是最有效的方法？

我能想到的唯一其他选择是制作图表的所有可能组合，并使用单个数字来表示每个组合。

因此，对于该图，有 4 个分支级别(32x32、16x16、8x8、4x4)，这将为我们提供 4^0 + 4^1 + 4^2 + 4^3 种可能的组合，等于 85 种组合。

因此，我能想到的存储图表的最小方法是使用 7 位(1010101 是二进制数 85)来表示可能的组合。

会Linear Quadtrees在存储效率方面等于这个，还是会占用更多或更少的空间？

Answer 1

我通常不会回答我自己的问题，但看到这个问题仍然没有得到回应，我会给出我的答案。

经过近 2 天的研究，我现在更好地了解了线性四叉树是什么。

线性四叉树只是以特定遍历顺序编写的四叉树的数组表示形式。

基本上只需选择要读取四叉树的特定“顺序”并按该顺序保存其值即可。

例如，在问题中使用的图表中，有 4 个堆栈级别，因为有 4 个 block 大小(32、16、8、4)。

每个堆栈都可以按顺序读取。

因此，假设整个图充满了 32x32 block ，树的“根”(我们读取的第一个节点)将填充“1”，以表示我们需要该 block ，而根的所有子节点将为“0”，因为图形已满，不再需要 block 。

所以线性四叉树在二进制中看起来像这样“10000000000000....(84个0)”

这显然比我在问题中提到的 7 位多，但那是因为没有对该线性四叉树应用压缩。

我确实问错问题了。您需要线性四叉树来表示四叉树，所以我真的应该被问“压缩线性四叉树的最佳方法是什么”，而我在问题中给出的想法是最好的方法。

使用所有不同的四叉树组合创建一个查找表，并使用数字代表每个组合。