Префиксное дерево - Помощь студентам

flance · 20.04.2013, 14:56

Привет коллегам.

Можете мне объяснить в чем суть префиксных деревьев?

Я понял про ключи.
Понял, что это ассоциативный массив, в котором ключи в дереве. И что каждый ключ добавляет символ. И при обращении к нему мы указываем всю строку до него и включая его.
Ну вот как здесь
http://upload.wikimedia.org/wikipedi...xample.svg.png

Только я не понимаю - какой в этом смысл?
Какие преимущества дает это. В сравнении с простым массивом.

Осознать не могу полезность)

flance · 20.04.2013, 19:14

Никто не сталкивался что ли?

Просто объясните, в таких деревьях не хранятся значения? т.е. сам ключи (их совокупность символов в строки) и является значение. чтобы компактно хранить слова calm, car, camel

Или что? В чем прикол?

Аватар · 20.04.2013, 19:22

http://habrahabr.ru/post/111874/

Вадим Мошев · 20.04.2013, 19:25

Я думаю, что эти необходимо для поиска по словам.

Например, есди в БД есть куча фамилий, а нам надо найти фамилию "Иванов". Вместо того, чтобы сравнивать каждую фамилию из БД со строкой поиска, мы встаём на элемент "И", затем ищем элемент "Ив", затем ищем "Ива" и так далее, пока не найдём терминальный элемент "Иванов".

Аватар · 20.04.2013, 19:33

Вспомнил, как-то даже использовал для решения задачи определения частотного вхождения слов в текст. Программку выкладывал в #11 темы http://programmersforum.ru/showthrea...D%E0+%EC%E8%F0

flance · 20.04.2013, 19:39

Аватар
Да, эта первая статья, которую я прочитал. Только я не понял сути - для чего. Непонятно - строка, составленная из ключей и является искомым? Т.е. значений как у массивов нет?

Вадим Мошев
Получается, И, в, а, н, о, в - это ключи, так? А значений нет?

Т.е. дерево из ключей?

flance · 20.04.2013, 20:03

Хотя сейчас вчитался. Значения есть. Т.е. ключи это именно ключи. А значения есть как надо.

Тогда непонятно вообще - для чего это.

Аватар · 20.04.2013, 20:13

Цитата:

для чего это.

Например для быстрого поиска в большом объеме слов, не используя методов сортировки больших текстовых массивов. И никто не мешает в узлах дерева хранить еще некую информацию, например количество вхождений слова в текст

alexander13 · 20.04.2013, 20:32

flance, читайте классику =) //Кнут, Искусство Программирования, т. 3

Вадим Мошев · 20.04.2013, 20:43

Цитата:

Сообщение от alexander13

flance, читайте классику =) //Кнут, Искусство Программирования, т. 3

А вот и эта книга:

20.04.2013, 19:14	#2
flance Форумчанин Регистрация: 31.05.2011 Сообщений: 184	Никто не сталкивался что ли? Просто объясните, в таких деревьях не хранятся значения? т.е. сам ключи (их совокупность символов в строки) и является значение. чтобы компактно хранить слова calm, car, camel Или что? В чем прикол? Программист-фрилансер, готовый рассмотреть предложения на постоянную удаленную работу... Ответственный, трудолюбивый telegram: flancejob

20.04.2013, 19:22	#3
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	http://habrahabr.ru/post/111874/ Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

20.04.2013, 19:33	#5
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	Вспомнил, как-то даже использовал для решения задачи определения частотного вхождения слов в текст. Программку выкладывал в #11 темы http://programmersforum.ru/showthrea...D%E0+%EC%E8%F0 Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

20.04.2013, 19:39	#6
flance Форумчанин Регистрация: 31.05.2011 Сообщений: 184	Аватар Да, эта первая статья, которую я прочитал. Только я не понял сути - для чего. Непонятно - строка, составленная из ключей и является искомым? Т.е. значений как у массивов нет? Вадим Мошев Получается, И, в, а, н, о, в - это ключи, так? А значений нет? Т.е. дерево из ключей? Программист-фрилансер, готовый рассмотреть предложения на постоянную удаленную работу... Ответственный, трудолюбивый telegram: flancejob

20.04.2013, 20:03	#7
flance Форумчанин Регистрация: 31.05.2011 Сообщений: 184	Хотя сейчас вчитался. Значения есть. Т.е. ключи это именно ключи. А значения есть как надо. Тогда непонятно вообще - для чего это. Программист-фрилансер, готовый рассмотреть предложения на постоянную удаленную работу... Ответственный, трудолюбивый telegram: flancejob

20.04.2013, 14:56	#1
flance Форумчанин Регистрация: 31.05.2011 Сообщений: 184	Префиксное дерево Привет коллегам. Можете мне объяснить в чем суть префиксных деревьев? Я понял про ключи. Понял, что это ассоциативный массив, в котором ключи в дереве. И что каждый ключ добавляет символ. И при обращении к нему мы указываем всю строку до него и включая его. Ну вот как здесь http://upload.wikimedia.org/wikipedi...xample.svg.png Только я не понимаю - какой в этом смысл? Какие преимущества дает это. В сравнении с простым массивом. Осознать не могу полезность) Программист-фрилансер, готовый рассмотреть предложения на постоянную удаленную работу... Ответственный, трудолюбивый telegram: flancejob

20.04.2013, 19:25	#4
Вадим Мошев Старожил Регистрация: 12.11.2010 Сообщений: 8,568	Я думаю, что эти необходимо для поиска по словам. Например, есди в БД есть куча фамилий, а нам надо найти фамилию "Иванов". Вместо того, чтобы сравнивать каждую фамилию из БД со строкой поиска, мы встаём на элемент "И", затем ищем элемент "Ив", затем ищем "Ива" и так далее, пока не найдём терминальный элемент "Иванов".

20.04.2013, 20:32	#9
alexander13 Форумчанин Регистрация: 07.02.2013 Сообщений: 267	flance, читайте классику =) //Кнут, Искусство Программирования, т. 3 Μολὼν λαβέ

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Дерево	ser70	Общие вопросы C/C++	2	25.11.2012 16:22
2-3 дерево С++	dimentius	Помощь студентам	0	08.06.2012 17:11
Префиксное увеличение строки(С++)	nhr	Помощь студентам	0	04.05.2011 20:46
Дерево в С#	vedro-compota	C# (си шарп)	5	07.11.2010 14:02
дерево С#	Natok	Помощь студентам	0	14.09.2009 23:42