介绍用于模板参数的 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 成为树的根。…… 阅读更多

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