Author 2020-03-04
PDF
算法实现1Burrows-Wheeler变换(Burrows–Wheeler Transform)刨根问底算法Contents算法实现 ............................................................................................... 1编码解码利用还原矩阵法变种代码实现 ............................................................................................... 3最近听一个医学专业的同学提到了在进行基因分析中用到算法，觉得挺有意思的，正巧赶上这次疫情在家，于是想研究一下这个算法。这个算法的核心思想在于，调整原来的字符串中字符的顺序（而不改变其长度及内容）从而更多的将重复的字符排列到一起，这样有助于其他的压缩算法获得更高的压缩比。这个算法在基因分析中大有用处也就顺理成章了，想想的双链表示大概都是会有很多这样的字符，那么运用应该可以有比较好的效果。算法实现考虑一个字符串，要想将相同的字符排列到一起，那么最简单的办法就是，将字符串中的字符进行排序。可是单纯的排序之后，虽然还是那么多字符，但是丢失了一个重要的信息就是字符原来的顺序，而的核心思想就是在于排序并想办法保存字符的顺序信息。编码编码方式如下：将作为字符串结尾标记加入到原字符串（记为末尾将字符串从左到右进行轮换，对于一个长度为的字符串，产生个新的字符串，记为将进行字典序排序，权值最小放在最前面，也即在第一个取排序后的所有字符串的最后一个字符，生成一个新的字符串（记为，即编码完成以字符串banana举例来说：字典序排序获取最后一个字符 算法实现2可以看出，转换后的字符串annb$aa比原来的字符串重复相连的字符的确更多了。实际上就是应用了结合进行压缩的：转换后的重复相连字符更多并不绝对，有时候可能转换后的情况反而更糟，比如这个例子：反而不如原始字符串了。解码利用还原矩阵法解码的过程分为以下几步：根据编码后的字符串，得到还原矩阵根据还原矩阵，逐个还原出原来的顺序根据编码的过程我们知道，实际上是这样的对应：还原矩阵得到这个矩阵非常简单，直接将字符串排个序就可以得到：排序还原矩阵在这样的一个还原矩阵中，每一个字符对应的就是它最末尾的字符。解码的过程如下：从左边列的开始，找到对应的字符作为下一个字符根据这个字符，在左边列找到对应的字符，其对应的字符即以此类推，直到结尾如果出现了多个相同的字符，那么就从上到下按顺序找就可以了 代码实现3变种另一种方式可能更清晰，但实质上是一回事，只是做法看着不一样。在上述构建还原矩阵的过程中，我们实际已知的是最后一列的数据，那么，如果我们想办法把其他的列都构建出来，就可以得到原来的字符串了。想办法变成这样然后拿到就可以了过程是这样的：将最后一列排序，作为第一列得到这个之后，从又到左得到a$,na,na,ba,$b, an, an，再将其排序作为第二列以此类推：排序得到第三列得到第三列如此反复，最终得到全部列代码实现看似复杂的操作，没想到用可以写的如此简单，不过不见得一看就懂 代码实现4EOL = '$'def encode(source): source = source + EOL table = [source[i:] + source[:i] for i in range(len(source))] table.sort() return ''.join([row[-1] for row in table])def decode(encoded): length = len(encoded) table = [''] * length for i in range(length): table = sorted([encoded[m] + table[m] for m in range(length)]) print(table) s = [row for row in table if row.endswith(EOL)][0] return s.rstrip(EOL)解码的这个循环不大好理解，打出来一看就懂了：['$', 'a', 'a', 'a', 'b', 'n', 'n']['$b', 'a$', 'an', 'an', 'ba', 'na', 'na']['$ba', 'a$b', 'ana', 'ana', 'ban', 'na$', 'nan']['$ban', 'a$ba', 'ana$', 'anan', 'bana', 'na$b', 'nana']['$bana', 'a$ban', 'ana$b', 'anana', 'banan', 'na$ba', 'nana$']['$banan', 'a$bana', 'ana$ba', 'anana$', 'banana', 'na$ban', 'nana$b']['$banana', 'a$banan', 'ana$ban', 'anana$b', 'banana$', 'na$bana', 'nana$ba']维基百科变换

HTML view coming soon.

Download PDF for the full formatted version.