СПОСОБ И СИСТЕМА ДЛЯ МАШИННОГО ИЗВЛЕЧЕНИЯ И ИНТЕРПРЕТАЦИИ ТЕКСТОВОЙ ИНФОРМАЦИИ
METHOD AND SYSTEM FOR MACHINE EXTRACTION AND INTERPRETATION OF TEXT INFORMATION

ОБЛАСТЬ ИЗОБРЕТЕНИЯ
[0001] Настоящее изобретение относится к извлечению и интерпретации информации из неструктурированных текстов на естественных языках. В частности, изобретение относится к области машинного извлечения и интерпретации информации в текстовых документах.
УРОВЕНЬ ТЕХНИКИ
[0002] Большие объемы неструктурированной информации/данных на естественных языках в электронном формате становятся все более доступными, особенно в Интернете. Эта неструктурированная информация на естественных языках включает в себя различные типы текстовой информации, например, тексты на естественном языке, числа и данные. Машинное извлечение и интерпретация этой информации вызывает сложности из-за неоднозначности, разнообразия объектов реального мира, их свойств и связей между этими объектами реального мира, а также из-за неоднозначности и разнообразия форм и выражений языка. Кроме того, часто также бывает востребована машинная интерпретация речи в аудио- и видеофайлах.
[0003] Учитывая существование омонимов и омографов в естественных языках, существующие программные продукты для компьютеров (то есть прикладные программы) для машинной интерпретации информации в текстовых документах часто некорректно отражают действительный смысл языковой части документов.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
[0004] Способ извлечения информации, относящийся к системе интеллектуального анализа данных, который является неотъемлемой частью универсальной технологии анализа текста, и его ключевой признак - возможность выполнять полный семантико-синтаксический анализ вводимого текста. Этот способ включает обработку текста и создание набора деревьев семантико-синтаксических зависимостей. Деревья семантико-синтаксических зависимостей создаются синтаксическим анализатором во время анализа текста. Одно семантико-синтаксическое дерево соответствует одному предложению исходного текста. Текстовое содержимое входного текстового документа представляется в виде деревьев семантико-синтаксических зависимостей, после чего обрабатывается и выводится в виде RDF-графов (схемы описания ресурсов) с использованием компьютерного языка OWL.
[0005] Таким образом, полученный исходный текстовый документ сначала анализируется с помощью синтаксического анализатора. Этот анализ порождает набор деревьев разбора на основе семантико-синтаксических зависимостей, при этом узлы и дуги каждого дерева, дополняются различной грамматической и семантической информацией. Лес деревьев разбора затем используется в качестве входных данных для продукционной системы правил извлечения информации. Применение правил извлечения информации приводит к формированию RDF-графа анализируемого текста, согласованного с онтологией предметной области.
[0006] Способность системы к анализу синтаксической и семантической структуры текста и способ в соответствии с настоящим изобретением позволяют извлекать из текста факты и сущности. Правила извлечения фактов, которые применяются к семантико-синтаксическим деревьям, как правило лаконичны, но очень эффективны, и с легкостью покрывают большинство выражений на естественных языках. Кроме того, предлагаемая система и способ демонстрируют слабую зависимость от конкретного языка. Поскольку деревья разбора содержат не зависящие от конкретного языка данные (такие, как семантические роли или универсальные, не зависящие от языка, семантические классы), многие правила извлечения являются универсальными и могут использоваться для анализа текста на различных языках.
[0007] Настоящая система и способ извлечения информации не ограничены извлечением на основе правил, поскольку синтаксический и семантический анализ, который предшествует извлечению, не базируется на наборах правил. Анализ, выполняемый синтаксическим анализатором по настоящему изобретению, можно считать основанным на моделях, он опирается на многоуровневую модель естественного языка, созданную лингвистами и прошедшую обучение на корпусе текстов. Таким образом, настоящий способ можно считать гибридным, он является основанным на моделях на первом (подготовительном) этапе и основанным на правилах на втором этапе.
[0008] Описываются способы машинной интерпретации информации в текстовых документах.
[0009] Логические утверждения по предложениям текстового документа формируются и проверяются с помощью лингвистических характеристик и лексико-морфологических свойств семантических/синтаксических структур и их деревьев. Данные, порожденные из логических утверждений, используются для повышения корректности и глубины интерпретации информации, и могут включаться в доступные для поиска онтологии по теме для дальнейшего использования.
[0010] Различные другие аспекты и способы осуществления изобретения подробнее описаны ниже. Предполагается, что отличительные признаки одного варианта осуществления изобретения могут включаться в другие варианты осуществления без дополнительных указаний.
[ООН] Сущность изобретения не предназначена для того, чтобы она толковалась как представляющая настоящее описание в полной мере и объеме. Все цели, особенности и преимущества настоящего изобретения будут очевидны из последующего подробного описания вариантов реализации в сочетании с прилагаемыми чертежами.
[0012] Элементы новизны, считающиеся характерными для описания, изложены в прилагаемой формуле изобретения.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[0013] На Фиг. 1А приведена блок-схема, иллюстрирующая способ согласно настоящему изобретению;
[0014] На Фиг. 1В показана блок-схема, иллюстрирующая способ получения универсальных семантических структур из документов в соответствии с вариантом реализации настоящего изобретения;
[0015] На Фиг. 1С приведена блок-схема, иллюстрирующая применение продукционных правил к последовательности семантических структур;
[0016] Фиг. 2А является иллюстрацией лингвистических описаний в соответствии с одним вариантом реализации настоящего изобретения;
[0017] На Фиг. 2В приведен пример лексико-морфологической структуры предложения в соответствии с одним вариантом реализации настоящего изобретения;
[0018] На Фиг. 3 показан пример морфологических описаний в соответствии с одним вариантом реализации настоящего изобретения;
[0019] На Фиг. 4 приведен пример синтаксических описаний в соответствии с одним вариантом реализации настоящего изобретения;
[0020] На Фиг. 5 показан пример синтаксических описаний в соответствии с одним вариантом реализации настоящего изобретения;
[0021] На Фиг. 6 приведен пример лексических описаний согласно одному варианту реализации настоящего изобретения;
[0022] На Фиг. 7 показана блок-схема, иллюстрирующая последовательность структур данных в соответствии с одним вариантом реализации настоящего изобретения;
[0023] Фиг. 8 является иллюстрацией графа обобщенных составляющих предложения на английском языке в соответствии с одним вариантом реализации настоящего изобретения;
[0024] Фиг. 9 является иллюстрацией синтаксической структуры предложения, показанного на Фиг. 8, в соответствии с одним вариантом осуществления настоящего изобретения;
[0025] Фиг. 10 является иллюстрацией семантической структуры предложения, показанного на Фиг. 8, в соответствии с одним вариантом осуществления настоящего изобретения;
[0026] Фиг. 11 является схематической иллюстрацией типов утверждений в соответствии с вариантом осуществления настоящего изобретения;
[0027] Фиг. 12 представляет собой схематическое изображение последовательности операций способа извлечения информации в соответствии с одним вариантом реализации настоящего изобретения;
[0028] Фиг. 13 является иллюстрацией системы в соответствии с одним вариантом реализации настоящего изобретения.
[0029] Чтобы облегчить понимание, на чертежах для обозначения могут использоваться идентичные цифры для обозначения идентичных по существу элементов, встречающихся на разных чертежах. При необходимости к ним могут добавляться буквенно-цифровые индексы и/или суффиксы, чтобы различать такие элементы.
ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ РЕАЛИЗАЦИИ ИЗОБРЕТЕНИЯ
[0030] Задачи, признаки и преимущества настоящего изобретения будут рассмотрены ниже со ссылкой на машинную (то есть программируемую) интерпретацию текстовой информации (то есть, информации, содержащейся в текстовых документах), доступной в электронном виде на одном из естественных языков (исходных языках). Было предусмотрено, что по меньшей мере части настоящего изобретения также могут использоваться для анализа документов других типов (например, документов, содержащих буквенно-цифровые данные, многоязычных документов и т.д.).
[0031] Выход (или желательный результат) механизма извлечения в соответствии с настоящим изобретением представляет собой RDF-граф. Цель RDF (Resource Definition Framework) заключается в назначении каждому отдельному информационному объекту уникального идентификатора и запись информации о нем в виде троек SPO. «S» обозначает субъект и содержит идентификатор соответствующего объекта, «Р» означает предикат и определяет некоторое свойство объекта, «О» обозначает объект и хранит значение этого свойства. Это значение может быть как примитивным типом данных (строкой, числом, булевым значением) или идентификатором другого объекта.
[0032] Все данные RDF согласуется с OWL-онтологией, которая является предопределенной и статической. Информация о ситуациях и события моделируется способом, который идеологически похож на способ, предложенный консорциумом W3C для моделирования N-арных отношений. Согласованность извлеченной информации с моделью предметной области является встроенной особенностью этой системы. Оно обеспечивается автоматически, во-первых, благодаря синтаксису правил извлечения и, во-вторых, с помощью процедур проверки, которые не допускают формирования онтологически некорректных данных.
[0033] Настоящая система и способ извлечения информации используют в качестве входных данных уже проанализированный синтаксическим парсером текст в виде совокупности синтактико-семантических деревьев. Совокупность синтаксико-семантических деревьев является результатом глубокого синтактико-семантического анализа исходного текста. Каждое такое [дерево] соответствует одному предложению текста. Синтактико-семантические деревья получают с помощью парсера, производящего анализ текста в соответствии со способом и системой, описанной в патенте США 8,078,450, который включен в настоящее описание посредством ссылки в полном объеме. Каждое дерево, соответствующее семантической структуре, имеет узлы, соответствующие словам исходного текста.
[0034] На Фиг. 1А показана последовательность этапов (100), выполняемых системой, в соответствии с которой на этапе (110) текстовый документ поступает в систему. На этапе (120) применяются средства семантического/синтаксического анализа для преобразования текстового документа в набор (130) независимых от естественного языка документа семантико-синтаксических структур и их деревьев, выборочно соответствующих предложениям документа. Затем на этапе (140) продукционные правила применяются к набору семантико-синтаксических деревьев для получения набора утверждений (150) об объектах. Информация об этих объектах содержится в исходном тексте. Созданный набор утверждений должен быть непротиворечивым, поэтому был разработан специальный алгоритм для формирования набора утверждений, при этом упомянутый набор утверждений был назван «мешком утверждений». «Мешок утверждений» показан (150) на Фиг. 1А. Затем сформированный «мешок утверждений» используется в качестве входа для построения RDF-графа на этапе (160). Результатом метода извлечения информации является построенный RDF-граф (170).
[0035] Фиг. 1В иллюстрирует часть предлагаемого способа, относящуюся к семантико-синтаксическому анализу (120). Этот анализ (120) выполняется парсером, он приводит к построению глубокой независимой от языка структуре, которая может быть применима в различных приложениях, например, в системах машинного перевода. Система извлечения информации также использует глубинную, независимую от языка структуру, что делает правила более обобщенными и универсальными. Тем не менее, синтаксис правил позволяет системе использовать поверхностные свойства синтаксического дерева.
[0036] Обратимся к Фиг. 1В, где на входе имеется исходный документ. Если исходный документ имеет формат изображения (например,.pdf или.tiff), то любой нетекстовый документ должен быть обработан с помощью метода оптического распознавания символов (OCR) или преобразован в текстовый документ с помощью другого метода конвертации.
[0037] На этапе (114) выполняется лексико-морфологический анализ каждого предложения исходного документа (112) для выявления морфологических значений слов в предложениях; каждое предложение делится на лексические элементы, после чего определяются их леммы (начальные или основные формы), а также соответствующие варианты грамматического значения. Обычно для каждого такого элемента выявляется множество вариантов, как следствие омонимии и совпадения словоформ с различными грамматическими значениями. Схематический пример результата этапа (114) для предложения «This boy is smart, he′ll succeed in life» (Этот мальчик умный, он добьется успеха в жизни) показан на Фиг. 2В.
[0038] Лексико-морфологический анализ исходного предложения производится для построения лексико-морфологической структуры исходного предложения. Затем производится синтаксический анализ - это двухступенчатый анализ, включающий грубый синтаксический анализ исходного предложения для построения графа обобщенных составляющих на этапе (115), который активизирует синтаксические модели одного или более потенциальных лексических значений конкретного слова и устанавливает все потенциальные поверхностные связи в предложении. Этот этап приводит к построению структуры данных, которая называется «графом обобщенных составляющих». После этапа (116), на котором происходит точный синтаксический анализ на графе обобщенных составляющих для построения по меньшей мере одной синтаксической структуры в виде дерева, выполняется этап (117) получения независящей от языка семантической структуры. Этот процесс подробно описан в заявке U.S. Patent Application Ser. №11/548214, поданной 10 октября 2006 г., на основании которой был выдан патент США 8,078,450, включенный в это описание посредством ссылки во всей полноте. В общем случае создается несколько таких структур, что вызвано в основном существованием различных вариантов для лексического выбора. Каждый вариант синтаксической структуры характеризуется собственным весом; структуры сортируются от более вероятных к менее вероятным.
[0039] Наконец, на этапе (117) происходит переход от выбранного наилучшего синтаксического дерева к независимой от языка семантической структуре (118), причем узлы структуры (118) являются семантическими классами, а связи отражают семантические отношения.
[0040] Ниже приведено описание набора упомянутых лингвистических описаний и подробностей отдельных этапов семантико-синтаксического анализа. На Фиг. 2А приведена схема, иллюстрирующая используемые языковые описания (210) в соответствии с одной из возможных реализаций изобретения. Языковые описания (210) включают морфологические описания (201), синтаксические описания (202), лексические описания (203) и семантические описания (204).
[0041] Фиг. 2А иллюстрирует языковые описания (210), в том числе морфологические описания (201), лексические описания (203), синтаксические описания (202) и семантические описания (204), а также отношения между ними. Среди них морфологические описания (201), лексические описания (203) и синтаксические описания (202) зависят от языка. Каждое из этих языковых описаний (210) может быть создано для каждого исходного языка, и все вместе они представляют собой модель исходного языка. Однако семантические описания (204) не зависят от языка, они используются для описания независимых от языка семантических признаков различных языков и для построения независимых от языка семантических структур.
[0042] Фиг. 3 иллюстрирует примеры морфологических описаний. Компоненты морфологических описаний (201) включают в том числе: описание словоизменения (310), грамматическую систему (320) (например, граммемы), описание словообразования (330) и т.д. Грамматическая система (320) представляет собой набор грамматических категорий, таких как, «Часть речи», «Падеж», «Род», «Число», «Лицо», «Возвратность», «Время», «Вид» и т.д. и их значения, в дальнейшем именуемые «граммемы», включая, например, имя прилагательное, имя существительное, глагол, и т.д.; именительный, винительный, родительный и т.д. падеж; женский, мужской, средний род и т.д. и т.п.
[0043] Описание словоизменения (310) показывает, как основная форма слова может меняться в зависимости от падежа, рода, числа, времени, и т.д., и в широком смысле оно включает в себя или описывает все возможные формы этого слова. Словообразование (330) описывает, какие новые слова могут быть созданы с участием этого слова (например, в немецком языке имеется множество составных слов). Граммемы - это единицы грамматических систем (320), граммемы могут использоваться для описания словоизменения (310) и словообразования (330).
[0044] При установлении синтаксических отношений для элементов исходного предложения используется составная модель. Составляющая может содержать группу соседних слов в предложении и вести себя как единое целое. Ядром составляющей является слово, она также может содержать дочерние составляющие на более низких уровнях. Дочерняя составляющая является зависимой составляющей и может быть прикреплена к другим составляющим (в качестве родительских составляющих) для построения синтаксических описаний исходного предложения.
[0045] Фиг. 4 иллюстрирует примеры синтаксических описаний. Компоненты синтаксических описаний (202) могут включать в том числе: поверхностные модели (410), описания поверхностных позиций (420), описания референциального и структурного контроля (456), описания управления и согласования (440), описание недревесного синтаксиса (450) и правила анализа (460). Синтаксические описания (202) используются для построения возможных синтаксических структур исходного предложения на данном исходном языке с учетом свободного линейного порядка слов, недревесных синтаксических явлений (например, согласование, эллипсис и т.д.), референциальных отношений и других соображений.
[0046] Поверхностные модели (410) представлены в виде совокупностей одной или более синтаксических форм («синтформ» (412)) для описания возможных синтаксических структур предложений, входящих в синтаксическое описание (202). Обычно лексическое значение языка связано с поверхностными (синтаксическими) моделями (410), которые представляют компоненты, возможные в том случае, когда лексическое значение играет роль «ядра» и включает набор поверхностных позиций дочерних элементов, описание линейного порядка, диатез и т.д.
[0047] Поверхностные модели (410) представлены синтформами (412). Каждая синтформа (412) может включать определенное лексическое значение, которое играет роль «ядра» и может дополнительно включать набор поверхностных позиций (415) своих дочерних составляющих, описание линейного порядка (416), диатезы (417), грамматические значения (414), описания управления и согласования (440), коммуникативные описания (480) в отношении ядра составляющей.
[0048] Описание линейного порядка (416) представлено в виде выражений линейного порядка, которые построены для выражения последовательности, и в которой различные поверхностные позиции (415) могут встречаться в предложении. Выражения линейного порядка могут включать имена переменных, имена поверхностных позиций, круглые скобки, граммемы, рейтинги и оператор «или» и т.д. Например, описание линейного порядка для простого предложения «Boys play football.» (Мальчики играют в футбол.) можно представить в виде «Подлежащее Ядро Прямое_Дополнение», где «Подлежащее» и «Прямое_Дополнение» являются именами поверхностных позиций (415), соответствующих порядку слов. Заполнители поверхностных позиций (415), указанные символами сущностей предложения, присутствуют в том же порядке для сущностей в выражениях линейного порядка.
[0049] Коммуникативные описания (480) описывают порядок слов в синтформе (412) с точки зрения коммуникативных актов, которые должны быть представлены в виде выражений коммуникативного порядка, похожих на выражения линейного порядка. Описание управления и согласования (440) содержит правила и ограничения на грамматические значения прикрепленных составляющих, которые используются во время синтаксического анализа.
[0050] Описания недревесного синтаксиса (450) связаны с обработкой различных языковых явлений, таких как эллипсис и согласование, они используются при трансформациях синтаксических структур, которые создаются на различных этапах анализа в различных вариантах реализации изобретения. Описания недревесного синтаксиса (450) среди прочего включают описание эллипсиса (452), описание сочинения (454), а также описание референциального и структурного контроля (456).
[0051] Правила анализа (460) как часть синтаксических описаний (202) могут включать в том числе: правила вычисления семантем (462) и правила нормализации (464). Несмотря на то, что правила анализа (460) используются на этапе семантического анализа, правила анализа (460) обычно описывают свойства конкретного языка, и они связаны с синтаксическими описаниями (202). Правила нормализации (464) обычно используются в качестве правил трансформации для описания трансформаций семантических структур, которые могут отличаться в разных языках.
[0052] На Фиг. 5 приведены примеры семантических описаний. Компоненты семантических описаний (204) не зависят от языка, они могут включать в том числе: семантическую иерархию (510), описания глубинных позиций (520), систему семантем (530) и прагматические описания (540).
[0053] Семантическая иерархия (510) состоит из семантических понятий (семантических сущностей) и именованных семантических классов, расположенных в иерархических взаимоотношениях типа "родитель-потомок". В общем случае дочерний семантический класс наследует большинство свойств своего прямого родителя и все родовые семантические классы. Например, семантический класс SUBSTANCE (вещество) является дочерним для семантического класса ENTITY (сущность) и родителем для семантических классов GAS (газ), LIQUID (жидкость), METAL (металл), WOOD MATERIAL (дерево) и т.д.
[0054] Каждый семантический класс в семантической иерархии (510) предоставляется с глубинной моделью (512). Глубинная модель (512) семантического класса представляет собой набор глубинных позиций (514), которые отражают семантические роли дочерних составляющих в различных предложениях с объектами семантического класса в качестве основной родительской составляющей, а также возможные семантические классы в качестве заполнителей глубинных позиций. Глубинные позиции (514) выражают семантические отношения, в том числе, например, «агент», «адресат», «инструмент», «количество» и т.д. Дочерний семантический класс наследует и уточняет глубинную модель (512) своего прямого родительского семантического класса.
[0055] Описания глубинных позиций (520) используются для описания общих свойств глубинных позиций (514), они отражают семантические роли дочерних составляющих в глубинных моделях (512). Описания глубинных позиций (520) также содержат грамматические и семантические ограничения заполнителей глубинных позиций (514). Свойства и ограничения глубинных позиций (514) и их возможных заполнителей очень похожи и зачастую бывают идентичны в разных языках. Таким образом, глубинные позиции (514) не зависят от языка.
[0056] Система семантем (530) представляет собой набор семантических категорий и семантем, которые представляют значения семантических категорий. В качестве примера семантическую категорию «DegreeOfComparison» (Степень сравнения) можно использовать для описания степени сравнения прилагательных, ее семантемами могут быть, например, «Positive» (Положительная), «ComparativeHigherDegree» (Сравнительная степень), «SuperlativeHighestDegree» (Превосходная степень) и др. Другой пример: семантическая категория «RelationToReferencePoint» (Отношение к некоторой исходной точке) может быть использована для описания порядка объектов или событий до (<<Previous>>) или после (<<Subsequent>>) точки отсчета. Это может быть порядок в пространстве или времени в широком смысле., В еще одном примере можно использовать семантическую категорию «EvaluationObjective» (Объективная оценка) для описания объективной оценки, такой как «Bad» (Плохой), «Good» (Хороший) и т.д.
[0057] Система семантем (530) включает независимые от языка семантические атрибуты, которые могут выражать не только семантические характеристики, но и стилистические, прагматические и коммуникативные характеристики. Некоторые семантемы можно использовать для выражения атомарного значения, которое находит регулярное грамматическое и (или) лексическое выражение в языке. По назначению и использованию систему семантем (530) можно разделить на различные виды, которые включают в том числе: грамматические семантемы (532), лексические семантемы (534) и классифицирующие грамматические (дифференцирующие) семантемы (536).
[0058] Грамматические семантемы (532) используются для описания грамматических свойств составляющих при преобразовании синтаксического дерева в семантическую структуру. Лексические семантемы (534) описывают конкретные свойства объектов (например, «быть плоским» или «являться жидкостью»), они используются в описаниях глубинных позиций (520) как ограничение заполнителей глубинных позиций (например, для глаголов «face (with)» (быть обращенным к) и «flood» (заливать), соответственно). Классифицирующие грамматические (дифференцирующие) семантемы (536) выражают дифференцирующие свойства объектов внутри одного семантического класса; например, в семантическом классе HAIRDRESSER (парикмахер) семантема <<RelatedToMen>> (Относится к мужчинам) присваивается лексическому значению «barber» (цирюльник), в отличие от других лексических значений, которые также относятся к этому классу, например, «hairdresser» (парикмахер), «hairstylist» (стилист по прическам) и т.д.
[0059] Следует отметить, что важная особенность системы и способа настоящего изобретения заключается в использовании в правилах извлечения информации из документа универсальных и независящих от языка особенностей, таких как семантические описания - семантические классы, семантемы и т.п.
[0060] Прагматические описания (540) позволяет системе назначить соответствующую тему, стиль или жанр для текстов и объектов семантической иерархии (510). Например, «Экономика», «Внешняя политика», «Юстиция», «Законодательство», «Торговля», «Финансы» и т.д. Прагматические свойства также могут выражаться при помощи семантемам. Например, прагматический контекст может приниматься во внимание при семантическом анализе.
[0061] Фиг. 6 иллюстрирует примеры лексических описаний. Лексические описания (203) представляют собой лексико-семантический словарь (604), включающий множество лексических значений (612) конкретного языка, каждое из которых имеет свое семантическое значение (610) и грамматическое значение (608). Для каждого лексического значения (612) имеется связь (602) с его независимым от языка семантическим предком, чтобы указать положение того или иного заданного лексического значения в семантической иерархии (510).
[0062] Каждое лексическое значение (612) связано со своей глубинной моделью (512), которая описывается независимыми от языка терминами, и с поверхностной моделью (410), в конкретном языке. Диатезы можно использовать в качестве «интерфейса» между поверхностными моделями (410) и глубинными моделями (512) для каждого лексического значения (612). Каждой поверхностной позиции (415) в каждой синтформе (412) поверхностных моделей (410) можно сопоставить одну или более диатез (417).
[0063] В то время как поверхностная модель (410) описывает синтаксические роли заполнителей поверхностных позиций, глубинная модель (512) обычно описывает их семантические роли. Описание глубинной позиции (520) выражает семантический тип возможного заполнителя, отражает реальные аспекты ситуаций, свойства или атрибуты объектов, обозначенных словами любого естественного языка. Каждое описание глубинной позиции (520) не зависит от языка, поскольку в различных языках используется одна и та же глубинная позиция для описания аналогичных семантических отношений или выражения подобных аспектов ситуаций, и, как правило, заполнители глубинных позиций (514) обладают одними и теми же семантическими свойствами даже в разных языках. Каждое лексическое значение (612) лексического описания языка наследует семантический класс от своего родителя и настраивает свою глубинную модель (512).
[0064] На Фиг. 2В показаны основные этапы процесса семантико-синтаксического анализа. Кроме того, на Фиг. 7 показана последовательность структур данных, формируемых в ходе такого анализа.
[0065] Предварительно на этапе (212) исходное предложение на исходном языке подвергается лексико-морфологическому анализу для построения лексико-морфологической структуры (722) исходного предложения. Лексико-морфологическая структура (722) представляет собой набор всех возможных пар «лексическое значение - грамматическое значение» для каждого лексического элемента (слова) в предложении. Пример такой структуры приведен на Фиг. 2В.
[0066] Затем проводится первый этап синтаксического анализа в лексико-морфологической структуре - грубый синтаксический анализ (115) исходного предложения для построения графа обобщенных составляющих (732). В процессе грубого синтаксического анализа (115) к каждому элементу лексико-морфологической структуры (722) применяются все возможные синтаксические модели для этого лексического значения, они проверяются для того, чтобы найти все потенциальные синтаксические связи в этом предложении, которые выражаются в графе обобщенных составляющих (732).
[0067] Граф обобщенных составляющих (732) представляет собой ациклический граф, узлами котором являются обобщенные (это означает, что они хранят все варианты) лексические значения слов в предложении, а ветви - это поверхностные (синтаксические) позиции, выражающие различные типы отношений между объединенными лексическими значениями. Все возможные поверхностные синтаксические модели активируются для каждого элемента лексико-морфологической структуры предложения в качестве потенциального ядра составляющих. Затем все возможные составляющие строятся и обобщаются в графе обобщенных составляющих (732). Соответственно, рассматриваются все возможные синтаксические модели и синтаксические структуры исходного предложения (212), и в результате на основе набора обобщенных составляющих строится граф обобщенных составляющих (732). Граф обобщенных составляющих (732) на уровне поверхностной модели отражает все потенциально возможные связи между словами исходного предложения (212). Поскольку количество вариаций синтаксического разбора в общем случае может оказаться большим, граф обобщенных составляющих (732) является избыточным, он имеет большое число вариантов как в отношении выбора лексического значения для вершины, так и в отношении выбора поверхностных позиций для дуг графа.
[0068] Граф обобщенных составляющих (732) изначально строится как дерево от листов к корневому узлу (снизу вверх). Составляющие строятся снизу вверх путем добавления дочерних составляющих к родительским составляющим, заполняя поверхностные позиции (415) родительских составляющих для того, чтобы охватить все начальные лексические единицы исходного предложения (212).
[0069] Корень дерева, являющийся основной вершиной графа (732), обычно представляет предикат. В ходе этого процесса дерево обычно становится графом, поскольку компоненты более низкого уровня (листья) могут включаться в различные составляющие более высокого уровня (корень). Составляющие, построенные для одних и тех же составляющих лексико-морфологической структуры, могут быть впоследствии обобщены для создания обобщенных составляющих. Составляющие обобщаются на основе лексических значений (612) или грамматических значений (414), например, для значений одних и тех же частей речи. На Фиг. 8 показан схематический пример графа обобщенной составляющей для упомянутого выше предложения «This boy is smart, he′ll succeed in life» (Этот мальчик умный, он добьется успеха в жизни).
[0070] Точный синтаксический анализ (116) выполняется для выделения синтаксического дерева (742) из графа обобщенных составляющих (732). Строится одно или более синтаксических деревьев, и для каждого из них вычисляется интегральная оценка на основе использования набора априорных и вычисляемых оценок, затем дерево с наилучшей оценкой выбирается для построения наилучшей синтаксической структуры (746) исходного предложения. Синтаксические деревья формируются в процессе выдвижения и проверки гипотез о возможной синтаксической структуре предложения, в этом процессе гипотезы о структуре частей предложения формируются в рамках гипотезы о структуре всего предложения.
[0071] Во время конвертации из выбранного дерева в синтаксическую структуру (746) устанавливаются недревесные связи. Если невозможно установить недревесные связи, то выбирается следующее синтаксическое дерево с наивысшим рангом и производится попытка использовать его для формирования недревесных связей. Результатом точного анализа является "лучшая" синтаксическая структура (746) анализируемого предложения.
[0072] На этапе (117) производится переход к независимой от языка семантической структуре (218), которая выражает смысл предложения на основе универсальных, не зависимых от языка понятий. Независимая от языка семантическая структура предложения представлена в виде ациклического графа (деревьев, дополненных недревесными связями), причем все слова на конкретном языке заменяются универсальными (независимыми от языка) семантическими сущностями, называемыми в этом документе «семантическими классами». Этот переход осуществляется с помощью семантических описаний (510) и правил анализа (460), которые формируют структуру в виде дерева или графа с верхним узлом, в котором узлы соответствуют семантическим классам, имеющим набор атрибутов (атрибуты выражают лексические, синтаксические и семантические свойства конкретных слов в исходном предложении), а дуги являются глубинными (семантическими) отношениями между словами (вершинами), которые они соединяют.
[0073] Построение языковой семантической структуры (117) завершается на этапе (118) построения семантической структуры. На Фиг. 9 показан пример синтаксической структуры исходного предложения на английском языке «This boy is smart, he′ll succeed in life» (Этот мальчик умный, он добьется успеха в жизни), а на Фиг. 10 показана соответствующая семантическая структура.
[0074] Аннотированный RDF-граф формируется на самом окончательном этапе процесса извлечения информации, в то время как во время процесса используется более сложная структура для хранения информации. Эту структуру можно описать как совокупность непротиворечивых утверждений об информационных объектах и их свойствах, это так называемый «мешок утверждений».
[0075] Упомянутый выше аннотированный RDF-граф также можно рассматривать как мешок утверждений, если каждая тройка SPO и каждая связь от объекта к сегменту текста считается утверждением об этом объекте. Однако, существует различие между структурой для хранения временной информации (внутренней структурой) и конечной продукцией в форме RDF-графа. Основное различие заключается в том, что утверждения из внутренней структуры могут использоваться для создания функциональных зависимостей, т.е. некоторые утверждения могут зависеть от наличия других свойств и/или зависимостей. Например, множество значений определенного свойства объекта может содержать набор значений какого-либо другого свойства другого объекта. Если набор значений второго объекта изменяется, то свойство первого объекта также изменяется. Такие утверждения (которые используют функциональные зависимости) далее называются «динамическими утверждениями». Еще одно отличие внутренней структуры заключается в том, что она может содержать некоторые дополнительные утверждения, которые не соответствуют окончательной структуре аннотированного RDF-графа, и используются только в процессе извлечения.
[0076] Ниже приведен список возможных типов утверждений:
[0077] 1. Кумулятивность. Добавлять в мешок новые утверждения можно, а удалять -нельзя.
[0078] 2. Непротиворечивость. Все утверждения в мешке не противоречат друг другу.
[0079] 3. Онтологичность. По мешку утверждений в любой момент можно построить аннотированный RDF-граф, согласованный с определенной онтологией.
[0080] 4. Транзакционность. Утверждения в мешок добавляются группами. Если хотя бы одно утверждение в группе входит в противоречие с другими утверждениями мешка, то отменяется добавление всех утверждений группы.
[0081] Ниже приведен список типов утверждений:
[0082] 1. Утверждения о существовании объекта
[0083] Утверждения существования постулируют существование информационных объектов и присваивают им уникальные идентификаторы.
[0084] 2. Утверждения о принадлежности классу
[0085] Утверждения, которые приписывают объекты классам в онтологии. В соответствии с концепцией OWL один и тот же экземпляр может входить более чем в один класс, поэтому утверждений данного типа для одного и того же объекта в мешке может быть несколько. Единственным ограничением является то, что соответствующие классы должны быть совместны, то есть не должно быть утверждений DisjointWith, блокирующих данную комбинацию классов. Система следит за выполнением этого требования при добавлении утверждений в мешок и не допускает возникновения противоречий. Утверждения о принадлежности классу могут быть динамическими: можно утверждать, что данный объект относится к тем же классам, что и некоторый другой.
[0086] 3. Утверждения о свойствах
[0087] Утверждения, которые задают свойства информационных объектов. В утверждении о свойствах набор значений свойств объекта включает некоторое конкретное значение. В соответствии с концепцией RDF оно может либо являться идентификатором другого информационного объекта, либо относится к простому типу данных (числовому, строковому, булевому). В раскрываемой системе идентификаторы узлов разбора дерева используются в качестве значений свойств (дополнительного простого типа данных). Такие свойства используются только во время процесса извлечения информации и не попадают в финальный RDF-граф.
[0088] Утверждения о свойствах могут быть динамическими. Допускается использование функций различной сложности, вычисляющих свойства на основании свойств других объектов. В качестве примера простой функции можно привести копирование значений (возможность утверждать, что множество значений некоторого свойства одного объекта включает в себя все значения некоторого свойства другого объекта). Примером сложной функции может служить функция генерации нормализованной строки по набору узлов дерева разбора. Эта функция задействует модуль синтеза текста.
[0089] Несколько утверждений об одном и том же свойстве одного объекта могут приводить к онтологическим противоречиям. Например, если суммарное количество значений этого свойства превышает максимальную кардинальность, заданную для данного свойства. Модуль извлечения информации не допускает появления подобных противоречий, отвергая любую группу утверждений, которая провоцирует противоречия.
[0090] 4. Утверждения об аннотациях
[0091] Утверждения об аннотациях позволяют связывать с информационным объектом некоторый отрезок исходного текста. Координаты аннотации вычисляются по границам узлов семантико-синтаксических деревьев. Для задания аннотации можно использовать один узел (т.е. слово) или целое поддерево этого узла.
[0092] Мешок утверждений может содержать несколько утверждений об аннотациях. Это означает, что аннотация объекта может состоять из нескольких отрезков (быть разрывной).
[0093] Утверждения об аннотациях могут быть динамическими. В частности, допускается возможность копирования аннотаций другого объекта и генерация аннотации по набору значений некоторого свойства (если эти значения содержат ссылки на узлы дерева разбора).
[0094] Утверждения об аннотациях не могут приводить к противоречиям.
[0095] 5. Утверждения о якорях
[0096] В рамках всего описываемого механизма извлечения информации утверждения о якорях занимают очень важное место. Утверждения такого рода позволяют привязывать информационные объекты к узлам дерева разбора, что позволяет повторно обращаться к этим объектам в дальнейшем в процессе извлечения. Термин «якорь» был придуман в процессе разработки системы, т.к. требовался для обозначения связей между объектами и узлами дерева. Один объект может быть зацеплен якорями за некоторый набор узлов с помощью нескольких утверждений о якорях.
[0097] Якоря специальным образом обрабатываются интерпретатором правил извлечения информации (которые описаны ниже): в левых (шаблонных) частях этих правил в системе могут использоваться так называемые объектные условия, позволяющие утверждать, что для успешного применения данного правила необходимо, чтобы к тому или иному узлу семантико-синтаксической структуры уже заранее был привязан ("приякорен") информационный объект определенного вида. Если такой объект будет найден, то к нему можно получить доступ, и он может быть изменен во время применения в правой части правила.
[0098] Объектные условия, в первую очередь, используются в правилах, выделяющих факты, но оказывается, что их удобно использовать и в ряде случаев для выделения именованных сущностей, т.к. благодаря объектным условиям удается разбивать процедуру выделения информационного объекта на несколько простых этапов. Например, одно правило может только создавать "персону", а несколько других могут выделять отдельные свойства (имя, фамилию, отчество и т.п.). Кроме того, достаточно распространенной техникой стало введение служебных информационных объектов, выполняющих роль динамических помет узлов дерева разбора. В одних правилах эти пометы создаются и прикрепляются к определенным узлам, а затем в других правилах проверяется наличие этих объектов (с помощью объектных условий в их левых частях).
[0099] В утверждении о якорях можно прикрепить якорь не только к непосредственно указанному узлу, но также и ко всем кореферентным с ним узлам (т.е. узлам, связанным с ним недревесными связями семантико-синтаксических деревьев). Эта возможность очень важна для повышения полноты выделения фактов - выделяемые информационные объекты автоматически связываются с их кореферентными узлами. В результате объект одновременно появляется в нескольких контекстах, и он может использоваться правилами, выделяющими факты.
[00100] Утверждения о якорях не могут вносить какие-либо противоречия.
[00101] 6. Утверждения об идентичности
[00102] В процессе извлечения информации часто возникают ситуации, в которых удается понять, что некоторые информационные объекты на самом деле описывают одну и ту же сущность реального мира, и поэтому должны быть объединены в один объект. Один очевидный пример: когда в разных местах текста независимо выделяются упоминания одной и той же персоны. На первом этапе каждому упоминанию соответствует отдельный информационный объект, однако они могут быть объединены в дальнейшем при совпадении имен и фамилий.
[00103] Объявить, что два информационных объекта являются одним и тем же, можно с помощью утверждения об идентичности. Это утверждение добавляется в мешок утверждений, после чего все утверждения мешка, характеризующие исходные объекты, считаются верными для нового объекта, представляющего их объединение.
[00104] Утверждения об идентичности двух объектов могут входить в противоречие с утверждениями некоторых других типов. Например, при объединении объектов могут возникать несовместные группы концептов или свойства, количество значений которых превышает максимальную кардинальность, заданную в онтологии. Возможны и другие более сложные варианты противоречий.
[00105] 7. Функциональные ограничения
[00106] В некоторых случаях удобно наложить на группу информационных объектов какое-то ограничение. Можно добавить функцию, возвращающую значение булева типа и принимающую в качестве аргументов набор идентификаторов информационных объектов и каких-то констант (например, идентификаторов узлов деревьев разбора). В момент добавления в мешок функция должно быть истинной. После добавления гарантируется, что в мешок утверждений не будет добавлено ни одно утверждение, благодаря которому значение функции станет ложным.
[00107] На Фиг. 11 схематично изображены все типы утверждений,, используемых в процессе извлечения информации. Ромбы обозначают информационные объекты (например, лица, сущности, персоны, местоположения, организации, факты и т.д.), эллипсы - классы (или концепты), а прямоугольники - узлы деревьев разбора.
[00108] Как уже упоминалось выше, утверждения могут быть динамическими, то есть они могут зависеть от других утверждений. Следует отметить, что в связи с этим обстоятельством при добавлении новых утверждений в мешок могут возникать противоречия, вызванные не непосредственно добавляемым утверждением, а утверждениями, зависящими от него. Это привело к определенным сложностям при реализации алгоритма, моделирующего поведение мешка утверждений. Тем не менее, все эти проблемы были решены.
[00109] Большая часть проверок согласованности выполняется в процессе добавления утверждений в мешок. Однако некоторые проверки можно делать только после того как процесс извлечения информации завершился. Например, проверки того, что количество значений свойств превышает минимальную кардинальность. После завершения процесса извлечения информации, в ходе преобразования мешка утверждений в аннотированный RDF-граф какая-то часть информации может отфильтровываться (например, служебные объекты и свойства).
[00110] Теперь, когда изложен способ хранения информации в ходе процесса извлечения, опишем механизм применения правил извлечения и формирования утверждений в отношении информационных объектов.
[00111] Процесс извлечения информации управляется системой продукционных правил. Существует два типа правил: правила интерпретации поддерева разбора (или просто правила интерпретации) и правила идентификации. В этом описании изобретения приведены описания правил обоих типов. Поскольку правила интерпретации используются гораздо чаще, то если точный тип правила не указан, имеется в виду правило интерпретации.
[00112] При проектировании механизма извлечения преследовались несколько целей. В первую очередь, намерение заключалось в том, чтобы использовать такие преимущества систем продукционных правил, как модульность и отделение знания от управления. Во-вторых, реализована эффективная (детерминированная) модель вывода. По аналогии с классическими продукционными системами можно определить лес деревьев разбора и мешок логических утверждений как базу знаний, в то время как сам процесс извлечения можно описать как логический вывод на основе данных. Следует отметить, что в общем случае нет гарантии, что процесс применения правил извлечения информации не будет зацикливаться. Однако возникновение цикла в реальной системе правил безусловно означает наличие логической ошибки в каком-то правиле. Как правило, ее легко найти и исправить, поскольку в алгоритм встроена эвристика, позволяющая обнаружить правила, которые вызвали зацикливание.
[00113] Правила интерпретации позволяют указать фрагменты деревьев разбора, которые должны быть обнаружены для некоторых логических утверждений, чтобы они стали истинными. Одно правило представляет собой продукцию, левой частью которой является эталон фрагмента семантико-синтаксического дерева, а правой - набор выражений, описывающих утверждения об информационных объектах.
[00114] Шаблоны деревьев разбора (далее «древесные шаблоны») представляют собой формулы, атомарными элементами которых являются проверки некоторых свойств узлов деревьев (например, наличие той или иной граммемы/семантемы, принадлежности определенному семантическому или лексическому классу, нахождения в некоторой поверхностной или глубинной позиции и многие другие свойства, полученные из результатов разбора). Помимо основных логических связок (конъюнкция, дизъюнкция, отрицание) в древесных шаблонах допускается использование операций, характеризующих взаимное расположение узлов в дереве. Например, можно проверить, находится ли узел в поддереве другого узла.
[00115] В большинстве случаев древесные шаблоны описывают связные фрагменты семантико-синтаксических деревьев (т.е. поддеревья). Единственным исключением является специальное анафорическое состояние. Это условие позволяет искать узлы в левом контексте некоторого узла, полностью игнорируя древесную структуру (в том числе и в соседних предложениях). Такие правила применяются для обработки сложных случаев кореференции (например, именной анафоры).
[00116] В древесных шаблонах могут встречаться условия, которые требуют, чтобы информационный объект был привязан якорями к соответствующему узлу дерева разбора. Это так называемые положительные объектные условия. Эти правила также поддерживают отрицательные объектные условия, которые требуют, чтобы к узлу не были привязаны объекты определенного типа. Объектные условия уже упоминались выше в связи с утверждениями о якорях.
[00117] Когда утверждение добавляется к правой части правил, часто требуется ссылаться на узлы означенного в левой части фрагмента узлов поддерева, а иногда и к информационным объектам, прикрепленным к этим узлам. Для этого вводятся имена (или переменные) для отдельных частей древесных шаблонов. Если определенное поддерево соответствует шаблону, то его узлы становятся доступными по именам частей шаблона. Эти имена могут использоваться в правой части правил для формулировки утверждений об объектах. В некоторых случаях они также могут использоваться в левых частях (для формулировки сложных условий, выражающих некоторую зависимость между несколькими узлами дерева). Переменные могут быть множественными или уникальными. С множественными переменными может сопоставиться более одного узла, а с уникальными - максимум один.
[00118] Для доступа к информационным объектам, сопоставленным с положительными объектными условиями, в правых частях правил используется специальная запись «Х.о», где X - это имя уникальной переменной, назначенной узлу, в зону действия которой попадает это условие. Переменная X должна быть уникальной, поскольку в процессе соотнесения шаблона с деревом в момент проверки объектного условия нужно однозначно понимать, к какому именно узлу дерева должен быть привязан информационный объект.
[00119] Правила идентификации применяются в тех ситуациях, когда требуется сливать (объединять) пару объектов. Правило идентификации представляет собой продукцию, в левой части которой описываются ограничения, накладываемые на два объекта. Если эти условия выполняются для пары объектов, то эти объекты будут объединяются в один объект. Правая часть всех правил идентификации считается одинаковой (это одно утверждение об идентичности двух объектов) и не записывается.
[00121] Существенным отличием правил идентификации от правил интерпретации является то, что правила идентификации работают только с информационными объектами - нет возможности обращаться к узлам деревьев. Предполагается, что вся необходимая для идентификации информация должна храниться в свойствах объектов (включая служебные свойства, недоступные для конечного пользователя).
[00122] Ниже приведен пример правила интерпретации.
[00123] Согласование шаблона дерева с сегментом дерева можно представить в виде пары <г, Vr>, где r - уникальный идентификатор правила, a Vr - набор отображений, в которых
[00124] - каждой множественной переменной правила г соответствует множество узлов семантико-синтаксических деревьев;
[00125] - каждой уникальной переменной соответствует ровно один узел;
[00126] - каждой уникальной переменной, в зоне действия которой есть положительное объектное условие, соответствует определенный информационный объект.
[00127] Заметим, что при наличии сопоставления правая часть правила интерпретации может быть однозначно преобразована в набор логических утверждений.
[00128] Для правила идентификации сопоставление - это тройка <r,o1,o2>, где r - идентификатор правила, a o1 и о2 - информационные объекты. Эти объекты отвечают первому и второму состояниям объекта, соответственно. По аналогии с правилами интерпретации, при наличии конкретного сопоставления для некоторого правила идентификации, становится возможным обработать его правую часть, т.е. сформулировать утверждение об идентичности двух объектов.
[00129] Поэтому, возвращаясь к Фиг. 1А, алгоритм извлечения информации выглядит следующим образом:
[00130] Предварительный этап (120, Фиг. 1А) - анализ входного текста (100) с помощью парсера, чтобы получить лес семантико-синтаксических деревьев разбора. Дальнейшие этапы показаны на Фиг. 1С. Этап (141) - поиск всех сопоставлений для правил интерпретации без объектных условий. Добавление найденных сопоставлений в сортированную очередь сопоставлений. Если очередь сопоставлений пуста (этап (142)), работа завершается. Если очередь не пуста, на этапе (143) из очереди берется сопоставление с наибольшим приоритетом. Преобразование правой части соответствующего правила в набор логических утверждений. На этапе (144) система делает попытку добавить сформированный набор в мешок утверждений. В случае неудачи сопоставление объявляется неверным и осуществляется переход к шагу (142). В случае успеха производится поиск новых сопоставлений на этапе (142). Если найдены новые сопоставления, они добавляются в очередь и выполняется переход к этапу (142).
[00131] Этапы (141) и (145) выполняются с помощью специального механизма поиска сопоставлений. Этот механизм на этапе (141) умеет находить все сопоставления для правил интерпретации без объектных условий. Он также постоянно следит за содержимым мешка утверждений. Каждый раз, когда этап (144) выполнен успешно, и новые утверждения попали в мешок, механизм учитывает их и при необходимости генерирует новые сопоставления (уже с объектными условиями). Эти новые сопоставления могут генерироваться как сопоставления для новых правил интерпретации и идентификации, так и сопоставления для правил, для которых до этого уже генерировались другие сопоставления. Так происходит в тех случаях, когда некоторому объектному условию того или иного правила удовлетворяет более одного информационного объекта. В этом случае каждый объект рассматривается в рамках отдельного сопоставления. На этапе (145) ищется не только соответствие для правил интерпретации, но также соответствия для правил идентификации.
[00132] Фиг. 12 схематически иллюстрирует процесс извлечения информации. Реализация механизма поиска сопоставлений достаточно сложна. Например, в механизм встроен интерпретатор байт-кода скомпилированных правил, система специальных индексов над семантико-синтаксическими деревьями, модуль отслеживания изменений в мешке утверждений и некоторые другие механизмы. Подробное описание этого механизма выходит за рамки данного описания изобретения.
[00133] Важно также объяснить способ сортировки очереди сопоставлений на шаге (145). В некоторых случаях разработчики могут влиять на порядок срабатывания правил, то есть задать частичный порядок на множестве всех правил. Про любые два правила есть возможность сказать, что одно из них приоритетнее другого. Это означает, что при прочих равных, когда оба срабатывания возможны, срабатывание одного из правил должно происходить раньше срабатывания другого. Для удобства поддержана также возможность упорядочивать группы правил. Если задано, что группа правил А приоритетнее группы правил В, то это означает, что каждое правило группы А приоритетнее каждого правила группы В. Отношение частичного порядка транзитивно. При компиляции системы правил проверяется, что частичный порядок введен корректно. Если обнаруживаются циклы, компиляция считается неудачной и пользователь видит сообщение об ошибке. Порядок сопоставлений в очереди всегда согласован с отношением частичного порядка, заданным на системе правил.
[00134] Такой подход существенно отличается от последовательного применения всех правил, т.к. частичный порядок, заданный на правилах, влияет лишь на выбор между очередными срабатываниями, но не блокирует повторное применение одних и тех же правил.
[00135] Очевидно, что приведенный алгоритм не рассматривает альтернативы. Если группа утверждений, полученная при сопоставлении, вошла в противоречие с текущим состоянием мешка утверждений, сопоставление просто отбрасывается. Использование такого "жадного" принципа оказалось возможным в первую очередь за счет того, что, парсер уже снял лексическую многозначность, поэтому почти не приходится строить гипотезы об узле. Исключение составляют неизвестные парсеру слова, но и для них удается применять специальные приемы, укладывающиеся в «жадную» модель.
[00136] На Фиг. 13 показан пример вычислительного средства (1300) для реализации описанных в настоящем документе методов и систем в соответствии с одним из вариантов осуществления настоящего изобретения. Пример вычислительного средства представляет компьютерную платформу, включающую локальное, удаленное, распределенное или основанное на веб вычислительное устройство, содержащее по меньшей мере один процессор (1302), соединенный с запоминающим устройством (1304). Процессор (1302) может представлять один или более процессоров (например, микропроцессоров), а память (1304) может представлять собой устройства оперативной памяти (RAM), представляющие собой основное запоминающее устройство вычислительного средства, а также любые дополнительные уровни памяти, например, кэш-память, энергонезависимые или резервные запоминающие устройства (например, программируемые запоминающие устройства или флэш-накопители), постоянные запоминающие устройства, и т.д. Кроме того, можно считать, что память (1304) включает запоминающее устройство, физически расположенное в другой части вычислительного средства, например, любую кэш-память в процессоре (1302), а также любое запоминающее устройство, используемое в качестве виртуальной памяти, например, память, хранящуюся в запоминающем устройстве большой емкости (1310).
[00137] Как правило, вычислительное средство имеет ряд входов и выходов для обмена информацией с другими устройствами. В качестве интерфейса пользователя или оператора вычислительное средство может содержать одно или более устройств ввода (1306) (например, клавиатуру, мышь, устройство обработки изображений, сканер и микрофон), а также одно или более устройств вывода (1308) (например, панель жидкокристаллического дисплея (LCD) и устройство воспроизведения звука (динамик)). Для реализации настоящего изобретения вычислительное средство, как правило, содержит как минимум одно устройство с экраном.
[00138] Для дополнительного хранения вычислительное средство может также содержать одно или более устройство большой емкости (1310), например, накопитель на гибком диске или на другом съемном диске, накопитель на жестком диске, запоминающее устройство с прямым доступом (ЗУПД), оптический привод (например, привод оптических дисков (формата CD), привод с цифровым универсальным диском (формата DVD)) и/или стример и т.д. Кроме того, вычислительное средство (1300) может включать в себя интерфейс с одной или более сетями (1312) (например, локальной сетью (LAN), глобальной сетью (WAN), беспроводной сетью и/или Интернет и т.д.) для обеспечения обмена информацией с другими компьютерами, подключенными к сетям. Следует иметь в виду, что вычислительные средства обычно содержат необходимые аналоговые и/или цифровые интерфейсы между процессором (1302) и каждым из компонентов (1304), (1306), (1308), (1312), что хорошо известно специалистам в данной области.
[00139] Вычислительное средство работает под управлением операционной системы (1314), на нем выполняются различные компьютерные программные приложения, компоненты, программы, объекты, модули и т.д. для реализации описанных выше способов. Кроме того, различные приложения, компоненты, программы, объекты и т.д., которые совместно обозначены на Фиг. 13 как прикладное программное обеспечение (1316), также могут выполняться в одном или более процессорах в другом компьютере, подключенном к вычислительному средству (1300) через сеть (1312), например, в распределенной вычислительной среде, в результате чего обработка, необходимая для реализации функций компьютерной программы, может быть распределена по нескольким компьютерам в сети.
[00140] В целом, стандартные программы, выполняемые для реализации вариантов осуществления настоящего изобретения, могут быть реализованы как часть операционной системы или конкретного приложения, компонента, программы, объекта, модуля или последовательности команд, которые называются «программа для компьютера». Обычно программа для компьютера содержит один набор команд или несколько наборов команд, записанных в различные моменты времени в различных запоминающих устройствах и системах хранения в компьютере; после считывания и выполнения одним или несколькими процессорами в компьютере эти команды приводят к тому, что компьютер выполняет операции, необходимые для выполнения элементов, связанных с различными аспектами настоящего изобретения. Кроме того, несмотря на то, что это изобретение описано в контексте полностью работоспособных компьютеров и компьютерных систем, специалистам в данной области техники будет понятно, что различные варианты осуществления этого изобретения могут распространяться в виде программного продукта в различных формах, и что это изобретение в равной степени применимо для фактического распространения независимо от используемого конкретного типа машиночитаемых носителей. Примеры машиночитаемых носителей включают в том числе: записываемые носители, такие как энергонезависимые и энергозависимые устройства памяти, гибкие диски и другие съемные диски, накопители на жестких дисках, оптические диски (например, постоянные запоминающие устройства на компакт-диске (формата CD-ROM), накопители на цифровом универсальном диске (формата DVD), флэш-память и т.д.) и т.п.Другой тип распространения можно реализовать в виде загрузки из сети Интернет.
[00141] Аспекты настоящего раскрытия были описаны выше в отношении методов машинной интерпретации информации в текстовых документах. Тем не менее, было предусмотрено, что части данного описания могут быть альтернативно или дополнительно реализованы в виде отдельных программных продуктов или элементов других программных продуктов.
[00142] Все утверждения, принципы цитирования, аспекты и варианты реализации настоящего изобретения и соответствующие конкретные примеры охватывают как структурные и функциональные эквиваленты раскрытия изобретения.
[00143] Специалистам в данной области техники должно быть очевидно, что возможны различные модификации устройств, способов и программных продуктов настоящего изобретения без отхода от сущности или объема раскрытия изобретения. Таким образом, подразумевается, что настоящее изобретение включает модификации, которые включены в объем настоящего изобретения, а также их эквиваленты.