使用消除運算法則及條件排列運算法則建立完全醢序函數

Abstract

在篇碩士論文中，首先我們將回顧過去文獻中對於完全醢序函數設計上的一些結果， 並將其歸納為兩類：類值計算法(Numerical Computation Method)與給值(Value Ass ignment Method )。接著，我們將提出一種新的醢序法，稱為「消除運算法則及條件 排列運算法則的完全醢序法」(Deletion-Conditional Permutation Perfect Hash Function Scheme)。 要建立這種新的完全醢序函數，其中包括兩個階段。在第一個階段中，我們依據每 一位元位置對方式對於分別關鍵集合中元素的能力，選出一組「非多餘位元集合」(n on-red-undant bits set) 。選出的方式，並不像一般做法中，必需測試所有位元位 置的組合。我們提出一個演算法則去處理「測試－消除－序列」(test-delete seque ce )以得到一個最小非多餘位集合。在此，許多有關「測試－消除－序列」的特性也 將逐一的提出來研討並證明。在第二階段中，我們將注意力完全放在「非多餘位元集 合」上。並且使用「條件排列」(Conditional Permutation ) 以改變關鍵集合的表示法而得到一些新的多餘位元。依此反覆第二階段，鍵碼的長度 將越來越小。最後，我們將以鍵碼在這些剩下位元位置上的值做為醢序值，以達到醢 序的目的。