СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ СООБЩЕНИЙ В СИСТЕМАХ ОБРАБОТКИ, ПЕРЕДАЧИ И ХРАНЕНИЯ ТЕКСТОВОЙ ИНФОРМАЦИИ Российский патент 2011 года по МПК G06F17/22 G06F17/30 G11C29/40 

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

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

Известно, что по статистике текстовых сообщений примерно 250 общеупотребительных слов составляют существенную долю всех слов (примерно 80-90%), которые используются при общении между людьми в повседневной жизни. В этом случае объем постоянного словаря будет составлять всего 250 слов, что требует для перечисления всего восьмиразрядного двоичного нумерующего кода (одного байта или символа), который однозначно идентифицирует или определяет каждое слово в постоянном словаре. Поскольку слово средней длины состоит примерно из 5 символов (букв), то коэффициент сжатия даже при использовании только постоянного словаря будет примерно равен 4-5. Для сравнения, средний коэффициент сжатия при использовании статистических методов сжатия Фано-Шеннона, Хаффмена или арифметического кодирования для текстовой информации примерно равен 3-4.

Если исходный текст относится не к общей лексике, а к какой-либо области знаний: медицине, информатике, экономике, архитектуре и так далее, постоянный словарь составляют из наиболее употребительных слов этой области знания, и коэффициент сжатия может быть еще более увеличен. Слова из постоянного словаря могут иметь разную частоту повторения в исходном тексте, поэтому коэффициент сжатия может быть дополнительно повышен за счет применения методов статистического кодирования как слов сжатой текстовой информации, так и нумерующих кодов постоянного словаря. Дальнейшее повышение коэффициента сжатия возможно также при использовании временного словаря редких слов, отсутствующих в постоянном словаре. Временный словарь формируют аналогично формированию словаря в известных словарных методах сжатия Лемпела и Зива [Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. М.: Диалог МИФИ, 2002].

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

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

Известен способ сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации, заключающийся в том, что при сжатии текстовой информации сначала в исходной текстовой информации выделяют слово, и нумерующий код, идентифицирующий это слово в словаре, записывают в массив сжатой текстовой информации. При восстановлении исходной текстовой информации по нумерующему коду, записанному в массив сжатой информации, определяют слово в словаре, которое помещают в массив восстановленной информации [Новик Д.А. Эффективное кодирование. М.: Энергия, 1965, стр.39].

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

