Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2006.12.10;
Скачать: [xml.tar.bz2];

Вниз

Бинарные деревья (деревья поиска)   Найти похожие ветки 

 
Николай1984   (2006-10-30 08:48) [0]

Задача о поиске текста.
Дан текст. Построить из слов бинарное дерево поиска по следующему принципу:"Чем чаще встречается слово в тексте тем ближе должно к корню должно храниться это слово, чем реже тем ближе к листьям". При добавлении слова нужно, чтобы с учетом частоты его появления менялось дерево (слово переводилось ближе к корню).

Вопрос в следующем, что делать со словами у которых частота появления одинакова? и какое слово взять за корень дерева? Мне непонятно. Подскажите, кто что может, Буду очень благодарен.
Зарание спасибо.


 
KilkennyCat ©   (2006-10-30 09:03) [1]

> что делать со словами у которых частота появления одинакова?

Исппользовать еще одно правило. Например, алфавитный порядок.

> и какое слово взять за корень дерева?

любое. потом поменять.


 
MBo ©   (2006-10-30 09:44) [2]

можно использовать простые бинарные деревья (BST), красно-черные (RB)или AVL. Автоматическую подстройку обеспечивают т.н. скошенные деревья (splay tree)


 
Alex Konshin ©   (2006-10-30 11:56) [3]

Это задача из лабораторной или из реальной жизни? Потому как для реальной жизни она абсолютно бессмыслена. Постановка задачи некорректна.

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

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

Реализации AVL деревьев есть у меня на сайте.

PS: И после этого люди еще сомневаются в необходимости систематического матматического образования...


 
Ketmar ©   (2006-10-30 13:14) [4]

кстати: а что вы скажете об FNV hash?


 
MBo ©   (2006-10-30 13:40) [5]

>Пытаться трансформировать дерево с учетом частоты - неблагодарное занятие

splay tree как раз для этого и предназначено, с его использованием, например, можно Хаффмана строить.


 
Alex Konshin ©   (2006-10-30 14:02) [6]

> MBo ©   (30.10.06 13:40) [5]
> >Пытаться трансформировать дерево с учетом частоты - неблагодарное занятие
>
> splay tree как раз для этого и предназначено, с его использованием,
>  например, можно Хаффмана строить.

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

По-большому счету нужно знать, что человек хочет сотворить. Скорее всего он просто неправильно формализует задачу.


 
KilkennyCat ©   (2006-10-30 14:14) [7]

> [6] Alex Konshin ©   (30.10.06 14:02)

формулирует :)


 
Alex Konshin ©   (2006-10-30 14:24) [8]

> KilkennyCat ©   (30.10.06 14:14) [7]
> > [6] Alex Konshin ©   (30.10.06 14:02)
> формулирует :)

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


 
Николай1984   (2006-10-30 15:20) [9]

Задача сформулирована верно, это задание по лабораторной работе
Целиком списал с распечатки.
Сижу уже неделю толку ни какого.
Может кто чтонибуть подскажет!


 
KilkennyCat ©   (2006-10-30 15:21) [10]

> [8] Alex Konshin ©   (30.10.06 14:24)

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


 
KilkennyCat ©   (2006-10-30 15:26) [11]

> [9] Николай1984   (30.10.06 15:20)
> Задача сформулирована верно, это задание по лабораторной
> работе

Когда я тупел в институте, я пользовался методичками (это книжечки такие, не девушки :) )... дабы делать задания на уровне института :)
Неужто их (методичек) уж больше нет?



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2006.12.10;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.47 MB
Время: 0.043 c
15-1164017098
Cyrax
2006-11-20 13:04
2006.12.10
Системные программы на C, С++, С# и Java


15-1164019452
Cyrax
2006-11-20 13:44
2006.12.10
Компиляторы, интерпретаторы и трансляторы


2-1164220218
zep
2006-11-22 21:30
2006.12.10
TClientDataSet


3-1159871123
ККВ
2006-10-03 14:25
2006.12.10
Как получить значение поля?


2-1164269566
IGo
2006-11-23 11:12
2006.12.10
Пронрамное создание элемента CheckBox





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский