Г.В.Носовский, А.Т.Фоменко.
ИМПЕРИЯ.

© Copyright Глеб Владимирович Носовский, Анатолий Тимофеевич Фоменко

Глава 3. МАТРИЦЫ СВЯЗЕЙ ДЛЯ ХРОНОЛОГИЧЕСКИХ СПИСКОВ ИМЕН

1. КАК УЗНАТЬ -- КАКИЕ ИМЕННО ЧАСТИ ЛЕТОПИСИ

ЯВЛЯЮТСЯ ДУБЛИКАТАМИ?

В предудущей главе с помощью гистограмм частот разнесений связанных имен проверялась гипотеза об отсутствии дубликатов в данном хронологическом списке имен.

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

КАКИЕ ИМЕННО ЧАСТИ СПИСКА ЯВЛЯЮТСЯ ДУБЛИКАТАМИ И В КАКОЙ МЕРЕ?

Напомним, что в соответствии с понятием слоистой хроники, два отрезка хронологического списка называются ДУБЛИКАТАМИ, если они содержат соответственно ДУБЛИРУЮЩИЕ ДРУГ ДРУГА СЛОИ.

В данной главе мы опишем метод, позволяющий отвечать на этот вопрос. Результатом его применения к историческому хронологическому списку будет являться так называемая ``МАТРИЦА СВЯЗЕЙ'' (фрагментов) данного списка. Это -- КВАДРАТНАЯ ТАБЛИЦА, показывающая в какой мере те или иные отрезка списка имен являются дубликатами друг друга ("связаны'' между собой).

Мы уже вкратце описали идею метода, пользуясь модельной задачей о колоде карт (см. главу 1). Проведем теперь эти рассуждения уже не для модельной задачи, а для РЕАЛЬНЫХ хронологических списков.

Пусть имеется список имен Х, который может содержать ошибки, пропуски и (или) дубликаты.

НЕИЗВЕСТНЫЙ НАМ ИСТИННЫЙ СПИСОК ИМЕН, лежащий в основе реального списка Х, обозначим через Y. Таким образом, Y - ВООбРАЖАЕМЫЙ список имен, содержащий полные неискаженные данные (скажем, об именах правителей данного государства) для длительного исторического промежутка времени I_Y.

РЕАЛЬНЫЙ список имен Х, который находится в нашем распоряжении является ИСКАЖЕНИЕМ, ``зашумлением'' списка Y с возможной потерей доли информации.

Предположим, что промежуток времени I_Y был описан МНОГИМИ летописцами -- очевидцами или современниками происходящих событий.

Каждый из них составлял свою короткую летопись Z_i по современным ему событиям. Поскольку мы изучаем сейчас не весь текст летописи, а только имена, извлеченные из нее, то можем считать (для удобства), что каждый летописец составлял некий короткий хронологический список имен, который мы также обозначим через Z_i.

Если промежуток времени I_Y описывался K летописцами, то в основе наших знаний о события, происходивших на этом промежутке, лежит K коротких летописей Z_1, Z_2,..., Z_K (включая и утраченные летописи). Множество этих летописей (коротких хронологических списков имен) мы обозначим через {Z_i}.

Множество {Z_i} образует некоторое покрытие списка Y. Это покрытие мы будем считать:

а) Достаточно плотным, то есть предположим, что каждый отдельный год из промежутка I_Y описывался не одним, а сразу несколькими летописцами независимо друг от друга.

б) Состоящим из уже искаженных -- как-то разреженных и местами ошибочных коротких хронологических списков. В самом деле, даже в своем исходном виде каждая из летописей Z_1, Z_2,..., Z_K упоминала, возможно, не все имена правителей, не всех исторических деятелей, участвующих в событиях. Кроме того, при последующем переписывании и компиляциях появлялись ошибки, пропуски, произвольные вставки и т. п. Для простоты рассуждений мы будем считать все эти ошибки присущими летописям Z_i с самого начала.

Итогом работы по составлению хронологии в ее современном виде явилась некоторая новая склейка списков Z_i (новое совмещение их на оси времени), которая и породила известный нам хронологический список имен Х.

Рассмотрим два отрезка \ВД\А_1, \ВД\А_2 списка имен Х и попытаемся ответить на вопрос: нет ли такой пары Z_i, Z_j коротких хронологических списков из множества {Z_i}, которые в списке Y (в реальности) относились к одному и тому же месту, а в списке Х оказались ``подклеенными'' к \ВД\А_1 и \ВД\А_2 соответственно? Так же как и в модельном примере с картами (см. главу 1), заключаем, что если такая пара есть, то увеличивается вероятность того, что имена из \ВД\А_1 и \ВД\А_2 окажутся близко друг от друга где-то в списке Х (за счет третьей, ``склеивающей'' летописи Z_m, смешивающей имена из Z_i и Z_j).

p3'3'2

2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ СВЯЗЕЙ МЕЖДУ ДУБЛИКАТАМИ

В ЛЕТОПИСИ

Пусть дан хронологический список имен Х. Начиная с этого места забудем на время о разбиении списка Х на главы. В отличие от задачи определения ВЕЛИЧИН СДВИГОВ между дубликатами, для построения МАТРИЦЫ СВЯЗЕЙ временна'я шкала в списке не используется. После построения матрицы мы снова воспользуемся ею для СОДЕРЖАТЕЛЬНОЙ интерпретации результатов.

Для уточнения понятий ``отрезок списка'' и ``близость в списке'' введем следующие определения.

ОПРЕДЕЛЕНИЕ. Для i-го имени a_i в списке имен Х = {a_1,..., a_n} его ОПРЕДЕЛЯЮЩЕЙ ОКРЕСТНОСТЬЮ РАДИУСА k назовем отрезок списка:

