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

 

ОП ИСА Н И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Соеетскяв

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

Республик

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

Кл. 42m, 14/04

Заявлено 30.Х!.1963 (№ 870148/26-24) с присоединением заявки №

Приоритет

Опубликовано 13.И!!.1966. Бюллетень № 17

Дата опубликования описания 18.XI,1966

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

СССР

МПК G 06!

УД К 681.142-523.8:621.383 (088.8) Автор изобретения

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

Заявитель

СПОСОБ РАЗДЕЛЕНИЯ НЕОДНОЗНАЧНО СЖАТЫХ

КОДОВ СЛОВ

Например

ГАЗЕТА

ГАЛЕТА

ТОН

БАНК

/ ГАЗЕТА

15 (ГАЛЕТА

/ ТОН БАНК

2Р БОКОВОЙ /)а СВАРНОИ СИЛОВОЙ

Мт М

БОКОВОЙ

СВАРНОЙ 1а

СИЛОВОИ"

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

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

Пусть для данного словаря N слов и заданной операции (способа) сжатия имеется т

ar =, N ; групп одинаково сжатых слов, 2

Здесь N jr — количество групп q, -ro типа. а

i означает количество слов (i= 2, З.....к) в конкретной группе неоднозначности сжатия т1;, имеющих одинаковый сжатый код слова и.

Для разделения от используют разделительные признаки, например прямые и обрат2 ные позиции слов (позиции rn — место в слове, на котором стоит та или иная буква), Набор разделительных признаков, достаточный для разделения or, определяют в следующей последовательности: для данной неоднозначности сжатия от определяют первую весовую характеристику. разделительных признаков.

Для этого строится матрица прямая (М ) и

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

1234567 — - Прямые Обратные — 7 б 5 4 3 2 1

25 позиции. позиции.

Таким образом, первые буквы слов попадают в первый столбец (колонку) матрицы

Мт, вторые буквы — во второй столбец и т. д.

30 Построение в обратной матрице Mr отличается лишь тем, что отсчет позиций ведется от

185583

3 конца слова. После этого находят вероятность

Рт разделения всех групп неоднозначности сжатия от каждым разделительным признаком в отдельности. Для этого каждую rpynriy неоднозначности сжатия кодов слов анализируют на полное разделение всех слов в данной группе каждой прямой и обратной позицией слова, т. е. берут каждую группу и в данной позиции сравнивают все слова группы. Если буквы всех слов группы в данной позиции различны, то, следовательно, данная позиция разделяет данную группу неоднозначно сжатых слов. Если же, например, лишь два слова группы имеют одну и ту же букву в данной позиции, то, следовательно, группа этим признаком (позицией) не разделяется.

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

Из весовой характеристики признаков Р берут наиболее весомый признак, т. е. тот, который разделяет наибольшее количество групп 1,. данной неоднозначности сжатия, т. е. берут признак жт, у которого в данной весо1 вой характеристике P значение P - =max.

Этот признак mr берут в качестве первого из набора признаков. Затем определяют состав и количество групп q, неразделенных первым разделительным признаком тт. т. е. неоднозначность сжатия orr, которая осталась на

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

Процесс нахождения признаков разделения или процесс разделения неоднозначности сжатия продолжается до тех пор, пока на какойто ступени разделения не окажется групп, которые требуется разделять, т. е. будет справедливо равенство Ж =О, где Nq; — количество групп q,.-го типа на ф-той ступени разделения. Сходимость процесса поиска разделительных признаков очень быстрая, так как

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

Таким образом, в результате применения данного способа для любого количества групп неоднозначности сжатия всегда можно найти такой набор признаков, который полностью разделяет исходную неоднозначность сжатия и по своей длине значительно меньше всего побуквенного кода слова. Так, например, для словаря объемом N=3006 слов и неоднозначности сжатия ar =151 группам, состоящей из

144 групп типа q2 и 7 групп типа q3, потребовалось лишь два признака (две ступени разделения). Если на какой-то ступени разделения появляется несколько равновесовых позиций, то путем последовательного перебора небольшого количества равновесовых признаков можно для данной неоднозначности сжатия установить оптимальный набор разделительных признаков, т. е. наименьшее количество признаков, необходимое для полного разделения исходной неоднозначности сжатия. Оптимальный набор признаков может быть меньше неоптимального на один-два признака.

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

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

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