Разработка многоплатформенной системы компрессии словарной информации для карманных персональных компьютеров
Диссертация
В ходе выполнения диссертационной работы разработаны принципы построения и алгоритмические решения для СКСИ, при этом получены следующие научные результаты: ф 1. Проведено всестороннее исследование существующих алгоритмов и методов сжатия словарной информации, в результате которого была обоснована необходимость создания новой СКСИ. Разработана бинарная и логическая структура данных словаря, что… Читать ещё >
Список литературы
- Боровко Р. Мировой рынок КПК. // CNews Analytics • (http://www.cnews.ru/reviews/laptop/part4).
- Moore G. E. Cramming More Components into Integrated Circuits. Electronics, Volume 38, Number 8, April 19, 1965 (ftp://download.intel.com/research/silicon/moorespaper.pdf).
- Кричевский P.E. Сжатие и поиск информации. — М.: Радио и связь, 1989.
- Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989.
- Ф 5. Кнут Д. Е. Искусство программирования для ЭВМ. Т. 1: Основныеалгоритмы. — М.: Мир, 1976.
- Кнут Д.Е. Искусство программирования для ЭВМ. Т. 2: Получисленные алгоритмы. — М.: Мир, 1977.
- Кнут Д.Е. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М.: Мир, 1978.
- Страуструп Б. Язык программирования С++. Специальное издание. -М.: Бином, 2002.
- Рябко Б.Я. Сжатие данных методом стопки книг // Проблемы передачи информации. — 1980. — Т. 16, N4. — С. 16−21.
- Ю.Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования -СПб: Питер, 2001 368 с.
- П.Кадач А. В. Эффективные алгоритмы неискажающего сжатия текстовой информации. Дисс. на соиск. уч. ст. канд. физ-мат наук., Новосибирск, 1997.
- Шеломовский П.Л. Реализация поиска в словаре с использованиемстрокового Б-дерева. //Оборонный комплекс — научно-техническому прогрессу России. — 2003. № 4. — с. 29−34.
- Шеломовский П.Л. Методологический подход к оптимизации технологического процесса автоматизированного перевода. //Оборонный комплекс — научно-техническому прогрессу России. — 2001.-№ 1.-с. 47−49.
- Н.Гагарина Л. Г., Шеломовский П. Л. Некоторые аспекты разработки и тестирования программного обеспечения. //Оборонный комплекс — научно-техническому прогрессу России. 2000. — № 4. — с. 26−28.
- Гагарина Л.Г., Шеломовский П. Л. «Моделирование структуры данных для компрессии текстовой информации» в сб."Информационное управление и телекоммуникационные системы." Межвузовск. сб. М.: МИЭТ, 2002, 232с.- с. 37−41.
- Шеломовский П.Л. Система автоматизированного перевода текстов. //Тезисы докладов 8-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов. -М/.МИЭТ, 2001.-c.227.
- Шеломовский П.Л. Моделирование для компрессии словарной информации при разработке ядра словаря. //Сборник трудов международной научно-технической конференции «Приборостроение 2001». -Черкассы.:ЧИТИ, 2002. — с.359−361.
- Шеломовский П.Л. Методика сжатия структурированной текстовой информации. //Тезисы докладов 9-й Всероссийской международной научно-технической конференции студентов и аспирантов. -М.:МЭИ, 2002. с.296−297.
- Simonyi C. Hungarian Notation // Microsoft Developer Network Library, 1999. (http://msdn.microsoft.com/library/enus/dnvsgen/html/hunganotat.asp).
- Abrahamson D. An Adaptive Dependency Source Model for Data Compression // Communications of the ACM. January 1989 Volume 32 Number 1, pp. 77−83
- Abramson N. Information Theory and Coding. — New York: McGraw-Hill, 1963.
- Shannon C.E., Weaver W. The Mathematical Theory of Communication.
- Urbana, IL: University of Illinois Press, 1949.
- Schwartz E.S., Kallick B. Generating a canonical prefix encoding // Communs. ACM. — 1964. — Vol. 7, N 3. — P. 166−169.
- Connell J.B. A Huffman-Shannon-Fano code // Proc. IEEE. — 1973. — Vol. 61, N7. —P. 1046−1047.
- Moffat A., Witten I., Neal R. Arithmetic coding revisited // ACM Transactions on Information Systems, Vol. 16, No. 3, July 1998. P. 256−294.
- Bookstein A., Klein S. Compression, Information Theory, and Grammars: A Unified Approach // ACM Transactions on Information Systems, Vol. 8, No. 1, January 1990, Pages 27−49.
- Witten I.H., Neal R.M., Cleary J.G. Arithmetic coding for data compression // Communications of the ACM. — 1987. — Vol. 30, N 6.1. P. 520−540.
- Bell T., Witten I., Cleary J. Modeling for Text Compression. // ACM Computing Surveys, Vol. 21, No. 4, December 1989, pp. 557- 591.
- Bell T., Cleary J., Witten I. Text Compression. — Englewood Cliffs, NJ: Prentice-Hall, 1990.
- Storer J.A. Data Compression: Methods and Theory. Rockville, ML: Computer Science Press, 1988.
- Cleary J., Teahan W., Witten I. Unbounded length contexts for PPM // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1995. — P. 52−61.
- Cleary J., Witten I. Data compression using adaptive coding and partial string matching // IEEE Trans. Communs. 1984. — Vol. 32, N 4. — p. 396−402.
- Bell T.C., Moffat A.M. A note on DMC data compression scheme // Computer J. 1989. — Vol. 32, N 1. — P. 16−20.
- Horspool R.N., Cormack G.V. Comments on «A locally adoptive data compression scheme» // Communs. ACM. — 1987. Vol. 16, N 2. — p. 792−794.
- Буяновский Г. Ассоциативное кодирование // Монитор. — 1994. — N8. —С. 10−19.
- McMillan В. Two inequalities implied by unique decipherability. //IRE Trans, on Inf. Th. IT 1956 — Vol. 2. — p. 115−116.
- Long D., Jia W. Optimal Maximal Prefix Coding and Huffman Coding (http://www.cs.cityu.edu.hk/~dylong/DMS2001 .pdf)
- Mehlhorn К. Data structures and algorithms I: Sorting and searching. — Berlin: Springer-Verlag, 1984.
- Kirkpatrick D., Reisch S. Upper bounds for sorting integers on random access machines // Theor. Computer Sei. — 1984. — Vol. 28, N 3. — P. 263−276.
- Burrows M., Wheeler D.J. A block-sorting lossless data compression algorithm. — Palo Alto, 1994. — (Tech. Rep. / DEC Systems Research Center, N 124).
- Fenwick P.M. — Block sorting text compression — final report. Auckland, 1996. — (Tech. Rep. / Dept. of Сотр. Sei., Auckland Univ., N CS-96−130).
- Марков A.A. Введение в теорию кодирования — М.: Наука. Гл. ред. физ.-мат. лит. 1982. 192 с.
- Rissanen J., Langdon G. Universal modelling and coding // IEEE Trans. Inform. Theoiy. 1981. — Vol. 27, N 1. — P. 12−23.
- Huffman D.A. A method for the construction of minimum-redundancy• codes//Proc. IRE.-1952.-Vol. 40.-P. 1098−1101.
- Vitter J.S. Design and analisys of dynamic Huffman algorithm // J. ACM. 1987. — Vol. 34, N 4. — P. 825−845.
- Golomb S.W. Run-length encodings // IEEE Trans. Inform. Theoiy. — 1966. — Vol. 12, N 3. — P. 399−401.
- Elias P. Interval and recency rank source coding: Two on-line variable-length schemes // IEEE Trans. Inform. Theory. — 1987. — Vol. 33, N 1.• —P. 3−10.
- Golomb S.W. Run-length encodings // IEEE Trans. Inform. Theory. — 1966. — Vol. 12, N 3. — P. 399−401.
- Teuhola J., Raita T. Text Compression Using Prediction // Сборниктрудов конференции RDIR'86, pp. 97−101.
- Teuhola J., Raita T. — Application of a finite-state model to text compression. Turku, 1993. — (Tech. Rep. / Dept. of Сотр. Sci., Univ. of• Turku, N TR-93−5).
- Lempel A., Ziv J. On the complexity of finite sequences // IEEE Trans. Inform. Theoiy. — 1976. — Vol. 22, N 1. — P. 75−81.
- Bell T.C., Witten I.H. The relationship between greedy parsing and symbol-wise text compression // J. ACM. — 1994. — Vol. 41, N 4. — P. 708−724
- Farach M., Muthukrishnan S. Proc. SPAA'95 Santa Barbara CA USA, pp. 244−253.
- Silva de Moura E., Navarro G. Ziviani N., Baeza-Yates R. Fast and Flexible Word Searching on Compressed Text // ACM Transactions on Information Systems, Vol. 18, No. 2, April 2000, Pages 113−139.
- Bentley J., Sleator D., Tarjan R., Wei V. A Locally Adaptive Data Compression Scheme. // Communications of the ACM April 1986 Volume 29 Number 4, pp. 320−330.
- Katajainen J. Raita T. An Analysis of the Longest Match and the Greedy Heuristics in Text Encoding. // Journal of the Association for Computing Machinery. Vol 39, N2, April 1992, p. 281−294
- Sundaresan N., Moussa R. Algorithms and Programming Models for Efficient Representation of XML for Internet Applications. // Сборник трудов конференции WWW10, May 1−5, 2001, Hong Kong, pp. 366 375.
- Manzini G. An analysis of the Burrows-Wheeler Transform (Extended Abstract)
- Jones D. Applicatioin of Splay Trees to Data Compression // Communications of the ACM August 1988 Volume 3 1 Number 8, pp. 996−1007
- Comer D. The Ubiquitous B-Tree //ACM Computing Surveys, Vol 11, No 2, June 1979.
- Vittert J. External Memory Algorithms. // Сборник трудов конференции PODS'98, Seattle, WA, USA, pp. 119−128.
- Ferragina P., Grossi R. The String B-Tree: A New Data Structure for String Search in External Memory and Its Applications. // Journal of the ACM, Vol. 46, No. 2, March 1999, pp. 236 -280.
- Farach M., Muthukrishnan S. Optimal Parallel Dictionary Matching and Compression //Сборник трудов конференции SPAA'95 Santa Barbara CA USA, pp. 244−253.
- Martinez C., Roura S. Randomized Binary Search Trees, //Journal of the ACM, Vol. 45, No. 2, March 1998, pp. 288 -323.
- Ferragina P., Grossi R. Fast String Searching in Secondary Storage: Theoretical Developments and Experimental Results.
- Crochemore M., Lecroq T. Pattern-Matching and Text-Compression Algorithms. //ACM Computing Surveys, Vol. 28, No. 1, March 1996, pp. 39−41.
- Larson P. Dynamic Hash Tables. //Communications of the ACM April 1988 Volume 31 Number 4, pp. 446−457.
- Farach M. Thorup M., //String Matching in Lempel-Ziv Compressed Strings. Сборник трудов конференции STOC'95, Las Vegas, Nevada, USA, pp. 703−712.
- Bayer R., McGreight C. Organization and maintenance of large ordered indexes//Acta Inf. 1.3 (1972), 173−18 971. «Unified Modeling Language Specification, Version 1.5», Object Management Group, Inc., March 2003
- Extensible Markup Language (XML) 1.0 (Second Edition) // W3C Recommendation 6 October 2000 (http://www.w3.org/TR/REC-xml)
- The Unicode Standard, Version 4.0http://www.unicode.Org/versionsAJnicode4.0.0/bookmarks.html)