РЕФЕРАТ
Устройство поиска вхождения образца
Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для решения таких задач символьной обработки информации как создание и поддержка баз данных, лингвистический анализ текстов, составление словарей. Кроме того, устройство может быть использовано в качестве подсистемы поиска позиций вхождения в вычислительных устройствах, реализующих марковские продукции.
В представленном устройстве выполняется сопоставление слова-образца и обрабатываемого слова. При обнаружении вхождения образца в слово, адрес позиции вхождения записывается в регистр результата.
Устройство поиска вхождений содержит: блок памяти слов, блок памяти формул, блок преобразования слов, блок обнаружения вхождения, блок результата и два блока управления.
Новым в устройстве является то, что в нем реализуется двухступенчатый конвейер, первая ступень которого решает задачу предсказания позиций вхождения образца в слово по минимальному объему данных, следуемых из структурных особенностей обрабатываемых слов, а вторая ступень, используя результаты работы первой, окончательно решает вопрос о позиции вхождении образца при помощи простой схемы побуквенного сопоставления.
Нововведения позволяют значительно снизить аппаратные средства, повысить надежность работы устройства поиска, увеличить скорость выполнения функции поиска.
10 иллюстраций, 15 стр.
ФОРМУЛА ИЗОБРЕТЕНИЯ
Устройство поиска вхождения образца, содержащее блок памяти слов, блок управления, блок памяти формул, блок обнаружения вхождения, блок преобразования слов, отличающееся тем, что дополнительно введены: второй блок управления, блок результата, первый выход которого связан с первым входом блока памяти слов, первый выход которого связан с первым входом блока результата, второй выход которого связан с первым входом блока преобразования слов, первый выход которого связан с первым входом блока памяти формул, первый выход которого связан со вторым входом блока преобразования слов и со вторым входом блока результата, с третьего по девятый входы которого связаны с первого по седьмой выходами второго блока управления соответственно, восьмой выход которого связан с третьим входом блока преобразования слов, с четвертого по одиннадцатый входы которого связаны с первого по восьмой выходами первого блока управления соответственно, девятый выход которого связан с двенадцатым входом блока преобразования слов и вторым входом блока памяти слов, десятый выход первого блока управления связан с тринадцатым входом блока преобразования слов и вторым входом блока памяти формул, третий вход которого связан с десятым входом блока результата и девятым выходом второго блока управления, первый и второй входы которого связаны с третьим и четвертым выходами блока результата соответственно, одиннадцатый вход которого связан с десятым выходом второго блока управления и третьим входом блока памяти слов, второй выход которого связан с четырнадцатым входом блока преобразования слов, второй выход которого связан с четвертым входом блока памяти слов и двенадцатым входом блока результата, с тринадцатого по пятнадцатый входы которого связаны с одиннадцатым по тринадцатый выходы первого блока управления соответственно, с четырнадцатого по девятнадцатый выходы которого связаны с первым по шестой входами блока обнаружения вхождения соответственно, первый выход которого связан с первым входом первого блока управления и шестнадцатым входом блока результата, семнадцатый вход которого связан со вторым входом первого блока управления и третьим выходом блока преобразования слов, четвертый выход которого связан с третьим входом первого блока управления и третьим входом второго блока управления, четвертый вход которого связан с пятым выходом блока результата, второй выход блока обнаружения вхождения связан с четвертым входом первого блока управления, пятый вход которого связан с пятым выходом блока преобразования слов, шестой и седьмой выходы которого связаны с седьмым и восьмым входами блока обнаружения вхождения соответственно, восьмой выход блока преобразования слов связан с пятым входом второго блока управления, пятый и шестой выходы блока результата, пятый и шестой входы блока памяти слов, четвертый и пятый входы блока памяти формул, с пятнадцатого по двадцатый входы блока преобразования слов, с шестого по девятый входы первого блока управления являются внешними.
Список используемой литературы
1. А. С. № 000 СССР, МКИ5 G 06 F 15/16. Устройство для реализации подстановок слов/ и др. 1988.
2. А. С. № 000 СССР, МКИ5 G 06 F 15/20. Устройство для реализации подстановок с двухкомпонентными вхождениями/ и др. 1987.
Устройство поиска вхождения образца
Фиг. 1
Устройство поиска вхождения образца
Фиг. 2
Устройство поиска вхождения образца
Фиг. 3
Фиг. 4
Фиг. 5
Устройство поиска вхождения образца
Фиг. 6
Устройство поиска вхождения образца
Фиг. 7
Устройство поиска вхождения образца
Фиг. 8
Фиг. 9
