简介用于模板参数的 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 年的论文“一种构造最小冗余代码的方法”中。哈夫曼算法的输出可以显示为用于编码源符号（例如文件中的字符）的可变长度代码表。该算法根据估计概率或……从……创建此表阅读更多

在虚拟树中，一些边被视为实线，一些被视为虚线。通常的伸展仅在实线树中执行。要在虚拟树中的节点 y 上进行伸展，请实现以下方法。该算法查看树三次，每次查看一次，并对其进行更改。在第一遍中，仅通过在实线树中伸展，从节点 y 开始，从 y 到整个树根的路径变为虚线。通过拼接创建此路径实线。现在，在节点 y 上进行最终伸展将使 y 成为树的根……阅读更多

对于给定的森林，我们创建一些给定的边“虚线”，其余的边保持实线。每个非叶节点都只与一条到其一个子节点的“实线”边关联。所有其他子节点都将借助虚线连接。更具体地说，在任何给定的树中，最右边的链接（到其子节点）应保持实线，而所有其他到其其他子节点的链接都创建为“虚线”。结果，树将被分解成一系列实线路径。实线路径的根将连接到其他……阅读更多