本頁使用了標題或全文手工轉換

廣義雜湊

來自維基學院
跳至導覽 跳至搜尋

前導[編輯 | 編輯原始碼]

定理一[編輯 | 編輯原始碼]

給定一有效可逼近的機率分佈 及其於某個k-限 上的密度 ,並給出一個instance 以及精度參數 可以得到一個不大於的解,且時間複雜度是的多項式函數。

(第四章)

與asym. optimal errCrct. code的關係[編輯 | 編輯原始碼]

Alon1992 中指出的

定義[編輯 | 編輯原始碼]

  • 是一個具字母數為 的鍵集。
  • 任何子集皆被視為(n,M)-code (n 碼長、M項的編碼)。
  • code rate 編碼效率定義為
  • 一個編碼 codeword 字串 (中每一個的元素),其中第 i 個字母表示作
  • t-hashing:一個參數,當某個編碼 的任 個元素必存在一個位置 足以區別該 個元素,即是,此時稱該編碼是一個 t-雜湊函數。
  • (m,q,k)-perfect hash family是一群雜湊函數H

與 k限之間之關係[編輯 | 編輯原始碼]

(t,k)-hashing是一種k限問題。

雜湊函數可以被視為是一個字串對應到。 k個限制,此處

Parent Identifying Code[編輯 | 編輯原始碼]

定義如下:

  1. 一個(n,M)-code C的子集 X,給座標,有 n 個projection 就是每個x第 i位置的字元集合。
  2. X的envelope