Программирование, 2023, № 5, стр. 3-18

4.1. Число общих A-вложений

Здесь мы докажем теорему, аналогичную лемме 6 в [3], но дадим свое доказательство, поскольку мы используем другие определения и обозначения.

Для непустой последовательности z ∈ H* и символа h ∈ H обозначим максимальный индекс, по которому в последовательности z находится символ h, или 0, если h не входит в z:

p(z, h) = max{i ∈ 1..|z|: z_i = h}, если h ∈ Im z; p(z, h) = 0, если h ∉ Im z.

Обозначим: k = p(x[m – 1], x_m}, l = p(y, x_m}.

Теорема 1.

A₀(x, y) = A₀(x[m – 1], y), если x_m ∉ Im y;

A₀(x, y) = A₀(x[m – 1], y) + A₀(x[m – 1], y[l – 1]), если x_m ∈ Im y и x_m ∉ Im x[m – 1];

A₀(x, y) = A₀(x[m – 1], y) + A₀(x[m – 1], y[l – 1]) – ‒ A₀(x[k – 1], y[l – 1]), если x_m ∈ Im y и x_m ∈ Im x[m – 1].

Доказательство.

Рассматриваем множества пар (e_r(u, x), e_r(u, y)) самых правых E-вложений общих A-вложений u последовательностей x и y. Обозначим пары последовательностей длины m и n:

E = A_r(x, y);

E_m = A_r(x[m – 1], y)(ε, ());

E_ml = A_r(x[m – 1], y[l – 1])(x_m, x_mε^n–l), если x_m ∈ ∈ Im y, иначе E_ml = ∅;

E_kl = A_r(x[k – 1], y[l – 1])(x_mε^{m–k– 1}x_m, x_mε^n–l), если x_m ∈ Im y и x_m ∈ Im x[m – 1], иначе E_kl = ∅.

Поскольку для любых x', y' имеет место A₀(x', y') = = |A(x') ∩ A(y')| = |A_r(x', y')|, утверждение теоремы можно переписать в виде:

|E| = |E_m|, если x_m ∉ Imy;

|E| = |E_m| + |E_ml|, если x_m ∈ Imy и x_m ∉ Imx[m – 1];

|E| = |E_m| + |E_ml| – |E_kl|, если x_m ∈ Imy и x_m ∈ Imx[m – 1].

Поскольку E-вложения из множества E_m имеют вид (…ε, …), а множества E_ml и E_kl либо пусты, либо E-вложения из них имеют вид (…x_m, …), имеем E_m ∩ E_ml = E_m ∩ E_kl = ∅. Поскольку m – 1 ≥ ≥ k – 1, имеем E_ml ⊇ E_kl.

Рассмотрим случай x_m ∉ Im y. Поскольку x_m ∉ Im y, переход от последовательности x[m – 1] к последовательности x = x[m – 1]x_m не добавляет новых общих A‑вложений. Поэтому E = E_m. Отсюда |E| = = |E_m|, что и требовалось доказать в этом случае.

Рассмотрим случай x_m ∈ Im y и x_m ∉ Im x[m – 1]. Поскольку x_m ∈ Im y, переход от последовательности x[m – 1] к последовательности x = x[m – 1]x_m может добавлять новые общие A-вложения, эти общие A‑вложения должны заканчиваться на x_m, но этих общих A-вложений раньше, в x[m – 1] и y, не было, поскольку x_m ∉ Im x[m – 1]. Заметим, что для такого нового общего A-вложения u в его самых правых E-вложениях в x и y последний непустой символ равен x_m по индексам m и l, соответственно, т.е. e_r(u, x)_m = e_r(u, y)_l = x_m. Имеем E = E_m ∪ E_ml. Поскольку E_m ∩ E_ml = ∅, имеем |E| = |E_m| + |E_ml|, что и требовалось доказать в этом случае.

Теперь рассмотрим случай x_m ∈ Imy и x_m ∈ ∈ Im x[m – 1]. Поскольку x_m ∈ Imy, переход от последовательности x[m – 1] к последовательности x = x[m – 1]x_m может добавлять новые общие A‑вложения u, но они новые только в том случае, когда таких A‑вложений не было раньше в x[m – 1] и y. Эти новые общие A-вложения должны заканчиваться на x_m. Заметим, что если такое общее A-вложение u было раньше, то в его самых правых E-вложениях в x[m – 1] и y последний непустой символ равен x_m по индексам k и l, соответственно, т.е. e_r(u, x[m – 1])_k = e_r(u, y)_l = x_m. В любом случае в самых правых E-вложениях u в x и y последний непустой символ равен x_m по индексам m и l, соответственно, т.е. e_r(u, x)_m = e_r(u, y)_l = x_m. Имеем E = E_m ∪ (E_ml\E_kl). Поскольку E_m ∩ E_ml = E_m ∩ E_kl = =∅, имеем E_m ∩ (E_ml\E_kl) = ∅ и поэтому |E| = |E_m| + |E_ml\E_kl|. Поскольку E_ml ⊇ E_kl, имеем |E_ml\E_kl| = |E_ml| – |E_kl|. Поэтому |E| = |E_m| + |E_ml| – |E_kl|, что и требовалось доказать в этом случае.

◻

Теорема 1 определяет алгоритм вычисления A₀(x, y). Число шагов алгоритма равно O(mn), что определяется числом функций вида A₀(x[m – i], y[n – j]), где i ∈ 0..m и j ∈ 0..n, при условии, что каждая функция вычисляется не более одного раза (после чего ее значение сохраняется). На каждом шаге проверка условий x_{m –i} ∈ Im y[n – j] и x_{m –i} ∈ Im x[m – i – 1] имеет сложность O(m + n), а остальные вычисления имеют сложность O(1). Сложность алгоритма равна O(m²n + mn²), что для m ≤ n равно O(mn²).

4.2. Сумма длин общих A-вложений

Теорема 2.

A1(x, y) = A1(x[m – 1], y), если xm ∉ Im y;

A₁(x, y) = A₁(x[m – 1], y) + A₁(x[m – 1], y[l – 1]) + A₀(x[m – 1], y[l – 1]), если x_m ∈ Im y и x_m ∉ Im x[m – 1];

A₁(x, y) = A₁(x[m – 1], y) + A₁(x[m – 1], y[l – 1]) + A₀(x[m – 1], y[l – 1]) – A₁(x[k – 1], y[l – 1]) – A₀(x[k – 1], y[l – 1]), если x_m ∈ Im y и x_m ∈ Im x[m – 1].

Доказательство.

Доказательство аналогично доказательству теоремы 1. Используем те же обозначения:

E = A_r(x, y);

E_m = A_r(x[m – 1], y)(ε, ());

E_ml = A_r(x[m – 1], y[l – 1])(x_m, x_mε^n–l), если x_m ∈ Im y, иначе E_ml = ∅;

E_kl = A_r(x[k – 1], y[l – 1])(x_mε^{m–k– 1}x_m, x_mε^n–l), если x_m ∈ Im y и x_m ∈ Im x[m – 1], иначе E_kl = ∅.

Имеем E_m ∩ E_ml = E_m ∩ E_kl = ∅ и E_ml ⊇ E_kl.

Также имеем A₀(x[m – 1], y[l – 1]) = |E_ml| и |A₀(x[k – 1], y[l – 1])| = |E_kl|.

Обозначим:

S = Σ {|u| : u ∈ A(x) ∩ A(y) & (e_r(u, x), e_r(u, y)) ∈ E},

S_m = Σ {|u| : u ∈ A(x) ∩ A(y) & (e_r(u, x), e_r(u, y)) ∈ E_m},

S_ml = Σ {|u| : u ∈ A(x) ∩ A(y) & (e_r(u, x), e_r(u, y)) ∈ E_ml}, если x_m ∈ Im y, иначе E_ml = ∅,

