四叉樹是一種用於高效儲存二維空間中點資料的樹。在這棵樹中，每個節點最多有四個子節點。我們可以透過以下步驟從二維區域構建四叉樹：將當前二維空間劃分為四個盒子。如果一個盒子包含一個或多個點，則構建一個子物件，其中儲存盒子的二維空間。如果一個盒子不包含任何點，則不為其構建子節點。對每個子節點執行遞迴操作。四叉樹應用於影像壓縮，其中每個節點包含平均值……閱讀更多

範圍樹被定義為一種有序樹資料結構，用於儲存點列表。它允許高效地檢索給定範圍內的所有點，通常在二維或更高維度中實現。它與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年發表的論文“一種構建最小冗餘碼的方法”中發表。霍夫曼演算法的輸出可以顯示為一個變長碼錶，用於對源符號（例如檔案中的字元）進行編碼。該演算法根據估計的機率或……閱讀更多