伪随机序列投影三维测量中的快速子序列匹配

摘要

提出了一种适用于伪随机序列投影三维测量技术的子序列匹配快速算法.首先根据源序列的内容及子串长度构造由多层子表组成的表格;然后根据子序列的内容,从首字符开始从左到右,依次从首层表格开始向下查找;最后得到子序列在源序列中的位置.即根据首字符在首层表格中查到对应的第二层表格地址,再在第二层表格中根据第二个字符,查找第三层表格地址.以此类推,查出最后一层表格的地址.在最后一层表格中,根据末字符查找到该子序列在源序列中的位置.给出了理论分析并进行了实验验证,结果表明,在目前主流的计算机上,对于典型场景采用查表法的子序列匹配速度较常用算法快60倍以上.