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

Введение.

Глава 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. Fenwick 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. 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).

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. 366375.

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. Farach 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-18971. "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)