A Note on Bit-Parallel Alignment Computation
A Note on Bit-Parallel Alignment Computation
复制标题
位并行对齐计算的注意事项
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Heikki Hyyrö
中科院分区：
文献类型：
--
作者：
Heikki Hyyrö
。字符或两个相邻字符之间的换位。计算这三个距离的算法，其中m是a的长度是b的长度，w是本文中的计算单词大小。和B.这样的对齐方式描绘了如何使用ED（a，b）操作将a转换为b，其中ed（a，b）是使用的编辑距离（上面提到的三个）。最长的公共序列的算法，在效果中对应于简单的编辑距离。
. The edit distance between strings A and B is defined as the minimum number of edit operations needed in converting A into B or vice versa. Typically the allowed edit operations are one or more of the following: an insertion, a deletion or a substitution of a character, or a transposition between two adjacent characters. Simple edit distance allows the first two operation types, Levenshtein edit distance the first three, and Damerau distance all four. There exist very efficient O ( ⌈ m/w ⌉ n ) bit-parallel algorithms for computing each of these three distances, where m is the length of A , n is the length of B , and w is the computed word size. In this paper we discuss augmenting the bit-parallel algorithms to recover an optimal alignment between A and B . Such an alignment depicts how to transform A into B by using ed ( A, B ) operations, where ed ( A, B ) is the used edit distance (one of the three mentioned above). Previously Iliopoulos and Pinzon have given such an algorithm for the longest common subsequence, which in effect corresponds to the simple edit distance. We propose a simpler method, which is faster and also more general in that our method can be used with any of the above three distances.