Министерство образования и науки Российской Федерации

Омский государственный технический университет

Кафедра информатики и вычислительной техники

На правах рукописи

Борисов Константин Евгеньевич

УДК 004.048

1  Введение

В современном мире идет постоянный и быстрый рост объемов информации. Значительную часть этой информации составляют текстовые данные. В связи с этим встает проблема создания средств доступа к текстовой информации.

Технически существует возможность доступа к значительной части имеющихся текстов, но практически доступна лишь малая часть. Это связано с несовершенством средств доступа.

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

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

Смысл традиционно является субъективной характеристикой текста. Отсутствуют математические методы описания смысловой нагруженности текста и отдельных его понятий. Поэтому выделение смысловых характеристик из реального текста на естественном языке является сложной задачей. Тем не менее исследования в этом направлении ведутся.

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

Информацию о семантической близости понятий удалось использовать для построения метода поиска текстовой информации.

В работе выделены вопросы, которые показывают направления дальнейших исследований.

2  Обзор существующих подходов, основные методы и проблемы

2.1  Историческое развитие подходов к поиску текстовой информации

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

1. Привлечение специалиста. Этот способ мало отличается от устной передачи информации между людьми. Каждый специалист обладает информацией о книгах по своей специальности, а в древности ученый человек мог охватить весь спектр доступной литературы. Этот способ очень эффективен, но не мог применяться долго. Рост объемов текстовой информации сделал его невозможным.
2. Использование библиотечной картотеки. Этот способ появился одновременно с созданием библиотек. В библиотеке поиск основан на однородности и структурированности информации. Элементарной единицей информации выступает книга. Все книги одинаковы и обладают небольшим числом характеристик: автор, название, год издания и т.д. Рост количества книг потребовал дальнейшего развития библиотечных средств поиска: потребовалось различать книги по области знаний, появились обзоры литературы по конкретной теме, а также ссылки на источники, позволяющие установить связь между книгами.

   С развитием ЭВМ появились электронные каталоги, увеличивающие производительность библиотечного поиска. Такое структурирование и каталогизирование текстовой информации оказалось довольно эффективным и стало недостаточным лишь с развитием электронных текстовых источников.

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

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

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

4. Поисковые машины, использующие языки запросов. Языки запросов являются распространенным инструментом поиска данных. Собственные языки запросов являются штатным средством всех современных СУБД. Развитая теория построения компиляторов (см. [1]) позволяет дополнить поисковые машины специальными языками запросов, ориентированными на поиск текстовой информации.

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

   Например, в поисковой системе Яндекс [2] запрос «(технология | изготовление)&&(сыра | творога)», позволяет найти документы содержащие слова «технология» или «изготовление» и одновременно слова «сыра» или «творога». А запрос «путеводитель по Парижу - (агентство | тур)» позволяет найти все документы, содержащие фразу «путеводитель по Парижу», но не содержащие ни слова «агентство», ни слова «тур».

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

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

   С такой проблемой часто сталкиваются в крупных корпорациях, которые обладают большой базой текстов по определенной области. Часто поиск по этой базе должны вести неспециалисты (например, менеджеры). При этом пользователи просто не могут точно сформулировать запрос, так как они слабо разбираются в предмете.

   Необходимость проведения такого «осмысленного» поиска привела к созданию экспертных поисковых систем. При создании таких систем работает команда экспертов, которая хорошо разбирается и в предметной области, и в области поиска текстов. Поисковая система дополняется специальной базой знаний, которая позволяет учитывать смысловую связь между различными понятиями и устойчивые лексические конструкции.

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

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

Механизмы поиска текстовой информации постоянно развиваются, так как изменяются сами массивы текстовой информации, состав пользователей поисковых систем и, соответственно, требования к системам поиска.

Можно выделить некоторые тенденции:

• Объемы текстов постоянно растут. Ежедневно появляются новые документы, переводится в электронную форму уже существующая литература, причем этот процесс никак не контролируется. Прогнозируется дальнейший рост текстовой информации, а также потребности в организации поиска по ней.
• Увеличивается разнородность текстов. Электронные документы никак не структурированы. Нет никакого надежного механизма, который позволил бы определить к какой области знаний относится тот или иной документ. Имеющиеся тематические каталоги охватывают лишь малую часть текстов и никак не связаны между собой. Причем такая ситуация, видимо, будет и дальше.
• Пользователи обладают все меньшими знаниями о технологиях поиска. Круг пользователей поисковых систем постоянно растет, причем пользователи часто не понимают связь и различия между поиском информации и поиском содержащих ее текстов. Не говоря уже об отсутствии навыков использования регулярных выражений и языков запросов, у пользователей нет представления о ключевых и малозначимых словах.

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

2.2  Выделение основных проблем и некоторые существующие решения

• Проблема морфологии языка. Это одна из первых проблем, проявившихся при поиске текстовой информации. Каждое слово русского языка имеет много различных по написанию форм (Для существительных, это шесть падежей и два числа). Причем смысл слов не меняется от того, в какой форме они употреблены, и если пользователь ищет строку «человек с погонами», то он наверняка захочет, чтобы в результат попали и тексты, в которых есть фраза «люди в погонах».

  Морфологические анализаторы включены в самые крупные русскоязычные поисковые системы Internet (Яндекс, Рамблер). Имеются базы данных начальных форм слов, а также алгоритмы определения начальной формы слов, не включенных в эти базы. Поиск проводится по всем формам слов из запроса, что увеличивает эффективность поисковых машин.

• Проблема синонимичности. В языке много слов с общим смыслом. Хотя они пишутся по-разному, но означают одно и то же. Примерами синонимов являются, например, существительные «пластик» и «пластмасса». Давно существуют словари синонимов и в некоторых поисковых системах они используются для повышения надежности поиска.

  К сожалению, синонимичность слов зависит от области знаний, в которых они применяются. Например, выражения «надежный» и «эффективный» применительно к методам хранения овощей могут считаться синонимами, а в области программного обеспечения они обладают собственным смыслом.

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

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

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

2.3  Построение качественной модели исследуемой системы и определение основных требований к ней

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

Объектом поиска является текст, то есть текстовый документ в электронной форме, который содержит некоторую информацию. Причем все тексты:

• неструктурированны;
• неоднородны.

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

