后缀树根边缘的证明

我想知道如何编写一个证据，证明后缀树中分支或根边的数量等于字符串S的字母大小。假设我们有S = {aaabaac} ，字母表= {a，b，c}，字母大小= 3，那么根边缘（或从根开始的分支）仅仅是3，即a，b和c。或者这可以通过定义来证明吗？我不确定！后缀树根边缘的证明

2016-05-15 perfecto

这取决于确切的定义您正在使用。通常情况下，你会假设否定假设。那么你会发现这样的树不能存在，因此这个假设是错误的，并且原来的假设是真实的。因此，在你的情况下，假设树有*不*只有三个根边缘，并表明这不可能是真的。 – Polygnome

感谢您的初始方向，但是我如何正确地对抗证明中的那个？这不是作业，而只是为了了解如何做到这一点。因此，我如何证明，如果它在这种情况下具有4个根边缘，那么不是有效的后缀树？ – perfecto

这实际上不一定是正确的。有两个因素需要考虑：

后缀树包括一个额外的结束串标记（通常表示$）这是用来确保所有后缀对应的叶子在树上。这意味着您可能有更多根以上的孩子比字母中的字符。
根将有一个孩子出现在字符串中的每个不同的字符，所以完全可能的是，根将比字母表的大小更少孩子孩子。例如，如果您的字母是{A，T，C，G}，那么AAAAAA $的后缀树将只有两个孩子 - 一个用于$，一个用于A.

2016-05-17 17:34:10 templatetypedef

如果你添加$作为一个字符，那么字母大小也增加1，即在你的例子中AAAAAA $将给出字母大小= 2，这将对应于2个根边缘，因此一个以A开头，另一个以$ – perfecto

字符串的字母表是*可能*字符的集合，而不是* used *字符的集合。 – templatetypedef

好吧，让我们来说一下_by definition_该树将被构造成没有$ - 是否可以证明树的始终具有与字母表大小相等的根边的确切数量？ – perfecto

回答