����� �� �����.



����������. ���� � �����. ������������� � �������

����������

������ � �������� ����������. ����� � �����

������ ���������� � �����������. �RC

������� � ��������� �����������. ��������

����� � �������, ��������,
�������������������


������ ���������.
����������� � ��������������


C�������� ������.
�������� ����������


AI, ��, ��������� ����

��������

����, � ��� � ���� ���������

������


����: �������� PS � PDF ������

   �������� ���-�������
   �������� ������� �����

����� � �������, ��������, �������������������.

����� ���������������������, ���������.

�����������.

C����� x ����� |x| = m ������������ ��� x1x2 ... xm, ��� xi ������������ i-� ������ x.

�������� xixi+1 ... xj ������ x, ��� i<=j<=m, ����� ������������ x(i,j). � ������, ����� i>j, ���������� ��������� ������������ ��� xR(i,j).

����� x ����� ���������� ������� �������, � y � ��������� ������; |x| = m, |y| = m �, �������, m<=n.

������:

x = trismegistus
|x| = 12
x(7,10) = gist
xR(7,4) = gems

���������� ����� ��������.

������� �������, ���������� ����������, ��� �������, ������������ � ����� ������ �������� � ����� ������������ ��� ������ �������� ���� ��������. ����� ������� ��������� ��� ����������� ���� ����� ���� ���������, ���, ��������, � ������������� ������� ��� ������������� �������� � ���������� ������� �����������.

����� � �����, d - �������.

��� ��������� �����, ������, ������� �� ������ ������� ������� �������, �������� �� ��, ��� ���� �������� �������� ���. ����� ����, ����� ��������� ���������� ������ ������ �����. ������� ��� ��������� ����� ������ ���������� �������, ����������� ������������ ��������� �������������� ����� ������ � ������. � ����� ������, ��������� ��������������, ������������ � ���� ��������������, � ������ ������ ��������, �� ������� � ��������, ����� ��������� ������ ����. ��������� ��� �������� ������ ���������� � ���� � �������� ������� (indel; �� insertion � deletion).

���������� �������� [Hamming, 1982] ����� ����� �������� ���������� ����� ������������ ��� ����� �������, � ������� ������� �� ���������. ��� ������������ ����������� ���� �������������� ������ ������ �� ������ � ������, ����� ��������� ������ �������� ������ � ��������� �����. ���� ����������� ��������� ����� ������ �����, ��, ��� �������, ��������� ����� ������� � ��������.

���� ������� �� ��� �� ���, ��� � ������, ����������� ����� ���� �������������� ����� ����� ����� �� ������, ������������ ������������ [Levenstein, 1965]. ������ ������� ����� ����������� ���� �������������� � ������, ����� ��������� ������ ������� � ��������. ��� ������������ ���������� ���� 1 �������� � �������, � 2 ������, ��� ��� ��������� ����� �������� ����� �������-��������. ������ �� ���� ������ �� ���� �������� ����������� �����������, � ������ � ����������� ��������������.

������ � ���������� ����� ��������.


��� ������ ����� xy, ��� |x|, |y| > 0, � ������� d, �������� ���������� ����� ��������, ��������� d(x,y).

� ������ ������ �������� ����� ������� xy ����� xi ��������� i-� ������ x, � ����� yjj-� ������ y. � ���� ������ ��������� ���������� ����������� ������������������ �������� ��������������, ������������� xy.

�� �������� ����������� ������� ���� ��������zip ������� ��������� �� ��, ����������� ��������� �����������, � ���������� ����� ������� ������ �� ������ ���� ����������� �������� �� ������.

����� �������� ��������zip ��������� �� ��++, ����������� ��������� ��������������.

�������� ��� ������� ���� �������� ����������� ����� ������� � ����������� ���������� ����� ���������������������, ������� ����� ���� ������.

������ � ���������� ����� ���������������������.


�������, ��� ��������������������� ������ ���������� ����� ���������� �� ��� ���� ��� ����� ��������, �� ����������� �������. ����� ��������������������� ���� ����� � ��� ������, ���������� ���������������������� ������ �� ���. ����� ������� �� ����� ����� ����������, �������� ����, ����� ������� ����� ����������������������.

����, ������ ������� � ���, ����� ��� ������ ����� xy (|x|, |y| > 0) ����� |lcs(x,y)|, ��� lcs(x,y) � ����� ������� ����� ��������������������� (longest common subsequence) xy. ��� �������, ��������� ����� �� ������ ����� lcs(x,y), �� � ���� ��� ������������������.

���� ��� ���������, �� �������� ������� �������������, � �� �������� � �������� ������� �������, ������ �������� �������� �������� ���������� lcs, �� �������� ����.

����� ����������� �������� �������.

����� ������������� ���������������� ������� � ������ ����� � ����������, ������ ������� ������������ ������ ������� � ������.