Второе свойство не позволяет считать все тексты одинаковыми. Тексты могут относиться к разным предметным областям, могут иметь различную внутреннюю структуру и форматирование. Даже значения одинаковых слов, входящих в разные тексты может быть различно (например, значение слова «символ» в тексте про языки программирования и про театральное искусство).

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

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

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

Таким образом, в поисковой системе имеются следующие две части:

1. пользователь, задающий ряд запросов;
2. поисковая машина, находящая документы, удовлетворяющие запросам.

Поисковая машина использует надежные алгоритмы (см. [3]), то есть если в тексте имеется подстрока, совпадающая с запросом, то это будет обнаружено в процессе работы алгоритма поиска.

Это значит, что ненадежным звеном системы является сам пользователь, который может задавать неточные запросы. Причем ошибки пользователя могут быть двух типов:

1. задание слова, имеющего отношение к теме поиска, но отсутствующего в текстах;
2. задание слова, не имеющего отношение к теме поиска.

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

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

2.4  Выводы

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

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

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

3  Учет семантической близости для повышения надежности поиска

3.1  Метрика в пространстве понятий как мера семантической близости

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

Будем понимать под термином «понятие» слово русского языка вместе с его семантикой, то есть множеством смыслов, которые несет это слово. Любое осмысленное предложение представляет собой конкретную реализацию этого абстрактного понятия. Договоримся называть такое предложение представлением. Основание рассматривать предложения в качестве основных семантических единиц частично вытекает из соображений лингвистики, где принимается, что предложение - это единица имеющая основной смысл, независящий от других предложений.

Каждое представление является реализацией всех понятий, содержащихся в нем. Каждое понятие имеет множество представлений. Таким образом, множество понятий и их представлений находятся в отношении типа «многие ко многим» и это отношение и определяет семантику языка.

Заметим, что любое предложение текста можно преобразовать в семантический предикат путем замены любого его слова, обозначающего понятие, на переменную. Например, предложение «Мама мыла раму» дает нам три возможных семантических предиката:

где X - переменная, вместо которой может быть подставлено любое понятие. Подстановкой вместо переменной понятия можно конкретное получить предложение. Например, предложение «Мама красила раму» получено подстановкой понятия «красила» в семантический предикат «Мама X раму».

При этом надо учитывать, что значение семантического предиката при подстановке понятия может быть семантически истинным или семантически ложным. Например, при подстановке в семантический предикат «Мама X раму» понятия «корова» мы даже не получим синтаксически корректного предложения, результат «Мама корова раму» не будет иметь никакого смысла.

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

Будем рассматривать предикаты, содержащие переменную лишь в одной позиции. Это позволяет упростить исследование, избежав проблем тождественности понятий и т.п. Кроме того, полученный предикат обычно имеет легко читаемый смысл. Например, семантический предикат «Мама мыла X» семантически истинен на множестве понятий, обозначающих объект, которые мама могла бы мыть.

Для построения метрики в пространстве понятий обозначим за A множество понятий языка, а за G множество представлений. Множество семантических предикатов P строится последовательной заменой слов, обозначающих понятия (значимых слов), в каждом представлении из G.

Для абстрактного семантического пространства (A, G) будем говорить, что определено множество семантических предикатов P, если определена операция подстановки p, отображающая P×A на множество U Й G, причем для каждого g О G существует такой элемент p О P, что для некоторого a О A выполняется p(p,a)=g.

Для каждого понятия a построим множество Z_a={p | p(a) О G}, то есть множество таких предикатов, подстановка a в которые дает семантически истинное значение. Метрика взаимозаменяемости на множестве понятий задается в этом случае как:

mab=1- |ZaЗZb| |ZaИZb|

(1)

То есть m_ab тем меньше, чем больший процент от их возможных употреблений в языке занимают взаимозаменяемые случаи. Значение m_ab=0 только для полных синонимов, то есть для таких слов a и b, что в предложении может использоваться любое из них (тривиальным является случай a=b). m_ab=1 для слов, которые ни в коем случае не могут быть встречены в одном контексте.

Если m_ab О (0, 1), то это означает взаимозаменяемость понятий лишь на части семантических предикатов. Например, понятия «стеклянный» и «остановившийся» будут иметь m < 1, так как они имеют сходное значение при описании взгляда человека. В то же время, например, понятия «голубой» и «бирюзовый», хотя и являются синонимами, но не будут иметь m = 0, так как в русском языке есть устойчивое сочетание слов «голубые экраны телевизоров», но не употребляется словосочетание «бирюзовые экраны телевизоров».

Наличие общего смысла у понятий a и b часто делает их взаимозаменяемыми в тексте, что означает уменьшение значения меры m_ab. В то же время большое отличие слов по смыслу часто означает невозможность взаимной их замены в предложениях. Например, довольно мало предложений, в которых на одной и той же позиции можно поставить и слово «сталь», и слово «пеликан». Еще меньше таких предложений для слов «сиреневый» и, например, «делать».

Таким образом имеется принципиальная возможность использовать такую меру для оценки схожести и различия смыслов понятий, их семантики (см. также [5]). То есть на качественном уровне показано, что для нахождения близких понятий можно сравнивать не сами эти понятия, а всевозможные контексты, в которых они встречаются.

3.2  Разработка метода оценки семантической близости понятий на основе реального текста на естественном языке

3.2.1  Понятие искусственного предиката

1. Сложность получения данных. Для анализа необходимо получить все возможные высказывания языка. Cложно даже оценить объем такого рода данных, не говоря уже о трудностях хранения и обработки. Кроме того такие данные невозможно получить, так как они нигде не представлены в чистом виде. Весь объем текстов охватывает лишь малую часть всех возможностей языка.

   Единственный возможный выход — генерация возможных высказываний. То есть по предложению «Мама мыла раму» создавать предложения «Мама мыла окно», «Мама мыла сына» и т.д. Но этот путь создает замкнутый круг, так как для возможности создания одних из других высказываний необходимо обладать знаниями о смысле понятий языка.

2. Временн\'ые затраты. Каждое понятие языка может входить в гигантское количество предложений. Для семантического сравнения понятий надо не только получить и хранить все эти предложения, но и обрабатывать их, находить общие и различные, подсчитывать те и другие. Такой объем вычислений может сделать затруднительным как практическое применение, так и исследовательское использование метода.

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

