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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Соеетскяд Социалистичеснид РеспубликЗависимое от авт, свидетельстваКл. 42 тп, 14/04 Заявлено 30.Х.1963 ( 870148/26-24)с присоединением заявкиПриоритетОпубликовано 13,И 11,1966, Бюллетень17Дата опубликования описания 18.Х 1,19 бб Комитет по деламобретений и открытийри Совете МинистровСССР 6 К 681,142-523.8:621.383 (088,8) зобретени Заявитель ПОСОБ РАЗДЕЛЕНИЯ НЕОДНОЗНАЧНО СЖАТЫХ КОДОВ СЛОВИзвестны способы разделения неоднозначно сжатых кодов слов, по которым для разделения используется длина слова, вся или большая часть побуквенного кода этого слова. Эти способы требуют для выполнения операции разделения обработки большого количества информации.Предлагаемый способ отличается от известных тем, что для повышения эффективности выполнения операции разделения путем подбора разделительных признаков с учетом их весовой характеристики строят прямую и обратную матрицы из слов, входящих в группы неоднозначно сжатых слов, определяют вес прямых и обратных позиций слов, выбирая в качестве первого разделительного признака позицию слова, разделяющую наибольшее количество групп неоднозначно сжатых слов, Цикл повторяют до полного разделения всех групп неоднозначно сжатых слов.Пусть для данного словаря Ж слов и заданной операции (способа) сжатия имеетсяЬч = , Ут, групп одинаково сжатых слов,2Здесь Ж - количество групп т 1; -го типа. а т означает количество слов (г=2,3 к) в конкретной группе неоднозначности сжатия имеющих одинаковый сжатый код слова и.Для разделения о используют разделительные признаки, например прямые и обрат(позиции и -оит та или иная ых признаков,т, определяют ти: для данной определяют пер разделительных ся матрица пр т. е, слова всех тия записываю и от конца словсло- Наный щей нь ве е позиции сло, на котором стбор разделительдля разделенияпоследовательносности сжатия отхарактеристикуДля этого строиобратная (М),нозначности сждругим от началаНапример:( ГАЗЕТАГАЛЕТА место в буква), достаточ в следую неодноз вую веспризна ямая (М начовую ков. ) и упп оди еод по ГАЗЕТА ГАЛЕТА ОНАНК ТОН БАН12345 б 7 -Прям5 пози слов попа- ) матрицы лбец и т. д. первые буквы толбец (колонку- во второй сто атной матрице М отсчет позиций50 55 60 3конца слова. После этого находят вероятность Рт разделения всех групп неоднозначности сжатия от каждым разделительным признаком в отдельности. Для этого каждую группу неоднозначности сжатия кодов слов анализируют на полное разделение всех слов в данной группе каждой прямой и обратной позицией слова, т. е. берут каждую группу и в данной позиции сравнивают все слова группы. Если буквы всех слов группы в данной позиции различны, то, следовательно, данная позиция разделяет данную группу неоднозначно сжатых слов. Если же, например, лишь два слова группы имеют одну и ту же букву в данной позиции, то, следовательно, группа этим признаком (позицией) не разделяется.УВесовая характеристика Р- на первой ступени разделения состоит из набора значений вероятностей Р-, каждая из которых характеризует определенную позицию матриц М, и М и определяется как отношение количества разделенных групп к количеству групп, участвовавших в разделении данной позицией (группа ), не участвует в разделении, если количество букв в самом длинном слове этой группы меньше числа, выражающего номер позиции).Из весовой характеристики признаков Р берут наиболее весомый признак, т. е. тот, который разделяет наибольшее количество групп т, данной неоднозначности сжатия, т. е. берут признак жт, у которого в данной весовой характеристике Р значение Р- =гпах, Этот признак т берут в качестве первого из набора признаков. Затем определяют состав и количество групп т, неразделенных первым разделительным признаком тт, т. е. неоднозначность сжатия од, которая осталась на 11-ю ступень разделения и равна разности между количеством групп всей исходной неоднозначности сжатия и количеством групп, разделенных на 1-й ступени разделения. СоПставляют весовую характеристику Р- для атт и также определяют наиболее весомый признак, т. е, второй разделительный признак ттт набора. Позиции, взятые на предыдущих ступенях разделения, не используют, так как они новой информации не несут.Процесс нахождения признаков разделения или процесс разделения неоднозначности сжатия продолжается до тех пор, пока на какойто ступени разделения не окажется групп, которые требуется разделять, т. е. будет справедливо равенство Ж =0, где У; - количество групп п,.-го типа на -той ступени разделения. Сходимость процесса поиска разделительных признаков очень быстрая, так как 5 10 15 20 25 30 35 40 45 происходит быстрое сужение области поиска необходимых разделительных признаков требуемого набора. То есть с увеличением количества ступеней разделения неоднозначности сжатия происходит весьма быстрое уменьшение количества групп, подлежащих разделению.Таким образом, в результате применения данного способа для любого количества групп неоднозначности сжатия всегда можно найти такой набор признаков, который полностью разделяет исходную неоднозначность сжатия и по своей длине значительно меньше всего побуквенного кода слова. Так, например, для словаря объемом У=3006 слов и неоднозначности сжатия о =151 группам, состоящей из 144 групп типа н 2 и 7 групп типа тз, потребовалось лишь два признака (две ступени разделения), Если на какой-то ступени разделения появляется несколько равновесовых позиций, то путем последовательного перебора небольшого количества равновесовых признаков можно для данной неоднозначности сжатия установить оптимальный набор разделительных признаков, т. е. наименьшее количество признаков, необходимое для полного разделения исходной неоднозначности сжатия. Оптимальный набор признаков может быть меньше неоптимального на один-два признака.Для дальнейшего увеличения эффективности выполнения операции разделения неоднозначно сжатых кодов слов в качестве разделительных признаков можно брать не весь код символа, стоящий в данной позиции, а лишь его часть, начиная, например, с младших разрядов, Предварительное установление необходимого и оптимального набора разделительных признаков для данной неоднозначности сжатия сравнительно простое выполняется на любой ЭЦВМ, а непосредственное составление набора признаков для конкретного слова заключается в выделении из побуквенного кода слова выбранных в нем позиций (или кодов букв в этих позициях). Предмет изобретения Способ разделения неоднозначно сжатых кодов слов, отличающийся тем, что, с целью повышения эффективности выполнения операции разделения путем подбора разделительных признаков с учетом их весовой характеристики, строят прямую и обратную матрицы из слов, входящих в группы неоднозначно сжатых слов, определяют вес прямых и обратных позиций слов, выбирая в качестве первого разделительного признака позицию слова, разделяющую наибольшее количество групп неоднозначно сжатых слов, и повторяют цикл до полного разделения всех групп неоднозначно сжатых слов,