Помощь в написании студенческих работ
Антистрессовый сервис

Разработка многоплатформенной системы компрессии словарной информации для карманных персональных компьютеров

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В ходе выполнения диссертационной работы разработаны принципы построения и алгоритмические решения для СКСИ, при этом получены следующие научные результаты: ф 1. Проведено всестороннее исследование существующих алгоритмов и методов сжатия словарной информации, в результате которого была обоснована необходимость создания новой СКСИ. Разработана бинарная и логическая структура данных словаря, что… Читать ещё >

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

Содержание

  • Глава 1. Методы и средства сжатия информации на основе существующих моделей вычислений и способов кодирования
    • 1. 1. Классификация методов сжатия
    • 1. 2. Критерии оценки методов сжатия
    • 1. 3. Методы энтропийного кодирования
    • 1. 4. Модель вычислений
    • 1. 5. Конечные вероятностные источники
    • 1. 6. Кодирование источников Бернулли с известной вероятностной структурой
    • 1. 7. Кодирование источников Бернулли с неизвестной вероятностной структурой
    • 1. 8. Методы статистического моделирования
    • 1. 9. Алгоритм сжатия сортировкой блоков
    • 1. 10. Словарные методы сжатия
  • Выводы по главе
  • Глава 2. Исследование процесса поиска в словаре с использованием строкового Б'-дерева
    • 2. 1. Классификация задач поиска
    • 2. 2. Деревья поиска
    • 2. 3. Задача поиска в сжатой информации
    • 2. 4. Поиск в строковом Б-дереве
    • 2. 5. Модификация Б-дерева. Б'-дерево
    • 2. 6. Постановка задачи диссертации
  • Выводы по главе
  • Глава 3. Разработка интегрированной вероятностной модели данных для компрессии словарной информации
    • 3. 1. Общие положения по дизайну и разработке ядра словаря
    • 3. 2. Реализация алгоритмов Б'-дерева
    • 3. 3. Модульная компоновка библиотеки компрессии словарной информации
    • 3. 4. Арифметическое кодирование
    • 3. 5. Моделирование
    • 3. 6. Контексты сжатия
    • 3. 7. Построение вероятностной модели данных. Использование контекстов
    • 3. 8. Формализация модели словарной статьи
    • 3. 9. Использование словаря для кодирования словарных статей
  • ЗЛО Структура многопроходного алгоритма сжатия данных
  • Выводы по главе
  • Глава 4. Параметризация интегрированной модели данных, анализ результатов
    • 4. 1. Изменение параметров модели на этапе сжатия
    • 4. 2. Методика эксперимента
    • 4. 3. Результаты эксперимента
  • Выводы по главе

Актуальность проблемы. Наблюдаемое в течение последних 15 лет стремительное увеличение количества используемых вычислительных машин (сопровождаемое неуклонным ростом их возможностей) привело к значительному расширению как круга пользователей ЭВМ, так и набора решаемых с их помощью задач.

Одновременное уменьшение размеров персональных компьютеров (ПК) сделало возможным создание карманных ПК (КПК). Сфера применения таких устройств необычайно широка: от использования в качестве персонального цифрового помощника (Personal Digital Assistant, PDA) до полноценной работы с изображением и звуком. Одним из возможных применений КПК является использование в качестве карманного словаря. Все попытки разработки программного обеспечения (ПО), предпринимаемые в последнее время в этой области, сталкиваются с необходимостью разработки и адаптации специальных алгоритмов обработки словарной информации для карманных устройств. В отличие от современных настольных и переносимых ПК, КПК обладают гораздо меньшим хранилищем данных и вычислительными ресурсами. Результаты исследований, направленных на создание эффективных схем неискажающего сжатия текстовой информации изложены в работах отечественных и зарубежных ученых: А. Маркова [43], Г. Буяновского [36],.

И. Уиттена[28,29,30,32,33,53], Т. Белла [29,30,34,53], М. Бурроуза [41], Д. Виллера [41] и др.

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

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