S_kl = Σ {|u| : u ∈ A(x) ∩ A(y) & (e_r(u, x), e_r(u, y)) ∈ E_kl}, если x_m ∈ Im y и x_m ∈ Im x[m – 1], иначе E_kl = ∅.

Длина общего A-вложения u равна числу непустых символов в каждом его E-вложении, в том числе, в самом правом E-вложении. Поэтому в этих обозначениях утверждение теоремы можно переписать в виде:

S = S_m, если x_m ∉ Im y;

S = S_m + S_ml + |E_ml|, если x_m ∈ Im y и x_m ∉ Im x[m – 1];

S = S_m + S_ml + |E_ml| – S_kl – |E_kl|, если x_m ∈ Im y и x_m ∈ Im x[m – 1].

При переходе от последовательности x[m – 1] к последовательности x = x[m – 1]x_m число непустых символов в самом правом E-вложении в x общего A‑вложения u не меняется, если в нем по индексу m оказывается пустой символ e_r(u, x)_m = ε, и увеличивается на 1 в противном случае, когда e_r(u, x)_m = x_m.

Это влечет следующие утверждения.

В случае x_m ∉ Im y имеем E = E_m, для каждого (u, ${v}$) ∈ E_m имеет место u_m = ε, поэтому S = S_m, что и требовалось доказать в этом случае.

В случае x_m ∈ Im y и x_m ∉ Im x[m – 1] имеем E = E_m ∪ E_ml и E_m ∩ E_ml = ∅, для каждого (u, ${v}$) ∈ E_m имеет место u_m = ε, для каждого (u, ${v}$) ∈ E_ml имеет место u_m = x_m, поэтому S = S_m + (S_ml + |E_ml|) , что и требовалось доказать в этом случае.

В случае x_m ∈ Im y и x_m ∈ Im x[m – 1] имеем E = E_m ∪ (E_ml\E_kl) и E_m ∩ E_ml = E_m ∩ E_kl = ∅, для каждого (u, ${v}$) ∈ E_m имеет место u_m = ε, для каждого (u, ${v}$) ∈ E_ml имеет место u_m = x_m, для каждого (u, ${v}$) ∈ ∈ E_kl имеет место u_m = x_m, поэтому S = S_m + (S_ml + + |E_ml|) – (S_kl + |E_kl|), что и требовалось доказать в этом случае.

□

Теорема 2 определяет алгоритм вычисления A₁(x, y), сложность которого по порядку, очевидно, не превышает сложности алгоритма вычисления A₀(x, y), т.е. равна O(m²n + mn²), что для m ≤ n равно O(mn²).

4.3. Cумма минимумов чисел E-вложений общих A-вложений

Для функции A₂(x, y) мы не знаем хорошего (отличного от полного перебора) алгоритма. Единственная полезная оптимизация – это предварительное удаление необщих символов.

4.4. Сумма произведений чисел E‑вложений общих A-вложений

Здесь мы докажем теорему, аналогичную теореме 2 в [3] с тем отличием, что мы учитываем пустую подпоследовательность, а в теореме 2 в [3] она не учитывается. Также мы дадим свое доказательство, поскольку мы используем другие определения и обозначения.

Теорема 3. A₃(x, y) = A₃(x[m – 1], y) + A₃(x, y[n – – 1]) – A₃(x[m – 1], y[n – 1]), если x_m ≠ y_n;

A₃(x, y) = A₃(x[m – 1], y) + A₃(x, y[n – 1]), если x_m = y_n.

Доказательство.

Обозначим следующие множества пар E-вложений общих A-вложений:

E = A(x, y),

E₀₀ = A(x[m – 1], y[n – 1])(ε, ε) – пара последних элементов (ε, ε),

E₀₁ = (A(x[m – 1], y])(ε, ()))\E₀₀ – пара последних элементов (ε, y_n),

E₁₀ = (A(x, y[n – 1])((), ε))\E₀₀ – пара последних элементов (x_m, ε),

E₁₁ = E\(E₀₀ ∪ E₀₁ ∪ E₁₀) – пара последних элементов (x_m, y_n), поскольку E₀₀ ∪ E₀₁ ∪ E₁₀ содержат все пары E‑вложений общих A‑вложений, в которых пара последних элементов содержит ε.

Очевидно, E = E₀₀ ∪ E₀₁ ∪ E₁₀ ∪ E₁₁. Пары последних элементов пар E-вложений из разных множеств E₀₀, E₀₁, E₁₀, E₁₁ разные, поэтому эти множества попарно не пересекаются. Поэтому |E| = |E₀₀| + |E₀₁| + |E₁₀| + |E₁₁|, |E₀₀ ∪ E₀₁| = |E₀₀| + |E₀₁|, |E₀₀ ∪ E₁₀| = |E₀₀| + |E₁₀|.

Поскольку A₃(x, y) = |A(x, y)|, в этих обозначениях утверждение теоремы имеет вид

|E| = (|E₀₀| + |E₀₁|) + (|E₀₀| + |E₁₀|) – |E₀₀| = |E₀₀| + + |E₀₁| + |E₁₀|, если x_m ≠ y_n,

|E| = (|E₀₀| + |E₀₁|) + (|E₀₀| + |E₁₀|) = 2|E₀₀| + |E₀₁| + + |E₁₀|, если x_m = y_n.

Рассмотрим случай  x_m ≠ y_n. В этом случае E₁₁ = ∅, что влечет |E₁₁| = 0 и |E| = |E₀₀| + |E₀₁| + |E₁₀|, что и требовалось доказать в этом случае.

Рассмотрим случай x_m = y_n = h. Каждая пара E-вложений из E₁₁ имеет вид ($u{{\varepsilon }^{m}}^{{ - |u| - 1}}h$, ${v}{{\varepsilon }^{n}}^{{ - |{v}| - 1}}h$), где ($u{{\varepsilon }^{m}}^{{ - |u| - 1}}\varepsilon $, ${v}{{\varepsilon }^{n}}^{{ - |{v}| - 1}}\varepsilon $) ∈ E₀₀ (последовательности u и ${v}$ могут быть обе пустыми). Будем говорить, что пара ($u{{\varepsilon }^{m}}^{{ - |u| - 1}}h$, ${v}{{\varepsilon }^{n}}^{{ - |{v}| - 1}}h$) соответствует паре ($u{{\varepsilon }^{m}}^{{ - |u| - 1}}\varepsilon $, ${v}{{\varepsilon }^{n}}^{{ - |{v}| - 1}}\varepsilon $). Это соответствие, очевидно, является биекцией множеств E₁₁ и E₀₀. Тем самым, |E₁₁| = |E₀₀|. Поэтому |E| = |E₀₀| + |E₀₁| + |E₁₀| + |E₁₁| = |E₀₀| + |E₀₁| + + |E₁₀| + |E₀₀| = 2|E₀₀| + |E₀₁| + |E₁₀|, что и требовалось доказать в этом случае.

□

Теорема 3 определяет алгоритм вычисления A₃(x, y). Число шагов алгоритма равно O(mn), что определяется числом функций вида A₃(x[m – i], y[n – j]), где i ∈ 0..m и j ∈ 0..n, при условии, что каждая функция вычисляется не более одного раза (после чего ее значение сохраняется). На каждом шаге вычисления имеют сложность O(1). Тем самым сложность алгоритма равна O(mn).

4.5. Функция похожести на основе наибольшей длины общего A-вложения

Задача вычисления длины наибольшей общей подпоследовательности (longest common subsequence, lcs) хорошо известна [1]. Простейший алгоритм сложности O(mn) основан на следующих соотношениях:

lcA(x, y) = lcA(x[m – 1], y[n – 1]) + 1, если x_m = y_n;

lcA(x, y) = max{lcA(x, y[n – 1]), lcA(x[m – 1], y)}, если x_m ≠ y_n.