\ВД\А_{a_i}(k) = \ВД\А_i(k) = \ВД\А_i = {a_{i-k},..., a_{i+k}}, (k

Определяющая окрестность радиуса k не вводится для k первых и k последних имен списка. Число 2k+1, равное числу имен в определяющей окрестности, будем называть ДЛИНОЙ этой окрестности.

ОПРЕДЕЛЕНИЕ. НЕНОРМИРОВАННОЙ СВЯЗЬЮ двух имен из множества I различных имен списка Х назовем число пар таких же имен, расположенных друг от друга в списке Х на расстоянии меньшем, чем p (то есть разность их номеров в списке меньше, чем p). Число p явяется параметром модели и называется ДЛИНОЙ СВЯЗЫВАЮЩЕЙ ОКРЕСТНОСТИ. Ненормированную связь имен u_i и u_j обозначим через l_0(u_i, u_j).

Параметры k и p подбирались в каждом случае отдельно с целью получить наиболее четкий результат. Оказалось однако, что изменение этих параметров для реальных хронологических списков имен слабо влияет на результат.

В частности, общая структура матрицы связей оставалась неизменной при всех рассмотренных значениях k и p (1\Д<\Аk\Д<\А7, 3\Д<\Аp\Д<\А17).

НЕНОРМИРОВАННАЯ СВЯЗЬ l_0(u_i, u_j) неудобна тем, что она не учитывает резких различий В КРАТНОСТЯХ вхождения имен в список Х, характерных для реальных хронологических списков. В то же время, часто употреблямые имена естественным образом должны в среднем чаще ``случайно'' есближаться в списке Х, чем имена более редкие. Чтобы исключить влияние кратности имен на их связь, введем следующее определение.

ОПРЕДЕЛЕНИЕ. Пусть два имени u_i и u_j входят в список Х с кратностями k_i и k_j соответственно. Назовем НОРМИРОВАННОЙ СВЯЗЬЮ этих имен (или просто -- СВЯЗЬЮ) число

| l_0(u_i, u_j)

---------- при iЬj,

k_ik_j

l(u_i, u_j) = { (*)

| 2l_0(u_i, u_j)

| ---------- при i=j, k_i>1.

Ю k_i(k_i- 1)

Для уникального имени в списке (то есть при i=j, k_i=1) понятие связи такого имени с самим собой не вводится.

Поясним выбор нормировки в этом определении. Эта нормировка выбиралась так, чтобы связь любой пары имен из списка Х являлась бы случайной величиной со средним, не зависящим от выбора этой пары.

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

ПРЕДПОЛОЖЕНИЕ.

ЗНАНИЕ ЛИШЬ НЕУПОРЯДОЧЕННОГО МНОЖЕСТВА ИМЕН ПРАВИЛЬНОГО ХРОНОЛОГИЧЕСКОГО СПИСКА Х НЕ МОЖЕТ НЕСТИ В СЕБЕ НИКАКОЙ ИНФОРМАЦИИ О ПОРЯДКЕ СЛЕДОВАНИЯ ЭТИХ ИМЕН В СПИСКЕ Х.

В этом предположении справедлива следующая лемма.

ЛЕММА 1. Пусть дан правильный хронологический список Х. Предположим, что максимальная кратность имени в этом списке, а также параметр p (длина связывающей окрестности) много меньше длины списка Х. Тогда среднее значение ненормированной связи двух имен u_i и u_j, входящих в список Х с кратностями k_i и k_j соответственно, пропорционально числу

| k_ik_j при iЬj,

c(u_i, u_j) = c(k_i, k_j) = {

k_i(k_i-1)/2 при i=j.

ДОКАЗАТЕЛЬСТВО.

а) Рассмотрим случай iЬj. Схему равновероятных размещений имен в списке Х можно представить как итог последовательного размещения n имен по n местам в списке. При этом, каждое имя равновероятно занимает одно из оставшихся свободными мест. Очередность размещения имен может быть выбрана произвольно, но будучи выбранной должна быть фиксирована.

Поэтому можно считать, что перед размещением k_j экземпляров имени u_j все k_i экземпляров имени u_i уже размещены. По предположению, k_i, k_j, p \а<\А n (напомним, что n обозначает длину списка Х). Поэтому числом случаев, когда два экземпляра имени u_i оказались в списке Х рядом (на расстоянии, меньшем, чем p) можно пренебречь по сравнению с общим числом способов размещения k_i экземпляров имени u_i в списке Х.

Представим теперь размещение k_j экземпляров имени u_j в виде последовательности испытаний Бернулли, причем успехом в одном испытании будем считать попадание в связывающую окрестность к одному из уже размещенных экземпляров имени u_i. Тогда значение ненормированной связи l_0(u_i, u_j) равно числу успехов в этой схеме Бернулли.

Вероятность успеха в одном испытании при этом пропорциональна числу k_i уже размещенных имен u_i (точнее говоря, пренебрегая влиянием случайного перекрытия связывающих окрестностей этих имен, получаем, что эта вероятность равна 2pk_i/n). Общее количество испытаний при этом равно k_j. Среднее число успехов (=среднее значение ненормированной связи l_0(u_i, u_j)) пропорционально произведению вероятности успеха в одном испытании на число испытаний, то есть пропорционально k_ik_j. Это и утверждается в лемме.

б) Рассмотрим случай i=j. Выберем последовательность размещения имен таким образом, чтобы сначала размещались все k_i экземпляров имени u_i, а затем -- все остальные имена. Пусть первый экземпляр имени u_i уже размещен. Вероятность того, что при размещении второго экземпляра он попадет в связывающую окрестность к уже размещенному первому экземпляру этого имени, равна 2p/n (здесь мы пренебрегаем вероятностью того, что первый экземпляр попал на самый край списка, и захват его связывающей окрестности оказался меньше, чем 2p, по сравнению с вероятностью того, что это не так).

Аналогично, пренебрегая малыми вероятностями перекрытий связывающих окрестностей (слагаемыми второго порядка), получаем, что третий экзеипляр имени u_i попадает в связывающую окрестность к одному из уже размещенных экземпляров с вероятностью 2(2p/n) и т. д. Для i-того экземпляра эта вероятность равно (i-1)2p/n.

Введем случайные величины \Вh\А_i (2 \Д<\А i \Д<\А k_i), положив по определению \Вh\А_i=1 если i-й экземпляр имени u_i при своем размещении попал в связывающую окрестность к одному из уже размещенных (i-1) экземпляров этого имени, и \Вh\А_i=0 иначе. Тогда, согласно приведенным рассуждениям,

P{\Вh\А_i=1} = (i-1)2p/n, (2 \Д<\А i \Д<\А k_i).

Заметим теперь, что число ``встреч'' имен u_i в списке Х (где под встречей понимается попадание пары имен в связывающую окрестность друг к другу) равняется сумме случайных величин \Вh\А_i:

k_i

l_o(u_i, u_j) = \ВS\А \Вh\А_i.

i=2

Следовательно, математическое ожидание (среднее значение) связи l_0(u_i, u_j) равно

k_i k_i 2p

M[l_0(u_i, u_j)] = M[ \ВS\А \Вh\А_i] = \ВS\А M[\Вh\А_i] = -- (1+... +(k_i-1))=

i=2 i=2 n

2p k_i(k_i-1)

= -- --------Д.

n 2

Дело в том, что математическое ожидание суммы случайных величин равно сумме их математических ожиданий, а M[\Вh\А_i] = P{\Вh\А_i=1} = (i-1)2p/n.)

