Известны спосо бы поиска патентнььх документов при помощи цифровых систем обработки информации, когда документы и запросы представлены в виде совокупности цепочек слов, объединяемых при помощи логических операторов «И, «ИЛИ.
При известном способе производят упорядочение слов запросов и документов. Упорядоченные по алфавиту списки слов сравнивают с учетом логических операторов, в результате чего вычисляют вес документа с использованием весового критерия соответствия.
Предлагаемый способ позволяет, решать такие задачи, как поиск ближайшего прототипа и проверка объекта на патентную чистоту.
Он отличается тем, что анализируют цепочки слов и разделителей запроса и в зависимости от их структуры преобразуют разделители запроса в логические операторы; по адресу каждого слова цепочжи в словаре считывают группы данных, задающие номера документов, содержащих даняый адрес слова; осуществляют над группами данных логические операции, полученные в результате преобразования, и в том случае, когда результат очередной логической операции над очередной группой данных для слова и промежуточным результатом не задает номера
документов, содержащих заданную совокупность слов, объединенных заданными логическими операторами, данный оператор и слово опускают и .переходят к обработке очередного слова. По окончании обработки всех слов по номерам документов, заданных результатом, считывают таблицы соответствий упорядоченных по величине пар разделителя и слова и номеров, характеризующих
O по.)ож€ние данной парЫ по отношению к началу набора однозначно выбранных цепочек слов и разделителей документа. Из цепочек слов и разделителей запроса выделяют цепочки однозначно выбранных подцепочек
5 слов и разделителей и формируют номера позиций пар слов и разделителей по отношению к началу однозначно- вы.бранных подцепочек слов запроса, по которым выбирают соответствующие строки таблицы документа ,и
Э по результатам сопоставления элементов таблицы для па:р слова и разделителя запроса и документа формируют результирующий вектор соответствия документа запросу. При поиске ближайшего прототипа суммируют
5 элементы результирующего вектора, формируют окончательные номера документов, соответствующие максимальной сумме единиц результирующего вектора. При проверке объекта на патентную чистоту суММируют колимируют окончательные номера документов, соответствующие минимальной сумме нулей результирующего вектора; выводят на печать тексты документов окюнчательным номерам. С целью повышений точности нахожделия ближайшего прототипд или патентов, порочащих патентную чистоту данного объекта запроса, путем анализа слов и разделителей запроса формируют одиоз«ачно заданную для запроса последовательность разделителей, СЛОВ и специальных индексов, а также набор последовательностей разделителей, слов и специальных индексов для каждого документа, для которого определены окончательные номера, сравнивают последовательность символов запроса с каждой последовательностью символов документа; выбирают из набора окончательных номеров уточненные номера документов для документов с максимальной суммой элементов уточненных результирующих векторов при поиске ближайшего прототипа.; формируют уточненные номера документов; для. документов, соответствующих минимальной сумме нулевых элементов уточненных результирующих векторов, выводят на лечать тексты документов по уточнеииьгм номерам. На чертеже представлена блок-схема размещения массивов в памяти системы обработки дапных, при помощи которой может быть реализован предлагаемый способ. Реализация способа рассматривается по отношению к цифровым системам обработки данных, содержащим м ассовую память на магнитных дисках и магнитных лентах и оперативную память большого объема. Как документы, так и запросы представлены в системе с использованием специа.льного информационно-поискового языка, позволяющего описывать объект, его составные части, взанмодействне составных частей (отношения включения, соединения, взаимного расположения:) и отношение между взаимодействиями (альтерпативой одновременности и последовательности), что требуется для: детальной передачи информации патентной формулы. Словарь ннформационио-иоискового явыка (ИПЯ) содержит определенные фиксированные формы слов русского языка, интерпретация которых зависит от разделителя, иредшествующего даниом-у слову в цепочке слов и разделителей. Отношения между частями и объектом задаются яри помощи цепочек слов, общий вид которых задается соотношением (1): индивидуальный или групповой индексатор 5, W,S,W,., . S,W или ТГ„,1 , - слово из словаря, а индексаторы и разделители SQ - 5з позволяют задать смысл цепочки слов (1). Документы и запросы представляют собой сово.кунность раздельных цепочек либо цеиоче.к, объединяемых при помощи дополнительных разделителей 54 и S, задающих отношения, между взаимодействиями. Для сокращен1ия записей документов может быть также использован служебный разделитель 5б, позволяющий объединить однородные члены по определенны-м прави там. Отметим, что индексаторы служат для различения эквивалентных объектов или их частей, задания группы эквива.чентных объектов и выделения подгруппы, эквивалентных объектов или частей. Индексаторы иодразделяются на индивидуальные и групповые. Первые эквивалентны порядковььм числительным естественного русского языка, последние служат для группового перечисления.. Разделители 5о-5з задают определенные семантические отношения между словами Wi. Несмотря па простоту синтаксиса па уровне информационно-иоискового языка возможны неоднозначности, которые далее устраняются нри автоматической обработке запросов и документов. Эти неоднозначности определяются возможностью использования во входных текстах синонимов, возможностью произвольного помещения пары разделителя и слова по отношению к цепочке слова и разделителя, возможностью выражения одного и того же смыслового содержания при помощи различных наборов разделителей и слов в цепочках слов и разделителей. Документы, записанные на указанном информационно-поисковом языке, вводятся в ВЫчислительную систему с перфокарт. Заиросы. могут вводиться с помощью машннки с пульта оператора. Документы и запросы представлены на входе системы в форме последовательностей двоичных символов. Прежде чем детально рассмотреть последовательность действий в соотвеЛтвии с данным способом, рассмотрим основные элементы системы и требования к ней. Для устранения неоднозначностей информационно-поискового языка используется автоматический словарь слов W, в котором СИНОНИМЫ получают одинаково сжатые коды, а информация в виде специальных меток в словаре и отсылки к сжатому коду синонима в совокупности позволяет осуществить унификациЮ не только слов запросов и документов, но и разделителей, т. е. осуществить унификацию цепочек (1), выражающих определенные смысловые отношения . С другой стороны использование сжатых кодов понятий в системе позволяет повысить ее быстродействие при выборе однозначно задаваемых цепочек слов и разделителей при ак.ализе текстов запросов и документов, так как все слова представляются последовательиостями двоичных знаков постоянной длины.
Путем выделеьния разделителей из входного текста и. его последовательного а нализа можно выде.тить каждое слово входного текста и направить его на вход автоматического словаря.
Автоматический словарь ыожет быть оргснизова на основе любых известных принципов с упорядочением слов в памяти системы, причем каждому слову присв аивается сжаты,й ход, равный адресу первого байта зтого слова в слов:аре при отсутстЕ1Ии отсылки, к синониму, или адрес первого-байта синопмма. Для поиска сжатого кода слова в автоматическом словаре может кспользсватьс.ч как известны.й поиск по дереву, так и комбинированные методы, основанные на адресации по комби.нации первых двух букв, получении параметров массива (верхний и нижний адреса), проверяемых делением массива пополам и сравнением. Могут также использоваться другие известные методы, основан1;ь е на случайном преобразовании кода несжатого слова в адрес, но юоторому хранится исходное слово. Для корректировки автоматического словаря используются извест}1ые методы поиска в слова-ре и добавления слов, отсутствующих в слов:аре, в специальную его часть с использованием ОДНОСБЯЗНЫХ спис):ов и привязок к определенным с.товам. Сжатый код слова также однозначно задает адрес данных, задающих номера- документов с данным сжатым кодом.
Принципиально возможны два способа хранения инфсрмашии о номерах доку.ментов, содержащих данный адрес:
1)хранение позиционного к-.ода по данному а-дресу, в котором едини-ца в г-ой позиции слова свидетельствует о присутствии сжатого кода в, t-OM документе, а ноль - об отсутствии документа.
2)Хранение упорядоченного списка номеров документов, в которых используется данный адрес.
Эта информация: может быть получена на этапе ввода документов, нахождения а-дресов в автоматическом словаре и коррекции позици-о.нного кода или упорядоченного списка известными методами-анализа или сравнения и внесения текущего номера или ед;;ницы. Информацию о номерах документов с да-нным адресом целесообразно хранить на магнитных дисках, так как все адреса, относящиеся к одному запросу, могут быть опрощены и соответствующие массивы могут быть переписаны в оперативную память системы за одно обращение к диску. Кроме того, дне;-; позволяет хранить больщие массивы информации, обеспечиБа-я достаточно быстрый поиск.
Отметим, что автоматический словарь :,;ожет храниться как в оперативпой памяти системы, так и на магнитных барабанах.
Вводимая информация о докуме1 тах хранится на магнитной ленте, так же, ка;-: предварительно подготовленные на этапе ввода
305479
;:,окументсв таолицы,относящиеся к дан.но.--;у документу. Документы, на. магнитной ленте хранятся в порядке их ввода в систему.
Распределение основных ма-осивов в основной и расщкренной памяти системы для одного из возможных вариантов реализаци-и способа представлено на чертеже.
ГЗ основной памяти / помещаются автоматический словарь, рабочие ячейки памяти, ячейки программы обработки, ячейки программы диспетчера. Автоматический словарь размещен Б блоке 2 основной памяти, программы его организа.ции - в зоне 3. Зона 4 .может использоваться для буферн-о.го хранения доку.ментов и запросов при их вводе. Рабочая программа хранится в зоне 5 основной памяти. В зоне 6, рабочей, динамически размещаются д,, считыва.емые с дисков, над которыми осуществляются логические О11ерации. Слово в автоматическом словаре :1;.ожет занимать ряд ячеек, например, ячейки 7 и 8. Для хранения слов .переменной дляны может использоваться часть слова 9, час;ь слова 10 используется для отсыло.к к ск1:,оквыам, а часть слова 11 может использоваться для отсылок к новым корректируемым массивам.
В зоне 5 хранятся программы ввода доку:.:е;-;тов, поиска блгжайщего прототипа и проb-jpKH на иате ггную чистоту объекта запроса, а также программа-диспетчер для дина:,;|Цческого перераспределения массивов в па.мяти. и вызова подпрограмм обработки. При нахождении адреса записи по данному сл;атому коду может ;спользоваться из и.ндеканых регистров 12 вычислителя 13, назначен;1е 1шторого - счет, сравнение, анализ и no6aihoBbie операции. Для обмена информаЦ1;.2Й между осЕювной инмитью /, вычислителем 13, магнитными дисками 14 и накопителя.ми 15 на магн}:т}юй ленте служит канал С1;язи 16. В зоне 17 блока запнс; 18 может храниться сжатый код слова для поиска информации о номерах документов. Каждый док мент на .магнитной ленте занимает массив 19 переменной длины с тем же номером i, что и цорядковый номер документа. Но.мер хранится в части 20 записи на магнитной ленте. Непосредственно за номером могут следовать часть 21 для- хранения длины массива и часть 22 для хранения длины (-1)-го массива.
Для бо.тее детального понимания способа остан-звимся на математических моделях дозап:
куменюв
сов, используемых в системе, а также ::.а постановке задач поиска ближайшего прототипа и проверКИ объекта на патентную чистоту, связанных с указанными мод-глями. Описанию запроса и документа ...;т быть поставлен в соответствие граф, которого соответствуют цепочки (1), задающие взаимоотнощения объекта и его состав-ных частей, а вершинам графа соответствуют общие части дуг, идентичных данной серщине. того для сопоставимых дут
графа (т. е. дуг, которые могут быть совмещены друг с другом) должны выполняться определенные оттюшеккя мел.ду ними, задаваемые при полгощи разделителей S и Sr,. При написаний реферата, описывающего структуру объекта в соответствии с патентной формулой, возможны логические несоответствия между оиисанием объекта в документе и в запросе, в основном связанные с тем, что онределеппые составные части объекта могут быть нроиущены. Для устранения таких логических неоднозначностей считается, что объект содержит иепосре,дственно все его- составные части и, кроме того, могут быть заданы отношения тина (часть Л объекта содержит часть Б). Индексаторы в oniicaнии объекта проставляются ироиЗВольно н служат для различения отдельных идентичных вершин графа.
Характерная особенность графа млдели состоит в том, что дуги, задаюш Ие отношекия включения между объектом и его частями, а также между частями, образуют з рафе, i5 котором не устранены неодноз :2чности з задании отношения включения, дергво.
В обш,ем случае граф, задающий запрос, может содержать бо.тьшое ко.тичество идентичных частей объекта, между которыими заданы отношения одного типа - соединения между частями.
Критерием подобия запроса и документа является количество сопоставимых дуг графа запроса и докумеита, для которых выполНяются отношения, задаваемые при иомощи разделителей 5.i и 85.
Под сопоставимостью понимается налич ие в двух сопоставляемых цепочках типа (1), преобразованных при помощи автоматического словаря, цепочек символов, задающих tti. Si, Ui, где ui - группа символов, определяемая направлением движения по дуге 5; гС разрешенных разделителей; Li - преобразованное при помощи автоматического словаря слово Wi (сжатый адрес с учетом синонимов) и ai, SL, Hi., для первой и второй цепочек типа (1), таких, что каждой цепочке может быть поставлена в соответствие какая-либо цепочка ai., или наоборот. Сопоставимые дуги должны быть связаны разделителями 4 и Ss как в первом, так и во, втором графе.
В качестве ближайшего прототипа выбирается объект, задаваемый документом, для которого мера, задаваемая данным критерием, максимальна. При проверке на патентную чистоту для, каждого графа документа и данного запроса вычисляется количество дуг графа запроса, которое не может быть сопоставлено с дугами документа с учетом отношений, задаваемых разделителями 5,. и 55. Патенты, порочащие патентную чистоту проверяемого объекта, иметь меру.
равную нулю. Индексаторы, имеющиеся во входном языке, позволяют нреобразовать входной текст в соответствующ;1е модели документа и запроса.
В связи с тем, что к быстродействию системы предъявляются особые требования, связанные с обеснечеиием возможности оперативиого изменения занросов, используются
две промежуточные модели. Связный граф модели объекта моисет быть преобразован в дерево, дуги )-;ото-рого задают отношения включения между объектом и его частями, которые также задают направления в дереве
от объекта к его частям, не содержащим каких-либо других частей. Вершины дерева определяются наборами преобразоваиных ири иомощи автоматического словаря (каждое слово /Vj замеиеио соответствующим Л;, где
Л; - сжатый код данного слова) ко1 струкций тина 1 с общ-ей частью вида:
(2)индивидуа.1ьнь1Й или групповой индексатор Л,5оЛ25цЛз. . . Sr.A,..
Рндивидуальные индексаторы при зтом заменяются разделителем Sj. В этой упрощеииой модели не учитывается произвольный характер расстановки индивидуальных иидексаторов, которые используются только для
преобразования исходного текста в упорядоченные цепочки слов и разделителей. Так как в дереве однозначно заданы ориентированные пеии, соединяющие объект (начало) с конечными частями (висячими вершинами),
то в результате анализа входного текста носледиий может быть преобразован в сово.куниость преобразованных и унифицированных посредствол автоматического словарЯ и программ упификации цепочек CJJA (где it - индеке вершины вдоль направленного пути от вершины дерева, задающей объект, к висячей вершине; / - иидекс, задающий порядковый номер конструкции, относящейся к данной вершине дерева, по отношению к котОрой все конструкции такого тииа находятся в отношении альтернативы, а /г - индекс цепи) вида:
(3)Sj
или групповой индексатор Л15оЛ2. . . 5оЛт с
или -im+lJ3--4m-2 . - 5зЛг-1.
5,
S7
ИЛИ групповой индексатор Лг5,Лг.и . . . SoWn (структура цепочки) Cijh
Модель объекта получается путем объедиЕ1ен -;я C,-j/j для 1: const через «ИЛИ, групп с 1 const посредством оператора «И в предел .х k const, / I, 2, 3, ... и групп с различными k иосредством оиератора
10
доку:ме1гтов, соотношения (3), (4), (5) /т быть преоб :1азованы р программу обра п векторов i;::,-, где / - порядковый нослова 3 цепочке слов и разделнтелей (3). программа задается соотношением вн
илиилиили с 12k иCssi ии Q.,4 (с) (Ss)(Ss)(Ss) илиилиили Цепочки разделителей и сжатых кодов слов 4(а), 4(в) и 4(с) представляют собой нараллельно-цослсдовательные цепи из конструкции типа (3). Дополиительные отношения между взаи :одейсгвиямИ задаются цепочкаМИ вида; (5) C{ijif, iqjqkq И также представляют со.бой цараллельноцоследовательные цепочки. Модель объекта, задаваемая соотноше 1иями (4) и (5), может быть иреобразована в более цростые соотношения, используемые для промежуточпого поиска, путем замены разделителей в каждой из цепочек на логический оператор «И для неповторяющихся разделителей и на логический оператор «ИЛИ для повторяюЩИхся разделителей, объединяемых в скобках ири задании порядка выполнения логических , операторов (Sg) - «И на «ИЛИ в соотношени.чх (4), разделителей 5 или Ss на «ИЛИ в соотношениях (4), а также соответствующих Л; на Vi, где Vi - группы данных, задающие номера документов, содержащих данный адрес Ai Слова, позволяют получить nporpaiiму, задающую предварительный поиск документов, удовлетворяющих данному занросу. Когда Vft представляет собой вектор длиной в Л двоичных ipaзpядoв, в котором в /г-ом разряде содержится «1, если данное слово/1; содержится в й-ом документе (.V - количестQl;AQsjftQijk и ,, и Qlm},,,.m , гдеQ;. V;/;a (Vt3 ИЛ J;,J ;/й(:л-М) и ОЛ (,,,,) и l/..,, и l/;/A(,j) или. . .Vij,J в соответствии с соотношением (3). Обработка векторов iOжeт производиться по частям в соответствии с программой, задаваемой соотношением (6), слева направо. Когда Vh задается списком померов документов, операция «И эквивалентна нахождению общих элементов соответствующих списков, а операция «ИЛИ - слиянию двух списков. Как видно- из соотношения (5), последовательность , задаваемую некоторой матрицей, целесообразно обрабатывать, пробегая все з;;ачения / и k для (i const, а затем твеличивая i на единицу. Зго связано с тем, что операция «И нахождения одинаковых элементов списков пропронзводится только в пределах Qnh, причем она может свести множество номеров доку: :ентов. задаваемых ее результатом, к нулевому. Однако, когда такие результаты нол}чаются при обработке, 1:апример, последнего по порядку Qijh общение потребителя с вычислительной системой становится невозможным, так как машина не выдает ни один документ. Существо способа сводится к тому, что, анализируя цепочки слов н разделителей запроса, цифровая вычисл :тельцая С стема преобразует цепочки слов запроса в адрес
II
Ai, по которым хрЕмятся соответсТЕующие гру.ппы данных Vj, задающих номера документов.
Текст запроса путем анализа разделителей преобразуерся в форму, задаваемую соотношением (6), которое определяет последовательность И логические операцнп пад соответствующими Vijhi. Когда промежуточный результат обработки нри логическо-М умножении промежуточного результата па очередной Vjjftj (или определении общпх номеров списков) становится равным пулю, запрос поставлен некорректно, причем последнее добавляемое Vijhi целесообразно пропустить, а коррекцию (Исходпое слово запроса) вывестИ па печать. Коррективьг необходимо произвести в модели, задаваемой соотношепие,м (4) - пропуск соответствующей части djit, а также в полном графе запроса. В результате обработки Vijhi получается вектор Q, задающий- номера документов, удовлетворяющих отде.тьным условиям, сформулированным в запросе. Среди них может содержаться больщое количество документов, не имеющих отношения к запросу.
Так как более точной моделью объекта запроса является модель, задаваемая соотношениями (4) и (5), в которой требуется учитывать пе только неопределенности помещения Слова по отпошению к цепочкам идентичных разделителей, но и логические пеопределенности, определяемые возможным нропуском определенных частей объекта по отношению к отношению включения, необходимо задать соответствие между парой разделитель- сжатый код слова цепочек вида 4(а), 4(в) и 4(с) и их положение в пределах зтих цепочек с учетом неопределенностей.
Правила присвоения порядковых номеров идентификаторам (разделителю перед словом и слову), составленные с учетом этих неопределенностей и рефлексивности конструкций (3), таковы:
а)при просмотре цепочки типа 4(а) по мере увеличения i в.се идентификаторы Sj или групповой индексатор А для получают номер 1;
б)при просмотре параллельно-последовательной целочкр, задаваемой соотношеннямк (3), (4) и (5), разделители SQ и 5з присваивают содержащим их идентификаторам номер па единицу больще -номера ближайшего идентификатора с разделителем другого типа, расположенного левее;
в)при просмотре идентификаторов слева направо с учетом правила «б номер увеличивается на единицу при переходе к каждому отличному от предшествующего идентификатору;
г)при распараллеливании цепочек (точки Ss, 84, Ss в соотношениях 4(а), 4(в) и 4(с) и 5, начиная с максимального номера i, присвоение, номеров для каждого нового отрезка последовательно-параллельной цепочки типа
12
4 (а) производится сог.тасмо правилам «а, «б и
д) при обнаружении разделителя 5,1 или S, (как и S;, (и)) последние :;ь пускаются; е) после ироизска 6.; номера присваиваются по правилам «а, «б, «в и «г, каждый раз начиная с единицы;
ж) но.мер идентификатора, следующего за 55, который, в свою очередь, следует за просмотренным караллельпым набором идентификаторов, на е;1иницу большим максимального номера идентификатора параллельного набора. Информацию о каждом документе удобно
хранить на магнитной лепте в виде упорядочеппой по величипе иден/гификатора таблицы в форме матрицы, количество строк которой соответствует количеству имеющихся в документе различных идентификаторов. Количество столбцов матрицы соответствует количеству параллельпо-последовательпых цепочек типа 4а, 4в, 4с или 5.
Каждый элемент таблицы содержит упорядоченную в порядке возрастания последовательность номеров, присвоепных данному идентификатору в пределах данной параллельно-последовательной цепочки. Для сравнепия запроса с предварительно отобранными докЗМентами его преобразуют в матрицу
запроса, количество столбцов которой соответствует количеству параллельно-последовательных цепочек. Идентификаторы упорядочивают в пределах столбцов с их возможным повторением так, чтобы порядковые номера,
присвоенные элементам без учета пропуска элементов в каждом из столбцов, образовали неубывающую последовательность из номеров. Выбирая идентификатор каждой строки матрицы запроса и по пему все элементы соответствующей строки матрицы докум-епта, разделяя номера одпого элемента запятой, а разных элементов - точки с запятой, можно сформировать расширенную матрицу запроса, :присоединяя к данному элементу всю
строку элементов матрицы документа и помещая их в скобках.
При отсутствии какого-либо эле.мента в матрице запроса н документа ставят «О. Расширенная матрица преобразуется далее в
матрицу весов по следующим
а) пулю в скобке при иенулевом. элементе перед скобкой ставится в соответствие нуль весового вектора, соответствующего даннОМу элементу;
б) если номер элемента запроса, стоящий перед скобкой, «О, все элементы весового век;ора, соответствующие элементам в скобке, приобретают значение в) первому элементу в каждой строке расширенной матрицы ставится в соответствие весовой вектор (1; 1; 1 ... 1; 1), где количество едипиц соответствует количеству столбцов в матрице документа, толькО тогда, когда векто;з расщирел ой матрицы имеет вид 1 г)при .последовательном движении идентификаторов с групповым индексатором или 57 каждому элементу расширенной матрицы в Скобках ставится в соответствие един-ичпый элемент весового вектора, если порядковый номер перед скобками меньше номера сопоставляемого элемента в скобках или равен ему, и нуль- В противном случае; д)нутем анализа идентификаторов вдоль столбца для запроса для всех элементов, кроме элемента с первым слева групповым индексатором или 57 в конструкциях вида (3), проверяют выполнение равенства суммы ноВ этой таблице / - групповой индексатор; скобки означают присоединение данной конструкции через элементы таблицы соответствуют поправкам.
е)после разделителя 54 следующему элементу в скобках расширенной матрицы присваивается «1 весового вектора, когда для первого идентификатора шсле данного выполняется условие «в, а для последующих - согласно пункту «г или
ж)после k-ro разделителя 55 в их последовательной цепочке требуется, чтобы сумма данного номера вне скобок плюс все поправки, определяемые с. цепоч-ками разделителей, согласно таблице, вплоть до данного разделителя соответствовала номеру данного элемента в скобке, что позволяет преобразовать последний в единичный элемент весового вектора в соответствующей позиции. Таким образом, каждый элемент расширенной матриты преобразуется в соответствующий весовой вектор, содержащий наборы «1 и «О. Далее все векторы вдоль каждого столбца поразрядно перемножаются. Это позволяет выделить частично совпадающие параллельно-последовательно цепочки для документа и запроса. Затем все векторы столбцов суммируют по mod 2, позволяет выделить количество совпадающих цепочек, -и получают результирующий, вектор соответствия документа запросу. Этот вектор определяется моделями (4) и (5). Суммируют все элементы результирующего Вектора, количество которых совпадает с количеством параллельно-последов ательных цепочек. Сумма единиц этого вектора может быть принята за меру совпадения; документа запросу. Для каждого документа хранят эту меру и номер документа.
Далее документы сортируют по величине
этой меры, « все номера документов, для которых мера максимальна, представляют собой окончательные номера, по которым информация о тексте документа, хранимая на магнитной ленте, может быть выведена на печать. Сумма нулей результирующего вектора является мерой несовпадения документа и запроса. Для каждого документа хранят эту меру и номер документа в виде таблицы. Сортируя по величине меры таблицу, можно получить номера всех документов, для которых мера минимальна. Когда мера равна нулю, документ порочит патентную чистоту объекта запроса. Матрицы, таблицы и векторы могут храниться на магнитной ленте в виде односвязанных списков. Обрабатывать эти списки с их преобразованием в результирующие векторы можно по частям.
Запросы можно обрабатывать с высоким быстродействием, так как матрицы докудгентов могут быть предварительно погдотовлены на этапе ввода, документов, когда не требуется существенного быстродействия системы. По окончательным номерам В1ходные тексты, также хранимые на магнитной ленте, могут быть выведены на печать.
Обладая высоким быстродействием, данный способ поиска ближайшего прототипа или объектов, порочащих патентную чистоту
объекта запроса, позволяет вывести все документы, относящиеся к запросу, на печать, однако вследствие неучета индивидуальных индексаторов, а также привязок отношений между взаимодейств.иями (5) с результатами мера первого слева идентиф гкатора с групповыад индексатором или 57 доку:,ента, задаваемого номером в скобках расширенного ве ктора, с поправкой из таблиг ы, в зависимости от вила разделителя и частного вида конструкции (3), и для всех элементов, для которых выполняется равенство, проверяют, больше данный элемент элемента перед скобками или равен ему. При выполнении этих условий в iBecOBOM векторе в соответствующей позиции, для которой выполняется данное условие, устанавливается «1, а при невыполнении их - «О. Таблица
лей, ВОЗМОЖНЫ петочпссти в выдаче докумеитов. Другими словами, коэффициент полноты выдагпых док}мектов будет удовлетгуорктелен, однако, козффицнетгг релевантности для запросов, содерл-сащих большое ;оличество однотинных частей в объекте запроса, не будет удовпетворитедьным.
Релевантность мож:но улучшить, иснользуя более сложные снособы ноиска, осиованные иа алалнзе модели документа и заироса в виде графа с ограничениями и подсчете количества соноставимых дуг графа запроса и документа, а также несопоставимых дуг графа запроса и графа документа согласно рассмотренным ранее критериям. Чтобы избежать обычного нер-ебора и учесть все топологические отношения между дугами графа, вначале рассматривают графы занроса и документа без ограничений. Такие графы могут быть получены нутем анализа входных текстов с учетом индексаторов и синтаКсических ценочек тина (3), также их обш;их частей, задаюш,их вершилы графов. Так как в общем случае графы могут представлять собою деревья и не быть сильно связанными, т. е. каждая их дуга может ирнн.адлежать какому-либо простому циклу, при ностроении матрицы смежностт исходного графа необходилю виести фиктивные дуги, число которых таково, что исходный, граф превращается в сильно связанный, нричем базовый набор независимых его циклов содержит минимальное количество циклов. Для этого по матрице смежности находят каркас графа, онределяющий какойлибо набор независил ых цростых циклов. Для деревьев каркас совпадает с исходным графом-деревом. Далее аналцзируют выброшенные из графа дуги, в результате выбрасывания которых построен каркас. выброшенная дуга определяет единсгвенный простой цикл базового циклов. Выделяются сильно связа)1цая часть графа и деревья. Для каждой сильно связациой части графа нутем пацравленного объединения циклов базового набора и анализа нолученных циклов нервоначальный базовый набор незаВ1 симых циклов преобразуется в набор независимых базовых циклов минимальной суммарной длины, обладающий свойствОМ инвариантности но отношению к изоморфизму и игзомо-рфному вложению графа в граф. Наборы таких независимЫ(Х циклов могут быть поставлены во взаимооднозначное соответствие в смысле длин независимьгх циклов. Анализируются висячие вершины каждого из деревьев, а также находится вершина, находящаяся на расстоянии «1 от общей вершины данного дерева и сильно связанной частн графа, такая, чтобы она Не являлась вершиной дуги, цринадлежащей каким-либо двум .независимым циклам базового набора сильно связанной части. Висячие вершииы и выбранная вершина должны быть соединены между собой фиктивиымн дугами. Для введения помеченных единиц в матрицу смежности исходного графа (для фиктивных дуг) образуется какой-либо цикл из фиктив1:ых дуг, иро.ходяший через все висячие вершины и выбранную вершину. После изменений по новой матрице смежности определяют новый набор независимых циклов минимальной длины. Цикломатическую матрицу для этого набора анализируют, причем находят такой ноднабор циклов, задаваемых ею, чтобы все ЦИКЛРЯ оставались связанными друг с другом, но содержали минимальный набор независимых циклов минимальной длины, задающий все нефиктивные дуги.
Путем неребора (направленно суммируя по
mod 2) простые независимые циклы миниального набора, которые могут быть обозначены какими-либо индексами или привязками, зная их д.тины, вычисляют длины всех простых циклов сильносвязанного графа и
формируют из них поисковую таблицу. Таблицы уиорядоченного набора длин, а также кодированные обозначения простых циклов, получаемые из независимых гщклов минимальной длины, показывающие, какие из этих
циклов объединены, позволяют быстро найти все дуги графа, входящие в данный простой цикл. Таблицы данных всех циклов графов документов вместе с их нривязкамн к дугам этнх графов получают иа этане ввода документа и хранят на магнитной ленте. Таблицы всех циклов запроса получают в цроцессе уточненной обработки запроса, так же, как и система привязок, позволяющая перечислить все дуги вдоль этого цикла, начиная с любой
из них, либо по часовой стрелке либо против нее. Для запроса и документа выбирают такие максимальные но длине циклы запроса или документа, чтобы в таблицах разница между их длинамн была минимальной. Предиочтение отдается циклам одицаковой длицы, а если это невозможно, выбирают циклы с минимальной разницей. Очевидно, что такие циклы всегда могут быть наложены друг на друга. Для выбранных в результате анализа
таблиц для заданного запроса и документа циклов составляют кодовые носледовательноС1и. Количество различных максимальных циклов не может превысить количество элементов базовых наборов и в общем случае
невелико. При составления кодовых последовательностей дуги графа запроса перечисляют, начиная с любой дуги этого максимального цикла, причем для каждой дуги помещают привязку к спискам упорядоченных
элементов, задающих сниски кодов, анализируемых при оиределении сопоставимости дуг, если дуга лежит на данном максимальном цикле. Однако привязка помещается со специальным индексом,если она впервые встречена нри обходе и ее оба конца лежат «а максимальном цикле, нричем по крайней мере дважды: когда дуга встречена первый раз пр-и обходе и зател - когда она встречена второй раз. Если какие-либо части графа замой кодирования (имеются: еще ка,кие-либо наборы циклов, содержащие дуги, не лежащие на сравниваем-ых максимальных циклах), то специальнвш И ндексы задают указаниые участки, которые далее могут быть сопоставлены, отдельно. Для документа составляют последовательность 2д, где q- длина цикла последовательностей, начиная с каждой дуги на цикле и церечисляя дуги как по часовой стрелке, так и против нее. Последовательпость может быть составлена один раз, а все остальные: могут быть получены циклическими нерестановками и реверсированием порядка. Правила кодирования аналогичны уже рассмотренным. Каждую последовательность для запроса сопоставляют с каждой из последовательностей для докулгента путем выбора по привязкам к соответстствующим спискам кодов для дуг запроса и документа соответствующих списков, их слИЯния и сравнения результирующего списка с исходными по количеству элементов. Если дуги сопоставима, ни одна из них не является фиктивной, лежат они на максимальных циклах и имеют одинаковые привязки с разделителем 54(5s) к позиции дуги, связанной- с данной разделителями 54(55) см. соотношение (5), то в результирующую последовательность вносят элемент а,-, в противном случае - пуль. Если дуги сопоставимы, ни одна из них не является фиктивной, но дуги не лежат на максимальных циклах, имея оба конца на максимальных циклах, проверяют принадлежность дуги одинаковым наборам базовых независимых циклов минимальной длины по их длинам, и, если эти наборы идентичны, вносят элемент a.i/Z. Здесь также требуется учитывать привязки между дугами с учетом их переменных позиций, а также соотнощение (5). При наличии ваборов циклов вне максимального сопоставления наборов требуется найти наиболее близкие по длине максимальные циклы для этих частей и получить соответствующие Oj и аг/2 в составляющих результирующих векторах, которые вставляются вместе с .нулем в позиции этих сравниваемых наборов. Инами словами, ют же процесс составления и сопоставления кодовых последовательностей касается частей, которые не вошли в первую результирующую последовательность. Результирующая последовательность-вектор, содержащий наборы иг, а;/2 и частные суммы а/ и ui/2, не вошедщие в первый максимальный цикл. Количество таких последовательностей определяется величиною 2qr, где г - количество максимальных циклов данного запроса. Отметим, что С; в результирующей последовательности лри учете одного, лишь пересечения дуг принимает зна чение «1. Это це.несообразно прн проверке объектов на пате.ятную чистоту. Для поиска прототипа может потребоваться учет позиции дуги в дереве включения. При обработке модели, задаваемой соотношениям (4) и (5), дугам могут быть приписаны веса uj в зависимости от их принадленхности определенному уровню в направленном дереве включения. Пусть k - минимальный номер уровня, на котором появляется данная дуга. Тогда а; 2-. В отдельных случаях можно считать ui 1 для всех дуг (для упрощения последовательности действий). При поиске ближайшего прототипа для каждого результирующего вектора вычисляют суммл всех а, и аг/2 по всем зпачения м i (порядковому номеру дуг при их квазиупорядочении) и для данного документа выбирают максимальную сумму. Среди всех документов выбирают докуiieuT с максимальны значениел такой сумПри проверке объекта на патентную чистоту вычисляют сумму пулевых члеНОВ по всем / и выбира от ми ;имум такой . Среди всех документов выбирают док мепты с инима.тьным .ти нулевым значениел такой суммы. Уточненные значения результирующих векторов: соответствия документа запросу получают для малого количества документов, обнаруженных в результате обработки по упрощенным моделям, вследств 1е чего быстродействие системы c пжaeтcя несущественно. П р е д .% е т изобретения 1. Способ поиска патентных докуме 1тов при помощи цифровых вычислительных сиcie.M, при котором патентные документы и запросы представлены в виде совокунностн цепочек слов, объединяемых при помощи логических оиераторов «И, «ИЛИ, отличающийся тем, что,Тс решения таких задач, как поиск ближайшего прототипа и проверка объекта на патентпу О чистоту, анализируют цепочки слов и разделителей запроса и в зависимости от структуры цепочек слов и разделителей преобразуют раздел 1тели запроса в логические операторы, но адресу каждого слова цепочки в словаре считывают группы данных, задающие документов, содержащих данный адрес слова, осуществляют над -руцпами данных логические операции, полученные в результате преобразования, и в том случае, результат очередной логической о :ерацнн };ад очередной рупной данных для слова и промежуточным результатом не задает омера документов, содержащих заданну О совокупность слов, объединенных задап -:ымн логическими о 1ератора И, то данный оператор и слово опуска от и переходят к обработке очередного с.чова; по окончании обработки всех слов по loмepa доку19
памяти таблицы соответствии упоря;;0чеииых го величи.не пар разделителя и слова и номеров, характернзуюЩНх положение дайной пары по отношению к началу набора однозначно выбранные цепочек слов и разделителей документа; из цепочек слов и разделителей запроса выделяют цепочки однозначно выбранных нодценочек слов и разделителей и формируют .номера позиций: нар слов и разделителей по отношению к началу однозначно выбранных нодценочек слов занроса, но которым выбирают соответствующие строки таблицы документа и по результатам соноставления элементов таблицы для нар слова и разделителя запроса и документа формируют результируюш,ий вектор соответствия документа запросу; при поиске блнжайшего нрототина суммируют элементы результирующего вектора, формируют окончательные номера документов, соответствующие максимальной сумме едиЦИц результирующего вектора; нри проверке объекта на патентную чистоту суммируют количество нулей результирующего вектора, формируют окончательные номера документов, соответствующие минимальной сумме нулей результирующего векГ/уII
I I-, I
I I
20
тора; выводят на печать тексты документов по окончательным номераин
ВЫ1ВОДЯТ на печать тексты документов по уточненным номерам.
20
15
-VW
2
22
