Пристрій для морфологічного аналізу природномовних текстів

Реферат: Пристрій морфологічного аналізу природномовних текстів належить до області обчислювальної техніки та комп’ютерної лінгвістики і може бути використана при побудові систем автоматичного опрацювання надвеликих об’ємів природо мовних текстів, або лінгвістичних корпусів текстів для довільних предметних галузей. Пристрій містить блок регістрів символів, блок дешифраторів символів, блок пам’яті основ закінчень, блок комутаторів, блок ключів і блок мікропрограмного керування додатково введені лічильники символів і адрес результату і перша та друга схеми порівняння, завдяки чому вирішена задача забезпечення достатньої повноти та швидкості морфологічного аналізу для вирішення практичних задач лінгвістичної обробки надвеликих об’ємів лінгвістичних корпусів текстів в реальному часі. Інакше інформація, закладена в природно мовному тексті, може бути загублена, або отримана, коли вона вже втратить свою актуальність. UA 72914 U (12) UA 72914 U UA 72914 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до області обчислювальної техніки та комп'ютерної лінгвістики і може бути використана при побудові систем автоматичного опрацювання надвеликих об'ємів природномовних текстів, або лінгвістичних корпусів текстів для довільних предметних галузей. Відомо, що дослідження того, як людина інтерпретує та розуміє мовні висловлювання, має як теоретичний, так і прикладний інтерес. Роботи в галузі автоматичного аналізу тексту та автоматичного вирішення задач, сформульованих на природній мові (або мові, близькій до неї), показали актуальність таких досліджень. В загальному випадку лінгвістичний аналіз складається з чотирьох етапів - графемного, морфологічного, синтаксичного та семантичного. В 60-70 роки минулого століття всі експериментальні дослідження в галузі машинної морфології починалися зі створення машинного словника. Не існувало єдиного, загальновизнаного формату і структури такого словника. Ці обставини мали два наслідки: по-перше, всі алгоритми автоматично ставали словниково-залежними, по-друге, кожен алгоритм розроблявся під конкретний формат словника. А основною проблемою в розробці машинно-орієнтованого алгоритму для лінгвістичних процесорів був великий об'єм вихідних даних, що використовує програма, тобто в об'ємі словників, які складалися вручну. Дослідження в цій області були орієнтовані на мінімізацію вихідних даних. Алгоритми програм, що працюють без словника, використовують ймовірносно-статистичні методи та лексикони основ чи квазіоснов, суфіксів чи квазісуфіксів, побудованих емпіричним шляхом. Наприклад в (Шереметьева CO., Ниренбург С. Эмпирическое моделирование в вычислительной морфологии // НТИ, №7, 1996.) описана працююча модель морфологічного аналізу, яка не потребує об'ємних словників основ відкритих класів слів. Вона використовує наступні лексикони: закінчень і рефлексивів, суфіксів, квазікоренів, префіксів, баз та основ. Кожній одиниці такого лексикону приписані всі можливі (але не вичерпні) граматичні характеристики словоформ, частиною якої може бути вказана одиниця. Моделі, які використовують словники, здатні дати більш повний аналіз словоформи (тобто оперувати більшим числом граматичних ознак). Ступінь точності такого аналізу вище у порівнянні з моделями, які не використовують словники. Отже задача автоматизованого аналізу природномовних текстів зводиться до двох параметрів: якості, що визначається парою - точність (рівень помилок у побудованих лінгвістичних структурах речень) і повнота (ступінь покриття тексту синтаксичними зв'язками, або зв'язність графа речення), та швидкодії, поки що недостатній для ряду прикладних задач. Описані два підходи до побудови моделей лінгвістичного аналізу (в (Гладун В.П. Процессы формирования новых знаний. - София: СД "Педагог 6", 1994.-192 с.) названі відповідно: зі словником - граматичним підходом; без словника - підходом безпосереднього розпізнавання), як вказувалося вище, мають свої недоліки та переваги. А тому оптимізація параметрів "Якість  Швидкодія" для кожного конкретного проекту повинна виконуватись індивідуально. Відомі й інші програми морфологічного аналізу слів природної мови. Один з базових підходів до розробки алгоритмів морфологічного аналізу для флективних мов розглядає будь-якого виду регулярне й нерегулярне чергування букв у слові як частину розширеної псевдофлексії, а як основа словоформи розглядається незмінна частина слова. У подібній моделі опису кількість парадигматичних класів для російської(української) мови зростає до 3 000, але зростання числа класів при проектуванні компенсується однорідністю лексикона й відсутністю, як винятків, так і правил альтернацій. Для пошуку в подібному словнику основи словоформи нерідко застосовується метод пошуку по бінарному дереву. Алгоритм заснований на знанні того, що масив основ упорядкований. При кожному порівнянні зона пошуку зменшується в 2 рази. Виконуючи не більш ніж Log 2 N (N кількість основ у словнику) порівнянь, можна або знайти необхідну основу в словнику або переконатися в її відсутності. Найбільш близьким до запропонованого є пристрій для морфологічного аналізу слів природних мов і мов "ділової прози" (Авторське свідоцтво СРСР №1455345 кл. G06F 15/20 1988 р.). Прототип містить блок пам'яті слів, блок регістрів символів, блок пошуку входжень, блок ключів, блок аналізу характеристичного вектора, блок закінчень, блок пам'яті основ, блок елементів АБО, блок дешифраторів символів, блок комутаторів, блок дешифраторів сполучень символів, блок збереження ознак, блок регістрової пам'яті, лічильник адрес результату, блок аналізу морфологічних ознак, блок регістрів символьного входження, блок формування результату класифікації, блок затримки та блок мікропрограмного керування. У прототипі характеристичним вектором називається двійкове слово, яке дорівнює довжині слова, що опрацьовується, та індукує одиницею в одному або декількох розрядах, позицію входження якої-небудь букви абетки в слові. Використання характеристичних векторів дозволяє 1 UA 72914 U 5 10 15 20 25 30 35 40 45 50 55 60 скоротити час на пошук входжень основ і закінчень в слова, що опрацьовуються, тому, що у випадку відсутності хоча би одного суміжного входження букви, що дозволяє уникнути непродуктивних витрат часу, особливо у тих випадках, коли входження основи чи закінчення, що розглядаються, в слові, що опрацьовується, немає. У прототипі основи і закінчення розташовуються в пам'яті, починаючи з основ і закінчень максимальної довжини, а аналіз виконується спочатку по закінченням, а потім виконується, якщо це необхідно, перехід до блока збереження основ. При цьому пошук виконується тільки на множині спряжених основ, тобто таких основ, які не "обнуляють" характеристичний вектор, отриманий на списку закінчень. Після формування непустого характеристичного вектора на списку закінчень, витягується ознака у вигляді двійкового слова. Якщо в цьому слові одна одиниця, то видається результат класифікації. Якщо в слові-ознаці декілька одиниць, то проглядається список основ. Ознаки, добуті по входженню закінчення й по входження основи в результаті порозрядної кон'юнкції слів-ознак дають кінцеву ознаку. Якщо в цьому слові є тільки одна одиниця, то результат класифікації позитивний, інакше формується запит на до визначення й виконується відмова від класифікації. Недоліками такого пристрою є наступне. По-перше, морфологічний аналіз у прототипі виконується послідовно для кожної букви абетки та кожної букви поданого на аналіз слова. Швидкодія такого пристрою мало чим відрізняється від програм морфологічного аналізу. Подруге, для прототипу словники основ, закінчень й ознак складаються вручну професіоналамилінгвістами, а це є надскладною задачею. Спільними ознаками прототипу і запропонованого пристрою морфологічного аналізу природномовних текстів є блок регістрів символів, блок дешифраторів символів, блок пам'яті основ, блок пам'яті закінчень, блок комутаторів, блок ключів і блок мікропрограмного керування, при цьому перший інформаційний вихід блока дешифраторів символів підключений до першого інформаційного входу блока пам'яті основ, а групи з першої по q-ту інформаційних виходів підключені відповідно до групи перших інформаційних входів блока ключів й інформаційних входів блока комутаторів, групи з першої по q-ту інформаційних виходів якого підключені відповідно до інформаційних входів блока пам'яті закінчень, керуючий вхід якого підключений до першого керуючого виходу блока мікропрограмного керування, а його перша група інформаційних виходів і другий інформаційний вихід підключені відповідно до другої групи інформаційних входів блока ключів та інформаційного виходу блока пам'яті основ і є інформаційним виходом пристрою, керуючі входи з першого по третій якого є відповідно керуючими входами "Пуск", "Сброс" і "Синхросигнал" блока мікропрограмного керування, другий та третій керуючі виходи якого підключені відповідно до керуючого входу блока пам'яті основ та другого керуючого входу блока регістрів символів, інформаційний вхід якого є інформаційним входом пристрою. В основу корисної моделі поставлена задача створити такий пристрій морфологічного аналізу природномовних текстів, в якому завдяки введенню нових блоків, розпаралелювання обчислень співвіднесеності поданого на аналіз слова з його основою та закінченням незалежно від кількості букв (символів) у слові, використанню новітніх інформаційних та мікроелектронних технологій та засобів з достатніми технічними показниками була б реалізована задача забезпечення достатньої повноти та швидкодії морфологічного аналізу для вирішення практичних задач лінгвістичної обробки надвеликих об'ємів лінгвістичних корпусів текстів в реальному часі. Інакше інформація, закладена в природномовному тексті, може бути загублена, або отримана, коли вона вже втратить свою актуальність. Поставлена задача вирішується тим, що пристрій морфологічного аналізу природномовних текстів (фіг. 1) містить блок регістрів символів 1, блок дешифраторів символів 6, блок пам'яті основ 4, блок пам'яті закінчень 5, блок комутаторів 8, блок ключів 7 і блок мікропрограмного керування 12, при цьому перший інформаційний вихід блока дешифраторів символів підключений до першого інформаційного входу блока пам'яті основ, а групи з першої по q-ту інформаційних виходів підключені відповідно до групи перших інформаційних входів блока ключів й інформаційних входів блока комутаторів, групи з першої по q-ту інформаційних виходів якого підключені відповідно до інформаційних входів блока пам'яті закінчень, керуючий вхід якого підключений до першого керуючого виходу блока мікропрограмного керування, а його перша група інформаційних виходів і другий інформаційний вихід підключені відповідно до другої групи інформаційних входів блока ключів та інформаційного виходу блока пам'яті основ і є інформаційним виходом пристрою, керуючі входи з першого по третій якого є відповідно керуючими входами "Пуск", "Сброс" і "Синхросигнал" блока мікропрограмного керування, другий та третій керуючі виходи якого підключені відповідно до керуючого входу блока пам'яті основ та другого керуючого входу блока регістрів символів, інформаційний вхід якого є інформаційним 2 UA 72914 U 5 10 15 20 25 30 35 40 45 50 55 60 входом пристрою, лічильники символів 2 й адрес 10 результату і перша 3 та друга 11 схеми порівняння, причому перший інформаційний вхід першої схеми порівняння підключений до інформаційних входів пристрою й блока регістрів символів, на другий інформаційний вхід якої підключено код символу закінчення передачі вхідного слова, постійний на весь час роботи пристрою, перший інформаційний вхід другої схеми порівняння підключений до інформаційних виходів блока пам'яті основ, блока пам'яті закінчень та інформаційного виходу пристрою, на другий інформаційний вхід якої підключено код символу закінчення передачі результату роботи пристрою, постійний на весь час роботи пристрою, а виходи першої та другої схем порівняння підключені відповідно до шостого та сьомого керуючих входів блока мікропрограмного керування, третій керуючий вихід якого підключений до перших керуючих входів лічильників символів та адрес результату, другі керуючі входи яких підключені відповідно до п'ятого керуючого входу та другого керуючого виходу блока мікропрограмного керування, четвертий керуючий вихід якого підключений до першого керуючого входу блока регістрів символів, n інформаційних виходів якого підключені відповідно до n інформаційних входів блока дешифраторів символів, а треті керуючі входи підключені до керуючих входів блока комутаторів та інформаційного виходу лічильника символів, інформаційний вихід лічильника адрес результату підключений до другого інформаційного входу блока пам'яті основ, третя група інформаційних входів якого підключена до інформаційних виходів блока дешифраторів сполучень символів, групи інформаційних входів якого підключені до відповідних груп інформаційних виходів блока ключів, четвертий і п'ятий керуючі входи блока мікропрограмного керування є керуючими входами відповідно "Читання" і "Запис" пристрою. Відмінними ознаками пристрою морфологічного аналізу природномовних текстів є додатково введені лічильники символів й адрес результату й перша та друга схеми порівняння, причому перший інформаційний вхід першої схеми порівняння підключений до інформаційних входів пристрою й блока регістрів символів, на другий інформаційний вхід якої підключено код символу закінчення передачі вхідного слова, постійний на весь час роботи пристрою, перший інформаційний вхід другої схеми порівняння підключений до інформаційних виходів блока пам'яті основ, блока пам'яті закінчень та інформаційного виходу пристрою, на другий інформаційний вхід якої підключено код символу закінчення передачі результату роботи пристрою, постійний на весь час роботи пристрою, а виходи першої та другої схем порівняння підключені відповідно до шостого та сьомого керуючих входів блока мікропрограмного керування, третій керуючий вихід якого підключений до перших керуючих входів лічильників символів та адрес результату, другі керуючі входи яких підключені відповідно до п'ятого керуючого входу та другого керуючого виходу блока мікропрограмного керування, четвертий керуючий вихід якого підключений до першого керуючого входу блока регістрів символів, n інформаційних виходів якого підключені відповідно до n інформаційних входів блока дешифраторів символів, а треті керуючі входи підключені до керуючих входів блока комутаторів та інформаційного виходу лічильника символів, інформаційний вихід лічильника адрес результату підключений до другого інформаційного входу блока пам'яті основ, третя група інформаційних входів якого підключена до інформаційних виходів блока дешифраторів сполучень символів, групи інформаційних входів якого підключені до відповідних груп інформаційних виходів блока ключів, четвертий і п'ятий керуючі входи блока мікропрограмного керування є керуючими входами відповідно "Читання" і "Запис" пристрою. На фіг. 1 наведена блок-схема пристрою морфологічного аналізу природномовних текстів. На фіг. 2 наведена блок-схема блока регістрів символів. На фіг. 3 наведена блок-схема блока дешифраторів символів. На фіг. 4 наведена блок-схема блока комутаторів. На фіг. 5 наведена блок-схема блока ключів. На фіг. 6 наведена блок-схема блока дешифраторів сполучень символів. На фіг. 7 наведена блок-схема блока мікропрограмного керування. На фіг. 8 наведена блок-схема алгоритму роботи пристрою. Пристрій морфологічного аналізу природномовних текстів (фіг. 1) містить блок регістрів символів 1, лічильник символів 2, першу схему порівняння 3, пам'ять основ 4, пам'ять закінчень 5, блок дешифраторів символів 6, блок ключів 7, блок комутаторів 8, блок дешифраторів сполучень символів 9, лічильник адрес результату 10, другу схему порівняння 11 і блок мікропрограмного керування 12. Інформаційний вхід блока регістрів символів 1 з'єднаний з першим Інформаційним входом першої схеми порівняння 3 і є інформаційним входом 13 пристрою. Другий інформаційний вихід пам'яті закінчень 5 з'єднаний з інформаційним виходом пам'яті основ 4, з першим інформаційним входом другої схеми порівняння 11 і є інформаційним виходом 14 пристрою. Керуючі входи з першого по п'ятий блока мікропрограмного керування 12 3 UA 72914 U 5 10 15 20 25 30 35 40 45 50 55 60 є відповідно керуючими входами 15-19 пристрою. Крім того, керуючий вхід 19 пристрою з'єднаний з другим керуючим входом лічильника символів 2. Шостий і сьомий керуючі входи блока мікропрограмного керування 12 з'єднані відповідно з виходами першої 3 та другої 11 схем порівняння. Перший та другий керуючі виходи блока мікропрограмного керування 12 з'єднані відповідно з керуючими входами пам'яті закінчень 4 і пам'яті основ 5. Крім того, другий керуючий вихід блока мікропрограмного керування 12 з'єднаний з другим керуючим входом лічильника адрес результату 10. Третій керуючий вихід блока мікропрограмного керування 12 з'єднаний з першими керуючими входами лічильників символів 2 і адрес результату 10 й другим керуючим входом блока регістрів символів 1, а до його першого керуючого входу підключений четвертий керуючий вихід блока мікропрограмного керування 12. Блок регістрів символів 1 (фіг. 2) містить n 8-бітових регістрів 26-1-26-n і дешифратор 27 на n виходів. Інформаційний вхід 28 з'єднаний з n інформаційними входами регістрів 26-1-26-n. Керуючий вхід 29 з'єднаний з першим керуючим входом дешифратора 27 і є четвертим керуючим виходом блока мікропрограмного керування 12. Керуючий вхід 30 з'єднаний з другим керуючим входом дешифратора 27, розрядність якого становить корінь квадратний із n. Керуючий вхід 31 з'єднаний з керуючими входами "Сброс" регістрів 26-1-26-n. Інформаційні виходи з першого по n дешифратора 27 підключені відповідно до входів синхросигналів регістрів 26-1-26-n, інформаційні виходи 32-1-32-n є інформаційними виходами блока регістрів символів 1. Блок дешифраторів символів 6 (фіг. 3) містить n блоків RAM 33-1-33-n, адресні входи яких з'єднані відповідно з інформаційними входами 34-1-34-n, а інформаційні виходи з'єднані відповідно з виходами 35 і 36-1-36-q. Вихід RAM 33-1 є 5-розрядним, так як перших букв у слові може бути не більше 32. Починаючи з другої букви (символу) у слові таких різних символів може бути більше, ніж 32 (зокрема, для української мови добавляються символи "Апостроф" і "Дефіс"). Тому інші пам'яті RAM мають шестирозрядні виходи, які згруповані у q груп по qst кожна. Таке групування виконується на попередньому етапі розробки пристрою і визначається згідно таблиці, яка буде наведена нижче. Блок комутаторів 8 (фіг. 4) містить (n-1) мультиплексор 37, інформаційні входи яких з'єднані відповідно з інформаційними входами 39-1-39-(n-1), причому тут неважливе групування символів у групи. На кожен інформаційний вхід підключений 6-розрядний код відповідного символу, починаючи з кінця слова, згідно з його порядком у слові. Наприклад, для української мови кількість символів у закінченні не перевищує 11, а отже мультиплексорів 37 необхідно 11 і символи, що підключаються, є С(n-11) - Сn. Керуючі входи мультиплексорів 37 з'єднані відповідно з керуючим входом 38, а їх інформаційні виходи - з 40-1-40-(n-1). Блок ключів 7 (фіг. 5) містить q груп по qst в кожній схем І 41, перші входи яких з'єднані відповідно з входами 42-1-42-(n-1), а другі - з 43-1-43-(n-1). Причому, перші з них є 6розрядними, а другі - однорозрядні. Входи 43-1-43-(n-1) є блокуючими для вхідних слів з закінченнями, причому блокуються відповідні позиції символів, що належать закінченням, і на вихід ключів передаються тільки коди символів, що належать основам вхідних слів. Виходи схем 141 з'єднані відповідно з виходами 44-1-44-q1,…, 44-qst-44-(n-1). Блок дешифраторів сполучень символів 9 (фіг. 6) містить q блоків RAM 45-1-45-q по одному блока на одну групу сполучень символів. Адресні входи блоків RAM з'єднані відповідно з входами 46-1-46-q1,…, 46-qst-46-(n-1), а інформаційні виходи - з виходами 47-1-47-q. Останні є середньою групою адрес пам'яті основ 4, причому виходи 47-1 підключені до старших розрядів, а виходи 47-q - до молодших. Повна адреса пам'яті основ 4 складається з п'яти старших розрядів, які з'єднані з виходом 35 блока дешифраторів символів 6, q груп середніх адрес, які з'єднані з виходами 47-1-47-q блока дешифраторів сполучень символів 9 і r молодших розрядів, які з'єднані з виходом лічильника адрес результату 10. Розрядність r обчислюється попередньо і залежить від найбільшої довжини послідовності слів результату обчислень, що передаються на вихід пристрою 14. Блок мікропрограмного керування 12 (фіг. 7) містить пам'ять мікрокоманд 48, регістр мікрокоманд 49 і мультиплексор умов 50. Адресні входи пам'яті мікрокоманд 48 підключені до молодших розрядів інформаційного виходу регістра мікрокоманд 49. їх розрядність залежить від довжини мікропрограм, реалізуючих алгоритм роботи пристрою. Виходи з другого по дев'ятий пам'яті мікрокоманд 48 підключені до молодших розрядів (починаючи з другого) інформаційного входу регістра мікрокоманд 49. Виходи з десятого по дванадцятий підключені до керуючих входів мультиплексора умов 50 і є керуючим сигналом "Джерело умови". Вихід мультиплексора умов 50 підключений до входу молодшого розряду регістра мікрокоманд 49. Виходи з тринадцятого по шістнадцятий підключені до відповідних входів регістра мікрокоманд 49, 4 UA 72914 U 5 10 15 20 25 30 35 40 45 50 55 60 виходи якого є керуючими виходами 58-61 відповідно. Інформаційні входи мультиплексора умов 50 підключені відповідно (починаючи з молодших розрядів) до першого виходу пам'яті мікрокоманд 48, керуючих входів 55, 54 "Запис", 53 "Читання", 52 і 51 виходів другої і першої схем порівнянь 11 і 3. Керуючі входи регістра мікрокоманд 49 "Синхроімпульси" і "Сброс" підключені відповідно до керуючих входів 56 і 57. Робота пристрою морфологічного аналізу природномовних текстів починається з надходження на керуючий вхід 16 блока мікропрограмного керування 12 (фіг. 7) сигналу "Сброс=1", який ініціює в ньому внутрішній керуючий сигнал 24 "Сброс=1". Цей сигнал встановлює в "нульове" положення блок регістрів символів 1, регістр мікрокоманд 49 (фіг. 7) і лічильники символів 2 і адрес результату 10. Потім пристрій переходить в режим очікування сигналу "Пуск=1". При його надходженні далі пристрій очікує надходження першого символу вхідного слова ("Запис=1"). При його надходженні на інформаційні входи блока регістрів символів 1 і першої схеми порівняння 3 подано 8-бітовий код першого символу (розглядається байтове кодування символів, наприклад Win 1251) і блок мікропрограмного керування 12 (фіг. 7) видає на керуючий вихід 22 сигнал "ЗпС=1". Номер символу запису формується лічильником символів 2, виходи якого керують дешифратором 27 (фіг. 2), виходи якого є сигналами запису у відповідний регістр символу 26-1,…,26-n. 8-бітовий код першого символу з виходу РгС1 26-1 дешифрується у дешифраторі 33-1 (фіг. 3), з виходу якого 5-розрядний код утворює старші адреси пам'яті основ 4. При цьому об'єм 5 останньої розбивається на 32 блоки (2 ), один з яких є блоком збереження результатів аналізу основ вхідних слів (такий "вільний" блок утворюється завдяки тому, що, наприклад для української мови немає жодного слова, яке починається з символу "м'який знак"). Аналогічним чином у блок регістрів символів 1 записуються всі символи вхідного слова. При цьому, при надходженні чергового символу в схемі порівняння 3 виконується порівняння "код вхідного символу тотожний коду символу закінчення передачі символів вхідного слова" (це може бути, наприклад код "09Н", що означає "Пробіл", який постійно присутній на другому інформаційному вході схеми порівняння 3. При надходженні коду символу закінчення передачі символів вхідного слова на виході схеми порівняння 3 встановлюється сигнал "1", який поступає на шостий керуючий вхід 25 блока мікропрограмного керування 12. Після цього блок мікропрограмного керування 12 (фіг. 7) переходить до інтерпретації фрагменту алгоритму аналізу символів вхідного слова (фіг. 8). Спочатку аналізуються символи, що, можливо, належать до закінчення вхідного слова. При цьому групування символів у групи важливе для перших інформаційних входів блока ключів 7 (фіг. 5) і неважливе для інформаційних входів блока комутаторів 8 (фіг. 4). Розглянемо алгоритм аналізу закінчення. При цьому у лічильнику символів 2 буде записано код "01Н", який поступає на вхід 38 мультиплексорів 37-1,…, 37-(n-1) (фіг. 4), на виходи яких будуть передані коди "0, 0,…,Сn", які передаються на адресні входи пам'яті закінчень 5. В комірці пам'яті закінчень 5 з адресою "0, 0,…,Сn" записано: - якщо символ Сn не являється закінченням і словом без основи, то на других інформаційних виходах пам'яті закінчень 5 буде код "NOP" (немає операції), а на перших - код "0, 0,…,0", тобто на виходах блока ключів 7 (фіг. 5) всі символи "С2,…,Сn" (символи всіх q груп) будуть заблоковані. Блокування символу означає, що у відповідних розрядах виходів блока ключів 7, виходах блока дешифраторів сполучень символів 9 (фіг. 6) і середніх адрес пам'яті основ 4 будуть коди "0, 0,…,0"; - якщо символ Сn є закінченням і словом без основи, то будуть вибрані адреси відповідних комірок пам'яті закінчень 5 і пам'яті основ 4, в яких зберігаються результати для закінчення і слова Сn відповідно. Якщо вхідне слово складається з двох букв (символів) С1 і С2 (вони ж при аналізі закінчень інтерпретуються як Сn-1 і Сn), то блоком ключів 7 символ С2 не буде заблокований і його дешифрований код через блок дешифраторів сполучень символів 9 поступить на середні адреси пам'яті основ 4. На виходах блока комутаторів 8 будуть присутні коди "0,…,Сn-1, Сn" і в пам'яті закінчень 5 буде вибрана адреса результату аналізу можливого закінчення "Сn-1, Сn". На відповідному виході других інформаційних виходів пам'яті закінчень 5 буде зчитано код. При цьому керуючий вихід 23 блока мікропрограмного керування 12 "Читання пам'яті закінчень=1". Аналогічно виконується аналіз для будь якого ланцюжка символів "С1,…,Сn-1,Сn". Після аналізу закінчення і основи вхідного слова блок мікропрограмного керування 12 переходить до інтерпретації мікропрограми видачі результату аналізу. Спочатку на інформаційний вихід пристрою 14 передається результат аналізу основи вхідного слова. При цьому другий керуючий вихід блока мікропрограмного керування 12 встановлюється в "1", що дозволяє читання пам'яті основ 4 і лічити в лічильнику адрес результату 10, або вибирати 5 UA 72914 U 5 10 15 20 25 30 35 40 45 50 55 послідовні (по "+1") комірки результату. Кількість комірок, в яких зберігається результат, є змінною величиною і залежить від конкретної основи. Кінцеві комірки кожного такого результату містять коди, наприклад "0D0AH", що означає кінець передачі результату проаналізованої основи. При цьому інформаційні виходи пам'яті основ 4 підключені до першого інформаційного входу другої схеми порівняння 11, вихід якої, встановлений в "1", поступає на сьомий керуючий вхід блока мікропрограмного керування 12 і сигналізує про закінчення передачі результату основи. Потім на інформаційний вихід 14 пристрою передається код комірки, що містить результат аналізу закінчення (при цьому керуючий сигнал 23 блока мікропрограмного керування 12 "Читання П3=1"). При кожній передачі слова результату на інформаційний вихід 14 пристрою в блоці мікропрограмного керування 12 аналізується четвертий керуючий вхід 18 "Читання=1", який сигналізує про завершення передачі чергового слова результату. При завершенні передачі на інформаційний вихід 14 пристрою кодів всіх комірок результату блок мікропрограмного керування 12 на своєму третьому керуючому виході 24 встановлює сигнал "Сброс=1", яким "обнуляє" відповідні регістри і лічильники, а алгоритм роботи пристрою переходить до очікування прийому чергового слова для аналізу. Практична реалізація пропонованого пристрою морфологічного аналізу природномовних текстів виконана для опрацювання текстів загальновживаної лексики української мови (для російської мови розробка пристрою аналогічна). Були виконані статистичні обчислення вказаної лексики на основі відомої лексикографічної системи "Словники України", доступної на вебпорталі http://lcorp.ulif.org.ua/dictua/. В якості прикладної програми був використаний додаток Microsoft Office-Microsoft Excel. Основні статистичні дані, необхідні для розробки пристрою, наведені в табл. 1. В ній кількість основ, що зберігаються в пам'яті основ 4 (фіг. 1), становить біля 260 тисяч, кількість строк закінчень, що зберігаються в пам'яті закінчень 5 - понад 2,5 тисячі. Середня довжина основи становить 9,27 символів. Практично досліджено, що від середньої довжини основи залежить кількість і розрядність q груп дешифраторів сполучень символів 9, розрядність середніх адрес пам'яті основ 4 та кількість і групування схем I 41-1,…,41-(n-1) (фіг. 5) блока ключів 7, тому що кількість сполучень символів, номера яких більші за номер середньої довжини (для української абетки - починаючи з символу 10), швидко зменшується і їх адресація в q-ій (останній) групі середніх адрес пам'яті основ 4 вирішується природним шляхом (або не визиває труднощів). В табл. 1 наведені дані обчислень для різних сполучень символів, починаючи з символу 2 (С2) і закінчуючи С10 (першим символом, більшим за середню довжину основ для української абетки). В середній частині табл. 1 показано групування сполучень символів (символ "X" вказує, що відповідне сполучення бере участь у відповідній архітектурі) для відповідної архітектури, від якого залежить розрядність q груп дешифраторів сполучень символів 9. В нижній частині табл. 1 наведено дані про необхідні об'єми пам'яті для пам'яті основ 4 для різних архітектур. Цей об'єм суттєво залежить від кількості символів у сполученні, а остання безпосередньо визначає розрядність адрес дешифраторів сполучень символів 47 (фіг. 6). Чим менший об'єм пам'яті основ 4 у відповідній архітектурі, тим більша кількість символів у сполученні і відповідно розрядність q-ої групи дешифраторів сполучень символів 9. Моделювання пристрою морфологічного аналізу природномовних текстів виконувалось в системі САПР ПЛІС Xilinx ISE 8.2i. Відома плата HTG-V6HXT - Х16РСІЕ - 565 фірми Hitech Global (www.hitechglobal.com/boards/ allboards.htm) на якій встановлені наступні апаратні засоби, доступні для користувача і необхідні, зокрема, для практичної реалізації пропонованого пристрою: 1) кристал ПЛІС Virtex-6 НХ 565Т, який містить 912 блоків RAM ємністю 36Кbх1, з можливість організації від 36Кbх1 до 512 × 36 (www.hilinx. com/products/boards_kits/virtex6.htm). Вказані блоки RAM використані для реалізації дешифраторів символів 6, дешифраторів сполучень символів 9 і пам'яті мікропрограм 48 (фіг. 7). На логічних комірках кристалу ПЛІС реалізовані блок регістрів 1, лічильники сполучень 2 і адрес результату 10, схеми порівняння 3 і 11, блок ключів 7, блок комутаторів 8, регістр мікрокоманд 49 і мультиплексор умов 50 (фіг. 7) блока мікропрограмного керування 12; 2) зовнішня (по відношенню до кристалу ПЛІС) пам'ять RAM: I) DDR3 SO DIMM - до 16GB (на цій пам'яті реалізовано пам'ять основ 4) і QDR-II - до 4Мх18 (на ній реалізовано пам'ять закінчень 5). В табл.2 наведені показники моделювання пропонованого пристрою. 6 UA 72914 U Таблиця 1 Кількісні показники сполучення символів (К - кількість, АП - необхідний адресний простір, біт) Кількість основ - біля 260 тисяч, кількість строк закінчень - понад 2,5 тисячі, середня довжина основи - 9,27 С9С2С4 С5С7 С8С10 С5-С6 С7-С8 С2С5 С6С9 С6С8 С9С11 С2С6 С7С11 С7С10 С10 К АП К АП К АП К АП К АП К АП К АП К АП К АП К АП К АП К АП К АП (тис.) (2ехРп) 26,45 15 7,95 13 4,99 13 0,9 10 0,78 10 0,7 10 32,2 15 21,54 15 6,8 13 4,08 12 76,4 17 23,9 15 16,3 14 Архітектура 1 Архітектура 2 Архітектура 3 X Х Х Х Х Х Х Архітектура 3Архітектура 1-1 Архітектура 2-1 1 X X X X X X X X X Архітектура 2Архітектура Архітектура 1-2 2 3-2 Необх. адр. простір ПО, Аст. і Об'єм Необхідний адресний простір пам'яті основ, Асер. Разом Амол. пам'яті Архітектура 1-1 15 плюс 13 плюс 13 дор. 41 5 плюс 6 11 52 4 Пета слів 128 Пета Архітектура 1-2 15 плюс 10 плюс 10 плюс 10 дор. 45 5 плюс 6 11 57 слів Архітектура 2-1 15 плюс 15 дор. 30 5 плюс 6 11 41 2 Тера слів Архітектура 2-2 15 плюс 13 плюс 12 дор. 40 5 плюс 6 11 51 2 Пета слів Архітектура 3-1 17 плюс 15 дор. 32 5 плюс 6 11 43 8Тера слів Архітектура 3-2 17 плюс 14 дор. 31 5 плюс 6 11 42 4 Тера слів Таблиця 2 Порівняльний аналіз показників морфологічної обробки для програмної та апаратної реалізацій Вид реалізації Програмний Апаратний 5 10 15 20 25 Середня довжина слова 9 9 Час обробки (мкс) 937 3,72 Прискорення (+)/зповільнення (-) морфологічного аналізу (раз) мінус 252 плюс 252 ФОРМУЛА КОРИСНОЇ МОДЕЛІ Пристрій морфологічного аналізу природномовних текстів, який містить блок регістрів символів, блок дешифраторів символів, блок пам'яті основ, блок пам'яті закінчень, блок комутаторів, блок ключів і блок мікропрограмного керування, при цьому перший інформаційний вихід блока дешифраторів символів підключений до першого інформаційного входу блока пам'яті основ, а групи з першої по q-ту інформаційних виходів підключені відповідно до групи перших інформаційних входів блока ключів й інформаційних входів блока комутаторів, групи з першої по q-ту інформаційних виходів якого підключені відповідно до інформаційних входів блока пам'яті закінчень, керуючий вхід якого підключений до першого керуючого виходу блока мікропрограмного керування, а його перша група інформаційних виходів і другий інформаційний вихід підключені відповідно до другої групи інформаційних входів блока ключів та інформаційного виходу блока пам'яті основ і є інформаційним виходом пристрою, керуючі входи з першого по третій якого є відповідно керуючими входами "Пуск", "Сброс" і "Синхросигнал" блока мікропрограмного керування, другий та третій керуючі виходи якого підключені відповідно до керуючого входу блока пам'яті основ та другого керуючого входу блока регістрів символів, інформаційний вхід якого є інформаційним входом пристрою, який відрізняється тим, що в нього додатково введені лічильники символів й адрес результату й перша та друга схеми порівняння, причому перший інформаційний вхід першої схеми порівняння підключений до інформаційних входів пристрою й блока регістрів символів, на другий інформаційний вхід якої підключено код символу закінчення передачі вхідного слова, постійний на весь час роботи пристрою, перший інформаційний вхід другої схеми порівняння підключений до інформаційних виходів блока пам'яті основ, блока пам'яті закінчень та інформаційного виходу пристрою, на другий інформаційний вхід якої підключено код символу закінчення передачі результату роботи 7 UA 72914 U 5 10 пристрою, постійний на весь час роботи пристрою, а виходи першої та другої схем порівняння підключені відповідно до шостого та сьомого керуючих входів блока мікропрограмного керування, третій керуючий вихід якого підключений до перших керуючих входів лічильників символів та адрес результату, другі керуючі входи яких підключені відповідно до п'ятого керуючого входу та другого керуючого виходу блока мікропрограмного керування, четвертий керуючий вихід якого підключений до першого керуючого входу блока регістрів символів, n інформаційних виходів якого підключені відповідно до n інформаційних входів блока дешифраторів символів, а треті керуючі входи підключені до керуючих входів блока комутаторів та інформаційного виходу лічильника символів, інформаційний вихід лічильника адрес результату підключений до другого інформаційного входу блока пам'яті основ, третя група інформаційних входів якого підключена до інформаційних виходів блока дешифраторів сполучень символів, групи інформаційних входів якого підключені до відповідних груп інформаційних виходів блока ключів, четвертий і п'ятий керуючі входи блока мікропрограмного керування є керуючими входами відповідно "Читання" і "Запис" пристрою. 8 UA 72914 U 9 UA 72914 U 10 UA 72914 U Комп’ютерна верстка Л. Купенко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 11