BWT算法与后缀树

BWT(Burrows–Wheeler Transform )

通过增加$并对字符串进行循环

图片alt

对字符串矩阵按照首字母进行排序

图片alt

保留最后一列信息，完成index构建

• BWT 的两条基本性质：
  • 每一行的第一个字符和最后一个字符一定在原始字符串中相连
  • 第一列和最后一列字母的相对次序不变
• Index Last = GC$AAAC
• 根据Index还原出最终矩阵的第一列
  • Index First=$AAACCG
• 根据上述两条性质即可反推Reference
  • Ref=ACAACG$

短序列查找

图片alt

后缀树(Suffix tree)

图片alt

图片alt