Тем самым, функция A₄(x, y) = lcA(x, y) вычисляется за время O(mn).

5.1. Число общих L-вложений

Теорема 4. L₀(x, y) = L₀(x[m – 1], y[n – 1])), если x_m ≠ y_n,

L₀(x, y) = 2L₀(x[m – 1], y[n – 1]), если x_m = y_n.

Доказательство.

Обозначим L = L(x) ∩ L(y) и L_–1 = L(x[m – 1]) ∩ ∩ L(y[n – 1]). Если x_m ≠ y_n, то L‑вложению u ∈ L_–1 соответствует одно L-вложение uε ∈ L. Тем самым, L₀(x, y) = |L| = |L_–1| = L₀(x[m – 1], y[n – 1])). Если x_m = y_n, то L-вложению u ∈ L_–1 соответствуют два L-вложения uε ∈ L и ux_m ∈ L. Тем самым, L₀(x, y) = |L| = 2|L_–1| = 2L₀(x[m – 1], y[n – 1])).

□

Теорема 4 определяет алгоритм вычисления L₀(x, y). Для m ≤ n число шагов алгоритма равно O(m), что определяется числом функций вида L₀(x[m – i], y[n – i]), где i ∈ 0..m. На каждом шаге вычисления имеют сложность O(1). Тем самым сложность алгоритма равна O(m).

Теорема 5. L₀(x, y) = 2^|μγ(x,y)|.

Доказательство.

Из теоремы 4 следует, что при добавлении к обеим последовательностям справа по одному символу число общих L-вложений увеличивается вдвое, если добавляются равные символы, и не меняется в противном случае. Поскольку |L(x) ∩ ∩ L(())| = |L(()) ∩ L(y)| = |ε| = 1, а |μγ(x, y)| равно числу совпадающих символов в одинаковых позициях x и y при отсчете справа налево, имеем L₀(x, y) = |L(x) ∩ L(y)| = 2^|μγ(x,y)|, что и требовалось доказать.

□

Теорема 5 определяет алгоритм вычисления L₀(x, y). Сложность алгоритма равна сложности вычисления μγ(x, y), которая, очевидно, для m ≤ n равна O(m), плюс сложность возведения числа два в степень |μγ(x, y)|, которая тоже равна O(m). Тем самым сложность алгоритма равна O(m).

5.2. Сумма μ‑длин общих L-вложений

Теорема 6. L₁(x, y) = L₁(x[m – 1], y[n – 1])), если x_m ≠ y_n,

L₁(x, y) = 2L₁(x[m – 1], y[n – 1] + L₀(x[m – 1], y[n – 1]), если x_m = y_n.

Доказательство.

Обозначим L = L(x) ∩ L(y) и L_–1 = L(x[m – 1]) ∩ ∩ L(y[n – 1]). Если x_m ≠ y_n, то L-вложению u ∈ L_–1 соответствует одно L-вложение uε ∈ L той же μ‑длины. Тем самым, L₁(x, y) = Σ {|μ(u)| : u ∈ L} = = Σ {|μ(u)| : u ∈ L_–1} = L₁(x[m – 1], y[n – 1])). Если x_m = y_n, то L‑вложению u ∈ L_–1 соответствуют два L‑вложения uε ∈ L той же μ‑длины и ux_m ∈ L с μ‑длиной на 1 большей. Тем самым, L₁(x, y) = = Σ{|μ(u)| : u ∈ L} = Σ {|μ(u)| : u ∈ L_–1} + (Σ {|μ(u)| : u ∈ L_–1} + L₀(x[m–1], y[n–1])) = 2Σ {|μ(u)| : u ∈ L_–1} + + L₀(x[m – 1], y[n – 1]) = 2L₁(x[m – 1], y[n – 1] + + L₀(x[m – 1], y[n – 1]).

□

Теорема 6 определяет алгоритм вычисления L₁(x, y), сложность которого по порядку, очевидно, не превышает сложности алгоритма вычисления L₀(x, y), т.е. равна O(m).

Теорема 7. L₁(x, y) = 1*${\text{C}}_{l}^{1}$ + 2*${\text{C}}_{l}^{2}$ + … + l*${\text{C}}_{l}^{1}$ (A001787), где l = |μγ(x, y)|.

Доказательство.

Утверждение теоремы непосредственно следует из того факта, что число общих L-вложений μ‑длины i равно ${\text{C}}_{{|\mu \gamma (x,y)|}}^{i}$.

□

Теорема 7 определяет алгоритм вычисления L₁(x, y). Сложность алгоритма равна сложности вычисления μγ(x, y), которая, очевидно, для m ≤ n равна O(m), плюс сложность вычисления факториалов i! для i ∈ 0..l, равная O(m), плюс сложность суммирования l чисел, равная O(m). Тем самым сложность алгоритма равна O(m).

5.3. Cумма минимумов и сумма произведений чисел E-вложений общих L-вложений

Теорема 8. L₂(x, y) = L₃(x, y) = L₀(x, y).

Доказательство.

Утверждение теоремы непосредственно следует из того факта, что L-вложению u ∈ L(x) соответствует ровно одно E-вложение ${v}$ такое, что λ(${v}$) = u: L₂(x, y) = Σ{min{|l(u, x)|, |l(u, y)|} : u ∈ L(x) ∩ ∩ L(y)} = Σ{min{1, 1} : u ∈ L(x) ∩ L(y)} = |L(x) ∩ ∩ L(y)| = L₀(x, y); L₃(x, y) = |L(x, y)| = |∪ {l(u, x) × × l(u, y) : u ∈ L(x) ∩ L(y)}| = |L(x) ∩ L(y)| = L₀(x, y).

□ 

Теорема 8 определяет алгоритм вычисления L₂(x, y) и L₃(x, y) той же сложности, что алгоритм вычисления L₀(x, y), т.е. для m ≤ n сложности O(m).

5.4. Функция похожести на основе наибольшей длины общего L-вложения

Теорема 9.

lcL(x, y) = lcL(x[m – 1], y[n – 1]) + 1, если x_m = y_n;

lcL(x, y) = lcL(x[m – 1], y[n – 1]), если x_m ≠ y_n.

Доказательство. Функция γ(x, y) устанавливает позиционное соответствие совпадающих символов x и y при счете позиций справа налево. Поэтому lcL(x, y) = |μγ(x, y)|. Отсюда непосредственно следует утверждение теоремы.

□

Теорема 9 определяет алгоритм вычисления функции L₄(x, y) = lcL(x, y) сложности O(m) для m ≤ n.

6.1. Число общих R-вложений

Теорема 10. R₀(x, y) = R₀(x[2..m], y[2..n])), если x₁ ≠ y₁,

R₀(x, y) = 2R₀(x[2..m], y[2..n]), если x₁ = y₁.

Доказательство.

Обозначим R = R(x) ∩ R(y) и R_–1 = R(x[2..m]) ∩ ∩ R(y[2..n]). Если x₁ ≠ y₁, то R‑вложению u ∈ R_–1 соответствует одно R-вложение εu ∈ R. Тем самым, R₀(x, y) = |R| = |R_–1| = R₀(x[2..m], y[2..n])). Если x₁ = y₁, то R‑вложению u ∈ R_–1 соответствуют два R‑вложения εu ∈ R и x₁u. Тем самым, R₀(x, y) = = |R| = 2|R_–1| = 2R₀(x[2..m], y[2..n])).

□

Теорема 10 определяет алгоритм вычисления R₀(x, y). Для m ≤ n число шагов алгоритма равно O(m), что определяется числом функций вида R₀(x[i..m], y[i..n]), где i ∈ 0..m. На каждом шаге проверка вычисления имеет сложность O(1). Тем самым сложность алгоритма равна O(m).

Теорема 11. R₀(x, y) = 2^|μδ(x,y)|.

Доказательство.