Например, при оценке семантической близости слов «банан» и «ананас» из текстов могут быть выделены следующие общие для обоих понятий фрагменты:

К сожалению, для выделения семантически законченных фрагментов из предложения надо обладать развитыми средствами синтаксического анализа. Таких средств существует очень мало (см., например, [6]), а имеющиеся мало пригодны для подобного применения.

Таким образом, необходимо констатировать, что выбор предиката, описывающего понятие, представляет собой проблему, и инструментов для решения этой проблемы в настоящее время нет. Поэтому для построения метода определения семантической близости автором был применен синтетический подход к построению предиката. Этот подход не предполагает учета семантики или синтаксиса русского языка при построении предиката.

Для построения синтетического предиката порядка r для понятия x в тексте выделяется r элементов слева и справа от самого слова x, полученные 2r элементов объединяются в предикат. При этом элементами считаются как любые слова, так и знаки препинания. Таким образом, синтетический предикат в отличие от семантического предиката имеет косвенное отношение к языку в целом, он напрямую связан с конкретным текстом или набором текстов.

Метрика m_abў при использовании синтетического предиката вычисляется по формуле, подобной выражению (1). Отличием является то, что множество синтетических представлений Gў в этом случае состоит из всех возможных наборов длины 2r+1 идущих подряд в рассматриваемом тексте слов.

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

В то же время множество синтетических предикатов и множество понятий, так же как и множество семантических предикатов находятся в отношении «многие ко многим». Благодаря этому и возможно осуществить сходное построение метрики в пространстве понятий.

3.2.2  Численная оценка близости понятий на основе реального текста

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

Gў® Aў Gў® Pў,

(2)

то на практике из текста необходимо выделять лишь множество Gў, то есть множество всех наборов длины 2r+1 элементов текста. Из данного множества легко получить множество A выделением лишь центрального элемента из каждого gў О Gў, множество Pў получается исключением этого центрального элемента.

Численная оценка осуществляется заданием функции, осуществляющей преобразование Aў×Aў®[0,1], то есть задающей соответствие между парой любых понятий и вещественным числом из отрезка [0,1].

Для такого преобразования хорошо подходит метрика взаимозаменяемости, модифицированная для случая синтетических предикатов. Определяя семантическую близость понятий a и b, надо рассмотреть множество Z_aў={pў О Pў | pў(a) О Gў}, синтетических предикатов и аналогично построенное множество Z_bў. Учитывая функциональные зависимости (2), можно сказать, что Z_aў - это множество образов в Pў прообразов элемента a из Gў.

Далее численная характеристика m_abў семантической близости понятий a и b может быть определена по формуле:

mabў=1- |ZaўЗZbў| |ZaўИZbў|

(3)

3.3  Пример определения семантической близости понятий

Продемонстрируем вышеизложенный метод на примере короткого искусственно составленного текста: «Долго книгу Вася искал. Долго рыбу Вася искал. Долго книгу Паша искал». Однотипно составленные предложения обеспечат наличие некоторых общих предикатов для понятий даже при такой мизерной длине отрывка. Результат выделения множеств A, Pў, Gў из этого текста показан в таблице .

Можно заметить, что в этом тексте проявляется семантическая близость понятий «Паша» и «Вася», так как им соответствуют общие предикаты «книгу X искал», в то же время для понятия «Вася» есть дополнительный предикат «рыбу X искал». То есть m _{Паша, Вася}ў=1/2. Аналогично, для понятий «книгу» и «рыбу» m _{книгу, рыбу}ў=1/2. Для всех остальных пар понятий a, b этого текста m_ab=1 при a № b и m_ab=0 при a=b.

Этот пример не демонстрирует эффективность вышеописанного метода, а лишь поясняет процедуру оценки семантической близости. На этом искусственном примере видна возможность ошибочной работы алгоритма. Слова «рыбу» и «книгу» метод счел достаточно близкими. Это произошло из-за единичного совпадения контекста данных слов.

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

3.4  Учет языковых особенностей

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

1. многообразие форм слов;
2. наличие различных частей речи;
3. существование синтаксической структуры предложений.

Многообразие форм слов проявляется в том, что одно и то же понятие может встречаться в тексте в виде множества различных слов. Очевидно, что слова «огня», «огню», «огнем» имеют непосредственное отношение к понятию «огонь». То есть при сравнении понятий надо учитывать все возможные формы словесного представления этих понятий.

Учет многообразия форм слов проводится с помощью лемматизации, то есть замены всех форм слов их начальной формой. Эта задача относится к задаче морфологического анализа русского языка и считается в целом решенной. Для лемматизации слов существует много коммерческих и свободно распространяемых программных продуктов (системы Диалинг и MYSTEM).

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

Во-вторых, учет частей речи позволяет выделять малозначимые слова. Наличие малозначимых слов, таких как союзы, предлоги, местоимения ведет к тому, что абсолютно разные по смыслу слова могут встречаться в одном и том же контексте. Например, синтетический предикат второго порядка «так как X еще не» довольно часто встречается в тексте. Причем вместо переменной X могут стоять самые разные слова: «он», «планета», «пока», не обладающие общим смыслом. Соответствующие предложения могут быть например такими:

• «Но так он еще не определился с выбором, разговора не получилось»;
• «А так как планета еще не была названа, то ей было дано имя»;
• «Так как пока еще не существует эффективных методов синтаксического анализа русского языка, данная проблема трудна».

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

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

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

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

3.5  Выводы

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

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

4  Разработка программного комплекса для автоматического выделения семантически близких понятий

4.1  Описание структуры программного комплекса

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

1. модуль морфологического анализа;
2. модуль лемматизации слов;
3. модуль построения синтетических предикатов;
4. модуль фильтрации синтетических предикатов;
5. модуль классификации понятий по частям речи;
6. модуль подсчета семантической близости понятий.

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

Для реализации данного программного комплекса была выбрана операционная система Linux, так как она обладает следующими достоинствами:

1. Бесплатность. Хотя для реализации учебного проекта этот фактор не играет большой роли, но разработка коммерческого продукта на базе данного программного комплекса потребует лицензирования используемого программного обеспечения, в том числе и операционной системы. ОС Linux содержит большое количество бесплатного программного обеспечения, предназначенного для разработки и отладки программ, что делает ее еще более привлекательной.
2. Распространенность и совместимость. ОС Linux широко применяется в сфере корпоративных приложений, особенно в области Internet. Кроме того, она во многом совместима с операционными системами семейства Unix. Имеются развитые средства портирования программ под другие операционные системы.
3. Простота организации межпрограммного взаимодействия. Архитектура операционной системы Linux традиционно ориентирована на интенсивный обмен между различными программами. Причем взаимодействие через потоки ввода/вывода является штатным, хорошо разработанным средством (см. [7]).

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

Кроме того, Perl является языком высокого уровня, что позволяет уменьшить объем исходного кода и сравнительно быстро менять алгоритм работы программ. Причем тот факт, что Perl является интерпретатором, не уменьшает эффективность программ, так как для регулярных выражений применяется встроенный механизм предкомпиляции. Так как работа большинства модулей сводится к многократному применения одного и того же регулярного выражения, то такая предкомпиляция является мощным средством повышения быстродействия (см. [8]).

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

Для связи программ в единый комплекс был использован язык оболочки bash, который является штатным средством написания пакетных файлов.

4.2  Модуль морфологического анализа

Морфологический анализ представляет собой довольно сложную задачу. Благодаря существованию большого количества наработок в этой области (см., например, [9]), не было нужды использовать собственные алгоритмы. При программной реализации метода оценки семантической близости понятий была использована библиотека RML, которая включает в себя систему морфологического анализа ДИАЛИНГ. Данная библиотека распространяется бесплатно на условиях лицензии LGPL.

В своей работе система ДИАЛИНГ использует три типа словарей:

• Большой словарь, который базируется на грамматическом словаре А.А.Зализняка (см. [10]);
• Словарь имен собственных;
• Словарь географических слов.

При лемматизации для каждого слова входного текста морфологический процессор выдает множество морфологических интерпретаций, в которые входят:

1. лемма;
2. морфологическая часть речи;
3. множество наборов граммем.

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

Граммема - это элементарный морфологический описатель, относящий словоформу к какому-то морфологическому классу, например, словоформе стол с леммой «стол» будут приписаны следующие наборы граммем: «мр, ед, им, но», «мр, ед, вн, но» (то есть неодушевленное существительное мужского рода в единственном числе, именительном или винительном падеже).

Текст анализируется по отдельным словам, причем для каждого слова выдается множество возможных морфологических характеристик.

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

Наличие алгоритма предсказания выгодно отличает данное средство морфологического анализа от других доступных продуктов и позволяет эффективно обрабатывать большие объемы разнородных текстов (включая специальные).

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

#Все буквы алфавита (символы, из которых могут состоять слова)
$letters="абвгдеёжзийклмнопрстуфхцчшщъыьэюяАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ";
#Входная информация считывается из стандартного потока ввода
while (<STDIN>) 
{
 while (/([$letters]+|[^$letters\r\n]+)/g)
 {
  $str=$1;
  $str=~s/[ \t]//g;
  if($str=~/[^ \t]/)
  {
   printf "$str\n";
  }
 } 
}
printf "\n";

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

Из этого потока вычленяются все слова текста в начальной форме, к ним в круглых скобках приписывается часть речи, определенная модулем морфологического анализа. Эту работу выполняет следующий скрипт:

while (<STDIN>) 
{
 while (/>[+-] ([^ ]+|[^ ]+) ([^ ]+)[ \n]/g)
 {
  printf "$1($2)\n";}} 

После такой обработку предложение «Мама мыла раму» превращается в «МАМА(С) МЫТЬ(Г) РАМА(С)», где буквы «С» и «Г» в скобках означают существительное и глагол соответственно. Таким образом информационный поток лишается избыточной информации о форме слова, но в него добавляется информация о части речи. Эта информация понадобится для работы других модулей.

4.3  Модуль построения синтетических предикатов

Этот модуль строит список всех встреченных в тексте слов с указанием контекста их встречи (синтетического предиката). Для выполнения такой работы удобно использовать специальный объект языка perl «список».

В программе имеются два списка (@leftside и @rightside), которые представляют собой левую и правую части синтетического предиката. Переменная $r задает порядок предиката, то есть радиус выборки окружения каждого слова.

Выходной поток содержит строки вида «ПОНЯТИЕ|ПРЕДИКАТ» (то есть текст с разделителями «|»). В синтетических предикатах не указывается положение переменной, так как оно фиксировано.

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

Множество всех строк выходного потока данного модуля представляет собой множество G ў, описанное в разделе 3.2.2.

$r=2; # Порядок предикатов (число включаемых в предикат
      # слов слева и справа выделенного понятий)

##### Выборка левой половины предиката
# Read the left part of predicate
$i=0;
push(@leftside, "X");
while($i<$r-1) 
{
 $curstr=<STDIN>;
 chomp($curstr);
 if(!defined($curstr))
 {
  die "Файл слишком мал!\n";
 }
 push(@leftside, $curstr);
 $i++;
}

$curstr=<STDIN>;
chomp($curstr);
if(!defined($curstr))
{
 die "Файл слишком мал!\n";
}
$word=$curstr;
# Выборка правой половины предиката
$i=0; 
while($i<$r) 
{
 $curstr=<STDIN>;
 chomp($curstr);
 if(!defined($curstr))
 {
  die "Файл слишком мал!\n";
 }
 push(@rightside, $curstr);
 $i++;
}

##### Обработка основной части файла
while ($curstr=<STDIN>) 
{
 chomp($curstr);

 # Обновить список
 shift(@leftside);         # Выделяем место для вставки слова
 push(@leftside, $word);   # Бывшее понятие входит в левую часть предиката
 $word=shift(@rightside);  # Текущее понятие берется из правой части
 push(@rightside, $curstr);# Вставляем новое слово в правую часть предиката

 # Вывод понятия и синтетического предиката в поток вывода
 printf "$word\|@leftside @rightside\n";
}

4.4  Модуль фильтрации синтетических предикатов

Для учета особенностей русского языка (см. раздел 3.4) нужно отбросить синтетические предикаты, содержащие знаки пунктуации и нераспознанные системой морфологического анализа слова (такие слова отмечены вместо части речи маркером «no»). Это делает следующий модуль:

