基于子空间三角不等式的高维码字搜索算法

本文分析了码字搜索算法中基于均值、方差和范数的删除准则,指出基于方差和范数的删除准则之间存在冗余缺陷.在此基础上,提出了一种新的子空间三角不等式删除准则,根据子空间中码字与参考点之间的距离来排除候选码字.基于方差的删除准则可以看成是子空间三角不等式删除准则的特例.在新的删除准则中,通过选择合适的子空间参考点,能够排除更多的不匹配码字.在编码前,首先计算每个码字的哈德码变换,并且计算在子空间中码字与参考点之间的距离,然后根据各码字哈德码变换域的第一维系数对码字进行升序排列.在编码过程中,根据码字的均值来终止最近邻搜索过程,采用子空间三角不等式删除准则来排除不匹配码字.测试结果表明,本文算法的搜索时间快于其他码字搜索算法,其搜索时间比当前最快的哈德码变换域等均值等方差等范数搜索算法要快8%~26%左右.