Фундаментом научного подхода к разработке алгоритмов, представленных в данной работе, является современная теория кодирования информации.

Объекты и задачи работы.

1 Программное ядро словаря.

Основные задачи:

— изучение целевых платформ разработки;

— выработка требований к библиотеке ядра словаря.

2 Структура словаря.

Основные задачи:

— исследование особенностей построения словарей и хранения словарной информации;

— разработка вероятностной модели данных;

— разработка бинарного формата файла.

3 Эффективные алгоритмы сжатия словарных данных. 5.

Основные задачи:

— исследование эффективных алгоритмов сжатия информации;

• - моделирование вероятностной структуры обрабатываемых данных.

4 Эффективные алгоритмы поиска в словаре.

Основные задачи:

— исследование быстрых алгоритмов поиска по словарю;

— разработка адаптированного к используемому аппаратному решению алгоритма поиска по словарю.

5 Интегрированная модель хранения и обработки информации.

Основные задачи:

— настройка параметров модели;

— оценка эффективности решения, сбор статистики и подготовка результатов.

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

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

• рамках продукта ЗОСКАТ 5.0, созданного при непосредственном участии автора диссертации.

Научная новизна. В работе осуществлено решение научной проблемы создания эффективных методов обработки и компактного хранения словарной информации.

В процессе исследований и разработок получены новые научные результаты, а именно:

— вероятностная модель словарных данных;

— алгоритмическое решение задачи высокоэффективной компрессии словарной информации (до 1,4 бит на символ);

— решение задачи быстрого случайного доступа к элементам словаря;

— бинарная и логическая структура данных СКСИ;

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

По результатам проведенных исследований (при внедрении работы) разработана многоплатформенная словарная система БОСЯЛТ 5.0 для КПК. Полученные файлы размером около 1,5 МБ позволяют одновременно использовать в зависимости от объема памяти КПК от 3 до 7−10 различных.

• словарей.

Реализация и внедрение результатов исследования. Предложенный алгоритм сжатия реализован автором в универсальной библиотеке ядра словаря, позволяющей компилировать словари из текстового формата обмена 7 во внутренний бинарный формат, а также работать со словарем в бинарном формате (поиск слов, получение статей). Клиентское исполнение библиотеки (без механизма сжатия) реализовано для следующих платформ: Windows СЕ (НРС2000, Pocket PC 2000, Pocket PC 2002), Windows 95/98/Me/NT/2000 (Win32), Palm OS (Начиная с версии 3.5). Библиотека ядра словаря распространяется в составе продукта SOCRAT Dictionary компании «Арсеналъ». Большинство полученных в работе результатов доведено до уровня инженерных методов, алгоритмов и ПО. Практическое использование результатов подтверждено актами о внедрении. Все работы по реализации и внедрению проводились под руководством и при непосредственном участии автора как руководителя и ответственного исполнителя. Официальный сайт ПО SOCRAT Dictionary в Интернет: http://www.arssoft.com/promopage/promo.htm.

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

— анализ состояния проблемы и необходимость создания системы компрессии словарных данных:

— формализация вероятностной модели словарных данных;

— сложная контекстно-ограниченная модель словарных данных;

— универсальный алгоритм поиска по словарю и доступа к произвольным элементам за конечное время;

— алгоритм сжатия словарных данных с качеством порядка 1,4 бит/символ;

— методика параметризации интегрированной модели- 8.

— способы повышения эффективности сжатия словарных данных;

— внедрение СКСИ в результате создания многоплатформенного ПО.

• SOCRAT Dictionary.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на следующих научных конференциях:

— 8-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов (Москва, МИЭТ, 2001).

— 9-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов (Москва, МИЭТ, 2002).

— Международной научно-технической конференции «Приборостроение -2001» (Черкассы., ЧИТИ, 2001).

— 9-й Всероссийской международной научно-технической конференции студентов и аспирантов (Москва, МЭИ, 2002).

