Способ образования сжатого кода словосочетаний

 

l79O98

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Саветскик

Социалистическиа

Республик

Зависимое от авт. свидетельства №

Заявлено 30.1V.1964 (№ 897854/26-24) с присоединением заявки ¹

Приоритет

Опубликовано 03.11.1966. Бюллетень № 4

Дата опубликования описания 17.П1.1966

Кл, 42ш, 141

МПК G 061

Комитет ло делам изобретений и открытиЯ при Совете Министров

СССР

УДК 681.142 — 523.8 (088.8) l

Автор изобретения

К. И. Курбаков

Заявитель

СПОСОБ ОБРАЗОВАНИЯ СЖАТОГО КОДА СЛОВОСОЧЕТАНИИ

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

Описываемый способ отличается от известных тем, что i-e слово каждого словосочетания в процессе предварительной обработки записывают в l.-ю колонку пословной матрицы, выбирают из образованной матрицы словосочетаний ключевые разряды, в которых вероятность появления нуля или единицы ближе к /2, а затем выбирают необходимое количество дополнительных ключевых разрядов в первую очередь из колонок матрицы с наибольшим количеством слов, при этом количество основных ключевых разрядов берут из условия 2" ) ф„. Способ позволяет уменьшить длину кода словосочетаний и время его образования.

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

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

Способ заключается в следующем. Имеется словарь из словосочетаний Л „. Каждое слоьосочетание длины L, ñîñòîèò из i слов (i =- 1, 2, 3...). Словарь словосочетаний записывают в виде матрицы Л1, которая состоит из i колонок (слов). В первой колонке (i = 1) матрицы Л4 записывают одно под другим пер10 вые слова всех словосочетаний словаря N„, Во второй колонке (i = 2) аналогично записывают вторые слова словосочетаний.

Записав таким образом все словосочетания, упорядоченные, например, по возрастанию

15 длины словосочетания L исходную матрицу И представляют в виде эквивалентной ей ступ енч атой м атр ицы.

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

20 по возрастанию длины слова.

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

Коды букв (символов алфавита) выбирают таким образом, что пары букв, вероятности появления которых на данном месте во взятом словаре A одинаковы, кодируются взаимно обратными двоичными кодами (в худшем случае в качестве кодов символов могут быть

30 взяты телеграфный или машинный код вход179098 пых-выходных алфавитно-цифроимх печатающих устройств ЦЭВМ).

Ступенчатая матрица словосочетаний, являющаяся суммой колонок пз слои словосочетаний, состоит пз нулей и единиц. 1хо н!чест!30 строк в первой колонке матрицы Л1 равно количеству словосочетаHHH в словаре словосочетаний У„, а количество строк 13 I.-ой колонке матрицы М равно количеству слов, стоящих в словосочетаниях на i-ом месте. Количество столбцов (двоичных разрядов) в матрице М

Л QL„„õ. 1

О

ГдЕ I.max, i — НИИбОЛЬШяя ЛЛ!П!с) СЛОВя, CTOHщего на i-ом месте в словосочетя (в буквах); т — длина кодовой комбинации символа алфавита (в двоичных знаках).

В каждом столбце матрицы М подсчитывают количество единиц (подсчет ведут в значащей части матрицы, т. е. в той ее части, которая заполнена кодами букв); из всей совокупности N„разрядов, образующих побуквенные коды словосочетаний, выбирают и кл!очевых разрядов, в которых вероятность появлепиrI нуля или единицы наиболее близка к !, 2.

Для однозначного представления Л « словосочетаний, исходя из условия 2"=„V„, требуется не менее и ключевых разрядов.

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

Количество дополнительных разрядов обыч4 5, но находится в интервале: n, хотя в

5 4) некоторых конкретных случаях оно может быть несколько меньше или больше этих значений.

Модификацией вышеприведенного способа является случай, когда исходный словарь словосочетаний Л1„представляют пе в поколопной записи слов словосочетаний, а в виде общей матрицы словосочетаний М,„- .

В этОм слуПОГО <>, КОТОРОС

РЯ)3НО C3 3!ÌB ÎУК!3 13ССХ С:!013 С )OIIOCI) !ЕTHHHH, зянисишых в той же послсдовятсл!я!ости, Ко5 личество строк при этом " матрице М,„-„, PBB)iO А сс, сl КОЛИ -CCTBO СТО.! ОЦОВ Л -»> — 7cc, max

I)I >

ГДЕ L«, >пах ПЯИООЛЬШЯЯ ДЛИПЯ СЛО!30СОЧЕтания (в буквах), 10 Буквы в матрице М,„-„„упорядоченной, например, по возрастанию длины словосочетания 13 буквах, кодируются как II при основном способе.

Выбор ключевых разрядов осуществляют в

15 первую очередь в тех разрядах матрицы

Мсá,„, которые соответствуют интервалу длин словосочетаний в буквах от L „,„„ до L«, ц,.

Такая операция установления набора ключевых разрядов для данного К„ !! кодирование

20 словосочетаний выполняется на ЦЭВМ.

Предмет изобретения

25 1. Способ 0013азовапия c>H ITokо кoIB с 0130сочетяний, и котором каждое словосочетание, выраженное побуквенным кодом, преобразуют в некоторый номер по словарю словосочетаний, отли)а)ои)ийся тем, что, с целью умень30 шения длины кода словосочетаний и времени его образования, i-e слово каждого словосо-! етанпя в процессе предварительной обработки записывают в i-ю колонку пос IOBkloH матрицы, выбирают из образованной матрицы

35 словосо

2. Способ по п. 1, orëè÷òoùèéñÿ тем, что все словосочетания рассматриваются как

45 «слова», нз которых в процессе предварительной обработки составляют общую матрицу, причем дополнительные ключевые разряды т:ыбирают в первую очередь в той части общей матрицы, которая соответствует интервалу длин словосочетаний от минимальной до средней.

Редактор И. Карпас

Составитель П. П. Кондратьев

Техред T. П. Курилко Корректоры: С. Н. Соколова и Ю. М. Федулова

Заказ 579/15 Тираж 1000 Формат бум. 60;к,90 /з Объем 0,21 изд. л. Подписное

ЦНИИПИ Комитета по делам изобретений и огкрытнй при Совете Министров CCCP

Москва, Центр, пр, Серова, д. 4

Типография, пр. Сапунова, д. 2