4

「canonize」関数 (Ukkonen の論文から以下に示す) はどのように機能し、特に while ループはいつ終了するのでしょうか? p' - k' の値は常に p - k の値よりも小さいままになると思います。私は正しいですか、それとも間違っていますか？

procedure canonize(s, (k, p)):
1. if p < k then return (s, k)
2. else
3. find the tk–transition g'(s, (k', p')) = s' from s;
4. while p' − k' <= p − k do
5.     k  = k + p' − k' + 1;
6.     s  = s';
7.     if k <= p then find the tk–transition g'(s, (k', p')) = s' from s;
8. return (s, k).
4

2 に答える 2

8

canonize関数が行うことは、この SA 投稿の最後に記載されていることです。ここでは、次のような状況を考えます。

ここに画像の説明を入力

状況は次のとおりです。

  1. アクティブなポイントは です。つまり、赤いノードから出るエッジ(red,'d',3)の 3 文字先です。defg

  2. ここで、緑色のノードへの接尾辞リンクをたどります。理論的には、現在のアクティブ ノードは(green,'d',3)です。

  3. de残念ながら、緑のノードから出るエッジには 2 文字しかないため、そのポイントは存在しません。したがって、canonize関数を適用します。

それはこのように動作します：

  1. 関心のあるエッジの開始文字は ですd。この文字は、Ukkonen の表記法ではt kと呼ばれます。したがって、「t kdeエッジを見つける」とは、緑のノードでエッジを見つけることを意味します。

  2. その辺の長さはわずか 2 文字です。つまり、 Ukkonen(p' - k') == 2の表記法です。しかし、元のエッジには 3 つの文字がありました(p - k) == 3。そう<=です、ループに入ります。

  3. 探しているエッジを から に短縮しdefますf。これがp := p + (k' - p') + 1ステップの機能です。

  4. deエッジが指す状態、つまり青い状態に進みます。それがそうですs := s'。

  5. エッジの残りの部分fは空ではないため ( )、関連する出力エッジ (青色のノードから出力されるk <= pエッジ) を識別します。fgこのステップでは、k' と p' がまったく新しい値に設定されます。これは、これらが string を参照するようにfgなり、その長さ (p' - k') が 2 になるためです。

  6. 残りのエッジの長さf(p - k) は現在 1 であり、新しいアクティブ ポイントの候補エッジの長さfg(p' - k') は 2 です。したがって、ループ条件は

    while (p' - k') <= (p - k) do

はもはや true ではないため、ループが終了し、実際に新しい (そして正しい) アクティブ ポイントは(blue,'f',1)です。

[実際には、ウッコネンの表記法では、エッジの終了ポインター p は、エッジに続く位置ではなく、エッジの最後の文字の位置を指します。したがって、厳密に言えば、(p - k) は 1 ではなく 0 であり、(p' - k') は 2 ではなく 1 です。ただし、重要なのは長さの絶対値ではなく、2 つの異なる値の相対的な比較です。長さ。

いくつかの最終的なメモ:

  • p や k などのポインターは、元の入力テキスト t 内の位置を参照します。それはかなり混乱する可能性があります。たとえばde、緑のノードのエッジで使用されるポインタは t の部分文字列を参照し、青のノードdeのエッジで使用されるポインタはt の部分文字列を参照します。文字列は t のどこかに 1 つの連続した文字列として表示される必要がありますが、部分文字列は他の場所にも表示される場合があります。したがって、エッジのポインター k は必ずしもエッジの終了ポインター p に1 を加えたものではありません。fgfgdefgfgfgde

  • したがって、ループを終了するかどうかを決定するときに重要なのは、絶対位置 k または p ではなく、現在の候補エッジの長さ (p' - k') と比較した残りのエッジの長さ (p - k) です。 .

  • あなたの質問、コード スニペットの 4 行目にタイプミスがありk'ますk;。

于 2012-04-11T02:00:51.667 に答える
0

補助状態を適切に処理しなかったため、canonize 関数を変更する必要がありました。'p < k' if の後に次のコードを追加しました。

if (s == auxiliary)
{
    s = root;
    k++;
    if (p < k)
        return;
}

今はうまくいくようです:)

于 2014-10-17T13:04:17.383 に答える