Заметим, что число слагаемых в двойной сумме,
определяющей значение связи L_0(\ВД\А_r, \ВД\А_s), равно множителю (2k + 1)^2,
стоящему в знаменателе. Следовательно, среднее значение по
размещениям для связи L_0(\ВД\А_r, \ВД\А_s) равняется среднему значению по
размещениям для связи l(a_i, a_j), умноженному на c, то есть равно
c\Ва\А(Х). Лемма 2 доказана.
p3'3'4
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).
Этот вывод был получен на основе сравнения гистограмм частот
значений L_0(\ВД\А_r, \ВД\А_s) при условии, что значение O(\ВД\А_r, \ВД\А_s)
фиксировано.)
Может показаться, что значение связи L_0(\ВД\А_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
\
L_1(\ВД\А_r, \ВД\А_s) = --------Д l(a, b),
/
|\ВД\А'_r|\Иx\А|\ВД\А'_s|
a\ВEД\А_r, b\ВEД\А'_s
c
\
L (\ВД\А_r, \ВД\А_s) = ----------Д l(a, b).
2 /
|\ВД\А"_{r, s}|\Иx\А|\ВД\А'_s|
a\ВEД\А"_{r, s}, b\ВEД\А'_s
Здесь через |ч| обозначена длина (разреженной) определяющей
окрестности, то есть число имен в ней.
Легко проверить, что определенная таким образом величина
связи L_2 НЕ ЗАВИСИТ ОТ ПОРЯДКА определяющих окрестностей:
L_2(\ВД\А_r, \ВД\А_s) = L_2(\ВД\А_s, \ВД\А_r).
Величина связи L_2(\ВД\А_r, \ВД\А_s) уже не связана напрямую с общими
именами в \ВД\А_r и \ВД\А_s -- эти имена в ее определении вообще не
участвуют. Оказалось однако, что для реальных списков,
относящихся к древней и средневековой истории Европы, зависимость
связи L_2(\ВД\А_r, \ВД\А_s) от O(\ВД\А_r, \ВД\А_s) остается прежней (такой же, как и
описанная выше зависимость L_0(\ВД\А_r, \ВД\А_s) от O(\ВД\А_r, \ВД\А_s) ). То же верно и
для связи L_1(\ВД\А_r, \ВД\А_s).
Итак, в примерах, относящихся к древней и средневековой
истории Европы (о них -- ниже) было обнаружено, что в основе двух
внешне не связанных друг с другом величин L_2(\ВД\А_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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
определяющей значение связи L_0(\ВД\А_r, \ВД\А_s), равно множителю (2k + 1)^2,
стоящему в знаменателе. Следовательно, среднее значение по
размещениям для связи L_0(\ВД\А_r, \ВД\А_s) равняется среднему значению по
размещениям для связи l(a_i, a_j), умноженному на c, то есть равно
c\Ва\А(Х). Лемма 2 доказана.
p3'3'4
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).
Этот вывод был получен на основе сравнения гистограмм частот
значений L_0(\ВД\А_r, \ВД\А_s) при условии, что значение O(\ВД\А_r, \ВД\А_s)
фиксировано.)
Может показаться, что значение связи L_0(\ВД\А_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
\
L_1(\ВД\А_r, \ВД\А_s) = --------Д l(a, b),
/
|\ВД\А'_r|\Иx\А|\ВД\А'_s|
a\ВEД\А_r, b\ВEД\А'_s
c
\
L (\ВД\А_r, \ВД\А_s) = ----------Д l(a, b).
2 /
|\ВД\А"_{r, s}|\Иx\А|\ВД\А'_s|
a\ВEД\А"_{r, s}, b\ВEД\А'_s
Здесь через |ч| обозначена длина (разреженной) определяющей
окрестности, то есть число имен в ней.
Легко проверить, что определенная таким образом величина
связи L_2 НЕ ЗАВИСИТ ОТ ПОРЯДКА определяющих окрестностей:
L_2(\ВД\А_r, \ВД\А_s) = L_2(\ВД\А_s, \ВД\А_r).
Величина связи L_2(\ВД\А_r, \ВД\А_s) уже не связана напрямую с общими
именами в \ВД\А_r и \ВД\А_s -- эти имена в ее определении вообще не
участвуют. Оказалось однако, что для реальных списков,
относящихся к древней и средневековой истории Европы, зависимость
связи L_2(\ВД\А_r, \ВД\А_s) от O(\ВД\А_r, \ВД\А_s) остается прежней (такой же, как и
описанная выше зависимость L_0(\ВД\А_r, \ВД\А_s) от O(\ВД\А_r, \ВД\А_s) ). То же верно и
для связи L_1(\ВД\А_r, \ВД\А_s).
Итак, в примерах, относящихся к древней и средневековой
истории Европы (о них -- ниже) было обнаружено, что в основе двух
внешне не связанных друг с другом величин L_2(\ВД\А_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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153