|
����� � �������, ��������, �������������������:
����� ���������������������, ���������.
����� ������� ����� ���������������������.
���� ������ �������� hcs ���������� � �� [Jacobson, Vo, 1992], ���������� �� ��������� ������ ����� ������� ������������ ��������������������� (lis) ���������-�������� [Schensted, 1961]. ������������� ����� ��������� �������������� � � ��� ���������� ���������� ������������ ������, ������������ � ����������.
������ �����, ��� ����� ��� ����� x � y ��������������������� s ����� ���������� ��������� �������:
|
(57)
|
��� (ip, jp) � ���� �������������� �������� �� x � y, �� ���� , � f � ������� �������.
��� ���������� hcs ����� ������������ ����� ������������� ����������������. ��������� W(hcs(x(1, i), y(1, j))) ��� Wi,j. ����� ������������ ����������� ��� Wi,j �������� ��������
Wi,j = max{Wi-1,j, Wi,j-1, Wi-1,j-1 + fi,j}
|
(58)
|
����������� ������� �� ������ ���������� ������� l. � ������� (i, j), �� ���� ����� ��������������� �������� x(1, i) � y(1, j), ���� xi = yj, ����� ����� ��������������������� ����� �������� ����������� ����� ������� � ������� ����� ��������������������� ����� x(1, i - 1) � y(1, j - 1), � �� ��� � ����������� ���� ����� ������������� � ���� ������� ����� ���������������������. � ��������� ������ ������� (i, j) �� ������ ���������� ���������. ����� �������, ��� ��� ������� (i, j) �������� ����� ������� �� ���������� �������� ������� �, ��� ������������ ��������, ����� ���������� �����.
�������� ����������-�������� ��� ���������� lis ������ y ����������� �� ������� 21. L � ��� ������������� ������ ��� (a, k), ��� a � ������ ������, � k � ��� ����� � ������. ������ �� ��������� �������� ����� ���� ��������� �� ����� O(log n), ����� L ����������� � ������� ����������������� ������.
insert(L, a) - �������� ������ a � ������ L
delete(L, a) - ������� ������ �� ������ L
next(L, a) - ���������� ���������� �� ������ ������� a �������� � L
prev(L, a) - ���������� ���������� �� ������ ������� a �������� � L
max(L) - ���������� ���������� ������ � L
min(L) - ���������� ���������� ������ � L
����� ������ �� ����������, ��������� next , prev , max � min ���������� ������� ��������. �������� next(L, null) � prev(L, null) �������� �������, ��������������, min(L) � max(L) .
��� ������� ������� yj ����� a ��������� ������ � L, ����� �������� ����� �������� yj, �� ������� ������ ������������ ������� � ���� ������. �������, ������� � L ����� a ��� ���� ���������� �� yj. ������������ ���� �������� ������ ��������� � ������� ������� node (����). ���������� node �������� ��������� �� ����, ��������� ���������� newnode, � ���������� ������, ��� ����� � ������ � ����� ����������� ����. �� ���������� lis ������ y ����� ���������� �������� ��������� � ����� - ������� � ������������� ���������� L.
- ������������� ������ L
L = null
���������� lis
for i = to n
(a, k) = prev(L, (yi, 0))
(b, l) = next(L, (a, k))
if b =/=null
delete(L, (b, l))
(L, (yi, i))
nodei = newnode((yi, i), nodek)
������� 21: ���������� lis �� ���������-��������
- ������������� ������ L
L = null
- ���������� his
for i = 1 to n
(a, u, k) = prev(L, (yi, 0, 0))
(b, v, l) = next(L, (a, u, k))
while ((b, v, l) =/=null) and (u + f(i, yi) > v)
delete(L, (b, v, l))
(b, v, l) = next(L, (b, v, l))
if ((b, v, l) = null) or (yi < B)
INSERT(L, (Yi, u + f(i, yi), i))
nodei = newnode((yi, u + f(i, yi), i), nodek)
�������� ��������, ��� and � ����� while �������� ��������, �.�. ������ ������� �����������, ������ � ������, ���� ������ �������� ��������.
������� 22: ���������� his �� ����������-��
��� ���������� his ����������, �� ���� ������ ���������, ������������ ������������ ����� ���� his ��������������� ������������ ��������� �����. ������������ L, ����� �������, ����� ������� ������ (a, u, k), ��� a � ������ ������� ������, u � ����� ��� his, ��������������� �������� a, � k � ����� a � ������. L �������� ������ ���������� �� ���� ���� ����� �����������. ������� ������� � L ����� ������������ ��������������� ����������� ������� ������ ��������� ����.
�������� ���������� his, ���������� �� ��������� ��� lis, �������� �� ������� 22. ����� a ���������� ���������� �� ������� yi �������� � L, ��� ��� ��������� ����� �������� � ����� ������������ ���������������������, ��������������� �������� a, � ����� �������� ������������ ���������������������. ���� ����� a ���, �� u ������� ������ 0. ���� while ������������ ����������� ������� ������������ ������� �������� ������. ����� ����� ������ ����������� � ������ L, ���� ��� ����������� �� ������� ������������ ������� �������� �����. ������ node ����������� ��� ���������� ��������� ��������� ��� ����������� ����������� his �� ���������� ��������.
���������� ��������� ������ L � ����� ������ ��������, ������������ Li. ��� ������ ���������� (a, u, k) �� Li ����� ���������� ������������ ������������������ �������� y(1, i), ��������������� a, ����� ��������� ������� �� ������� a � ������������ �����. ����� ����� ��������, ��� ��� ������ ������������ ��������������������� s(1, k) �������� y(1, i) ���������� ������� b ������ Li, �����, ��� b < sk, �.�. ����������� ������������ ��������������������� � �����, �� ����� �������, ��� s(1, k). ����� �������, ������������ ������ Li ������ � ������ ���� his �������� y(1, i). �������������, ������������ ������� L �� ���������� �������� ���������� his ��� ���� ������ y.
����������� ���� ����������� �������� ��������� ��� i = 1. �����������, ��� ��� ����������� ��� �������� i - 1, � ���������� �������� ��� �������� i. ����� s(1, k) � ��� ������������ ��������������������� ��� �������� y(1, i). �� ���������������, ���� sk = yi, �� � Li-1 ������� ������� b < sk-1, ������������ ������������ ���������������������, �� ����� �������, ��� s(1, k - 1). ����, ������� b �� ����� ���� ������ �� ������ �� ���� ��������, ��������� b < yi. � ����� i-� �������� yi ���� ����������� � ������, ���� ��� ��� ������������. �����, ��� ������������ ���� � L �������� ������ �������������, ����� ������, ��� ������������ ���������������������, ������������ yi, ������������� ���������� �������������.
������ �������� � ��������, ����� sk =/=yi. ����� ������� ��� �����������: sk < yi � sk > yi. � ������ ������ ������������� �����������, ��� ��� ����� ������, �������������� yi, �� ������������� i-� ���������. �������� ����������� ������, ����� sk > yj. ������������������ s(1, k) ����� ������ ���� ����� ������������ ���������������������� y(1, i-1). ����� �������, ������ ������������ ������������ ���������������������, ������������ ��������� b � Li-1, �� ����� �������, ��� s(1, k). ���� b ������� � Li, ������������� �������� �����������. � ��������� ������ b ������ ���� �������� �� L �� i-� ��������, ������ ������������ ������� ����� while �����������, ��� ������������������, ������������ yi, �������� �� ����� �������, ��� ����������, ������������ b. ����� �������, �� ��������, ��� ���� ������������� ����������� ��� ���� ���������������, ������� �������� ��������� ��������� his ������� ������.
�������� ���� ��������� ����������� n ���, ������ ������ �� ����������� � ��� �������� ������� �� ������ O(log n) �������. �������� ��������, ��� ����� ���������� �������� ����������� ����� while �� ��������� n, ��� ��� ������ �� n ��������� y ����� ���� �������� ��� ������ �� ������ L �� ������ ������ ����. ����� �������, ��������� ��������� ����� ��������� ���������� O(n log n).
i 1 2 3 4 5 6 7 8 9
Yi z e i t g e i s t
f(i,yi) 1 1 1 1 1 2 2 1 2
Li (z,1) (e,1) (e,1) (e,1) (e,1) (e,2) (e,2) (e,2) (e,2)
(i,2) (i,2) (g,2) (t,3) (i,4) (i,4) (i,4)
(t,3) (t,3) (s,5) (s,5)
(t,7)
������ ����� ������ ����� ����������������� ��������� ��������. ���� ��������� ���������� (a, u) ����� ������ L �� ������ ���� i ��� ������ y = zeitgeist. �������, ��� lis � ���� ������ �������� eigst. ������, ��� ������� ��������� ������� � ������ ���� ���������� ������� 1, � ��� ������� � ������� 2. ��� ���� �������� ������������ ��������������������� eist, ������������ ������ e � i, �������, ��� lis eigst. �� ���������� (t, 7), ������������ ������� L, ������������ ��� ����������� ���� e is t � ������������ �����.
������������ ����
null <--- (z, 1)
null <--- (e, 1) <--- (i, 2) <--- (t, 3)
|
�---<--- (g, 2)
null <--- (e, 2) <--- (i, 4) <--- (s, 5) <--- (t, 7)
���� ������������� (i, j) ����� �������� x � y �������� � ������� ����������� i � � ������� �������� j ��� ������ �������� i, �� ������ ����� ��������������������� ������� ������������ ��������������������� ������������������ �������� j. � ��������, ����� ��������������������� ����� ������� �� ������������ ��������������������� �������� j. ��������� ������� j ��� ���������� i ������������� ��������� � ��������������������� ���������� �������� y, �������������� ������ ������� x. ���� �������� ������ ��� ����� preterit � zeitgeist. ������������ ������� �������� lis ������������������ j, ��������������� lcs ���� ���� �����.
i 1 2 3 4 5 6 7 8
xi p r e t e r i t
- - - - -
j 1 2 3 4 5 6 7 8 9
yj z e i t g e i s t
- - - - -
�������������
i 3 3 4 4 5 5 7 7 8 8
j 6 2 9 4 6 2 7 3 9 4
- - - -
� ����������� ���� ������������ �������������, ��������������� ���� f(i, j, xi) ����� ��������� ��������� j. ����������� ��� �����, ����������� �� ������� 23, �������� ���������� ��������� lcs �����-����������. �������� ��������, ��� ��� �������� ����� �������� ������ ���������� (a, u) ����� ������ L.
������ position �������� ������������� ������ ������� ��������� �������� � y. ���� �� ����� �� matchlist ��������� �����-����������. ��������� ������� � ������� ��������, � �� ����� ��� ������ ������� positions ������ � ������� �����������. ���������� ������� ������������� ����������� ������������ ����� �� ������� j �� ������� ��� ������� i. � ���������� ������������������ �������� j ����������� �������� his. ��������������� hcs(x, y) ����� ���������� ����� ���������� �������� �� ������������� �����, ���������� �������� � ��������� ����� ������� ��� ��������.
- ���������� ������������� ������� ������� �������� � y
for i = 1 to n
- ������������� ������ L
L = null
- ���������� hcs
for i = 1 to n
while j =/=null
(a, u) = prev(L, (j, 0))
(b, v) = next(L, (a, u))
while ((b, v) =/=null) and (u + f(i, j, xi) > v)
delete(L, (b, v))
if ((b, v) = null) or (j < B)
INSERT(L, (J, U + F(I, J, Xi)))

