Мне было интересно, как написать доказательство того, что количество ветвей или корневых ребер в дереве суффиксов равно размеру алфавита строки S. Скажем, если у нас есть S = {aaabaac} , алфавит = {a, b, c}, размер алфавита = 3, тогда корневые ребра (или ветви, начинающиеся с корня) будут только точно такими, как a, b и c. Или это можно доказать по определению? Я не уверен!Доказательство краев корня дерева суффикса
Это на самом деле не обязательно так. Есть два фактора, которые необходимо учитывать:
Суффикс деревья включают дополнительный конца-строки маркера (часто обозначается символом $), который используется для того, чтобы все суффиксы соответствуют листьев в дереве. Это означает, что у вас могут быть более детей с корнем, чем символы в алфавите.
У корня будет один ребенок для каждого отдельного символа, который появляется в строке, поэтому вполне возможно, что у корня будет меньше детей, чем размер алфавита. Например, если ваш алфавит равен {A, T, C, G}, тогда дерево суффиксов для AAAAAA $ будет иметь только двое детей: один для $ и один для A.
, если вы добавите $ в качестве символа, тогда размер алфавита также увеличен на 1, т. Е. В вашем примере AAAAAA $ даст размер алфавита = 2, и тогда это будет соответствовать двум корневым ребрам, таким образом, один начинается с A, а другой, начиная с $ – perfecto
Алфавит строки - это набор * возможных * символов, а не набор * используемых символов *. – templatetypedef
Хорошо, давайте скажем _ по определению_ дерево будет построено без $ - можно ли, таким образом, доказать, что дерево всегда будет иметь точное число корневых ребер, равное размеру алфавита? – perfecto
Это зависит от точного определения ты используешь. Обычно вы предполагаете, что отрицание предположения. Тогда вы увидите, что такое дерево не может существовать, поэтому предположение неверно, и исходное предположение верно. Итак, в вашем случае предположим, что дерево имеет * не * ровно три корневых ребра и показывает, что это не может быть правдой. – Polygnome
Спасибо за начальное направление, но как я точно противопоставил это в доказательстве? это не домашнее задание, а просто понять, как это можно сделать. Итак, как я могу доказать, что если он имеет, например, в этом случае, он имеет 4 корневых ребра, а не действительное дерево суффикса? – perfecto