Известиы способы сжатия словосочетаний (фраз, состоящих из иескольких слов). Они состоят в выборе некоторого набора букв из побуквенной записи словосочетаний или постаповке в соответствие данному словосочетанию некоторого порядкового номера по словарю словосочетаиий.
Описываемый способ отличается от известных тем, что t-e слово каждого словосочетания в процессе предварительной обработки записывают в i-ю колонку пословной матрицы, выбирают из образованной матрицы словосочетаний ключевые разряды, в которых вероятность появления пуля или едипицы ближе к /2, а затем выбирают необходимое количество дополнительных ключевых разрядов в первую очередь из колонок матрицы с наибольшим количеством слов, при этом количество основных ключевых разрядов берут из условия 2 Aicc. Способ позволяет умепьшить длину кода словосочетаний и время его образовапия.
Целесообразно также все словосочетания рассматривать как «слова, из которых в процессе предварительной обработки составляется общая матрица, причем дополнительные ключевые разряды в первую очередь выбираются в той части общей матрицы, которая соответствует иптервалу длин словосочетаний от минимальной до средней.
На чертенке изображен график, поясняющий предложенный способ.
Способ заключается в следующем. Имеется словарь из словосочетаний Лсс Каждое словосочетание длины LCC состоит из i слов (f 1, 2, 3...). Словарь словосочетаний записывают в виде матрицы М, которая состоит из i колонок (слов). В первой колонке (i 1) матрицы М записывают одно под другим первые слова всех словосочетаний словаря Лсс, Во второй колонке (i 2) аналогично записывают вторые слова словосочетаний.
Записав таким образом все словосочетания, упорядоченные, например, по возрастанию длины словосочетапия LCC , исходную матрицу М представляют в виде эквивалентной ей ступенчатой матрицы.
Слова в каждой колонке матрицы, в свою очередь, могут быть упорядочены, например по возрастанию длины слова.
В каждой колонке матрицы побуквенные коды слов записывают один под другим, начиная с первого разряда первой буквы слова. Коды букв (символов алфавита) выбирают таким образом, что пары букв, вероятности появления которых на данном месте во взятом словаре Лсс одинаковы, кодируются взаимно обратными двоичными кодами (в худшем случае в качестве кодов символов могут быть взяты телеграфный или машинный код входных-выходных алфавитно-цифровых печатающих устройств ЦЭВА). Ступенчатая матрица словосочетаний, являющаяся суммой колонок из c;ioB словосочетанцй, состоит цз нулей и единиц. Количество строк в первой колонке матрицы М равио количеству словосочетаиий в словаре словосочетаний Лсс , а количество строк в г-ой колонке матрицы М равно количеству слов, стоящих в словосочетаииях на /-ом месте. Количество столбцов (двоичных разрядов) в матрице М - . i /П, О где /-max, i - иаибольшая длииа слова, стоящего на г-ом месте в словосочетаниях (в буквах); т - длииа кодовой комбинации символа алфавита (в двоичивьх знаках). В каждом столбце матрицы М нодсчнтывают количество единиц (подсчет ведут в значащей части матрицы, т. е. в той ее части, которая заполнена кодами букв); нз всей совокуиности УУдв разрядов, образующих побуквенные коды словосочетаний, вв1бирают п ключевых разрядов, в которых вероятность ноявлепня нуля или единицы иаиболее близка к /а. Для однозначного представления словосочетаний, исходя из условия (.f, требуется не менее я ключевых разрядов. При сжатии словосочетаиий до п двоичных разрядов возникает неоднозначность сжатия (т. е. образуется группа неоднозначности сжатия, в которой несколько различных словосочетаний имеют одииаковое зиачение я), которая устраняется выбором доиолнительного icoличества ключевых разрядов. Выбор доиолиительных ключевых разрядов в первую очередь производят в колонках матрицы М с большим количеством слов. Количество дополнительных разрядов обыч 4 5 но находится в интервале -;- п, хотя в 5 4 У некоторых конкретных случаях оно может быть несколько меньнте или больше этих значений. Модификацией вышеприведенного способа является случай, когда исходный словарь словосочетаний представляют не в поколонной записи слов словосочетаний, а в виде общей матрицы словосочетаний Мобщ. В этом случае словосочетание представляют в виде отделыюго «слова, )е равно сумме букв всех слов словосочетания, заниеанных в той же иоследовательности. Количество строк при этом г. матрице равно Лсс, а количество столбцов .. -Lcc.maxгде LCC, max - наибольшая длина словосочетания (в буквах). Буквы в матрице Моощ, унорядочеииой, ианример, по возрастанию длины словосочетания в буквах, кодируются как и ири основном способе. Выбор ключевых разрядов осуществляют в первую очередь в тех разрядах матрицы сбщ, которые соответствуют интервалу длин словосочетаний в буквах от LCC, ми„ до LCC. срТакая операция уетановления набора ключевых разрядов для даииого и кодирование словосочетаний выполняется на ЦЭВМ. Предмет изобретения 1. Способ образования сжатого кода словосочетаний, в котором каждое словосочетание, выраженное побуквенным кодом, преобразуют в некоторый номер но словарю словосочета;1нй, отличающийся тем, что, с целью умень;иения длины кода словосочетаиий и времени его образоваиия, t-e слово каждого словосочетания в процессе предварительной обработки записывают в /-ю колоику пословной матрицы, выбирают из образованной матрицы словосочетаний ключевые разряды, в которых вероятность появления нуля или единицы ближе к /2, а затем выбирают необходимое количество доиолиительных ключевых разрядов в первую очередь нз колонок матрицы с наибольшим количеством слов, при этом количество основных ключевых разрядов берут из условия 2 ; . Способ ио п. 1, отличающийся тем, что все словосочетания рассматриваются как «слова, из которых в процессе предварительной обработки составляют общую матрицу, причем дополнительные ключевые разряды выбирают в первую очередь в той части общей .матрицы, которая соответствует интервалу длин словосочетаиий от минимальной до средней.
LCC слоба
