А.Т.Фоменко
МЕТОДИКА РАСПОЗНАВАНИЯ ДУБЛИКАТОВ И НЕКОТОРЫЕ ПРИЛОЖЕНИЯ

Докл. АН СССР., 1981. т.285, 6, c.1326-1330.
(Представлено академиком Е.П. Велиховым 22.1.1981)

1. Пусть в евклидовом пространстве Rn задано конечное множество точек D и многозначное отображение V: Rn->Rn, переводящее D в большее (конечное) множество V(D). Например, V может моделировать многократный процесс измерений случайной величины D, результаты которого неоднозначны вследствие случайных ошибок; V(D) можно рассматривать как множество значений, полученных в результате измерений. При этом каждое реальное значение х величины x превращается в множество точек V(х), представляющих исходное значение х; каждую точку из V(x) можно рассматривать как приближенное значение для х. При изучении реальных процессов трудность заключается в правильном моделировании (с помощью V) реальных ошибок. Пусть теперь D неизвестно, и мы знаем только множество V(D) "результатов измерений". Как распознать среди точек V(D) те из них, которые отвечают одной точке из D? Точки, отвечающие одному и тому же реальному значению, назовем дубликатами. Пусть V таково, что V(x)ЗV(y)=f, если xy.

1. Введем меру l удаленности друг от друга точек из V(D), стремясь к тому, чтобы точки, принадлежащие одному и тому же V(х), были достаточно близки в смысле меры l, а точки из разных V(х) и V(х), напротив, были далеки. Пусть a, bОV(D). Фиксируем точку a и построим специальную окрестность Hr, точки a. Будем стремиться к тому, чтобы точка a была центром Hr, а точка b была на границе Hr или близко к границе. Простейший вариант такой:
H'r= {cОRn: | ai - ci | <= | ai - bi |, 1<= i <= n}, т.е. H'r - параллелепипед с центром в a, имеющий точку b одной из своих вершин.

Для того чтобы эта конструкция стала пригодной для приложений, нужно дополнить ее, чтобы она моделировала механизм ошибок, влияющих на измерения. Ниже мы предъявим такую окрестность Hr(a,b), введем меру l удаленности точек a и b друг от друга, положив в основу определения схему, изложенную в [1], а именно: l(a,b) = vol Hr(a,b)/ vol V(D), где vol V(D) - число точек в множестве V(D), а vol Hr(a,b) - число точек из V(D), попавших в Hr(a,b).

3. Опишем задачу, для решения которой вводится эта мера l. Пусть обнаружен исторический текст, описывающий неизвестную нам династию правителей с указанием длительности их правлений. Является ли эта династия новой, ранее не встречавшейся, или это я одна из известных династий, но описанная в непривычных терминах (видоизмененные имена и т.д.)? Рассмотрим n последовательных реальных правителей (р. династию) с истинными длительностями правлений (p1, p2, ... , pn); часто одна и та же р. династия описывается в разных первоисточниках с разных точек зрения. Но существуют "инвариантные факты", описания которых мало зависят от автора текста, например, длительность правления: обычно нет особых причин, по которым автор значительно исказил бы это число. Тем не менее часто возникали трудности в вычислении длительностей правлений, приведшие к тому, что в разных документах для одного и того же правителя приводятся разные числа.

Итак, каждый автор, описывая р. династию p = (p1, p2, ... , pn), по-своему вычисляет длительности правлений и получает последовательность чисел a = (a1, a2, ... , an), где ai, -- длительность правления правителя с номером i. Эту последовательность чисел (вектор a О Rn) назовем числовой династией (ч. династией). Другой автор, описывая эту же р. династию, получит, возможно, другой вектор b О Rn. Итак, одна и та же р. династия может изображаться разными ч. династиями.

