автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка эффективных алгоритмов поиска слов в текстах для построения методов сжатия данных

ВВЕДЕНИЕ.

Глава 1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КОДИРОВАНИЯ И ТЕОРИИ АЛГОРИТМОВ, ИСПОЛЬЗУЕМЫЕ В ДИССЕРТАЦИИ.

1.1 Введение.

1.2 Задача поиска слов в тексте и методы ее решения.

1.2.1 Основные понятия.

1.2.2 Постановка задачи.

1.2.3 Обзор алгоритмов поиска.

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

1.2.5 Алгоритм Бойера - Мура и его модификации.

1.3 Сжатие данных.

1.3.1 Общая характеристика проблемы и основные понятия.

1.3.2 Алгоритмы сжатия данных.

1.3.3 Влияние способов кодирования на эффективность сжатия.

1.3.4 Сжатие данных и прогнозирование.

2.2 Алгоритм "максимальногорасстояния".56

2.2.1 Основная идея алгоритма.56

2.2.2 Подробное описание алгоритма "максимального расстояния" .58

2.2.3 Пример поиска с применением построенного алгоритма "максимального расстояния".66

2.2.4 Ускоренный алгоритм "максимального расстояния".68

2.3 Алгоритм "быстрого сдвига".70

2.3.1 Основная идея алгоритма.70

2.3.2 Подробное описание алгоритма "быстрого сдвига".72

2.3.3 Пример поиска с применением построенного алгоритма "быстрого сдвига".76

2.3.4 Ускоренный алгоритм "быстрого сдвига".79

2.4 Экспериментальное сравнение построенных алгоритмов поиска с ранее известными алгоритмами.81

Выводы.85

Глава 3 ВЫБОР КОДОВЫХ МНОЖЕСТВ ДЛЯ НОВОЙ

ВЕРСИИ АЛГОРИТМА ЛЕМПЕЛА - ЗИВА 86

3.1 Введение.86

3.2 Модифицированный метод Лемпела - Зива и его сравнение 87

3.2.1 Описание метода и пример кодирования с его использованием.87

3.2.2 Экспериментальное сравнение методов сжатия.94

3.3 Сравнительный анализ кодовых множеств.96

3.3.1 Описание кодовых множеств для кодирования целых чисел.96

3.3.2 Экспериментальное сравнение кодовых множеств и выбор наилучших для использования в методе сжатия.100

3.3.3 Статистическое кодирование.109

Выводы. 115

Глава 4 ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ ПОИСКА И МЕТОДА ПРОГНОЗА ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДА Ч СЖА ТИЯ ДАННЫХ.116

4.1 Введение.116

4.2 Алгоритм определения типа данных, основанный на методе прогноза, и его применение к задаче анализа генетических текстов.119

4.2.1 Общее описание метода прогноза.119

4.2.2 Особенности реализации алгоритма определения типа данных.123

4.2.3 Пример работы алгоритма.130

4.3 Распознавание границ между данными различной структуры.136

4.4 Экспериментальные расчеты. 140

4.4.1 Исследование метода прогноза на тестовых данных.140

4.4.2 Подготовка генетических данных для обработки.143

4.4.3 Идентификация фрагмента текста по его типу.144

4.4.4 Распознавание границ между данными различной структуры.148

Выводы.151

ЗАКЛЮЧЕНИЕ.152

ЛИТЕРАТУРА. .155

ПРИЛОЖЕНИЕ.164

ВВЕДЕНИЕ

Актуальность темы

В современных системах передачи и хранения информации важную роль играет эффективное неискажающее сжатие данных. Методы сжатия информации используются в компьютерных сетях при архивации файлов, в модемах и многих других системах и устройствах телекоммуникаций. Решением проблемы сжатия данных занимались многие российские и зарубежные ученые, среди которых можно отметить В. Ф. Бабкина, Р. Е. Кричевского, Б. Я. Рябко, В. К. Трофимова, Ю. М. Штарькова, Е.Н.Гилберта, Я. Зива, А. Лемпела, Э. Ф. Мура, Й. Риссанена, Д. Хаффмана, П. Элайеса. Их труды базировались на методах теории информации, основанной К. Шенноном и А.Н. Колмогоровым в середине ХХ-го века. Стремительное развитие информационных технологий и постоянное совершенствование элементной базы дают возможность реализовывать все более эффективные методы сжатия текстовой информации, поэтому во всем мире исследования и разработка новых алгоритмов сжатия данных продолжаются (см. [14, 15, 32, 45, 67]).