Наиболее близким к предлагаемому способу является способ (прототип) сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации, заключающийся в том, что при сжатии текстовой информации сначала в исходной текстовой информации выделяют слово, далее определяют наличие или отсутствие этого слова во временном словаре, при наличии выделенного слова во временном словаре нумерующий код, определяющий слово во временном словаре, помещают в массив сжатой текстовой информации, при отсутствии выделенного слова во временном словаре выделенное слово помещают во временный словарь и в массив сжатой текстовой информации. При восстановлении текстовой информации, при наличии в массиве сжатой текстовой информации нумерующего кода, определяющего слово во временном словаре, выбирают из временного словаря это слово и помещают его в массив восстановленной текстовой информации, при наличии в массиве сжатой текстовой информации слова исходной текстовой информации это слово помещают в массив восстановленной текстовой информации и во временный словарь [Ситняковская Е.И. Построение эффективных побуквенных кодов для словарных методов сжатия данных. Проблемы передачи информации, 1998, #34, вып.2, стр.47].

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

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

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

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

Сначала заранее формируют постоянный словарь. Постоянный словарь подготавливают заранее перед сжатием текстовой информации. Он заранее известен как при сжатии, так и при восстановлении текстовой информации. Для формирования постоянного словаря используют массивы исходной текстовой информации определенных областей знания, например таких областей знания, как радиотехника, физика, химия, медицина и так далее. Для составления постоянного словаря целесообразно использовать наиболее употребительные по частоте слова данных областей знания. Сначала выбирают массивы исходной текстовой информации, относящиеся к какой-либо области знания. Эти массивы используют для построения постоянного словаря данной области знания. Построение постоянного словаря начинают с выделения слов в массивах исходной текстовой информации. Слово состоит из букв (символов) и имеет определенную длину. Например, в массивах исходной текстовой информации словом может быть последовательность символов, ограниченная спереди и сзади пробелами или знаками препинания. Слова могут иметь переменную длину. Каждое вновь встретившееся в массивах исходной текстовой информации слово помещают в постоянный словарь. Для слов, которые записаны в постоянный словарь, подсчитывают их частоту. Слова в предложениях могут отличаться падежом, склонением и так далее. Поэтому в постоянном словаре можно хранить лишь неизменные части слов, например корни слов. Наиболее употребляемые приставки, суффиксы и окончания слов можно также хранить в постоянном словаре, но отдельно. При этом осуществляют неискажающее сжатие информации без потерь с точным восстановлением слов в предложениях. Возможно также хранить слова в постоянном словаре только в определенном падеже, склонении и т.д. Тогда восстановление исходной информации осуществляют с потерями, т.е. с искажениями приставок, суффиксов и окончаний слов. При этом восприятие смысла многих предложений после восстановления информации может сохраняться. В последнем случае получают более высокий коэффициент сжатия информации. Коррекцию приставок, суффиксов и окончаний слов можно затем проводить отдельно, используя правила орфографии.

После того как все слова исходной текстовой информации размещены в постоянном словаре, выполняют кодирование слов постоянного словаря с помощью равномерного или неравномерного нумерующего кода. Наиболее просто слова в постоянном словаре могут нумероваться равномерным кодированием слов в постоянном словаре. При таком кодировании для записи номера каждого слова в постоянном словаре используют одно и то же число двоичных разрядов нумерующего кода. Можно пользоваться и другими более экономичными, но при этом и более сложными методами кодирования номеров. К числу таких методов относится кодирование с помощью неравномерных разделимых кодов, например, с помощью кода Хаффмена (или других эффективных кодов: Фано-Шеннона, арифметического и так далее), учитывающего частоту использования слов постоянного словаря.

Постоянный словарь будет состоять из слов и соответствующих им равномерных или неравномерных нумерующих кодов. После этого слова в постоянном словаре располагают в лексикографическом порядке (по алфавиту), что упрощает и ускоряет поиск слов в словаре при сжатии информации. Существенное значение при реализации способа имеет объем постоянного словаря. При слишком большом объеме постоянного словаря нумерующий код слова в постоянном словаре будет иметь большое число разрядов, что может уменьшить величину коэффициента сжатия. С другой стороны, при ограничении числа слов в постоянном словаре в исходной информации может оказаться большое число слов, отсутствующих в постоянном словаре, что также может уменьшить величину коэффициента сжатия. Объем постоянного словаря следует ограничивать определенным значением, оставляя только наиболее часто употребляемые слова. Следует выбирать такой объем постоянного словаря, при котором слова постоянного словаря составляют существенную долю слов в исходной текстовой информации (например, >2/3). По статистике 250 общеупотребительных слов составляют существенную долю всех слов, которые используются при общении между людьми в повседневной жизни. В этом случае объем словаря может составлять всего 250 слов, что требует восьмиразрядного равномерного двоичного нумерующего кода (одного байта), который однозначно идентифицирует или определяет каждое слово в постоянном словаре. При использовании неравномерного разделимого статистического кодирования средняя разрядность нумерующего кода уменьшится.

После составления постоянного словаря можно выполнять сжатие исходной текстовой информации. Допустим, что исходная информация представляется в виде последовательности символов х₁х₂х₃,…,x_r. Пусть выделенное слово есть x_qx_q+1,x_q+2,…,x_q+i. Сначала выделенное слово ищут в постоянном словаре. Поскольку слова в постоянном словаре упорядочены в лексикографическом порядке (по алфавиту), то поиск слова целесообразно проводить методом дихотомии (деления области поиска пополам). При этом сначала искомое слово сравнивают со средним словом постоянного словаря. Если искомое слово лексикографически больше этого среднего слова, продолжают поиск в верхней половине постоянного словаря, в противном случае - в нижней половине и так далее. Если такое слово найдено, в массив сжатой информации добавляется нумерующий код, начинающийся с признака постоянного словаря, например с 11. Далее в массив сжатой информации дописывается нумерующий код α_q, идентифицирующий это слово в постоянном словаре. Таким кодом может быть, например, нумерующий код, определяющий положение слова в постоянном словаре.

В том случае, если слово не найдено в постоянном словаре, осуществляют поиск этого слова во временном словаре. При обнаружении слова во временном словаре в массив сжатой информации помещают код признака временного словаря, равный 10, и осуществляют, например, неравномерное разделимое кодирование положения и длины этого слова во временном словаре. Сформированный код β_q также помещают в массив сжатой текстовой информации.

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

Затем выделяется следующее слово в исходной текстовой информации, и вся процедура сжатия исходной текстовой информации повторяется для этого слова. И так продолжается до конца исходной текстовой информации.

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

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

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

Восстановление текстовой информации начинают с анализа очередных двух битов в массиве сжатой текстовой информации. Если эти два бита равны 11, то по нумерующему коду слова α_q, который следует за этими двумя битами, ищут само слово в постоянном словаре. При равномерном кодировании слов в постоянном словаре для этого достаточно по коду слова, как по адресу, выбрать слово из постоянного словаря. При неравномерном кодировании, если слова упорядочены по нумерующему коду, поиск слова в постоянном словаре целесообразно, с целью его ускорения, проводить методом дихотомии. Далее найденное слово помещают в массив восстановленной информации. В случае, если очередные два бита массива сжатой информации равны 10, то ищут слово во временном словаре. Для этого используют код идентификации β_q слова во временном словаре, который следует за этими двумя битами. При этом код идентификации слова состоит из кода номера положения слова в словаре и кода длины этого слова. Выбранное слово помещают в массив восстановленной информации. Если очередные два бита массива сжатой информации равны 00, массив сжатой информации дополняется словом, которое следует за 00, и одновременно это слово записывается во временный словарь, реконструируя его в процессе восстановления текстовой информации.

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

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

В предлагаемом способе сжатие и восстановление информации осуществляется с применением постоянного словаря. При соответствующем выборе постоянного словаря и в зависимости от характера сжимаемой исходной информации коэффициент сжатия информации можно повысить по сравнению с известным способом. Коэффициент сжатия текстов в известном способе статистического сжатия составляет величину, примерно равную 2…2.5. Такие же значения коэффициента сжатия обеспечивают известные архиваторы, использующие словарные методы сжатия ZIP и RAR. При использовании предлагаемого способа для сжатия тех же текстов более 80% слов исходной информации, которые присутствуют в постоянном словаре, могут быть сжаты с коэффициентом сжатия 3.5…4. В итоге получим более высокий коэффициент сжатия, чем в известном способе.

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

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

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

2. Способ по п.1, отличающийся тем, что постоянный словарь формируют заранее с учетом распределения статистики слов сообщений.

3. Способ по п.1, отличающийся тем, что нумерующим кодом постоянного словаря является неравномерный статистический код.

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

5. Способ по п.1, отличающийся тем, что слова в постоянном словаре, используемом для восстановления исходной текстовой информации, располагают по величине нумерующего кода.

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

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