当前位置: 首页 > 工具软件 > bwt > 使用案例 >

BWT算法

孙渝
2023-12-01

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("");
}


 

 类似资料: