廣義雜湊

本页使用了标题或全文手工转换
来自维基学院

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

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

给定一有效可逼近的几率分布 及其于某个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