Пусть D={p = (p1, p2, ... , pn)} -- достаточно большое множество р. династий длины n. Модель (гипотеза): если две ч. династии близки (в смысле меры l), то они изображают одну и ту же р. династию, являются двумя вариантами ее описания (такие ч. династии назовем зависимыми); если же две ч. династии изображают две различные р. династии, то ч. династии значительно отличаются друг от друга (тогда назовем их независимыми). Перед проверкой модели дадим точное определение l, отождествив множество всех ч. династий, описывающих р. династии из множества D М Rn, с множеством V(D).

4. Укажем ошибки, чаще всего приводившие к разногласиям в определении длительностей правлений: а) перестановка (путаница) двух соседних правителей, б) замена двух, правителей одним, длительность правления которого равна сумме длительностей их правлений, в) неточность в вычислении длительности правления: чем она больше, тем больше и ошибка в ее вычислении. Эти три основных типа ошибок можно описать при помощи подходящего отображения V: D->Rn. Пусть p О D; вектор с назовем виртуальной вариацией вектора p, c=v(p), если каждая координата c, вектора с совпадает либо с одной из следующих трех координат вектора p: pi-1 , pi , pi+1 , либо с числом pi+pi+1. Ясно, что каждый вектор c=v(p) можно рассматривать как ч. династию, получившуюся из р. династии p в результате первых двух типов ошибок: а) и б).

Положим V(D) -- объединение всех векторов c=v(p), где p О D. Осталось смоделировать ошибку типа в). Пусть на положительной полуоси t >= 0 задана кусочно-гладкая функция a(t)>= 0 (у нас роль a(t) будет играть плотность вероятностей случайной величины h см. ниже). Положим H(a(t))=h(t), где H(s) -- монотонно убывающая функция на полуоси s >= 0,  lims0H(s) = + oo , например, H(s) = 1/s.Если h - дискретная случайная величина, то h(t) тем больше, чем с меньшей вероятностью h принимает значение t. Пусть t я длительность правления, a(t) -- число правителей, правивших t лет. В [1], стр. 115, приведена вычисленная автором экспериментальная гистограмма частот. Если t -- значение, принимаемое h с большой вероятностью, то амплитуда ошибок h уменьшается (небольшие длительности правлений лучше поддавались вычислению, чем редкие -- большие длительности) . Укажем функцию h(t) для плотности вероятностей случайной величины -- длительности правления ([1], стр. 115). Разобьем отрезок (0, 100) целочисленной оси t на отрезки (10t, 10t + 9), 0 <=t <=9. Тогда h(t) = 2 при t = 0, 1; h(t) = 3 при t = 2; h(t) = 5 (t-1) при 3 <=t <=9. Рассмотрим в Rn параллелепипед П(a,b)=П, ортогональные проекции
pi=ai( | ai-bi | )+h(ai)) которого на координатные оси в Rn задаются отрезками со следующими концами:
pi=ai+-( | ai-bi | )+2),        0<=ai<20
pi=ai+-( | ai-bi | )+3),        20<=ai<30
pi=ai+-( | ai-bi | )+5( [ai /10] - 1 ),        30<=ai<100

здесь [y] -- целая часть числа y. Итак, если 0<=ai<20, то значения ai и bi рассматриваются с точностью до 1 (т.е. такова ошибка, допускаемая при их измерении), если 20<=ai<30, то допустимая ошибка равна 3/2 и т.д. Оcталось смоделировать то, что факт принадлежности точки cО V(D) к параллелепипеду П можно рассматривать лишь приближенно. Для этого нужно сделать границу П  "более размытой", приближенной. Пусть r -- фиксированное число. Рассмотрим реальный вектор pО D, для которого по крайней мере r его координат p попали в проекции pi , параллелепипеда П и некоторая виртуальная вариация которого c=v(p) целиком попала в P. Такие векторы pО D и назовем r-близкими к P. Окончательно определим окрестность Hr(a,b), взяв объединение П и всех виртуальных вариаций векторов pО D, r-близких к П. В качестве l(a,b) возьмем отношение числа векторов множества V(D), попавших в окрестность Hr(a,b) (при этом не засчитываются виртуальные вариации самих векторов a и b, отличные от a и b) к числу векторов в V(D). Это число l имеет вероятностную интерпретацию. В самом деле, построим по множеству V(D) функцию j плотности вероятностей. Разобьем Rn на стандартные кубы достаточно малого размера так, чтобы ни одна точка из V(D) не попала на границу какого-либо куба. Если xО Rn - внутренняя точка куба, то положим j(х) = (число точек множества V(D), попавших в куб)/(число точек в V(D)); если х на границе куба, то j(х) = 0. Ясно, что l(a,b) является интегралом от функции j по множеству Hr(a,b) при условии, что Hr, состоит из кубов нашего разбиения. Поскольку мы моделируем приближенные вычисления, то можно считать это условие выполненным. Число  l(a,b) можно рассматривать как вероятность того, что случайный вектор, распределенный в Rn с функцией плотности j, попал в окрестность Hr с центром в a и "радиуса" | a-b|+h(a).