Из теоремы 10 следует, что при добавлении к обеим последовательностям слева по одному символу число общих R-вложений увеличивается вдвое, если добавляются равные символы, и не меняется в противном случае. Поскольку |R(x) ∩ ∩ R(())| = |R(()) ∩ R(y)| = |ε| = 1, а |μδ(x, y)| равно числу совпадающих символов в одинаковых позициях x и y при отсчете слева направо, имеем R₀(x, y) = |R(x) ∩ R(y)| = 2^|μδ(x,y)|, что и требовалось доказать.

□

Теорема 11 определяет алгоритм вычисления R₀(x, y). Сложность алгоритма равна сложности вычисления μδ(x, y), которая, очевидно, для m ≤ n равна O(m), плюс сложность возведения числа два в степень |μδ(x, y)|, которая тоже равна O(m). Тем самым сложность алгоритма равна O(m).

6.2. Сумма μ-длин общих R-вложений

Теорема 12. R₁(x, y) = R₁(x[2..m], y[2..n])), если x₁ ≠ y₁,

R₁(x, y) = 2R₁(x[2..m], y[2..n] + R₀(x[2..m], y[2..n]), если x₁ = y₁.

Доказательство.

Обозначим R = R(x) ∩ R(y) и R_–1 = R(x[2..m]) ∩ ∩ R(y[2..n]). Если x₁ ≠ y₁, то R-вложению u ∈ R_–1 соответствует одно R-вложение εu ∈ R той же μ‑длины. Тем самым, R₁(x, y) = Σ{|μ(u)| : u ∈ R} = = Σ{|μ(u)| : u ∈ R_–1} = R₁(x[2..m], y[2..n])). Если x₁ = y₁, то R‑вложению u ∈ R_–1 соответствуют два R-вложения εu ∈ R той же μ-длины и x₁u ∈ R с μ-длиной на 1 большей. Тем самым, R₁(x, y) = Σ{|μ(u)| : u ∈ ∈ R} = Σ{|μ(u)| : u ∈ R_–1} + (Σ{|μ(u)| : u ∈ R_–1} + + R₀(x[2..m], y[2..n])) = 2Σ{|μ(u)| : u ∈ R_–1} + + R₀(x[2..m], y[2..n]) = 2R₁(x[2..m], y[2..n] + + R₀(x[2..m], y[2..n]).

□

Теорема 12 определяет алгоритм вычисления R₁(x, y), сложность которого по порядку, очевидно, не превышает сложности алгоритма вычисления R₀(x, y), т.е. для m ≤ n равна O(m).

Теорема 13. R₁(x, y) = 1*${\text{C}}_{r}^{1}$ + 2*${\text{C}}_{r}^{2}$ + … + r*${\text{C}}_{r}^{r}$ (A001787), где r = |μδ(x, y)|.

Доказательство.

Утверждение теоремы непосредственно следует из того факта, что число общих R-вложений μ-длины i равно ${\text{C}}_{{|\mu \delta (x,y)|}}^{i}$.

□

Теорема 13 определяет алгоритм вычисления R₁(x, y). Сложность алгоритма равна сложности вычисления μδ(x, y), которая, очевидно, для m ≤ n равна O(m), плюс сложность вычисления факториалов i! для i ∈ 0..r, равная O(m), плюс сложность суммирования r чисел, равная O(m). Тем самым сложность алгоритма равна O(m).

6.3. Cумма минимумов и сумма произведений чисел E-вложений общих R-вложений

Теорема 14. R₂(x, y) = R₃(x, y) = R₀(x, y).

Доказательство.

Утверждение теоремы непосредственно следует из того факта, что R‑вложению u ∈ R(x) соответствует ровно одно E‑вложение ${v}$ такое, что ρ(${v}$) = u: R₂(x, y) = Σ{min{|r(u, x)|, |r(u, y)|} : u ∈ R(x) ∩ ∩ R(y)} = Σ{min{1, 1} : u ∈ R(x) ∩ R(y)} = |R(x) ∩ ∩ R(y)| = R₀(x, y); R₃(x, y) = |R(x, y)| = |∪ {r(u, x) × × r(u, y) : u ∈ R(x) ∩ R(y)}| = |R(x) ∩ R(y)| = R₀(x, y).

□

Теорема 14 определяет алгоритм вычисления R₂(x, y) и R₃(x, y) той же сложности, что алгоритм вычисления R₀(x, y), т.е. для m ≤ n сложности O(m).

6.4. Функция похожести на основе наибольшей длины общего R-вложения

Теорема 15.

lcR(x, y) = lcR(x[2..m], y[2..n]) + 1, если x₁ = y₁;

lcR(x, y) = lcR(x[2..m], y[2..n]), если x₁ ≠ y₁.

Доказательство. Функция δ(x, y) устанавливает позиционное соответствие совпадающих символов x и y при счете позиций слева направо. Поэтому lcR(x, y) = |μδ(x, y)|. Отсюда непосредственно следует утверждение теоремы.

□

Теорема 15 определяет алгоритм вычисления функции R₄(x, y) = lcR(x, y) сложности O(m) для m ≤ n.

7.1. Число общих O‑вложений

Для случая x_m = y_n = h обозначим через I = {i ∈ ∈ 1..m : x_i = h} и J = {j ∈ 1..n : y_j = h} множества индексов по которым находится символ h в x и y, соответственно.

Обозначим для i ∈ I, j ∈ J: L_i,j = L(x[i – 1]) ∩ ∩ L(y[j – 1]).

Обозначим K = (I × J)\{(m, n)} и L_h(x, y) = = L_m, n\∪ {L_{i, j}: (i, j)∈ K}.

Для i ∈ I и  j ∈ J обозначим через u_i,j максимальное общее L‑вложение в x[i – 1] и y[j – 1]: u_i,j = = λ(${{{v}}_{i}}_{{,j}}$), где ${{{v}}_{i}}_{{,j}}$ общее E-вложение в x[i – 1] и y[j – 1], определяемое условием: ∀ t = 1..min{i, j} – 1 (x_{i –t} = = y_{i –t} ⇒ ${{{v}}_{i}}_{{,j}}$(i – t) = x_{i –t}) & (x_{i –t} ≠ y_{i –t} ⇒ ${{{v}}_{i}}_{{,j}}$(i – t) = = ε). Множество всех общих L-вложений в x[i – 1] и y[j – 1] равно λE(u_i,j), т.е. получается из u_i,j всеми возможными заменами некоторых символов на пустой символ и последующим удалением префикса пустых символов.

Лемма 1. Пусть x_m = y_n = h. Вычисление |L_h(x, y)| эквивалентно вычислению числа слагаемых СДНФ некоторой конъюнкции дизъюнкций переменных без отрицаний, где число переменных равно числу непустых символов в максимальном общем L-вложении u_m,n в x[m – 1] и y[n – 1].

Доказательство.

L_h(x, y) = L_m,n\∪{L_i,j : (i, j)∈ K} = L_m,n\∪{L_m,n ∩ ∩ L_i,j : (i, j)∈ K}. Для получения L_h(x, y) нам нужно из L_m,n удалить множество L_m,n ∩ L_i,j для каждых (i, j)∈ K.

Определим “пересечение” $u_{{i,j}}^{ \wedge }$ вложений u_m,n и u_i,j, имеющее длину |u_m,n| и совпадающее с u_m,n и u_i,j в тех позициях, считая справа налево, в которых они совпадают между собой, а во всех остальных позициях содержит пустой символ: |$u_{{i,j}}^{ \wedge }$| = |u_m,n| и ∀ t = 1..|u_m,n| (t > |u_i,j| ⇒ $u_{{i,j}}^{ \wedge }$(|u_m,n| – t) = ε) & (t ≤ |u_i,j| & u_m,n(|u_m,n| – t) = u_i,j(|u_i,j| – t) ⇒ $u_{{i,j}}^{ \wedge }$(|u_m,n| – t) = u_m,n(|u_m,n| – – t)) & (t ≤ |u_i,j| & u_m,n(|u_m,n| – t) ≠ u_i,j(|u_i,j| – t) ⇒ ⇒ $u_{{i,j}}^{ \wedge }$(|u_m,n| – t) = ε). Очевидно, $u_{{m,n}}^{ \wedge }$ = u_m,n.

Удалим из вложения $u_{{i,j}}^{ \wedge }$ символы в тех позициях, в которых u_m,n содержит пустой символ, и обозначим результат w_i,j: если $u_{{i,j}}^{ \wedge }$ = u₁h₁u₂h₂…u_kh_{k – 1}u_k, u_m,n = ${{{v}}_{1}}\varepsilon {{{v}}_{2}}\varepsilon ...{{{v}}_{k}}_{{ - 1}}\varepsilon {{{v}}_{k}}$ и для i ∈ 1..k |u_i| = |${{{v}}_{i}}$| и ${{{v}}_{i}}$ ∈ H*, то w_i,j = u₁u₂…u_{k – 1}u_k. Очевидно, w_m,n = μ(u_m,n).

Все w_i,j имеют одинаковую длину |w_m,n|, равную числу непустых символов в u_m,n. Каждому L‑вложению из L_m,n ∩ L_i,j взаимно-однозначно соответствует E-вложение в w_i,j, число таких вложений равно 2^k, где k = |μ(w_i,j)| число непустых символов в w_i,j.

Поставим каждому t ∈ 1..|w_m,n| в соответствие булеву переменную α_t, означающую, что в позиции t может быть непустой символ. Тогда E-вложения в w_i,j задаются булевой функцией F_i,j = = &{¬α_t : t ∈ 1..|w_m,n| & w_i,j(t) = ε}, которая принимает значение true на тех и только тех наборах α₁, …, в которых α_t = false для всех тех индексов t, по которым в w_i,j и, следовательно, в любом E-вложении в w_i,j находится пустой символ. Если по индексу t в w_i,j находится непустой символ, то в одних E-вложениях в w_i,j в этой позиции будет пустой символ, а в других непустой символ, что означает, что функция F_i,j не зависит от α_t. Очевидно, что F_m,n = &∅ = true.

Разность L_m,n\∪ {L_m,n ∩ L_i,j : (i, j)∈ K} задается булевой функцией F = F_m,n\∨ {F_i,j : (i, j)∈ K} = & {¬F_i,j : (i, j)∈ K}, и ¬F_i,j = ∨{α_t : t ∈ 1..|w_m,n| & w_i,j(t) = ε}. Таким образом, F – это конъюнкция дизъюнкций переменных без отрицаний, и число |L_h(x, y)| равно числу слагаемых в СДНФ функции F.

□

Теорема 16.

O₀(x, y) = O₀(x[m – 1], y) + O₀(x, y[n – 1]) – ‒ O₀(x[m – 1], y[n – 1]), если x_m ≠ y_n.

O₀(x, y) = O₀(x[m – 1], y) + O₀(x, y[n – 1]) – ‒ O₀(x[m – 1], y[n – 1]) + L_h(x, y]), если x_m = y_n.