# Вырезаем мало значащие предикаты и слова
while ($cur=<STDIN>) # Считываем очередную строку
{
 if($cur=~/[-*\"\'1234567890\.\!\?\;\:\,]|(no)/){}
 else
 {
  print $cur;
 }
}

while ($cur=<STDIN>)   # Считываем очередную строку
{                    
 $line=$cur;           # Запомним то, что считали
 $cur=~s/[^\|]+\|//;   # Оставляем только предикат, без определяемого слова
 $numgood=0;           # Число "хороших" слов в предикате
 while($cur=~/\((ПРИЧАСТИЕ|ЧИСЛ|ДЕЕПРИЧАСТИЕ|П|С|Г|ИНФИНИТИВ)\)/g)
 {
  $numgood++;
 }

 if($numgood>=2)       # Хотя бы два "хороших" слова
 {
  print $line;
 }
}

4.5  Модуль классификации понятий по частям речи

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

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

open(OUTS, ">S.txt"); # Файл для существительных
open(OUTP, ">P.txt"); # Файл для прилагательных
open(OUTG, ">G.txt"); # Файл для глаголов
while ($cur=<STDIN>)  # Считываем очередную строку
{
 $curfile=0; 
 if($cur=~/С\)\|/) # Существительное
 {
  $curfile=1;
 }
 else
 {
  if($cur=~/П\)\|/) # Прилагательное
  {
   $curfile=2;
  }
  else
  {
   if($cur=~/(Г|ИНФИНИТИВ)\)\|/) # Глагол
   {
    $curfile=3;
   }
  }
 }
 $cur=~s/\([^\)]*\)//g; # Вырезаем информацию о части речи
 # Производим запись
 if($curfile==1)
 {
  print OUTS $cur;
 }
 if($curfile==2)
 {
  print OUTP $cur;
 }
 if($curfile==3)
 {
  print OUTG $cur;
 }
 if($curfile==0)
 {
  print $cur;
 }
}

# Закрываем файлы
close(OUTS);
close(OUTP);
close(OUTG);

В результате работы всех вышеперечисленных модулей создаются три файла G.txt, P.txt и S.txt, в которых содержатся понятия (глаголы, прилагательные и существительные соответственно), а также синтетические предикаты, которым эти понятия соответствовали в обрабатываемом тексте.

Начало файла P.txt, полученного при обработке сборника рассказов А.Конан-Дойла о Шерлоке Холмсе, приведено в таблице . Можно видеть, что обработанные данные все еще содержат достаточно информации, чтобы человек смог восстановить кусочки предложений, из которых выделены данные понятия и предикаты.

4.6  Модуль подсчета семантической близости понятий

В настоящее время общепринятым средством обработки больших массивов информации являются языки запросов, являющиеся частью современных систем управления базами данных. Причем задача определения семантической близости понятий представляет собой обработку множеств с заданными отношениями с целью получения новых отношений. Таким образом, наиболее подходящим инструментом обработки имеющейся информации представляется реляционная база данных и соответствующий язык запросов (например, SQL).

Обработка проводилась с помощью системы управления баз данных PostgreSQL-7.3.2. Язык запросов этой СУБД в большой степени удовлетворяет стандарту ANSI SQL/92, что упрощает написание сложных запросов, а также обеспечивает переносимость запросов на большинство современных СУБД. Некоторые дополнительные возможности (например такие, как последовательности) позволяют с помощью запросов к базе данных реализовать функции обычно доступные лишь через внешние программы.

Вначале результат работы модулей необходимо загрузить результаты обработки текста предыдущими модулями в таблицу базы данных PostgreSQL. Это осуществляется специальной командой загрузки данных из текстового файла с разделителями.

Входной файл уже содержит отношение ТЕКСТ(ПОНЯТИЕ, ПРЕДИКАТ), это отношение и загружается в таблицу inpt.

drop table inpt; -- Удалить предыдущий вариант таблицы

create table inpt -- Создать таблицу для входных данных
(
 atom character(150), -- Поле "понятие"
 pred character(175)  -- Полу "предикат"
);

copy inpt  -- Импортировать данные из файла text.txt
 from 'text.txt'
 using delimiters '|';

Информацию, хранящуюся в символьной форму не удобно обрабатывать, особенно если учесть, что самой распространенной операцией при подсчете семантической близости является операция сравнения. Поэтому отношение ТЕКСТ заменяется тремя отношениями:

1. СПИСОК_ПОНЯТИЙ(ИДЕНТИФИКАТОР_ПОНЯТИЯ, ПОНЯТИЕ), таблица atoms;
2. СПИСОК_ПРЕДИКАТОВ(ИДЕНТИФИКАТОР_ПРЕДИКАТА, ПРЕДИКАТ), таблица preds;
3. КОДИРОВАННЫЙ_ТЕКСТ(ИДЕНТИФИКАТОР_ПОНЯТИЯ, ИДЕНТИФИКАТОР_ПРЕДИКАТА), таблица coded.

При этом имеются взаимные функциональные зависимости:

ИДЕНТИФИКАТОР_ПОНЯТИЯ « ПОНЯТИЕ, ИДЕНТИФИКАТОР_ПРЕДИКАТА « ПРЕДИКАТ.

(4)

Отношения СПИСОК_ПОНЯТИЙ и СПИСОК_ПРЕДИКАТОВ представляют собой словари для перевода соответствующих строковых значений в числовые коды (суррогатные ключи) и обратно. Эти отношения создаются с помощью следующих запросов:

-- Удалить старые таблицы и последовательности
drop table atoms;
drop sequence atoms_id_seq;
drop table preds;
drop sequence preds_id_seq;
drop table coded;

-- Создать таблицу 'atoms' и заполнить ее
create table atoms (atom) as
select distinct atom, 0 as id from inpt;
-- Создать последовательность для идентификаторов
create sequence atoms_id_seq cycle;
-- Заполнить поле идентификаторов
update atoms set  id=nextval('atoms_id_seq');
-- Проиндексировать таблицу
create unique index atoms_id on atoms(id);
create unique index atoms_atom on atoms(atom);

-- Аналогично создать и заполнить таблицу 'preds'
create table preds (pred) as
select distinct pred, 0 as id from inpt;
create sequence preds_id_seq cycle;
update preds set  id=nextval('preds_id_seq');
create unique index preds_id on preds(id);
create unique index preds_pred on preds(pred);