5. Для проверки модели п.3 были использованы хронологические таблицы Ж.Блера [2] и Гинцеля [3], содержащие все сохранившиеся данные о реальных исторических династиях. Мною был составлен полный список всех династий длины n = 15 из истории Европы, Средиземноморья, Ближнего Востока, Египта от 4000 г. до н.э. до 1800 г. н.э. Эти данные были дополнены сведениями из 14 других хронологических таблиц. В получившемся списке D некоторые р. династии представлены несколькими ч. династиями. Укажем основные династии, вошедшие в список D:
епископы и папы в Риме, сарацины, первосвященники в Иудее, грекобактрийцы, экзархи в Равенне, все династии Египта, Византии, Римской империи, Испании, России, Франции, Италии, Оттоманской империи, Шотландии, Лакедемона, Германии, Швеции, Дании, Израиля, Вавилона, Сирии, Сициона, Иудеи, Португалии, Парфии, Боспорского царства, Македонии, Польши, Англии. Число векторов в V(D) М R15 равно примерно 15*1011. Если для какой-то пары a, bО V(D)   число l(a,b) мало, то наблюдаемая близость династий a и b -- редкое событие, тем более редкое, чем меньше l. В качестве r бралось 1 +  2/3 n =11 по правилу "двух третей". Затем был проведен обширный вычислительный эксперимент по определению l(a,b). Результаты полностью подтвердили модель п. 3: для зависимых ч. династий a, b число l колеблется от 10-12 до 10-8, а если a и b независимы, то l не меньше 10-3. Налицо резкое различие (на 5 порядков) между зависимыми и независимыми династиями. Это, очевидно, позволяет решать задачу распознавания ч. династии.

6. Эксперимент обнаружил несколько особых пар a, b (всего несколько десятков из 106 обработанных пар), считавшихся ранее независимыми, но для которых l(a,b) таково, как и для зависимых пар.

Примеры.
1) Римская империя от 82 г. до н.э. до 217 г.н.э. и Римская империя 270-526 гг. н.э.,  l=1.3*10-12
2) Римско-Германская империя 962-1254 гг. н.э. и империя Габсбургов 1273-1619 гг. н.э., l=1.2*10-12
3) Две Римские империи 270-553 гг. н.э. и 962-1254 гг. н.э., l=2.3*10-10.
4) Империя Карла Великого (681 -- 887 гг. н.э.) и Восточная Римская империя 333 -- 527 гг. н.э., l=8.25*10-9.

