Информационно-поисковая система

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СЭЙДВТВЛЬСТВУ

Союз Советских

Соцналнетнческнх

Республнк

643892 (6!) Дополнительное к авт. свил-ву-, (22) Заявлено 01 07-76 (2!) 2382860/18-24 с присоединением заявки №(23) ПриоритетОпубликовано25.01.79.Бюллетень № 3 (5l) М. Кл.

G 06 F 15/40

Государстовиивб коиитвт

СССР оо делам изоорвтвиий и отиритий (53) УДК 681-322 (088.8}

Дата опубликования описания 28.01.79

И. С. Гибни, N. A Гофман, С. Ф. Кибирев, П. (72) Авторы изобретения

Сиб ийя нститут автоматики и электрометрии

AH СССР

{Zf) Заявитель пращ.ц от М (54) ИНФОРМАЦИОННОПОИСКОВАЯ СИСТЕМА

Изобретение относится к вычислительной технике и может найти приме-. нение при создании информационно-поисковых систем, когда необходимо сочетание быстрого поиска со значительными объемами хранимой информации.

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

Недостатком этой системы явлао мвначительные затраты времеви при обработке запросов на сложный поиск.

Из известных систем наиболее близ кой цо технической сущности к предлагаемой являетси система,содержащая последовательно связанные источник света, оптическую запоминающую среду, % устройство маскирования, оптическое устройство считывания, и устройство обработки (2)

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

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

643892

Целью изобретения является повышение быстродействия системы.

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

Кроме того, блок анализа данных содержит элементы H-HE, ИЛИ-HE.

ИЛИ, НЕ, причем входы первого и второго элементов ИЛИ-HE и элемента.

ИЛИ соединены с соответствуюшими входами блока, выход второго элемента ИЛЙ-НЕ и первый выход элемента ИЛИ через последовательно соединенные третий элемент ИЛИ-НЕ и элемент НЕ подключены к первому входу первого элемента H-НЕ, второй вход которого соединен с выходом первого элемента

ИЛИ-НЕ, вход второго элемента И-HE соединен со вторым выходом элемента ИЛИ, выходы элементов И-НЕ подключены к выходам блока.

На фиг. 1 изображена схема системы, нв фиг. 2 - пример реализации блока анап,иэа данных, На фиг. 1 показаны источник света 1 оптическая эапочинвюшаи среда 2, устройство 3 маскирования, оптическое уст» ройство считывании 4, блок 5 нвмяти, выполненный в виде матрицы триггеров с входной логикой, блок 6 анализа данных, блоки 7, 8 памяти (матрипы триг геров с входной логикой), блок 9 считывания данных, устройство 10 обработки.

В состав схемы, изображенной на фиг. 2, входят элементы ИЛИ-НЕ 11.

12,13, элемент ИЛИ 14, элемент НЕ

15, элементы И 16, 17.

При описании раооты устройства ис» польэованы следующие обозначения:

5 Aj - управляющие команды блока 51

А2 - управляющие команды блока 7;

A3 - управляющие команды блока 8;

Д ф - управляюшие команды блока 9>

К0 - двоичное содержимое устройства 4 4 - двоичное содержимое блока 5;

К2 - двоичное содержимое блока 7

KS -двоичное содержимое блока 8

Х 4 — код, характеризующий состоя l5 ние блока 5, принимает значении:

00 — если s Kl все нули;

01 - если в К1 есть нулин единицы

10 - если в Kl все,единицы.

При реализации блоков памяти матрица триггеров может быть построена, например, на основе двухтактных синхронных триггеров. Двухтактная син25 хронная схема позволяет, во-первых, испольэовать во входной логике сигналы исходного состоянии триггера и, вовторых, одновременно выполнять оперв30 ции в блоках 5,7,8. Многошаговость процедуры поиска проводит к необходимости хранения результатов промежуточных вычислений, причем, при таких сложных процедурах, как поиск по сис33 теме признаков в заданных пределах каждого признака, необходимо хранение двух промежуточных результатов при одновременном вычислении третьего.

Хранение можно осуществлять в

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

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

Если устройство обработки представля50 ет собой ЭВМ, то параллельно принять и обработать слова длиной 10 бит зф она не способна (размерность слова современных ЭВМ 16-64 разряда). В

55 етом случае поивлиетси необходимость последовательных вычислений.

Онерации, выполняемые по этим командам, указаны в таблице.

643892

О О О Кl — Кl

О О 1 КО К1 К1

О 1 О КО K1L K1 1а

А1

О 1 1 Уст. 1 Кl

