Разработка эффективных алгоритмов поиска слов в текстах для построения методов сжатия данных
Диссертация
Следует заметить, что задача поиска повторяющихся строк в текстах при сжатии данных имеет отличия от задачи поиска слов в текстах в ее обычной постановке. Это отличие состоит в том, что необходимо выполнять многократный поиск последовательностей символов постепенно возрастающей длины, в то время как в обычной задаче длина искомого слова фиксирована. Эта особенность может быть учтена при… Читать ещё >
Содержание
- Глава 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. Сжатие данных и прогнозирование
Список литературы
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — Т. 1: Синтаксический анализ. — М.: Мир, 1978. — 611 с.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. 535 с.
- Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 1974.-719 с.
- Гельфанд М.С. Предсказание белок-кодирующих областей в нуклеотидных последовательностях // Препринт НЦБИ АН СССР. -Пущино, 1990.
- Гордеев А.В., Молчанов А. Ю. Системное программное обеспечение: Учебник. СПб.: Питер, 2001. ~ 734 с.
- Елепов Б.С., Чистяков В. М. Управление процессами использования информационных ресурсов. Новосибирск: Наука, 1989. — 237 с.
- Кнут Д. Искусство программирования для ЭВМ: В 3 т. -Т. 1: Основные алгоритмы. М.: Мир, 1976. — 734 с.
- Кнут Д. Искусство программирования для ЭВМ: В 3 т. -Т.З: Сортировка и поиск. М.: Мир, 1978. — 840 с.
- Колесник В.Д., Полтырев Г. Ш. Курс теории информации. М.: Наука, 1982. -416 с.
- Кричевский Р.Е. Сжатие и поиск информации. М: Радио и связь, 1989.-167 с.
- Левенштейн В.И. Об избыточности и замедлении разделимого кодирования натуральных чисел // Пробл. кибернетики. М., 1968. -Вып. 20.-С. 173−179.
- РябкоБ.Я. Алгоритмический подход к задаче прогнозирования // Пробл. передачи информ. 1993. — Т. 29, Вып. 2. — С. 96−103.
- Рябко Б.Я. Прогноз случайных последовательностей и универсальное кодирование // Пробл. передачи информ. 1988. — Т. 24, Вып. 2. -С. 3−14.
- Рябко Б.Я. Сжатие данных с помощью «мнимого скользящего окна» // Пробл. передачи информ. 1996. — Т. 32, № 2. — С. 22−30.
- Рябко Б.Я. Сжатие данных с помощью «стопки книг» // Пробл. передачи информ. 1980. — Т. 16, № 4. — С. 16−21.
- Ситняковская Е.И. Оценка эффективности универсальных кодов класса LZ для сжатия информации // Обработка сигналов в системах связи: Сб. науч. тр. уч. ин-тов связи, 1995. № 160. — С. 31−38.
- Слисенко А.О. Алгорифмы поиска периодичности и идентификации слов, работающие в реальное время: Автореф. дисс. на соискание уч. ст. д-ра физ.-мат. наук. -М., 1980. 14 с.
- Трофимов В.К. Кодирование источников с неизвестной и неточно известной статистикой сообщений: Автореф. дисс. на соискание уч. ст. д-ра техн. наук. М., 1988. — 31 с.
- Фионов А.Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. 1997. — Т. 4, № 2. — С. 51−74.
- Штарьков Ю.М. Кодирование сообщений конечной длины на выходе источника с неизвестной статистикой // Тр. V Всесоюз. конф. по теории кодирования и передачи информации: Тез. докл. Москва -Горький, 1972.-Ч. 1.-С. 147−152.
- 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:
- Springer-Verlag, 1999. Milovy, Czech Republic, Lecture Notes in Computer Science 1725, — P. 291−306.
- Apostolico A., Crochemore M. Optimal Canonization of all Substrings of a String // Inform, and Computation. 1991. — Vol. 95, № 1. — P. 76−95.
- Apostolico A., GiancarloR. The Boyer-Moore-Galil String Searching Strategies Revisited // SIAM J. on Computing. 1986. — Vol. 15, № 1. -P. 98−105.
- 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.
- 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.
- Bell T.C., Witten I.H., Cleary J.G. Modelling for Text Compression // ACM Computing Surveys. 1989. — Vol. 21, № 4. — P. 557−591.
- Bell T.C., Witten I.H., Cleary J.G. Text Compression // Englewood Cliffs, N J: Prentice-Hall, Inc. 1990.
- 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.
- Boyer R.S. and Moore J.S. A Fast String Searching Algorithm // Commun. ACM. 1977. — Vol. 20, № 1 o. — P. 762−772.
- Brent R.P. A Linear Algorithm for Data Compression // Aust. Comput. J. 1987. — Vol. 19, № 2. — P. 64−68.
- Burrows M., Wheeler D.J. A Block-sorting Lossless Data Compression Algorithm // SRS Research Report. 1994.
- Charras C., Lecroq T. Exact string matching algorithms. France: Universite de Rouen, Laboratoire d’Informatique de Rouen. 1998.
- Colussi L. Correctness and Efficiency of the Pattern Matching Algorithms // Information and Computation. 1991. — Vol. 95, № 2. — P. 225−251.
- Colussi L. Fastest Pattern Matching in Strings // J. of algorithms. 1994. -Vol. 16, № 2.-P. 163−189.
- 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.
- CrochemoreM. String-Matching on Ordered Alphabets // Theoretical Computer Science. 1992. — Vol. 92, № 1. — P. 33−47.
- 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.
- 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.
- Crochemore M., Perrin D. Two-Way String-Matching // J. of the ACM.1991. Vol. 38, № 3. — P. 651−675.
- Crochemore M., Rytter W. Text Algorithms. Oxford University Press. -1994.
- Elias P. Universal Codeword Sets and Representations of the Integers // IEEE Trans. Inf. Theory. 1975. — Vol. IT-21, № 2 (Mar.). — P. 194−203.
- Feder M., Merhav N., Gutman M. Universal Prediction of Individual Sequences 11 IEEE Trans. Inf. Theory. 1992. — Vol. 38, P. 1258−1270.
- Fiala E.R., Greene D.H. Data Compression with Finite Windows // Commun. ACM. 1989. — Vol. 32, № 4. — P. 490−505.
- Galil Z., Giancarlo R. On the Exact Complexity of String Matching: upper Bounds // SIAM J. on Computing. 1992. — Vol. 21, № 3. — P. 407 437.
- Galil Z., Seiferas J. Time-space optimal string matching // J. of Computer and System Science. 1983. — Vol. 26, № 3. — P. 280−294.
- Gallager R.G. Variations on Theme by Huffman // IEEE Trans. Inform. Theory. 1978. — Vol. 24, № 6. — P. 668−674.
- 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.
- Horspool R.N. Practical Fast Searching in Strings // Software Practice & Experience. — 1980. — Vol. 10, № 6. — P. 501−506.
- Hume A., Sunday D.M. Fast String Searching // Software Practice & Experience.-1991.-Vol. 21, № 11.-P. 1221−1248.
- Jakobsson M. Compression of Character Strings by an Adaptive Dictionary // BIT 25. 1985. — № 4. — P. 593−603.
- KarpR.M. Mathematical Challenges from Genomics and Molecular Biology // Notices of the AMS. 2002. — Vol. 49, № 5 (May). — P. 544 553.
- 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.
- KiefferJ. Prediction and Information Theory // preprint, 1998. -ftp: I/oz.ee.umn.edu/users/kieffer/papers/prediction.pdf.
- Knuth D.E. Dynamic Huffman Coding // J. Algorithms. 1985. — Vol. 6, № 6.-P. 163−180.
- 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.
- 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.
- Lecroq T. A Variation on the Boyer-Moore Algorithm // Theoretical Computer Science 92. 1992. — № 1. — P. 119−144.
- Morris J.H., Pratt V.R. A Linear Pattern-Matching Algorithm // Technical Report 40. Berkeley: University of California. — 1970.
- 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.
- Pevzner P. Computational Molecular Biology. MIT Press. — 2000.
- Raita Т. Tuning the Boyer-Moore-Horspool string searching algorithm, Software Practice & Experience. — 1992. — Vol. 22, № 10. — P. 879−884.
- Rissanen J.J. A Universal Data Compression System // IEEE Trans. Inf. Theory. 1983. — Vol. IT-29, № 5(Sept.). — P. 656−664.
- Rissanen J.J., Langdon G.G. Arithmetic Coding // IBM J. Res. Develop. 1979. — Vol. 23, № 2. — P. 149−162.
- Ryabko B.Ya. Fast Enumerate Source Coding // Proceedings of the IEEE International Symposium on Inform. Theory. 1995. — P. 266.
- Salzberg S., Searls D., Kasif S. Computational Methods in Molecular Biology. Elsevier Science. — 1998.
- 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.
- Storer J.A. Data Compression: Methods and Theory. USA: Computer Science Press, Rockville, MD. — 1988.
- Storer J.A., Szymanski T.G. Data Compression via Textual Substitution // J. of the ACM. 1982. — Vol. 29, № 4. — P. 928−951.
- 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.
- Sunday D.M. A very fast substring search algorithm // Communications of the ACM. 1990. — Vol. 33, № 8. — P. 132−142.
- Welch T.A. A Technique for High-Performance Data Compression // IEEE Computer. 1984. — Vol. 17, № 6. — P. 8−19.
- Wu S., Manber U. Fast Text Searching Allowing Errors // Commun. ACM. 1992.-Vol. 35, № 10.-P. 83−91.
- 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.
- 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.
- Ziv J., Lempel A. An Universal Algorithm for Sequential Data Compression // IEEE Trans. Inform. Theory. 1977. — Vol. IT-23, № 3(May) — P. 337−343.
- 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.
- Работы автора, в которых изложены основные результатыдиссертаиии
- Бах О. А. Выделение экзонов в нуклеотидных последовательностях // 4-я Межрегион, конф. «Обработка сигналов в системах двусторонней телефонной связи». М., 1995. — С. 63−65.
- 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.
- Бах О. А. Методы эффективного поиска повторяющихся подстрок при обработке текстовой информации. // Тр. 5-го Междунар. семинара «Распределенная Обработка Информации» 10−12 окт. 1995 г. (РОИ-95). Новосибирск, 1995. — С. 307−310.
- Бах О. А. Быстрый метод идентификации символьных последовательностей в применении к генетическому анализу // Рос. науч.-техн. конф. «Информатика и проблемы телекоммуникаций»: Тез. докл. Новосибирск, 1996. — Т. 1. — С. 61.
- Бах О. А. Использование методов кодирования источников информации для выделения кодирующих областей в генетических текстах // Второй Сиб. Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96): Тез. докл. Новосибирск, 1996. — С. 20.
- Бах О. А. Построение эффективных кодов для новых классов словарных методов сжатия данных // Информатика и проблемы телекоммуникаций: Междунар. науч.-техн. конф.: Материалы конф. -Новосибирск, 2002. С. 33.