7. Все эти результаты были проанализированы так: автором была построена глобальная "карта" (ГК) всех династий, описанных выше (см. [2, 3]). Для этого на плоскости, вдоль горизонтальной оси времени были отложены (в виде отрезков) периоды правлений всех правителей и даты всех основных событий на интервале 4000 г. до н.э. -- 1800 г. н.э. Дата события определяется проекцией точки (отрезка), изображающей это событие, на ось времени. Соправители и одновременные события изображались друг над другом в развертке по вертикали. (Эта "карта" ГК является "полным учебником" по древней и средневековой истории всех перечисленных выше государств и регионов.) К ГК была применена методика обнаружения дубликатов: на ГК были отмечены все пары династий (и соответствующих им эпох) a,b, для которых l(a,b) мало: имеет порядок от 10-12 до 10-8 (т.е. дубликаты). В силу подтвержденной модели п. 3 малость l указывает на зависимость династий (эпох). Опишем часть Е "карты" ГК на интервале от 1600 г. до н.э. до 1800 г. н.э., регион: Греция, Италия, Германия. Результат дадим в виде строки Е, в которой династии (эпохи) обозначены буквами, причем одинаковыми буквами отмечены дубликаты. Ввиду огромного объема материала приводим только грубую схему (часть ее см. в [1]). Буквы, помещенные в числителе и знаменателе дроби, указывают одновременные эпохи. Итак,

Здесь Е = C1+ С2+ С3+ С4, C1 = С0 + С'. Итак, все 4 строки C1, С2, С3, С4 практически одинаковы и для получения всей длинной строки-учебника Е достаточно склеить их друг с другом (по вертикали). Строка С2 приклеивается к строке С1 со сдвигом на 333 года, С3  -- к С1+ С2 со сдвигом на 1053 года, C4 к C1+ С2+ С3 со сдвигом на 1778 лет. Все эти результаты полностью согласуются с хронологическими выводами, полученными в [4].

Итак, строка Е - важнейшая часть ГК -- склеена из четырех практически одинаковых кусков и полностью восстанавливается по некоторой своей часта С0, целиком расположенной правее 300 г. н.э. Более того, основная масса информации в С0 осредоточена на интервале 960-1700 гг. н.э.

В "карте" ГК имеются и другие куски, содержащие дубликаты. Пример:
строка Б, построенная для интервала 4000-586 гг. до н.э. по таблицам 1-7 в [2], а именно: по столбцам 1, 2 для таблиц 1, 2, 3 в (2); по столбцам 1, 2, 3 для таблицы 4; по столбцам 1, 2 для таблицы 5; по столбцу 1 для таблицы 6; по столбцу 3 для таблицы 7. События, составляющие эту строку Б (и описанные в Old Testament, кн. Gen., Ex., Lev., Numb., Deuter., Josh., Jud., Ruth, 1-2 Sam., 1-2 Kings, Ez., Neh., Esth.), традиционно относятся к другим регионам (Ближний Восток), чем события, составляющие строку Е. Применение методики распознавания дубликатов (и методик, описанных в [1], дает:

Здесь блок Са является частью блока С. Мы не случайно использовали те же символы, что и при описании строки Е. оказывается, строка Б совпадает с частью строки Е. А именно:

Длина строки Б, измеренная в годах, равна 2300. Итак, полный "учебник" ГК содержит не только укорачивающиеся строки (вида Е и Б), но и изоморфные друг другу (совпадающие) строки значительной длины, традиционно рассматривающиеся как различные эпохи. Общий результат: вся "карта" ГК (а не только строки Б и Е) полностью восстанавливается по своей меньшей части С0, расположенной правее 300 г. н.э., причем основная масса событий расположена правее 960 г. н.э. В частности, строка Б практически целиком восстанавливается по части, расположенной на интервале 960-1400 гг. н.э.
 

Московский государственный университет им. М.В. Ломоносова

Поступило
5 II 1981

 

 

ЛИТЕРАТУРА
1 А Л. Фоменко, Некоторые статистические закономерности распределения плотности информации в текстах со шкалой. Семиотика и информатика, в. 15, М., 1980, стр. 99.
2 Ж. Блер, Хронологические таблицы (Brit. Roy. Soc.), М., т. 1-2,1808.
3 F.K. Gimel, Handb. der Mathematischen und Technischen Chronologie, v. I-III, Leipzig, 1906, 1914.
4А.Т.Фоменко, В сб.: Проблемы механики управляемого движения. Иерархические системы, Межвузовск. сб., научн, тр., 1980, стр. 161
.