ABD技术及其在最优部分匹配检索算法设计中的应用

ABD TECHNIQUE AND ITS APPLICATION TO THE OPTIMAL PARTIAL-MATCH RETRIEVAL ALGORITHM DESIGN

组合Hash是一种对多重属性文件进行部分匹配检索的最优算法,而ABD(Associative Block Design即“相联区组设计”)技术乃是这种算法设计的关键。本文在D.Knuth,R.Rivest等人工作的基础上考察了ABD表的若干重要性质,提出了分级的概念,对相当大的一类ABD表给出了有效的构造方法。进而由于解决了与ABD表相一致的桶定位Hash变换问题,使得ABD技术在上述最优算法设计中的应用成为可能。文中分析表明这种组合Hash算法不仅具有最优的期望时间复杂性,而且其最坏情况时间特性也相当好。

Combinatorial hashing is one of the optimal partial-match retrieval algorithms for multi-attribute files, while ABD (Associative Block Design) technique is a key to the design of such an algorithm. In this paper some important properties of ABD tables are investigated, a concept distinguishing ABD tables into grades is suggested and an effkient construction method for a rather large class of ABD tables is given on the basis of studies by D. Knuth, R. Rivest et al. Furthermore it is possible to apply ABD technique to the aforementioned algorithm design, for the relative problem of bucket location hash transformation is solved. An analysis is made in this paper to demostrate that this kind of algorithm possesses not only an optimal expected time complexity, but also an excellent worst-case time behavior.