Как правило, текстовая информация обладает большой избыточностью. Неискажающее сжатие данных состоит в устранении этой избыточности. Методы неискажающего сжатия подразделяются на методы для источников с известной статистикой, адаптивные и универсальные. Так, коды Хаффмана [7], Шеннона, арифметический код [19] строятся для источников с известной статистикой, а универсальными являются коды, которые строятся для классов источников (см. [16, 18,20, 58]). Адаптивные коды (например, код "стопка книг" [15], словарные коды) позволяют кодировать источники с неизвестной или меняющейся статистикой. Особое место в этом классе методов занимают словарные алгоритмы.

Словарные методы сжатия данных базируются на поиске в тексте повторяющихся фрагментов и их последующем кодировании (см., например [25, 52, 74]). При таком кодировании, а также в некоторых задачах анализа текстовой информации необходимо многократно выполнять поиск вхождений заданных подстрок в обрабатываемый текст. Следовательно, скорость выполнения операций поиска существенно влияет на быстродействие методов сжатия и анализа текстовой информации в целом. Поэтому построение и исследование быстрых методов поиска подстрок в тексте является базой для построения эффективных алгоритмов сжатия и различных методов обработки данных.

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

Одним из приложений рассмотренных алгоритмов является задача эффективного сжатия генетических данных, хранящихся в различных базах, которая приобрела чрезвычайную актуальность в последнее десятилетие [4, 53, 68]. Значительная часть этой информации получена в рамках международной программы "Геном человека", согласно которой ведутся исследования в разных странах уже более десяти лет, с 1988 года. Молекулы ДНК, несущие генетическую информацию, секвенированы [53], т.е. представлены в базах данных в виде символьных последовательностей. При этом такие последовательности высокоорганизованных живых существ содержат как информационные, так и неинформационные участки. Для их сжатия используются разные методы (в том числе и искажающие - часто неинформационные участки просто удаляются). Поэтому задача распознавания информационных и неинформационных участков играет важную роль при разработке методов сжатия генетических текстов.

В середине 80-х годов (см., например, [13]) было показано, что задача неискажающего сжатия данных математически идентична задаче прогнозирования случайных процессов. Поэтому в последнее время многие алгоритмы, предназначенные для эффективного сжатия данных, применяются к прогнозированию, и наоборот - методы прогноза используются в сжатии данных [44, 55]. Задача прогнозирования также требует применения эффективных методов поиска слов в тексте для своего решения.

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

Цель диссертационной работы

Целью настоящей диссертационной работы является разработка и экспериментальное исследование высокоскоростных методов поиска слов в текстах для построения эффективных систем сжатия информации, использующих новые кодовые множества.

Задачи исследований

Для достижения поставленной цели были определены следующие основные задачи:

1. Разработка и экспериментальное исследование быстрых алгоритмов поиска слов в текстах, учитывающих специфику задачи сжатия и прогнозирования.

2. Экспериментальное исследование и сравнительный анализ кодовых множеств для повышения степени сжатия данных применительно к словарным методам сжатия.

3. Построение эффективных систем сжатия данных, основывающихся на новых алгоритмах быстрого поиска и полученных кодовых множествах.

4. Разработка алгоритмов выделения фрагментов специального вида в генетических последовательностях для построения эффективных методов их сжатия.

Методы исследований

Для решения поставленных задач в диссертационной работе использовались методы теории передачи информации, теории кодирования дискретных источников, теории формальных языков, теории вероятностей и компьютерное моделирование.

Научная новизна

Научная новизна результатов работы состоит в следующем:

1. Предложены новые алгоритмы поиска, быстродействие которых на 10-20 % выше, чем у ранее известных.

2. Построены кодовые множества, эффективность которых при их использовании в задаче неискажающего сжатия данных превосходит применявшиеся ранее.

3. Разработаны высокоскоростные методы сжатия текстовой информации, базирующиеся на эффективных кодовых множествах и быстрых алгоритмах поиска.

4. Впервые построен просто реализуемый алгоритм выделения участков с заданными свойствами в генетических последовательностях, позволяющий повысить эффективность их сжатия.

Практическая ценность

Практическая ценность результатов работы состоит в следующем:

1. Разработаны алгоритмы быстрого поиска слов в текстах, которые могут использоваться в архиваторах файлов и других системах сжатия данных для увеличения скорости кодирования и декодирования и повышения коэффициента сжатия.

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

Основные положения, выносимые на защиту

1. Разработанные алгоритмы поиска слов в текстах превосходят по быстродействию известные ранее в применении их к ряду задач сжатия данных.

2. Предложенные и исследованные в работе кодовые множества позволяют повысить эффективность словарных методов сжатия данных.

3. Сочетание новых алгоритмов поиска слов и новых кодовых множеств дает возможность получить методы кодирования с более высоким быстродействием, позволяющие улучшить коэффициент сжатия текстовой информации.

4. Предложенные быстрые алгоритмы для предварительного разделения генетических текстов на информационные и неинформационные участки повышают эффективность сжатия.

Структура работы

Диссертация состоит из введения, четырех глав, заключения и приложений.

Основные выводы

1. Разработанные алгоритмы быстрого поиска слов в текстах превосходят известные методы по быстродействию в задаче поиска слов возрастающей длины.

2. Использование новых кодовых множеств для представления параметров кодовой комбинации позволяет улучшить коэффициент сжатия модифицированного метода Лемпела-Зива.

3. Построенные алгоритмы определения типа данных и распознавания границ в файлах сложной структуры могут быть использованы для создания системы анализа и обработки генетических последовательностей, предназначенной для выделения в генетических текстах фрагментов, обладающих некоторыми специфическими свойствами. Эти методы основаны на разработанных алгоритмах поиска и методе прогноза.

Апробация работы и публикации

Основные положения и результаты работы докладывались и обсуждались на различных конференциях и конгрессах, в частности: 2-я международная НТК "Актуальные проблемы электронного приборостроения АПЭП-94" (Новосибирск, 1994); 4-я Межрегиональная конференция "Обработка сигналов в системах двусторонней телефонной связи" (Москва, 1995); Seventh Joint Swedish-Russian International Workshop on Information Theory (St.-Peterburg, 1995); международная НТК "Информатика и проблемы телекоммуникаций" (Новосибирск, 1995); 5-й Международный семинар "Распределенная Обработка Информации" 10-12 окт. 1995 г. - РОИ-95 (Новосибирск, Академгородок, 1995); Российская НТК "Информатика и проблемы телекоммуникаций" (Новосибирск, 1996); Второй сибирский конгресс по прикладной и индустриальной математике - ИНПРИМ-96 (Новосибирск, 1996); международная НТК "Информатика и проблемы телекоммуникаций" (Новосибирск, 2002).

По теме диссертации опубликовано восемь печатных работ, которые приведены в конце списка литературы. Кроме того, результаты работы отражены в двух отчетах по НИР.

Реализация результатов работы

Основная работа над диссертацией проводилась в рамках проектов Российского Фонда Фундаментальных Исследований № 96-01-00052 "Асимптотически оптимальные коды для стационарных источников информации", 1996-1998 гг., и № 99-01-00586 "Построение эффективных алгоритмов для кодирования и прогнозирования источников информации и нумерации комбинаторных объектов", 1999-2001 гг.

Отдельные результаты исследований, касающиеся быстрых методов поиска и алгоритмов сжатия данных, внедрены в учебный процесс в Сибирском государственном университете телекоммуникаций и информатики в лекционных, лабораторных и практических занятиях по специальным дисциплинам "Теория вычислительных процессов и структур", "Теория языков программирования и методы трансляции", что отражено в методических указаниях по этим предметам. Разработанные автором методы используются при составлении заданий на дипломное проектирование.

ЗАКЛЮЧЕНИЕ

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - Т. 1: Синтаксический анализ. - М.: Мир, 1978. - 611 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. 535 с.

3. Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 1974.-719 с.

4. Гельфанд М.С. Предсказание белок-кодирующих областей в нуклеотидных последовательностях // Препринт НЦБИ АН СССР. -Пущино, 1990.

5. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение: Учебник. СПб.: Питер, 2001. ~ 734 с.

6. Елепов Б.С., Чистяков В.М. Управление процессами использования информационных ресурсов. Новосибирск: Наука, 1989. - 237 с.

7. Кнут Д. Искусство программирования для ЭВМ: В 3 т. -Т. 1: Основные алгоритмы. М.: Мир, 1976. - 734 с.

8. Кнут Д. Искусство программирования для ЭВМ: В 3 т. -Т.З: Сортировка и поиск. М.: Мир, 1978. - 840 с.

9. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 1982. -416 с.

10. Кричевский Р.Е. Сжатие и поиск информации. М: Радио и связь, 1989.-167 с.

