Относительная сложность. Колмогоровский подход

1. Относительная сложность. Колмогоровский подход

Kolmogorov defined the complexity of an object as the length of the
shortest description K(S) by which the original object can be uniquely
reconstructed. When there are two objects (texts S1 and S2), we can speak
about the quantity of information about S1 contained in S2. This quantity
can be regarded as the relative complexity K(S1/S2) of reconstruction of S1
by S2.
K ( S1 ) K ( S1 / S 2 )
d K ( S1 , S 2 ) 1
K ( S1S 2 )
M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitányi: The Similarity Metric // SODA.- 2003- P. 863-872

2. Относительная сложность. Обобщение подхода Лемпеля-Зива

S2:
S1
• Представление S1 в виде конкатенации фрагментов из S2 назовем
сложностным разложением S1 по S2.
• Разложение S1 по S2 строится слева – направо.
• На каждом шаге копируется максимальный фрагмент S2,
совпадающий с префиксом непокрытого участка S1
• Если такого фрагмента нет, используется операция генерации
символа
• c(S1 / S2) – сложность S1 относительно S2 определяется числом
компонентов в разложении S1 по S2
2

3. Относительная сложность и редакционное расстояние

S2
= aaaa a cccc c ttttttttttttt – acacacac a atatatat
S1
= aaaa g cccc g ttttttttttttt g acacacac g atatatat
d(S1,S2) = 4
H(S1/S2) = aaaa*g*cccc*g*ttttttttttttt*g*acacacac*g*atatatat
c(S1/S2) = 9
S2 =
S1 =
–––––---tttttttttttttttttaaaaaaaa
aaaaaaaattttttttttttttttt––---–––
d (S1 , S2) = 16
H(S1 / S2) = aaaaa * ttttttttttttttttt
с (S1 / S2) = 2
c (S1/S2) 2d(S1, S2) + 1
3

4. Трансформационное расстояние

S2:
S1
• Трансформационое расстояние и относительная сложность идейно
близки.
• Операция «вставка сегмента» используется, если посимвольная
генерация фрагмента «дешевле» его копирования.
• Порядок покрытия S1 предполагает оптимизацию по всем парам
межтекстовых повторов и промежуткам между ними. O(N6).
J.-S.Varré, J.-P.Delahaye, E. Rivals: Transformation Distances: a Family of Dissimilarity
Measures Based on Movements of Segments. // Bioinformatics 15(3): 194-202 (1999)
4

5. Инверсионное расстояние

1 2 i 1 i i 1 j 1 j j 1 N
1 2 i 1 j j 1 i 1 i j 1 N
• Инверсионное расстояние dI( , ) между последовательностями и
определяется минимальным числом инверсий, переводящих одну из
них в другую Задача вычисления инверсионного расстояния для
перестановок является NP-полной
• В случае "знаковых" перестановок существуют полиномиальные
решения
+1 [+2 4 5 ] +3 +6
→ +1 +5 +4 2 +3 +6
Hannenhalli, S. and Pevzner, P. Transforming Cabbage into Turnip (Polynomial Algorithm for
Sorting Signed Permutation by Reversals). Proc. 27th Ann. ACM Symposium on the Theory of
Computing, 1995, pp. 178–189
5

6. Точки разрыва

0 = 0 and N+1 = N + 1
and произвольные перестановки.
Разрыв между i = a и i+1 = b фиксируется, если в нет биграмм ab и ba.
= 0 | 6 4 | 1 8 5 | 3 | 2 9 7 | 10
= 0 | 5 8 1 | 2 9 7 | 6 4 | 3 | 10
r( , ) = 5
Пусть тождественная перестановка (1 2 … N).
Число точек разрывов (breakpoint distance) r( , ) определяется
количеством позиций таких что | i i+1| 1.
0 1 2 3 | 8 7 6 | 4 5 | 9 10
6

7. Инверсионное расстояние, число точек разрыва и относительная сложность

