Как рассчитать количество узлов в дереве, учитывая набор слов

Question

Интересно, есть ли общий алгоритм или методика для вычисления количества узлов (и, таким образом, сколько байтов) в дереве.

Так, скажем, существует дерево, которое начинается так:*

   a        t
   p        h
e  p        e  i
   l  s  r  i  s
   e     e  r

ape
apps
apple
the
their
there
this

Тогда представьте, что вместо этого есть большой словарь тысяч слов.Каждое слово состоит из набора букв L из алфавита A.Таким образом, по существу, мы можем генерировать n количество L (слов), скажем, 100 000, различной длины.В некоторых ситуациях они будут перекрываться, поэтому количество байтов, которое он занимает в последнем файле, не будет равным 100 000 x (средняя длина).Вместо этого это будет некоторая доля от общего числа.

Мне интересно, как это вычислить.Если вам действительно нужно сгенерировать данные, а затем измерить их, или если есть математический метод для быстрого моделирования, то это очень быстро.

Answer 1

Я думаю, что это может сильно отличаться от входных данных, поэтому вам придется сканировать их, чтобы выработать ответ.На самом деле вам не нужно создавать попытки, при условии, что вы можете сначала отсортировать входные данные: учитывая отсортированный ввод, вы можете просто посчитать новые буквы из последней общей буквы в каждой строке, которую вы сканируете.Нет необходимости в каком-либо распределении, кроме запоминания последней строки, и вы можете найти правильный ответ в одном сканировании.

Используя ваш пример, обрабатывает отсортированный список:

1. "ape"- три новые буквы
2. «приложения» - вернуться к общему «р», затем две новые буквы = 5 на данный момент
3. «яблоко» - обратно ко второй «р», котораяпоследняя общая буква, затем две новые буквы = 7
4. "the" - общности нет, поэтому вернемся к началу и три буквы = 10
5. "их" - две новые буквы = 12
6. «там» - назад два, два новых = 14
7. «это» - назад три, два новых = 16

, что соответствует вашей диаграмме с 16 узлами.