11. Левенштейн В.И. Об избыточности и замедлении разделимого кодирования натуральных чисел // Пробл. кибернетики. М., 1968. -Вып. 20.-С. 173-179.

12. РябкоБ.Я. Алгоритмический подход к задаче прогнозирования // Пробл. передачи информ. 1993. - Т. 29, Вып. 2. - С. 96-103.

13. Рябко Б.Я. Прогноз случайных последовательностей и универсальное кодирование // Пробл. передачи информ. 1988. - Т. 24, Вып. 2. -С. 3-14.

14. Рябко Б.Я. Сжатие данных с помощью "мнимого скользящего окна" // Пробл. передачи информ. 1996. - Т. 32, № 2. - С. 22-30.

15. Рябко Б.Я. Сжатие данных с помощью "стопки книг" // Пробл. передачи информ. 1980. - Т. 16, № 4. - С. 16-21.

16. Ситняковская Е.И. Оценка эффективности универсальных кодов класса LZ для сжатия информации // Обработка сигналов в системах связи: Сб. науч. тр. уч. ин-тов связи, 1995. № 160. - С. 31-38.

17. Слисенко А.О. Алгорифмы поиска периодичности и идентификации слов, работающие в реальное время: Автореф. дисс. на соискание уч. ст. д-ра физ.-мат. наук. -М., 1980. 14 с.

18. Трофимов В.К. Кодирование источников с неизвестной и неточно известной статистикой сообщений: Автореф. дисс. на соискание уч. ст. д-ра техн. наук. М., 1988. - 31 с.

19. Фионов А.Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. 1997. - Т. 4, № 2. - С. 51-74.

20. Штарьков Ю.М. Кодирование сообщений конечной длины на выходе источника с неизвестной статистикой // Тр. V Всесоюз. конф. по теории кодирования и передачи информации: Тез. докл. Москва -Горький, 1972.-Ч. 1.-С. 147-152.

21. Allauzen С., Crochemore М., Raffinot М. Factor Oracle: a New Structure for Pattern Matching // Proceedings of SOFSEM'99: Theory and Practice of Informatics / J. Pavelka, G. Tel and M. Bartosek ed. Berlin:

22. Springer-Verlag, 1999. Milovy, Czech Republic, Lecture Notes in Computer Science 1725, - P. 291-306.

23. Apostolico A., Crochemore M. Optimal Canonization of all Substrings of a String // Inform, and Computation. 1991. - Vol. 95, № 1. - P. 76-95.

24. Apostolico A., GiancarloR. The Boyer-Moore-Galil String Searching Strategies Revisited // SIAM J. on Computing. 1986. - Vol. 15, № 1. -P. 98-105.

25. Bell T.C. A Unifying Theory and Improvements for Existing Approaches to Text Compression: Ph.D. dissertation, Dept. of Computer Science. -New Zealand: Univ. of Canterbury, 1987.

26. Bell T.C. Longest Match String Searching for Ziv-Lempel Compression 11 Res. Rept. New Zealand: Dept. of Computer Science, Univ. of Canterbury. - 1989. - № 6.

27. Bell T.C., Witten I.H., Cleary J.G. Modelling for Text Compression // ACM Computing Surveys. 1989. - Vol. 21, № 4. - P. 557-591.

28. Bell T.C., Witten I.H., Cleary J.G. Text Compression // Englewood Cliffs, N J: Prentice-Hall, Inc. 1990.

29. Bender P.E., Wolf J.K. New Asymptotic Bounds and Improvements on the Lempel-Ziv Data Compression Algorithm // IEEE Trans. Inform. Theory. 1991. - Vol. 37, № 3. - P. 721-729.

30. Boyer R.S. and Moore J.S. A Fast String Searching Algorithm // Commun. ACM. 1977. - Vol. 20, № 1 o. - P. 762-772.

31. Brent R.P. A Linear Algorithm for Data Compression // Aust. Comput. J. 1987. - Vol. 19, № 2. - P. 64-68.

32. Burrows M., Wheeler D.J. A Block-sorting Lossless Data Compression Algorithm // SRS Research Report. 1994.

33. Charras C., Lecroq T. Exact string matching algorithms. France: Universite de Rouen, Laboratoire d'Informatique de Rouen. 1998.

34. Colussi L. Correctness and Efficiency of the Pattern Matching Algorithms // Information and Computation. 1991. — Vol. 95, № 2. - P. 225-251.

35. Colussi L. Fastest Pattern Matching in Strings // J. of algorithms. 1994. -Vol. 16, №2.-P. 163-189.

