Три экономит место, но как?

Question

Я смущен тем, как реализация Trie экономит место и сохраняет данные в наиболее компактной форме!

Если вы посмотрите на дерево ниже.Когда вы храните символ в любом узле, вам также необходимо сохранить ссылку на него и, таким образом, для каждого символа строки, в которой вам нужно сохранить его ссылку.Хорошо, мы сэкономили немного места, когда появился общий символ, но потеряли больше места при хранении ссылки на этот символьный узел.

Так не слишком ли много структурных издержек для поддержки самого этого дерева?Вместо этого, если вместо этого использовался TreeMap, скажем, для реализации словаря, это могло бы сэкономить намного больше места, так как строка сохранялась бы в одной части, следовательно, при хранении ссылок не терялось места, не так ли?

Answer 1

Чтобы сэкономить место при использовании дерева, можно использовать сжатое дерево (также известное как дерево Патрисия или основное дерево), для которого один узел может представлять несколько символов:

В информатике радикальное дерево (также patricia trie или radix trie) - это оптимизированная по пространству структура данных trie, в которой каждый узел, имеющий только одного дочернего элемента, объединяется со своим дочерним элементом.В результате каждый внутренний узел имеет как минимум двух дочерних элементов.В отличие от обычных попыток, ребра могут быть помечены как последовательностями символов, так и отдельными символами.Это делает их намного более эффективными для небольших наборов (особенно если строки длинные) и для наборов строк, которые имеют длинные префиксы.

Пример радикального дерева:

Обратите внимание, что три обычно используется как эффективная структура данных для сопоставления префиксов в наборе строк.Три можно также использовать в качестве ассоциативного массива (например, хеш-таблицы), где ключом является строка.

Answer 2

Пространство экономится, когда у вас много слов, которые будут представлены деревом. Потому что многие слова имеют один и тот же путь в дереве; чем больше у вас слов, тем больше места вы сэкономите.

Но есть лучшая структура данных, если вы хотите сэкономить место. Trie не экономит место так же, как направленный ациклический граф слов (DAWG) , потому что он разделяет общий узел по всей структуре, тогда как trie не разделяет узлы. Запись вики объясняет эту деталь, поэтому взгляните на нее.

Вот разница (графически) между Trie и DAWG:

Строки «tap», «taps», «top» и «tops», хранящиеся в Trie (слева) и DAWG (справа), «EOW» означают «конец слова».

Дерево слева - это Три, а дерево справа - РАГ. Сравните их и посмотрите, как DAWG эффективно экономит пространство. У Trie есть повторяющиеся узлы, которые представляют одну и ту же букву / подслово, в то время как DAWG имеет ровно один узел для каждой буквы / подслово.

Answer 3

Дело не в дешевом месте в памяти, а в драгоценном месте в файле или в канале связи. С помощью алгоритма, который строит эту последовательность, мы можем отправить 'десять' в трех битах, слева направо и справа. По сравнению с 24 битами «десять» будет занимать несжатый, это огромная экономия ценного дискового пространства или пропускной способности передачи.

Answer 4

Вы можете сделать вывод, что это экономит место на идеальной машине, где каждый байт распределяется эффективно.Однако реальные машины выделяют выровненные блоки памяти (8 байтов в Java и 16 байтов в некоторых C ++), и поэтому они могут не экономить место.

Строки и коллекции Java добавляют относительно большое количество накладных расходов, поэтому разница в процентах может быть очень небольшой.

Если ваша структура не очень велика, значение вашего тайм-аута взвешивает затраты на память, так как использование самого простого, стандартного и простого в обслуживании сбора намного важнее.Например, ваше время может легко стоить 1000x или больше значения памяти, которую вы пытаетесь сохранить.

Например, скажем, у вас есть 10000 имен, которые вы можете сохранить по 16 байт каждое с помощью дерева.(Предполагая, что это можно доказать, не занимая больше времени) Это равняется 16 КБ, что по сегодняшним ценам стоит 0,1 цента.Если ваше время обходится вашей компании в 30 долларов в час, стоимость написания одной строки протестированного кода может составить 1 доллар.

Если вы думаете, что это займет мгновение, чтобы сэкономить 16 КБ, вряд ли это будетстоит того для ПК.(мобильные устройства - другая история, но тот же аргумент применим ИМХО)

РЕДАКТИРОВАТЬ: Вы вдохновили меня на добавление обновления http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html

Answer 5

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

Пытается, как и любая другая структура, преуспеть в хранении определенных типов данных. В частности, попытки лучше всего хранить строки, имеющие общий корень. Например, подумайте о хранении списков каталогов с полным путем.