-- Создать и заполнить таблицу 'coded'
create table coded as
select a.id as atom_id, p.id as pred_id
 from 
  atoms a, 
  preds p, 
 where
  a.atom=g.atom
  and p.pred=g.pred;
create index coded_atomid on coded(atom_id);
create index coded_predid on coded(pred_id);

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

-- Удаляются все записи о редких понятиях из таблицы 'coded'
delete from coded 
 where atom_id in
 (
  select atom_id
   from coded counted
   group by atom_id
   having count(*)<=4 -- Должно быть не меньше 5 вхождений
 );

-- Удаляются неиспользуемые записи о понятиях
delete from atoms
 where not exists
 (
  select * from coded
  where coded.atom_id=atoms.id
 );

-- Удаляются неиспользуемые записи о предикатах
delete from preds
where not exists
(
 select * from coded
 where coded.pred_id=preds.id
);

Теперь все готово для подсчета семантической близости понятий. Результат подсчета помещается в отдельную таблицу distances, имеющую схему РАССТОЯНИЯ(АТОМ1, АТОМ2, РАССТОЯНИЕ). Вместо расстояния m, описанной в разделе 3.1, подсчитывается величина близости 1-mў.

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

-- Удалить таблицу расстояний между понятиями
drop table distances;

create table distances as
(
 select  atom1, atom2, round(numeq, 8)/round(numall, 8) as r
 from
 (
  select a1.atom as atom1, a2.atom as atom2, -- Строковое представление понятий
  (select count(*)
   from coded apeq1, coded apeq2
   where apeq1.atom_id=a1.id and apeq2.atom_id=a2.id 
    and apeq1.pred_id=apeq2.pred_id) as numeq, -- Количество одинаковых предикатов
   (select count(*)
    from coded apall
    where apall.atom_id=a1.id 
     or apall.atom_id=a2.id) as numall -- Общее количество предикатов
   from atoms a1, atoms a2
   where a1.id<a2.id
 ) dist
 where numeq<>0 order by 3);

4.7  Выводы

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

5  Проведение эксперимента по выделению семантически близких понятий из текстов русского языка

5.1  Выбор текстов для проведения эксперимента

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

1. Тексты должны иметь большой объем. Необходимо, чтобы разные понятия много раз употреблялись в одном и том же контексте. Так как автор обычно избегает близко расположенных повторяющихся групп слов, то объем текста должен быть достаточно велик.
2. Текст должен описывать одну область. Для получения результатов необходимо многократное повторение одних и тех же понятий, причем, в одном и том же значении. Если автор описывает разнообразные явления, то используемые понятия будут постоянно меняться и даже, возможно, употребляться в разных смыслах.
3. Текст должен описывать явления, действия, факты. Именно при таком описании наибольшим образом проявляется смысл слов. Не подходят тексты, основной целью которых является описание чувств, эмоций. Не подходят стихотворные тексты, так как в них большое значение имеет звучание слов, их эмоциональная окраска.
4. Текст не дожен содержать специальных символов, сокращений, иллюстраций и т.д. Такие тексты вызывают большие проблемы для морфологического анализа, требуют специальных сложных алгоритмов расшифровки сокращений. Кроме того значительная часть смысла текстов может содержаться в графиках, таблицах, числовых данных. Основная смысловая нагрузка должна ложиться на сами слова, понятия.

Список выбранных для анализа текстов представлен в таблице 3. Все эти тексты рассчитаны на массового читателя и описывают поведение одних и тех же героев в примерно одних и тех же ситуациях. Так как большинство из этих книг рассчитаны скорее на коммерческий успех, чем на литературное признание, то от автора можно ожидать использование примерно одних и тех же слов и сходных ситуаций.

Кроме того, эти книги образуют серии и имеют большой объем. Например, цикл «Неро Вульф» Рекса Стаута содержит около 6500 печатных страниц, что дает значительное количество информации для анализа.

Выбор подобных текстов в качестве объекта для анализа позволяет получить большой спектр объемов исходных данных, что способствует выявлению различных зависимостей.

5.2  Зависимость числа выделенных пар понятий от объема текста

№ текста	10	9	8	7	6	5	4	3	2	1
Число пар понятий, N	109	120	183	616	204	764	951	1018	1205	1973
Объем, V (миллионов байт)	3,82	7,46	7,48	8,39	9,37	13,38	14,58	14,74	15,45	16,15

Для выделения близких по смыслу пар понятий использовались синтетические предикаты порядка 2. Это обусловлено тем, что использование предикатов первого порядка дает слишком много ошибочных результатов (из-за слабого учета контекста), а использование предикатов более высоких порядков дает малый объем результатов, без повышения правдоподобности.

На рис. 2 показана зависимость числа выделенных из текста близких по смыслу пар понятий в зависимости от объема этого текста. Таблица под графиком содержит точные значения числа семантически близких пар для текстов. Нумерация текстов соответствует таблице 3.

Видно, что даже на относительно небольших текстах выделяется значительное число общих понятий. С ростом объема текста число близких понятий растет очень быстро. Это видимо связано с постоянным употреблением близких по смыслу слов в сходном контексте.

Нелинейность роста числа выделяемых понятий с ростом объемов обрабатываемых текстов еще более заметна на рис. 3 На этом графике по оси ординат откладывается отношение числа выделенных пар к объему текста.

Лучше видны индивидуальные особенности некоторых текстов. Например, видно, что самый маленький текст («Рассказы о Шерлоке Холмсе») содержит относительно много близких понятий. По этому графику заметно, насколько выбивается из общего ряда текст №7 («Тарзан»): по числу относительному числу выделенных понятий он приближается к текстам в два раза большего объема.

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

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

Видно, что хотя тексты отличаются по объему в 5 раз, отличия мощностей используемых словарей не так значительны. Большинство текстов укладываются в рамки 40 000-60 000 используемых слов. Это означает, что с ростом текстов одни и те же понятия встречаются все большее количество раз. Учитывая ограниченность темы, можно утверждать, что вероятность использования похожих по смыслу слов в одинаковых случаях растет очень быстро.

