後綴樹根邊緣的證明

我想知道如何編寫一個證據，證明後綴樹中分支或根邊的數量等於字符串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

回答