知识卡片
逆变换沿末列与秩倒推原文
BWT把“原文加唯一终止符$”的所有循环移位按字典序排列,并保存排序矩阵的末列L;首列F就是L排序后的结果。相同字符在L和F中的出现次序一一对应:若L第r行的字符c是该字符在L中的第k次出现,就转到F中字符c的第k次出现所在行。这一LF转移对应把当前循环移位向前扩展一个字符。
因为$只出现一次,可从L中$所在行开始。每次读取当前行的L字符,再做一次LF转移;反复执行会按从后向前的顺序走过原文的字符。去掉$并逆序,即恢复原文。这里“第k次”是稳定的出现秩,不能只按字符值跳转,否则重复字符会混淆。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
There is enough information in BWT and rank to reconstruct T′ from back to front. Suppose that you know the rank r of a character c in T′. Then c is the first character in row r of the sorted cyclic rotations. The last character in row r must be the character that precedes c in T′. But you know which character is the last character in row r, because it is BWT[r]. To reconstruct T′ from back to front, start with $, which you can find in BWT. Then work backward using BWT and rank to reconstruct T′. Let’s see how this strategy works for rutabaga. The last character of T′, $, appears in position 7 of BWT. Since rank[7] = 1, row 1 of the sorted cyclic rotations of T′ begins with $. The character that precedes $ in T