В настоящее время не используются адекватные математические средства для анализа порядка следования событий в цепях конечной длины. Поэтому затруднены или невозможны измерение и сравнение формы сигналов, композиции музыкальных текстов, порядка элементов в длинных молекулярных цепях, взаимного расположения элементов в массивах данных, представляющих цепи событий разной природы. Объектом исследования в данной работе являются знаковые последовательности. Cформулированы выражения для числовых характеристик, которые описывают оригинальный порядок элементов цепи.
The formalization of the analysis building of symbolic chains.pdf Для исследования текстов и знаковых цепей разработано и используется мно-жество специальных подходов, процедур и моделей, среди которых можно отме-тить спектральный, корреляционный, фрактальный, статистический подходы,марковские цепи, потоки заявок. Однако почти не уделяется внимания законо-мерностям «конкретного расположения всех знаков или слов, составляющих от-дельную символьную последовательность». На наш взгляд, такое положение, внекоторой степени, объясняется отсутствием формализма для выделенного абст-рактного объекта и названного «строем или построением цепи» [1, 2]. Следуетотметить, что разные по природе последовательности событий с равномощнымсоставом могут иметь один и тот же оригинальный строй. С другой стороны, оче-видно, что мультимножество событий некоторой мощности, может быть основойдля построения последовательностей, имеющих разный строй. В данной работерассматривается подход, который предназначен для формального анализа по-строения отдельного текста, знаковой последовательности или цепи сообщений.Подчеркнем, что здесь не рассматриваются методы исследования локальнойструктуры символьных последовательностей.1. Формализация строя цепиРассмотрим множество знаковых последовательностей конечной длины. Вы-делим подмножество кортежей с одинаковыми наборами чисел вхождения симво-лов собственных алфавитов. Так как имеется в виду неоднократное вхождениенекоторых компонентов, то все множество кортежей, составленных на основеконкретного алфавита, - это комбинации типа «перестановки с повторениями»,каждая из которых отличается оригинальным взаимным расположением компо-нентов, собственной их композицией или построением.Кортеж, в котором знаки заменены натуральными числами, как это показанона рис. 1, назовем порядком следования элементов, построением или строем цепи[1, 2]. В результате таких замен все равномощные по составу знаковые последова-тельности, имеющие одинаковое взаимное расположение компонентов (компози-цию), будут отображены одной и той же последовательностью натуральных чи-сел, которая представляет оригинальный для данного подмножества текстов стройцепи (порядок следования элементов).Q R D & V Y S S & S D D S Q S D &W T C G H U R R G R C C R W R C GT Y M H T O S S H S M M S T S M HU I L J W O Y Y J Y L L Y U Y L JV N A B J K T T B T A A T V T A Bзнаковыепоследо-вательно-сти1 2 3 4 5 6 7 7 4 7 3 3 7 1 7 3 4 строй цепиРис. 1. Примеры знаковых последовательностей, имеющих одинаковый строй цепиСтрой цепи событий (сообщений, знаков и т.д.) определен как кортеж (упорядо-ченное множество), в котором каждому компоненту данной цепи поставлено в со-ответствие натуральное число, причем идентичные по выбранному признаку ком-поненты отображены одним и тем же числом. Самый первый компонент такогокортежа - единица, а все остальные первые встречные разные натуральные числа(представляющие вместе с единицей алфавит строя) возрастают на единицу.В соответствии с теоретико-множественным определением вектора назовемтакой специфически сформированный (организованный) кортеж «вектор строя».Разложим полную неоднородную символьную последовательность (без сво-бодных мест на ее позиции) на m неполных «однородных» кортежей, в которыхзаняты только некоторые места данной позиции одинаковыми знаками. Аналогомоднородной последовательности является однородный поток событий, рассмат-риваемый в теории массового обслуживания. Вообще разложение цепи можетосуществляться по разным правилам. Так на рис. 2 представлена декомпозициястроя неоднородной знаковой цепи на неполные однородные. Разложение на не-полные «разнородные» цепи, когда отдельные места данной позиции занятытолько разными знаками, осуществляется по следующему правилу: при просмотрецепи от ее начала в состав первой разнородной цепи выбираются все первые вхо-ждения каждого знака из алфавита, при втором - все вторые вхождения и т.д..В случае правильно выполненных декомпозиций полученные множества од-нородных (разнородных) последовательностей будут несовместными (т.е. не со-держат занятых мест с одинаковыми номерами на позиции). Композиция всех не-полных однородных (разнородных) кортежей дает исходную полную неоднород-ную знаковую последовательность.Определим «интервал» как расстояние от выделенного в цепи компонента додругого, ближайшего, отмеченного в направлении просмотра (рис. 2); по другому- это модуль разности номеров мест двух выделенных компонентов на позициикортежа.Пусть первое считывание текста осуществляется отличным от обычного (чте-ние подряд) способом с самого начала до конца таким образом, что выбираютсятолько элементы строя с номером «1»; при этом последний интервал определяетсядо знака «финиш» (возможен и другой вариант - определение первого интервалаот начала текста - «старта»). Интервалы данной однородной последовательностиразместим в соответствии с номерами считываемых элементов в первой строкематрицы. Далее, при втором просмотре строя текста, аналогично выберем элемен-ты с номером «2» и разместим вектор интервалов, соответствующий другой одно-родной последовательности, во второй строке матрицы. В каждой следующейстроке помещается вектор интервалов «новой» при очередном просмотре одно-родной последовательности. Одиночные знаки, слова или сообщения будут пред-ставлены всего одним интервалом (до финиша), который размещается в крайнемстолбце соответствующей строки матрицы. Число столбцов nj max в «матрице ин-тервалов» однородных цепей равно числу вхождений самого частого знака (илислова) текста. Незанятые интервалами элементы матрицы заполним нулями. Чис-ло строк m равно мощности собственного алфавита или словаря текста.V N A B J K T T B T A A T V T A B знаковая цепь1 2 3 4 5 6 7 7 4 7 3 3 7 1 7 3 4 строй цепи1 123 33 34 4 4567 7 7 7 7однородные цепи исоответствующие имцепи интервалов0 0 0 13 40 0 080 160 8 1 4 2010 0 0 0 130 0 5матрицаинтервалов121 2 3 2 30 0 0Рис. 2. Декомпозиция строя неоднородной знаковой цепи на неполные однородныеПусть считывание текста осуществляется вторым (вышеописанным) способомпо разнородным цепям. В результате получим матрицу интервалов разнородныхцепей, в которой число столбцов равно m, а число строк - nj max.2. Числовые характеристики строя цепиИспользуем понятие однородной знаковой последовательности и ее векторноеотображение в виде соответствующей строки матрицы интервалов для определе-ния некоторых числовых характеристик строения текста, которые для компактно-сти представлены в табл. 1 [3].В таблице обозначены: j - номер знака в алфавите или номер однородной це-пи; ij - интервал между i-м и (i+1)-м вхождениями знака j в однородной цепи;logij - удаленность (i+1)-го вхождения знака j относительно его i-го вхождения;nj - число вхождения знака j в цепи; m - мощность алфавита знаков цепи; n -длина полной знаковой цепи, равная числу всех ее позиций; aj, gj - соответст-венно средний арифметический и средний геометрический интервалы строя j-йоднородной цепи; Vj - абсолютный объем строя j-й однородной цепи; Gj - глубинарасположения строя j-й однородной цепи; gj = loggj - средняя удаленность знака jв строе однородной цепи; V - абсолютный объем строя на основе однородных це-пей; G - глубина расположения строя на основе однородных цепей; g - среднийгеометрический интервал строя на основе однородных цепей; g - средняя удален-ность любого элемента строя на основе однородных цепей; D - число описатель-ных информаций, используемых (по Мазуру [4]) для определения некоторого зна-ка цепи; I - число идентифицирующих информаций, используемых (по Мазуру)для дихотомического распознавания отдельного знака; j - периодичность (следо-вания знаков) строя j-й однородной цепи; r - регулярность (следования любогоэлемента) строя на основе однородных цепей.Т а б л и ц а 1Числовые характеристики строя на основе однородных цепей(1)1n jj ijiV== (2) njgj= Vj (3) 21logn jj ijiG== (4)1mjjV V== (5) ng = V (6)1mjjG G== (7) 1ajj jnn P = = (8) gjjaj = (9) r g 1D= ≤(10)1m njng gjj= = (11)1logmjgjjng= n= (12) g =logg(13)1m njnajjD== (14)1logmjajjnI= n= (15)1logmj jjH P P== −Множества величин {Gj} и {gj} являются соответственно распределением глу-бин и распределением средних удаленностей всех однородных последовательно-стей для строя отдельной цепи. При анализе и описании строя данной цепи рас-пределение средних удаленностей дополняет обычное частотное распределениезнаков {nj} комплексным распределением строя вида {}.Легко определяются аналогичные по форме, но отличные по содержанию, чи-словые характеристики строя данной цепи, с использованием векторов интерва-лов, представленных строками матрицы для разнородных цепей. В таком случаеформулы (1) - (15) определяются при выделении знаков j в i-х разнородных цепях ипредставляют числовые характеристики строя на основе разнородных цепей.3. Числовые характеристики для «предельных» моделей строя цепиДля «регулярной» знаковой цепи, в которой все интервалы каждой однород-ной цепи равны ij = aj = n/nj, числовые характеристики строя цепи (10) и (11)принимают максимальные значения (см. (16), (17)) и записываются формуламиМазура (13) и (14), представляющими соответственно числа описательных иидентифицирующих информаций в цепи сообщений.g = g max = D; (16)g = gmax = I; (17)D > g; (18)H > g = logg. (19)Для бесконечной знаковой цепи (n) формула Мазура (14), в которойaj = (n/nj) (1/Pj), принимает вид формулы К.Шеннона (15) для энтропии иликоличества информации. Такая информация используется только для дихотоми-ческой идентификации (но не для описания) отдельных сообщений. Для текстов идругих нерегулярных последовательностей формулы Мазура и Шеннона даютоценку строя только «сверху», так как в этих случаях имеют место неравенства(18) и (19). Соответственно числовые характеристики строя на основе однород-ных цепей принимают минимальные значения для «сплошных» последовательно-стей, в которых все одинаковые элементы расположены подряд.Таким образом, формулы для среднего геометрического интервала и среднейудаленности знаковой цепи обобщают формулы Мазура и Шеннона, так как, в от-личие от последних, при описании строя данной цепи учитывают не только мощ-ность состава, но и взаимное расположение ее компонентов (знаков, слов).Полагаем важным отметить взаимосвязь характеристик строя цепи, получен-ных на основе однородных и разнородных цепей. Так, для рассмотренных вышемоделей регулярной и сплошной последовательностей, характеристики строя наоснове разнородных цепей принимают соответственно минимальное и макси-мальное значения.4. Числовые характеристики строя текстадля литературных произведенийПроиллюстрируем чувствительность описанных выше характеристик к изме-нению взаимного расположения элементов последовательности на примере лите-ратурных текстов.В табл. 2 представлены результаты обработки строя произведения А.С. Пуш-кина «Капитанская дочка» и его трех модификаций в виде энтропийных характе-ристик и числовых характеристик строя текста. Проведенные эксперименты пока-зали, что даже малые изменения строя текста (модификация 2) приводят к изме-нениям значений числовых характеристик строя: для глубины G во втором знакепосле запятой, для удаленности g и регулярности r - в шестом. Отметим, что дан-ные характеристики позволяют только определять факт изменения взаимногорасположения знаков в цепи, без его локализации.При автоматической сегментации текстов в качестве элементарных единиц ис-пользовались слова, нормированные путем отбрасывания окончания. Критериемкачества сегментации являлась степень совпадение мощностей составов, полу-ченных автоматически и вручную в работах Ю.К. Орлова [5].Т а б л и ц а 2Энтропийные и числовые характеристики строяповести А.С. Пушкина «Капитанская дочка»n m Hs G H g r1 29312 4789 290585.01 253104.07 9.913517 8.634847 0.4122072 29312 4789 290585.01 253104.03 9.913517 8.634845 0.4122063 29312 4789 290585.01 263790.75 9.913517 8.999375 0.5307154 29312 4789 290585.01 63944.14 9.913517 2.181500 0.004704В таблице обозначены: Нs - количество информации в тексте; вычисляется впредположении статистической независимости слов путем перемножения H и n;1 - строй оригинального текста; 2 - модификация строя с небольшими измене-ниями (переставлены два смежных слова); 3 - модификация строя с большимиизменениями (со случайными перестановками всех слов); 4 - модификация строясо словами, упорядоченными по алфавиту.Так же было проведено исследование 56 литературных произведений, представ-ляющих три направления: русская художественная классика (Пушкин (6), Тургенев(6), Гоголь (7)), фантастика (Фармер (6), Муркок (5), Желязны (6)) и философскиетексты (Ницше (6), Шопенгауэр (5), Фрейд (9)). В табл. 3, приведены числовые ха-рактеристики строя текстов трех авторов, представляющих разные направления.Тексты упорядочены по возрастанию значений средней удаленности.Первые исследования небольшой выборки текстов разных авторов и направле-ний показали, что каждый текст характеризуется уникальным значением рассмот-ренных числовых характеристик, которые представляют только взаимное располо-жение слов без учета их морфологии. Исследованные литературные произведения,упорядоченные по величине g или r, группируются в различимые таксоны.Т а б л и ц а 3Характеристики строя исследованных текстов№ Автор Произведение m n G g r1 Шопенгауэр О политике 1818 8363 65655,1 7,851 0,3852 Шопенгауэр О жизни 1712 5740 45541,4 7,934 0,4103 Шопенгауэр О смерти 2824 17853 144301,9 8,083 0,4294 Шопенгауэр О философии 1711 5495 44611,8 8,119 0,4365 Тургенев Муму 2363 8510 69871,3 8,211 0,4156 Тургенев Ася 2953 13835 115179,9 8,325 0,4477 Тургенев Рудин 5019 35498 300182,9 8,456 0,4038 Фармер Несколько слов 3040 11288 95830,8 8,490 0,4169 Тургенев Вешние воды 6020 38718 338561,2 8,744 0,40310 Тургенев Дворянское гнездо 6480 46795 409538,6 8,752 0,41111 Тургенев uc2Отцы и детиОбозначим: (l/j)i - интервал между i-ми ближайшими справа знаками l по от-ношению к знакам j; n(l/j) - число пар знаков j и l, связанных интервалами (l/j)i.На диаграмме: (l/j)1 = (l/j)3 = 1; (l/j)2 = 2; (l/j)4 = 3. Определим среднее гео-метрическое значение (l/j)g всех n(l/j) установленных интервалов (бинарной це-пи) (l/j)i между «смежными» элементами двух однородных цепей.Полная неоднородная цепьj-я однородная цепьl-я однородная цепьБинарно-однородная цепьРис. 3. Диаграммы цепейИнтервалы только между теми знаками выделенной однородной цепи l, кото-рые являются «ближайшими справа» относительно знаков цепи j, обозначены(lj)i. В примере: (lj)1 = 9; (lj)2 = 2; (lj)3 = 4; (lj)4 = 1.Определим среднее геометрическое значение (lj)g интервалов (lj)i междувыделенными элементами lj в данной однородной цепи. При условии (lj)g >(l/j)g, разность (lj) = 1 - (l/j)g / (lj)g представляет «избыточность» l-й цепи, за-висимой от j-й. Некоторые элементы такой цепи «связаны справа» с элементамиj-й цепи. В противном случае, при (lj)g ≤ (l/j)g, данная разность свидетельствуетоб отсутствии избыточности.С учётом избыточности (lj) и величины n(l/j)/nl введен коэффициент частич-ной зависимости K1(l/j) l-й однородной цепи (от j-й цепи). Отметим, что отноше-ние n(l/j)/nl представляет собой условную вероятность события, состоящего в по-явления пары знаков l и j, связанных причинной зависимостью, от появления зна-ков цепи l. Если все элементы l-й цепи связаны интервалами (l/j)i с элементамиj-й однородной цепи n(l/j) = nl, то оценка частичной зависимости становитсяоценкой полной зависимости и определяется равенством K1(l/j) = (lj). Если, кро-ме отмеченного, числа выделенных элементов сравниваемых однородных цепяхравны nl = nj, то такие цепи считаются полностью взаимозависимыми. Причиннаязависимость названа установленной, определенной или закономерной, если раз-меры всех интервалов (l/j)i бинарной цепи задаются определенным операцион-ным преобразованием. В противном случае отмечается неопределенная причин-ная зависимость. Частный случай определенной зависимости назван фиксирован-ной причинной зависимостью. При этом «следование за» в бинарной цепи пред-ставлено равными интервалами (l/j)i = (l/j)g = const, i = 1,2,…, n(l/j). Предель-ный случай определенной зависимости назван непосредственной причинной зави-симостью; при этом бинарная цепь задается единичными интервалами (l/j)i = 1,i = 1,2,…, n(l/j).Также определена степень зависимости K2(l/j) одной цепи от другой, с учетомвеличины 2n(l/j)/(nj + nl), характеризующей «полноту её участия» в составе обеиходнородных цепей.Если не требуется учитывать индивидуальную зависимость l-й цепи от j-й, товычисляется (средний геометрический) коэффициент взаимной зависимости K3(j,l).Наличие «сильной» причинной зависимости может быть использовано для«сжатия» информации при описании взаимного расположения элементов массиваданных.В табл. 4 представлена причинная зависимость К1 однородных последователь-ностей некоторых слов, рассматриваемых в составе повести «Пиковая дама»А.С. Пушкина. Полная матрица причинной зависимости слов имеет большойразмер, поэтому были выбраны только некоторые пары, по признаку относитель-но большого значения коэффициента.Для каждой пары однородных цепей j и l в таблицах приведены отношениеn(l/j)/nl, избыточность v(lj) и определяемый ими коэффициент частичной зависи-мости K1.Т а б л и ц а 4Значения коэффициента причинной зависимости (К1) для некоторых пар слов изтекста повести А.С. Пушкина «Пиковая дама» (в первом столбце слова-причины)n(l/j)nlv(lj) K1 n(l/j)nlv(lj) K1 n(l/j)nlv(lj) K1 n(l/j)nlv(lj) K1Выигрыш Долг Игроки Деньгикарты 0,900 0,957 0,862 0,858 0,820 0,703 1,000 0,681 0,681 0,243 0,837 0,204Вечер Дом Года Деньвремя 0,750 0,854 0,640 0,800 0,849 0,679 0,715 0,841 0,601 0,750 0,797 0,598Игроки Лица Люди Долггости 0,625 0,847 0,530 0,556 0,923 0,513 0,715 0,628 0,449 0,715 0,644 0,460Люди Ужас Смотрит Словостаруха 1,000 0,903 0,903 0,910 0,906 0,824 0,875 0,932 0,816 0,924 0,876 0,809Как видно из представленных данных, коэффициент пространственной зави-симости можно использовать для определения контекстуальной емкости понятий,придаваемой им автором соответствующего произведения.6. Числовые характеристики строя для нуклеотидных цепейОписанные выше формализмы апробированы при компьютерном исследова-нии рибосомальных РНК 18 организмов, представляющих два царства жизни -прокариота и эукариота [8]. Характеристика g полного неоднородного строя от-дельной РНК вычислялась на основе четырех его характеристик однородных це-пей: гуанина G, цитазина C , тимина T, аденина A.Названия исследуемых организмов (упорядоченных по возрастанию величинысредней удаленности g) получили следующие номера: 1 - mus musculusdomesticus, 2 - caiman crocodylus, 3 - canis familiaris, 4 - gallus gallus, 5 - amiacalva, 6 - homo sapiens (человек), 7 - thermotoga thermarum, 8 - thermus thermophilus,9 - ixodes persulcatus, 10 - ornithodorus moubata, 11 - pediculus humanus capitis,12 - musca domestica, 13 - streptococcus pyogenes, 14 - bacillus anthracis, 15 - borreliaburgdorferi B31, 16 - candidatus nitros. maritimus, 17 - mycoplasma pneumoniae,18 - neisseria gonorrhoeae.На числовой оси (рис. 4) организмы расположены в соответствии со значения-ми их характеристики g - средней удаленности элементов в нуклеотидной цепи.Как видно, эукариоты (позвоночные) образовали группу организмов (слева наоси), имеющих наименьшие значения средней удаленности. Прокариоты (бакте-рии) образовали группу организмов (справа на оси), имеющих наибольшие значе-ния средней удаленности. Эукариоты (беспозвоночные) расположены между эти-ми крайними на оси группами, примыкая к бактериям. Факт выделения из группыпрокариот (по характеристике g) двух бактерий (7 и 8), значительно отличающих-ся условиями существования от других, исследуемых в данной работе, требуетпроведения дальнейших исследований.11,42 1,44 1,48 1,49 1,50 1,53 g3 5 7 9 11 13 15 172 4 6 8 1 0 12 14 16 18позвоночные беспозвоночные бактерии и археиРис. 4. Расположение номеров организмов на оси средней удалённости нуклеотидовЗаключениеВ работе представлен инструментарий для описания и анализа нового абст-рактного объекта, названного строем цепи событий. Вычисленные значения ха-рактеристик строя однозначно отображают оригинальные построения выбранныхнуклеотидных цепей и литературных текстов. Это дает основания для проведенияисследований больших множеств знаковых последовательней разной природы спомощью средств анализа строя цепи.
Гуменюк А.С., Шпынов С.Н., Морозенко Е.В., Родионов И.Н. Пример применения средств анализа для сравнения строя нуклеотидных последовательностей и кластеризации организмов // Нейроинформатика, ее приложения и анализ данных: Материалы XVI Всероссийского семинара / под ред. А.Н. Горбаня, Е.М. Миркеса. Красноярск: ИВМ СО РАН, 2008. С. 166−170.
Гуменюк А.С., Морозенко Е.В. О характеристике зависимости однородных цепей в составе нуклеотидной последовательности / Нейроинформатика, её приложения и анализ данных: Материалы XVII Всероссийского семинара, 2 - 4 октября 2009 г. / под ред. А.Н. Горбаня, Е.М. Миркеса. Красноярск: ИВМ СО РАН, 2009. С. 53−56.
Гуменюк А.С. О средствах анализа взаимного расположения компонентов знаковой последовательности. // Материалы III Международного технологического конгресса. Омск: ОмГТУ, 2005. Ч. II. С. 48−52.
Мазур М. Качественная теория информации. М.: Мир, 1974. 249 с.
Орлов Ю.К. Частотные структуры конечных сообщений в некоторых естественных информационных системах: дис. ... канд. наук. Тбилиси: Изд-во Тбилисского университета, 1974.
Гуменюк А.С., Богорад Д.М. Об исчислении взаимного расположения элементов в массивах данных // Труды РНТОРЭС им. Попова, серия: научная сессия, посвященная Дню радио. 2004. Вып. LIX. № 2. С. 114−116.
Gumenyuk A., Kostyshin A., Simonova S. An approach to the research of the structure of linguistic and musical texts // Glottometrics. 3 (2002). Liideschtid RAM Verl. S. 61−89.
Гуменюк А.С. О формализме «строение знаковой последовательности» и его использовании для анализа, сравнения, преобразования и распознавания лингвистических текстов // Четвертый сибирский конгресс по прикладной и индустриальной математике: Тез.докл. Новосибирск: Изд-во Института математики СО РАН, 2000. Ч. 3. С. 84−85.
Вы можете добавить статью