Лемма доказана.

СЛЕДСТВИЕ. Среднее значение связи l(u_i, u_j) двух имен, входящих в правильный хронологический список Х, НЕ ЗАВИСИТ от выбора пары имен (u_i, u_j) и, следовательно, является ХАРАКТЕРИСТИКОЙ СПИСКА Х и параметров модели.

Это среднее мы будем обозначать через \Ва\А(Х). Из доказательства леммы следует, что \Ва\А(Х) = 2p/n.

Генеральное (теоретическое) среднее \Ва\А(Х) мы будем называть СРЕДНИМ ПО РАЗМЕЩЕНИЯМ в отличие от эмпирического СРЕДНЕГО ПО МАТРИЦЕ, получаемого усреднением фактических значений связи пар имен по всем парам имен, входящих в данный список Х.

Последнее название объясняется тем, что значения связи пар имен списка естественным образом составляют некоторую квадратую матрицу.

ЗАМЕЧАНИЕ. Сформулированное выше предположение aposteriori подтверждается для реальных правильных хронологических списков (летописей) тем, что для них ЭМПИРИЧЕСКОЕ СРЕДНЕЕ ПО МАТРИЦЕ практически совпадает с ГЕНЕРАЛЬНЫМ СРЕДНИМ ПО РАЗМЕЩЕНИЯМ \Ва\А(Х) (вычисленным с помощью этого предположения).

Если же список содержит дубликаты, то для него, как показали расчеты, среднее по матрице обычно чуть больше, чем среднее по размещениям.

Но различие между этими величинами было НЕВЕЛИКО для всех рассмотренных нами реальных исторических списков. Это -- отражение того обстоятельства, что даже в том случае, когда хронологический список имен содержит дубликаты, доля пар-дубликатов среди общего количества всех пар определяющих окрестностей, обычно невелика.

В соответствии с описанной в главе 1 моделью возникновения дубликатов в хронологический списках (см., например, модельную задачу о колодах карт), введем меру связи двух произвольных определяющих окрестностей \ВД\А_r, \ВД\А_s в списке Х.

Эта мера отражает количество ``связывающих летописей'' для данной пары отрезков списка, нормированное таким образом, чтобы при отсутствии дубликатов в списке, оно сохраняло бы приблизительно одно и то же значение для всех пар определяющих окрестностей списка Х.

Более точно, мера связи двух отрезков списка подбиралась таким образом, чтобы в случае правильного списка (который мы, в соответствии со сделанным предположением, рассматриваем как некоторый случайный элемент) среднее значение этой меры не зависело бы от выбора конкретной пары отрезков, то есть было бы единым для всего списка Х.

ОПРЕДЕЛЕНИЕ. Пусть дан хронологический список имен Х и фиксированы параметры модели k и p. Назовем СВЯЗЬЮ ДВУХ ОПРЕДЕЛЯЮЩИХ ОКРЕСТНОСТЕЙ \ВД\А_r и \ВД\А_s списка Х число

r+k s+k

c \ \

L_0(\ВД\А_r, \ВД\А_s) = -------- l(a_i, a_j).

(2k + 1)^2 / /

i=r-k j=s-k

jЬi

Здесь c -- постоянная масштаба, задаваемая из соображений удобства вычислений (мы брали значение c=25).

