Восстановление и различимость слов по подсловам тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Хошманд Асл Мохаммад Реза

• Хошманд Асл Мохаммад Реза
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Хошманд Асл Мохаммад Реза

1 Введение

1.1 Реконструкция по подсловам.

1.2 Различимость слов.

2 Реконструкция по подсловам

2.1 Подслова, окрестности, классы эквивалентности.

2.2 Описания классов эквивалентности в терминах логического перманента.

2.2.1 Классы эквивалентности Wk{x)

2.2.2 Классы эквивалентности W<k(x).

2.3 Серийное описание классов эквивалентности.

2.3.1 Характеризация < 2 -эквивалентности.

2.4 Восстановление слова по подсловам длины > [|] +

3 Различимость слов

3.1 Различающие слова, тестовые множество, тесты.

3.2 Свойства и оценки функции t(х, у).

3.3 Алгоритм построения минимального теста.

3.3.1 Простейший алгоритм.

3.3.2 Префикс-функция, ассоциированная с образцом

3.3.3 Алгоритм Кнута - Морриса - Пратта.

3.3.4 Алгоритмы нахождения t(х, у).

Введение диссертации (часть автореферата) на тему «Восстановление и различимость слов по подсловам»

1.1 Реконструкция по подсловам Часть и целое всегда является предметом изучения науки. Основной философский вопрос при таком изучении звучит так: как устроен мир? Еслипри исследовании информацию принят следующий тезис:Всякая информация может быть представлена словом в конечном алфавите, то часть проблем, связанных с понятием информация может бытьсформулировано в виде изучения слова и его частей. Что понимать под частью слова зависит от контекста изучаемой проблемы и точные постановкизадач могут варьироваться в достаточно широких пределах? В целом такого роде задачи имеют глубокие связи с алгеброй, топологией, теориейчисел,теорией информации и математической генетикой.Основным объектом изучения в диссертации являются слова конечнойдлины над бинарным алфавитом {0,1}. Это множество обозначается черезв*. Если X = xiX2 • • • Хп- слово из Б*, то любое слово виданазывается подсловом х. При этом 1 <к <п—г. Таким образом множествовсех подслов длины к слова х содержит не более чем (п — А; + 1)— различных подслов и обш,ее число подслов слова длины, с учётом их кратности,равно ("^^) • Каждое подслово а слова х несёт определённую информациюоб этом слове. Как оценить или измерить эту информацию? Этот вопросявляется одним из ключевых вопросов, рассматриваемых в этой диссертации. Интуитивно ясно, что чем длиннее подслова слова ж, тем большенесут они информации об исходном слове. В каком случае слово можнооднозначно восстановить по набору его подслов ограниченной длины и вкаком случае это можно сделать лишь с определенной погрешностью? Всеэти вопросы уже рассматривались в целом ряде исследований, относяш,ихся к комбинаторике слов и на многие из них получены ответы той илииной степени полноты и определённости. Однако вопросы восстановимостии различимости формулировались в основном по отношению к фрагментам слова, а не к под словам. Фрагмент- это более широкое понятие частислова, чем только подслова ограниченной длины. Однако подслово- это боли структурированная часть слова, чем фрагмент, что также привноситопределённую специфику в проблему восстановимости и различимости поподсловам. Пусть В — {0,1}— двоичный алфавит и В*— множество всехслов конечной длины над алфавитом В. Если х = (a;iX2 • • • Хп) Е В*, тодлину слова х мы будем обозначать через \х\. Множество всех бинарныхслов длины п и < п мы будем обозначать соответственно через В"^ и В-"^.Множество В* является моноидом с операцией конкатенациих,у G В* -)-ху е В*Определение 1.1.1. Слово у = {у\У2'"Ук) называется подсловом словаX = (xiX2 • • -Хп), еслиХГ = УЪ ^i+i = У2Г'- , Xi+k-i = Укдля некоторого г из интервала [1,п — к + 1].Слово у = {у\У2'"Ук) называется фрагментом слова х =если существует такая последовательность 1 < ii < 12 < - • • < ik < п,чтоXii =yi,Xi^=y2,--- , Xik = УкЗамечание. У части авторов исследований по комбинаторике слов используется несколько отличная терминология. Так в монографии[1] подслово (subword) в нашей терминологии- это фактор (factor), а фрагментэто подслово. Мы будем придерживаться введённых выше обозначений,понимая всю условность преимуш,еств и недостатоков различных терминологий.На множестве В* введём частичный порядок (<) , положивX <уесли X— является подсловом слова у.Пусть а Е 5* и 14(а)— мультимножество всех подслов длины к у слова а.Пример. Если бп = (01)" = 1010 • • • 10 G Л", точто означает что нодслово "1" входит в £„ ^ рэ-з и подслово "О"- входитв £п — ^ — раз.Аналогичнов тех же терминах. При этом |Vi(£:n)| = 2п, |F2(£^n)| = 2п — 1.АналогичноВ содержательном смысле класс Wk{a)— означает, что все его элементы"неотличимы" по окрестности порядка к от слова а £ Б " . Таким образом"точность" задания слова а с помош,ью окрестности порядка < к измеряется мош,ностью класса эквивалентности И^<^(а).Далее в главе / / предлагается алгоритм для построения классов эквивалентности Wk{a) и W<f.{a). Этот алгоритм формулируется в терминах логического перманента булевой матрицы и использует некоторые идеи изаналогичных построений для случая раснознавая по фрагментам [2].Алгоритм построения классов эквивалентности.Пусть теперь А < v,e > — множество всех решений уравнения<x,v>=e (1.2)Здесь V = {iii2 • • • ik), е = (eie2 • • • вк) G В^, х — (жхжг • • • Хп) G -В". Такимобразом A{v^ е)— это множество двоичных слов длины п "проектирование"которых на оси {iii2 • • • u ) приводит к слову е. В терминах булевой алгебрыэто множество выглядит следующим образом.Лемма 1.1.1. Справедливо соотношениеДругими словами A{v^e)— это {п — к)— мерный нодкб, В'^ или элементарная конъюнкция ранга к.По схеме (1.1) сформируем логическую матрицу А = \\Aij\\. Эта матрицаимеет размеры {п — к -\- 1) х [п — к -\- 1). Под логическим перманентомматрицы А мы будем понимать следующую Д.Н.Ф= \JЗдесь Sn-k+i— симметрическая группа порядка {п — к + 1).Теорема 1.1.1. Класс эквивалентности Wk{a) описывается следующийформулойWk{a) = per АТаким образом множество элементов класса эквивалентности Wk{a) совпадает с множеством единиц булевой функции Д.Н.Ф. которой есть per А. Далее в этой главе строится описание класса эквивалентности H^<fc(a).Этот класс также описывается с помощью перманента логической матрицыА^1с{а), которая является "клеточной" матрицей с блоками А^,в главе (2) строится "алгебраическое" описание классов эквивалентностиWk[a) для "малых" А; = 1, 2,3 и приводится общая схема такого описания.Пусть X — {х\Х2 • • -Хп) £ -В", а = {aia2 • • • а^) Е В^ и ta{x)— число вхождений слова а в слово х в качестве подслова. Другими словами -ta{x)это кратность вхождения слова а в мультимножество Vk{x), определенноевыше.Если г Xi при а = 11 — Xi при а = Ото справедливо следующее утверждение.Лемма 1.1.2.10Таким образом ta{x)— это полином от п— переменных степени к.Теорема 1.1.2. Слова х и у из В"^ являются 2— эквивалентными тогда^ и только тогда, когда выполняются условияS{x) = S{y)(1.4)2) Ы - \\y\\ =Х1-у1 = Хп-УпТеорема 1.1.2 нозволяет провести проверку 2-эквивалентности слов изВ^ за линейное по входу время, т.к. вычисление S{x) и \\x\\ может бытьсделано с линейной сложностью от п.Отметим также, что в работе [4] предложен алгоритм установления 2эквивалентности слов длины п над произвольным конечным алфавитам,имеющий сложностьИз Теоремы 1.1.2 можно получить условия, при которых любое слово изБ " однозначно определяется своими подсловами длины 2.11Теорема 1.1.3. Слово а G В" однозначно определяется своими подсловами длины 2 если и только если выполняются следующие условия:1) S{a) < 22) а = 77 "^7 и п>43) а = 7777 • • • 77 •" ^ = О (mod 2) (п > 2).Отметим также, что в работе [4] предложено "алгоритмическое" решениезадачи о восстановимости, если это возможно, слова длины п по подсловамдлины два в случае произвольного конечного алфавита. Сложность такогоалгоритмаОписание классов (< 2)— эквивалентности содержатся в теореме 1.1.4.Теорема 1.1.4. Слова х и у из В^ являются < 2 -эквивалентными еслии только если выполняются следующие условия1) S{x) = S{y) 3) xi = Ух, Хп = Уп(1.5)2) \\x\\ = \\y\\Так как имеет цепочка включений• • • С W<k{a) С И^<А.-1(а) С W<k-2[a) С • • •то начиная с некоторого к эта цепочка стабилизируется, что означает следующий факт:Слово а однозначно определяется своими нодсловами длины < к. Значение12этого к как функции от а £ В" мы обозначим черезПримеры.1. Если а = О", то Хп{а) = 12. Если а = ОЧ"-^ то Хп(а) = 2, т.к.иV2(a) = {0^ Г - ^По V2{a) слово а восстанавливается однозначно, т. к. структура У2{а) показывает, что у слова а равно 2 серии (если бы не так, то в V2(a) входилибы слова (01) и (10).) и слово начинается с нуля.ПустьТеорема 1.1.5. Справедливо равенствоЭто теорема показывает, что задача о восстановлении слова длины ппо "различным" фрагментам и задача восстановлении слова по всем подсловам (с учётом кратности) приводят к одной и той же величине длины"частей", необходимых для однозначной реконструкции.

Список литературы диссертационного исследования кандидат физико-математических наук Хошманд Асл Мохаммад Реза, 2005 год

1. Lothaire М.// Combinatorics on Words. Encyclopedia of Mathematics and its Application Reading. M1.: Addition-Wisely.Publ. Co, 1983.

2. Леонтьев В.К.// Задачи восстановления слов по фрагментам и их приложения. "Дискретный анализ и исследование операций", 1995, Т. 2, № 2. С. 26-48.

3. Зенкин А. И., Леонтьев В.К.// Об одной неклассической задаче распознавания, Журнал вычислительной математики и математической физики. 1984, Т. 24, № 6, С. 925-931.

4. Сметанич Я. С.// О восстановлении слов, Труды Математической института, А. Стеклова. М. "Наука", 1973, Т. 83, С. 183-202.

5. Леонтьев В.К., Сметанин Ю. Г.// О восстановлении векторов набору их фрагментов//Докл. АН СССР. 1988, Т. 302, № 6.

6. Журавлев Ю. И.// Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики.М.:Наука,1978.

7. Леонтьев В. К.// Распознавание двоичных слов по их фрагментам // Докл. РАН. 1993. Т. 330, № 4. С. 434-436.

8. Калашник В. В.// Восстановление слова по его фрагментам // Вы-числ. математика и вычисл. техника. Харьков, 1973. Вып. 4. С. 56-57.

9. Simon I.// Piecewise testable events // Automata Theory and Formal Languages. Berlin etc.: Springer-Verl., 1975. P. 214-222. (Lecture Notes in Com-put. Sci.; V. 33).

10. Burosch G., Frankl U., Rohl S.// Uber Ordnungen von Binaworten // Rostock Math. Kolloq. 1990. N 39. P. 53-64.

11. Алиев Ш. M.// Алгоритмические вопросы построения оптимальных кодов для многих приемников: Дис. . канд. физ.-мат. наук. М., 1993.

12. Сметанич Я. С. // О восстановлении слов // Докл. АН СССР. 1971. Т. 201, № 4. С. 798-800.

13. L.J.Guibas and A.M.Odlyzko //Periods in strings. J. Comb. Theory (A) 30 (1981), 19-42.

14. L.J.Guibas and A.M.Odlyzko // String overlaps, pattern matching, and non-transitive games. J.Comb. Theory (A) 30 (1981), 183-208.

15. A.M.Odlyzko// Enumeration of Strings AT'T Bell Laboratories, Murra Hill, New Jersey 07974 USA.

16. Т. Кормен, Ч. Лейзерсон, P. Ривест// Алгоритмы: построение и анализ/ Пер. с англ. под ред. А. Шеня/ МЦНМО: БИНОМ. Лаборатория знаний, 2004.

17. Lothaire М.// Applied Combinatorics on words//Version June 23, 2004.