知识卡片
三字符元字符保留样本排序信息
DC3把起点位置模3余1或2的后缀称为样本后缀。对每个样本起点,把连续三个字符(T[i],T[i+1],T[i+2])视为一个元字符;末尾不足三字符时,用编码0且小于正常字符的特殊符号补齐。
把模3余1位置的元字符依次组成P₁,把模3余2位置的元字符依次组成P₂,再拼成P=P₁P₂。若n是3的倍数,原书还在P₁末尾追加全由特殊符号组成的元字符(ØØØ)。这个哨兵保证P₁以含Ø的最小元字符结束,比较P₁中的后缀时不会越过拼接边界、误把P₂开头当作原文本的延续。
先按三个字符的字典序给元字符赋秩,P上的后缀就成为秩序列:比较两个秩序列,等价于每三个字符一组比较原样本后缀。若元字符秩仍有重复,再递归求P的后缀次序,便得到全部样本后缀的次序。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
Construct two texts P1 and P2 made up of “metacharacters” that are actually substrings of three consecutive characters from T. We delimit each such metacharacter with parentheses. Construct P1 = (T[1:3])(T[4:6])(T[7:9]) ⋯ (T[n′:n′ + 2]), where n′ is the largest integer congruent to 1, modulo 3, that is less than or equal to n and T is extended beyond position n with the special character Ø, with encoding 0.