跳转到内容

User: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