Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 30.09.2005, 10:30   #1
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Distance between trees

A teper sovsem netrivialnyj vopros: kto nibud znaet metod sravnenia derevyev? Prichem derevya ne binarnye, a s proizvolnym kolichestvom vetvey u uzla. Pod sravneniem imeetsa vvidu ne prosto proverka na odinakovost, a izmerenie distancii, tak chtoby potom sgenerirovat phylogeneticheskoe derevo. Budu vesma blagodaren za otvet.
Reply With Quote
Old 30.09.2005, 14:55   #2
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

а ты $дистанцию определи, а потом подумаем
Reply With Quote
Old 01.10.2005, 11:24   #3
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

OK, popytayus popodrobnee:

1. Trees are lebelled, rooted, n-degree.

2. They're not ordered, but I think the branches of each node may be ordered according to any law (e. g. alphabetically)

3. Physically the leaves are species (substances) or reactions in a biochemical pathway. They may be treated as symbols of an alphabet, but the alphabet is endless (as anything in the nature). Hence, I can't use a predefined distance matrix, I have to develop a function for counting distance. The simplest law is the following: 0 for match, 1 for mismatch, deletion or insertion. The more sophisticated functions take into account the similarity degree between mismatching nodes. Actually, any distance-calculating rule may be used, as soon as you have an algorithm to compare the whole trees

P. S. Now I've got an idea, but I would like to address the community at first, to find out if anything suitable exists already. Discovering America is an unthankful job But all I've found so far is for binary trees.
__________________
Она нахмурила свой узенький лобок...
Reply With Quote
Old 01.10.2005, 21:46   #4
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

так, давай тогда разбираться.

пусть мы сравниваем узлы дерева (FOO и BAR)

1. если $FOO и $BAR содержат только листья и мы их сравниваем - то дистанция равна дистанции Левинштейна(число операций insert/delete).

2. думаем - если $FOO в данной позиции [1,n] имeeт поддерево , а $BAR - нет, то как мы считаем дистанцию? можно посчитать ее как num_elements($FOO[i]) -- в случаем если требовать, чтоб поддеревья всегда находились в нужной позиции узлов, которые мы сравниваем, а можно посчитать по-другому, постараться найти такое поддерево $BAR, которое совпадает с поддеревом $FOO и найти количество операций insert/delete для того, чтоб его привести в нужную позицию.
вобщем вот тут по-моему и проблема. после того, как ты точно определишь, что ты считаешь дситанцией между поддеревьями - реализация станет простой и ясной.

примеры:
Reply With Quote
Old 01.10.2005, 21:57   #5
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

если я все правильно посчитал , то просто для узлов только с листьями:

FOO = [ a, b, c ], BAR = [ ] -> distance = 3
FOO = [ a, b, c ], BAR = [ a, a, b, c ] -> distance = 1
FOO = [ a, b, c ], BAR = [ b, c, a ] -> distance = 2 (убираем один силвол в начале, добавляем один в конце)


FOO = [ [a], [b], [c] ], BAR = [ а, [b], [c] ] ->
вариант 1 - distance = 2 (убираем дерево [a], добавляем символ)
вариант 2 - distance = 3 (убираем символ из под-дерева [a], убираем пустов поддерево, добавляем символ)

FOO = [ [a], [b], [c] ], BAR = [ [b], [c], [a] ] ->

вариант 1 - distance = 2 (убираем под-дерево [a], добавляем под-дерево [a] в конце)
вариант 2 - distance = 4 (убираем символ из под-дерева [a], убираем пустов поддерево,
добавляем пустое под-дерево, добавляем символ а)

мне лично по душе вариант 2 -
при подсчете дистанции между поддеревьям - разрешены только операции
удалить символ, добавить символ и удалить пустое дерево, вставить пустое дерево.

не обосновывая - такой набор операций кажется мне более простым в реализации и более логичным
Reply With Quote
Old 02.10.2005, 14:44   #6
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

1. Возможно ли нарушение иерархии? Например у узла X два сына, а у каждого из них по три. Теперь в другом дереве у узла X сразу 6, во всем остальном деревья одинаковы - теперь насколько они похожи? Например, в случае биологии не знаю, для сравнения схем - они одинаковы.
2. Глобально, если возможны так же ротации - то NP полная задача.
Reply With Quote
Old 03.10.2005, 13:06   #7
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Спасибо, nm и Виктор! Я честно говоря и не ожидал получить столь подробные ответы Тогда подумаем дальше?

>Возможно ли нарушение иерархии? Например у узла X два сына, а у каждого из них по три. Теперь в другом дереве у узла X сразу 6, во всем остальном деревья одинаковы - теперь насколько они похожи? Например, в случае биологии не знаю, для сравнения схем - они одинаковы.

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

