|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 31 Oct 2002 04:16:08
To : Eduard Vatutin
Subject : Обработка деревьев
--------------------------------------------------------------------------------
SN>> Представить деревья каким-нибудь одномерным способом, сортируя
SN>> вершины с общим предком в определенном порядке. Далее все сводится к
SN>> поиску подстроки в строке, для которого есть готовые алгоритмы на
SN>> любой вкус.
EV> Такой вариант у меня был. Только я до конца не решил, когда сортировать:
EV> то ли при построении дерева, то ли перед поиском поддерева. Что одно, что
EV> другое достаточно труднореализуемо (в смысле ресурсоемко ;),
Если алгоритм поиска подстроки - из тех, что просматривают строку более или
менее последовательно, то можно не строить заранее полную одномерную копию
дерева, а использовать буффер размером порядка максимума из числа вершин
поддерева и максимальной степени вершины дерева.
EV> а операций таких надо будет проводить достаточно много (к примеру,
EV> среди 50 деревьев найти такую пару, в которой одно дерево является
EV> поддеревом другого, модифицировать набор деревьев (их станет на одно
EV> меньше) и опять то же самое, пока будут находиться поддеревья).
Подозреваю, что все сильно от типа задачи зависит. Hапример, если набор
деревьев не сильно меняется со временем, и сами деревья не гигантских размеров,
то это расширяет круг возможных алгоритмов. Видел как-то в одной статье описание
алгоритма, строящего суффиксное метадерево суффиксных деревьев за линейное
время. Очень может быть, что с помощью такого алгоритма можно решить
вышеприведенную задачу.
EV> Может есть еще какие задумки?
Сюда, помнится, буквально на днях кто-то кидал ссылку на выборку из статей про
tree matching. Может, там что-нибудь подходящее есть.
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
