知识卡片
伯罗斯惠勒变换取排序旋转末列
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