本页使用了标题或全文手工转换

用户:TNTErick/k Restriction/Generalized Hashing

来自维基学院
跳到导航 跳到搜索

前導[编辑 | 编辑源代码]

定理一[编辑 | 编辑源代码]

給定一有效可逼近的機率分布 及其於某個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