四叉树是一种用于高效存储二维空间点数据的树。在这种树中，每个节点最多有四个子节点。我们可以通过以下步骤从二维区域构建四叉树：将当前二维空间划分为四个区域。如果一个区域包含一个或多个点，则构建一个子对象，其中存储该区域的二维空间。如果一个区域不包含任何点，则不为其构建子节点。对每个子节点执行递归操作。四叉树在图像压缩中得到应用，其中每个节点包含平均……阅读更多

范围树被定义为一种有序的树形数据结构，用于保存一系列点。它允许高效地检索给定范围内的所有点，通常在二维或更高维度中实现。它与 kd 树相同，只是查询时间更快 (O(logd n + k))，但存储空间更差 (O(n logd-1 n))，其中 d 表示空间的维度，n 表示树中点的数量，k 表示给定查询检索到的点的数量。范围树可以与区间树区分开来：不是……阅读更多

简介 用于模板参数的半边数据结构 (缩写为 HalfedgeDS) 被定义为一种以边为中心的数据结构，能够维护顶点、边和面的关联信息，例如平面图、多面体或嵌入在任意维度中的其他可定向二维曲面。每条边都被分成两个方向相反的半边。每个半边存储一个关联面和一个关联顶点。每个面和每个顶点都存储一个关联半边。半边数据结构的简化变体可以消除一些信息，例如面中的半边指针或面的存储……阅读更多

在计算几何中，平面直线图，简称 PSLG（或直线平面图，或平面直线图），被定义为在平面上嵌入平面图的术语，使得其边被映射到直线段。Fáry 定理 (1948) 的陈述是，每个平面图都有这种嵌入。在计算几何中，PSLG 通常被称为平面细分，假设或断言细分是多边形的。如果没有度数为 1 的顶点，PSLG 定义了平面细分为多边形区域，反之亦然。缺少……阅读更多

多元横截面数据（即不是时间序列或重复测量）由矩形数据表示，其中每列是一个变量（特征），每行是一个案例或记录。表示矩形数据的第一个过程是将其映射到更高维度的点数据，并使用基于点的数 据结构过程，例如网格文件、PR 四叉树、点四叉树和 k-d 树。将矩形数据映射到四维点的过程可以通过多种技术来执行，例如相对角的 x 和 y 坐标，或一个角的 x 和 y 坐标以及宽度和高度……阅读更多

桶排序构建哈希表，作为二维数组而不是一维数组。数组中的每个条目都很大，足以容纳 M 个项目（M 不是数据量。只是一个常数）。问题 会产生大量浪费的空间。如果超过 M，则需要实现另一种策略。对于基于内存的实现来说，性能不是很好，但如果桶是基于磁盘的，则可以实现。对于桶排序，λ>1是可以的。但是，λ越大，碰撞的可能性就越高。λ>1 保证至少会发生 1 次碰撞（鸽巢原理）。这将提高运行时间……阅读更多

寻找不等字母成本的最优前缀码的问题包括计算最小成本前缀码，其中编码字母表由不等成本（长度）字母组成，长度为 α 和 β，其中 α ≤ β。我们将自己限制在二叉树中。该代码由一棵倾斜树表示，类似于霍夫曼树表示霍夫曼编码问题的解。尽管有相似之处，但不等字母成本的情况比经典的霍夫曼问题困难得多；尽管存在……阅读更多

下面给出了高度限制或深度限制霍夫曼树的图表。树深度限制是一个非平凡问题，大多数现实世界的霍夫曼实现都必须处理这个问题。霍夫曼构造不限制高度或深度。如果限制了，它就不可能“最优”。当然，霍夫曼树的最大深度受斐波那契数列的限制，但这留下了比想要的更大的深度空间。限制霍夫曼树深度的理由是什么？快速霍夫曼解码器实现查找表。可以实现多个表级别来降低内存成本，但是非常快的……阅读更多

一个简单的算法 准备一个由 n 个初始霍夫曼树组成的集合，每个树都是一个单叶节点。根据权重（频率）将 n 棵树保留到优先队列中。删除或删除前两棵树（权重最小的两棵树）。组合这两棵树以创建一棵新树，其根与这两棵树作为子节点相关联，其权重是两个子树权重的总和。将这棵新树放入优先队列中。重复步骤 2-3，直到所有部分霍夫曼树都合并成一棵树为止。这是一个贪婪……阅读更多

霍夫曼编码 霍夫曼编码被定义为一种特殊的最佳前缀码，通常用于无损数据压缩。找到或实现这种代码的过程是通过霍夫曼编码进行的，这是一种由 David A. Huffman 在麻省理工学院攻读 Sc.D. 期间开发的算法，并在 1952 年的论文“一种构建最小冗余码的方法”中发表。霍夫曼算法的输出可以显示为用于编码源符号（例如文件中的字符）的可变长度代码表。该算法根据估计概率或……从……阅读更多