知识卡片

普通读书笔记卡 · 3707.e.1

三字符元字符保留样本排序信息

理解等级:高级

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的后缀次序,便得到全部样本后缀的次序。

这张卡片看不懂?

已有反馈 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[85000,90000))。 - 结论依据:原文第32.5节复杂度、LCP算法与引理,或章末问题32-1/32-2给出的定义与构造步骤。 - 原始内容:Construct two texts P 1 and P 2 made up of “metacharacters” that are actually substrings of three consecutive characters from T . We delimit each such metacharacter with parentheses. Construct P 1 = ( 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.