边缘在一个后缀树最大和最小数 [英] Maximum and minimum number of edges in a suffix tree

问题描述

哪些边缘在一个后缀树的最大和最小数目？我知道最大为2m-1，但我不明白为什么会这样。

解决方案

首先，关于在最大边数：

这是很容易的，如果你觉得边作为未来两种形式了解：导致内部节点的边，导致叶节点和边缘。在下文中，我假设后缀树的构造的字符串 N 字符的长度。

1. 关于边缘，导致叶。必须有每个后缀正是一片叶子，每片叶子都有唯一一个入边（没有出站边）。所以必须有 N 边缘，导致叶。

2. 关于边缘导致内部节点。像叶子节点，内部节点，也只有一个入站边各。因此，为了确定有多少边缘导致内节点那里都不可能，它足以确定内节点有多少都可以。那么，什么是内部节点的最大可能是多少？

   有关该地看到，内节点只插入后缀树在分支点，即内节点的出的边缘的数量是很重要的是总是至少2个（如果有只有一个出边缘，内节点不会被在首位构造的）。但是，每一个出站的边缘必须最终到叶节点（可能会通过进一步的内部节点之后）导致。换句话说，被插入该树中的每个节点内增加叶子节点的由至少1总数此外，即使一个树无内部节点都必须具有至少一个边缘走出根节点的（除非树是空）。因此，在一个非空的树，叶子总数→必须

     L＆GT; = I + 1
    

   其中，我是内部节点的数量。相反地​​，内节点的数目是

     I＆LT; = L  -  1 = N  -  1
    

   返回到原来的问题，边缘导致内节点的数量是，我们说过，同样作为内的节点的数量，因此，它也必然由 N - 1 。

我们得出结论：的边的总数是边缘导致叶片数（ N ），加上边缘，导致内数节点（＆LT; = N-1 ），因此它的最大被绑定

  N +（N-1）= 2N  -  1
 

狴ERAT demonstrandum。

---

关于在最小边数：这遵循相同的原理，即，我们计算边缘导致叶的数目和边缘，导致内部节点的数量，然后添加在一起<。 / P>

节点，导致叶片数总是 N ，即 N 是最大和最小可能的。

节点通往内部节点的数量，但是，可能是零。例如。当输入的字符串没有重复的元素，如 ABCDEF ，恰好有 N 边，每个从根直到叶。没有分支点，没有内部节点。因此边缘通向内部节点的最小数量是0

总之，边缘的最小数量为 N + 0 = N 。

What are the maximum and minimum number of edges in a suffix tree? I know the maximum is 2m-1, but I don't understand why that is so.

解决方案

First, about the maximum number of edges:

It's quite easy to understand if you think of the edges as coming in two flavours: Edges that lead to a leaf node, and edges that lead to an inner node. In the following, I'll assume that the string the suffix tree is constructed for is N characters in length.

1. About the edges leading to leaves. There must be exactly one leaf for every suffix, and every leaf has only one inbound edge (and no outbound edges). So there must be N edges leading to leaves.

2. About the edges leading to inner nodes. Like with leaf nodes, inner nodes, too, have only one inbound edge each. Therefore, to determine how many edges leading to inner nodes there can possibly be, it suffices to determine how many inner nodes there can be. So, what is the maximum possible number of inner nodes?

   For this it is important to see that inner nodes are only inserted into the suffix tree at branching points, i.e. the number of outbound edges of an inner node is always at least 2 (if there was only one outbound edge, the inner node wouldn't have been constructed in the first place). But every outbound edge must eventually lead to a leaf node (possibly after going through further inner nodes). In other words, every inner node inserted into the tree increases the total number of leaf nodes by at least 1. Furthermore, even a tree with no inner nodes whatsoever must have at least one edge going out of the root node (unless the tree is empty). Hence, in a non-empty tree, the total number of leaves L must be

   L >= I + 1
   

   where I is the number of inner nodes. Conversely, the number of inner nodes is

   I <= L - 1 = N - 1
   

   Returning to the original question, the number of edges leading to inner nodes is, as we said, the same as the number of inner nodes, hence it is also bound by N - 1.

We conclude that the total number of edges is the number of edges leading to leaves (N) plus the number of edges leading to inner nodes (<=N-1), hence its maximum is bound by

N + (N-1) = 2N - 1

quod erat demonstrandum.

---

Regarding the minimum number of edges: This follows the same principle, i.e. we calculate the number of edges leading to leaves and the number of edges leading to internal nodes, and then add them together.

The number of nodes leading to leaves is always N, i.e. N is the maximum as well as the minimum possible.

The number of nodes leading to internal nodes, however, may be zero. E.g. when the input string has no repeated elements, such as abcdef, there are exactly N edges, each from the root straight to a leaf. No branching points, no internal nodes. Hence the minimum number of edges leading to internal nodes is 0.

In conclusion, the minimum number of edges is N + 0 = N.

这篇关于边缘在一个后缀树最大和最小数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！