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

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

Rapid Subsequence Match in Pseudo Random Sequence Projection Based Three-dimensional Measurement System

A rapid algorithm for three-dimensional measurement was proposed based on pseudo random sequence projection. Firstly, a multi-layer table was constructed according to source sequence and length of sub-sequence. Then, the operation of looking up table was performed from table on top layer to which on bottom layer corresponding to the character in subsequence from left to right. Finally, the position of subsequence was obtained by looking up the table on bottom layer. That is to say, the address of table on second layer was obtained by looking up table on top layer according to first (left) character in subsequence. Then, the address of table on third layer was obtained by looking up table on second layer according to second character in subsequence. The rest can be done in the same manner. Finally, the address of table on bottom layer was obtained and the position of subsequence was obtained by looking up this table. The theory analysis and experimental results were presented. The results show that the speed of algorithm based on look-up table for representative scene is about 60 times faster than the general ones on mainstream computer.