我想知道如何編寫一個證據,證明後綴樹中分支或根邊的數量等於字符串S的字母大小。假設我們有S = {aaabaac} ,字母表= {a,b,c},字母大小= 3,那麼根邊緣(或從根開始的分支)僅僅是3,即a,b和c。或者這可以通過定義來證明嗎?我不確定!後綴樹根邊緣的證明
回答
這實際上不一定是正確的。有兩個因素需要考慮:
後綴樹包括一個額外的結束串標記(通常表示$)這是用來確保所有後綴對應的葉子在樹上。這意味着您可能有更多根以上的孩子比字母中的字符。
根將有一個孩子出現在字符串中的每個不同的字符,所以完全可能的是,根將比字母表的大小更少孩子孩子。例如,如果您的字母是{A,T,C,G},那麼AAAAAA $的後綴樹將只有兩個孩子 - 一個用於$,一個用於A.
如果你添加$作爲一個字符,那麼字母大小也增加1,即在你的例子中AAAAAA $將給出字母大小= 2,這將對應於2個根邊緣,因此一個以A開頭,另一個以$ – perfecto
字符串的字母表是*可能*字符的集合,而不是* used *字符的集合。 – templatetypedef
好吧,讓我們來說一下_by definition_該樹將被構造成沒有$ - 是否可以證明樹的始終具有與字母表大小相等的根邊的確切數量? – perfecto
- 1. Google Sketchup中的明顯邊緣邊緣
- 2. 樹中的邊緣切割
- 3. 從邊緣構建樹
- 4. 邊緣樣式對於樹
- 5. 樹邊緣和正向邊緣之間的區別
- 6. 從後綴樹生成後綴
- 7. 透明Networx邊緣標籤
- 8. 後綴樹構造
- 9. 在D3 v4中隱藏根節點和邊緣樹圖
- 10. ImageView透明設置邊緣/邊框Android
- 11. 曼哈頓邊緣的空間樹
- 12. 可摺疊樹D3的邊緣
- 13. 帶邊緣信息的Haskell樹
- 14. 根據邊緣屬性添加多個邊緣使用igraph
- 15. Matlab中的後綴樹
- 16. JavaScript中的後綴樹?
- 17. 獲取邊緣檢測後的邊緣座標(Canny)
- 18. 後綴樹是否唯一?
- 19. 令牌後綴樹教程
- 20. 後綴樹搜索時間
- 21. 在C++構建後綴樹
- 22. 後綴數組優於後綴樹的位置?
- 23. 邊緣到邊緣的HTML5視頻
- 24. 紋理邊緣透明問題
- 25. AS3 - bitmapData邊緣alpha透明問題
- 26. 邊緣檢測和透明度
- 27. 後綴樹中的後綴鏈接是否與aho-corasick自動機中的失敗邊相同?
- 28. 關於Ukkonen的後綴樹的澄清
- 29. @ LGSon的答案後的樣式尖左邊緣和圓角右邊緣
- 30. 表達式樹的後綴表示法
這取決於確切的定義您正在使用。通常情況下,你會假設否定假設。那麼你會發現這樣的樹不能存在,因此這個假設是錯誤的,並且原來的假設是真實的。 因此,在你的情況下,假設樹有*不*只有三個根邊緣,並表明這不可能是真的。 – Polygnome
感謝您的初始方向,但是我如何正確地對抗證明中的那個?這不是作業,而只是爲了瞭解如何做到這一點。因此,我如何證明,如果它在這種情況下具有4個根邊緣,那麼不是有效的後綴樹? – perfecto