|
本帖最后由 喜欢喝冰茶 于 2013-10-6 20:40 编辑 ( j2 V* ^1 F, [ r
如果两个字符串是这个样子
& s4 F* g, y& p& h2 ~9 k) o3 c! B8 f9 H( b( B [$ _: T
string1: AAAAAATTTTCCCCCGGGTTTTAAAACCCCCCGG! k! e8 ~% g @
string2: TTAAA 6 V+ ? T& Q' W
" @4 m1 T' L1 J4 D3 f/ T当然要省很多时间,因为不需要对string1一个一个比了!!!
. W! q! o5 B/ c1 ~& a2 q1 M# i: \: b9 \5 n3 o& A5 r# c
string1可以写成:/ u5 @2 a: Q2 K* o5 I% v
长度 字符 起始位置
, E0 O9 |( ?- v6 A 12 z1 e3 f; ~" [+ [* q- J
4 T 7# l$ B; G* u- R( c6 |
5 C 11
2 y4 v. U* H1 v; i3 G 164 L! g0 }. Y+ `( G9 \
4 T 19; e; F( t& y) L, S: \' {3 B
......0 `6 Z2 I) c6 V- `& l; I- k" f
+ K1 R7 H6 K& x: u1 R# F! A
所以当用string2去比的时候,一开始根本就不用考虑字符为A,G,C的行,因为string2开始是T。因此在这个例子中,不需要去检查string1的每个位置,而是非常有限的几个位置,所以可以省很多时间。, G" Q4 k6 D3 d
8 J# F- E0 i) f, @* V
那么如果存在一种这样的转换方法能够将主贴里的字符串转化成这种,势必会省很多时间。有这样一种方法吗?哪里去找?4 Z _9 j6 N% S0 C
7 w1 l1 U9 Y7 X, E
如果你是有心人,你觉得这个东西最常用在哪里?( ~1 ]/ i' l- b) M- T8 y- i6 P; C `
+ Z7 Z8 ~- s' b1 E1 @8 D# l2 C
对了,文件压缩。: C& J4 U4 Y9 U$ z F
" f8 S" y& h" O+ v+ S' ?
事实上,真正的解决方法就是借鉴了最早用于文件压缩的一种算法,称为Burrows-Wheeler Transform,又称block-sorting compression。这是当年在DEC工作的Michael Burrows和David Wheeler发明的,所以以他们的名字命名,bzip2的压缩文件就是基于该算法的。它的转换其实很简单,如果感兴趣大家可以google/wiki(wikipedia上很详细的操作细节)上去看细节,但简单的来说,就是把一个字符串头围相接,不停的移动一位,然后排序,最后取出最后一列就行了。Burrows-Wheeler Transform的特性就是转换后的字符串相对于原始字符串含有大量的重复字符片段,所以就可以使得我们的问题变的相对快捷。
" V; V: B' N( x% C7 `( n' G5 e- w r$ H% {
那么是否就十全十美,万事大吉了呢?这个需要从实际的具体需求来看。
$ o" M# S# d/ x
+ V; K* ^1 _4 V2 o F扛吧,没什么好说的。6 B! a4 H. N5 ^; V- e
' P+ e' V( R. O" A# s+ Z4 b |
|