Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.01.2012, 12:42   #1
yaapelsinko
Пользователь
 
Регистрация: 15.01.2012
Сообщений: 67
По умолчанию Алгоритмы/структуры для "двунаправенных" деревьев

Чисто из научных побуждений пришла в голову вот такая идея, а вот как её хорошо реализовать - ещё в голову не пришло.

Опишу нехорошую реализацию, чтобы была понятна суть.

Таблица:

Термин | Определение
"мяч" | "шар", "упругий"
"шар" | "круглый", "объемный"
"упругий" | "деформируется", "восстанавливается"
"планета" | "шар", "большой"

И т.д.

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

Если таблица большая, то обрабатывать такие выборки будет непросто.

Можно кешировать "восходящие" связи в третьем поле "Вхождения", но тогда записи в этих самых вхождениях могут разрастаться до неприличных размеров.
Кроме того, ещё вопрос, не разрастутся ли записи в "Определениях" до не менее неприличных размеров. Тут ведь не предугадаешь, будет ли понятие напрямую состоять из сотен элементарных, либо будет многоуровневая структура, когда десяток другой понятий определяет что-то чуть более сложное, а это чуть более сложное в свою очередь входит в состав следующего термина.
Структура при этом предполагается весьма изменчивой, стало быть вхождения могут как образовываться, так и удаляться.

Вооот.

Есть у кого идеи получше моей, какую структуру данных надо создать, чтобы обеспечить "естественное" возникновение связи "снизу вверх", если была создана связь "сверху вниз"? Точнее даже, чтобы связь "сверху вниз", которая уже существует, являлась одновременно и связью "снизу вверх", вот как в приведёном мной примере таблицы и выборки из неё, но более эффективно с точки зрения скорости работы?
yaapelsinko вне форума Ответить с цитированием
Старый 15.01.2012, 12:57   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

Таблица1: ид, понятие
1 мяч
2 шар
3 упругий
4 круглый
5 объемный
6 деформируется
7 восстанавливается
8 планета
9 большой

Таблица2: ид1,ид2
1 2
2 1
1 3
3 1
2 4
4 2
2 5
5 2
3 6
6 3
3 7
7 3
8 2
2 8
8 9
9 8

Выборка для "шар"

Код:
SELECT T1.понятие
  FROM Таблица2 T2
    LEFT JOIN Таблица1 T1 ON T1.ид=T2.ид2
  WHERE T2.ид1=2
Результат

мяч
круглый
планета
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 15.01.2012, 14:54   #3
yaapelsinko
Пользователь
 
Регистрация: 15.01.2012
Сообщений: 67
По умолчанию

Иначе говоря, вместо хранения понятий хранить связи между ними.
Хитро придумано. Эдак сами понятия вовсе можно выбросить.
yaapelsinko вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Ошибка "Expecting a valid name" для оператора "<" в JScript Ратибор Редоран JavaScript, Ajax 0 15.12.2011 14:38
ООП Delphi разработка классов для реализации контейнера на основе структуры"упорядоченный динамический список" naffy Помощь студентам 0 28.06.2011 00:22
задачи в Си на "Строки" и "Структуры" Ховард Помощь студентам 2 14.06.2011 11:10
программа для лабораторной работы "Генетические алгоритмы" maximp Фриланс 2 11.11.2010 20:14
при вводе на листе "магазин"- код товара появлялось "описание" товара из "склада" с "продажной ценой" aleksei78 Microsoft Office Excel 13 25.08.2009 12:04