Пусть к к -- некая пара последовательных карт в К (то есть к и
1 2 1
к -- соседи). Предположим, что к и к -- "истинные" соседи, то есть
2 1 2
они были соседями также и в исходных малых колодах, до тасования.
Тогда пары вида к к, разбросанные по колоде К, будут отмечать в
1 2
ней положения своих малых колод (откуда они пришли).
Сдедовательно, расстояния (разнесения) между такими парами
будут равны сдвигам (разнесениям) между экземплярами малых колод
в К.
Это -- идеальная ситуация. В реальности, конечно, по
экземплярам одной только пары к к в колоде К судить о сдвигах
1 2
между дубликатами (малыми колодами) в К нельзя, даже если сама
пара к к -- "истинная". В самом деле некоторые экземпляры этой
1 2
пары могут случайным образом быть разбиты при тасовании и
информация о соответствущем сдвиге в этом случае потеряется.
С другой стороны, среди экземпляров пары к к могут
1 2
встретиться и "ложные", случайно возникшие при тасовании, и в
этом случае мы зарегистрируем ложный сдвиг. Кроме того, мы
заранее не знаем -- "истиная" ли данная пара карт-соседей в К или
нет.
Поэтому поступим следующим образом. Чтобы исключить потерю
информации при случайном разбиении пар к к в ходе тасования,
1 2
будем рассматривать карты к и к в колоде К по отдельности.
1 2
Итак, ПОДСЧИТАЕМ РАССТОЯНИЯ МЕЖДУ ВСЕМИ ПАРАМИ КАРТ В К, ПРИ
УСЛОВИИ ОДНАКО, ЧТО ХОТЯ БЫ В ОДНОМ МЕСТЕ КОЛОДЫ К ЭТИ (ТАКИЕ ЖЕ)
КАРТЫ ВСЕ ЖЕ СТОЯТ РЯДОМ (ЯВЛЯЮТСЯ СОСЕДЯМИ).
В чем смысл этого условия? Оно позволяет выделить такую
совокупность пар карт, в которой "истинные" карты-соседи
составляют заметную долю. В самом деле, пусть к к -- "истинная"
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
множества: множество пар-дубликатов (в статистическом смысле) и
множество "независимых" пар.
Эта методика требует значительного объема вычислений на ЭВМ.
При применении к хронологическим спискам имен ее результатом
является так называемая МАТРИЦА СВЯЗЕЙ списка, дающая его
разложение на систему дублирующих друг друга "слоев".
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