�� ���� ������� � ���, ����� ��������������� ��������� ���������� ����� ��� ����� �������� ���������� ����� � �� ��������� �������������� ����������. ������������� ���������� ����������� ���������� � �������� � ������� ����� (m+1) * (n+1), ��� �������� � ������� � ������ O(mn). ����� ������� � ������ ��������� ��������� lcs ����� �� ������������ ������� ����������.

������ ��� ������� ���������� ��������������� ������ ��������� � �������� ��������.

� ��� ������ ���������� ����������� ����� lcs ��������������� ��������������� ��������� �����, � �� ���������� ����� ����. �������� ������ ���������� �� ���� ����, ��� � ������ �������� ������ ������� � ������ �������� ������ ��� ������ �������, ���������� ������������� ����������������. ������ ��������� ����� �������, ������, �������� � ����� �������� ������ ��������� lcs ���� �����. ������������ ���������� ������ ������� ������ ������ � �������� ��� lcs � ��� ������ �������� � ���������� ��������� ������ ������. �������� �������������� �� ��� ���, ����, � ����� ������, ��������� lcs �� ������ �����������. ������������� lcs ������ ����� ����� ����� ���������� ������� ������������� ������ �����, ���������� �� ����� ��������.

������, �������� �����-���������� �� ������ ����������� ����� ����������� ����� ������� �������������, ������� ����������� ����� ����, ��� � ������ ������ ��������� ��������� ���������� ������ ������������.

������ � ��������� lcs ���� ����� ������������ ����������� ������ �������� ��������� ������������� ���� �� �����, ������������ �� ����� (i,j), �����, ��� xi = yi. � �� ����� ��� ��������� ������� ������ ��������� ������������ �����, ����� ����� ��������� ��� ����� ���������� ����� � ����� ���� O((r+n) * log(n)), ��� r � ����� ����� ������������� ��� �������, � ������� ������� ���� ����� ���������. � ������ ������ ����� ������������ ���������� ������ ������� x � ������ �������� y, ��� �������� � n2 ����� ������������� ��� � ��������� O(n2 * log(n)). ������, �� ������ �����������, ��������, � ������ ������ �������� � ������, ��� ������ ������ ����� ����������� ������� ������, ����� �������, ��� r ����� ������ � n, � ��� ���� ������������� O(n * log(n)) � ������������ ��������� �� ��������� � �����������, ���������� ������������� �������.

�������� ������ � ��������� � ������������ �� ��������� ����������, �������� � ������ ������ ��������� ��������������� �����.

����� ������, ������, ���������, ����� ������� ��� ��������, � ������� ���� � ������ ����������� �������������� ��������������� �����. �������� ���������� ����� '������� �������' [���������, �����, ������� � ��������, 1970], ��� ����� � ������ ������ ����� O(n2/log n) � ��� ����� ������ �����. �������� ���� ����� ������ ������� � ��������� ������� ���������� �� ������������ ���������. �� ������ � ������ ���� ����� ����� ��������� �� ����������� ����� ���������, ����������� � ������� ������ � �����, � ��������������� ���������� xy, � ������� �������������� ����������� �������. ���� �������������� ���� �������� ������� �������� ������������� ����������������, ����� � �������� [Masek, Patterson, 1983) ���������, ��� ��� ������� ������������ ������ ��� ������� �����; ��������, ��� ���������� ���������� �������������� ����� ����� ��������� �������� �� ���������� ��-���������� �������, ������ ����� ����� ����� ����������� 262418.

������, ����� ��� ������������ ������ ������, �� ���� ����� d ����, ����� ����� ��������.

� ������ ��� ������ ����� ����� ���� ����������� ���� �� �����, ������� ��������� �� ������ ������� ����������, � ����� ��������������, ������������ � ������������ �����, ��������������� ������ ����� �������� ������. ��������� ���� ���������� � (0, 0) � ������������� � (m, n).

  • ������������ �����English pdf ������ lcs: ���� ���� ��� ������ � ������� m � n: m<=n, �� �� mn ����������� �� ����������� O(logm) ��������, � � ����� ����������� ������ - �� O(log2m) ��� mn/log2m �����������.

    ����� ������� ����� ��������������������� (heaviest common subsequence, hcs) � ��� ������������������, ����� ��� xy, ������� ��� ������ ������� ������� ������������ ����� ����� ���������. � ����� ������, ������� ����� �������� ��� �� ����� ��������, ��� � �� �� ��������� � �������� �������.

    ����� ������� ������������ ��������������������� ( lis ) � ��� ������������ ��������������������� �����, ���������� �������, ��� �������� �������� ������������ ��������, ������ ����������, � ����� ������� ������������ ��������������������� ( his ) � ��� ������������ ��������������������� � ������������ �����.

    ��������� ���������� ���� ����������������������



  • SpyLOG