返回主题:文本压缩与熵编码

知识卡片

普通读书笔记卡 · 3709.b.1

逆变换沿末列与秩倒推原文

理解等级:高级

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

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[95000,100000))。 - 结论依据:原文章末问题32-2给出的构造步骤、问题32-3给出的BWT定义及逆变换说明,或章末脚注。 - 原始内容: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