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

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

简介用于模板参数的HDS或半边数据结构（缩写为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年发表的论文“一种构建最小冗余码的方法”中发表。霍夫曼算法的输出可以显示为一个变长码表，用于对源符号（例如文件中的字符）进行编码。该算法根据估计的概率或……阅读更多