�������� ��������, ��� and � ����� while �������� ���������
������� 23: ���������� hcs �� ����������-��
����� ����� ������������������� �������� j ����� ����� �������������, r. ����� ����� ������� ����� �� ������� ������ L, ������� ��������� ������ ����� �������� �� ���� ������� �����. ����� �������, ����� ����� ���������� ���������� O((r + m)log n).
��������� ������ ������������ ���������� hcs. ��� ����������� � ���������� �����, ������� ������� ������������ ���������� ����� ����������� ��� �������� ������������ ��� ������ ����� ���������������������� ��� ������ ����������� �������������. ���������� ���� ����� warfare � forewarn. ���� ��������� ����� ��������������������� ���� ���� ������ � �� ������ �������� ������� ������� ������������ ���������� 8 - |i - j|, ������� ������������� ������ ����������� �������������. ���� ���� lcs ������ � �������.
i 1 2 3 4 5 6 7
xi w a r f a r e
yj f o r e w a r n
j 1 2 3 4 5 6 7 8
xi w a r w a r w a r
i 1 2 3 1 2 6 1 5 6
j 5 6 7 5 6 7 5 6 7
8 - |i - j| 4 4 4 (12) 4 4 7 (15) 4 7 7 (18)
xi r a r f a r f r e
i 3 5 6 4 5 6 4 6 7
j 3 6 5 1 6 7 1 3 4
8 - |i - j| 8 7 7 (22) 5 7 7 (19) 5 5 5 (15)
�� �����, ��� ����� ������� �� lcs �������� rar. ��������� ������ L ����� ������� ����� i ���������� hcs(warfare, forewarn) ��� ������ ������������ ������� �������� ����, ������ ������������ ������������ ������. � ����� ��� �������� ������ ������ ���������� (a, u).
i 1 2 3 4 5 6 7
xi w a r f a r e
Li (5,4) (5,4) (3,8) (1,5) (1,5) (1,5) (1,5)
(6,8) (7,12) (3,8) (3,8) (3,10) (3,10)
(7,12) (6,15) (6,15) (4,15)
(7,22) (7,22)
������������ ����
null <--- (5, 4) <--- (6, 8) <--- (7, 12)
NULL <--- (3, 8) <--- (6, 15) <--- (7, 22)
NULL <--- (1, 5) <--- (3, 10) <--- (4, 15)
�� ���������� ������������ ������� L, � ������, (7, 22) ������������ ��� ��������� ���� 3 6 7 �� ������������� ����� �������� j � ������������ � ���������������������� rar.
������� ������� ������ hcs �������� ������, ����� ���� �� ������� �� �������, �� ���� ����� f �������� �������� ������ ��������. ���� ����������� ��������, ����������� ��������������� ��������� ���� ������� ������� ��������������.
����� ������� ������� �� ������� �� �������, ��� ����, ��������������� �������� j � ������ �����. ���������� ������, ����� ������ j ����������� � ������ L ����� a. ��������, ��� �������� j �� ������ ������� �������������� � ��������� �������, ������� ���� ��������� ������� �������� j ����� ������ a, �� ������ j ��������� �� ������, � �� ��� ����� ����������� �����, ��� ��� ��� ��� ����� ���� � ��� �� ���. ����� ����� ��������, ���� ���������� ����� � ����������� j � , �������� a. ����� �������, j ����� ��������� �������� next( , a) ����� ���������� (a, u) � (b, v).
���� j ��� ������������ � ������ L, �� b ������������� �������� j. ���� ���� � L, ��������������� �������������� j, ��� ��, ��� � ��� ������� j, �� �������� ������ ������ j �� L, � ����� ������ ������� ��� � �� �� �����. ����� �������, ����� ������� j ����������� � L, �� ����� ���� ������ �� �� ��������� ��������� ��������. ������, �� ������ ���� ������������ � ����� ������ �������, � ������ �������� �� ������ L ��� ��������� ��� ��������������� � ������ L.
- ���������� ������������� ������� ������� �������� � y
for i = 1 to n
- ������������� ������ L
L = null
- ���������� hcs
for i = 1 to m
while j =/=null
(a, u) = prev(L, (j, 0))
(b, v) = next(L, (a, u))
j = next( , a)
while ((b, v) =/=null) and (u + f(xi) > v)
delete(L, (b, v))
(b, v) = next(L, (b, v))
insert(L, (j, u + f(xi)))
delete( , j)

�������� ��������, ��� and � ����� while �������� ���������
������� 24: ���������� hcs �� ����������-�� ��� �����, �� ��������� �� �������
� �������, ����� ���� �� ������� �� �������, ������� ������� j � L ����� �� ���������. �������� b �� ����� ���� ������ j, ��� ��� a �������� ���������� �� ������� j ��������� ������ L. ����� �������, b > j. � ������, ����� b > j, j ����� �������� � L ����� a � b �� ������� ������������ ������. ���� b = j, j ����� ����� ��������� ������ b, ��� ��� �� ���� ���������. ������ � �����, ��� j ����� ������������ ��������� � L.
�� ������� 24 �������� �������� hcs, ���������� ��������� ���� ������������������ ��� ������ �����, �� ��������� �� �������; � ��������� ����� ��� �������� ������� ���������� ������������� ����� � ������� ������ ���� (a, u) ��������� ������ L. ���� ���� ���� �������� �������� �����, ���� �������� ������������ � �������� lcs ����������-������.
| |