Доказательство.

Обозначим следующие множества пар E-вложений:

E = O_r(x, y),

E₀₀ = O_r(x[m – 1], y[n – 1])(ε, ε) – пара последних элементов (ε, ε),

E₀₁ = (O_r(x[m – 1], y])(ε, ()))\E₀₀ – пара последних элементов (ε, y_n),

E₁₀ = (O_r(x, y[n – 1])((), ε))\E₀₀ – пара последних элементов (x_m, ε),

E₁₁ = E\(E₀₀ ∪ E₀₁ ∪ E₁₀) – пара последних элементов (x_m, y_n), поскольку E₀₀ ∪ E₀₁ ∪ E₁₀ содержат все пары E-вложений общих O-вложений, в которых пара последних элементов содержит ε.

Очевидно, E = E₀₀ ∪ E₀₁ ∪ E₁₀ ∪ E₁₁. Пары последних элементов пар E-вложений из разных множеств E₀₀, E₀₁, E₁₀, E₁₁ разные, поэтому эти множества попарно не пересекаются. Поэтому |E| = |E₀₀| + |E₀₁| + |E₁₀| + |E₁₁|, |E₀₀ ∪ E₀₁| = |E₀₀| + |E₀₁|, |E₀₀ ∪ E₁₀| = |E₀₀| + |E₁₀|.

Поскольку для любых x, y имеет место O₀(x, y) = = |O(x) ∩ O(y)| = |O_r(x, y)| и L₀(x, y) = L₃(x, y) = |L(x, y)|, утверждение теоремы можно переписать в виде:

|E| = (|E₀₀| + |E₀₁|) + (|E₀₀| + |E₁₀|) – |E₀₀| = |E₀₀| + + |E₀₁| + |E₁₀|, если x_m ≠ y_n,

|E| = (|E₀₀| + |E₀₁|) + (|E₀₀| + |E₁₀|) – |E₀₀| + |L_h(x, y)| = = |E₀₀| + |E₀₁| + |E₁₀| + |L_h(x, y)|, если x_m = y_n.

Рассмотрим случай x_m ≠ y_n. В этом случае E₁₁ = ∅, что влечет |E₁₁| = 0 и |E₀₀| = |E₀₀| + |E₀₁| + |E₁₀|, что и требовалось доказать в этом случае.

Рассмотрим случай x_m = y_n = h. В этом случае каждая пара E‑вложений из E₁₁ имеет вид (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$), где (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$) ∈ L_h(x, y), т.е. при переходе от x[m – 1] и y[n – 1] к x и y эта пара образована добавлением справа символа h к паре E-вложений общих L-вложений в x[m –1] и y[n –1], но таких, которых не было раньше, т.е. которые не являются парой E-вложений общих L-вложений в x[i – 1] и y[j – 1], где x_i = y_j = h и i < m или j < n. Будем говорить, что пара (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$) соответствует паре (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$). Это соответствие, очевидно, является биекцией множеств E₁₁ и L_h(x, y). Тем самым, |E₁₁| = |L_h(x, y)|. Поэтому |E| = |E₀₀| + |E₀₁| + |E₁₀| + + |E₁₁| = |E₀₀| + |E₀₁| + |E₁₀| + |L_h(x, y)|, что и требовалось доказать в этом случае.

□

Теорема 16 определяет алгоритм вычисления O₀(x, y). Число шагов алгоритма равно O(mn), что определяется числом функций вида O₀(x[m – i], y[n – j]), где i ∈ 0..m и j ∈ 0..n, при условии, что каждая функция вычисляется не более одного раза (после чего ее значение сохраняется). На каждом шаге вычисления имеют сложность O(1). Тем самым сложность алгоритма равна O(mn)*O(L_h(x, y)), где O(L_h(x, y)) сложность вычисления функции |L_h(x, y)|.

Лемма 2. Пусть имеется k не обязательно различных множеств a(s), s ∈ 1..k. Обозначим для S ⊆ ⊆ 1..k, S ≠ ∅, пересечение множеств a(s), индексы которых пробегают множество S, через c(S) = = ∩{a(s) : s ∈ S} и сумму числа подмножеств множества c(S) по всем S, для которых |S| = l, через E(l) = Σ{2^|c(S)| : S ⊆ 1..k & |S| = l}. Тогда число различных множеств, вложенных хотя бы в одно из множеств a(s), s ∈ 1..k, равно чередующейся сумме E(1) – E(2) + E(3) – E(4) … (‑1)^{k+ 1}E(k), а сумма F  размеров этих множеств, увеличенных на 1, равна чередующейся сумме F(1) – F(2) + F(3) – F(4) … (–1)^{k+ 1}F(k), где F(l) = Σ{(|c(S)| + 2) 2^{|c(S)| – 1} : S ⊆ ⊆ 1..k & |S| = l}. Эти чередующиеся суммы могут быть вычислены за время O(2^k) при условии, что за время O(1) могут выполняться операции пересечения двух множеств (а также арифметические операции над целыми числами).

