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

知识卡片

普通读书笔记卡 · 3709

伯罗斯惠勒变换取排序旋转末列

理解等级:初级

BWT先给文本末尾加一个小于原字母表全部字符的唯一终止符,再列出所有循环旋转并按字典序排序。

顺序读取排序结果的最后一列,就得到变换后的字符串。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      The Burrows-Wheeler transform, or BWT, for a text T is defined as follows. First, append a new character that compares as lexicographically less than every character of T, and denote this character by $ and the resulting string by T′. Letting n be the length of T′, create n rows of characters, where each row is one of the n cyclic rotations of T′. Next, sort the rows lexicographically. The BWT is then the string of n characters in the rightmost column, read top to bottom. For example, let T = rutabaga, so that T′ = rutabaga$. The cyclic rotations are rutabaga$ utabaga$r tabaga$ru abaga$rut baga$ruta aga$rutab ga$rutaba a$rutabag

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[90000,95000))。 - 结论依据:原文章末问题32-2给出的构造步骤、问题32-3给出的BWT定义及逆变换说明,或章末脚注。 - 原始内容:The Burrows-Wheeler transform , or BWT , for a text T is defined as follows. First, append a new character that compares as lexicographically less than every character of T , and denote this character by $ and the resulting string by T ′. Letting n be the length of T ′, create n rows of characters, where each row is one of the n cyclic rotations of T ′. Next, sort the rows lexicographically. The BWT is then the string of n characters in the rightmost column, read top to bottom. For example, let T = rutabaga , so that T ′ = rutabaga$ . The cyclic rotations are rutabaga$ utabaga$r tabaga$ru abaga$rut baga$ruta aga$rutab ga$rutaba a$rutabag