На рис. 5 показана зависимость квадрата отношения объема текста V к объему используемого словаря W в зависимости от объема текста. Эта зависимость построена искусственно и не обладает каким-либо точно определенным смыслом. Однако заметно сходство графиков 3 и 5. Это позволяет сделать предположение о том, что большие значения величины N для текста №7 объясняются малым набором используемых слов. Таким образом, можно пытаться предсказывать тексты, наиболее перспективные для выделения близких слов.

Тем не менее видно, что число выделенных семантически близких пар не определяются только лишь объемом текста и размером словаря произведения. Видимо, большое значение имеет стиль автора, используемая им структура предложений.

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

5.3  Распределение выделенных близких пар понятий по частям речи

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

Распределение частей речи в выделенных близких понятиях показано на рис. . Оно значительно отличается от исходного. Можно заметить значительно меньшее содержание глаголов и несколько большее содержание прилагательных и существительных. В каждом же конкретном случае изменение состава носит сложный и непредсказуемый характер.

Частично такую ситуацию объясняет рис. 8, который содержит распределение частей речи в множестве значимых понятий и предикатов Gў (см. раздел 3.2.2). Это множество содержит понятия вместе со связанными с ними синтетическими предикатами, причем предикаты обработаны с помощью морфологического процессора и не содержат знаки пунктуации и малозначимые слова (местоимения, предлоги и т.д.).

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

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

5.4  Профилирование вычислений

Обработка всех текстов проводилась на компьютере, оборудованном процессором AMD Duron-850 МГц и имеющем объем ОЗУ 512Mb.

Общее время обработки T для всех текстов представлено на рис. . Для самого большого из текстов это время составило менее 2 часов, что свидетельствует о практической применимости созданного программного комплекса.

Время предобработки T_p, включающее время подготовки текста для морфологического анализа, время морфологического анализа и время разделение понятий по частям речи гораздо меньше времени, затраченного на вычисление близости семантических понятий (см. рис. 10).

Для увеличения скорости обработки можно уменьшить количество сравниваемых понятий. Для этого можно, например, ввести аналоги стоп-листов поисковых машин Internet.

Стоп-лист содержит понятия, которые нет необходимости сравнивать с другими понятиями. Например, для глаголов это «быть», «стать» «делать». Для существительных можно выделять собственные имена и также исключать их из обработки.

Можно ужесточить требования к синтетическим предикатам. Например, потребовать, чтобы они содержали не два значимых слова, а больше. Это может не только уменьшить время обработки, но и избежать ошибочных результатов.

5.5  Анализ результатов выделения семантически близких пар понятий

Наиболее достоверной оценкой результатов выделения семантически близких понятий пока является субъективная оценка. Поэтому результаты работы программы оценивались визуально. К сожалению, объемы результирующих файлов для больших текстов не позволяют провести оценку всех результатов. Полностью будут приведены лишь семантически близкие понятия из «Рассказов о Шерлоке Холмсе» Артура Конан-Дойла.

Все выделенные программой семантически близкие глаголы представлены в таблице . Каждая строка содержит выделенную пару понятий и числовую близость для этой пары. Близость является дополнением семантического расстояния mў, введенного в разделе 3.2.2 до единицы. То есть p=1-mў, где p — близость.

Дополнительный столбец «Ошибка» содержит знак «X», если были выделены далекие по смыслу понятия. Знак «?» ставился тогда, когда выделенные понятия нельзя назвать семантически очень близкими, но тем не менее у них есть некоторый общий смысл. Например, пару «БРОСАТЬ-СКАЗАТЬ» трудно причислить и к семантически близким, и к семантически далеким. Бросать имеет значение «отрывисто сказать», которое синонимично понятию «сказать». Здесь проявляется полисемия, то есть наличие многих смыслов у одного слова. Пара понятий «ДУМАТЬ-СОБИРАТЬСЯ» также имеет нечто общее. Собираться что-то сделать — это то же самое, что и подумывать сделать это.

Отчерченная часть таблицы содержит строки, которые следовало бы отбросить. Глаголы «БЫТЬ» и «СТАТЬ» имеют довольно общий смысл и могут считаться семантически близкими практически любому другому глаголу. Избавиться от таких пар можно с помощью словаря запрещенных для сравнения слов, стоп-листа.

Ошибочная пара «ЗНАТЬ-ТЕРЯТЬ» появилась из-за наличия в тексте одного предложения «Я не буду знать ни минуты покоя», которое дает синтетический предикат «НЕ БЫТЬ НИ МИНУТА». Фраза «Не будем терять ни минуты» встречается в тексте очень часто и дает такой же предикат для понятия «ТЕРЯТЬ». Такой ошибки можно избежать, ужесточив требования к синтетическим предикатам (например, увеличив обязательное количество значимых слов или причислив понятие «БЫТЬ» к малозначимым). Ошибочная пара «СКРЫТЬСЯ-СТРЕЛЯТЬ» появилась из-за наличия в тексте похожих отрывков: «что убийца стрелял через окно» и «что убийца скрылся через окно». Избавляться от ошибок такого рода довольно сложно, потому что здесь проявляется свойство окна пропускать через себя любой предмет (убийцу или выстрел).

Выделенные прилагательные оценивать (таблица 5) трудно, так как в основном они касаются черт характера человека. Следует обратить внимание на то, что антонимы являются близкими по семантике понятиями и их выделение не является ошибкой алгоритма. Для поиска текстов удобнее считать антонимы одним понятием, так как набор антонимов понятий определяет ту же предметную область, что и сами понятия. Например, если человек вводит запрос на поиск «повышение благосостояния», то ему интересны и тексты, содержащие «снижение нищеты».

Слабое выделение прилагательных с общим смыслом является не особенностью алгоритма, а характеристикой текста. Для цикла «Тарзан» Эдгара Берроуза алгоритм вполне корректно выделяет большой набор прилагательных. Начальные понятия этого набора представлены в таблице .

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

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

Кроме того, на именах существительных проявляется несовершенство морфологического анализатора. Множество местоимений («ОН», «ОНА», «МЫ» и т.д.) классифицируются как существительные. А так как они близки по смыслу практически любому существительному (особенно если учесть, что при предобработке текст теряется информация о роде и числе), то возникает большое количество лишних пар. Следовательно, требуется либо улучшить алгоритмы морфологического анализа, либо включить подобные слова в стоп-лист и отбрасывать их при обработке.

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

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