Доказательство.

Обозначим число различных множеств, вложенных хотя бы в одно из множеств a(s), s ∈ 1..k, через E(a(1), …, a(k)), а сумму их размеров, увеличенных на 1, через F(a(1), …, a(k)).

Будем вести доказательство индукцией по k. Для k = 1 имеется единственное множество S ⊆ ⊆ 1..1, S ≠ ∅, а именно S = {1}, и c({1}) = ∩{a(s) : s ∈ {1}} = a(1). Число различных подмножеств множества a(1) равно 2^|a(1)| и E(a(1)) = E(1) = 2^|a(1)|, а сумма их длин, увеличенных на 1, равна $1{\kern 1pt} {\text{*C}}_{r}^{0}\, + \,2{\kern 1pt} {\text{*}}{{{\text{C}}}_{r}}^{1}\, + \,{\text{ }}...\, + \,r{\kern 1pt} {\text{*}}{{{\text{C}}}_{r}}{{^{r}}^{{ - 1}}}$ + (r + 1)*${\text{C}}_{r}^{r}$ = (r + 2)2^{r – 1} (A001792), и F(a(1)) = F(1) = (r + 2)2^{r– 1}, где r = = |a(1)|.

Пусть утверждение верно для k и докажем его для k + 1.

Число различных множеств, вложенных хотя бы в одно из множеств a(s), где s ∈ 1..k + 1, равно числу различных множеств, вложенных хотя бы в одно из множеств a(s), где s ∈ 1..k, т.е. E(a(1), …, a(k)), плюс число различных множеств, вложенных в a(k + 1), т.е. 2|^{a(k+ 1)}|, кроме тех, что вложены в пересечение a(k + 1) с объединением множеств a(1), …, a(k), число которых равно E(a(k + 1) ∩ ∩ a(1), …, a(k + 1) ∩ a(k)).

Обозначим E_{k + 1} = E(a(1), …, a(k + 1)), E_k = = E(a(1), …, a(k)), $E_{k}^{ \wedge }$ = E(a(k + 1) ∩ a(1), …, a(k + 1) ∩ ∩ a(k)). Имеем E_{k + 1} = E_k + 2|^{a(k+ 1)}| – $E_{k}^{ \wedge }$.

Рассмотрим S ⊆ 1..k + 1. Пусть |S| = 1, тогда S = {i}, i ∈ 1..k + 1. Для i ∈ 1..k слагаемое 2^|сS)| = 2^|a(i)| один раз входит в сумму E_k со знаком “+”, в результате для i ∈ 1..k + 1 слагаемое 2^|сS)| = 2^|a(i)| один раз входит в сумму E_{k + 1} с тем же знаком. Пусть |S| > 1. Если k + 1 ∉ S, то слагаемое 2^|c(S)| один раз входит в сумму E_k со знаком “(–1)^{|S| + 1}”, в результате для i ∈ ∈ 1..k + 1 слагаемое 2^|c(S)| один раз входит в сумму E_{k + 1} с тем же знаком. Если k + 1 ∈ S, то c(S) = = {a(i₁) ∩ … ∩ a(i_{|S| – 1}) ∩ a(k + 1)} = {(a(k + 1) ∩ ∩ a(i₁)) ∩ … ∩ (a(k + 1) ∩ a(i_{|S| – 1}))}. Поэтому слагаемое 2^|c(S)| один раз входит в сумму $E_{k}^{ \wedge }$ со знаком “(–1)^|S|”, но, поскольку сумма $E_{k}^{ \wedge }$ вычитается, слагаемое 2^|c(S)| один раз входит в сумму E_{k + 1} со знаком “(–1)^{|S| + 1}”.

Аналогично сумма длин, увеличенных на 1, различных множеств, вложенных хотя бы в одно из множеств a(s), где s ∈ 1..k + 1, равно сумме длин, увеличенных на 1, различных множеств, вложенных хотя бы в одно из множеств a(s), где s ∈ 1..k, т.е. F(a(1), …, a(k)), плюс сумма длин, увеличенных на 1, различных множеств, вложенных в a(k + 1), т.е. (|a(k + 1)| + 2)2^{|a(k+ 1)| – 1}, кроме тех, что вложены в пересечение a(k + 1) с объединением множеств a(1), …, a(k), сумма длин которых, увеличенных на 1, равна F(a(k + 1) ∩ a(1), …, a(k + + 1) ∩ a(k)). Обозначим F_{k + 1} = F(a(1), …, a(k + 1)), F_k = F(a(1), …, a(k)), $F_{k}^{ \wedge }$= F(a(k + 1) ∩ a(1), …, a(k + + 1) ∩ a(k)). Имеем F_{k + 1} = F_k + (|a(k + 1)| + + 2)2^{|a(k + 1)| – 1} – $F_{k}^{ \wedge }$. Рассмотрим S ⊆ 1..k + 1. Пусть |S| = 1, тогда S = {i}, i ∈ 1..k + 1. Для i ∈ 1..k слагаемое (|c(S)| + 2)2^{|c(S)| – 1} = (|a(i)| + 2)2^{|a(i)| – 1} один раз входит в сумму F_k со знаком “+”, в результате для i ∈ 1..k + 1 слагаемое (|c(S)| + 2)2^{|c(S)| – 1} = (|a(i)| + + 2)2^{|a(i)| – 1} один раз входит в сумму F_{k + 1} с тем же знаком. Пусть |S| > 1. Если k + 1 ∉ S, то слагаемое (|c(S)| + 2)2^{|c(S)| – 1} один раз входит в сумму F_k со знаком “(–1)^{|S| + 1}”, в результате для i ∈ 1..k + 1 слагаемое (|c(S)| + 2)2^{|c(S)| – 1} один раз входит в сумму F_{k + 1} с тем же знаком. Если k + 1 ∈ S, то слагаемое (|c(S)| + 2)2^{|c(S)| – 1} один раз входит в сумму $F_{k}^{ \wedge }$ со знаком “(–1)^|S|”, но, поскольку сумма $F_{k}^{ \wedge }$ вычитается, слагаемое (|c(S)| + 2)2^{|c(S)| – 1} один раз входит в сумму F_{k + 1} со знаком “(–1)^{|S| + 1}”.

Утверждение доказано.

Число (не обязательно различных) множеств c(S) равно числу непустых подмножеств S множества 1..k, которое равно 2^k – 1, поэтому сложность вычисления E равна O(2^k) при условии, что за время O(1) могут выполняться операции пересечения двух множеств (а также арифметические операции над целыми числами).

□

Обозначим множество индексов последовательности x, по которым находится символ h: K_x(h) = {i ∈ 1..m : x(i) = h}. Для i ∈ K_x(h) обозначим множество пар (символ в x, позиция символа в x относительно позиции i), кроме пары (h, 0): P_x(i) = {(x(t), t – i) : t ∈ 1..m & t ≠ i}. Пусть символ h входит |K_x(h)| > 0 раз в x и |K_y(h)| > 0 раз в y. Обозначим k = |K_x(h)|*|K_y(h)|. Для i ∈ K_x(h) и  j ∈ K_y(h) для краткости обозначим P(i, j) = P_x(i) ∩ P_y(j). Для S ⊆ ⊆ K_x(h) × K_y(h), S ≠ ∅ обозначим c(S) = ∩{P(i, j) : (i, j) ∈ S}.

