XML关键字检索中Dewey码存储方式的研究

摘要

Dewey encoding is an important method used in XML keyword search. In the present research, Dewey codes are usually stored directly as a string, and the price of saving Dewey codes and calculating LCA is huge. This paper proposes a storage method called PSVL(Prefixes Sharing and Variable Length integer encoding) for Dewey codes. This method is based on variable length integer encoding and prefixes sharing method. Experimental results show that this storage method can notably reduce the storage cost of Dewey codes and improve LCA calculation of Dewey codes.%Dewey码是XML关键字检索中采用的重要编码方式.在目前的研究当中,Dewey码通常以字符形式进行存储,这种方式造成Dewey码存储代价过大,并且在LCA求解过程中也必须通过字符比较才能获得Dewey码各层的数值,影响LCA求解效率.提出采用前缀共享和变长整形编码思路的PSVL存储方式,在消除字符比较操作的同时减少了Dewey码集合的存储代价.实验证明利用该存储方式对Dewey码集合进行存储,可以有效地降低其存储代价,并且减少获取Dewey码各层数值这一步骤花费的时间,间接提高了LCA的求解效率.