Наилучшие результаты получены с выделением близких по смыслу глаголов. Число выделяемых пар глаголов довольно значительно, причем, число ошибочно выделенных относительно невелико. Ошибочно выделенные пары глаголов в основном расположены в области малых значений p (больших значений m), что позволяет легче их отсеивать. Для остальных частей речи это менее характерно.

5.6  Выводы

Проведенные эксперименты показали работоспособность созданного программного комплекса и его пригодность для широкого применения. Анализ полученных результатов позволяет сделать предварительный вывод о действенности метода выделения семантически близких понятий.

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

6  Применение семантической близости понятий для поиска текстовой информации

6.1  Описание метода поиска текстов

Предположим, что для любой пары понятий a и b задана численная характеристика семантической близости m_ab (см. раздел 3.1). Необходимо для запроса s= < s₁, s₂, ј, s_n > найти соответствующий по смыслу отрывок в тексте или констатировать отсутствие такого совпадения.

Рассмотрим характеристику, определяющим семантическое расстояние между запросом и некоторой выделенной строкой текста:

R(s, t)= 1 n n е i=1  m min j=1  msi,tj,

где n — число слов в запросе, m — число слов в строке-кандидате, m_si,tj — семантическое расстояние между i-м словом запроса и j-м словом строки-кандитата.

Если в выделенной строке-кандидате будут содержаться все слова запроса, то R=0, так как расстояние между равными понятиями m_aa=0, и меньше оно быть не может. Таким образом при точном совпадении запроса с фрагментом текста величина R определяет наличие в тексте всех слов запросом так же, как и при обычном поиске слов.

Если в выделенной строке-кандидате нет ни одного семантически близкого со словами запроса понятия, то есть все m_{si, tj}=1, то R=1. В этом случае констатируется отсутствие совпадения запроса с текстом аналогично обычному поиску слов.

Если в выделенной строке-кандидате есть слова, семантически близкие словам запроса понятия, то величина R характеризует степень соответствия текста запросу. Чем меньше значение R, тем точнее соответствует запрос тексту.

Таким образом множество всех строк, находящихся с запросом на расстоянии R < 1, образуют список найденных фрагментов, ранжированный по степени соответствия с исходному запросу.

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

6.2  Особенности практической реализации метода поиска

Возникающая проблема выбора строки-кандидата решается так же, как и в обычных поисковых системах. Можно в качестве такой строки выбирать сразу весь документ (в поисковой системе Яндекс такая возможность заложена в язык запросов) или последовательно выделять фрагменты фиксированного или меняющегося размера (предложения, абзацы). Если в тексте выделены несколько кандидатов t_k, то самому тексту будет соответствовать наименьшее расстояние R(s,t_k) из вычисленных.

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

Решением может быть подсчет предполагаемого значения m по практически полученному. Другим решением является использование только двух значений m, 0 и 1. Значение m_a,b=0 означает, что понятие b выделено в словарь синонимов для a. Даже такой подход не отменяет ранжирование результатов поиска, а только ограничивает возможное множество значений R числами вида [(k)/(n)], где k=1јn.

Кроме того, поиск, использующий семантическое расстояние, устойчив к ошибкам пользователя. Если в запросе будет по ошибке введено слово из другой области, то документы, содержащие остальные слова запроса (или близкие к ним) все равно будут включены в результат, правда, с большими значениями R (меньшим значение релевантности). Влияние ошибочного слова сведется к добавлению к результатам документов, содержащих это слово. Должно быть много ошибочных слов, чтобы документы, содержащие их, получили меньшие значения R, чем документы соответствующие остальным словам запроса. Но и в этом случае нужные документы не удаляются из результатов поиска и остаются доступными.

Таким образом, поиск на основе семантического расстояния обладает двумя важными особенностями:

1. Текст может включаться в результирующий список, даже если в нем отсутствуют слова запроса, достаточно наличие слов, близких к ним по смыслу;
2. Даже если запрос содержит слово, не имеющее отношения к теме поиска, это не будет означать неудачу поиска, документы, содержащие остальные слова запроса будут включены в результат.

Следовательно поиск на основе семантической близости устойчив к ошибкам поиска, описанным в разделе 2.3, и соответственно имеет повышенную надежность по сравнению с традиционными алгоритмами поиска.

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

6.3  Выводы

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

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

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

7  Заключение

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

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

• выделение и систематизация вычисляемых зависимостей, присущих естественному языку;
• выделение семантических зависимостей, присущих определенному автору;
• выделение семантических зависимостей, присущих определенной тематике.

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

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

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

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

Литература

[1]

Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты - М.: Издательский дом «Вильямс», 2001. — 768 с.

[2]

Поисковая машина «Яндекс» — описание//Belmedia. — 2000. — 2 июня. http://www.belarusmedia.com/news/internet/cdebace019c9c06e.html

[3]

Кнут Д. Искусство программирования, т.3. Сортировка и поиск, 2-е изд — М.: Издательский дом «Вильямс», 2000. — 832с.

[4]

Флоренсов А.Н. Метризация знаний в системах информации: Труды Международной научно-практической конференции KDS-2001 «ЗНАНИЕ-ДИАЛОГ-РЕШЕНИЕ», Т.1 — СПб.: «Лань», 2001. — с.608-614

[5]

Флоренсов А.Н. Об автоматическом построении ассоциативных связей в текстах: Квантитативная лингвистика и семантика. Сб. науч. тр. — Новосибирск: НГПИ, 2001. — Вып. 3. с.53-58.

[6]

Панкратов Д.В., Гершензон Л.М. Описание синтаксического анализа в системе Диалинг. — 1999. — http://www.aot.ru/docs/synan.htm

[7]

Митчелл М., Оулдем Дж., Самьюэл А. Программирование для Linux. Профессиональный подход — М.: Издательский дом «Вильямс», 2002. — 288 с.

[8]

Фридл Дж. Регулярные выражения. Библиотека программиста — СПб.: Питер, 2001. — 352с.

[9]

Аношкина Ж.Г. Морфологический процессор русского языка// Альманах «Говор» — Сыктывкар, 1995. — с.17-23.

[10]

Зализняк А.А. Грамматический словарь русского языка: словоизменение. 3-е изд. — М.: Рус.яз., 1987 год.