Как найти величины хронологических сдвигов

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

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

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

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

Простейший отрезок колоды – это две последовательно расположенные в ней карты. (Такие карты мы в дальнейшем будем называть картами-соседями.) Если имеющаяся в нашем распоряжении большая колода действительно была получена с помощью описанного выше механизма «блочного тасования» из нескольких одинаковых малых колод, то многие из карт-соседей в ней были соседями и в исходных малых колодах.

Конечно, в ходе тасования появятся и новые «ложные» пары карт-соседей. Но все же доля «истинных» (исходных) соседей среди всех пар карт-соседей большой колоды будет значительной.

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

Используя описанную модельную задачу, перейдем к неформальному описанию методик статистического анализа хронологических списков.

4. 6. Метод гистограмм частот разнесения связанных имен.
Определяет величины сдвигов между дубликатами в хронологических списках

Здесь мы на модельном примере изложим идею и основные шаги методики. На формальном уровне она изложена в главе 2.

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

Пусть k1 k2 – некая пара последовательных карт в К (то есть k1 и k2 – соседи). Предположим, что k1 и k2 – «истинные» соседи, то есть они были соседями также и в исходных малых колодах, до тасования. Тогда пары вида k1 k2, разбросанные по колоде К, будут отмечать в ней положения своих малых колод (откуда они пришли).

Сдедовательно, расстояния (разнесения) между такими парами будут равны сдвигам (разнесениям) между экземплярами малых колод в К. Это – идеальная ситуация. В реальности, конечно, по экземплярам одной только пары k1 k2 в колоде К судить о сдвигах между дубликатами (малыми колодами) в К нельзя, даже если сама пара k1 k2 – «истинная». В самом деле некоторые экземпляры этой пары могут случайным образом быть разбиты при тасовании и информация о соответствущем сдвиге в этом случае потеряется.

С другой стороны, среди экземпляров пары k1 k2 могут встретиться и «ложные», случайно возникшие при тасовании, и в этом случае мы зарегистрируем ложный сдвиг. Кроме того, мы заранее не знаем – «истиная» ли данная пара карт-соседей в К или нет.

Поэтому поступим следующим образом. Чтобы исключить потерю информации при случайном разбиении пар k1 k2 в ходе тасования, будем рассматривать карты k1 и k2 в колоде К по отдельности.

Итак, подсчитаем расстояния между всеми парами карт в К, при условии однако, что хотя бы в одном месте колоды К эти (такие же) карты все же стоят рядом (являются соседями). В чем смысл этого условия? Оно позволяет выделить такую совокупность пар карт, в которой «истинные» карты-соседи составляют заметную долю. В самом деле, пусть k1 k2 – «истинная» пара карт-соседей. Поскольку все исходные малые колоды были до тасования одинаковы, то эта пара существовала перед тасованием в N экземплярах (где N – число исходных малых колод).

Чтобы данная пара карт не попала в нашу совокупность, необходимо, чтобы все N экземпляров этой пары были разъединены при тасовании.

Вероятность этого события мала.

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

Таким образом, большинство «истинных» пар карт-соседей попадут в нашу совокупность, а большинство «ложных» – не попадут в нее. В итоге, существенную часть этой совокупности составят «истинные» пары карт-соседей.

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

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

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

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

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.

Поиск по сайту: