Содержание к диссертации
Введение
1 Введение 4
1.1 Реконструкция по подсловам 4
1.2 Различимость слов 14
2 Реконструкция по подсловам 17
2.1 Подслова, окрестности, классы эквивалентности 17
2.2 Описания классов эквивалентности в терминах логического перманента 20
2.2.1 Классы эквивалентности Wk(x)
2.2.2 Классы эквивалентности W 2.3 Серийное описание классов эквивалентности 29 2.3.1 Характеризация 2-эквивалентности 30 2.4 Восстановление слова по подсловам длины > [|] + 1 . 39 3 Различимость слов 48 3.1 Различающие слова, тестовые множество, тесты 48 3.2 Свойства и оценки функции t(x, у) 50 3.3 Алгоритм построения минимального теста 56 3.3.1 Простейший алгоритм 58 3.3.2 Префикс-функция, ассоциированная с образцом . 59 3.3.3 Алгоритм Кнута - Морриса - Пратта 61 3.3.4 Алгоритмы нахождения t(x, у) 62 Литература 65 Введение к работе 1.1 Реконструкция по подсловам Часть и целое всегда является предметом изучения науки. Основной философский вопрос при таком изучении звучит так: как устроен мир? Если при исследовании информацию принят следующий тезис: Всякая информация может быть представлена словом в конечном алфавите, то часть проблем, связанных с понятием информация может быть сформулировано в виде изучения слова и его частей. Что понимать под частью слова зависит от контекста изучаемой проблемы и точные постановки задач могут варьироваться в достаточно широких пределах? В целом такого роде задачи имеют глубокие связи с алгеброй, топологией, теорией чисел,теорией информации и математической генетикой. Основным объектом изучения в диссертации являются слова конечной длины над бинарным алфавитом {0,1}. Это множество обозначается через В*. ЕСЛИ X = Х\Хч Хп- СЛОВО ИЗ В*, ТО ЛЮбое СЛОВО ВИДа XfrXk+l ' ' * хк+г называется подсловом х. При этом 1 < к < п—т. Таким образом множество всех иодслов длины к слова х содержит не более чем (п — к + 1)— различных подслов и общее число подслов слова длины, с учётом их кратности, равно (П2 ). Каждое подслово а слова х несёт определённую информацию об этом слове. Как оценить или измерить эту информацию? Этот вопрос является одним из ключевых вопросов, рассматриваемых в этой диссертации. Интуитивно ясно, что чем длиннее подслова слова х, тем больше несут они информации об исходном слове. В каком случае слово можно однозначно восстановить по набору его подслов ограниченной длины и в каком случае это можно сделать лишь с определенной погрешностью? Все эти вопросы уже рассматривались в целом ряде исследований, относящихся к комбинаторике слов и на многие из них получены ответы той или иной степени полноты и определённости. Однако вопросы восстановимое и различимости формулировались в основном по отношению к фрагментам слова, а не к подсловам. Фрагмент- это более широкое понятие части слова, чем только подслова ограниченной длины. Однако подслово- это боли структурированная часть слова, чем фрагмент, что также привносит определённую специфику в проблему восстановимости и различимости по подсловам. Пусть В = {0,1}— двоичный алфавит и В*— множество всех слов конечной длины над алфавитом В. Если х = (хіХ2---хп) Є J3*, то длину слова х мы будем обозначать через |х|. Множество всех бинарных слов длины п и < п мы будем обозначать соответственно через Вп и В-п. Множество В* является моноидом с операцией конкатенации х,у Є В* -> ху Є В* Определение 1.1.1. Слово у = (у\У2 Ук) называется подсловом слова X = (Xl^2 -Хп), еСЛи Хі = Уъ &t+i = У2, , Xi+k-i — Ук для некоторого і из интервала [1, п — k + 1]. Слово у = {у\У2'"Ук) называется фрагментом слова х = {х\Х2 -хп), если существует такая последовательность 1 < і\ < ї2 < ' * < Ч < п, %h - Уі^І2 = у2,--- ,xik = yk Замечание. У части авторов исследований по комбинаторике слов используется несколько отличная терминология. Так в монографии[1] подслово (subword) в нашей терминологии- это фактор (factor), а фрагмент-это подслово. Мы будем придерживаться введённых выше обозначений, понимая всю условность преимуществ и недостатоков различных терминологий. На множестве В* введём частичный порядок (<) , положив х < у если х— является подсловом слова у. Пусть а є В* и 14(a)— мультимножество всех подслов длины к у слова а. Пример. Если є„ = (01)" = 1010 - 10 є Вп, то ^(ев) = {(1)»,(0)в} что означает что подслово "1" входит в єп — п— раз и подслово "О"- входит в е„ — п— раз. Аналогично V2(en) - {(10)",(Olf"1} в тех же терминах. При этом |Vi(e„)| = 2п, |^(еп)| — 2п — 1. По другому, если Вк = {ui, «2, ,V2k], то или при фиксированном упорядочении вершин Вк можно принять такое описание окрестности Vk(a): Vk(a) = (61,62,--- ,)* где Si > 0 и 2_\ 6i = п — к + 1 Аналогично определим окрестность порядка < & слове а Є Вп как следующее множество Определение 1.1.2. (7лоеа а, 6 -В" наз-ыеаютсл fc(< fc)— экеивалент-пими, если Vk(a) = Vk(b) или У<,(а) = V<k(b) Эти отношения к(< к) — эквивалентности являются обычными отношениями эквивалентности в чисто алгебраическом смысле и потому весь куб Вп может быть представлен в следующем виде B^{jWk(a) где Wjt(a)— это класс к— эквивалентности, определяемый словом а Є Вп. Аналогично Bn = {JW<k(a) В содержательном смысле класс Wk(a)— означает, что все его элементы "неотличимы" по окрестности порядка к от слова a Вп. Таким образом "точность" задания слова а с помощью окрестности порядка < к измеряется мощностью класса эквивалентности 1У<&(а). Далее в главе // предлагается алгоритм для построения классов эквивалентности Wk{a) и VK Таким образом с помощью операции < x,v > из слова х "вырезается" его подслово, соответствующее v или с координатами из множества v. Пусть теперь А < v, е > — множество всех решений уравнения < x,v >— е (1.2) Здесь v = («ії2 ik), є = (еіе2 є*) Є Вк, х — (х\Х2 хп) Є Вп. Таким образом A(v, є) — это множество двоичных слов длины п "проектирование" которых на оси [і\%2 ik) приводит к слову е. В терминах булевой алгебры это множество выглядит следующим образом. Лемма 1.1.1. Справедливо соотношение A(Vje) = xJX8---<* Другими словами A(v, е)— это (п — к) — мерный подкб, Вп или элементарная конъюнкция ранга к. По схеме (1.1) сформируем логическую матрицу А — |jj4y||. с?та матрица имеет размеры (п — к + 1) х (п ~ к + 1). Под логическим перманентом матрицы А мы будем понимать следующую Д.Н.Ф per А = У Al Здесь Sn-k+i— симметрическая группа порядка (п — к + 1). Теорема 1.1.1. Класс эквивалентности Wfc(a) описывается следующий формулой Wh(a) = per А Таким образом множество элементов класса эквивалентности Wk(a) совпадает с множеством единиц булевой функции Д.Н.Ф. которой есть регА. Далее в этой главе строится описание класса эквивалентности W В главе (2) строится "алгебраическое" описание классов эквивалентности Wk{a) для "малых" к = 1, 2,3 и приводится общая схема такого описания. Пусть х = {х\Х2 — хп) Є Вп, а = (с^с^ - ак) Є Вк и ta(x) — число вхождений слова а в слово х в качестве подслова. Другими словами -ta(x)-это кратность вхождения слова а в мультимножество V^x), определенное выше. і при а = 1 1 — Хі при а = О то справедливо следующее утверждение. Лемма 1.1.2. *.(*) = «f*Si-*n (1-3) Таким образом ta(x) — это полином от п— переменных степени к. Пример. Пусть а = (10). Тогда П—1 п—1 л—1 і—1 г=1 і—1 Ясно, ЧТО / л %i = 1\%\1 &n—1 Если a: = у"!^"^... у*- — серийное представление слова а;, то У^ ж^г+1 — (mi -1) + (тз — 1) Н + (тг — 1) при геі (mod 2) С помощью леммы 1.1.2 доказываются следующие утверждения. Теорема 1.1.2. Слова х и у из Вп являются 2~ эквивалентными тогда и только тогда, когда выполняются условия 1) S{x) = S(y) 2) INI - h\\ = ^і - уі = хп - Уп Теорема 1.1.2 позволяет провести проверку 2-эквивалентности слов из Вп за линейное по входу время, т.к. вычисление S{x) и \\х\\ может быть сделано с линейной сложностью от п. Отметим также, что в работе [4] предложен алгоритм установления 2-э к вивал ентн ости слов длины п над произвольным конечным алфавитам, имеющий сложность 0(п4). Из Теоремы 1.1.2 можно получить условия, при которых любое слово из Вп однозначно определяется своими под словам и длины 2. Теорема 1.1.3. Слово а Є Вп однозначно определяется своими подслова-ми длины 2 если и только если выполняются следующие условия: S(a) < 2 а = 77п^27 и п>4 а — 7777 ---77 и п = 0 (mod 2) (п > 2). Отметим также, что в работе [4] предложено "алгоритмическое" решение задачи о восстановимости, если это возможно, слова длины п по подсловам длины два в случае произвольного конечного алфавита. Сложность такого алгоритма 0(п4). Описание классов (< 2)— эквивалентности содержатся в теореме 1.1.4. Теорема 1.1.4. Слова х и у из Вп являются < 2 -эквивалентными если и только если выполняются следующие условия 1) S(x) ~ S{y) 3) xi = з/i, хп = уп (1.5) 2)И1 = 1Ы1 Так как имеет цепочка включений С W<k{a) С W Если а = 0П, то А„(а) — 1 Если а = 0*1ПЛ то Лп(а) = 2, т.к. У!(а) = Уі(а) V2(a) = {0fc, 1п~\ (00)fc"\ (01)1, (10), (її)"-*"1} По V^ip) слово а восстанавливается однозначно, т. к. структура V^fa) показывает, что у слова а равно 2 серии (если бы не так, то в V^fa) входили бы слова (01) и (10).) и слово начинается с нуля. Пусть An = maxAn(a) Теорема 1.1.5. Справедливо равенство А» = ] + ! Это теорема показывает, что задача о восстановлении слова длины п по "различным" фрагментам и задача восстановлении слова по всем под-словам (с учётом кратности) приводят к одной и той же величине длины "частей", необходимых для однозначной реконструкции. 1.2 Различимость слов В главе II рассматривается задаче "различимости" слова по подсловам без учёта их кратности. Пусть х,у Вп и Т(х,у)— множество всех слов, являющихся подсловами х, и не являющих подсловами у. Любое слово а Є Т(х, у) называется "различающим" хну. Любое слово из множества Т(х,у) = Т(х,у) U Т(у,х) называется тестовым для пары (ж, у) Є Вп х Вп. Задача состоит в нахождении или построении слова минимальной длины из множества Т(х,у). Любое такое слово называется минимальным тестом, а длина его обозначается через t(x, у). В содержательном смысле чем больше величина (ж, у) тем "труднее" различать слова х и у или, по другому, тем более они "похожи". Пример. Если а = (10)", а = (01)" то слова а и а неразличимы но подсловам длины < 2п — 1 и, таким образом, t(a, а) = 2п. Замечание. Если х = у, то t(x, у) = \х\. Рассмотрим следующую функцию, характеризующую меру различия слов ж, у Є Вп: d(xty) = n-t(x,y) Лемма 1.2.1. Функция d(x,y) является псевдометрикой на В71. Метрикой этой функции "мешает" быть то обстоятельство, что 4(Ю)п/2,(01)п/2) = 0 в то время как (10)71/2 ф (01)п'2. Функция t(x, у) имеет довольно сложную комбинаторную природу и потому поиски хороших аппроксимаций для неё весьма актуальны. Определение 1.2.1. Пусть х Є Вп. Величина 5(х) называется типом слова х, если в х в качестве подслова фигурируют все слове длины < 8(х) и нет хотя бы одного подслова длины 5(х) + 1. Лемма 1.2.2. Справедливы неравенства t(z,y)>mm{5(x),5(y)} + l 6(х) ^(y),t(x,y) < тах{5(х),%)} Для S(x) в свою очередь справедливы следующие границы 26Ы+5(х)<п + 1 и таким образом S(x) < lg(n + 1)- !і^±11 (1.7) Следующая "аппроксимация" использует серийное представление слов. Пусть х = j^m* 7m", У = 7п'7Па 7n% S\x) = {m2, m3, - , mr_i}, 51^) = {щ, тіз, , n5_i} и S^rc) Л51 (у)— симметрическая разность множеств S1(x) и Sl(y). Лемма 1.2.3. Если ре Si{x) A Sl(y), то выполняется неравенство t(x,y) Границы (1.7) и (1.8) наводят на мысль, что в "типичном" случае функция t(x,y) растёт не быстрее log2n. Определённым подтверждением этой гипотезы является следующие утверждение. Теорема 1.2.1. Для "почти всех" пар точек (х,у) Вп X Вп длина минимального теста не превосходит асимптотически log2n. В этой же главе предложен алгоритм для построения минимального теста t(x,y) для произвольных слов (х,у) Є Вп х Вп. Часть и целое всегда является предметом изучения науки. Основной философский вопрос при таком изучении звучит так: как устроен мир? Если при исследовании информацию принят следующий тезис: Всякая информация может быть представлена словом в конечном алфавите, то часть проблем, связанных с понятием информация может быть сформулировано в виде изучения слова и его частей. Что понимать под частью слова зависит от контекста изучаемой проблемы и точные постановки задач могут варьироваться в достаточно широких пределах? В целом такого роде задачи имеют глубокие связи с алгеброй, топологией, теорией чисел,теорией информации и математической генетикой. Основным объектом изучения в диссертации являются слова конечной длины над бинарным алфавитом {0,1}. Это множество обозначается через называется подсловом х. При этом 1 к п—т. Таким образом множество всех иодслов длины к слова х содержит не более чем (п — к + 1)— различных подслов и общее число подслов слова длины, с учётом их кратности, равно (П2 ). Каждое подслово а слова х несёт определённую информацию об этом слове. Как оценить или измерить эту информацию? Этот вопрос является одним из ключевых вопросов, рассматриваемых в этой диссертации. Интуитивно ясно, что чем длиннее подслова слова х, тем больше несут они информации об исходном слове. В каком случае слово можно однозначно восстановить по набору его подслов ограниченной длины и в каком случае это можно сделать лишь с определенной погрешностью? Все эти вопросы уже рассматривались в целом ряде исследований, относящихся к комбинаторике слов и на многие из них получены ответы той или иной степени полноты и определённости. Однако вопросы восстановимое и различимости формулировались в основном по отношению к фрагментам слова, а не к подсловам. Фрагмент- это более широкое понятие части слова, чем только подслова ограниченной длины. Однако подслово- это боли структурированная часть слова, чем фрагмент, что также привносит определённую специфику в проблему восстановимости и различимости по подсловам. Пусть В = {0,1}— двоичный алфавит и В — множество всех слов конечной длины над алфавитом В. Если х = (хіХ2---хп) Є J3 , то длину слова х мы будем обозначать через х. Множество всех бинарных слов длины п и п мы будем обозначать соответственно через Вп и В-п. Множество В является моноидом с операцией конкатенации для некоторого і из интервала [1, п — k + 1]. Слово у = {у\У2 "Ук) называется фрагментом слова х = {х\Х2 -хп), если существует такая последовательность Замечание. У части авторов исследований по комбинаторике слов используется несколько отличная терминология. Так в монографии[1] подслово (subword) в нашей терминологии- это фактор (factor), а фрагмент-это подслово. Мы будем придерживаться введённых выше обозначений, понимая всю условность преимуществ и недостатоков различных терминологий. На множестве В введём частичный порядок ( ) , положив если х— является подсловом слова у. Пусть а є В и 14(a)— мультимножество всех подслов длины к у слова а. что означает что подслово "1" входит в єп — п— раз и подслово "О"- входит или при фиксированном упорядочении вершин Вк можно принять такое описание окрестности Vk(a): Эти отношения к( к) — эквивалентности являются обычными отношениями эквивалентности в чисто алгебраическом смысле и потому весь куб Вп может быть представлен в следующем виде В содержательном смысле класс Wk(a)— означает, что все его элементы "неотличимы" по окрестности порядка к от слова a Вп. Таким образом "точность" задания слова а с помощью окрестности порядка к измеряется мощностью класса эквивалентности 1У &(а). Далее в главе // предлагается алгоритм для построения классов эквивалентности Wk{a) и VK fc(a). Этот алгоритм формулируется в терминах логического перманента булевой матрицы и использует некоторые идеи из аналогичных построений для случая распознавая по фрагментам [2]. Теорема 2.3.1 позволяет провести проверку 2-эквивалентности слов из Вп за линейное по входу время, т.к. вычисление S{x) и \\х\\ может быть сделано с линейной сложностью от п. Отметим также, что в работе [4] предложен алгоритм установления 2-эквивалентности слов длины п над произвольным конечным алфавитам, имеющий сложность 0(п ). Теорема 2.3.1 показывает, что над словами из класса эквивалентности W%{x) можно проводить определённые преобразования, не выводящие за пределы этого класса. Мы используем далее некоторые из таких преобразований для описания случаев, в которых бинарное слово однозначно определяется своими подсловами длины 2. 1) Итак пусть х = у вектор серий слова х. Теорема 1 утверждает, что серии одинаковой чётности не выводят за пределы класса W cc) Более точно, пусть S— подгруппа симметрической группы Sr действующая отдельно не "чётные" и "нечётные" элементы множества {1,2,--- ,г}. Тогда действие S на слово х определяется следующим образом. Пусть Таким образом д действует на "чётные" серии тождественным образом, а "нечётные" серии переставляет между собой. 2) Другое преобразование состоит в том, что любые две серии одинаковой чётности можно изменять по длине но так, чтобы сумма их длин сохранялось и ни одна из серий не исчезла, т.е. не стала нулевой. Пример. Пусть S(x) = (24421) и Т(х)— преобразование изменяющее второго и четвёртую серию указанным выше способом. Тогда, например, Т{х) = 72774757 Нетрудно понять, что первое из указанных выше преобразований является частным случаем второго. С помощью введённых преобразований можно описать все классы эквивалентности, состоящие из одного слова. Будем проводить классификацию по длине серий S(x). 1) S(x) = 1. Тогда x = 7", V2(x) = {{77)1 1} и \W2(x)\ = 1. 2) S(x) = 2. Тогда x = YT P и K2(x) = {(77) , (77), (77) -1}. В этом случае также jH fz)! = 1 3) S(x) — 3. Тогда x = jpjqjr- Путём преобразования вида 2) слово х можно привести к 2-эквивалентному ему слову х 7 7 71 Если W fz)! 1, то х = х1 ЧТО означает равенство: г = 1. Путём аналогичного рассуждения получаем, что р \. Таким образом х — 77п_27- Отсюда следует, что y2W = {(77)n 3,77,77} и при п 4 класс эквивалентности И Ся) состоит только из слова х. Если же п = 3, то ж = 777 ИЇ Ї, т.е. И 2( ) ф 1 4) 5(ж) 4, т.е. ж = 7mi7m2 - 7mr где г 4. Применяя преобразование вида 2) так же как и в предыдущее случае и используя равенство И (а;) = 1 можно показать, что х = 777 ---7- Отсюда г следует, что если г- = 0 (mod 2), то jH fx)! = 1; если жег = 1 (mod 2), то Все эти рассуждения можно суммировать в следующей теореме. Теорема 2.3.2. Слова а Є В однозначно определяется своими подслова-ми длины 2 если и только если выполняются следующие условия: 1) S{a) 2 2) а = 77n 27 u п 4 5) а — 777 " " 7 ип = 0 (mod 2) (п 2). п Отмстим также, что в работе [4] предложено "алгоритмическое" решение задачи о восстановимое, если это возможно, слова длины п по подсловам длины два в случае произвольного конечного алфавита. Сложность такого алгоритма 0(п4). Рассмотрим в заключение задачу о проверке 2 -эквивалентности. Из теоремы 2.3.2 легко получить следующее утверждение. Теорема 2.3.3. Слова х и у из Вп являются 2 -эквивалентными если и только если выполняются следующие условия Теоремы 2.3.1 и 2.3.3 показывают, что имеется существенная разжи-до в описании классов эквивалентностей по подсловами длины 2 и по фрагментам длины 2 [2]. Одно из важных отличий состоит в том, что 2-эквивалентность по фрагментам влечёт за собой 1-эквивалентность, а 2-эквивалентность по подсловам не имеет таких последствий. Рассмотрим опять серийное представление слова х = 7mi72 7mr-Пусть е(х) = {mi,m2, ,тг}— полный серийный слова х и е1 ) {гп2, тз, , nir-i} внутренний серийный спектр. Далее определим следующие параметры Лемма 2.3.2. Если к а(х) + 2 то все слова из класса эквивалентности W k{%) имеют имеют одинаковые внутренние серийные спектры. Доказательство. Пусть а є V k{x) и у слова а нет серий длины т , где 2 г г — 1. Тогда в слова о нет подслова вида х = y Ti которое есть в слове х. т.к. к а(х) + 2, то к ті + 2 и, значит, х К (а), т.е. условие к— эквивалентности не выполнено. Следствие 2.3.1. Если к а(х) + 2, то все слова из класса эквивалентности V k{%) имеют одинаковое число серий. Доказательство. Т.к. внутренние спектры слов а, 6 t fcf )- совпадают, что их мощности тоже одинаковы. Поэтому общи число серий е(а) = к1 )! + 2 = le1 )! + 2 = е(Ь). Пример. Пусть г = Q и х = 1031403 Є Вп. Рассмотрим класс V Q(X). Если а = 13021204, то е\а) = {2,2} и е1(х) = {3,4}. Дали а V Q(X), Т.К., например, а = 1021 Є а и а = 1021 х. Пусть ж = 12031406, у - 120214061. Тогда S(x) = {3,4}, 5(у) = {2,4, 6} Ясно, что 2 Є S(x) Д 5(у). Поэтому 1021 у и 1021 я В этом случае t(x, у) = 4. Отметим также, что S(x) = 3 и (г/) = 4. 2) Пусть х = 1021031041, у = 1202130214. Тогда 5(ж) = {2,1,3,1,4}, S(y) = {2,3,2} так как 1 Є S(x) A S(y), то 010 х и 010 у. В этом случае i(x,y) = 2, т.к. I2 у и І2 ж. Как ведёт себя величина t(x, у) в "типичном" случае? Это стандартный вопрос при изучении поведения сложных дискретных функций[1]. Из леммы (3.2,4) следует, что вполне правдоподобной верхней оценкой для t(x, у) "почти всегда" может служить функция log2 п. Ниже следующее утверждение служит подтверждением этой догадки. Теорема 3.2.1. Для "почти всех" пар точек (х,у) Вп X Вп длина ми-нимального теста не превосходит асимптотически log2n. Доказательство. Возьмём слово a = 10 -1 и найдём число пар слов (х,у) Є Вп х Вп, которые различает точка а. Пусть Xn(z) — это число число слов v Є Вп таких, что Функция \n{z) достаточно подробно изучалось в работах [13],[14] и [15]. Ясно, что слово z Є Вк различает ровно Xn(z)(2n — \n(z)) пар слов из Вп х Вп, т.к. z принадлежит Xn(z) — словам и не принадлежит остальным (2п — Xn{z))— словам. Как следует из [14] и [15]. и в качестве z может быть выбрано слово а = 10 -1. Отсюда следует, что при к log2 п справедливо асимптотическое неравенство Хп(а) п.2п-к Отсюда для числа vn(a)— пар слов из Вп х Вп различимых словом а Є Вк получаем оценку Положив в (3.3) к = [log2 п + log log2 п] получаем Таким образом, выбрав к log2n мы найдём, что тест такой длины различает асимптотически 22п пар слов ч.и.т.д. 3.3 Алгоритм построения минимального теста Через А обозначается множество всех конечных строк над алфавитом А, включая пустую строку , имеющую нулевую длину и обозначаемую е. Дли на строки х обозначается х. Соединение, или конкатенация строк х и у получится, если выписать строку х, а за ней встык - строку у. Конкатенация строк х и у обозначается ху; очевидно, ху = х + у Мы будем говорить, что строка w - префикс, или начало, строки х, если х = wy для некоторого у Є Л . Будем говорить, что w - суффикс, или конец, строки х, если х = yw для некоторого у є Л . Будем писать W р X, если w - префикс х, и w с х, если w - суффикс X. Пример. аЬ р abcca и сса с abcca. Лемма 3.3.1. Пусть х, у и z - строки, для которых х с z и у с z. Тогда х с у, если х у, у с х, если \у\ \х\, и х = у, если х = \у\. Мы определяем нахлестку двух слов х и у- как самый длинный суффикс х, который является также префиксом у и обозначаем через overlap(a:,y). Если х ф е, то определяем бордюр х как overlap(:c, х) и обозначаем через border(a:). иа при иа х Если T{L.r] - строка длины г, то ее префикс длины к г будет обозначаться Tfc = s[l..k] (в частности, TQ — е и Тт — Т). В этих обозначениях задача о нахождении образца Р длины m в тексте Т длины п состоит в нахождении всех таких і из промежутка 0 і п — т, что Р с Ті+тп Первый приходящий в голову алгоритм для поиска образца Р в тексте Т последовательно проверяет равенство P[l..m] = T[s + l..s + m] для всех п — m + 1 возможных значений s: Naive string matcher algorithm (T,P) Время работы процедуры простейшего алгоритма в худшем случае есть 0((п — m + l)m). В самом деле, пусть Т = an, а Р = ат. Тогда для каждой из п — т + 1 проверок будет выполнено т сравнений символов, всего (п — т + \)т. 3.3.2 Префикс-функция, ассоциированная с образцом Префикс-функция, ассоциированная с образцом Р, несёт информацию о том, где в строке Р повторно встречаются различные префиксы этой строки. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов или обойтись без предварительного вычисления функции перехода. Префикс-функцией , ассоциированной со строкой Р[1..т], называется функция называется функция 7г : {1, 2, , т} —У {0,1, - , т — 1}, определенная следующим образом: Следующий алгоритм вычисляет длину префикс-функция слова Р длины т. Это продукции строки Ь из т целых чисел такой, из что b[j] является длина наибольшего префикса Pj. Доказательство. Пусть а є V k{x) и у слова а нет серий длины т , где 2 г г — 1. Тогда в слова о нет подслова вида х = y Ti которое есть в слове х. т.к. к а(х) + 2, то к ті + 2 и, значит, х К (а), т.е. условие к— эквивалентности не выполнено. Следствие 2.3.1. Если к а(х) + 2, то все слова из класса эквивалентности V k{%) имеют одинаковое число серий. Доказательство. Т.к. внутренние спектры слов а, 6 t fcf )- совпадают, что их мощности тоже одинаковы. Поэтому общи число серий е(а) = к1 )! + 2 = le1 )! + 2 = е(Ь). Пример. Пусть г = Q и х = 1031403 Є Вп. Рассмотрим класс V Q(X). Если а = 13021204, то е\а) = {2,2} и е1(х) = {3,4}. Дали а V Q(X), Т.К., например, а = 1021 Є а и а = 1021 х. 2.4 Восстановление слова по подсловам длины [] + 1 По принятой нами концепции частичная информация о слове х = (х\Х2 х это набор его подслов длины не превосходящей некоторой фиксированной величины к. Таким образом точность определения слова х Є Вп по его подсловам длины к- это класс эквивалентности W k{x). Другими словами, если задано мультимножество всех подслов длины к, то любое слово из класса эквивалентности W k может служить представителем этого класса. Мы не обсуждаем в этой работе проблему реализуемости данного мультимножества подслое, отсылая читателя к работе Щ, в которой показано, что даже самые простые формулировки тлкой проблемы приводят к NP— трудным задачам. Заметим теперь, что справедлива следующая цепочка включений Отсюда следует, что для любого слова а Є Вп существует такое минимальное натуральное число А(а), что Таким образом величина А (а) задаёт порядок окрестности однозначно определяющий слово а Є В" по всем его кратным подсловам. Примеры. 1. Пусть а — 0П, тогда А(о) = 1. 2. Если а = Г О, то (1 0) = V Ol""1), т.е. А(а) 2. С другой стороны, если слово х Є Вп имеет три или больше серий, то в него входит подслово (01) и, значит, V 2(x) ф V 2(a). Поэтому Х(а) = 2. Покажем, что A(a2n) = 2. Действительно, если слово х = у Примеры. 1) Пусть ж = 12031406, у - 120214061. Тогда S(x) = {3,4}, 5(у) = {2,4, 6} Ясно, что 2 Є S(x) Д 5(у). Поэтому 1021 у и 1021 я В этом случае t(x, у) = 4. Отметим также, что S(x) = 3 и (г/) = 4. 2) Пусть х = 1021031041, у = 1202130214. Тогда 5(ж) = {2,1,3,1,4}, S(y) = {2,3,2} так как 1 Є S(x) A S(y), то 010 х и 010 у. В этом случае i(x,y) = 2, т.к. I2 у и І2 ж. Как ведёт себя величина t(x, у) в "типичном" случае? Это стандартный вопрос при изучении поведения сложных дискретных функций[1]. Из леммы (3.2,4) следует, что вполне правдоподобной верхней оценкой для t(x, у) "почти всегда" может служить функция log2 п. Ниже следующее утверждение служит подтверждением этой догадки. Теорема 3.2.1. Для "почти всех" пар точек (х,у) Вп X Вп длина ми-нимального теста не превосходит асимптотически log2n. Доказательство. Возьмём слово a = 10 -1 и найдём число пар слов (х,у) Є Вп х Вп, которые различает точка а. Пусть Xn(z) — это число число слов v Є Вп таких, что z v Функция \n{z) достаточно подробно изучалось в работах [13],[14] и [15]. Ясно, что слово z Є Вк различает ровно Xn(z)(2n — \n(z)) пар слов из Вп х Вп, т.к. z принадлежит Xn(z) — словам и не принадлежит остальным (2п — Xn{z))— словам. Как следует из [14] и [15]. г=1 и в качестве z может быть выбрано слово а = 10 -1. Отсюда следует, что при к log2 п справедливо асимптотическое неравенство Хп(а) п.2п-к Отсюда для числа vn(a)— пар слов из Вп х Вп различимых словом а Є Вк получаем оценку vn{a) = Хп{а)(2п - Хп(а)) п.2п к(2п - п.2п к) (3.3) Положив в (3.3) к = [log2 п + log log2 п] получаем v(a) „ ! (i _ Л.) " 22"(1 - -і-) 22п пу ! 2к К 2к n + log2n v log2n; Таким образом, выбрав к log2n мы найдём, что тест такой длины различает асимптотически 22п пар слов ч.и.т.д. 3.3 Алгоритм построения минимального теста Через А обозначается множество всех конечных строк над алфавитом А, включая пустую строку , имеющую нулевую длину и обозначаемую е. Дли на строки х обозначается х. Соединение, или конкатенация строк х и у получится, если выписать строку х, а за ней встык - строку у. Конкатенация строк х и у обозначается ху; очевидно, ху = х + у Мы будем говорить, что строка w - префикс, или начало, строки х, если х = wy для некоторого у Є Л . Будем говорить, что w - суффикс, или конец, строки х, если х = yw для некоторого у є Л . Будем писать W р X, если w - префикс х, и w с х, если w - суффикс X. Пример. аЬ р abcca и сса с abcca. Лемма 3.3.1. Пусть х, у и z - строки, для которых х с z и у с z. Тогда х с у, если х у, у с х, если \у\ \х\, и х = у, если х = \у\. Мы определяем нахлестку двух слов х и у- как самый длинный суффикс х, который является также префиксом у и обозначаем через overlap(a:,y). Если х ф е, то определяем бордюр х как overlap(:c, х) и обозначаем через border(a:). Если T{L.r] - строка длины г, то ее префикс длины к г будет обозначаться Tfc = s[l..k] (в частности, TQ — е и Тт — Т). В этих обозначениях задача о нахождении образца Р длины m в тексте Т длины п состоит в нахождении всех таких і из промежутка 0 і п — т, что Р с Ті+тп Первый приходящий в голову алгоритм для поиска образца Р в тексте Т последовательно проверяет равенство P[l..m] = T[s + l..s + m] для всех п — m + 1 возможных значений s: каждой из п — т + 1 проверок будет выполнено т сравнений символов, всего (п — т + \)т. 3.3.2 Префикс-функция, ассоциированная с образцом Префикс-функция, ассоциированная с образцом Р, несёт информацию о том, где в строке Р повторно встречаются различные префиксы этой строки. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов или обойтись без предварительного вычисления функции перехода. Префикс-функцией , ассоциированной со строкой Р[1..т], называется функция называется функция 7г : {1, 2, , т} —У {0,1, - , т — 1}, определенная следующим образом:уГПг имеет хотя бы одну серию ms 2, то либо и потому V 2(x) ф У г{р гп)- Отсюда следует, что если то слово х не имеет серий длины 2. Поэтому х должно иметь следующий вид: х = (77)71- Но если х = (01)п, то o(a2n) = , аю(ж) = п — 1. Поэтому ж = ои А(а2П) = 2. Пусть теперь Таким образом А(п)- обычная функция Шеннона, которая определяет максимальный размер окрестности, позволяющий восстановить по кратным подсловам любое бинарное слово длины п. Отметим, что без учёта кратности подслов слова а = 1010-- -10- (10)п 6 = 0101---01 = (01)" неразличимы по подслова длины 2тг—1. Таким образом, если под частичной информацией понимать просто подслова данного слова, то некоторые из слов невозможно восстановить по собственным подсловам. Ситуация несколько меняется, если под частичной информацией понимать подслова с кратностью их вхождения в данное слово.Реконструкция по подсловам
Описания классов эквивалентности в терминах логического перманента
Различающие слова, тестовые множество, тесты
Префикс-функция, ассоциированная с образцом