4. Зависимость связи l_0 от числа общих имен в определяющих окрестностях

Изучим характер зависимости между величиной связи L_0 двух определяющих окрестностей Д_r и Д_s и количеством общих имен в этих окрестностях (с учетом кратности вхождения имен в Д_r и Д_s).

Определение.

Числом общих имен двух определяющих окрестностей Д_r(k) и Д_s(k) в списке Х (с учетом кратностей) назовем число:

r+k s+k

O(Д_r, Д_s) = д(a_i, a_j),

i=r-k j=s-k

где д(a_i, a_j)=1 если a_i=a_j (то есть имена a_i и a_j одинаковы) и равно нулю иначе.

Другими словами, O(Д_r, Д_s) – это число пар из декартового произведения Д_r x Д_s, таких, что в паре стоят одинаковые имена.

В рассмотренных нами случаях реальных хронологических списков, описывающих древнюю и средневековую историю Европы, обнаружилось весьма примечательное обстоятельство:

Значения L_0(Д_R, Д_S) И O(Д_R, Д_S) связаны между собой таким образом, что при увеличении O(Д_R, Д_S) увеличивается (в статистическом смысле) и L_0(Д_R, Д_S).

Этот вывод был получен на основе сравнения гистограмм частот значений L0(Д_r, Д_s) при условии, что значение O(Д_r, Д_s) фиксировано.)

Может показаться, что значение связи L0(Дr, Д_s) увеличивается при увеличении O(Д_r, Д_s) непосредственно за счет общих имен в Д_r и Д_s (механизмы, приводящие к такому увеличению даже в правильных списках действительно существуют, но они очень слабы). Однако это не так. Чтобы показать это, введем еще две меры связи определяющих окрестностей Д_r и Д_s в хронологическом списке Х.

Пусть дана пара определяющих окрестностей Д_r и Д_s в списке Х. Определим соответствующие разреженные определяющие окрестностиследующим образом:

Д'_r = множество различных имен из Д_r;

Д'_s = множество различных имен из Д_s;

Д»_r, s = множество имен из Д'_r, не совпадающих ни с какими именами из Д_s;

Таким образом, окрестности Д_r, Д'_s и Д»_r, s разрежены таким образом, что в них не осталось различных имен. Кроме того, окрестность Д_r, s не содержит имен, общих с Д_s или с Д'_s.

Определение.

Положим c

L1(Дr, Д_s) – ____________________Д l(a, b),

|Д'_r|x|Д'_s| aД_r, bД'_s c

L (Д_r, Д_s) – ____________________Д l(a, b).

|Д»_r, s|x|Д'_s| aД»_r, s, bД'_s

Здесь через |ч| обозначена длина (разреженной) определяющей окрестности, то есть число имен в ней.

Легко проверить, что определенная таким образом величина связи L_2 не зависит от порядка определяющих окрестностей:

L2(Дr, Д_s) – L_2(Д_s, Д_r).

Величина связи L2(Дr, Д_s) уже не связана напрямую с общими именами в Д_r и Д_s – эти имена в ее определении вообще не участвуют. Оказалось однако, что для реальных списков, относящихся к древней и средневековой истории Европы, зависимость связи L_2(Д_r, Д_s) от O(Д_r, Д_s) остается прежней (такой же, как и описанная выше зависимость L_0(Д_r, Д_s) от O(Д_r, Д_s)). То же верно и для связи L_1(Д_r, Д_s).

Итак, в примерах, относящихся к древней и средневековой истории Европы (о них – ниже) было обнаружено, что в основе двух внешне не связанных друг с другом величин L2(Дr, Д_s) и O(Д_r, Д_s) лежит некий общий фактор (общая причина), приводящий к их статистической зависимости.

Таким фактором может являться наличие дубликатовв хронологических списках имен. В самом деле, как было показано выше, дублирующие друг друга определяющие окрестности в хронологическом списке имеют (в среднем) повышенное значение связи L_0. То же верно и для связей L_1, L_2.

Но с другой стороны, и значение O(Д_r, Д_s) для них должно быть в среднем выше, чем для пар независимых определяющих окрестностей, так как дубликаты иногда (не далеко не всегда!) используют одни и те же имена (точнее: использут одинаковые имена чаще, чем недубликаты, что и приводит к повышению значения O(Д_r, Д_s)). Таким образом, присутствие в списке Х дубликатов приводит к прямой зависимости (в статистическом смысле) величины L_2(Д_r, Д_s) от O(Д_r, Д_s). Эту зависимость мы и обнаруживаем в упомянутых примерах.

Замечание.

Может показаться, что для различения дубликатов в хронологических списках можно было бы использовать значения O(Д_r, Д_s) с тем же успехом, что и L_0(Д_r, Д_s). Отметим, что подсчет O(Д_r, Д_s) вычислительных сложностей не представляет какова бы ни была длина списка (т. к. сложность его вычисления вообще не зависит от длины списка).

Между тем, вычисление связей L_0, L_1 или L_2 для реальных списков, которые содержат сотни и тысячи имен, требует многочасовых вычислений на современных ЭВМ (сложность их вычисления пропорциональна квадрату длины списка).

Однако, использование O(Д_r, Д_s) в качестве меры связи отрезков списка, дает слишком «зашумленную» картину и не позволяет, в реальных примерах, надежно определить дубликаты в нем. Дело в следующем. Если O(Д_r, Д_s) велико, то, как правило, велико и значение L_0, L_1 или L_2.

Но обратное верно далеко не всегда. При больших значениях связи L_0, L_1 или L_2 соответствующее значение O(Д_r, Д_s) часто оказывается небольшим. Это означает, что дубликаты в значительной доле случаев используют различные имена для обозначения одних и тех же деятелей (иначе они были бы все видны «на глаз»). Использование же связей типа L_0 позволяет «выжать» из хронологического списка ту информацию о его структуре, которая на глаз не видна и определить дубликаты даже в том случае если все имена, используемые в них, попарно различны.

Для всех рассмотренных нами хронологических списков использование связей L_0, L_1 и L_2 приводило к одному и тому же виду ответа (обнаруживались одни и те же системы дубликатов). Поэтому мы будем иногда говорить просто о связи L, подразумевая под этим одну из связей L_0, L_1 или L_2.