BWT算法

BWT算法

来自mengbi_er

BWT算法可以将原文本转换成相似文本，并且可以用其他技术进行压缩。

编码方式

（1） 将文本串后加一个文本中不会出现的字符‘#’。（定义#小于文本串中任一字符） 
（2） 将文本串不断右移，得到新文本串。 
（3） 将所有得到的文本串从小到大排序。 
（4） 记F为排序后每个字符串第一个字符，L为每个字符串最后一个字符。易知原文本串中字符在F和L中分别出现且仅出现一次。 
（5） L列即为处理后的文本串。（存储时只需存储L，因为F可由L排序得出）

 

序号	文本串	排序	F	L
1	abcbbcab#	#abcbbcab	#	b
2	#abcbbcab	ab#abcbbc	a	c
3	b#abcbbca	abcbbcab#	a	#
4	ab#abcbbc	b#abcbbca	b	a
5	cab#abcbb	bbcab#abc	b	c
6	bcab#abcb	bcab#abcb	b	b
7	bbcab#abc	bcbbcab#a	b	a
8	cbbcab#ab	cab#abcbb	c	b
9	bcbbcab#a	cbbcab#ab	c	b

 

所以编码后的文本串为bc#acbabb

解码方式

我们发现这样几个性质：

1:L列的第一个元素就是原文本最后一个元素

‘#’在首位时最后一位元素即为L列第一个元素。

2:对原文本来说，F列每个元素，都是对应L列元素的下一个元素（除首个元素）

由右移可以观察得出。 
所以：

1：确定最后一个元素。

2：通过F列对应L列得到每个元素前一个元素

 

序号	排序	F	L		转化
1	#abcbbcab	#	b		#-b
2	ab#abcbbc	a	c		4:b-a
3	abcbbcab#	a	#		2:a-c
4	b#abcbbca	b	a		8:c-b
5	bbcab#abc	b	c		6:b-b
6	bcab#abcb	b	b		5:b-c
7	bcbbcab#a	b	a		9:c-b
8	cab#abcbb	c	b		7:b-a
9	cbbcab#ab	c	b		3:a-#

 

遇到相同字符怎么处理？我们只需要知道该字符在它之前L列出现几次，对应排名F列该字符就是我们要找的位置。 
why：由于F列代表首字符，将其忽略或插到尾部后，对应排名不变。 
eg：1.babc-abcb 
2.bcba-cbab 
前后排名相同。

如何实现？

1.维护每个字符在F列的前缀和。 
2.维护count数组，记录每个L列字符在它之前有多少相同字符（可用count函数代替(效率挺慢的)）。 
例题 bzoj 2408

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int l[10005],f[10005],a[10],s[10],ans[10005],head,tot;
int main()
{
    int n,m;
   // freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&l[i]);
        s[l[i]]++;//桶排
    }
    for(int i=1;i<=m;i++)
    {
        a[i]=a[i-1]+s[i-1];//前缀和
        for(int j=1;j<=s[i];j++)
        {
            f[++head]=i;
        }
    }
    tot=n+1;
    ans[--tot]=l[1];
    int now=l[1];
    //for(int i=1;i<=m;i++)
    //a[i]++;
    int pos=1;
    for(int i=n;i>0;i--)
    {
        ans[i]=l[pos];//答案
        int x=l[pos];//对应前缀和
        pos=a[x]+count(l+1,l+pos+1,x);//查找相同字符的对应位置
    }
    for(int i=1;i<=n-1;i++)
    {
        printf("%d ",ans[i]);
    }
    printf("%d",ans[n]);
    puts("");
}