4. 7. Метод построения матриц связей. Предназначен для поиска дубликатов в хронологических списках

Здесь мы на приведенном выше модельном примере изложим лишь общую идею методики. Метод был предложен авторами в [10], [12]. Подробно он изложена в главе 3.

Анализ дубликатов (исходных малых колод) в колоде К можно осуществить на основе следующих простых соображений.

Предположим, что имеющаяся в нашем распоряжении колода К была действительно получена описанным выше способом из нескольких экземпляров более короткой (исходной) колоды. Рассмотрим два отрезка А1 и А2 колоды К. Будем называть отрезки А1 и А2 дубликатами, если они соотвественно содержат карты, которые в экземплярах исходной колоды находились рядом (рис. 19).

Заметим, что при этом может случиться, что отрезки А1 и А2 вовсе не содержат одинаковых карт и тем не менее, являются дубликатами. Такая ситуация возникает, когда в отрезок А при тасовании попали одни карты из некоторого малого отрезка А исходной колоды, а в отрезок А – другие карты из того же «прообраза» А (рис. 19).

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

Однако в любом случае, если А1 и А2 – действительно дубликаты, то есть содержат части, восходящие к общему прообразу А в исходной короткой колоде, то среди множества экземпляров их прообраза А, разбросанных при тасовании по колоде К и как-то искаженных при этом, должны встретиться и такие экземпляры, которые содержат как карты, попавшие из А1 в А2, так и карты, попавшие в А (на рис. 19 такой экземпляр А обведен кружком).

Следовательно, в том случае, когда А1 и А2 – дубликаты, вероятность встреч карт из А1 и А2 где-нибудь в колоде К, больше, чем аналогичная вероятность в случае, когда А1 и А2 дубликатами не являются (естественно, имеются в виду не сами экземпляры карт из А1 и А2, а такие же карты).

В самом деле, в первом случае действует описанный механизм, объединяющий карты из А1 и А2 в колоде К, а во втором – это объединение может произойти лишь чисто случайным образом.

Приведенные соображения позволяют предложить методику, разделяющую всевозможные пары отрезков А1 и А2 колоды К на два множества: множество пар-дубликатов (в статистическом смысле) и множество «независимых» пар.

Эта методика требует значительного объема вычислений на ЭВМ. При применении к хронологическим спискам имен ее результатом является так называемая матрица связей списка, дающая его разложение на систему дублирующих друг друга «слоев». Методика была впервые предложена авторами в [11]. Подробное изложение метода см. в главе 3.

Глава 2. Определение сдвигов в хронологии по гистограммам частот разнесений связанных имен

1. Основные определения

1. 1. Большая колода карт и составляющие ее малые колоды

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

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

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

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