Изобретение относится к области информационных технологий и может быть использовано для уменьшения избыточности информации, и в частности, для сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации.The invention relates to the field of information technology and can be used to reduce redundancy of information, and in particular, to compress and restore messages in processing systems, transmission and storage of text information.
Способ, описанный в настоящей заявке, может применяться для неискажающего, "бесшумного" сжатия текстовой информации без потерь, хотя его использование возможно и в системах с потерями информации. Способ относится к словарным методам сжатия и основан на использовании словарей двух типов: временного словаря, формируемого в процессе сжатия и восстановления информации, и заранее подготовленного постоянного словаря (базы данных слов), неизменного при сжатии и восстановлении информации. Постоянный словарь включает в себя наиболее употребительные слова языка, а временный словарь, формируемый и изменяемый в процессе сжатия и восстановления информации, состоит из редко встречающихся слов, не вошедших в постоянный словарь.The method described in this application can be used for non-distorting, "silent" compression of text information without loss, although its use is possible in systems with loss of information. The method relates to dictionary compression methods and is based on the use of two types of dictionaries: a temporary dictionary generated in the process of compressing and recovering information, and a previously prepared permanent dictionary (database of words) unchanged during compression and restoration of information. The permanent dictionary includes the most common words of the language, and the temporary dictionary, formed and modified during the compression and restoration of information, consists of rarely found words that are not included in the permanent dictionary.
Известно, что по статистике текстовых сообщений примерно 250 общеупотребительных слов составляют существенную долю всех слов (примерно 80-90%), которые используются при общении между людьми в повседневной жизни. В этом случае объем постоянного словаря будет составлять всего 250 слов, что требует для перечисления всего восьмиразрядного двоичного нумерующего кода (одного байта или символа), который однозначно идентифицирует или определяет каждое слово в постоянном словаре. Поскольку слово средней длины состоит примерно из 5 символов (букв), то коэффициент сжатия даже при использовании только постоянного словаря будет примерно равен 4-5. Для сравнения, средний коэффициент сжатия при использовании статистических методов сжатия Фано-Шеннона, Хаффмена или арифметического кодирования для текстовой информации примерно равен 3-4.It is known that, according to the statistics of text messages, approximately 250 common words make up a significant proportion of all words (approximately 80-90%) that are used in communication between people in everyday life. In this case, the volume of the permanent dictionary will be only 250 words, which requires an entire eight-bit binary numbering code (one byte or character) to enumerate, which uniquely identifies or defines each word in the permanent dictionary. Since a medium-length word consists of approximately 5 characters (letters), the compression ratio, even when using only a constant dictionary, will be approximately 4-5. For comparison, the average compression ratio when using statistical methods of compression Fano-Shannon, Huffman or arithmetic coding for text information is approximately 3-4.
Если исходный текст относится не к общей лексике, а к какой-либо области знаний: медицине, информатике, экономике, архитектуре и так далее, постоянный словарь составляют из наиболее употребительных слов этой области знания, и коэффициент сжатия может быть еще более увеличен. Слова из постоянного словаря могут иметь разную частоту повторения в исходном тексте, поэтому коэффициент сжатия может быть дополнительно повышен за счет применения методов статистического кодирования как слов сжатой текстовой информации, так и нумерующих кодов постоянного словаря. Дальнейшее повышение коэффициента сжатия возможно также при использовании временного словаря редких слов, отсутствующих в постоянном словаре. Временный словарь формируют аналогично формированию словаря в известных словарных методах сжатия Лемпела и Зива [Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. М.: Диалог МИФИ, 2002].If the source text does not refer to general vocabulary, but to any field of knowledge: medicine, computer science, economics, architecture, and so on, a permanent dictionary is made up of the most common words in this field of knowledge, and the compression ratio can be further increased. Words from a permanent dictionary can have different repetition rates in the source text, therefore, the compression ratio can be further increased by applying statistical coding methods for both words of compressed text information and numbering codes of the constant dictionary. A further increase in the compression ratio is also possible by using a temporary dictionary of rare words that are not in the permanent dictionary. A temporary dictionary is formed similarly to the formation of the dictionary in the well-known dictionary compression methods of Lempel and Ziva [Watolin D., Ratushnyak A., Smirnov M., Yukin V. Data compression methods. M .: Dialog MEPhI, 2002].
Для восстановления исходной текстовой информации используют постоянный словарь и массив сжатой текстовой информации. В процессе восстановления информации по массиву сжатой информации реконструируют временный словарь, идентичный временному словарю, используемому при сжатии информации.To restore the original text information using a permanent dictionary and an array of compressed text information. In the process of recovering information from an array of compressed information, a temporary dictionary is reconstructed that is identical to the temporary dictionary used to compress the information.
Эффективность сжатия оценивают коэффициентом сжатия информации, который вычисляют как отношение объема массива исходной текстовой информации к объему массива сжатой текстовой информации. Коэффициент сжатия существенным образом зависит от того, насколько постоянный словарь соответствует характеру сжимаемой текстовой информации, то есть от полноты (объема) постоянного словаря. Поэтому большую роль для эффективной реализации способа играет определение области знания, к которой относится исходная текстовая информация и формирование постоянного словаря.Compression efficiency is estimated by the information compression coefficient, which is calculated as the ratio of the volume of the source text information array to the volume of the compressed text information array. The compression ratio substantially depends on how constant the dictionary corresponds to the nature of the compressible text information, that is, on the completeness (volume) of the constant dictionary. Therefore, a large role for the effective implementation of the method is played by the determination of the field of knowledge to which the source text information and the formation of a permanent dictionary belong.
Известен способ сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации, заключающийся в том, что при сжатии текстовой информации сначала в исходной текстовой информации выделяют слово, и нумерующий код, идентифицирующий это слово в словаре, записывают в массив сжатой текстовой информации. При восстановлении исходной текстовой информации по нумерующему коду, записанному в массив сжатой информации, определяют слово в словаре, которое помещают в массив восстановленной информации [Новик Д.А. Эффективное кодирование. М.: Энергия, 1965, стр.39].A known method of compressing and restoring messages in processing systems, transmitting and storing text information, which consists in the fact that when compressing text information, a word is first extracted from the source text information, and the numbering code identifying this word in the dictionary is written into an array of compressed text information. When restoring the original textual information from the numbering code recorded in the compressed information array, the word is determined in the dictionary, which is placed in the restored information array [D. Novik Effective coding. M.: Energy, 1965, p. 39].
Недостатком этого способа является невысокий коэффициент сжатия, поскольку его использование возможно лишь при наличии слов исходной текстовой информации в словаре. Это требует больших объемов словаря, большой разрядности нумерующего кода слов в словаре и, следовательно, приводит к уменьшению коэффициента сжатия.The disadvantage of this method is the low compression ratio, since its use is possible only if there are words of source text information in the dictionary. This requires large volumes of the dictionary, large bit depth of the numbering code of words in the dictionary, and, consequently, leads to a decrease in compression ratio.
Наиболее близким к предлагаемому способу является способ (прототип) сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации, заключающийся в том, что при сжатии текстовой информации сначала в исходной текстовой информации выделяют слово, далее определяют наличие или отсутствие этого слова во временном словаре, при наличии выделенного слова во временном словаре нумерующий код, определяющий слово во временном словаре, помещают в массив сжатой текстовой информации, при отсутствии выделенного слова во временном словаре выделенное слово помещают во временный словарь и в массив сжатой текстовой информации. При восстановлении текстовой информации, при наличии в массиве сжатой текстовой информации нумерующего кода, определяющего слово во временном словаре, выбирают из временного словаря это слово и помещают его в массив восстановленной текстовой информации, при наличии в массиве сжатой текстовой информации слова исходной текстовой информации это слово помещают в массив восстановленной текстовой информации и во временный словарь [Ситняковская Е.И. Построение эффективных побуквенных кодов для словарных методов сжатия данных. Проблемы передачи информации, 1998, #34, вып.2, стр.47].Closest to the proposed method is a method (prototype) for compressing and recovering messages in processing systems, transmitting and storing text information, which consists in the fact that when compressing text information, the word is first selected in the source text information, then the presence or absence of this word in the temporary dictionary, if there is a selected word in the temporary dictionary, the numbering code defining the word in the temporary dictionary is placed in an array of compressed text information, in the absence of the selected words and in the temporary dictionary, the selected word is placed in the temporary dictionary and in an array of compressed text information. When recovering textual information, if there is a numbering code in the array of compressed textual information defining a word in the temporary dictionary, this word is selected from the temporary dictionary and placed into the array of restored textual information; if there is word in the array of compressed textual information, the source textual information is placed into the array of the restored textual information and into the temporary dictionary [Sitnyakovskaya E.I. Building effective letter-by-word codes for dictionary data compression methods. Information Transmission Problems, 1998, # 34, issue 2, p. 47].
Недостатком этого способа является невысокий коэффициент сжатия текстовой информации, поскольку слова, входящие в массив исходной текстовой информации, по крайней мере один раз, а может быть и несколько раз войдут в массив сжатой текстовой информации, в зависимости от ограничений на объем создаваемого при сжатии и восстановлении текстовой информации временного словаря, что приведет к увеличению объема массива сжатой текстовой информации.The disadvantage of this method is the low compression ratio of text information, since the words included in the array of source text information at least once, and maybe several times, will be included in the array of compressed text information, depending on the restrictions on the amount of compression and recovery text information of a temporary dictionary, which will lead to an increase in the volume of an array of compressed text information.
Цель изобретения - повышение коэффициента сжатия текстовой информации за счет совместного использования при сжатии и восстановлении текстовой информации постоянного словаря для наиболее часто встречающихся слов и временного словаря для редко встречающихся слов сообщения и последующего сжатия нумерующих кодов постоянного словаря методами статистического кодирования.The purpose of the invention is to increase the compression ratio of text information due to the use of a constant dictionary for the most frequently occurring words and a temporary dictionary for rarely encountered message words during compression and recovery of text information of the dictionary and subsequent compression of the numbering codes of the permanent dictionary by statistical coding methods.
Для достижения цели предложен способ сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации, заключающийся в том, что при сжатии сообщений в массиве исходной текстовой информации выделяют слово, далее определяют наличие или отсутствие этого слова во временном словаре, при наличии выделенного слова во временном словаре нумерующий код, определяющий слово во временном словаре, помещают в массив сжатой текстовой информации, при отсутствии выделенного слова во временном словаре выделенное слово помещают во временный словарь и в массив сжатой текстовой информации. При восстановлении сообщения, при наличии в массиве сжатой текстовой информации нумерующего кода, определяющего слово во временном словаре, извлекают из временного словаря это слово и помещают его в массив восстановленной текстовой информации, при наличии в массиве сжатой текстовой информации слова исходной текстовой информации это слово помещают в массив восстановленной текстовой информации и во временный словарь. Новым является то, что при сжатии сообщений сначала определяют наличие или отсутствие выделенного слова массива исходной текстовой информации в постоянном словаре, при наличии этого слова в постоянном словаре нумерующий код, определяющий слово в постоянном словаре, помещают в массив сжатой текстовой информации, при отсутствии слова в постоянном словаре определяют его наличие или отсутствие во временном словаре. После кодирования всех слов массива исходной текстовой информации с помощью постоянного и временного словаря последовательность нумерующих кодов постоянного словаря в сжатой текстовой информации кодируют статистическим кодом. При восстановлении сообщения сначала в массиве сжатой текстовой информации выбирают коды статистического кодирования и восстанавливают последовательность нумерующих кодов постоянного словаря, получая при этом массив нумерующих кодов постоянного и временного словаря, затем при наличии в этом массиве нумерующего кода постоянного словаря, извлекают из постоянного словаря слово, соответствующее этому нумерующему коду, и помещают его в массив восстановленной информации, при отсутствии нумерующего кода постоянного словаря в массиве нумерующих кодов постоянного словаря для восстановления текстовой информации используют временный словарь. Причем постоянный словарь формируют заранее с учетом распределения статистики слов сообщений, используя в качестве нумерующего кода постоянного словаря неравномерный статистический код, слова в постоянном словаре, используемом для сжатия текстовой информации, располагают в лексикографическом порядке, а слова в постоянном словаре, используемом для восстановления текстовой информации, располагают по величине нумерующего кода и для поиска слова в постоянном словаре при сжатии и восстановлении текстовой информации используют метод дихотомии. Составляют несколько постоянных словарей для сообщений, относящихся к различным областям знания, перед началом сжатия сообщения определяют постоянный словарь, в котором наиболее часто встречаются слова данного сообщения, и затем этот постоянный словарь используют для сжатия и восстановления сообщения.To achieve the goal, a method for compressing and restoring messages in processing systems for the transmission, transmission and storage of text information is proposed, which consists in the fact that when a message is compressed in a source text information array, a word is extracted, then the presence or absence of this word is determined in the temporary dictionary, if there is a selected word in the temporary dictionary, the numbering code defining the word in the temporary dictionary is placed in an array of compressed text information, in the absence of a selected word in the temporary dictionary, the selected word is placed in a temporary dictionary and in an array of compressed text information. When recovering a message, if there is a numbering code in the array of compressed text information defining a word in the temporary dictionary, this word is extracted from the temporary dictionary and placed in an array of restored text information, if there is word in the array of compressed text information, the source text information is placed in an array of recovered text information and into a temporary dictionary. What is new is that when compressing messages, the presence or absence of a selected word of an array of source text information in a constant dictionary is first determined, if this word is in a constant dictionary, the numbering code defining the word in the constant dictionary is placed in an array of compressed text information, if there is no word in a permanent dictionary determines its presence or absence in a temporary dictionary. After encoding all the words in the array of the source text information using a permanent and temporary dictionary, the sequence of numbering codes of the constant dictionary in the compressed text information is encoded with a statistical code. When recovering a message, first select the statistical coding codes in the compressed text information array and restore the sequence of numbering codes of the permanent dictionary, obtaining an array of numbering codes of the permanent and temporary dictionary, then if there is a numbering code of the constant dictionary in this array, the word corresponding to to this numbering code, and place it in the array of recovered information, in the absence of the numbering code of the permanent dictionary in the number array The operating codes of the permanent dictionary use a temporary dictionary to recover textual information. Moreover, the permanent dictionary is formed in advance, taking into account the distribution of statistics of message words, using an uneven statistical code as the numbering code of the permanent dictionary, the words in the constant dictionary used to compress text information are placed in lexicographic order, and the words in the constant dictionary used to restore text information , have the largest numbering code, and to search for a word in a permanent dictionary when compressing and restoring text information, use the di Otomo. They compose several permanent dictionaries for messages belonging to different fields of knowledge, before starting to compress the message, a constant dictionary is defined in which the words of the message are most often found, and then this constant dictionary is used to compress and restore the message.
Предлагаемый способ сжатия и восстановления сообщений в системах обработки, передачи и хранения текстовой информации реализуют следующим образом.The proposed method of compression and recovery of messages in processing systems, transmission and storage of text information is implemented as follows.
Сначала заранее формируют постоянный словарь. Постоянный словарь подготавливают заранее перед сжатием текстовой информации. Он заранее известен как при сжатии, так и при восстановлении текстовой информации. Для формирования постоянного словаря используют массивы исходной текстовой информации определенных областей знания, например таких областей знания, как радиотехника, физика, химия, медицина и так далее. Для составления постоянного словаря целесообразно использовать наиболее употребительные по частоте слова данных областей знания. Сначала выбирают массивы исходной текстовой информации, относящиеся к какой-либо области знания. Эти массивы используют для построения постоянного словаря данной области знания. Построение постоянного словаря начинают с выделения слов в массивах исходной текстовой информации. Слово состоит из букв (символов) и имеет определенную длину. Например, в массивах исходной текстовой информации словом может быть последовательность символов, ограниченная спереди и сзади пробелами или знаками препинания. Слова могут иметь переменную длину. Каждое вновь встретившееся в массивах исходной текстовой информации слово помещают в постоянный словарь. Для слов, которые записаны в постоянный словарь, подсчитывают их частоту. Слова в предложениях могут отличаться падежом, склонением и так далее. Поэтому в постоянном словаре можно хранить лишь неизменные части слов, например корни слов. Наиболее употребляемые приставки, суффиксы и окончания слов можно также хранить в постоянном словаре, но отдельно. При этом осуществляют неискажающее сжатие информации без потерь с точным восстановлением слов в предложениях. Возможно также хранить слова в постоянном словаре только в определенном падеже, склонении и т.д. Тогда восстановление исходной информации осуществляют с потерями, т.е. с искажениями приставок, суффиксов и окончаний слов. При этом восприятие смысла многих предложений после восстановления информации может сохраняться. В последнем случае получают более высокий коэффициент сжатия информации. Коррекцию приставок, суффиксов и окончаний слов можно затем проводить отдельно, используя правила орфографии.First, a permanent dictionary is formed in advance. A permanent dictionary is prepared in advance before compressing textual information. It is known in advance both in compression and in text information recovery. For the formation of a permanent dictionary using arrays of source text information of certain areas of knowledge, for example, areas of knowledge such as radio engineering, physics, chemistry, medicine and so on. To compile a permanent dictionary, it is advisable to use the most commonly used words of these areas of knowledge. First, arrays of initial textual information related to any field of knowledge are selected. These arrays are used to build a permanent dictionary of a given field of knowledge. The construction of a permanent dictionary begins with the selection of words in arrays of source text information. A word consists of letters (characters) and has a certain length. For example, in arrays of source textual information, a word can be a sequence of characters limited to front and back by spaces or punctuation marks. Words can have a variable length. Each word that was again found in the arrays of the source text information is placed in a permanent dictionary. For words that are recorded in a permanent dictionary, their frequency is calculated. Words in sentences may differ in case, declension, and so on. Therefore, in a permanent dictionary you can store only the invariable parts of words, for example, the roots of words. The most used prefixes, suffixes and word endings can also be stored in a permanent dictionary, but separately. At the same time, non-distorting lossless information compression is performed with the exact restoration of words in sentences. It is also possible to store words in a permanent dictionary only in a specific case, declension, etc. Then, the restoration of the initial information is carried out with losses, i.e. with distortions of prefixes, suffixes and word endings. At the same time, the perception of the meaning of many sentences after the restoration of information can be preserved. In the latter case, a higher compression ratio is obtained. Correction of prefixes, suffixes and word endings can then be carried out separately using spelling rules.
После того как все слова исходной текстовой информации размещены в постоянном словаре, выполняют кодирование слов постоянного словаря с помощью равномерного или неравномерного нумерующего кода. Наиболее просто слова в постоянном словаре могут нумероваться равномерным кодированием слов в постоянном словаре. При таком кодировании для записи номера каждого слова в постоянном словаре используют одно и то же число двоичных разрядов нумерующего кода. Можно пользоваться и другими более экономичными, но при этом и более сложными методами кодирования номеров. К числу таких методов относится кодирование с помощью неравномерных разделимых кодов, например, с помощью кода Хаффмена (или других эффективных кодов: Фано-Шеннона, арифметического и так далее), учитывающего частоту использования слов постоянного словаря.After all the words of the source text information are placed in a permanent dictionary, the words of the permanent dictionary are encoded using a uniform or uneven numbering code. Most simply, words in a permanent dictionary can be numbered by uniformly coding words in a permanent dictionary. With this encoding, the same number of binary bits of the numbering code is used to record the numbers of each word in a constant dictionary. You can use other more economical, but at the same time more complex methods of encoding numbers. Among these methods is encoding using non-uniform separable codes, for example, using the Huffman code (or other effective codes: Fano-Shannon, arithmetic, etc.), taking into account the frequency of use of the words of a constant dictionary.
Постоянный словарь будет состоять из слов и соответствующих им равномерных или неравномерных нумерующих кодов. После этого слова в постоянном словаре располагают в лексикографическом порядке (по алфавиту), что упрощает и ускоряет поиск слов в словаре при сжатии информации. Существенное значение при реализации способа имеет объем постоянного словаря. При слишком большом объеме постоянного словаря нумерующий код слова в постоянном словаре будет иметь большое число разрядов, что может уменьшить величину коэффициента сжатия. С другой стороны, при ограничении числа слов в постоянном словаре в исходной информации может оказаться большое число слов, отсутствующих в постоянном словаре, что также может уменьшить величину коэффициента сжатия. Объем постоянного словаря следует ограничивать определенным значением, оставляя только наиболее часто употребляемые слова. Следует выбирать такой объем постоянного словаря, при котором слова постоянного словаря составляют существенную долю слов в исходной текстовой информации (например, >2/3). По статистике 250 общеупотребительных слов составляют существенную долю всех слов, которые используются при общении между людьми в повседневной жизни. В этом случае объем словаря может составлять всего 250 слов, что требует восьмиразрядного равномерного двоичного нумерующего кода (одного байта), который однозначно идентифицирует или определяет каждое слово в постоянном словаре. При использовании неравномерного разделимого статистического кодирования средняя разрядность нумерующего кода уменьшится.A permanent dictionary will consist of words and their corresponding uniform or uneven numbering codes. After this, the words in the permanent dictionary are placed in lexicographic order (alphabetically), which simplifies and speeds up the search for words in the dictionary when compressing information. Essential in the implementation of the method is the volume of the permanent dictionary. If the volume of the permanent dictionary is too large, the numbering code of the word in the permanent dictionary will have a large number of bits, which can reduce the value of the compression coefficient. On the other hand, when limiting the number of words in a permanent dictionary, the source information may contain a large number of words that are not in the permanent dictionary, which can also reduce the value of the compression coefficient. The volume of a permanent dictionary should be limited to a certain value, leaving only the most frequently used words. You should choose such a volume of the permanent dictionary, in which the words of the permanent dictionary make up a significant proportion of the words in the source text information (for example,> 2/3). According to statistics, 250 common words make up a significant proportion of all the words that are used in communication between people in everyday life. In this case, the volume of the dictionary can be only 250 words, which requires an eight-bit uniform binary numbering code (one byte), which uniquely identifies or defines each word in a permanent dictionary. When using uneven separable statistical coding, the average bit depth of the numbering code will decrease.
После составления постоянного словаря можно выполнять сжатие исходной текстовой информации. Допустим, что исходная информация представляется в виде последовательности символов х1х2х3,…,xr. Пусть выделенное слово есть xqxq+1,xq+2,…,xq+i. Сначала выделенное слово ищут в постоянном словаре. Поскольку слова в постоянном словаре упорядочены в лексикографическом порядке (по алфавиту), то поиск слова целесообразно проводить методом дихотомии (деления области поиска пополам). При этом сначала искомое слово сравнивают со средним словом постоянного словаря. Если искомое слово лексикографически больше этого среднего слова, продолжают поиск в верхней половине постоянного словаря, в противном случае - в нижней половине и так далее. Если такое слово найдено, в массив сжатой информации добавляется нумерующий код, начинающийся с признака постоянного словаря, например с 11. Далее в массив сжатой информации дописывается нумерующий код αq, идентифицирующий это слово в постоянном словаре. Таким кодом может быть, например, нумерующий код, определяющий положение слова в постоянном словаре.After compiling a permanent dictionary, you can compress the source text information. Suppose that the source information is represented as a sequence of characters x1 x2 x3 , ..., xr . Let the selected word be xq xq + 1 , xq + 2 , ..., xq + i . First, the highlighted word is searched in the permanent dictionary. Since words in a permanent dictionary are ordered in lexicographic order (alphabetically), it is advisable to search for a word using the dichotomy method (dividing the search area in half). In this case, first the searched word is compared with the middle word of the permanent dictionary. If the search word is lexicographically larger than this middle word, continue the search in the upper half of the permanent dictionary, otherwise - in the lower half and so on. If such a word is found, a numbering code is added to the compressed information array, starting with the attribute of a permanent dictionary, for example, 11. Next, a numbering code αq identifying this word in the permanent dictionary is added to the compressed information array. Such a code can be, for example, a numbering code that determines the position of a word in a permanent dictionary.
В том случае, если слово не найдено в постоянном словаре, осуществляют поиск этого слова во временном словаре. При обнаружении слова во временном словаре в массив сжатой информации помещают код признака временного словаря, равный 10, и осуществляют, например, неравномерное разделимое кодирование положения и длины этого слова во временном словаре. Сформированный код βq также помещают в массив сжатой текстовой информации.In the event that the word is not found in the permanent dictionary, search for this word in the temporary dictionary. When a word is detected in a temporary dictionary, the attribute code of the temporary dictionary equal to 10 is placed in the compressed information array, and, for example, uneven separable encoding of the position and length of this word in the temporary dictionary is performed. The generated code βq is also placed in an array of compressed text information.
В том случае, если ни выделенное слово, ни его части не обнаружены ни в одном из двух словарей, то в массив сжатой информации помещают код отсутствия слова в словарях, равный, например 00, и далее в массив сжатой информации помещают само слово и это же слово помещают во временный словарь.In the event that neither the highlighted word, nor its parts are found in either of the two dictionaries, then the code for the absence of the word in the dictionaries equal to, for example, 00 is placed in the compressed information array, and then the word itself is placed in the compressed information array and this is the word is placed in a temporary dictionary.
Затем выделяется следующее слово в исходной текстовой информации, и вся процедура сжатия исходной текстовой информации повторяется для этого слова. И так продолжается до конца исходной текстовой информации.Then the next word is highlighted in the source text information, and the entire compression process of the source text information is repeated for that word. And so it goes on until the end of the original textual information.
При реализации способа, особенно если исходная текстовая информация имеет большой объем, временный словарь ограничивают по размеру. При достижении предельных размеров временного словаря осуществляют сдвиг содержимого временного словаря, вытесняя более старые, давно не используемые слова и освобождая место для новых слов.When implementing the method, especially if the source text information is large, the temporary dictionary is limited in size. Upon reaching the maximum size of the temporary dictionary, the contents of the temporary dictionary are shifted, displacing older, long-unused words and making room for new words.
В результате сжатия информации получаем массив сжатой текстовой информации, который требует для хранения меньшего объема памяти или передается за меньшее время, чем исходная текстовая информация.As a result of information compression, we obtain an array of compressed text information, which requires less storage space or is transmitted in less time than the original text information.
Для восстановления текстовой информации используют массив сжатой текстовой информации и постоянный словарь, который содержит те же слова, что и постоянный словарь, используемый при сжатии текстовой информации, но расположенные в другом порядке. Слова в постоянном словаре, используемом при восстановлении текстовой информации, упорядочены по величине нумерующего кода, который идентифицирует эти слова. Такой порядок расположения слов в постоянном словаре упрощает и ускоряет поиск слов в постоянном словаре, поскольку позволяет для их поиска использовать метод дихотомии.To recover textual information, an array of compressed textual information and a permanent dictionary are used, which contains the same words as the permanent dictionary used to compress textual information, but arranged in a different order. The words in the permanent dictionary used to recover textual information are ordered by the numbering code that identifies these words. This arrangement of words in a permanent dictionary simplifies and speeds up the search for words in a permanent dictionary, because it allows you to use the dichotomy method for their search.
Восстановление текстовой информации начинают с анализа очередных двух битов в массиве сжатой текстовой информации. Если эти два бита равны 11, то по нумерующему коду слова αq, который следует за этими двумя битами, ищут само слово в постоянном словаре. При равномерном кодировании слов в постоянном словаре для этого достаточно по коду слова, как по адресу, выбрать слово из постоянного словаря. При неравномерном кодировании, если слова упорядочены по нумерующему коду, поиск слова в постоянном словаре целесообразно, с целью его ускорения, проводить методом дихотомии. Далее найденное слово помещают в массив восстановленной информации. В случае, если очередные два бита массива сжатой информации равны 10, то ищут слово во временном словаре. Для этого используют код идентификации βq слова во временном словаре, который следует за этими двумя битами. При этом код идентификации слова состоит из кода номера положения слова в словаре и кода длины этого слова. Выбранное слово помещают в массив восстановленной информации. Если очередные два бита массива сжатой информации равны 00, массив сжатой информации дополняется словом, которое следует за 00, и одновременно это слово записывается во временный словарь, реконструируя его в процессе восстановления текстовой информации.The restoration of textual information begins with the analysis of the next two bits in an array of compressed textual information. If these two bits are equal to 11, then by the numbering code of the word αq that follows these two bits, they search for the word itself in a constant dictionary. With uniform coding of words in a permanent dictionary, for this it is enough to select a word from the permanent dictionary by the code of the word, as at the address. In case of uneven coding, if the words are ordered by numbering code, it is advisable to search for a word in a permanent dictionary in order to speed it up using the dichotomy method. Next, the found word is placed in an array of recovered information. If the next two bits of the compressed information array are equal to 10, then they look for the word in the temporary dictionary. To do this, use the identification code βq of the word in the temporary dictionary that follows these two bits. Moreover, the word identification code consists of a code for the position number of a word in the dictionary and a code for the length of this word. The selected word is placed in an array of recovered information. If the next two bits of the compressed information array are 00, the compressed information array is supplemented with the word that follows 00, and at the same time this word is written into a temporary dictionary, reconstructing it in the process of recovering text information.
Аналогичным образом, затем анализируют следующие два бита в массиве сжатой информации, и так далее процедура продолжается до конца массива сжатой текстовой информации.Similarly, the next two bits in the compressed information array are then analyzed, and so on, the procedure continues to the end of the compressed text information array.
Следует отметить, что выше описан наиболее простой однопроходный вариант сжатия и восстановления информации. Переход к многопроходному варианту существенно повышает эффективность или коэффициент сжатия. При многопроходном варианте можно повысить качество постоянного словаря, поскольку при первом проходе можно выбрать наиболее подходящий постоянный словарь из списка заранее подготовленных постоянных словарей. При этом в начале массива сжатой информации дополнительно помещают информацию о выбранном постоянном словаре, которую используют при выборе постоянного словаря при восстановлении информации.It should be noted that the simplest single-pass option for compressing and restoring information is described above. Switching to the multi-pass option significantly increases the efficiency or compression ratio. With the multi-pass option, you can improve the quality of the permanent dictionary, since at the first pass you can select the most suitable permanent dictionary from the list of pre-prepared permanent dictionaries. At the same time, information about the selected permanent dictionary is additionally placed at the beginning of the compressed information array, which is used when choosing a permanent dictionary when restoring information.
В предлагаемом способе сжатие и восстановление информации осуществляется с применением постоянного словаря. При соответствующем выборе постоянного словаря и в зависимости от характера сжимаемой исходной информации коэффициент сжатия информации можно повысить по сравнению с известным способом. Коэффициент сжатия текстов в известном способе статистического сжатия составляет величину, примерно равную 2…2.5. Такие же значения коэффициента сжатия обеспечивают известные архиваторы, использующие словарные методы сжатия ZIP и RAR. При использовании предлагаемого способа для сжатия тех же текстов более 80% слов исходной информации, которые присутствуют в постоянном словаре, могут быть сжаты с коэффициентом сжатия 3.5…4. В итоге получим более высокий коэффициент сжатия, чем в известном способе.In the proposed method, the compression and restoration of information is carried out using a permanent dictionary. With the appropriate choice of a permanent dictionary and depending on the nature of the compressible source information, the compression ratio of information can be increased in comparison with the known method. The compression ratio of texts in the known method of statistical compression is approximately equal to 2 ... 2.5. The same compression ratio values are provided by well-known archivers using dictionary compression methods ZIP and RAR. When using the proposed method for compressing the same texts, more than 80% of the source information words that are present in the permanent dictionary can be compressed with a compression ratio of 3.5 ... 4. As a result, we obtain a higher compression ratio than in the known method.
Достигаемым техническим результатом предлагаемого способа сжатия и восстановления информации является повышение коэффициента сжатия информации.Achievable technical result of the proposed method of compression and recovery of information is to increase the compression ratio of information.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2010143361/08ARU2437148C1 (en) | 2010-10-22 | 2010-10-22 | Method to compress and to restore messages in systems of text information processing, transfer and storage |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2010143361/08ARU2437148C1 (en) | 2010-10-22 | 2010-10-22 | Method to compress and to restore messages in systems of text information processing, transfer and storage |
| Publication Number | Publication Date |
|---|---|
| RU2437148C1true RU2437148C1 (en) | 2011-12-20 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| RU2010143361/08ARU2437148C1 (en) | 2010-10-22 | 2010-10-22 | Method to compress and to restore messages in systems of text information processing, transfer and storage |
| Country | Link |
|---|---|
| RU (1) | RU2437148C1 (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2014163524A1 (en)* | 2013-04-03 | 2014-10-09 | Sherbakov Andrei Yuryevich | Method for creating virtual portrait of user |
| RU2592456C1 (en)* | 2015-07-06 | 2016-07-20 | Акционерное общество "Калужский научно-исследовательский институт телемеханических устройств"(АО"КНИИТМУ") | Method of processing, storage and transmission of telecode control commands |
| RU2611257C1 (en)* | 2015-10-01 | 2017-02-21 | Акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" | Method of preparation, storage and transfer of operational and command information in telecode control complexes |
| Title |
|---|
| СЭЛОМОН Д. Мир программирования. Цифровая обработка сигналов. Сжатие данных, изображений и звука. - М.: Техносфера, 2004, глава 2.* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2014163524A1 (en)* | 2013-04-03 | 2014-10-09 | Sherbakov Andrei Yuryevich | Method for creating virtual portrait of user |
| RU2592456C1 (en)* | 2015-07-06 | 2016-07-20 | Акционерное общество "Калужский научно-исследовательский институт телемеханических устройств"(АО"КНИИТМУ") | Method of processing, storage and transmission of telecode control commands |
| RU2611257C1 (en)* | 2015-10-01 | 2017-02-21 | Акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" | Method of preparation, storage and transfer of operational and command information in telecode control complexes |
| Publication | Publication Date | Title |
|---|---|---|
| KR101049699B1 (en) | Data Compression Method | |
| CN101800556B (en) | Method and apparatus for adaptive data compression | |
| EP0127815B1 (en) | Data compression method | |
| RU2437148C1 (en) | Method to compress and to restore messages in systems of text information processing, transfer and storage | |
| JP2012124679A (en) | Apparatus and method for decoding encoded data | |
| JP5913748B2 (en) | Secure and lossless data compression | |
| US20080270117A1 (en) | Method and system for text compression and decompression | |
| Gripon et al. | Compressing multisets using tries | |
| Reznik | Coding of sets of words | |
| RU2386210C2 (en) | Method for data compression | |
| US9143163B2 (en) | Method and system for text compression and decompression | |
| Korodi et al. | Lossless data compression using optimal tree machines | |
| Arif et al. | An enhanced static data compression scheme of Bengali short message | |
| CN102891730A (en) | Method and device for encoding satellite short message based on binary coded decimal (BCD) code | |
| Shanmugasundaram et al. | Text preprocessing using enhanced intelligent dictionary based encoding (EIDBE) | |
| Rani et al. | A survey on lossless text data compression techniques | |
| Zia et al. | Two-level dictionary-based text compression scheme | |
| Shanmugasundaram et al. | IIDBE: A lossless text transform for better compression | |
| Anisimov et al. | Variable length prefix (Δ, k)-codes | |
| Frenkel et al. | Lempel-Ziv-welch compression algorithm with exponential decay | |
| Swarnkar et al. | An Implementation of Efficient Text Data Compression | |
| Wirth | Symbol-driven compression of Burrows Wheeler transformed text | |
| Reznik | Codes for unordered sets of words | |
| Kotze et al. | An evaluation of the Lempel-Ziv-Welch data compression algorithm | |
| Radescu et al. | Recent results in combined coding for word-based PPM |
| Date | Code | Title | Description |
|---|---|---|---|
| MM4A | The patent is invalid due to non-payment of fees | Effective date:20121023 |