r( , ) 2dI( , )
Точки разрыва однозначно соответствуют границам
компонентов сложностного разложения, построенного с
использованием операций прямого и обратного копирования
r( , ) = с( / ) – 1
=123456789
H( / ) = 1 2 3 * 8 7 6 * 4 5 * 9
Сложностные разложения позволяют перейти от исходных
перестановок к "знаковым" и сократить размерность задачи
вычисления инверсионного расстояния
7

8.

Phylogenetic trees for 65 species of the genus Chironomus
C.agilis
C.agilis
C.agilis2
C.agilis 2
C.nuditarsis
C.sinicus
C.nudiventris
C.nuditarsis
C.entis
C.nudiventris
C.muratensis
C.entis
C.plumosus
C.muratensis
C.bonus
C.plumosus
C.sp.J
C.borokensis
C.borokensis
C.bonus
C.suwai
C.sp.J
C.behningi
C.suwai
C.sinicus
C.behningi
C.bernensis
C.bernensis
C.anthracinus
C.anthracinus
C.annularius
C.annularius
C.longistylus
C.longistylus
C.tenuistilus
C.tenuistilus
C.sp.Is
C.sp.Is
C.cucini
C.cucini
C.nigrifrons
C.nigrifrons
C.sp.Al1
C.sp.Le1
C.riihimakiensis
C.riihimakiensis
C.sp.Le1
C.fraternus
C.fraternus
C.jonmartini
C.jonmartini
C.beljaninae
C.beljaninae
C.aberratus
C.aberratus
C.sororius
C.sororius
C.albimaculatus
C.albimaculatus
C.trabicola
C.trabicola
C.esai
C.esai
C.tuvanicus
C.tuvanicus
C.sp.Al1
C.staegeri
C.fundatus
C.blaylocki
C.maturus
C.sp.B1
C.whitseli
C.utahensis
C.sp.B1
C.obtusidens
C.blaylocki
C.arcustylus
C.utahensis
C.sokolovae
C.obtusidens
C.acutiventris
C.arcustylus
C.heterodentatus
C.sokolovae
C.atrella
C.acutiventris
C.fundatus
C.heterodentatus
C.maturus
C.atrella
C.whitseli
C.heteropilicornis
C.heteropilicornis
C.pilicornis
C.pilicornis
C.crassicaudatus
C.novosibiricus
C.staegeri
C.dilutus
C.novosibiricus
C.tentans
C.dilutus
C.pallidivittatus
C.tentans
C.setivalva
C.pallidivittatus
C.crassicaudatus
C.setivalva
C.yoshimatsui
C.yoshimatsui
C.piger
C.piger
C.riparius
C.riparius
C.acidophilus
C.aprilinus
C.alluaudi
C.pseudothummi
C.melanescens
C.acidophilus
C.pankratovae
C.melanescens
C.aprilinus
C.pankratovae
C.pseudothummi
C.alluaudi
C.dorsalis
C.dorsalis
C.luridus
C.luridus

9.

Расстояния и меры сходства, отличные от ред. расстояния
Пусть T1 и T2 два текста.
Назовем совместной частотной характеристикой l-го порядка
текстов T1 и T2 совокупность элементов
l (T1, T2)= { l1(T1, T2), l2(T1, T2), …, l Ml (T1, T2)}
где Ml = Ml (T1, T2) — число l-грамм, общих для обоих текстов,
а элемент l i (1 i Ml) есть тройка:
<< i-я общая l-грамма – xi,
частота ее встречаемости в T1 – F(T1, xi) и в T2 – F(T2, xi) >>.
Простейший набор мер сходства, упорядоченный по возрастанию l
имеет вид:
,
M l (T1 , T2 )
ql (T1 , T2 )
M l (T1 ) M l (T2 ) M l (T1 , T2 )
l = 1,2,…,lmax(T1,T2)
9

10.