Теорема 17. Число различных общих O-вложений в x и y, содержащих символ h, равно чередующейся сумме E = E(1) – E(2) + E(3) – E(4) … (–1)^{k+ 1}E(k), где слагаемое E(l) это сумма числа всех подмножеств множества c(S) по всем S размера l, |S| = l: E(l) = Σ{2^|c(S)| : S ⊆ 1..k & |S| = l}. Сложность вычисления равна O(n2^k).

Доказательство.

Рассмотрим общее O-вложение u и пару его E‑вложений ${v}$(x) ∈ o(u, x) и ${v}$(y) ∈ o(u, y) таких, что ${v}$(x)_i = x_i = h и ${v}$(y)_j = y_j = h. Этому взаимно-однозначно соответствует подмножество множества пар P(i, j). Нам нужно вычислить число различных множеств, вложенных хотя бы в одно из множеств P(i, j), где i ∈ K_x(h) и j ∈ K_y(h). Число таких множеств пар P(i, j) равно k. По лемме 2 оно равно E = E(1) – E(2) + E(3) – E(4) … (–1)^{k+ 1}E(k), где E(l) = Σ{2^|c(S)| : S ⊆ 1..k & |S| = l}, l = 1..k, сумма числа всех подмножеств множества c(S) по всем S ⊆ K_x(h) × K_y(h) размера l, т.е. |S| = l, а c(S) = ∩{P(i, j) : (i, j) ∈ S}.

Просматриваем последовательность x длиной m, вычисляем K_x(h). Просматривая K_x(h), вычисляем множества P_x(i). Вычисление множества P_x(i) требует просмотра последовательности x длиной m. Тем самым, все множества P_x(i), i ∈ K_x(h), вычисляются за O(m|K_x(h)|). Аналогично все множества P_y(j), j ∈ K_y(h), вычисляются за O(n|K_x(h)|). Можно считать, что множество P_x(i) = {(x(t), t – i) : t ∈ 1..m & t ≠ i} линейно упорядочено по возрастанию относительного индекса t – i; размер этого множества равен m – 1.  Аналогично для множества P_y(j); размер этого множества равен n – 1. Тогда для построения пересечения P(i, j) = P_x(i) ∩ P_y(j) требуется просмотр этих множеств, т.е. время O(n + m), а все множества P(i, j), i ∈ K_x(h) и j ∈ K_y(h), вычисляются за время O(k(n + m)). Аналогично каждое пересечение множеств P(i, j) строится за время O(n + m). Сложность вычисления суммы E по лемме 2 равна O(2^k), но при условии, что пересечение двух множеств строится за время O(1), поэтому в данном случае потребуется время O((n + m)2^k). Общая сложность равна O(m) + O(n) + O(m|K_x(h)|) + + O(n|K_y(h)|) + O(k(n + m)) + O((n + m)2^k) = O((n + + m)2^k), что для m ≤ n равно O(n2^k).

□

Теорема 17 определяет следующий алгоритм вычисления O₀(x, y):

1. SUMMA = 0.

2. Просматривая последовательность x, ищем непустой символ h, входящий в x.

2.1. Если не нашли, то конец алгоритма.

2.2. Если нашли, то ищем символ h в y.

2.2.1. Если не нашли, то в x заменяем h на пустой символ и переходим на п. 2.

2.2.2. Если нашли, то:

2.2.2.1. Вычисляем множество K_x(h) индексов в x, по которым находится h, и множество K_y(h) индексов в y, по которым находится h.

2.2.2.2. Для каждой пары (i, j) ∈ K_x(h) × K_y(h) строим множество пар P(i, j).

2.2.2.3. Для каждого множества пар индексов S ⊆ K_x(h) × K_y(h), S ≠ ∅ строим пересечение c(S) = = ∩ {P(i, j) : (i, j) ∈ S}.

2.2.2.4. Вычисляем E = E(1) – E(2) + E(3) – E(4) … (–1)^{k+ 1}E(k).

2.2.2.5. SUMMA = SUMMA + E.

2.2.2.6. В x и в y заменяем h на пустой символ и переходим на п. 2.

7.2. Сумма μ‑длин общих O‑вложений

Теорема 18. Сумма μ‑длин различных общих O‑вложений в x и y, содержащих символ h, равно чередующейся сумме F = F(1) – F(2) + F(3) – F(4) … (–1)^{k + 1}F(k), где F(l) = Σ{(|c(S)| + 2) 2^{|c(S)| – 1} : S ⊆ ⊆ 1..k & |S| = l} сумма мощностей всех подмножеств всех множеств c(S) для |S| = l. Сложность вычисления O(n2^k).

Доказательство аналогично доказательству теоремы 17.

□

Теорема 18 определяет следующий алгоритм вычисления O₁(x, y):

1. Просматривая последовательность x, ищем непустой символ h, входящий в x.

1.1. Если не нашли, то конец алгоритма.

1.2. Если нашли, то ищем символ h в y.

1.2.1. Если не нашли, то в x заменяем h на пустой символ и переходим на п. 2.

1.2.2. Если нашли, то:

1.2.2.1. Вычисляем множество K_x(h) индексов в x, по которым находится h, и множество K_y(h) индексов в y, по которым находится h.

1.2.2.2. Для каждой пары (i, j) ∈ K_x(h) × K_y(h) строим множество пар P(i, j).

1.2.2.3. Для каждого множества пар индексов S ⊆ K_x(h) × K_y(h), S ≠ ∅ строим пересечение c(S) = = ∩ {P(i, j) : (i, j) ∈ S}.

1.2.2.4. Вычисляем F = F(1) – F(2) + F(3) – F(4) … (–1)^{k+ 1}F(k).

1.2.2.5. SUMMA = SUMMA + F.

1.2.2.6. В x и в y заменяем h на пустой символ и переходим на п. 2.

7.3. Cумма минимумов чисел E‑вложений общих O‑вложений

Теорема 19. Cумма минимумов чисел E-вложений общих O-вложений в x и y, содержащих символ h, равна Σ{min{|I|, |J|} * 2^{|A(I,J)| – 1} : I ⊆ K_x(h) & I ≠ ≠ ∅ & J ⊆ K_y(h) & J ≠ ∅}, где A(I, J) = (∩{P(i, j) : i ∈ I, j ∈ J})\(∪{P(i, j): i ∈ K_x(h)\I ∨ j ∈ K_y(h)\J}).

Сложность вычисления равна O(n2^k).

Доказательство. Множество A(I, J) представляет все общие O-вложения, содержащие символ h, которые имеют E-вложения в x, представляемые множеством I, и E-вложения в y, представляемые множеством J. Для каждого из таких O‑вложений минимум чисел их E-вложений в x и в y равен min{|I|, |J|}. Число таких O‑вложений равно 2^|A(I,J)|, поэтому сумма минимумов чисел E-вложений таких общих O-вложений равна min{|I|, |J|} * 2^|A(I,J)|. Суммируя по всем парам множеств I ⊆ ⊆ K_x(h), I ≠ ∅ и J ⊆ K_y(h) , J ≠ ∅, получаем искомую сумму минимумов чисел E-вложений общих O-вложений в x и y, содержащих символ h.

При вычислении этой суммы операции сложения, умножения, возведения в степень числа 2 и вычисление минимума из двух чисел выполняются O(2^k) раз. Для вычисления всех A(I, J) операции вычисления разности двух множеств, пересечения двух множеств, объединения двух множеств выполняются O(2^k) раз, а каждая такая операция выполняется за время O(n + m).

