radix tree

Переклад книжки Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms". Обговорення, термінологія.
Відповісти
ReAl
Повідомлень: 56
З нами з: П'ят жовтня 27, 2017 11:58 pm

radix tree

Повідомлення ReAl »

У книжці radix tree це дерево, у кожного вузла якого число дітей визначено основою системи числення частин, з яких складаються ключі («символів», в тому числі власне символів текстових рядків). У «примітках розділу» сказано, що їх часто називають trie.
Мені на думку відразу спало «префіксне дерево» (через «префіксні коди», які отримують із вже побудованих з інших міркувань дерев, Гаффманівске кодування).

Але в англійській вікіпедії це дві різних статті
TrieПрефіксне дерево
і, як оптимізований варіант,
Radix tree

Хоча на початку першої і зазначено
«In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree»

Префіксне дерево?
Востаннє редагувалось Пон квітня 02, 2018 10:53 am користувачем ReAl, всього редагувалось 1 раз.
Yola
Повідомлень: 170
З нами з: Чет квітня 28, 2011 9:25 am

Re: radix tree

Повідомлення Yola »

Я тут колись намагався відшукати переклад для trie. Також цікава ідея була у chizh'а в коментарях.
Відповісти

Повернутись до “Переклад "Introduction to Algorithms"”