Мера сходства, учитывающая частоты встречаемости
подслов:
min F (T1, ), F (T2 , ) | |
(T1 , T2 )
max F (T1, ), F (T2 , ) | |
– произвольная цепочка символов из текстов T1 и/или T2,
| | – ее длина.
(Findler N.V., Van Leeuten, 1979)
10

11. Ранговые меры близости. Коэффициент корреляции τ

S
1
2 n( n 1)
n 1
S
n
g (i, j )
i 1 j i 1
1, если r (T1 , xi ) r (T1 , x j ) & r (T2 , xi ) r (T2 , x j )
g (i, j ) 1, если r (T1 , xi ) r (T1 , x j ) & r (T2 , xi ) r (T2 , x j )
1,
в остальных случаях
ученики
А В С D
математика
7 4 3 10 6 2 9 8
1 5
музыка
5 7 3 10 1 9 6 2
8 4
E F G H I J
3
1
0,07
2 10 9
11

12. Ранговые меры близости. Коэффициент корреляции τ

S
1
2 n( n 1)
n 1
S
n
g (i, j )
i 1 j i 1
1, если r (T1 , xi ) r (T1 , x j ) & r (T2 , xi ) r (T2 , x j )
g (i, j ) 1, если r (T1 , xi ) r (T1 , x j ) & r (T2 , xi ) r (T2 , x j )
1,
в остальных случаях
ученики
А В С D
математика
7 4 3 10 6 2 9 8
1 5
музыка
5 7 3 10 1 9 6 2
8 4
ученики
I
F С B J E A H G D
математика
1
2 3 4
5 6 7 8
9 10
музыка
8
9 3 7
4 1 5 2
6 10
E F G H I J
3
1
0,07
2 10 9
S (2 7) (1 7) (5 2) (1 5) (3 2) (4 0) (2 1) (2 0) (1 0) 3
12

13. Ранговые меры близости. Коэффициент корреляции τ

Пусть l-граммы в l(T1) и l(T2) упорядочены по убыванию частот.
Порядковое место l-граммы xi в упорядочении определяет ее ранг –
r(T1 , xi) (соответственно, r(T2 , xi)).
n 1
n
S g (i, j )
S
1
2 n( n 1)
i 1 j i 1
1, если r (T1 , xi ) r (T1 , x j ) & r (T2 , xi ) r (T2 , x j )
g (i, j ) 1, если r (T1 , xi ) r (T1 , x j ) & r (T2 , xi ) r (T2 , x j )
1,
в остальных случаях
xi
а
c
g
t
f(T1 , xi)
123
101
98
37
r(T1 , xi)
1
2
3
4
f(T2 , xi)
147
211
988
1137
r(T2 , xi)
4
3
2
1
6
1
1
4(4 1)
2
13

14.

Ранговые меры близости. Коэффициент Спирмэна
6S (T1 , T2 )
(T1 , T2 ) 1
;
2
n(n 1)
n
S (T1 , T2 ) r (T1 , xi ) r (T2 , xi )
2
i 1
ученики
А
В
С
D
E
F
G
H
I
J
математика
7
4
3
10
6
2
9
8
1
5
музыка
5
7
3
10
1
9
6
2
8
4
Разности d
2
-3
0
0
5
-7
3
6
-7
1
d2
4
9
0
0
25
49
9
36
49
1
6 182
(T1 , T2 ) 1
0,103;
990
14

15.

Ранговые меры близости. Коэффициент конкордации W
W используется для сравнения m последовательностей.
Вычисляем суммы рангов каждого объекта
m
SR( xi ) r (Tk , xi )
k 1
Среднее значение суммы рангов одного объекта составляет ES = m(n+1)/2.
n
S ( SR( xi ) ES ) 2
S – сумма квадратов отклонений от ES
i 1
12S
W 2 3
m ( n n)
Равночастотным l-граммам назначаются усредненные ранги и в
определения , , W вносится поправка на "связанность".
W
S
1
12 m ( n n) m T '
2
3
T'
T ' 121 (t 3 t )
t – число элементов в одной группе.
t
W, в отличие от и изменяется от 0 до 1.
15