Просматриваем последовательность x длиной m, вычисляем K_x(h). Просматривая K_y(h), вычисляем множества P_x(i). Вычисление множества P_x(i) требует просмотра последовательности x длиной m. Тем самым, все множества P_x(i), i ∈ K_x(h), вычисляются за O(m|K_x(h)|). Аналогично все множества P_y(j), j ∈ K_y(h), вычисляются за O(n|K_y(h)|). Можно считать, что множество P_x(i) = {(x(t), t – i) : t ∈ 1..m & t ≠ i} линейно упорядочено по возрастанию относительного индекса t – i; размер этого множества равен m – 1. Аналогично для множества P_y(j); размер этого множества равен n – 1. Тогда для построения пересечения P(i, j) = P_x(i) ∩ P_y(j) требуется просмотр этих множеств, т.е. время O(n + m), а все множества P(i, j), i ∈ K_x(h) и j ∈ K_y(h), вычисляются за время O(k(n + m)). Для вычисления множества A(I, J) операции вычисления разности двух множеств, пересечения двух множеств, объединения двух множеств выполняются за время O(n + m), а число таких множеств A(I, J) равно O(2^k). В результате все множества A(I, J) строятся за время O((n + m)2^k), после чего для вычисления суммы арифметические операции выполняются O(2^k) раз. Общая сложность равна O(k(n + m)) + + O((n + m)2^k) + O(2^k) = O((n + m)2^k), что для m ≤ n равно O(n2^k).

□

Теорема 19 определяет следующий алгоритм вычисления O₂(x, y):

1. Просматривая последовательность x, ищем непустой символ h, входящий в x.

1.1. Если не нашли, то конец алгоритма.

1.2. Если нашли, то ищем символ h в y.

1.2.1. Если не нашли, то в x заменяем h на пустой символ и переходим на п. 2.

1.2.2. Если нашли, то:

1.2.2.1. Вычисляем множество K_x(h) индексов в x, по которым находится h, и множество K_y(h) индексов в y, по которым находится h.

1.2.2.2. Для каждой пары (i, j) ∈ K_x(h) × K_y(h) строим множество пар P(i, j).

1.2.2.3. Для каждых I ⊆ K_x(h), I ≠ ∅, J ⊆ K_y(h), J ≠ ∅ строим A(I, J).

1.2.2.4. Вычисляем M = Σ{min{|I|, |J|} * 2^{|A(I,J)| – 1} : I ⊆ K_x(h) & I ≠ ∅ & J ⊆ K_y(h) & J ≠ ∅}.

1.2.2.5. SUMMA = SUMMA + M.

1.2.2.6. В x и в y заменяем h на пустой символ и переходим на п. 2.

7.4. Сумма произведений чисел E‑вложений общих O‑вложений

Теорема 20. O₃(x, y) = O₃(x[m – 1], y) + O₃(x, y[n – 1]) – O₃(x[m – 1], y[n – 1]), если x_m ≠ y_n;

O₃(x, y) = O₃(x[m – 1], y) + O₃(x, y[n – 1]) – ‒ O₃(x[m – 1], y[n – 1]) + L₃(x[m – 1], y[n – 1]), если x_m = y_n.

Доказательство. Обозначим следующие множества пар E-вложений:

E = O(x, y),

L₀₀ = L(x[m – 1], y[n – 1]),

E₀₀ = O(x[m – 1], y[n – 1])(ε, ε) – пара последних элементов (ε, ε),

E₀₁ = (O(x[m – 1], y])(ε, ()))\E₀₀ – пара последних элементов (ε, y_n),

E₁₀ = (O(x, y[n – 1])((), ε))\E₀₀ – пара последних элементов (x_m, ε),

E₁₁ = E\(E₀₀ ∪ E₀₁ ∪ E₁₀) – пара последних элементов (x_m, y_n), поскольку E₀₀ ∪ E₀₁ ∪ E₁₀ содержат все пары E-вложений общих O-вложений, в которых пара последних элементов содержит ε.

Очевидно, E = E₀₀ ∪ E₀₁ ∪ E₁₀ ∪ E₁₁. Пары последних элементов пар E-вложений из разных множеств E₀₀, E₀₁, E₁₀, E₁₁ разные, поэтому эти множества попарно не пересекаются. Поэтому |E| = |E₀₀| + |E₀₁| + |E₁₀| + |E₁₁|, |E₀₀ ∪ E₀₁| = |E₀₀| + |E₀₁|, |E₀₀ ∪ E₁₀| = |E₀₀| + |E₁₀|.

В этих обозначениях утверждение теоремы имеет вид

|E| = (|E₀₀| + |E₀₁|) + (|E₀₀| + |E₁₀|) – |E₀₀| = |E₀₀| + + |E₀₁| + |E₁₀|, если x_m ≠ y_n,

|E| = (|E₀₀| + |E₀₁|) + (|E₀₀| + |E₁₀|) – |E₀₀| + |L₀₀| = = |E₀₀| + |E₀₁| + |E₁₀| + |L₀₀|, если x_m = y_n.

Рассмотрим случай x_m ≠ y_n. В этом случае E₁₁ = ∅, что влечет |E₁₁| = 0 и |E₀₀| = |E₀₀| + |E₀₁| + |E₁₀|, что и требовалось доказать в этом случае.

Рассмотрим случай  x_m = y_n = h. Каждая пара E‑вложений из E₁₁ имеет вид (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$), где (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$) ∈ L₀₀. Будем говорить, что пара (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}h$) соответствует паре (${{\varepsilon }^{m}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$, ${{\varepsilon }^{n}}^{{ - |{v}| - k - 1}}{v}{{\varepsilon }^{k}}$). Это соответствие, очевидно, является биекцией множеств E₁₁ и L₀₀. Тем самым, |E₁₁| = |L₀₀|. Поэтому |E| = |E₀₀| + |E₀₁| + |E₁₀| + |E₁₁| = |E₀₀| + |E₀₁| + |E₁₀| + |L₀₀|, что и требовалось доказать в этом случае.

□

Теорема 20 определяет алгоритм вычисления O₃(x, y). Число шагов алгоритма равно O(mn), что определяется числом функций вида O₃(x[m – i], y[n – j]) и L₃(x[m – i], y[n – i]), где i ∈ 0..m и  j ∈ 0..n, при условии, что каждая функция вычисляется не более одного раза (после чего ее значение сохраняется). На каждом шаге вычисления имеют сложность O(1). Тем самым сложность алгоритма равна O(mn).

7.5. Функция похожести на основе наибольшей длины общего O‑вложения

Теорема 21.

lcO(x, y) = max{lcL(x[m – 1], y[n – 1]) + 1, lcO(x[m – 1], y[n – 1])}, если x_m = y_n:

lcO(x, y) = max{lcO(x, y[n – 1]), lcO(x[m – 1], y)}, если x_m ≠ y_n.

Доказательство. Если x_m = y_n, то самые правые E-вложения общего O-вложения могут иметь в позиции m в x и в позиции n в y либо 1) символ x_m = y_n, либо 2) пустой символ. Если общее O-вложение наибольшей длины относится к случаю 1, то оно имеет вид ux_m, где u общее L-вложение префиксов x[m – 1] и y[n – 1], т.е. его μ‑длина на 1 больше наибольшей длины общего L-вложения префиксов x[m – 1] и y[n – 1]. Если общее O-вложение наибольшей длины относится к случаю 2, то оно является O-вложением наибольшей длины префиксов x[m – 1] и y[n – 1] и имеет такую же μ‑длину. Отсюда следует утверждение теоремы для случая x_m = y_n.

Если x_m ≠ y_n, то самые правые E‑вложения общего O-вложения имеют пустой символ либо 1) в позиции m в x, либо 2) в позиции n в y. Если общее O-вложение наибольшей длины относится к случаю 1, то оно является O-вложением наибольшей длины префикса x[m – 1] и последовательности y и имеет такую же μ-длину. Если общее O-вложение наибольшей длины относится к случаю 2, то оно является O-вложением наибольшей длины последовательности x и префикса y[n – 1] и имеет такую же μ‑длину. Отсюда следует утверждение теоремы для случая x_m ≠ y_n.

□

Теорема 21 определяет алгоритм вычисления функции O₄(x, y) = lcO(x, y) сложности O(mn).