Алгоритмы, структуры данных

       

ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ.


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

Сейчас лучшие схемы достигают сжатия в 2.3 - 2.5 битов/символ для английского текста. Показатель иногда может быть немного улучшен за счет использования больших объемов памяти, но сообщений о преодолении рубежа в 2 бита/символ еще не было. Обычные люди достигали результата в 1.3 бита/символ при предсказании символов в английском тексте [21]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или системы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуpовневой связности. Однако, необходимо иметь в виду, что очень большое количество слов обычного английского текста в обычном английском словаpе может быть не найдено. Например, Уолкер и Эмслер[107] проверили 8 миллионов слов из New York Times News Service для Webster's Seventh New Collegiate Dictionary[65] и обнаружили, что в словаpе отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них - грамматические формы слов, еще 1/4 - собственные существительные, 1/6 - слова, написанные через дефис, 1/12 - напечатаны с орфографическими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содеpжат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в рассчете на лингвистическую информацию более высокого уровня, будут несомненно зависеть от системной сферы.
Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование. Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей состояний; показанный метод DMC - лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в частично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний. Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут несомненно продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными путями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска.


В общем, увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов. Последняя область на будущее - это разработка и реализация новых систем, включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных пpогpамм pазных областей применения, включая текст-процессор MaxWrite(7)[117], цифровой факсимильный аппаpат [42], сетевую почту и новости (например, UNIX "net-news") и архивацию файлов (например, программы ARC и PKARC для IBM PC(8), которые часто применяются для pаспpеделяемого ПО из электронных бюллютеней). Для увеличения скорости и сокращения стоимости большинство этих систем используют удивительно простые методы сжатия. Все они представляют собой потенциальные сферы применения для более сложных методов моделирования. Люди часто размышляют над объединением адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные системные проблемы, частично в сглаживании взрывного характера вывода большинства алгоритмов сжатия, но в основном в согласовывании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие имеет значительные преимущества для конечного движения - некоторые высокоскоростные модемы (например, Racal-Vadic's Scotsman) и конечные эмуляторы (например, [3]) уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования определенно будут давать преимущество в скорости реализации. Еще одной сферой применения является шифрование и защита данных [113]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретности. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредством удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистичекий порядок.


В-третьих, что самое важное, модель действует как очень большой ключ, без которого расшифровка невозможна. Применение адаптивной модели означает, что ключ зависит от всего текста, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, опpеделяющий модель для дальнейшего pаскодиpования[47]. Сжатие текстов является настолько же нужной областью исследований как и 40 лет назад, когда ресурсы ЭВМ были скудны. Его пpименение продолжает изменяться вместе с улучшением технологии, постоянно увеличивая выигрыш за счет машинного времени, скорости передачи данных, первичного и вторичного хранения. (1) - Везде в этой статье основание логарифма есть 2, а единица информации - бит.
(2) - Вероятность может быть менее 100% в случае иностранных слов, таких как "Coq au vin" или "Iraq.".
(3) - Понятие введено Моффатом в [69] для техники, использованной в [16].
(4) - Эта перемена инициалов в аббревиатуре является увековеченной нами исторической ошибкой.
(5) - UNIX - торговая марка AT&T Bell Laboratories.
(6) - На самом деле это дерево Patricia [51,71].
(7) - MacWrite - зарегестрированная торговая марка Apple Computer,Inc.
(8) - IBM - зарегестрированная торговая марка International Business Machines.



ADSM = adaptive dependency source model.
Arithmetic coding - арифметическое кодирование.
Bits per character (bit/char) - биты на символ - единица измерения степени сжатия.
Blending strategy - смешанная стратегия.
Code space - кодовое пространство.
Compression ratio - характеристика степени сжатия.
Conditioning classes - классы условий.
Cross-product - перекрестное умножение.
Cumulative probability - накапливаемая вероятность.
DAFC = A doubly-adaptive file compression algorithm.
Dictionary coding - словарное кодирование.
Digram coding - кодирование диадами.
Entropy - энтропия.
Escape probability - вероятность ухода.
File - файл, обозначение сжимаемых данных.
Finite-context modeling - контекстно-ограниченное моделирование.
Finite-context probabilistic model - вероятностные модели с конечным числом состояний.
FSM = finite-state machine - конечный автомат.
Greedy parsing - тщательный разбор.
Hyphenated words - слова, разделенные дефисом.
Input - ввод, обозначение сжимаемых данных.
Lazy exclusion - ленивое исключение.
Lookahead buffer - упpеждающий (пpосмотpенный) впеpед буфер.
LFF = Longest Fragment First - метод помещения в начало самого длинного фрагмента.
Noiseless compression - сжатие без помех (обpатимое).
Order-o fixed-context model - контекстно-зависимая модель степени o.
Parsing - разбор текста на фразы.
PPMA = prediction by partial match, method A.
Proper nouns - имена собственные.
Recency models - модели новизны.
Run-length coding - кодиpование длин тиpажей.
Skew count - ассиметричный счет.
Source - источник, производящий (содержащий) данные для сжатия.
Source coding - синоним процесса сжатия.
Statistical coding - статистическое кодирование.
String - строка, обозначение сжимаемых данных.
Text - текст, обозначение сжимаемых данных.
Trie = digital search tree - дерево цифрового поиска.
Update exclusion - обновляемое исключение.
Vowel-consonant pairs - пары "гласная-согласная".
Zero frequency problem - проблема нулевой частоты.
Ziv-Lempel compression - сжатие Зива-Лемпела.
<


References

  • Abramson D.M. 1989. An adaptive dependency source model for data compression. Commun.ACM 32,1(Jan.),77-83.
  • Angluin D.,and Smith C.H. 1983. Inductive inference:Theory and methods. Comput.Surv. 15, 3(Sept.),237-269.
  • Auslander M., Harrison W., Miller V., and Wegman M. 1985. PCTERM: A terminal emulator using compression. In Proceedings of the IEEE Globecom'85. IEEE Press, pp.860-862.
  • Baum L.E., Petrie T.,Soules G. and Weiss N. 1970. A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Stat.41, 164-171.
  • Bell T.C. 1986. Better OPM/L test compression. IEEE Trans. Commun. COM-34. 12(Dec.),1176-1182.
  • Bell T.C. 1987. A unifying theory and improvements for existing approaches to text compression. Ph.D. dissertation, Dept. of Computer Science, Univ. of Canterbury, New Zealand.
  • Bell T.C. 1989. Longest match string searching for Ziv-Lempel compression. Res. Rept.6/89, Dept. of Computer Science, Univ. of Canterbury, New Zealand.
  • Bell T.C. and Moffat A.M. 1989. A note on the DMC data compression scheme. Computer J. 32,1(Feb.), 16-20.
  • Bell T.C. and Witten I.H. 1987. Greedy macro text compression. Res. Rept.87/285/33. Department of Computers Science, University of Calgary.
  • Bentley J.L.,Sleator D.D., Tarjan R.E. and Wei V.K. 1986. A locally adaptive data compression scheme. Commun. 29, 4(Apr.), 320-330. Shows how recency effectscan be incorporated explicitly into a text compression system.
  • Bookstein A. and Fouty G. 1976. A mathematical model for estimating the effectivness of bigram coding. Inf. Process. Manage.12.
  • Brent R.P. 1987. A linear algorithm for data compression. Aust. Comput. J. 19,2,64-68.
  • Cameron R.D. 1986. Source encoding using syntactic information source model. LCCR Tech. Rept. 86-7, Simon Fraser University.
  • Cleary J.G. 1980. An associative and impressible computer. Ph.D. dissertation. Univ. of Canterbury, Christchurch, New Zealand.
  • Cleary J.G. and Witten I.H. 1984a. A comparison of enumerative and adaptive codes.


    IEEE Trans. Inf. Theory, IT-30, 2(Mar.),306-315. Demonstrates under quite general conditions that adaptive coding outperforms the method of calculating and transmitting an exact model of the message first.
  • Cleary J.G. and Witten I.H. 1984b. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr.),396-402. Presents an adaptive modeling method that reduces a large sample of mixed-case English text to around 2.2 bits/character when arithmetically coded.
  • Cooper D. and Lynch M.F. 1982. Text compression using variable-to-fixed-length encoding. J. Am. Soc. Inf. Sci. (Jan.), 18-31.
  • Cormack G.V. and Horspool R.N. 1984. Algorithms for adaptive Huffman codes. Inf.Process.Lett. 18,3(Mar.), 159-166. Describes how adaptive Huffman coding can be implemented efficiently.
  • Cormack G.V. and Horspool R.N. 1987. Data compression using dynamic Markov modelling. Comput. J. 30,6(Dec.), 541-550. Presents an adaptive state-modelling technique that, in conjunction with arithmetic coding, produces results competitive with those of[18].
  • Cortesi D. 1982. An effective text-compression algorithm. Byte 7,1(Jan.),397-403.
  • Cover T.M. and King R.C. 1978. A convergent dambling estimate of the entropy of English. IEEE Trans. Inf. Theory IT-24, 4(Jul.),413-421.
  • Darragh J.J., Witten I.H. and Cleary J.G. 1983. Adaptive text compression to enhance a modem. Res.Rept.83/132/21.Computer Science Dept.,Univ.of Calgary.
  • Elias P. 1975. Universal codeword sets and representations of the integers. IEEE Trans.Inf.Theory IT-21,2(Mar.),194-203.
  • Elias P. 1987. Interval and recency rank source coding: Two on-line adaptive variable-length schemes. IEEE Trans.Inf.Theory IT-33, 1(Jan.),3-10.
  • El Gamal A.A., Hemachandra L.A., Shperling I. and Wei V.K. 1987. Using simulated annealing to design good codes. IEEE Trans.Inf.Theory,IT-33,1,116-123.
  • Evans T.G. 1971. Grammatical inference techniques in pattern analysis. In Software Engineering, J. Tou. Ed.Academic Press, New York, pp.183-202.
  • Faller N. 1973.


    An adaptive system for data compression. Record of the 7th Asilomar Conference on Circuits, Systems and Computers. Naval Postgraduate School, Monterey, CA, pp.593-597.
  • Fiala E.R. and Greene D.H. 1989. Data compression with finite windows. Commun.ACM 32,4(Apr.),490-505.
  • Flajolet P. 1985. Approximate counting: A detailed analysis. Bit 25,113-134.
  • Gaines B.R. 1976. Behavior/structure transformations under uncertainty. Int.J.Man-Mach.Stud. 8, 337-365.
  • Gaines B.R. 1977. System identification, approximation and complexity. Int.J.General Syst. 3,145-174.
  • Gallager R.G. 1978. Variations on a theme by Huffman. IEEE Trans.Inf.Theory IT-24, 6(Nov.),668-674. Presents an adaptive Huffman coding algorithm, and derives new bound on the redundancy of Huffman codes.
  • Gold E.M. 1978. On the complexity of automation identification from given data. Inf.Control 37,302-320.
  • Gonzalez-Smith M.E. and Storer J.A. 1985. Parralel algorithms for data compression. J.ACM 32,2,344-373.
  • Gottlieb D., Hagerth S.A., Lehot P.G.H. and Rabinowitz H.S. 1975. A classification of compression methods and their usefulness for a large data processing center. National Comput.Conf. 44. 453-458.
  • Guazzo M. 1980. A general minimum-redundancy source-coding algorithm. IEEE Trans.Inf.Theory IT-26, 1(Jan.),15-25.
  • Held G. 1983. Data Compression: Techniques and Application, Hardware and Software Considerations. Willey, New York. Explains a number of ad hoc techniques for compressing text.
  • Helman D.R. and Langdon G.G. 1988. Data compression. IEEE Potentials (Feb.),25-28.
  • Horspool R.N. and Cormack G.V. (1983). Data compression based on token recognition. Unbublished.
  • Horspool R.N. and Cormack G.V. 1986. Dynamic Markov modelling - A prediction technique. In Proceedings of the International Conference on the System Sciences, Honolulu, HI,pp.700-707.
  • Huffman D.A. 1952. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40,9(Sept.),pp.1098-1101. The classic paper in which Huffman introduced his famous coding method.
  • Hunter R.


    and Robinson A.H. 1980. International digital facsimile coding standarts. In Proceedings of the Institute of Electrical and Electronic Engineers 68,7(Jul.),pp.854-867. Describes the use of Huffman coding to compress run lengths in black/white images.
  • Jagger D. 1989. Fast Ziv-Lempel decoding using RISC architecture. Res.Rept.,Dept.of Computer Science, Univ.of Canterbury, New Zealand.
  • Jakobsson M. 1985. Compression of character string by an adaptive dictionary. BIT 25, 4, 593-603.
  • Jamison D. and Jamison K. 1968. A note on the entropy of partial-known languages. Inf.Control 12, 164-167.
  • Jewell G.C. 1976. Text compaction for information retrieval systems. IEEE Syst., Man and Cybernetics Soc.Newsletter 5,47.
  • Jones D.W. 1988. Application of splay trees to data compression. Commun.ACM 31,8(Aug.),996-1007.
  • Katajainen J. and Raita T. 1987a. An appraximation algorithm for space-optimal encoding of a text. Res.Rept.,Dept.of Computer Science, Univ. of Turku, Turku, Finland.
  • Katajainen J. and Raita T. 1987b. An analysis of the longest match and the greedy heuristics for text encoding. Res.Rept.,Dept.of Computer Science, Univ. of Turku, Turku, Finland.
  • Katajainen J., Renttonen M. and Teuhola J. 1986. Syntax-directed compression of program files. Software-Practice and Experience 16,3,269-276.
  • Knuth D.E. 1973. The Art of Computer Programming. Vol.2, Sorting and Searching. Addison-Wesley, Reading,MA.
  • Knuth D.E. 1985. Dynamic Huffman coding. J.Algorithms 6,163-180.
  • Langdon G.G. 1983. A note on the Ziv-Lempel model dor compressing individual sequences. IEEE Trans.Inf.Theory IT-29, 2(Mar.),284-287.
  • Langdon G.G. 1984. An introduction to arithmetic coding. IBM J.Res.Dev. 28,2(Mar.),135-149. Introduction to arithmetic coding from the point of view of hardware implementation.
  • Langdon G.G. and Rissanen J.J. 1981. Compression of black-white images with arithmetic coding. IEEE Trans.Commun.COM-29, 6(Jun.),858-867. Uses a modeling method specially tailored to black/white pictures, in conjunction with arithmetic coding, to achieve excellent compression results.
  • Langdon G.G.


    and Rissanen J.J. 1982. A simple general binary source code. IEEE Trans.Inf.Theory IT-28 (Sept.),800-803.
  • Langdon G.G. and Rissanen J.J. 1983. A doubly-adaptive file compression algorithms. IEEE Trans.Commun. COM-31, 11(Nov.),1253-1255.
  • Lelewer D.A. and Hirschberg D.S. 1987. Data compression. Comput.Surv. 13,3(Sept.),261-296.
  • Lempel A. and Ziv J.1976. On the complexity of finite sequences. IEEE Trans.Inf.Theory IT-22,1(Jan.),75-81.
  • Levinson S.E., Rabiner L.R. and Sondni M. 1983. An introduction to the application of the theory of probabilistic function of a Markov process to automatic speech recognition. Bell Syst.Tech.J. 62,4(Apr.),1035-1074.
  • Llewellyn J.A. 1987. Data compression for a source with Markov characteristics. Comput.J. 30,2,149-156.
  • Lynch M.F. 1973. Compression of bibliographic files using an adaption of run-length coding. Inf.Storage Retrieval 9,207-214.
  • Lynch T.J. 1985. Data Compression - Techniques and Application. Lifetime Learning Publications, Belmont, CA.
  • Mayne A. and James E.B. 1975. Information compression by factorizing common strings. Comput.J.18,2,157-160.
  • G. & C. Merriam Company 1963. Webster's Seventh New Collegiate Dictionary. Springfield, MA.
  • Miller V.S. and Wegman M.N. 1984. Variations on a theme by Ziv and Lempel. In Combinatorial Algorithms on Words.A.Apostolico and Z.Galil, Eds.NATO ASI Series, Vol.F12.Springer-Verlag,Berlin,pp.131-140
  • Moffat A. 1987. Word based text compression. Res.Rept.,Dept.of Computer Science, Univ.of Melbourne,Victoria,Australia.
  • Moffat A. 1988a. A data structure for arithmetic encoding on large alphabets. In Proceeding of the 11th Australian Computer Science Conference. Brisbane,Australia(Feb.),pp.309-317.
  • Moffat A. 1988b. A note on the PPM data compression algorithm. Res.Rept.88/7,Dept.of Computer Science, Univ.of Melbourne, Victoria,Australia.
  • Morris R. 1978. Counting large numbers of events in small registers. Commun.ACM 21,10(Oct.),840-842.
  • Morrison D.R. 1968. PATRICIA - Practical Algorithm To Retvieve Information Coded In Alphanume- ric. J.


    ACM 15,514-534.
  • Ozeki K. 1974a. Optimal encoding of linguistic information. Systems, Computers, Controls 5, 3, 96-103. Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D,No.6,June 1974, pp.361-368.
  • Ozeki K. 1974b. Stochastic context-free grammar and Markov chain. Systems, Computers, Controls 5, 3, 104-110. Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D,No.6,June 1974, pp.369-375.
  • Ozeki K. 1975. Encoding of linguistic information generated by a Markov chain which is associated with a stochastic context-free grammar. Systems, Computers, Controls 6, 3, 75-78. Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.58-D,No.6,June 1975, pp.322-327.
  • Pasco R. 1976. Source coding algorithms for fast data compression. Ph.D. dissertation.Dept.of Electrical Engineering, Stanford Univ. An early exposition of the idea of arithmetic coding, but lacking the idea of incremental operation.
  • Pike J. 1981. Text compression using a 4 bit coding system. Comput.J.24,4.
  • Rabiner L.R. and Juang B.H. 1986. An Introduction to Hidden Markov models. IEEE ASSP Mag.(Jan.).
  • Raita T. and Teuhola J.(1987). Predictive text compression by hashing. ACM Conference on Information Retrieval,New Orleans.
  • Rissanen J.J. 1976. Generalized Kraft inequality and arithmetic coding. IBM J.Res.Dev.20,(May.),198-203. Another early exposition of the idea of arithmetic coding.
  • Rissanen J.J. 1979. Arithmetic codings as number representations. Acta Polytechnic Scandinavica, Math 31(Dec.),44-51. Further develops arithmetic coding as a practical technique for data representation.
  • Rissanen J.J. 1983. A universal data compression system. IEEE Trans.Inf.Theory IT-29,5(Sept.),656-664.
  • Rissanen J.J. and Langdon G.G. 1979. Arithmetic coding. IBM J.Res.Dev.23,2(Mar.),149-162. Describes a broad class of arithmetic codes.
  • Rissanen J.J. and Langdon G.G. 1981. Universal modeling and coding. IEEE Trans.Inf.Theory IT-27,1(Jan.),12-23. Shows how data compresion can be separated into modeling for prediction and coding with respect to a model.
  • Roberts M.G. 1982.


    Local order estimating Markovian analysis for noiseless source coding and authorship identification. Ph.D.dissertation.Stanford Univ.
  • Roden M., Pratt V.R. and Even S. 1981. Linear algorithm for data compression via string matching. J.ACM 28,1(Jan.),16-24.
  • Rubin F. 1976. Experiments in text file compression. Commun.ACM 19,11,617-623. One of the first papers to present all the essential elements of practical arithmetic coding, including fixed-point computation and incremental operation.
  • Rubin F. 1979. Arithmetic stream coding using fixed precision registers. IEEE Trans.Inf.Theory IT-25,6(Nov.),672-675.
  • Ryabko B.Y. 1980. Data compression by means of a "book stack". Problemy Peredachi Informatsii 16,4.
  • Schieber W.D. and Thomas G.W. 1971. An algorithm for compaction of alphanumeric data. J.Library Automation 4,198-206.
  • Schuegraf E.J. and Heaps H.S. 1973. Selection of equifrequent word fragments for information retrieval. Inf.Storage Retrieval 9,697-711.
  • Schuegraf E.J. and Heaps H.S. 1974. A comparison of algorithms for data-base compression by use of fragments as language elements. Inf.Storage Retrieval 10,309-319.
  • Shannon C.E. 1948. A mathematical theory of communication. Bell Syst.Tech.J.27(Jul.),398-403.
  • Shannon C.E. 1951. Prediction and entropy of printed English. Bell Syst.Tech.J.(Jan.),50-64.
  • Snyderman M. and Hunt B. 1970. The myriad virtues of text compaction. Datamation 1(Dec.),36-40.
  • Storer J.A. 1977. NP-completeness results concerning data compression. Tech.Rept.234.Dept.of Electrical Engineering and Computer Science, Princeton Univ.,Princeton,NJ.
  • Storer J.A. 1988. Data Compression: Methods and Theory. Computer Science Press, Rockville,MD.
  • Storer J.A. and Szymanski T.G. 1982. Data compression via textual substitution. J.ACM 29,4(Oct.),928-951.
  • Svanks M.I. 1975. Optimizing the storage of alphanumeric data. Can.Datasyst.(May),38-40.
  • Tan C.P. 1981. On the entropy of the Malay language. IEEE Trans.Inf.Theory IT-27,3(May),383-384.
  • Thomas S.W., McKie J., Davies S., Turkowski K., Woods J.A.


    and Orost J.W. 1985. Compress (Version 4.0) program and documentation. Available from joe@petsd.UUCP.
  • Tischer P. 1987. A modified Lempel-Ziv-Welch data compression scheme. Aust.Comp.Sci.Commun. 9,1,262-272.
  • Todd S., Langdon G.G. and Rissanen J. 1985. Parameter reduction and context selection for compression of gray-scale images. IBM J.Res.Dev.29,2(Mar.),188-193.
  • Tropper R. 1982. Binary-coded text, a compression method. Byte 7,4(Apr.),398-413.
  • Vitter J.S. 1987. Design and analysis of dynamic Huffman codes. J.ACM 34,4(Oct.),825-845.
  • Vitter J.S. 1989. Dynamic Huffman coding. ACM Trans.Math.Softw. 15,2(Jun.),158-167.
  • Wagner R.A. 1973. Common phrase and minimum-space text storage. Commun.ACM 16,3, 148-152.
  • Walker D.E. and Amsler R.A. 1986. The use of machine-readable dictionaries in sublanguage analysis. In Analysis languages in restricted domains: Sublanguage description and processing, R.Grishman and R.Kittridge, Eds.Lawrence Erlbaum Associates,Hillsdale, NJ, pp.69-83.
  • Welch T.A. 1984. A technique for high-performance data compression. IEEE Computer 17,6(Jun.),8-19. A very fast coding technique based on the method of [119], but those compression performance is poor by the standarts of a [16] and [19]. An improved implementation of this method is widely used in UNIX systems under the name "compress".
  • White H.E. 1967. Printed English compression by dictionary encoding. In Proceedings of the Institute of Electrical and Electronics Engineering 55, 3,390-396.
  • Williams R. 1988. Dynamics-history predictive compression. Inf.Syst. 13,1,129-140.
  • Witten I.H. 1979. Approximate, non-deterministic modelling of behavior sequences. Int.J.General Systems 5(Jan.),1-12.
  • Witten I.H. 1980. Probabilistic behavior/structure transformations using transitive Moore models. Int.J.General Syst.6,3,129-137.
  • Witten I.H. and Cleary J. 1983. Picture coding and transmission using adaptive modelling of quad trees. In Proceeding of the International Elecrical, Electronics conference 1,Toronto,ON,pp.222-225.
  • Witten I.H.
  • Witten I.H., Neal R.


    and Cleary J.G. 1987. Arithmetic coding for data compression. Commun.ACM 30,6(Jun.),520-540.
  • Wolff J.G. 1978. Recording of natural language for economy of transmission or storage. Comput.J. 21,1,42-44.
  • Young D.M. 1985. MacWrite file formats. Wheels for the mind (Newsletter of the Australian Apple University Consortium), University of Western Australia, Nedlands, WA 6009, Australia, p.34
  • Ziv J. and Lempel A. 1977. A universal algorithms for sequental data compression. IEEE Trans.Inf.Theory IT-23,3,3(May),337-343.
  • Ziv J. and Lempel A. 1978. Compression of individual sequences via variable-rate coding. IEEE Trans.Inf.Theory IT-24,5(Sept.),530-536. Describes a method of text compression that works by replacing a substring with a pointer to an earlier occurrence of the same substring. Although it performs quite well, it does not provide a clear separation between modeling and coding.

    About the authors...

    Tim Bell reseived a B.Sc. (First Class Honours) and Ph.D. from the University of Canterbury, New Zealand. In 1987 he held a post-doctoral fellowship at the Knowledge Sciences Institute, University of Calgary, Canada. He currently teaches at the University of Canterbury. His interests include text compression, algorithms, and the use of computers for music performance, composition, and printing. Ian H. Witten is Professor of Computer Science at the University of Calgary, Canada. In the past he has worked on numerous aspects of man-machine systems, particularly speech synthesis and documentation graphics. His current research interests include prediction and modeling, machine learning, and office information systems. He has published around 80 papers and three books: Communication with Microcomputers (Academic Press,1980), Principles of Computer Speech (Academic Press,1982), and Talking with Computer (Prentice Hall,1986). John G.Cleary is Associate Professor of Computer Science at the University of Calgary, Canada. He received his Ph.D. in electrical engineering from the University of Canterbury, New Zealand.


    Prior to moving to Canada in 1982 he spent six years working on commercial software systems. His current research include adaptive systems, parralel algorithms and hardware particularly for high quality graphics, logic programming and its application to distributed simulation using virtual time techniques. Drs. Bell, Cleary, and Witten have recently collaborated on a book entitled Text Compression (Prentice Hall, in press).

    TIMOTHY BELL Department of Computer Science, University of Canterbury, Christchurch, New Zealand IAN H. WITTEN Department of Computer Science, University of Calgary, Calgary, Alberta, Canada T2N 1N4 JOHN G. CLEARY Department of Computer Science, University of Calgary, Calgary, Alberta, Canada T2N 1N4 MODELING FOR TEXT COMPRESSION ACM Computing Surveys. Vol.21, No.4( Dec.1989 ), pp.557-591. CATEGORIES AND SUBJECT DESCRIPTORS: Data compaction and compression, information theory. GENERAL TERMS: Algorithms, Experimentation, Mearsurement. ADDITIONAL KEY WORDS AND PHRASES: Adaptive modeling, arithmetic coding, context modeling, natural language, state modeling, Ziv-Lempel compression.



    Содержание раздела