>Глобально, если возможны так же ротации - то NP полная задача.

Если я правильно понял вопрос:

((a, b), (c, d)) и ((d, c), (b, a)) - идентичны.Играет роль лишь иерархия, а не последовательность детей у одного узла (tree is unordered). я тоже читал, что проблема в данном случае NP-complete, а что если произвольно упорядочить деревья, хотя бы по алфавиту?

>если $FOO и $BAR содержат только листья и мы их сравниваем - то дистанция равна дистанции Левинштейна(число операций insert/delete).

Да, и как я понял, сувествующие алгоритмы основаны на определении editing distance (к сожалению full text стоит денег).

>постараться найти такое поддерево $BAR, которое совпадает с поддеревом $FOO

Вот тут то и вся загвоздка Я тоже начал мыслить в этом направлении - находить ”соответствующие” друг другу поддеревья и сравнивать их. Но во первых, нахождение таковых выливается в самостоятельную, тоже нетривиальную подзадачу. Во вторых, в случае если дистанция заведомо большая, возможно что никаких схожих поддеревьев и нет вовсе, а схожести равномерно ”размазаны” по дереву. Остается одно - сравнивать все со всем, то есть global seqeunce alignment. Вопрос в том, как представить дерево в виде линейной последовательности. Хочу попробовать что то вроде recursive dynamic programming. Типа: если на одном уровне сравниваются два листа, то просто дистанция между ними. Если лист и узел - идти вглубь и сравнивать лист со всеми его подузлами, а в таблицу вставить - пока неясно, alignment score, или среднюю дистанцию (или ???). Если два узла - опять же - на один уровень вглубь и снова сравнивать.Насчёт сложности всей этой хрени пока подробно не думал, но по моему квадрат, как и при обычых строках.

Last edited by Ablertus; 03.10.2005 at 14:04.
Reply With Quote
Old 03.10.2005, 15:04   #8
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Вот кстати статья, где эта хрень описана в подробностях

http://www2005.org/cdrom/docs/p76.pdf

Но боюсь, что некоторой модифицации подвергнуть все таки придется.
Reply With Quote
Old 15.11.2005, 19:49   #9
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

V poslednij raz byl zdes' bol'she mesjaca nazad. Neuzheli na etom forume algoritmy nikogo ne interesujut?
Reply With Quote
Old 15.11.2005, 20:32   #10
(vagabond)
 
Gypsy's Avatar
 
Join Date: 12 2004
Location: Himalayas
Posts: 823
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by Ablertus
V poslednij raz byl zdes' bol'she mesjaca nazad. Neuzheli na etom forume algoritmy nikogo ne interesujut?
You must be more specific:

Quote:
I have to develop a function for counting distance. The simplest law is the following: 0 for match, 1 for mismatch, deletion or insertion. The more sophisticated functions take into account the similarity degree between mismatching nodes.
A simplest algorithm that would do this wuold just give you the percentage of matching subtrees. Very simple and works fine.

update:
-----------------------------

Compare(Tree1, Tree2):

if (Tree1 and/or Tree2 are Atomic): specific application-dependent comparison here, return 0 for total match, 1 for total mismatch

take all subtrees of Tree1: {S1, ..., Sn}
take all subtrees of Tree2: {P1, ..., Pm}

(it'd be better here if your subtrees in each node had a specific order)
(if not, the most general and least effective algorithm goes as follows)


Calculate a matrix (Cij), where Cij = Compare(Si, Pj)
For simplicity, most elements can be assumed to be 0 without calculation (how you do this depends on your application).

Find non-repeating indexes I1 ... Im that would minimize the sum:
Sum( C(Ij,j), j = 1..m )

I assumed n >= m, the opposite case is symmetric. In case n = m, and if the subtrees are somehow ordered, you could just take I1 = 1 ... In = n.

Store that minimal sum found in M

return (M / m)

-----------------------------

Now your goal is to reduce the number of recursive calls, which you can do if you have specific knowledge about the subtrees, how they are stored, if they are somehow sorted or not, etc.

Last edited by Gypsy; 15.11.2005 at 21:07.
Reply With Quote
Old 15.11.2005, 20:46   #11
(vagabond)
 
Gypsy's Avatar
 
Join Date: 12 2004
Location: Himalayas
Posts: 823
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

One general trick that would largely reduce the number of comparisons is to store the height of each subtree, and compare only those subtrees whose heights are the same (or, say, differ insignificantly, depending on your application).

Last edited by Gypsy; 15.11.2005 at 21:14.
Reply With Quote
Old 16.11.2005, 16:47   #12
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Thanks!
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 21:33.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.