Публикации. По материалам диссертации опубликовано 8 работ.

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

Структура и объем работы. Диссертационная работа изложена на 141.

• страницах машинописного текста, иллюстрирована 26 рисунками и 5 таблицами. Она состоит из введения, четырех глав, заключения, списка литературы из 73 наименований и четырех приложений.

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

Вторая глава посвящена обзору методов поиска слов в словаре.

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

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

Акт внедрения результатов работы приведен в приложении.

Выводы по главе.

В Главе 4 были получены следующие результаты.

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

— на медленных устройствах с частой процессора ниже 200 МГц;

— на устройствах с ограниченной памятью доступной устанавливаемым программам.

2 Кроме того, было предложено.

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

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

Заключение

.

В работе осуществлено решение научной проблемы создания # эффективных методов обработки и компактного хранения словарной информации.

В процессе исследований и разработок получены новые научные данные, а именно:

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

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

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

4. В результате анализа методов поиска было показано, что Б-дерево, является гибким, эффективным средством решения задач поиска во внешней памяти. Предложенные модификации Б-дерева (Б'-дерево), позволяют эффективно организовать последовательный доступ к данным в то время, как сохраняются все полезные свойства его предшественника: логарифмические функции поиска, добавления, удаления элементов, что, в свою очередь, решает задачу быстрого случайного доступа к элементам словаря .

5. Предложена интегрированная вероятностная модель словарных данных, применение которой в сочетании с арифметическим кодированием позволяет добиваться высоких степеней сжатия и производительной работы СКСИ.

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

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

8. Предложена модульная архитектура библиотеки ядра СКСИ, реализованная в виде многоплатформенной объектно-ориентированной библиотеки компрессии словарной информации на языке С++.

9. Предложена методика параметризации интегрированной вероятностной модели СКСИ, на основе которой выработан механизм оптимального выбора параметров для компрессии данных, полученные файлы имеют размер около 1,5 МБ, что позволяет одновременно использовать в зависимости от размера памяти КПК от 3 до 10 различных словарей.. Предложенные методы и алгоритмы обработки и хранения словарной информации позволяют создавать высокопроизводительное ПО для словарей, справочных систем и решения других задач хранения и отображения связанных данных и успешно внедрены в программные продукты SOCRAT Dictionary 5.0 for Pocket PC и SOCRAT Dictionary 5.1 for Palm, что позволило увеличить количество продаж через Интернет в 6 раз.

Показать весь текст

Список литературы

  1. Р. Мировой рынок КПК. // CNews Analytics • (http://www.cnews.ru/reviews/laptop/part4).
  2. 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).
  3. P.E. Сжатие и поиск информации. — М.: Радио и связь, 1989.
  4. Н. Алгоритмы и структуры данных. — М.: Мир, 1989.
  5. Ф 5. Кнут Д. Е. Искусство программирования для ЭВМ. Т. 1: Основныеалгоритмы. — М.: Мир, 1976.
  6. Д.Е. Искусство программирования для ЭВМ. Т. 2: Получисленные алгоритмы. — М.: Мир, 1977.
  7. Д.Е. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М.: Мир, 1978.
  8. . Язык программирования С++. Специальное издание. -М.: Бином, 2002.
  9. .Я. Сжатие данных методом стопки книг // Проблемы передачи информации. — 1980. — Т. 16, N4. — С. 16−21.
  10. Ю.Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования -СПб: Питер, 2001 368 с.
  11. П.Кадач А. В. Эффективные алгоритмы неискажающего сжатия текстовой информации. Дисс. на соиск. уч. ст. канд. физ-мат наук., Новосибирск, 1997.
  12. П.Л. Реализация поиска в словаре с использованиемстрокового Б-дерева. //Оборонный комплекс — научно-техническому прогрессу России. — 2003. № 4. — с. 29−34.
  13. П.Л. Методологический подход к оптимизации технологического процесса автоматизированного перевода. //Оборонный комплекс — научно-техническому прогрессу России. — 2001.-№ 1.-с. 47−49.
  14. Н.Гагарина Л. Г., Шеломовский П. Л. Некоторые аспекты разработки и тестирования программного обеспечения. //Оборонный комплекс — научно-техническому прогрессу России. 2000. — № 4. — с. 26−28.
  15. Л.Г., Шеломовский П. Л. «Моделирование структуры данных для компрессии текстовой информации» в сб."Информационное управление и телекоммуникационные системы." Межвузовск. сб. М.: МИЭТ, 2002, 232с.- с. 37−41.
  16. П.Л. Система автоматизированного перевода текстов. //Тезисы докладов 8-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов. -М/.МИЭТ, 2001.-c.227.
  17. П.Л. Моделирование для компрессии словарной информации при разработке ядра словаря. //Сборник трудов международной научно-технической конференции «Приборостроение 2001». -Черкассы.:ЧИТИ, 2002. — с.359−361.
  18. П.Л. Методика сжатия структурированной текстовой информации. //Тезисы докладов 9-й Всероссийской международной научно-технической конференции студентов и аспирантов. -М.:МЭИ, 2002. с.296−297.
  19. Simonyi C. Hungarian Notation // Microsoft Developer Network Library, 1999. (http://msdn.microsoft.com/library/enus/dnvsgen/html/hunganotat.asp).
  20. Abrahamson D. An Adaptive Dependency Source Model for Data Compression // Communications of the ACM. January 1989 Volume 32 Number 1, pp. 77−83
  21. Abramson N. Information Theory and Coding. — New York: McGraw-Hill, 1963.
  22. Shannon C.E., Weaver W. The Mathematical Theory of Communication.
  23. Urbana, IL: University of Illinois Press, 1949.
  24. Schwartz E.S., Kallick B. Generating a canonical prefix encoding // Communs. ACM. — 1964. — Vol. 7, N 3. — P. 166−169.
  25. Connell J.B. A Huffman-Shannon-Fano code // Proc. IEEE. — 1973. — Vol. 61, N7. —P. 1046−1047.
  26. Moffat A., Witten I., Neal R. Arithmetic coding revisited // ACM Transactions on Information Systems, Vol. 16, No. 3, July 1998. P. 256−294.
  27. 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.
  28. 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.
  29. Bell T., Witten I., Cleary J. Modeling for Text Compression. // ACM Computing Surveys, Vol. 21, No. 4, December 1989, pp. 557- 591.
  30. Bell T., Cleary J., Witten I. Text Compression. — Englewood Cliffs, NJ: Prentice-Hall, 1990.
  31. Storer J.A. Data Compression: Methods and Theory. Rockville, ML: Computer Science Press, 1988.
  32. Cleary J., Teahan W., Witten I. Unbounded length contexts for PPM // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1995. — P. 52−61.
  33. Cleary J., Witten I. Data compression using adaptive coding and partial string matching // IEEE Trans. Communs. 1984. — Vol. 32, N 4. — p. 396−402.
  34. Bell T.C., Moffat A.M. A note on DMC data compression scheme // Computer J. 1989. — Vol. 32, N 1. — P. 16−20.
  35. Horspool R.N., Cormack G.V. Comments on «A locally adoptive data compression scheme» // Communs. ACM. — 1987. Vol. 16, N 2. — p. 792−794.
  36. Г. Ассоциативное кодирование // Монитор. — 1994. — N8. —С. 10−19.
  37. McMillan В. Two inequalities implied by unique decipherability. //IRE Trans, on Inf. Th. IT 1956 — Vol. 2. — p. 115−116.
  38. Long D., Jia W. Optimal Maximal Prefix Coding and Huffman Coding (http://www.cs.cityu.edu.hk/~dylong/DMS2001 .pdf)
  39. Mehlhorn К. Data structures and algorithms I: Sorting and searching. — Berlin: Springer-Verlag, 1984.
  40. Kirkpatrick D., Reisch S. Upper bounds for sorting integers on random access machines // Theor. Computer Sei. — 1984. — Vol. 28, N 3. — P. 263−276.
  41. Burrows M., Wheeler D.J. A block-sorting lossless data compression algorithm. — Palo Alto, 1994. — (Tech. Rep. / DEC Systems Research Center, N 124).
  42. P.M. — Block sorting text compression — final report. Auckland, 1996. — (Tech. Rep. / Dept. of Сотр. Sei., Auckland Univ., N CS-96−130).
  43. A.A. Введение в теорию кодирования — М.: Наука. Гл. ред. физ.-мат. лит. 1982. 192 с.
  44. Rissanen J., Langdon G. Universal modelling and coding // IEEE Trans. Inform. Theoiy. 1981. — Vol. 27, N 1. — P. 12−23.
  45. Huffman D.A. A method for the construction of minimum-redundancy• codes//Proc. IRE.-1952.-Vol. 40.-P. 1098−1101.
  46. Vitter J.S. Design and analisys of dynamic Huffman algorithm // J. ACM. 1987. — Vol. 34, N 4. — P. 825−845.
  47. Golomb S.W. Run-length encodings // IEEE Trans. Inform. Theoiy. — 1966. — Vol. 12, N 3. — P. 399−401.
  48. 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.
  49. Golomb S.W. Run-length encodings // IEEE Trans. Inform. Theory. — 1966. — Vol. 12, N 3. — P. 399−401.
  50. Teuhola J., Raita T. Text Compression Using Prediction // Сборниктрудов конференции RDIR'86, pp. 97−101.
  51. 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).
  52. Lempel A., Ziv J. On the complexity of finite sequences // IEEE Trans. Inform. Theoiy. — 1976. — Vol. 22, N 1. — P. 75−81.
  53. 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
  54. Farach M., Muthukrishnan S. Proc. SPAA'95 Santa Barbara CA USA, pp. 244−253.
  55. 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.
  56. 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.
  57. 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
  58. 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.
  59. Manzini G. An analysis of the Burrows-Wheeler Transform (Extended Abstract)
  60. Jones D. Applicatioin of Splay Trees to Data Compression // Communications of the ACM August 1988 Volume 3 1 Number 8, pp. 996−1007
  61. Comer D. The Ubiquitous B-Tree //ACM Computing Surveys, Vol 11, No 2, June 1979.
  62. Vittert J. External Memory Algorithms. // Сборник трудов конференции PODS'98, Seattle, WA, USA, pp. 119−128.
  63. 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.
  64. Farach M., Muthukrishnan S. Optimal Parallel Dictionary Matching and Compression //Сборник трудов конференции SPAA'95 Santa Barbara CA USA, pp. 244−253.
  65. Martinez C., Roura S. Randomized Binary Search Trees, //Journal of the ACM, Vol. 45, No. 2, March 1998, pp. 288 -323.
  66. Ferragina P., Grossi R. Fast String Searching in Secondary Storage: Theoretical Developments and Experimental Results.
  67. Crochemore M., Lecroq T. Pattern-Matching and Text-Compression Algorithms. //ACM Computing Surveys, Vol. 28, No. 1, March 1996, pp. 39−41.
  68. Larson P. Dynamic Hash Tables. //Communications of the ACM April 1988 Volume 31 Number 4, pp. 446−457.
  69. M. Thorup M., //String Matching in Lempel-Ziv Compressed Strings. Сборник трудов конференции STOC'95, Las Vegas, Nevada, USA, pp. 703−712.
  70. 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
  71. Extensible Markup Language (XML) 1.0 (Second Edition) // W3C Recommendation 6 October 2000 (http://www.w3.org/TR/REC-xml)
  72. The Unicode Standard, Version 4.0http://www.unicode.Org/versionsAJnicode4.0.0/bookmarks.html)
Заполнить форму текущей работой