1 О О КО К2- К1

1 0 1 КО К2 К1

1 1 О КΠ— К1

1 1 1 B устройстве

i10 код К4"

О О К2 — -К2 М

А2 О 1 К1 + К2 — "К2

1 О К1 — - К2

1 1 Кl KÇ К2

О О КЗ вЂ "КЗ

0 1 К2-КЗ вЂ” КЗ

1 0 Уст. "1 KÇ 36

01 В10К1

А4 1 О В 10К2

1 1 В10КЗ

Отрелка в обозначениях операций указывает на блок памяти, в который записывается результат выполнения операций.

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

Работа системы представляетси в виде многошаговой процедуры. На определенном шаге в нее вводится очередная маска (очередность ввода и содержимое масок определяется задачей) °

Световой луч от источника света 1 прс ходит через оптическую запоминающую среду 2 и маску устройства 3. Свет, промодулнрованный содержимым среды 2 и устройства 3 маскирования, попадает в входную плоскость оптического устройства 4 считывания. Содержимое устройства 4 посылается в блок 5 памяти.

При этом возможные операции между

KO u Kl определяются таблицей и выбираются, исходя из решаемой задачи.

Затем содержимое блока 5 посьшается либо в блок 6 для анализа, либо в блок

7 для последующей обработки, либо в блок 9 для считывания в устройстве обработки 10. Блок 7 и блок. 8 работак т аналогично блоку 5.

В процессе работы системы в устройство обработки 10 с блока 6 поступает код, характеризующий нулевое, единичное или смешанное состояние страницы

Kl, а с блока 9 - сама страница Kl или страницы К2, КЗ. С помощью операций КО К1- К1, Ко К1 К1", Уст. "1 Kl", Kl + К2 — К2, К1 — К2 в блоках 5 и 7 вычисляются в виде логических функций адреса тех массивов, которые удовлетворяют отдельным признакам. В блоке 8 опера- циями К2 KÇ вЂ” « КЗ" и Уст. l

К3 из указанных систем функций путем их поразрядного логического умножения формируется искомый адресный массив, удовлетворяющий всей совокуп ности признаков. Команды КО К2 К1.

"КО К2 К1 и в устройстве 10 код

К4 введены с целью ускорения, cno ного поиска типа поиска по неравенству или упорядоченной выборки. Команды

"КО- -вК1 и В 10 Kl обеспечивают работу в режиме простого поиска, формула изобретения

1. Информационно-поисковая система, содержащая последовательно связанные источник света, оптическую запоминаю шую среду, устройство маскирования, оптическое устройство считывания и уст643892 . Д» »» »:3»- « ° ..«....»«» .., »1»««»» ройство обработки, о т л и ч а ю щ ая с я тем, что, с целью ловьппения быстродействия, s нее введены три блока памяти, блок анализа данных и

1 блок считывания данных, причем группа входов первого блока памяти соединена с выходом оптического устройства считывания, группа выходов подключена ко входам блока анализа данных, второго блока памяти и блока считывания дан- t0 ных, группа выходов. второго блока памяти соединена со входами первого блока памяти, блока считывания данных и третьего бпока памяти, группа выходов которого соединена со входами второго >s блока памяти и блока считывания данных, ивформапионные выходы блоков ана.лиза данных и считывания данных подключены ко входу устройства обработки, управлякиций выход которого соединен с 20 управляющими входами упомянутых блоков памяти и блока считывания данных.

2. Устройство по и. 1, о т л и ч ею щ е е с s тем, что блок анализа даиI р,у 25 ных содержит элементы И-НЕ, ИЛИ-НЕ»

ИЛИ, НЕ, причем входы первого и вто-, рого элементов ИЛИ-HF. и элемента ИЛИ соединены с соответствующими входами блока, выход второго элемента ИЛИ-НЕ и первый выход элемента ИЛИ через пос ледовательно соединенные третий элемент ИЛИ-НЕ и элемент КЕ подключены к первому входу первого элемента И-НЕ, второй вход которого соединен с выхс дом первого элемента ИЛИ-НЕ; вход второго элемента И-НЕ соединен со вторым выходом элемента ИЛИ, выходы элементов И НЕ подключены к выходам блока.

Источники информации, принятые во. внимание при экспертизе:

1. Satagucbi м. "Anew авьосл а1ive

nternars цО6и1пд йойодгар1п IEEE Transoctions 1970, С- 19,Ф-И.

2. Патент СЩА hb 3841729,: кл. З50-3.5, N.Êë. G Ъ2 В 27/00

1 974.