Устройство для обнаружения искажений в тексте Советский патент 1983 года по МПК G06F17/21 

Изобретение относится к вычислительной технике и может быть исполь зовано в системах обработки текстовой информации. По основному авт. св. № 920730 известно устройство для обнаружения искажений в тексте, содержащее регистр кодов символов, распределитель информации, блоки дешифрации до пустимых биграмм и корреляций символов, регистр фиксации ошибок и блок выделения слова, первым и вторым вхо дами соединенный соответственно с ин формационным и тактовым входами устройства, причем первый выход и вход регистра кодов си волов соединены соответственно с третьим входом и вы ходом блока выделения слова, а второй вькод - с управляюР5Ими входами блоков двРгшЬрации допустимых биграмм и корреляций символов, выходы которы соединены с соответствующими входами регистра фиксации ошибок, йыход которого является выходом устройства, информационные входа блоков дешифрации допустимых биграмм корреляций символов через распределитель информаисии соединены с группой инфор мационных выходов регистра кодов сим волов 1 . Недостаток известного устройства сЪстоит в том, что оно не позволяет . локализовать-место искажения - искаженные символы в словах текста. Цель изобретения - расширение функциональных возможностей устройства путем обеспечения локализации места искажения и указаний позиции ошибки в тексте. Поставленная цель достигается тем ,что в устройство введены Формирова тель позиции ошибки в слове, состоящий из трех элементов И, элемента ИЛ и блока приоритетов, и индикатор, со диненный управляющнм входом с выходо регистра фиксации оишбок, а первым и вторым.информационными входами - с ответственно с выходом блока приоритетов и с третьим вьпсодом регистра кодов символов, Первый и второй входы первого элемента И соединены с Первым и вторым выходами блока депшф рации допустимых корреляций символов третий и четвертый выходы которого соединены с первым и вторым входами второго элемента И, выход которого соединен с первыми входами элемента iUHi и третьего элемента И, выход кот рого соединен с первым .входом блока 982 приоритетов, а второй вход - с выходом первого элемента И и вторым входом блока приоритетов, второй вход элемента ШИ соединен с первым выходом блока дешифрации допустимых биграмм, а выход - с третьим входом блока приоритетов, группа входов которого соединена с группой выходов блока дешифрации допустимых биграмм. На чертеже представлена блок-схема предлагаемого устройства для обнаружения искажений в тексте. Устройство содержит регистр 1 кодов символов, распределитель 2 информации, блок 3 депшфрации допустимых биграмм, блок 4 дешифрации допуйтимык корреляций символов, регистр 5 (Фиксации ошибок, блок 6 выделения слова. Формирователь 7 позиции ошибки в слове, cocтoяп5 й из первого, ( второго и третьего элементов.И 8, 9, 0, элемента ИЛИ 11 и блока 12 приоритетов, индикатор 13, инЛормационные выходы 14 и 15 распределителя информации, тактовый вход 16 устройства, выход 17 блока приоритетов, информационный вход 18 устройства, выходь 19,1, 1.9.2 ,..., 19(п-2) блока дешифрации 3 и выходы 20.1, 20.2 , 20.3, 20.4 блока 4 дешиеТфации. Кпок 12 приоритетов представляет собой известную схему последовательного опроса заявок и предназначен для поиска крайней правой единицы 2. Устройст во работает следуюп им образом. В исходном состоянии регистр 1 находится в обнуленном состоянии. Распределитель 2 информации вырабатывает на своих выходах 14 и 15 нулевые коды. На выходах блока 3 (на выходах 19,1,..,,19,п-2), блока 4 (на выходах 20,1,..,,20.4), регистра 5 и формирователя 7 присутствуют нулевые сигналы. На индикаторе 13 от.сутствует информация об ошибках. Поступление кодов символов текста через блок 6 разрешается по тактовым сигналам в цепи 16. При поступлении на вход 18 неискаженноготекста на регистре 1 производится накопление кодов-символов слова до появления пробела после последнего символа слова, В этом случае по сигналу, поступающему на управляющий вход блока 6 с регистра 1, запрещается дальнейшее поступление кодов символов. Таким образом, на регистре оказываетя выделенной совокупность кодов сим 3 волов, соответствующая одному слову текстал Каждое слово текста представляется в устройстве как совокупность .первого -символа и наборов комбинаций последующих символов слова двух видов: отношений 2-3, 3-4,... символов, отражаюр51х зависимость пре дыдущего символа в слове от последую щего, корреляций 2-4, 2-5, 3-5 3-6 символов в слове. Каждый начальный символ алфавита используемого языка имеет свой комЪлект эталонных (разрешенных комбинаций символов, соответствуклщх различным позициям я слове. Тем самым учитываются устойчивые комбинации символов в словах используемого языка. Оршбки в тексте обнаруживаются при сравнении эталонных комбинаций с поступив1чими в слове. Запрещенные сочетания символов пре ставляют собой такие сочетания,которы никогда не встречаются в русском языке При определении является ли некоторое сочетание разрешенным или запрещенным анализируется большой массив слов русского (или другого) языка. Итак, после приема очередного сло ва текста распределитель 2 информаци фор трует в цепях 14 пары кодов отношений (биграмм) 2-3, 3-4,... (n-l)-n символов, а в цепях 15 пары кодов корреляции символов 2-4 2-5, 3-5, 3-6 выделенного слова. По коду первого символа, поступающего с второго выхода регистра 1 , в блоках 3 и 4 осуществляется подклю чение рабочих дешифраторов кодов пар 2-3, 3-Д,..., (п-1)-п символов и пар 2-4, 2-5, 3-5, 3-6 сим волов выделенного слова соответствен но. Для неискаженных слов текста код отношений символов и корреляций символов, соответствующие зафиксированному первому символу слова, являются разрешенными, При этом на выходах 19. 1 ,,.t,19, п-2 , подключенных к выхода блока 3 дешифрации допустимых биграмм 2-3,..., (n-l)-n символов и на выходах 20.1 ,... ,20.4, подключенных к выходам блока 4 дехчифрации допустимых корреляций 2-4, 2-5, 3-5, 3-6 символов Формируются нулевые сигналы. На выходе ре гистра 5 отсутствует сигнал об оиибке в слове,на выходе блока 1 2 - сигнал о позиции ошибки в слове.На индикаторе 1 информация об ошибке не индицируется. 19Я4 Работа устройства в случае ошибок в поступаюр1ем кодированном тексте производится следующим образом. Допустим, что на вход устройства по входу 18 поступает последовательность кодов символов текста, соответствующая искаженному слову ОИГНАЛ, образованному вследствие искажения первого символа (правильно ). По тактовым сигналам с вхОда 16 осуществляется разблокировка поступления кодированного текста на регистр 1 на котором производится накопление кодов символов слова до появления пробела после символа Л. В этом случае по сигналу, поступающему на управляющий вход блока 6 с первого выхода регистра 1, запрещается дальнейшее поступление кодов символов. Таким образом, на регистре 1 оказываются выделенными коды символов слова СИГНАЛ. Pi определитель 2 информахдаи формирует на выходе 14 пары кодов отношений 2-3, 3-4, 4-5.и 5-6 символов, т.е. пары кодов символов , ГН, НА и АЛ, а на выходах 15 пары кодов корреляций 2-4 (Ш), . 2-5 ). 3-5 (ГА) и 3-6 ГЛ символов слова, просмотр которых осуществляется с помош.ью блоков . 3 и 4. Так как пары кодов отношений 2-3 (ИГ), 3-4 (ГН), 4-5 (ПА) и 5-6 (АЛ) символов и корреляции 2-4 (НН), 2-5 (IIA), 3-5 (ГА) и 3-6 (ГЛ) символов являются запрещенными комбинациями для слова, начинающегося с символа о, то блоки 3 и 4 вырабатывают на соответствующих выходах- 19.1, 19.2, 19.3, 19.4 и 20.1, 20.2, 20.3, 20.4 единичные сигналы. Единичные сигналы, поступающие на блок 12,, указывают на выходе 19.2 ,. на оггибку в четвертой позиции, на выходе 19.3 - на ошибку в пятой позиции, на выходе 19.4 - на ошибку в. шестой позиции. По единичным сигналам на выходах 20.1 и 20.2 элемент И 8 формирует единичный сигнал, указывающий на ощибку во второй позиции, по единичным сигналам на выходах 20.3 и 20.4 элемент И 9 формирует единичный сигнал, указываюпщй на ощибку в третьей позиции. Кроме того, единичный сигнал на выходе 19.1, поступаюрий на блок 12 через элемент ИЛИ 1I, также указывает на ошибку в третьей позиции. Элемент ПЛИ 11 Форми- рует единичный сигнал, указываюп ин на ошибку в третьей позиции. Элемент И 10 фор {ирует сигнал об ошибке в первой позиции слова. Таким образам, на первый - шеетой входы блока 12 поступают сигналы об ошибках в первой-гаестой позициях поступившего слова. Блок 12 осуществляет поиск крайней правой единицы из поступивших входных сигналов и AopNttipyeT на шинах 17 информации об ошибке в первой позиции слова, поступаюЕчую на индикатор 13, Для искажений в первом символе слова харак терным является появление сигналов об опшбках в последующих позициях поступившего слова. Одновременно на индикатор 13 передается по управляющему сигналу регистра 5 содержимое регистра 1, Таким образом, на индикаторе 13 после соответствуницей дешиЛрации отображается поступившее слова СИГНАЛ и информация об обнаруженной ошибке в первой позиции этого слова, Допустим, что на вход устройства 18 поступает последовательность кодов символов текста, соответствующая искаженному слову ДЙИЕТА, образованному вследствие ошибочного добавления второго символа (правильн ДИЕТА)., На регистре 1 осуществляет ся накопление кодов символов до появ ления пробела после последнего симво ла А, В этом случае по сигналу, поступающему на управляющий вход блока в с регистра 1, запрещается дальнейшее поступление кодов символов. Таким образом, на регистре 1 оказываются выделенными коды символов слова , Распределитель 2 информации на выходе 14 пары кодов отношений 2-3 3-4, 4-5, и 5-6 символов, т,е, пары кодов символов ИИ, ИЕ, ЕТ и а на выходе 15 - коды корреляций 2-4 (ЙЕ), 2-5 (ЙТ) 3-5 (1ГГ) и 3-6 (IIA) символов слова, просмотр которых осуществляет ся с помощью рабочих дешифраторов блоков 3 и 4, Так как пары кодов отношений 2-3 (Й11), 3-4 (ИЕ) и коррелятши 2-4 (ЙЕ), 2-5 (ЙТ) символов являются запрещенными комбинатщями дня слова, начинающе гося с символа Д, то блоки 3 и 4 вырабатывают на выходах 19,1, 19,2, 20.1, 20,2 соответственно единичные сигналы, ЕДИНИЧ1ГЫЙ сигнал на выходе 19.1, поступающий на блок 12 через элемент ИЛИ 11,.указывает на ошибку в третьей позиции слова. Единичный ситнал на выходе 19,2, поступающий на вход блока 12, указывает на ошибку в четвертой позиции. По единичным сигнал.ам на выходах 20,1 и 20,2 элемент И 8 формирует единичный сигнал, указываюпщй на ошибку во второй позиции слова. Таким образом, на второй, третий и четвертый входы блока 12 поступают сигналы об ошибках во второй, третьей и четвертой позициях поступившего слова, Дпя ошибок во втором символе слова наиболее характерно то что запрещенными комбинациями является совокупность символов корреляции 2-4 и 2-5, Поэтому единичный сигнал элемента И В, поступающий на вто рой вход блока I2, будет определяющим при указании позиции ошибки. Замеченные ошибки в последующих позициях поступившего слова - следствие опибки в предыдущем символе. Таким образом, ошибка в мпадшем разряде считается основной. Блок 2 осуществляет поиск крайней правой едини 1 из поступивших входных сигналов и формирует на выходе 17 информацию об ошибке во второй позиции слова, пос- тупаюр|ую на индикатор 13, Одновременно н индикатор 13 передается по управляющему дигналу регистра 5 содержимое регистра 1, Таким образом, на индикаторе 13 йосле соответствующей дешифрации отображается поступившее искаженное слойо ДЙИЕТА и информация об обнаруженной ошибке во второй позиции этого слова. Допустим, ч.то на вход устройства 18 поступает последовательность кодов символов текста, соответствующая искаженному слову ДИМКТОР, образованному вследствие добавления третьего символа (правильно ДИКТОР), На регистре 1 осуществляется накопление кодов символов до .появления пробела после последнего символа Р, В этом случае по сигналу, поступающему на управлякнций вход блока 6 с регистра 1, запрещается дальнейшее поступление кодов символов. Таким образом, на регистре 1 оказываются выделенными коды символов слова ДИИКТОР. Распределитель 2 информации формирует на вьпсоде 14 пары кодов отношеНИИ/2-3, 3-4, 4-5, 5-6 и 6-7 символов, т.е. пары кодов сим волов Ш1, МК, КТ, ТО и ОР, а на выходе 15 - коды корреляции 2-4 (ИК), 2-5 (МК), 3-5 (I1T) и 3-6 (МО) символов слова, просмотр которых осуществляется с помощью рабочих дешифраторов блоков 3 и 4, Так как пары кодов отноше ний 4-5 (КТ) и корреляций 3-5 (МТ), 3-6 (МО) символов являют ся запрещенными для слова, начинающе гося с символа Д, блоки 3 и 4 выра батывают на выходах 19.3 и 20.3, 20. йоответственно единичные сигналы, Ед ничный сигнал на выходе 19.37 поступаюрщй на блок 12, указывает на ошиб ку в пятой позиции. По единичным сиг налам на выходах 20.3 и 20.4 элемент И 9 формирует единичный сигнал, указываюпд й на ошибку в третьей позиции. Таким образом на третий и пятьй входы блока 12 поступают сигналы об ошибках в третьей и пятой позициях поступившего слова. Для ошибок в третьем символе слова наиболее характерно то, что запрещенными ком бинациями является совокупность символов корреляции 3-5 и 3-6 или символы отношений 2-3. Поэтому единичный сигнал элемента ИЛИ 11, поступающий на третий вход, блока 12, будет определяющим при указании пози ции ошибки; Замеченные ошибки в последующих позициях поступившего, слова - следствие ошибки в предыдущем .символе. Таким образом, ошибка в мпадгаем разряде считается основной. Блок .12 осув1ествляет поиск крайней правой единицы из поступивших входны сигналов и формирует на шинах 17 информацию об ошибке в третьей позиций слова, поступающую на индикатор 13. Одновременно на инидкатор 13 передается по управляющему си,гналу регист ра 5 содержимое регистра 1. Таким об разом, на индикаторе 13 после соответствующей дешифрации отображается поступившее искаженное слово Д1МКТОР и информация об обнаруженной ошибке в третьей позиции этого слова. , Допустим, что -на вход устройства 18 поступает последовательность кодов символов текста, соотпетствующая искаженному слову РЕГИ Р, образованному вследствие пропуска шестого символа Т (правильно РЕГИСТР). На регистре 1 осуществляется накопление кодов символов до появления: пробела после последнего символа Р. В этом случае по сигналу, поступающему на управляюп1ий вход блока 6 с регистра 1 , запрещаете дальнейшее поступление кодов символов. Таким образом, на регистре 1 оказы ваются выделенными .коды символов -слова РЕГИС Р. Распределитель 2 информации формирует на выходе 14 пары кодов отношений 2-3, 3-4, 4-5 и 5-6 СИМ-, волов, т.е. пары кодов символов ЕГ, ГН, ИС и а на выходе 15 коды корреляций 2-4 (ЕЙ) , 2-:5 (ЕС). 3-5 (ГС) и 3-6 (ГР). символов слова, просмотр которых осуществляется с помощью блоков 3 и 4. Так как пара кодов отношений 5-6 (СР) и корреляций 3-6 (ГР) являются запрещенными комбинациями для слова, начинающегося с символа Р, блоки 3 и 4 вырабатывают на выходах 19.4 и 20.4 соответственно единичные сигналы. Единичный сигнал на выходе 19.4, поступающий на вход блока 12, указывает на ошибку в шестой позиции .. Таким образом, на шестой вход блока 12 поступает единичный сигнал об ошибке в шестой позиции поступившего слова. Дпя ошибок в четвертом.- п-м символе наиболее характерно то что запрещенной комбинацией является соответственно биграмма 3-4, (п-1)п, т.е. для ошибки в шестом. символе биграмма 5-6 является запрещенной. Поэтому единичные сигна- . лы на выходах 19.2-19.n-2 (19.4 - для биграмнь 5-6) являются определяющими при указании ошибки. Таким образом, ошибка в младшем.разряде считается основной. Блок 12 Лор1 мрует на выходе 17 информацию об ошибке в шестой позиции слова, поступающую на индикатор 13, одновременно на индикатор 13 передается по управляющему сигналу регистра 1. Таким образом, на индикаторе 13 после соответствующей дешифрации отображается,поступившее искаженное слова РЕГИС Р и информация об обнаруженной ошибке в шестой позиции этого слова. Использование формирователя 7 позиции ормбки в слове, включающего элементы И 8-10, НИИ 11, блок 12 поиска крайней правой единицы и индикатор 13, соединенные указанным выше образом, позволяет расширить функциональные возможности устройства путем отображения искаженного слова и указания позиции ошибки в кем.

Вероятность обнаружения ошибок в тексте составляет 0,8-Q,97 в зависимости от типа ошибок, (пропуск, добавление или замена символа), позиции ее в слове и начального символа слова.

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

УСТРОЙСТВО ДЛЯ ОВНАРУ ККННЯ ИСКА Ш;НИЙ в ТЕКСТЕ по авт. св. № 920730, отличающееся тем что, с целью расширения функциональных возможностей путем обеспечения локализации места искажения и указания позиции ошибки в тексте, в него введены формирователь позиции. опибки в слове, состоя1ций из трех элементов И, элемента ИЛИи блока приоритетов, и индикатор, соединенный УПРАВЛЯЮЩИМ входом с выходом регистра Ликсации ошибок, а первым и вторым информационными входами - соответственно с выходом блока приоритетов ис третьим выходом регистра , кодов символов, первый и второй входы первого элемента И соединены с первым и вторым выходами блока дешифрации допустимых корреляций символов, третий и четвертый выходы которого соединены с первым и вторым входами второго элемента И, выход которого соединен с первыми входами элемента ИЛИ и третьего элемента И, выход которого соединен с первым входом блока приоритетов, а второй, I вход - с выходом первого элемента И и с вторым входом блока приоритетов, сл второй вход элемента HJBI соединен с первым выходом блока дешифрации допустимых биграмм, а выход - с третьим входом блока приоритетов, группа входов которого соединена с группой . выходов блока дешифрации допустимых биграмм. о сл а со 00