36. Cook S.A. Linear Time Simulation of Deterministic Two-Way Pushdown Automata // Proc. IFIP. Congr. North-Holland: Amsterdam, 1971. -Vol. TA-2.-P. 172-179.

37. CrochemoreM. String-Matching on Ordered Alphabets // Theoretical Computer Science. 1992. - Vol. 92, № 1. - P. 33-47.

38. Crochemore M., Czumaj A., Gasieniec L., Jarominek S., Lecroq Т., Plandowski W., Rytter W. Speeding up Two String Matching Algorithms // Algorithmica. 1994. - Vol. 12, № 4/5. - P. 247-267.

39. Crochemore M., Hancart C. Automata for Matching Patterns // Handbook of Formal Languages. Berlin: Springer-Verlag, 1997. - Vol. 2: Linear Modeling: Background and Application / G. Rozenberg and A. Salomaa ed. - Chapter 9. - P. 399-462.

40. Crochemore M., Perrin D. Two-Way String-Matching // J. of the ACM.1991. Vol. 38, № 3. - P. 651-675.

41. Crochemore M., Rytter W. Text Algorithms. Oxford University Press. -1994.

42. Elias P. Universal Codeword Sets and Representations of the Integers // IEEE Trans. Inf. Theory. 1975. - Vol. IT-21, № 2 (Mar.). - P. 194-203.

43. Feder M., Merhav N., Gutman M. Universal Prediction of Individual Sequences 11 IEEE Trans. Inf. Theory. 1992. - Vol. 38, P. 1258-1270.

44. Fiala E.R., Greene D.H. Data Compression with Finite Windows // Commun. ACM. 1989. - Vol. 32, № 4. - P. 490-505.

45. Galil Z., Giancarlo R. On the Exact Complexity of String Matching: upper Bounds // SIAM J. on Computing. 1992. - Vol. 21, № 3. - P. 407437.

46. Galil Z., Seiferas J. Time-space optimal string matching // J. of Computer and System Science. 1983. - Vol. 26, № 3. - P. 280-294.

47. Gallager R.G. Variations on Theme by Huffman // IEEE Trans. Inform. Theory. 1978. - Vol. 24, № 6. - P. 668-674.

48. Hancart C. Une analyse en moyenne de l'algorithme de Morris et Pratt et de ses raffinements // Theorie des Automates et Applications, Actes des 2e Journees Franco-Beiges / D. Krob ed. France: Rouen, 1991, PUR 176.1992.-P. 99-110.

49. Horspool R.N. Practical Fast Searching in Strings // Software Practice & Experience. - 1980. - Vol. 10, № 6. - P. 501-506.

50. Hume A., Sunday D.M. Fast String Searching // Software Practice & Experience.-1991.-Vol. 21, № 11.-P. 1221-1248.

51. Jakobsson M. Compression of Character Strings by an Adaptive Dictionary // BIT 25. 1985. - № 4. - P. 593-603.

52. KarpR.M. Mathematical Challenges from Genomics and Molecular Biology // Notices of the AMS. 2002. - Vol. 49, № 5 (May). - P. 544553.

53. Karp R.M., Rabin M.O. Efficient Randomized Pattern-Matching Algorithms I I IBM J. of Research and Development. 1987. - Vol. 31, №2.-P. 249-260.

54. KiefferJ. Prediction and Information Theory // preprint, 1998. -ftp: I/oz.ee.umn.edu/users/kieffer/papers/prediction.pdf.

55. Knuth D.E. Dynamic Huffman Coding // J. Algorithms. 1985. - Vol. 6, №6.-P. 163-180.

56. Knuth D.E., Morris J.H., Pratt V.R. Fast Pattern Matching in Strings // SIAM J. on Computing. 1977. - Vol. 6, № 1. - P. 323-350.

57. Krichevsky R.E., Trofimov V.K. Optimal sample based encoding Markov sources // Third Czechoslovak-Soviet-Hungarian seminar on information theory. Liblice, 1980.-P. 131-138.

58. Lecroq T. A Variation on the Boyer-Moore Algorithm // Theoretical Computer Science 92. 1992. - № 1. - P. 119-144.

59. Morris J.H., Pratt V.R. A Linear Pattern-Matching Algorithm // Technical Report 40. Berkeley: University of California. - 1970.

60. Ouassia K., Abdat M., Plume P. Adaptive limitation of the dictionary size in LZW data compression // Proceedings of the IEEE International Symposium on Inform. Theory. 1995. - P. 18.

