BETHASH官方网站

　　to9o年 1月 重 厌 大 学 学 报 Vo】．1 3，№．1 第t 3卷第 l期 OURNAL OF CHONGQING UNIVERSI[ Y Jan．1990 数据压缩的hash方法 DATA COMPRESS[ON WITH HASH CODES 谭 强 孵 Tan Qiangmin (计算机系) 摘 要 在数据库应用中常要求教据压缩存贮。所采用的压缩方Ij丢应当有较小 的系统开销和期望的压缩效呆。文章给出了一种用其hash函数值作为编鸡来取代截 据本身以溅少文件的数据存 量的压缩方法。该方法对许多应用都有较好莳压缩放 果，并其编码／解码的成本1 为对hash表一次查找或直接访问的开销。文章也讨论 了hash 鸹数据压缩方法的买现技术，以及编码和解码的算法。 主题词 数据库：数播 压缩：数据存储；文件系统；算法；编码／文件结构 中国图书资料分类法分类号TP~P2 ABSTR~CS In many database applications，data have to be compresag before they can Ice stored Data comprmsion techniques with less overhead and better《m∞ saving are expected This paper gives a data compression technique b， which tb ． size of a file may be reduced tit【ough substituting codes for its field values The ． codes are the corresponding locations of the values in the hash table that is compri+ sed of a1】the values of the fieldThe comptes~ion is effective for many applications ． 。 and the CoSt of the codingdecoding is equal to that of one access to the hash tab． ． 1e The implementation of the technique as a compression tool in DBMS for幽la ． storage and the algorithms ot the coding／decoding are discussed． SUBJECT W ORDS data lib*aries data comp ression；data storage：fil七 syste- ms：algoritl?m：codisg／tilc 一 、 引 言 多微机数楷系统，其数批的存贮量往往超过计算机有限的存贮空间(硬盘)。解决这 一 问题可柑 F纠帕途静： ’ 合理的数据库设计，减少数 采。 一j ’ j日 废 大 学 学 报 990年 - 把不常用的数据脱机。例如保存 磁带上，在要求使甩时才装入。 · 增加新的硬盘。 一 要用数据压缩技术。 考虑使用何种途径来解决存贮空间不足的问题应视具体的对象丽定。但列数据进行压缩存贮 无疑是优先选择的 既经跻又有效的一种途径。 数据压缩的方法多种多样，但基本上都是利用数据的重复特征进行压缩 】 压缩的效 果与特定的应用有关，并且对系统效率的影响也备有不同。一般地，无论采用何种压缩技术 ， 系统效率的降低是不可避免的 设 是系统允许的最大响应时间， o是期望的数据压缩 (允许数据存贮的空间与数据存贮量之比)，那么，所选用的数据压缩技术应满足 其数据 压缩率a《po，并且压缩后系统的响应时间I．≤I．。。如果数据压缩不能满足这一要求，就只有 另辟途径。 下列的情况是数据库应用常见的。设置是一数据库文件(关系)，其记录数为N，有选 样的域(属性)满足域长Z3．域值个数 Ⅳ。显然，该域的值在足中有多次重复，可 以对它们进行某种编码(编码眭z)，然后用这些编码替换对应的域值，以获得对足的压 缩存贮．对确 编码存贮应对用户透明，用户在使用日时不应感到有任何编码的存在．因此，除 了对存贮教据进行编码外，在输出时还应做解码，即把编码转换成原有的数据形式．无论编码 和解码都会 生系统额外的开销，增加系统的响应时间。对文件压缩存贮所获得的好处能否抵 偿由此而引起的系统效率的F降，压缩后系统的响应时间是否超过允许的限度——这成为系 统设计者决定对数据进行压缩存贮时先要考虑的问题。以前许多数据压缩方法都是利用数据 本身的重复性进行压缩，而很少考虑许多应用中数据之间存在着大量重复这一事实r ． 本文所提出的方法对文件中数据大量重复的域进行压缩，并采用hash表技术进行编码和解 码．是一种有效简单而应用面较广的数摒压缩方法。Hash编码压缩的基本思想是把文件中要 压缩的属性值散入一hash表中，剐它们在该表中的存放位置作为对应的编码。去取代文件中 枢应数据的存在 作者在文章中讨论了该方法在数据库系统中的实现技术以及编码和解码的 算法，并且分析了它的压缩效果及其对系统响应时间瞬影响。 =、压 缩 方 法 设有一有限集合z．I』z}l一Ⅳ，^是z到整数集合[1：村]上的hashN数，E 1：村)是一存贮 空间，将每个x6 Z按下列方法存贮后 在日中的位置称为x~hash编码。 国 计算 =^( )． ∈[j：埘] ② 若日 )为空，则日 )0 否则在日中任找一空单元其位置为m．日(m)0 。 我们把已存入了Z的存贮空间圩称为在Z上的hash表。显然，在日中．每个 都有唯一确 定的位置．而每个位置也有一对应的 亦即存在一个由hash表日确定的由z列[1： ]的置 2… … h )，这里 ，是 在口中的位置或l-thash编码．我们记≈一 ( )为 在日 2 … … 上编码，而 = )=日( )为 在日J：解码。 一 般的， 对Z是不唯一的，随着生成 hash表时取 的顺序不同而变化 ，并且^(砷 第1期 谭强明：数据压缩的hash编码方法 l l (砷。但若h(x)在[1： ]上均匀分布，~ll h(x)为z到[1：M]的一一对应函数，则有唯一的 ， 并且 ( )=h( )。 设数据文件R的域f．的域值空间为z ，H 是z 依赖于hash函数^的hash表。 为由盯 确定 的z 到[1： ]的置换，将 的辞个值磷}换成 ( 1的过程，称为对R在f 上的hash编码压缩。 堆缩后的数据文件R，记为 ．(20 压缩后的域f， 记为 ( ；)，其域值空间为[1,M3。对 多个 域进行hash编码压缩是可能的，同样有 ’一 ’ ． ： R，= cR)= 1( 2( 3… ^(R1-”)) 称为对R的hash编码压缩 三、压 缩 _ ≈≥、 誊 讨论用hash编码对数据压缩存贮的效果，我们有如下的定义： 期望压缩率 o 。一五／s 、 一 这里S 是文件 的数据量(byte)，K是期望R存贮的空间大小。在要求数据压缩的场合．有 0 0l，1《S ． 实际压缩率 ，口=S ( 】／s ． 、 这里s ㈣是对硎玉缩后数据的存贮量，它等于 t )的大小与所增加的hash表大小之和。 与 。之间关系为 盯0。 对域 -的压缩率口 ， 。= ．㈨／s 这里s ㈨是对在f 上压缩后的数据存贮量。存f 上进行有效的数据压缩要求 l。 设 瀚域长为 ，? 为， 值的平均长度，P为编码长度，Ⅳ为Rig录的总数， i为，衙；同域 值的个数，工为每个记录 长鏖，显然 ’ _ l ± =-～ + ． ． ． 、 。 。 、 一 - ． 要使 l。则有下列不等式成立： ， ’ ． ． ’ M}／ lt_二P _Ⅳ… 一 ． 一 般有 f =， ，使得(f ～P)／f 1，因此 。Ⅳ就有 1。若f{2t。既使 ；=N时。也 有 f1。 对于 ，当N《 i并且Lf 时，cQ近似有 一 -一 = 因此，在Ⅳ《 和L 时， 仅与 相关(假定L不变)，即“越大，压缩效果越好． 下面分析 与 的关}，设对R的 个域进行了hash编码压缩，因此有 重 庆 大 学 学 报 l990罐 - ^ ∑N(L—I +p)+∑M 一( —I)NL tII l-J ～ 一 一 一 ～ ～ … 一 一 ∑ ±世丑 ． ∑… a ∑a。一 + 叮O + L^ 要求 ，就有 四、压 缩 的 实 现 (一)Hash囊存贮结构 在使甩了ha 编码压缩技术的系统中，ha8h表作为相联数据文件曲一部分，也应作为一 磁盘文件来存贮．由于操作系统访盘时间远大于内存数据的存取时间，因此，评价文件的访 _阿授率将以访盘的扶数为标准。考虑到操作系统读写文件的特点，hash表的文件缮构捌图1 所示．文件分为G个组，每个组又由 个块组成(块的尺寸为操作系统一个磁盘读写块的尺 寸)。Hash函数把每个压缩数据棚 射到唯一的组；在每个组内。州哽序存放。当一个组存满 之后，文件在自由存贮区获取一滥出组．并把放入这个溢出组内．文件中每个组最后两字节 g～，{r作为指瞰溢出组的指针。 Hash表可具有定长记录和变长记录两种格式。变长记录除了存放昝 身外，前面还加一 记录长度域．变长记录hash表对于压缩属性值长度变化范围大的域十分有效． ． ：： 记录1记录2 E = 圈l Hash袭文件罐构 (=)■码算码算法 ’ 如此实现的hash表文件结构决定了 的ha 编码是～二元组( )．其中g是枷 在的组 e是其为凌组的第n几个记录 对 编码即找司 hash表的位置( ， )，其算法如下。 CODING(x．g，e) 第i期 傅强明：数 压缩翦 hash编码方法 1 23 (1)g一 ( )， 1。 (2)置读指针到第g组。 (3)读一记录 ．如果有0= ，返回(g， )退出 (4)如果为空，若ha sh表为变长记录格式，计算 的长度，形成 的壁长记录写入；否则 以 为一定长记录写入 返回(g， )退出。 t 5)若当前组读完，如果溢出组指针g～ t r为空，由自由存贮区取一溢出组．置g和g一 r为溢出组的组号；否则，即g—p r存在，置g=g— r，e=0，并置读指针到第 g组。 (6) = +1．转(3)。 对 的解码即由其hash编码(g， )查找 ，其算法为： 、 DECOING(x，g， ) ． (1)如果为定长记录则直接置读指针到第g组的第8个记录处；否则 (2)若。=1，重复做：读记录长度，由此置读指针剥下一记录并且 = —l。 (3)读记录 。 删除hash表中的记录将使同～组或相连溢出组在该记录后面的所有记录向前移动。下面 日 是按编码删除 的算法； DELETE(g，e1 (i)执行DECODING( ，g，e)获得 和 记录开始位置B。 (2)重复做：清空B开始的记录 置读指针五一B+当前记录长度并读丑开始的记录为 新的当前记录。若当前记录为空则退出，否则写到B．置B= 。任何时惺若组结束出 现，置读指针到g～ 指向的组。 删除 将使hash表中 以后记录位置均产生改变，亦即它们~Jhash编码发生改变。为了保 证数据的正确性，必须对与hasj 表相联的数据文件中对应的hash编码做相应的修改． 由于对数据文件修改可能将耗费大量的开销，在删除ha sh表中的记录时可以考虑不做移 动，而只在被删除的记录上做一删除标志。这样，只需在—定的时间后重组hash表。便可减 少大量的对相联数据文件修改的开销 设hash表中每个组的平均记录数为卢，那么由前面给出的算法可蜘，对于编码读写记录 的平均次数为 ( +1)；解码定长记录为1，变长记录为{t芦+1)。删除将有卢次读记录和 ‘ - 平均 十1)次写(没有考虑对相联数据文件的改动)。如泉烈滁不做记录移动，贼该操作 的平均读写记录的次数只为解码的读写次数加i。~hash表中某个记录的修改由嬲除被修改 记录DELETE(g， )和编码修改值CODING(x，g， )组成 。其平均读写记录的次数等子删 除和编码读写次数之和 (三)实现方法 在数据库管理系统中实现ha出编码压缩技术很简单，在操作系统和数据库管理系缠 问 2所示。该介可的功能是完成对由数据库读出数据的解码，以 D 明的，并不引起任何用户应用程序的改变。因 施加在压缩文 重 庆 大 学 学 报 1990年 件 (月)上的任何操作在解码／编码后，完 全与施加在未压缩文件五上相同。Hash编 码压缩技术在数据库管理系统中实现，将 使该管理系统增加数据压缩的功能。下列 曲命令提供用户压缩数据．以及维护hash 表使用。 ～ ^ (文件 )，属性名 )，(hash 表名)．G， ．格式 )，选择)， (装入内存){，自编hash函数入 口)) 对文件的指定属性进行数据压缩。这 里hash表名)是生成hash表的文件名． 图2 Hash编码压缩在数据库管理系统中实现 G是hash表的组划分数，冒是每组块数． 格式)说明hash表是定长或是变长记录。(选择)给出是否打印输出hash表 中记录的分 布、空间的利用率等信息。(装入内存)规定是否在读写联数据文件时把整个hash表放入内 存。 茸编hash~]数入口)可缺省，缺省由系统定义的hash~数计算。 ins一^ hash表名 )，(值串) 在hash表中增加数据。 d一 (hash表名)，(值 )，(修改值 ) 把hash：~：中的值 )修改成 (修改值 )． clr一^ 文件名 )，(属性名)，选择 ) 对压缩属性进行清理。去掉相联hash表中无用的数据。选择)说明是否打印输出has“ 表中记录的分布、空间的利用率等信息。 res hf文件名)，属性名 ) 恢复对属性的压缩，去掉与 (属性名)相联的hash表文件 五、对系统效率的影响 设在数据文件五上的 个域进行Thash编码压缩。压缩后的数据文件 ( )每个记录的平均 访盘次数． L一∑(?，一P) ‘ +∑ i．I 这里(L～∑(f，一P))／B为访问 ( )本身每个记录的平均访盘次数 c为对，艟编码■ ／ t-I 码的平均访盘次数，B为一个磁盘读写块的大小。由于对未压缩文件的每个记录平 数为 B，故压缩盾所增加的系统开销为， 第 1期 谭强明：数挠 压缩的hash编码方法 1 2 5 — — — — — — — — — — — — — — — 一 — — — — — — — — — — — — — — — — — — — — — — — — — — — ～ — — — ：；；i Au=∑( 一(f 一P)／B) (2) 由上式可知，要减少 ．须减少 ，即提高对hash表记录的平均访问速度，或减少对hash表 记录的平均读盘次数 要做到邀～点，除了正确地选择h(引使， 上的域值在hash寝中均匀分 布之外．还须在建5~．hash表时，适当地选择文件的组数G和每个组的块鼓嚣，使得既不浪费 存贮空间．又使每个组的记录所占的平均块数尽量少。因此，设 为与， 相联的hash表每个 组的平均记录数 8i=MtfGi 在选择G 和置t耐须要遵循下列建议 · 使G ≤ ．即卢。≥l，因为每个记录只能装在一个组内，G，尬则浪费空间。 · 嚣．尽可能为1，并且使每组记录的平均长度卢， 尽量为B的整倍数五；。这里_在定长 记录hash表中为，·的域长，在变长记录hash表中为，t值的平均长度， ≤l“ · Gt最好为质数．并且不为2和5的倍数。因为太多悄况下hash~数均以G 作除取余。 在hash表的每个组中．记录所占的平均块数为 ·f ／ 。记 一 【 ／ ． ]表示 取不小于f，(平均每个hash表记录所占的磁盘块数)的最小整数。由于编码在组内顺序查 找，故编码时平均访盘次数 为 w 一 一盟掌 (3) 解码若定长格式为一次直接访问，故其 为 、 ， ≥B 一 { 1 ～ (4) 1一去 f B 若变长格式解码为组内顺序查找．故其 i为 ／3+ 一 fld, 一 ～ n· (5) _I 采用定长记录hash表对文件进行hash编码压缩一般有△uo(例外的情况是对G·很小的 定长记录hash表解码)。因为一般有 最小为1，要使△。≤0，至少要使 ≤(f 一p)／B，印 f，≥B+P。由此有f B，并且 =2(f{=ft)。另一方面， =1，只有( ft／B+n )／2崔1． 由此可得出 +22．这是不可能的。同理可推断在 l时均有AuO． 嗣变长记录hash表压缩文件有可能使△uo 例如，当 一1时，f·≤(2( ～P)～B)／芦 就可使Au0。在这种情况下 ， 的域长f．将远大于，。值的平均长度 。例如．若 =300，P=3． B一 51 2， 角=2，Ⅲ ≤41． 另一种减少△ 开销的方法是在hash~ dx并且内存有足够的空时把整个hash表一次装入 内存。在频繁访闯数据文件时这种方法可大大降低访问成本． 重 庆 大 学 学 报 l 99 0年 六、结 论 Hash缔码数括压缩是采用文件的域值在hash表屿位置对文件进行编码压缩来减少存贮量 的一种方法。压缩与数摧值奉身曲特征无关，因此这种方法可以为数据库系统的一种通用的 压缩数据存贮的工具 Ha sh辅 缩在文件域长f，较大，并且文件的总记录数Ⅳ大于域值个 数 时，或者域长 f 大于其值的平均长爱 压缩效果较好 并且所增加的系统开销也较 小 其一次编码或锵码的成本为一捩hash查找或一次直接访问的开销。 实际实现的hash表按组划分 每个组由若干班组成．组的戈4分G和每组块数丑的选择直接 影响压缩效果和系统效率。选择G和E必须遵循一定的原则使得既获得满意的压缩效果又具 有较低的解码编码时间。用户也可 通过列／t~hash表中记录分布 及空间利用率等信息，随 时修改G和日，或把hash表装入内存来改进效率 除在数据库系统中使用设方法来压缩数据的存贮外，在一般