4817
правок
Поддерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
м
Поддерево максимального соответствия (посмотреть исходный код)
Версия от 11:38, 22 сентября 2015
, 22 сентября 2015→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 51: | Строка 51: | ||
Задача нахождения поддерева максимального соответствия естественным образом возникает в биологии и лингвистике; она описывает меру соответствия между двумя эволюционными деревьями видов и языков, соответственно. Эволюционное дерево для набора таксонов (видов или языков) представляет собой корневое дерево, листьями которого являются таксоны, а внутренние вершины содержат информацию о предках. Определение истинного филогенеза набора таксонов нередко вызывает трудности, и одним из вариантов обретения уверенности в правильности конкретного дерева может стать получение нескольких наборов данных в поддержку этого дерева. В случае биологических таксонов можно построить деревья из различных отрезков ДНК нужных видов, называемые деревьями генов. По многим причинам полное согласование таких деревьев невозможно, так что остается задача нахождения консенсуса между различными деревьями генов. Одним из способов нахождения такого консенсуса является поиск поддерева максимального соответствия. Заметим, что дерево генов обычно является бинарным, поскольку репликация ДНК представляет собой процесс бинарного ветвления. Таким образом, случай бинарных деревьев представляет особый интерес. | Задача нахождения поддерева максимального соответствия естественным образом возникает в биологии и лингвистике; она описывает меру соответствия между двумя эволюционными деревьями видов и языков, соответственно. Эволюционное дерево для набора таксонов (видов или языков) представляет собой корневое дерево, листьями которого являются таксоны, а внутренние вершины содержат информацию о предках. Определение истинного филогенеза набора таксонов нередко вызывает трудности, и одним из вариантов обретения уверенности в правильности конкретного дерева может стать получение нескольких наборов данных в поддержку этого дерева. В случае биологических таксонов можно построить деревья из различных отрезков ДНК нужных видов, называемые деревьями генов. По многим причинам полное согласование таких деревьев невозможно, так что остается задача нахождения консенсуса между различными деревьями генов. Одним из способов нахождения такого консенсуса является поиск поддерева максимального соответствия. Заметим, что дерево генов обычно является бинарным, поскольку репликация ДНК представляет собой процесс бинарного ветвления. Таким образом, случай бинарных деревьев представляет особый интерес. | ||
Еще одним возможным применением является автоматический перевод между двумя языками [10]. Два дерева представляют собой деревья разбора для утверждений с одним и тем же значением на двух языках. Сложность в данном случае связана с несовершенством словарных определений; она заключается в том, что слова не обязательно должны иметь уникальную пару, т.е. слово в листе первого дерева может соответствовать нескольким (обычно их число невелико) словам в листьях второго дерева. Цель состоит в нахождении поддерева максимального соответствия; затем оно будет использоваться для улучшения контекстно-зависимых словарей при автоматическом переводе. В случае, если каждое слово в одном дереве имеет константное число соответствий в другом дереве (возможно, с учетом различных весов), можно использовать вышеприведенный алгоритм, и продолжительность его работы останется равной O( | Еще одним возможным применением является автоматический перевод между двумя языками [10]. Два дерева представляют собой деревья разбора для утверждений с одним и тем же значением на двух языках. Сложность в данном случае связана с несовершенством словарных определений; она заключается в том, что слова не обязательно должны иметь уникальную пару, т.е. слово в листе первого дерева может соответствовать нескольким (обычно их число невелико) словам в листьях второго дерева. Цель состоит в нахождении поддерева максимального соответствия; затем оно будет использоваться для улучшения контекстно-зависимых словарей при автоматическом переводе. В случае, если каждое слово в одном дереве имеет константное число соответствий в другом дереве (возможно, с учетом различных весов), можно использовать вышеприведенный алгоритм, и продолжительность его работы останется равной <math>O(n \; log \; n)</math>. В более общем случае, если допускается m сопоставленных слов, время работы алгоритма составит <math>O((m + n)\; log \; n)</math>. Заметим, что при наличии двух наборов слов с равными значениями в двух деревьях размеров <math>k_1 \;</math> и <math>k_2 \;</math>, соответственно, они порождают <math>k_1 k_2 \;</math> сопоставлений. | ||
== См. также == | == См. также == | ||