一種產生最佳化赫序函數的學習演算法

Abstract

當我們使用電腦時，如何儲存資訊，並能有效取用是一重要的典型課題。一般而言， 每筆資料可區分為鍵值(key) 與資料兩部份，只要給定鍵值就能從一群資料中取出所 要的一筆。在擷取資料的方法中，赫序(hashing) 是最常被使用的技術之一。傳統的 赫序方法要找出最佳化赫序函數(minimal perfect hashing function)必需先分析鍵 值的特性，再經由一些繁瑣的步驟才得出所要的赫序函數，但是要分析鍵值的特性並 不容易，本文即使用類神經網路(artificial neural network) 中的學習(learning) 演算法，經由學習範例(training example)建立輸入(key) 對應輸出(address) 的函 數，而導出另一種型態的最佳化赫序函數，即函數的功能就架構在神經元(cell)與神 經元間的連接(connection)鏈上。 類神經網路的應用包羅萬象，不勝枚舉，本文利用第三節所提的具功能連結的認知機 演算法，用以產生不同鍵值集所須的最佳赫序函數效果不錯。應用PASCAL語言中三十 六個保留字與四十個識別字的實例，充分說明本文所提演算法的：(1) 無需分析鍵值 集的特性(2) 不限制鍵值集大小的通用性(3) 純粹只是加減運算的簡單性。