Способ поиска патентных документов при помощи цифровых вычислительных систем

305479. ОПИСАНИЕ ИЗОБРЕТЕН ИЯ к АВТОРскОму свидетепьстВуСоюз Советских Социалистических РеспубликЗависимое от авт. свидетельстваЗаявлено 15.1 Х,1969 ( 13611,31/8-24),с присоединением заявкиПриоритет р 1 т л ц 61 16(40 П 1," 6 Комитет по делам зобретений и открытий при Совете Министров СССР. Субботин, В. Н. Майдан и Е. В. Вавилина явител СПОСОБ ПОИСКА ПАТЕНТНЫХ ДОПРИ 1 ОМОИИ ЦИФРОВЬ 1 Х ВЬ 1 Ч ИСЛ ИТЕ МЕНТОВНЫХ СИСТЕМ ать то чи. 1Известны способы поиска патентных документов при помощи цифровых систем обработки информации, когда документы и запросы представлены в виде совокупности цепочек слов, объединяемых при помощи логических операторов И, ИЛИ.При известном способе производят упорядочение слов запросов и документов. Упорядоченные по алфавиту списки слов сравнивают с учетом логических операторов, в ре зультате чего вычисляют вес документа с использованием весового критерия соответствия.Предлагаемый способ позволяет. реш такие задачи, как поиск ближайшего про типа и проверка объекта на патентную стоту.Он отличается тем, что анализируют цепочки слов и разделителей запроса и в зависимости от их структуры преобразуют раздели тели запроса в логические операторы; по адресу каждого слова цепочки в словаре считывают группы данных, задающие номера документов, содержащих данный адрес слова; осуществляют над группами данных ло гические операции, полученные в результате преобразсвания, и в том случае, когда результат очередной логической операции над очередной группой данных для слова и промежултачным результатом не задает номера 3 документов, содержащих заданную совокупность слов, объединенных заданными логическими операторами, данный оператор и слово опускают и,переходят к обработке очередного слова, По окончании обработки всех слов по номерам документов, заданных результатом, считывают таблицы соответствий упорядоченных по величине пар разделителя и слова и номеров, характеризующих положение данной пары по отношению к началу набора однозначно выбранных цепочек слов и разделителей документа. Из цепочек слов и разделителей запроса выделяют цепочки однозначно выбранных подцепочек слов и разделителей и формируют номера позиций пар слов и разделителей по отношению к началу однозначно выбранных подцепочек слов запроса, по которым выбирают соответствующие строки таблицы документа и по результатам сопоставления элементов таблицы для пар слова и разделителя запро са и документа формируют результирующий вектор соответствия, документа запросу. При гоиске ближайшего прототипа суммируют элементы результирующего вектора, формируют окончательные номера документов, соответствующие максимальной сумме единиц результирующего вектора. При проверке объекта на патентную чистоту суммируют количество нулей результирующего вектора, фор 3054792019памяти таблицы соответствий упоря;,очг 1 гных го величине пар разделителя и слова и номеров, характеризу 1 ощих положение да:ной пары по стнсшени 1 о к началу наоора однозначно выбранных цепочек слов и разделителей документа; из цегочек слов и разделиелей з"проса выделяют цепочки однозначно вь; - браьпь.х подцепочек слов и разделителей и форм:руют гомера гозиций пар слов и разделиелей г;о отношению к началу однозначно выбранных подцепочек слов запроса, по которым выбирают соответствующие строки таблицы документа и по результатам сопостав.ения элементов таблицы для пар слова и разделителя запроса и документа форм:руют результирующий вектор соответствия документа запросу; при поиске ближайшего прототипа сумм 11 ру 1 От элементы результиру- ющего вектора, формируют окончательные помес а документоВ, ссог Ветствующ 1 е ы аксималыой сумме единиц результирующего вектора; при проверке объекта на патентную чистоту суммируют количество нулей результирующего вектора, формируют окончательные номера документов, соответствующие минимальной сумме нулей резульгирующего векОр а; Вь,всдят ив 11 гча ь тгксы дскмгнтОВпо окончательным номерам,.,2. Способ по п. 1, Отличаюиийся тем, что,с целью новь:щения точности нахождения5 блюайшгго прототипа или патентов, гороча:цих патенпую чистоту данного осъека запроса, путем анализа слов и разделителейзапроса формиру 1 о однозначно зада" уюля запроса последовательность разделите 10 лей, слов и спгциальньгх индексов, а такженабор последовательностей раздглителей,слсв и специальных индексов для каждогодокумента, для которого определены окончательные номера, сравнивают последователь 15 ность символов запроса с каждой последователь:остью символов документа, вь;бираютиз набора окончательных номеров уточненныеномера документов для документов с максимальной суммой элементоВ уточнгп 1 ых рг 20 зульгирующих векторов при поиске бл 1 жа 1 щего прототипа; формируют уточненные номера документов для документов, соответствующих минимальной сумме нулевых элеменгов уточненных результиру 1 ощих векторов;25 выВодят на печать тексты документов поуточненным номерам.ыруют окончательные номера документов, соответствующие минимальной сумме нулей результирующего вектора; выводят на печать тексты документов пд". ОкОнчательным номерам. 5С целью Новьшеия точности нахождения ближайшего прототипз или патентов, порочащих патентную чистоту данного объекта запроса, путем анализа слов и разделителей запроса формируют однозначно заданную 10 для запроса последовательность разделителей, слов и специальных индексов, а так)ке набор последовательностей разделителей, слов и специальных индексов для каждого документа, для которого определены окончательные номера, сравнивают последовательность символов запроса с каждой последовательностью символов дроку мента; выбир ают из набора окончательных номеров уточненные номера документов для документов с 20 максмальО суммой злеентов уточненных результирующих векторов при поиске ближайшего прототипа; формируют уточненные номера документов для, документов, соответствующих минимальной сумме нулевых эле ментов уточненных результирующих векторов, выводят на печать тексты документов по уточненным номерам.На чертеже представлена блок-схема размещения массивов в памяти системы обработки данных, при помощи которой может быгь реализован предлагаемый способ.Реализация способа рассматривается по отношению к цифровым системам обработки 35 данных, содержащим массовуо память на магнитных дисках и магнитных лентах и оперативную память большого объема.Как документы, так и запросы представлены в системе с использованием специального 40 информационно-поискового языка, позволяющего описывать объект, его составные части, взаимодействие составных частей (отношения вксочения, соединения, взаимного расположения) и отношение между взаимодействия ми (альтернативой одновременности и последовательностч), что требуется для детальной передачи информации патентной формулы.Словарь информационно-поискового языка (ИПЯ) содержит Определенные фиксирован ные формы слов русского языка, интерпретация которых зависит от разделителя, предшествующего данному слову в цепочке слов и р азделителей. Отношения между частями и объектом задаются при помощи цепочек 15 слов, общий вид которьгх задается соотношеИеы (1):индивидуальный или групповой индексатор5,60ф 50 2 50%,д или %щ5,5,Р+2 5 зРИндивцдуальный или групповой индгксатор. 65 где:У, - слово из словаря, а индексаторы и разделители 5 о - 5 З позволяют задать смысл цепочки слов (1).Документы и запросы представляют собой совокупность раздельных цепочек лиоо цепочек, объединяемых при помощи дополнительных разделителей 54 и 5 ь задающих отношения между взаимодействиями.Для сокращения записей документов может быть также использован служебный разделитель 56, позволяющий объединить однородные члены по определенным правилам.Отметим, что индексаторы служат для различения эквивалентных объектов или их частей, задания группы эквивалентных объектов и выделения подгруппы эквивалентных объектов или частей. Индексаторы подразделяются на индивидуальные и групповые. Первые эквивалентны порядковым числительным естественного русского языка, последние служат для группового перечисления. Разделители 5, - 5 з задают определенные семантические отношения хежду словами У,. Не смотря на простоту синтаксиса на уровне информационно-поискового языка возможны неоднозначности, которые далее устраняются при автоматической обработке запросов и документов. Эти неоднозначности определяются возможностью использования во входных текстах синонимов, возможностью произволь,ного помещения пары разделителя и слова по отношению к цепочке слова и разделителя, возыожНостью выражения одного и того же смыслового содержания при помощи различных наборов разделителей и слов в цепочках слов и разделителей,Документы, записанные на указанном ин. формационно-поисковом язычке, вводятся в вычислительную систему с перфокарт. Запросы могут вводиться с помощью машинки с пульта оператора,Документы и запросы представлены на входе системы в форме последовательностей ДВОичных симВОлОВ. Прежде чем детально рассмотреть последовательОсть действий в соответствии с данным способом, рассмотрим основные элементы системы и требования к ней,. Для устр анения неоднозн ач:о той информационно-поискового языка нс:ользуется автоматический словарь слов В в котором синонимы получают одинаково ежаые коды, а информация в виде специальных меток В словаре и отсылки к сжатому коду синонима в совокупности позволяет осуществить унификацию не только слов запросов и документов, но и разделителей, т. е. осущестзить унификацию цепочек (1), выражающих определенные смысловые отношения.С другой стороны использование сжатых кодов понятий в системе позволяет повысить ее быстродействие при выборе однозначно задаваемых цепочек слов и разделителей прн анализе текстов запросов и документов, так как все слова представляются последовательностями двоичных знаков постоянной длины.Пу-Тем Выделения разделителей из 1;ходното текста и его госледовательного англ 32:,Ожно Выделить каждое слОВО ВходнОГО текста и направить его на вход автоматического словаря.ЛВтом 2 тическиЙ слоь 2 рь может Оыть О, ГгнизОВ 2 н нг Основе любых извест:1 ых принц:- пов с упорядочением слов в памяи систеь, причем каждому слову присваивается сжатый код, равный адресу первого байта этоо слова в словаре при отсутствии отсылк:1, к синониму, или адрес первого байта сино; Мг. Для поиска сжаОГО кода слова в автоматц- ЧЕСКОМ СЛОВ 2 РЕ МОЖЕТ ИСПОЛЬЗСВ 2 ТЬСЯ КаК известный поиск по дереву, так и кох:бцнированные методы, основгн ые на адресации по комб 1 нацзи первьх двух букв, получепги пар 2 метрОВ массива (ВерхнцЙ и никний а,- реса), проверяемых делением массива:сполам и сравнениемЕОГ т также испол 1,30 Ваться друГие тзвестные методы, ОснОВаннье на случаЙном преобразОВани кода несжатого слова в адрес, по иоторому хранится исходкое сово. Для корректировки автоматического словаря используются известиь;е методы поиска в словаре и добавления слов, отсутствующих в словаре, в специа. ьную сто часть с использованием одпссвязных спис;Ов и привязок к определенным словам. Сжатый код слова также однозначно згдает "." ес данных, задаюп их номера докуме тон данным сжатым кодом.Принципиально возможы два способа хранения инфОрмапии 0 номер 2 х документов, содержащих данный адрес:1) хранение позиционного года по данному адресу, в котором единица в 1-0 Г.озиции слова свидетельствует о присутствии сжгого кода в 1-ом документе, г ноль об отсутствии документа,2) Хранение упорядоченного списка номеров документов, н которых используется дгн ый адрес,Эта информация может бь;ть голучена нг зт апе ввода документов, нахождения адресов в авгоматическом словаре и коррекции позиционного кода или у:юрядоченного ст;иска известными методами - анализа нлц сравнения и внесения текущего номера,:ли ед.:- ницы. Ьнформацию 0 номерах документов с данных адресом целесообразо хранить па магнитных дисках, так как все адреса, от;осящиеся к одному затросу, могут быть опрошены и соответстнующе массивы могут быть переписаны в оперативнтю память системы за одно обрацение к диску, Кроме;ого, дпск позволяет хранить бо;ьшие масс;вы и;1 формации, обеспечивая достаточно быстрый гоиск.Отметим, что автоматический слорар Может храниться как в оператив;ой памят;1 системы, так и на м 2 гнитных б 21 гознак.Вводимая информация о докухентгх хранится н 2 12 ГнитнОЙ лене, так же, кгн прсдварительно подготов.енпые пг этапе ввода 305479 ,",скументсв тголиты, 01 носящиеся к данно у дОкументу. Документы на м гГнитнОЙ ленте хранятся В по ядке их ввода в систему.РаСП;.ЕДЕЛЕНЕ ОСНОВНЫХ МаССИВОВ В ОСНОВ ной и расширенной памяти системы для одного из возможных вариантов реализации способа представлено на чертеже.В основной памяти 1 гомещаются автома."еский словарь, рабочие ячейки памяти, 10 Ячеики програмыы Обработки, ЯчеЙки программы диспетчера. Лвтоматический словарь разме,ен в боке 2 ссновной памяти, программы его Органзгци - в зоне 3. Зона 4 .Сжет ис;ользоваться для буферного хране,: я документов и зап осов при их вводе, Рабочая проГрамъ 2 х 21:ится В Зоне б ОснОВнОЙ п 2 ъ 1 Я 11. В "01 е 6, 02 бочеЙ, дпп 2 ъ 1 и 1 ески размещаются дапнье, счтываемые с дисков, над которымц осуществляются логические 20 о:е, ации. Слово В автоматическом словаре:ОЖЕТ Запн 12 Ь РЯД ЯЧЕЕК, НВПРИХ 1 ЕР, ЯЧЕЙ- и 7 и 8, Для х. а;ен я слов переменной длины мскет ис;ользоваться часть слова 9.чзс.ь слова 10 используется для отсылок к 25 сл скимам, г часть слова 11 может использоваться для отсылок к новым корректируемым массивам.Б зоне б хр: нягся программы ввода доку:.;: Ов, поиска ближайшего прототипа и про ь"р 1.1 нз ге Гную чистоу объекта запроса, а такж п,огргмма-днс етчер для дина:,мческоо;ерераспределенця массивов в памя;и и вызовг подпрограмм обработки, При нахож;енин адреса занцси по данному сжа тому коу может использоваться один из индексьх регистров 12 вычислителя 13, назначене ,оторого - счет, сравнечие, анализ и побайтовые операции. Еля Обмена информац;е 1 между ос:Овной памятью 1, вычислите лем 13, магнитными д;,скгмп И и накопителя.и 15 нг магнитной ленте служит канал связи 16. В зоне 17 блока запп 18 может хргн:Ться сжатый код слова для поиска информации о но.; ерах документов. Каждый до е мент на маГНИНОЙ ленте 32 нимает массив11 переменной длины с тем же номером 1, ". о и поряд,овы 1 номер докуента, ЕЕомерчасти 20 Заиси н 2 маНИТНОЙленте, 1-епосредственно за номером могут 50 с; сдор=ь часть 1 для храпения длины массцва и часть 22 для хранения длины (1 - 1)-го массива.Ля более детальноо понимания способаосгновимся на математческих моделях до кумеОВ и 32.1 рссОВ, испо;.ьзуемъх В систем , а тгк:еа постановке задач поиска ближгшегз 1 рстотипг и проверки Объект 2 на патентную;пс от связанных ." указанными моделями. Описанию запроса н документа 600;. 1 Оыть постав;ен в Соо.ветстВце Граф,КотОЕО. О СОСтЬЕтгтВуЮаг ЦЕПОЧКИ (1),задающие взаимоотношения объекта и его сос;авнЫх чгсте 11, а гершпнам графа соответствуют оощце части дуг, идентичных даПой 65 В=.шие. Кроме того для сопоставимых дуг305479 графа (т. е. дуг, которь:е мсгут быть совмещены друг с другом) должны выполни,ься определенные отпошеРРя м,ж 1 у 11 ми, задагаемые прп ГОмощР раз елктелей 5, и 5,- При написании реферат 2, ОппсьВ 210 цеГО структуру объекта в соответствии с патепт- НОЙ ФОРМУЛОЙ, ВОЗМО)КПЫ,1 ОГРЧЕСКРЕ ПССООТ- вегствия между описанием объекта в документе и в запгосе, в основном связанные с тем, что определен.ые составые Часк ооъект 2 510 Гут быть проЩепы, ц;1 я устрапе 1 Ря таких логических неоднозначностей счп ается, что объект содержРП пепосрс,.стве;По все его, составные части и, кроме того, 1 Огу ОЫТЬ ЗадапЫ ОТНОШЕНИЯ Тина ,:2 СТЬ А ООЪЕЕ- та содержит часть Б). Ипдеесаторь. в опСании обьекта проставляются произвольно и служат для разлчснкя отдельных идентичных вершин графа.ХЗР 2 КТЕРНая ОСООЕН НОСТЬ Г 1 с 1)2 МОДЕЛР СО- стоит в том, что дуги, зада 1 огцпе Отпоше 1:11 я вкл 1 очепия между обьзктом и е;о частя)11, 2 также между час 51 МР 1, Обр 23 От 3 Гэ афе, В котОрО."1 пе устранены Р 1 еодп 031.21 поси32- дании отношения включения, дерево. В общем случае граф, задающий запрос, может содержать большое количество идсн- ТИЧНЫХ ЧЗСТЕИ ООЪЕКТ 2, 51 ЕжУ ЕОТОРЬМс 32- даны отношепкя одного ткг;а - соеди 1:е 1:.я между частями.Критерием подобия запроса и документа является количество сопоставимых дуг Графа запроса и документа, для которых выполп 51- кгся отношения, задаваемые при:1 омощи разделителей 51 Р 1 55 Под СОПОСТаВИМОСТЬЮ ПОПИМ 2 ЕТС 51 1.2 Л:ЧКЕ в двух сопоставляемых цепочках типа (1), преобразованных при помощи авто.;атпческого словаря, цепочек смволов, задающих а;, 5 Угде а, - группа символов, определяемая направлением движения по дуге 5; =; разрешенных разделителей; У; - пр "образованное при помощи азтоматического словаря слово 1151 (сжатый адрес с учето синон- мов) и а 1, 51 Ус, для первой и ВтороЙ цепочек типа (1), таких, что каждой цепочке а 1,51,Ут, мо)кет быть поставлеп 2 В соответ- СтВИЕ КаКая-ЛИбО цЕПОЧКа а 7,51,У 7 ИЛИ ПаО- борот, СопоставР.Ые д;ГР 1 должнь Оьсть связаны разделителями 51 и 5 Б как в первом, так и во, втором графе. В качестве ближайшего грототипа выб- рается объект, задаваемый документом, для которого мера, задаваемая данным критер 1- ем, максимальна, Прк проверке на патентную чистоту для е 2 ждОГО Гр 2 фа документ 2 и дашюго запроса вычисляется ксличест о дуг графа запроса, которое не мс.ет бы:ь СОПОСтаВЛЕПО С дуГаМИ ДСЕуМЕнта С усЕТОМ От 1 ошен 11 Й, задаваемых рссзделителя ми 5:, и 5-, Патенть, порочащие патентуо чкстоту проверяемого объекта, должны иметь меру,равную нулю. Ин "ексаторы, имеющиеся Во входном явь:ее, позволяОт 1:реобразовать ВХО ;НОЙ ТЕСТ В СООРВЕТСВУРСЩ:Е МОДЕЛИ ДО- ку.; ента и за;роса.5 В связи с тем, что к Оыстродействию системы предъявляются особые требования, свя- ЗаННЬ)Е С ОбЕСПесЕНИЕМ ВОЗМОЖНОСТИ ОПЕра тивпого изменения запросов, используются 10 две 11 ромежуточнье модели. Связный графмодели объекта может быть преобвазовап в дерево, дуги еото рого задают опошения В 1 ЛОсСЭкя М;жду ОбЪЕКтОМ и ЕГО ЧаетяМИ, ко:орые также задают направления в дереве 55 от обьета к его частям, не содержащим как: х-лиоо др,гкх час)ей, Вершгны д рева оп 13 еде)5 юзся наоорамР преобразованных при ОМОЩР 2 ВТО.121 КЧЕСЕОГО СЛСВсРЯ (ЕЯРКДОЕ С;ОВО А Зс,МЕ 11 ЕПО СООТВЕТС Ву 10 щР 31 АЬ ГДЕ 20 А; - с)катьЙ код данного слова) конструкц 1:и типа 1 с общей частью вида:(2) индивидуальный или гп.Новой кндексатор А 5 ДА.,Аз Ь,;А .ИндРВидуальРЫе инд:есаторы при этом заменяотея разделктелем 57. В этой упрощен.Ой модели не учитькается произвольный характер расста. овкк ипдквидуальных ипдеесаторов, которые пспользу 1 отся только для преобразования исходного текста в уОрядо,енные цепочки слов и разделТелей. Так как В дереве однозначно заданы ориентирован;ые пе;и, соединяющие объект (качало) с коне 11;ь 1 ми частями (висячи:1 и вершинамп), 35 то в результате анализа входного текста последний:.0)кст бьть преобразован в совокуп СТЬ ПРЕООРазопа 1 НЫХ 11 УнифИЦКРОВВННЫ.; :осредством автоматсческого словаря и проГрамм упфкеации цепочек с;, (где с - ин деке вершины вдоль нап,авленного пути отьершпы дерева, задающей объект, к висяверп;ине;- индекс, задаощий порядковый номер конструкции, относящейся к Д 2 Н П О Й В Е Р Ш Р. П Е ДЕ Р Е В 2, 1. О 0 Т Р О Ш Е 1. П 10 К КО торой гсе конструкции такого типа находятСЯ В 01 П 01 са Н:1 Р 1 2 ЛЬТЕРИ 2 ТР 1 ВЫ, 2 с - ИРДЕКС цепи) вича:(5) 5750 или групповой индексатор А,5,А, 5 А,Сь /Рсл Ат.А, - 5 зА, 1,5,с 5или груП)оной индексатор АЯА, 5,РР 7(структура цепоптк)с,60 Лодель объекта полмчаегся путех: объедкс= ссгз Госрсдством оператора И в пре - елах Й =-:. Сопз,= 1, 2, 3 и групп с разлкчымп Й посре-,ством оператора 65 И.И.(4) С, (5,) С, (5,) ИЛИ ИЛИ Сг ИЛИС 10 121 ИЛИ Огг ИЛИ ИЛИ ИЛИ ИЛИ И ИЛИ И(6) ИЛИ ИЛИ Я 1 Д ИЛИ ПЛП ПЛИ ПЛИ 1 ЛП ИЧИ ИЛИ С 1,ИЛИ(5;)ИЛИ ИЛИСи С ИЛИ С, и 61 г ИЛИ ИЛИ ИЛИ 25"1;д.,)1/И С, ((5 ) Цепочки разделителей и сжатых кодов слов 4(а), 4(в) и 4(с) представляют собой параллельно-гослсдовательные цепи из Конструкциии типа (3),Дспслп:телыыг Отношения мекду В 32 ПМО- действяи Зада 10 тся цгпочкади Вида: (5) С 1 д,5 и С д и также представляют собой параллельно- последов ательные цепочки.Модель объекта, задаваемая состношгнпя. ми (4) и (5), может быть преобразована в более простые соотношения, используемые для промежуточного поиска, путем замеы разделителей в каждой из цепочек на логический оператор И для неповторяющихся разделителей и на логический оператор ИЛИ для повторяющихся раз елителей, объединяемых в скобках при задании порядка выполнения логических операций, операторов (5,) - И на ИЛИ в соотношениях (4), разделителей 54 или 52 на ИЛИ в соотношениях (4), а также соответствуощих А; на У;, где У; - группы данных, задаопцие номера доеу ментОВ, ссдгпжащих д 21 ный 2 дрес А; слова, позволяют получить программу, задасщую предварительный поиск документов, удовлетворяющих данно.;у запросу. Когда Уд представляет собой вектор дл:иоп в Л двоичных разрядов, в котором в 1 г-см разряде содержится 1, если данное СЛОБО 11 содержится в Й-ом документе (Л - количестго доумстсв 1, ссэт 1 сшгппя (3), (4), (5)Ог; Оьть пзесоагзсвапы Б поограъму Обоабстеп БсетОрОБ 1;1;, где- ГО 1 ЯДЕОВый НО- мсп с,.ова Б ц,.с:;1 с ГЛОБ и раздглптслгп (д).5;.1 та ПБСГПаю а задается Состпошгн:еч БПИЛИ ИЛП ПЛП, , ИЛИ, , ИЛИ ЯТ 11 С,;.Я 11 дт И Я 1 1111О С 11-1 т 1 тт 1,1 Ф0ГдЕ Я 1, =.1. П (У,г ИЛИ .1"11"и 11,1,пчиЗбв ссствгтствн:1 с ссотпсшгнпгх (3),Обработка векторов Может п 130 пзвсдитьсяПО ЧаСТЯМ В СООТБЕТСТВПИ С ПРОГР 2 ммсй, 32 Д 240 Баемсй соотношением (6), слева направо.Когда Уд задается списком номеров документов, операпия И эквивалентна нахождению общих злегсентОВ ссотВетстВм 10 щихсписков, а операция ИЛИ - слиянию двух45 списков.Как видно из соотношения (6), последовательность Я 1;.1, задаваемую некоторой датрицей, целесообразно обрабатывать, пробегаявсг з,ачгния 1 и /г для . = сопв, а затем уве 50 личивая 1 на единицу,.1 10 связано с тгм, что Опер ация И на"х 02 кдг-.Ия Одина:Оных элгд:гнтОВ сппскОБ пропропзводпт"я только в гределах Я 11 д,причем сна может свести множество номеров55 домме:тсв., зад 2 ваеъых ее ргзультатсх, спу;евому. Сднаес, когда таеиг результатыполч 2 ются 1:; 1 с бр асстег, 2 пр имер, послед его 1:о поядеу Я;,д общение потребителя " Вычислительпой системой станов:тсяб 0 1 гвсз:Ожпым, т 2 е еак м 2 шпн 2 нг Выдает ниОдин дое 1 мент.Суцсствс с;10 С 002 сводится к тсд 1, что,анап 3 гУЯ Цг:ОЧЕ С;.ОВ П Р 23 ДгЛИТСЛгй 32 проса, цифрова 1 Бь;числтельная системабб пресбргзует целони слов запроса в адресрЛ;, по котогь 1 м хранятся соответству ощие группы данных ;, задающих номера документов.Текст запроса путем анализа раздсли 1 е:Сй преобразуеся в форму, задаваему 10 соогпошением (6), которое опр "деляет 1;оследовательность и логические операции над сооВетствующими 1;1,. Когда промежуточный реобрабоки при логическо умножении промежуточного результата на очередной Ъ 4 м (или определснии общих комаров списков) станос р авных Иул 10, запрос поставлен некорректно, причем последнее добавляемое У,р целесообразно пропустить, а коррекцию (исходное слово запроса) вывести на печать. Коррективы необходимо произвести в модели, задаваемой соотношением (4) - про. пуск ссответству 1 ощей части С 1 ь а такке в полном графе запроса. В резуль-.ате обработки Г;,1, получается вектор Я, задающий номера документов, удовлетворя 1 ощ 1 готдельным условиям, сформулированным в запросе, Среди них может содержаться большое количество документов, не имеющих отношения к запросу.Так как более точной моделью объекта запроса является модель, задаваемая соотношениями (4) и (5), в которой требуется учитывать не только неопределенности по, сщения слова по отношению к цепочкам идентичных разделителей, но и логические неопределенности, определяемые возможным пропуском определесн 11 ых частей объекта по отношению к отношению включения, необходимо задать соответствие между парой разделитель -- сжатый код слова цепочек вида 4(а), 4(в) и 4(с) и их положение в преде;ах этих цепо:Ск с учетом неопределенностей,Правила присвоения порядковых номе;ов идентификаторам (разделителю перед словом и слову), составленные с учетом этих неопределенностей и рефлексивности копструкций (3), таковы:а) при просмотре цепочки типа 4(а) по мере увеличения 1 все идентификаторы 57 или групповой индексатор А, для 1= 1 получают номер 1;б) при просмотре параллельно-последовательной це 1 точк 11, задаваемой соот 11 ошениями (3), (4) и (5), разделители 5 И 5, присваивают содержащим их идентификаторам комер на единицу бол 1-ше номера ближайшего идентификатора с разделителем другого типа, расположе 11 ного левее;в) при просмотре идентификаторов слева направо с учетом правила б номер увеличивается на едип 11 цу при гсреоде к каждому отличному от предшествующего идентификатору;г) при распараллеливании цепочек (точки 58, 54, 55) В соотношених 4(2), 4(в) и 4(с) и 5, начиная с максимального номера 1, присвоение, номеров для каждого нового отрезка последовательно-параллельной цепочки т 14 па 510 15 20 25 30 35 40 45 50 55 60 65,а) производится согласно прав:лам а, 0 11 Г;Д) и;. обна" ужении разделителя 5, или -"-, (как и 5;, 1,и) 1:оследне 1;ь 1 пускаюгся;е) после пропуска 54 номера присваиваю 1- ся НО щавила 2, О, В и Г, каж;ы раз качйпая с единицы;ж) номер идсктификатора, следующего за 5 ь которы, в свою очередь, следует за просмотрсш ым параллельным набором идентификаторов, ка сдиницу большим аксимального комер 2 и:е 1;тифК 2 т 012 п 21 аллельного набора,1 нф 01 мацию 0 к 2 ждом Доклхнте удобно ранигь на магнитной ленте в виде упорядоченной по вел: чине идентификатора таблиць. в форме матрицы, количество строк которой ссотве-.ствует количеству имеющися в документе различных идентификаторов, Кол 1 чество столбцов матрицы соответствует количестьу параллельно-последовательных цепочек типа 4 а, 4 в, 4 с 1 ли 5.Каждый элемент таблицы содеркит упорядо енную в порядке возрастания последовательность комеров, присвоенных данному идентификатору в пределах данной паралле;.ьпо-последовательной цепочки. Г 1 ля сравненпя загроса с предварительно отобранными документами его преобразуют в матрицу запроса, количество столбцов которой соответствует количеству параллельно-последовательных цепочек. Идентификаторы упорядочивают в пределастолбцов с их возможны повторением так, чтобы порядковые номера, присвоен 1 гые элементам без учета пропуска элементов В какдом из столбцов, Образовали :еубывающую последовательность из номеров, Вь:оирая идентификатор каждой строки .атркцы запроса и по нему все элементы соотвеч ству 1 ощей строки матрицы окумепта, разделяя номера одного элемента запятой, а 1 азньэле 1 оптов - оч с эяой, можно сформировать расширенную матрицу запроса, присоедикяя к данному элементу всю строку элементов матрицы документа и помещая нх в скобка.При отсутствии какого-либо элемента в матрице запроса и документа ставят 0, Рас 1 пиренная .1 атрица пре 0012 зуется д 2 лее в матрицу весов по следующим правилам:2) нулю в скобке при пенулеьом элементе перед с 1(сб 1.ОЙ ст 2 Вится В соответс. Вие нуль Весового Вектора, соответствующего данному элементу;б) если номсп элеме 11 та запроса, стоящий пессд скобко;";, 0, все элементы весового Век;Ора, соотвегств 101 цпе элемента в скобке, приобре Таот значение 1;в) первому эле, енту в кажой строке раскп:енной матрицы ставится в соответствие весовой вектор (1; 1; 1 1; 1), где количестВо едппц соответствует количеству столбцов В матрице доку:ента, только тогда, когда фекл ор расширенной матрицы имеет вяд 1 (1; 1;1; 1);305479 14 5 10 Таблица Последовательность разделителей в частном виде конструкции (3) Разделитель идентификатора2,1 2,3 3,4 2,1 2, 3, 4 3,4 г) при госледовательном движении идентификаторов с групповым индексатором или 57 каждому элементу расширенной матрицы в скобках ставится в соответствие единичный элемент весового вектора, если порядковый номер перед скобками меньше номера сопоставляемого элемента в скобках или равен ему, и нуль - в противном случае;д) путем анализа идентификаторов вдоль столбца для запроса для всех элементов, кроме элемента с первым слева групповым индексатором или 57 в конструкциях вида (3), проверяют выполнение равенства суммы ноВ этой таблице 1 - групповой индексатор; скобки означают присоединение данной конструкции через ИЛИ; элементы таблицы соответствуют поправкам.е) после разделителя 54 следующему элементу в скобках расширенной матрицы присваивается 1 весового вектора, когда для первого идентификатора после данного выполняется условие в, а для последующих - согласно пункту г или д;ж) после А-го разделителя 55 в их последовательной цепочке требуется, чтобы сумма данного номера вне скобок плюс все поправки, определяемые с цепочками разделителей, согласно таблице, вплоть до данного разделителя соответствовала номеру данного элемента в скобке, что позволяет преобразовать последний в единичный элемент весового вектора в соответствующей позиции. Таким образом, каждый элемент расширенной матриты преобразуется в соответствующий весовой вектор, содержащий наборы 1 и О. Далее все векторы вдоль каждого столбца поразрядно перемнокаются. Это позволяет вьгделить частично совпадающие параллельно-последовательно цепочки для документа и запроса. Затем все векторы столбцов суммируют по тосУ 2, что позволяет выделить количество совпадающих цепочек, и получают результирующий, вектор соответствия документа запросу. Этот вектор определяется моделями (4) и (5). Суммируют все элементы результирующего вектора, количество которых совпадает с количеством параллельно-последовательных цепочек. Сумма единиц этого вектора может быть принята за меру совпадения документа запросу. Для каждого документа хранят эту меру и номер документа. 15 20 25 30 35 40 45 50 мера первого слева идентиф 1:.катора с групповьпм индексатором или 57 документа, задаваеа;ого номером в скобках расширенного вектора, с поправкой гз таблицы, в зависимости от вида разделителя и частного вида конструкции (3), и для всех элементов, для которых выполняется равенство, проверяют, больше данный элемент элемента перед скобками или равен ему. При выполнении этих условий в весовом векторе в соответствующей позиции, для которой выполняется данное условие, устанавливается 1, а при невыполнении их - О,Далее документы сортируют по величине этой меры, и все номера документов, для которых мера максимальна, представляют собой окончательные номера, по которым информация о тексте документа, хранимая на магнитной ленте, может быть выведена на печать. Сумма нулей результирующего вектора является мерой несовпадения документа и запроса. Для каждого документа хранят эту меру и номер документа в виде таблицы. Сортируя по величине меры таблицу, можно получить номера всех документов, для которых мера минимальна. Когда мера равна нулю, документ порочит патентную чистоту объекта запроса. Матрицы, таблицы и векторы мо. гут храниться на магнитной ленте в виде односвязанных списков. Обрабатывать эти списки с их преобразованием в результирующие векторы можно по частям,Запросы можно обрабатывать с высоким быстродействием, так как матрицы документов могут быть предварительно погдотовлены на этапе ввода документов, когда не требуется существенного быстродействия системы,По окончательныц номерам выходные тексты, также хоанимые на магнитной ленте, могут быть выведены на печать.Обладая высоким быстродействием, данный способ поиска ближайшего прототипа или объектов, горочащих патентную чистоту объекта запроса, позволяет вывести все документы, относящиеся к запросу, на печать, однако вследствие неучета индивидуальных индексаторов, а также привязок отношений между взаимодействиями (5) с результатами сравнения, полученными для однозначно сформированных цепочек слов и разделите 3054791516лст, возможны нсзотпости В Вы;аче:оку."с:- тОВ. ДруГИМИ СЛОВаМП, Козффнцнсит ПО;тоты Б 1 датт;ьх докумецОВ бде удовлс ВО.:целен, однако, коэффициент релевантнссти для запросов, содержащих большое количсство ОДП 01 ипных ас 1 си В Ооьскте Запроса, це б- дст удовпетго 01 тельныз.РслсваТнссть можно улучшить, испол,зуя более сложные способы по;ска, основацпьс на анализе модели документа и запроса в в 1- ;е графа с ограничениями ц подсчете колячества сопоставимых дуг графа запроса и документа, а также несоОставимых дуг Графа запроса ц графа документа согласно рассмотренным ранее кр иериям. Чтобы изб жат ь обьчного перебора и учесть все топологическце отпогненця между дугами графа, в;ачалс рассматривают графы запроса и документа Оез огранцченц. Такие графы хОгут Оыть получены путем анализа входных текстов с учетом индексаторов и синтаксических цепочек типа (3), также пх общих частей, задаощих вершины графов. Так как в общем случае графы могут представлять собою деревья и не быть сильно связанными, т. е, ка;кдая их дуга может принадлежать какому-либо простому циклу, при построении матрицы смежности исходного гр а фа необходимо вт:ести фиктивные дуги, число которых таково, что исходный граф превращается в сильно связанньй, причем базовый набор независимых ЕГО ЦИКЛОВ СОДЕРЖИТ МИНИМаЛЬНОЕ КОЛИсЕСтзо ьиклов, Для эоо по матрц 1 е смсжцоси находят каркас графа, определяющий какой- либо набор нсзависцмых простых циклов. Для дереВьеВ К 2 ркас совпад 2 ет с исходных графом-дерево.;т. Далее анализируют выброшенные из графа дуги, в результате выбрасываия которых построен каркас. 1 хаждая выброшенная дуга определяет едцнсгвеппый простой ци,л Оазового набора цц,лов. Выделиотея слыо связанная часть графа;1 дсРеВь 51. ДЛЯ КЗЖДОй СИЛЬНО СВЯ 32 ццой 2 СтИ графя путем паправлсшого объедппсшя циклов базового набора и анализа получс;шых циклов пегвопачальный базовый набор незаВцсимых циклов преоб 1 З 23 уется В наоор независимых базовых циклов мипмальной суммарной длины, обладающий свойством цньариаГгпости го отношен;ю к изоморфизму и цзоморфному Гложению графа в граф. Нсатборы так:х незав;симых циклсв могут бь 11. Поставлены во взаимоодпозцачпое соответств:е в смысле длин независимых циклов. Лгалцзи- РУ 101 СЯ ВИСЯЧ 1 Е ВЕРШИНЫ КВЖДОГО ЦЗ ДЕЕВЬ- ев, а также находится вершина, цаходятцаяся ца расстоянии :1 от общсц всрш.Пы даного дерева ц сильно связан:ой части графа такая, чтобы опа не являлась вершиной дуги, принадлежащей каких-либо двум независимым циклам базового набора сильно связанной части. Висячие вершины и выбранная Вершина должны быть соединены между собой фиктивными дуГами. Для введения помеченных единиц в матрицу смежности исход 5 10 15 20 25 30 35 40 45 50 55 60 65:ого графа 1 для фиктивных дуг) образуется какой-лцоо цикл цз фиктивных дуг, проходяш.1 й через Рсе В:1 сяч:с Вершины и Выов 2 нную вершину. После изменений по новой матрице смежности определяют нозый набор незаВ 1.сцмь 1 х 1 иклов мцпимал 1 ной длцн 11. 11,иклэматическую матрицу для этого набора аналзцруот, присем находят такой поднабор циклов, задаваемых ею, чтобы все циклы оставались,связанными друг с другом, но содержали минимальный набор независимых циклов минимальной длины, задающий все пефиктивпые дуги.Путем перебора (направленно суммируя по ной 2) простые 1:езависимыс циклы мцпиалцОго 1 абора, которые могут быть ооозначены какими-либо индексами или привязками, зная цх длины, вычисляют длины всех простых циклов сильносвязанного графа и формируют из цих поисковуо таблицу. Таблц,ы упорядочснцого набора длин, а также кодированные обозначения простых циклов, ПОЛУ 2 ЕМЬЕ ИЗ НЕЗависи:Ых ПИКЛОВ мальпой длины, показывающие, какие из этих циклов объединены, позволяют быстро найти все дуги графа, входящие в данный простой цикл. Таблицы данных всех циклов графов документов вместе с их привязками к дугам этих графов получают на этапе ввода документа и хранят па магнитной ленте. Таблицы всех циклов запроса получают в процессе уточненной ооработки запроса, так же, как и СРСТЕМ а ПРИГЯЗОК ПОЗВОЛЯЮ 1 цая ПсрЕЧИСЛИТЬ все дуги гдоль этого цикла, начиная с любой из пцх, либо по часовой стрелке либо против нее. Для запроса и документа выбирают такие т;аксимальные по длине циклы запроса цли документа, чтобы в таблицах разница между их длинами была минимальной. Предпочтение отдается циклам одинаковой длины, а если это цевозможпо, Выбирают циклы с минимальной разницей. Очевидно, что такие циклы всегда могут быть наложены друг на ;,руга. Для выбранных в результате анализа таблц 1 для заданного запроса и документа циклов составляОт кодовые последовательности. 1 хэлцтество различных максимальны циклов не может превысить количество элементэв базовых наборов и в общез случае невелико. При ссставлении кодовых последовательностей дуги графа запроса персчисляОт, начиная с любой дуги этого максимального цикла, причем для каждой дуги помещают привязку к сгискам упорядоченньх ЭЛЕМСНТОВ, ЗссОЩИХ СПИСКИ КОДОВ, анаЛИЗИ- руе.,тых прц определении согоставимости дуг, ЕСЛИ ДУГ 2 .ЕЖИТ На ДВННОМ М 2 КСсмаЛЬНОХ 1 цикле. Однако привязка помещается со специальным: цдексом, если она впервые встречена при обходе и ее оба конца лежат на максимальном цикле, причем по крайней мере дважды: коГда ду Га Встречена первыЙ раз при обходе и затем - когда она встречена второй раз. Если какие-либо части графа загроса несовместимы с рассмотренной систе.17мой кодированияимеются еще какие-либо наборы циклов, содержащие дуги, не лежащие на сравниваемых максимальных циклах), то специальные индексы задпот указанные участки, которые далее могут оыть сопоставлены, отдельно. Для докуме;та составляют последовательность 2, где а - днна цикла последовательностей, начиная с каждой дуги на цикле и перечисляя дуги как по часовой стрелке, так и прогив нее. Последовательность может быть составлена один раз, а все остальные могут быть получены циклическими перестановками и реверсированием порядка. Правила кодирования аналогичны уже рассмотренным.Каждую последовательность для запроса сопоставляют с каждой из последовательностей для документа путем выбора по привязкам к соответстствующим спискам кодов для дуг запроса и документа соответствующих списков, их слияния и сравнения результирующего списка с исходными по количеству элементов,Если дуги сопоставимы, ни одна из них не является фиктивной, лежат они па максимальных циклах и имеют одинаковы: - привязки с разделителем 5, (55) к позиции дуги, связанной с данной разделителями 5(5;) 1 см. соотношение (5) , то в результирующую последовательность вносят элемент аь в противном случае - нуль. Если дуги сопоставимы,.ни одна из них не является фиктивнои, но дуги не лежат на максимальных ц;клах, имея оба конца на максимальных циклах, проверяют принадлежность дуги одинаковым наборам базовых независимых циклов минимальной длины по их длинам, и, если эти наборы идентичны, вносят элемент а,/2. Здесь также требуется учить:вать привязки между дугами с учетом их переменных позиций, а также соотношение 5) .При наличии наборов циклов вне максимального сопоставления наборов требуется найти наиболее близкие по длине максиальные циклы для этих частей и получить соответствуОщие а; и а;/2 в составляющих результирующих векторах, которые вставляотся вместе с нулем в позиции этих сравниваемых наборов. Инами словами, 1 от же процесс составления и сопоставления кодовых последовательностей касается частей, которые не вошли в первую результирующуо последовательность.Результирующая последОВателы 10 сть - ьектор, содержащий наборы аь а;/2 и частные суммы а, и а,/2, не вошедшие в первый максимальный цикл, Количество таких последовательностей определяется Величиною 2;,", где г - количество максимальных цклов данного запроса.Отетим, что а; в результирующей последовательности при учете одного лишь пересечения дуг принимает значение 1. Это це 18лесообразно при проверке объектов на патентную чистоту. Для поиска прототипа может потреооваться учет позиции дуги В дереВе включения. При обраоотке модели, задаваемой соотноцениями (4) и (5), дугам могут быть прип:саны веса а; в зависимости от их 11 ринадлежности определенному уровню в направленном дереве включения.Пусть Й минимальный номер уровня, на 10 котором появляется данная, дуга. Тогда а; == 2 - ". В Отдельных случаях можно счгтать а; = 1 для всех дуг (для упрощения последователы ости действий), При поиске ближайшего прототипа для каждого результирующе го вектора вычисляют сумму всех а и а,/2ПО Всем значениям г (порядковоъу номеру дгг при их квазиупорядочении) и для данно докуъента Выбирают макси.алыую суъ- му. Среди всех докумегтов выбирают доку мент с гаксимальньи знаением т 2 кой суммы.Прп проверке объекта на патентную чистоту вычисляют сумму нулевых членов о всем г и Вь;бираот ми.иум такой су 1 мь. Среди 25 всех документов выбирают документы с минималы;ым или нулевым значением такой суммы,Уточненнь.е значения результирующих векторов соответствия документа запросу полуЗ 0 чают для малого колпчества документов, Обнаруженных в результате обработки по упрощеным моделям, вследствие чего быстродействие системы снижается несущественно.Предмет изобретения1. Способ поиска патентных документоври помощи цифровых вычислительных си сем, при котором патентные документы и запросы представлены В виде совокупности цепочек слов, объединяемых при помощи логических операторов И, ИЛИ, от,ггчагогггиася тем, что,тс целью решения таких задач, 45 к 2 к 1 оиск Олижайшего пр 01 Отипа и проверк 2объекта на патентную чистоту, анализируот цепочки слов и разделителей запроса и в зависимости от структу-ы цепочек слов и разделителей преобраз;ют разделители запроса 50 в логические операторы, го адресу каждогослова цепочки в словаре считывают группы данных, задаюц;ие номера, документов, содержащих данный адрес слова, осуществляют над группами данных логические операции, 55 полученные В резльтате преобразования, ив том случае, когда результат очередной логическои о.ерации ад очередои группой данных для слова и промежуточным результатом не задает номера документов, содержа щих заданную совокупность слов, объединенньх зад 2 Н 1:ыми логическими Опер 2 тор 2 ми, то данный оператор и слово опускают и перехо- ДЯТ и ООР 200 ТКЕ ОЧЕРЕДНОГО С:ОВ 2; ПО ОКОН- чании ООГ 200 тк:1 Всех слОВ по номера доку ментов, заданых результатом, считывают из