Чтение онлайн

1 2 пара карт-соседей. Поскольку все исходные малые колоды были до тасования одинаковы, то эта пара существовала перед тасованием в N экземплярах (где N -- число исходных малых колод).

Чтобы данная пара карт НЕ ПОПАЛА в нашу совокупность, необходимо, чтобы ВСЕ N экземпляров этой пары были разъединены при тасовании.

Вероятность этого события МАЛА.

С другой стороны, для "ложной" пары карт-соседей условием ПОПАДАНИЯ в указанную совокупность является случайная встреча этих карт при тасовании, что при неполном "блочном" тасовании ТАКЖЕ МАЛОВЕРОЯТНО.

Таким образом, большинство "ИСТИННЫХ" пар карт-соседей ПОПАДУТ в нашу совокупность, а большинство "ЛОЖНЫХ" -- НЕ ПОПАДУТ в нее. В итоге, существенную часть этой совокупности составят "истинные" пары карт-соседей.

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

По этому набору построим график -- ГИСТОГРАММУ ЧАСТОТ РАЗНЕСЕНИЙ КАРТ-СОСЕДЕЙ следующим образом. Отложим по горизонтальной оси все возможные значения разнесений между картами в колоде К (ясно, что разнесения не могут превосходить длины К), а по вертикальной оси -- частоту, с которой данное значение встречается в наборе разнесений.

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

1 2

Если "необычно" частых значений разнесения между картами-соседями в колоде К нет, то соответствующая гистограмма ВООБЩЕ НЕ БУДЕТ СОДЕРЖАТЬ ВСПЛЕСКОВ (доказательство см. в главе 2).

В ЭТОМ СЛУЧАЕ СЛЕДУЕТ ПРЕДПОЛОЖИТЬ, ЧТО ДУБЛИКАТОВ ОПИСАННОГО ВЫШЕ ТИПА В КОЛОДЕ К НЕТ.

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

4. 7. МЕТОД ПОСТРОЕНИЯ МАТРИЦ СВЯЗЕЙ.

ПРЕДНАЗНАЧЕН ДЛЯ ПОИСКА ДУБЛИКАТОВ В ХРОНОЛОГИЧЕСКИХ СПИСКАХ

Здесь мы на приведенном выше модельном примере изложим лишь ОБЩУЮ ИДЕЮ методики. Метод был предложена авторами в [10, 12]. Подробно он изложена в главе 3.

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

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

1 2 1 2 ДУБЛИКАТАМИ, если они соотвественно содержат карты, которые в экземплярах исходной колоды находились рядом (рис. 19).

Заметим, что при этом может случиться, что отрезки А и А

1 2 вовсе не содержат одинаковых карт и тем не менее, являются дубликатами. Такая ситуация возникает, когда в отрезок А при

1 тасовании попали одни карты из некоторого малого отрезка А исходной колоды, а в отрезок А -- другие карты из того же

2 "прообраза" А (рис. 19).

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

Однако в любом случае, если А и А -- действительно

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

1 попавшие в А (на рис. 19 такой экземпляр А обведен кружком).

2

Следовательно, в том случае, когда А и А -- дубликаты,

1 2 вероятность встреч карт из А и А где-нибудь в колоде К, БОЛЬШЕ,

1 2 чем аналогичная вероятность в случае, когда А и А дубликатами

1 2 не являются (естественно, имеются в виду не сами экземпляры карт из А и А, а такие же карты).

1 2

В самом деле, в первом случае действует описанный механизм, объединяющий карты из А и А в колоде К, а во втором -- это

1 2 объединение может произойти лишь чисто случайным образом.

Приведенные соображения позволяют предложить методику, разделяющую всевозможные пары отрезков А и А колоды К на два

1 2 множества: множество пар-дубликатов (в статистическом смысле) и множество "независимых" пар.

Эта методика требует значительного объема вычислений на ЭВМ. При применении к хронологическим спискам имен ее результатом является так называемая МАТРИЦА СВЯЗЕЙ списка, дающая его разложение на систему дублирующих друг друга "слоев". Методика была впервые предложена авторами в [11-13]. Подробное изложение метода см. в главе 3.

p3'2'1

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

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

1. 1. БОЛЬШАЯ КОЛОДА КАРТ И СОСТАВЛЯЮЩИЕ ЕЕ МАЛЫЕ КОЛОДЫ

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

Предположим, что в нашем распоряжении имеется некоторая последовательность карт К (колода карт), которая может содержать ПОВТОРЯЮЩИЕСЯ КАРТЫ. Будем говорить, что колода К СОДЕРЖИТ ДУБЛИКАТЫ, если она получена из нескольких одинаковых по составу и порядку более коротких колод карт Х (также содержащих, возможно, повторяющиеся карты), которые были сложены подряд в одну общую колоду ХХ... Х, а затем получившаяся таким образом БОЛЬШАЯ КОЛОДА БЫЛА ПЕРЕТАСОВАНА.

Мы допускаем, что перед тасованием каждый экземпляр исходной колоды Х был как-то ИСКАЖЕН. Под ИСКАЖЕНИЯМИ будем понимать случайное исключение, дублирование или замену отдельной карты или же последовательности подряд стоящих карт. Предположим однако, что локальные искажения в различных частях каждой из исходных колод НЕЗАВИСИМЫ друг от друга.

Если же исследуемая колода ДУБЛИКАТОВ НЕ СОДЕРЖИТ (то есть порядок карт в ней не порожден описанным выше механизмом), будем называть порядок карт в колоде ПРАВИЛЬНЫМ.