61. Pevzner P. Computational Molecular Biology. MIT Press. - 2000.

62. Raita Т. Tuning the Boyer-Moore-Horspool string searching algorithm, Software Practice & Experience. - 1992. - Vol. 22, № 10. - P. 879-884.

63. Rissanen J.J. A Universal Data Compression System // IEEE Trans. Inf. Theory. 1983. - Vol. IT-29, № 5(Sept.). - P. 656-664.

64. Rissanen J.J., Langdon G.G. Arithmetic Coding // IBM J. Res. Develop. 1979. - Vol. 23, № 2. - P. 149-162.

65. Ryabko B.Ya. Fast Enumerate Source Coding // Proceedings of the IEEE International Symposium on Inform. Theory. 1995. - P. 266.

66. Salzberg S., Searls D., Kasif S. Computational Methods in Molecular Biology. Elsevier Science. - 1998.

67. Simon I. String matching algorithms and automata // Proceedings of 1 st American Workshop on String Processing / R.A. Baeza-Yates and N. Ziviani ed. Brazil: Universidade Federal de Minas Gerais, 1993. -P. 151-157.

68. Storer J.A. Data Compression: Methods and Theory. USA: Computer Science Press, Rockville, MD. - 1988.

69. Storer J.A., Szymanski T.G. Data Compression via Textual Substitution // J. of the ACM. 1982. - Vol. 29, № 4. - P. 928-951.

70. Subrahmanya P., Berger T. A Sliding Window Lempel-Ziv Algorithm for Differential Layer Encoding in Progressive Transmission // Proceedings of the IEEE International Symposium on Inform. Theory. 1995. - P. 266.

71. Sunday D.M. A very fast substring search algorithm // Communications of the ACM. 1990. - Vol. 33, № 8. - P. 132-142.

72. Welch T.A. A Technique for High-Performance Data Compression // IEEE Computer. 1984. - Vol. 17, № 6. - P. 8-19.

73. Wu S., Manber U. Fast Text Searching Allowing Errors // Commun. ACM. 1992.-Vol. 35, № 10.-P. 83-91.

74. WynerA.D., WynerA.J. Improved Redundancy of a Version of the Lempel-Ziv Algorithm // IEEE Trans, on Inform. Theory. 1995. -Vol. 41, №3.-P. 723-731.

75. Zhu R.F., Takaoka T. On improving the average case of the Boyer-Moore string matching algorithm // J. of Information Processing. 1987. -Vol. 10, №3.-P. 173-177.

76. Ziv J., Lempel A. An Universal Algorithm for Sequential Data Compression // IEEE Trans. Inform. Theory. 1977. - Vol. IT-23, № 3(May) - P. 337-343.

77. Ziv J., Lempel A. Compression of Individual Sequences via Variable-rate Coding // IEEE Trans. Inform. Theory. 1978. - Vol. IT-24, № 5(Sept.) -P. 530-536.

78. Работы автора, в которых изложены основные результатыдиссертаиии

79. Бах О.А. Выделение экзонов в нуклеотидных последовательностях // 4-я Межрегион, конф. "Обработка сигналов в системах двусторонней телефонной связи". М., 1995. - С. 63-65.

80. Bach О.А. Algorithms of the Efficient Pattern Matching in the Information Files //Seventh Joint Swedish-Russian International Workshop on Information Theory: Proceedings. St.-Peterburg, 1995. - P. 27-29.

81. Бах О.А. Методы эффективного поиска повторяющихся подстрок при обработке текстовой информации. // Тр. 5-го Междунар. семинара "Распределенная Обработка Информации" 10-12 окт. 1995 г. (РОИ-95). Новосибирск, 1995. - С. 307-310.

82. Бах О.А. Быстрый метод идентификации символьных последовательностей в применении к генетическому анализу // Рос. науч.-техн. конф. "Информатика и проблемы телекоммуникаций": Тез. докл. Новосибирск, 1996. - Т. 1. - С. 61.

83. Бах О.А. Использование методов кодирования источников информации для выделения кодирующих областей в генетических текстах // Второй Сиб. Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96): Тез. докл. Новосибирск, 1996. — С. 20.

84. Бах О.А. Построение эффективных кодов для новых классов словарных методов сжатия данных // Информатика и проблемы телекоммуникаций: Междунар. науч.-техн. конф.: Материалы конф. -Новосибирск, 2002. С. 33.