ЛЕММА 2. Если хронологический список имен Х не содержит дубликатов (является правильным) и выполнены предположения Леммы 1, то среднее значение по размещениям для связи L_0(\ВД\А_r, \ВД\А_s) НЕ ЗАВИСИТ от \ВД\А_r и \ВД\А_s и равно c\Ва\А(Х).

Доказательство. Утверждение Леммы 2 следует из Леммы 1 и из того, что среднее значение суммы случайных величин равно сумме их средних значений. Заметим, что число слагаемых в двойной сумме, определяющей значение связи 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.

ОПРЕДЕЛЕНИЕ. Положим

L_1(\ВД\А_r, \ВД\А_s) = --------Д l(a, b),

|\ВД\А'_r|\Иx\А|\ВД\А'_s|

a\ВEД\А_r, b\ВEД\А'_s

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.

p3'3'5

5. РАЗЛИЧЕНИЕ ЗАВИСИМЫХ И НЕЗАВИСИМЫХ ПАР

ОПРЕДЕЛЯЮЩИХ ОКРЕСТНОСТЕЙ В ХРОНОЛОГИЧЕСКИХ СПИСКАХ ИМЕН

Перейдем к описанию способа определения порогов в множестве значений связи $L(\Delta_r, \Delta_s)$, разделяющих зависимые и независимые пары определяющих окрестностей $\Delta_r, \Delta_s$. Приводимые ниже рассуждения имеют КАЧЕСТВЕННЫЙ характер. Они оправдываются aposteriori, так как позволяют получить более четкую картину структуры списка.

Важно, что наиболее существенные черты этой картины оказываются (во всех рассмотренных нами реальных примерах) нечуствительными не только к выбору параметров модели $k$ и $p$ (а также к приведенным выше изменениям в определении самой связи, что уже отмечалось), но и к колебаниям указанных порогов.

Пусть дан хронологический список имен Х. Зафиксируем для него параметры модели $(k, p)$ и построим набор гистограмм частот появления значений связи $L_0(\Delta_r, \Delta_s)$ ($L_1$ или $L_2$), при условии, что значение $O(\Delta_r, \Delta_s)$ постоянно (для каждой из гистограмм оно свое). В рассмотренных нами реальных списках все эти гистограммы имели вид приблизительно как на рис. 28.

В КАЧЕСТВЕ ЗНАЧЕНИЯ ПОРОГА, ОТДЕЛЯЮЩЕГО СВЯЗЬ $L_0$ ($L_1$, $L_2$) ДЛЯ НЕЗАВИСИМЫХ ПАР ОПРЕДЕЛЯЮЩИХ ОКРЕСТНОСТЕЙ $(\Delta_R, \Delta_S)$ ОТ СВЯЗИ ДЛЯ ЗАВИСИМЫХ ПАР $(\Delta_R, \Delta_S)$ ВОЗЬМЕМ НАИМЕНЬШЕЕ ЗНАЧЕНИЕ, ПРИ КОТОРОМ СООТВЕТСТВУЮЩАЯ ГИСТОГРАММА ПАДАЕТ ДО НУЛЯ (ЭТО ЗНАЧЕНИЕ ДЛЯ КАЖДОЙ ПАРЫ $(\Delta_R, \Delta_S)$, ВООБЩЕ ГОВОРЯ, СВОЕ, Т. К. ОНО ЗАВИСИТ ОТ ВЕЛИЧИНЫ $O(\Delta_R, \Delta_S)$).

Связь, превосходящую такой порог, будем называть СУЩЕСТВЕННОЙ связью, а связь, не превосходящую его - НЕСУЩЕСТВЕННОЙ связью.

ОПРЕДЕЛЕНИЕ. МАТРИЦЕЙ СВЯЗЕЙ $M(k, p, L_i, Х)$, $0\lei\le2$, хронологического списка имен Х называется построенная по этому списку квадратная верхнетреугольная матрица размера $(n-k)\times(n-k)$, в ячейке $(r, s)$ которой стоит значение $$ M_{r, s} =

\cases

L_i(\Delta_r, \Delta_s), & \text{если связь $L_i(\Delta_r, \Delta_s)$

определяющих} \\

& \text{окрестностей $\Delta_r$ и $\Delta_s$

существенна и $r\le s$;}

0, & \text{в противном случае. }

\endcases $$

p3'4'1

Продолжение