JP2000311166A - 自然言語入力データからプロセッサ使用可能データを生成する装置及びその方法 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】 入力された自然言語から文章及び語義情報を
抽出するマルチレベル処理を使用する解析を提供する。 【解決手段】 入力データのユニットカテゴリデータは
ユニットカテゴリデータのパターンと比較される。パタ
ーンが一致する場合、グループカテゴリデータが出力さ
れる。ユニットグループかつあるいはグループは、カス
ケードの連続ステージで一緒にグループ化される。カス
ケードの各ステージで一致するものがある場合、入力デ
ータユニットに対応する変数が出力される。少なくとも
いくつかの変数は、解析処理の様々なステージによって
識別される入力データユニット間の修飾関係を識別する
ために他の変数によってインデックス化される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般的には、自然
言語形態の入力データの構成ユニットからプロセッサ使
用可能形式データを生成する方法及び装置に関するもの
である。特に、本発明は、自然言語入力及びプロセッサ
使用可能データ出力間のインタフェースに関するもので
ある。

【０００２】

【従来の技術】コンピュータ及びデータ処理装置の進歩
につれて、これらの装置の操作はより複雑となり、ユー
ザによって要求される訓練を削減することによって直感
的に使用することができるより「ユーザフレンドリ」な
インタフェースを提供するためにユーザインタフェース
の簡略化が要求されている。

【０００３】ユーザがコンピュータあるいはデータ処理
装置の操作の実行を行いたい場合は、ユーザによって指
示が入力されなければならない。指示あるいはデータの
入力方法として自然言語を使用することは、例えば、E
Ｐ−Ａ−０１１８１８７に言及されている。

【０００４】単純なキーワード入力の代わりに自然言語
が使用される場合、判定対象の入力された自然言語指示
の意味が必要である。自然言語入力の意味の説明は、解
析（parer）の使用が必要である。解析は、大まかに２
つの種類に分けることができる。ある理論的アプローチ
に基づく全言語解析を使用する解析は、１９８０年代で
使用されており、これは、これらのアプローチが、より
詳細な言語解析の抽出の報酬を与えていたからである。
しかしながら、このようなシステムには欠点があり、特
に、このような解析を設計し維持することは難しく、ま
た、大量のコンピュータリソースを必要とする。全言語
解析をしようする解析の例は、ＧＢ−Ａ−２２６９９２
３及びEＰ−Ａ−０７３７９２８に開示されている。

【０００５】構築システムに関係する自然言語コミュニ
ティによって使用される別の解析の形態は、有限状態技
術及びその拡張を要する単純言語処理技術である。近年
では、有限状態技術は、自然言語処理コミュニティで自
身が再定義され、有限状態言語処理分野における近年リ
サーチでは、「有限状態遷移を有する決定性品詞のタグ
付け（Deterministic Part-of-Speech Tagging with Fi
nite-State Transducers）」（E. Roche及びY. Schabe
s；コンピュータ言語学 ２１（２）ページ２２７から
２５３）という名称の論文に記述されている。有限状態
技術の出現は、負荷の高い言語学アプローチの制限によ
って、また、かなり大量のフリーテキストを処理するた
めの要求によって、また、効果的な有限状態言語構成要
素をいかにして作成するかをより理解した結果によりも
たらされたものである。

【０００６】有限状態解析は、「有限状態カスケードを
介する部分解析（Partial Parsingvia Finite-State Ca
scades）」(S. Abney；EＳＳＬＬＩ９６年番耐性解析ワ
ークショップの手順)という名称の論文に記述されてい
る。有限状態解析技術が入力テキストの言語構造を効果
的に抽出し出力することができることがこの論文から認
められる。つまり、解析は統語構造を得ることができる
が、語義情報は得られない。

【０００７】

【発明が解決しようとしている課題】本発明の１態様
は、インデックス化変数とするプロセッサ使用可能形態
のデータを出力するために、入力された自然言語から文
章及び語義情報を抽出するマルチレベル処理を使用する
解析を提供する。

【０００８】

【課題を解決するための手段】本発明の目的の１つは、
自然言語入力とプロセッサ使用可能出力間のインタフェ
ースとして動作する方法及び装置を提供することであ
る。入力された自然言語は、複数の異なるカテゴリに分
類されたユニット形式である。各データユニットのカテ
ゴリは、ユニットカテゴリデータを生成するために判定
される。次に、ユニットカテゴリデータはパイプライン
あるいはカスケード化処理アレイに入力され、そこで、
入力データのユニットカテゴリデータはユニットカテゴ
リデータのパターンと比較される。パターンが一致する
場合、グループカテゴリデータが出力される。パイプラ
インあるいはカスケードの後続処理ステージは、前のい
ずれのステージでも一致していない入力されたユニット
カテゴリデータと、前のいずれのステージでも一致して
いない前のいずれかのステージで生成されるグループカ
テゴリデータを使用でき、ユニットかつ／あるいはグル
ープカテゴリデータの所定パターンをマッチングし、新
規グルーカテゴリデータを生成する。この方法では、ユ
ニットグループかつあるいはグループは、カスケードの
連続ステージで一緒にグループ化される。カスケードの
各ステージで一致するものがある場合、入力データユニ
ットに対応する変数が出力される。少なくともいくつか
の変数は、解析処理の様々なステージによって識別され
る入力データユニット間の修飾関係を識別するために他
の変数によってインデックス化される。

【０００９】

【発明の実施の形態】本発明の上記構成に従えば、イン
デックス化変数を出力することによって、一致するもの
がある場合、入力自然言語の統語構造を判定できるばか
りでなく、入力言語ユニット、即ち、単語間の修飾関係
の形態の語義情報を判定することができる。インデック
ス化は、他の自然言語ユニットを修飾する自然言語ユニ
ットを識別するためのポインタとして動作する。

【００１０】一実施形態では、マルチレベルパイプライ
ンあるいはカスケード化処理は有限状態装置を使用して
実行され、そこで、各ステージは、遷移セットである特
定文法規則を実行する有限状態装置を構成する。有限状
態装置は、自身を実行するために要求されるコンピュー
タリソースを削減するために決定性（deterministic）
であることが好ましい。しかしながら、非決定性有限状
態装置は、より大きな処理リソースを必要とするが、本
発明の範囲内で実行されても良い。

【００１１】変数の種類は、所定パターンと一致するセ
グメントに対応する入力データのセグメントの少なくと
もheadユニットを識別し、そこで、セグメントのheadユ
ニットは、そのセグメント内の他のユニットを修飾せ
ず、修飾句はheadあるいは他の修飾句のいずれか一方を
修飾する。変数内で使用可能な語義情報のレベルが増加
するにつれて、異なる種類の変数（修飾句）は、ユニッ
ト間の異なる修飾関係を識別するために使用できる。ま
た、修飾句によって修飾されるユニットを識別するため
に、少なくともいくつかの変数がインデックス化され
る。各変数の内容は、データユニットの内容に対応し、
修飾されるデータの構成ユニットの内容による変数をイ
ンデックス化することによってインデックス化が達成さ
れる。

【００１２】変数のインデックス化は、自然言語入力に
おける多義性（ambiguity）が生じない変数が生成され
るときの処理ステージで発生する。多義性が生じる場
合、自然言語文法規則は、その多義性を吸収するように
記述され、これは、処理中のより早い段階のステージで
生成される変数を使用してインデックス化されるインデ
ックス化変数を使用することになり、つまり、インデッ
クス化のない初期段階のステージで変数は生成され、以
降のステージでインデックス化される。

【００１３】実施形態では、入力データは、自然言語の
単語を構成する。これは、語彙ユニットと対応品詞デー
タを有する辞書を参照する辞書プロセッサによって処理
される。辞書プロセッサからの出力は、対応品詞データ
と一緒に入力単語と一致する語彙ユニットである。品詞
データは、ユニットカテゴリデータとして直接使用する
ことができる。しかしながら、辞書プロセッサはコンテ
キスト解析を行わないので、割り当てられる品詞にエラ
ーが生じる場合がある。それゆえ、本実施形態では、辞
書プロセッサの出力は、より正しく語彙ユニットへ品詞
を割り当てるために統計コンテキスト解析を実行する品
詞タグ付け（tagger）部へ入力される。

【００１４】本発明によって生成される出力データは、
システムの動作を制御するために使用することができ
る。入力データから生成される変数は、変数間の等価を
定義する関係に従って、入力データあるいは参照データ
のheadを示す変数から開始する参照データから生成され
る変数と比較される。次に、システムは、その比較結果
に従って制御される。このようなシステムには、例え
ば、入力データが自然言語クエリーを構成し、参照デー
タがデータベース内のデータに関連付けられた自然言語
キーを構成するデータベース検索システムが挙げられ
る。自然言語クエリーと自然言語キーが一致する場合、
このことがオペレータに提示され、データが検索され
る。

【００１５】概要 図１は本発明の実施形態の概要図であり、入力信号プロ
セッサセクション、出力信号生成器セクション、制御装
置を有する。

【００１６】入力信号プロセッサセクションは、入力バ
ッファ（１）に記憶されている自然言語の入力データを
受信する。この入力データは、プロセッサ使用可能形態
で入力信号プロセッサセクションの出力データを生成す
る有限状態解析（FＳＰ）モジュール（２）を通過す
る。有限状態解析モジュール（２）は、辞書データベー
ス（３）の語彙データをアクセスし、入力データに対す
る結果として生じる語彙データを作業メモリ（４）に入
力する。また、自然言語入力データの役割、例えば、品
詞、を示す役割データが辞書データベース（３）から生
成される。有限状態解析モジュール（２）は、作業メモ
リ（４）に記憶される統語データを生成し、作業メモリ
（４）に記憶される変数データを生成するために、メモ
リ（６）内の有限状態解析データに従って動作する。

【００１７】有限状態解析モジュール（２）は、メモリ
（６）に記憶される有限状態解析データを形成するため
に、文法規則記憶モジュール（５）から文法規則を読み
出す。つまり、有限状態解析モジュール（２）は、文法
規則記憶モジュール（５）内の文法規則に従って構成さ
れている。この構成による動作は、有限状態解析モジュ
ール（２）の構成の一部として実行される。

【００１８】有限状態解析モジュール（２）によって入
力信号プロセッサセクションから出力されるデータは、
語彙データと統語データの語彙ユニット間の修飾関係を
示す変数データである。このデータは、出力信号生成器
内のデータマッチングモジュール（７）で受信される。
データマッチングモジュール（７）は、受信データと入
力／出力信号データベース（８）に記憶されたデータと
の間でマッチング動作を実行し、これについての詳細は
後述する。マッチングに依存して、制御装置部内の制御
モジュール（９）への出力信号が生成される。

【００１９】ハードウェア 本実施形態では、入力信号プロセッサセクションは、適
切にプログラム化された多目的コンピュータを使用して
実行される。図２はこのようなハードウェアを示してい
る。

【００２０】表示装置（１０）は、自然言語の入力テキ
ストを表示するために提供される。コンピュータ内のプ
ロセッサ（１１）は、２つの機能、即ち、語彙処理及び
有限状態解析を実行する。語彙処理は、辞書（１２）を
参照して入力データに対し実行する。この処理は、作業
メモリとして動作するランダムアクセスメモリ（ＲＡ
Ｍ）（１５）に記憶される語彙データを生成する。プロ
セッサ１１によって動作する有限状態解析（FＳＰ）
は、ＲＡＭ（１５）に記憶される統語データ及び変数デ
ータを生成するために作業領域内の電子データを解析す
る。ハードディスク（１６）は、プロセッサ（１１）で
動作する有限状態解析を構成するために使用される有限
状態解析データを記憶するために提供される。また、ハ
ードディスク（１６）は、プロセッサ（１１）内で語彙
処理及び有限状態解析を実行するために文法規則データ
とプログラムを記憶する。また、キーボード（１４）
は、自然言語のデータの入力を可能にするために提供さ
れる。

【００２１】また、出力信号生成器は、図２のコンピュ
ータ内で実行することができ、また、本実施形態では、
プロセッサ（１１）は、制御信号を生成するためにデー
タベース内のデータと解析結果とをマッチングする追加
処理を実行する。

【００２２】機能説明 図３は本発明の実施形態の機能構成を示す図である。

【００２３】入力バッファ（２０）は、自然言語のテキ
ストを受信する。これは、辞書（２２）を参照する語彙
プロセッサ（２１）に対する入力である。語彙プロセッ
サ（２１）は、入力単語と辞書内の単語をマッチングす
る。本実施形態では、入力単語のすべての語形変化が辞
書に含まれており、これは、出力語彙データを取得する
ために辞書（２２）内で入力単語を参照するために必要
である。辞書（２２）からの出力は、単語自身と、単語
の役割、即ち、その単語の１つ以上の品詞である。語彙
データ（単語）は、語彙データ記憶部（３１）に記憶さ
れる。語彙プロセッサ（２１）から出力される各単語に
対する役割データは、１つ以上の品詞から構成される。
しかしながら、解析は、各単語の単一の品詞を必要と
し、品詞を処理する追加処理が必要である。また、語彙
プロセッサ（２１）は、単語のコンテキストを考慮しな
いで各単語に対する品詞を取得するので、単語に対して
選択された品詞には補正が必要であるかもしれない。こ
の補正は、タグ付け器（tagger）（２３）を使用して達
成される。タグ付け器（２３）は周知であり、単語のコ
ンテキストと関係する単語に対して最も可能性のある品
詞を判定することを試行するために、自然言語に対する
品詞に統計コンテキスト解析を実行する。例えば、タグ
付け器の詳細は、「品詞タグ付けにおける自動エラー検
出（AutomaticError Detection in Part of Speech Tag
ging）」（１９９７年、編集人がDaniel Jones and Har
old Somersで、ロングマン社から出版されている文献、
ページ２５６からページ２６８にあるD. Elworthyによ
る論文「言語精度における新方法（New methods in Lan
guage Precision）」）及び「実用的な品詞タグ付け
器」（１９９２年、文献、ページ１３３から１４０にあ
るD. Cuttingらによる「適用自然言語処理における第３
会議の手順（The Proceedings of the Third Conferenc
e on Applied Natural Language Processing）」）で知
ることができる。このようなタグ付け器の動作は周知で
あり、当業者に理解されるので、タグ付け器が、エイリ
アスデータ（２６）を参照するエイリアスプロセッサ
（２５）に出力される品詞タグを生成するために、タグ
付けモデルデータ（２４）を参照することは言うまでも
ない。エイリアスプロセッサ（２５）は、品詞のグルー
プに対する属性ラベルとして使用することができるエイ
リアスタグを生成するために提供される。換言すれば、
タグは、品詞の集合を参照して生成される。これは、記
述されるべき文法規則のセットをよりコンパクトにする
ことを可能にし、以下に詳細されるエイリアスタグを利
用する。つまり、エイリアスプロセッサ（２５）の出力
は、品詞タグとエイリアスタグである。次に、これら
は、ユニットカテゴリデータとして有限状態プロセッサ
の各ステージへ入力される。各ステージは、ステージへ
の入力とそのステージの文法規則間のマッチング処理を
実行するいくつかの有限状態装置を構成する。このユニ
ットカテゴリデータは、第１有限状態プロセッサステー
ジ（２７）に入力される。第１有限状態プロセッサステ
ージ（２７）は、入力ユニットカテゴリデータ（タグ）
のシーケンスと第１ステージに対する文法規則に従うユ
ニットカテゴリデータのパターンとをマッチングする。
一致するものがある場合、一致したユニットカテゴリデ
ータのシーケンスに対する出力グループカテゴリデータ
（タグ）が生成される。シーケンス内のユニットカテゴ
リデータ間のマッチングに対し、変数記憶（３０）に変
数が記憶される。変数は、語彙データ、即ち、単語を保
持する。変数記憶（３０）に記憶された変数の種類は、
入力自然言語テキスト内の単語間の修飾関係に依存す
る。変数は、FＳＰの各ステージに対し、かつそれらに
関係する各グループカテゴリに対し、局所的に記憶され
る。文法定義における規則が変数を提供する場合に限り
カスケードの連続ステージを変数は通過でき、詳細につ
いては後述する。一致しないユニットカテゴリデータ
は、一致したグループカテゴリデータと一緒に次のステ
ージに出力される。

【００２４】有限状態解析の第２及び第３ステージ（２
８及び２９）では、カテゴリデータが前のステージから
入力される。各ステージ内で各入力からの一致しないカ
テゴリデータがユニットかつ／あるいはグループカテゴ
リデータのシーケンスとマッチングされる。一致するも
のがある場合、カテゴリデータ内の一致に対する変数が
変数記憶（３０）に記憶される。一致しないカテゴリデ
ータは、新規に一致したグループカテゴリデータと一緒
に出力される。

【００２５】図３では、簡単化のために、３つのステー
ジだけで有限状態解析が示されている。本実施形態で
は、実際には、以下に詳述するように、より多くの数が
存在する。

【００２６】有限状態解析の最終ステージが一度実行さ
れると、一致しないカテゴリデータ（タグ）と新規に一
致したグループカテゴリデータが、統語構造として出力
装置（３２）によって出力される。また、変数は、語義
情報を提供するために出力装置（３３）によって出力で
きる。

【００２７】上述の説明から明らかなように、有限状態
解析は、コンピュータプログラム内の処理ステージのシ
ーケンスとして実行される。

【００２８】解析処理 解析処理は、入力からどのようにして出力が得られるか
を定義する規則集合を構成する文法定義を使用する。本
実施形態では、解析に対する入力は、単一の品詞に付随
する各単語のシーケンスである。この解析は、単語及び
品詞を使用し、入力の部分から句を収集するための試行
を行う。句は、品詞に類似するラベルによって与えられ
る。上述の品詞はユニットカテゴリと称し、句に対する
ラベルはグループカテゴリと称する。

【００２９】解析は、有限状態カスケードと呼ばれる方
法を使用する。文法定義は、ステージあるいはレベルと
呼ばれるセクションに分割され、そこで、１つ以上の規
則が実行される。各ステージ内では、入力中にカテゴリ
のパターンが存在する場合の解析を説明する１つ以上の
規則が存在し、これにより、特定カテゴリの語句を構成
することができる。語句のカテゴリは、規則の出力カテ
ゴリと呼ばれる。入力ユニットカテゴリ（品詞）は、第
１ステージへ入力され、そこで、規則が品詞の語彙部分
で完全に定義される。そのステージからの規則がすべて
試された場合、その結果はステージ２を通過する。ステ
ージ２の規則は、ステージ１で一致しない品詞の語彙部
分とステージからの出力とするカテゴリで定義される。
ステージの数は限定されず、同一カテゴリが１つ以上の
ステージでの出力カテゴリとして出現することができ
る。唯一の制限は、規則に対する入力が前のレベルとオ
リジナル入力とのみから引き出されることである。

【００３０】１つ以上の規則をステージに対し与えるこ
とができるので、１つ以上の規則が入力とマッチングで
きる。規則は、文法定義内に出現するシーケンス内で適
用される。各ステージに対する入力は、いくつかのカテ
ゴリ（語彙あるいは語句）を構成する。各ステージで
は、マッチング処理は、規則に対しカテゴリのシーケン
スとマッチングすることを試行する。与えられた規則が
１つ以上のカテゴリのシーケンスと一致する場合、より
長いカテゴリのシーケンスがマッチング対象とされる。
次に、入力カテゴリのシーケンスは、出力において句カ
テゴリに置換される。句カテゴリを生成するために入力
カテゴリのシーケンスが一度マッチングされ、入力カテ
ゴリの左側にまだ入力が存在する場合、残りの入力に対
し、次に一致した句カテゴリとのマッチングを続ける。
入力カテゴリの一番左側から開始する規則に対し一致す
るものがない場合、一番左側のカテゴリはスキップさ
れ、かつマッチング処理が次の入力カテゴリに対し再度
試行される。このマッチング処理が失敗する場合、その
入力カテゴリはスキップされて、そのマッチング処理が
繰り返される。このマッチング処理が規則に対する全入
力を通して実行された後、そのステージで実行されるべ
き別の規則が存在する場合、この次の規則が、上述した
マッチングを実行するために使用される。

【００３１】レベルに対する規則が一度実行されると、
そのレベルに対してスキップされた入力カテゴリと、そ
のレベルに対して生成された句あるいはカテゴリは、入
力として次のレベルを通過する。

【００３２】つまり、「tall man with a dog」（Adj
（形容詞） N（名詞） Prep（前置詞） Det（冠詞）
Adj（形容詞） N（名詞））のステージへの入力か
ら、ステージはDet? Adj* N形式の名詞グループを認識
し、「tall man」がNGへ集約され、マッチング処理は
「with」に対し継続する。前置詞から始まる名詞グルー
プに対する規則が存在しないので、単語「with」はスキ
ップされ、「a big dog」はＮＧに集約される。次のレ
ベルでは、その入力として「ＮＧ prep ＮＧ」カテゴ
リを受信する。この例では、単語は、１つの単語、即
ち、「with」の後にスキップされる必要があると判定さ
れる。しかしながら、これは、マッチング対象がなく、
かつ単語がスキップされる必要があると識別される前に
いくつかの単語を取得することができる。例えば、入力
「tall man the red with a big dog」に対し、単語「r
ed」に続く名詞が存在しないのでＮＧ規則が完了できな
いと判定される前に、「the red」は、Det?、Adjに対し
てマッチングされる。次に、単語「the」はスキップさ
れ、マッチング処理は単語「red」から再度開始でき
る。もう一度、マッチングが失敗すると、単語「red」
はスキップされる。これに続く、マッチングは失敗する
ので、単語「with」は上述の例のようにスキップされ
る。

【００３３】このマッチング方法は、左方探索最長マッ
チング方法と称される。

【００３４】上述したように、一致するものが存在する
場合に出力するグループ（句）カテゴリと、規則もま
た、変数として記憶されるべき入力の一部分を与える。
後述するように、変数は、入力の単語からあるいは前の
レベルで設定された変数の一方から設定される。変数
は、処理ステージに対し局所的に単語のリストを記憶す
る。変数は、次のステージの規則によってアクセスだけ
がなされる。

【００３５】文法定義文法は、カテゴリに基づいて定義
される。本実施形態では、ユニットカテゴリは品詞、例
えば、名詞、動詞等を構成する。また、これらは、品詞
を使用するあるいは使用しない特定単語に対し使用する
ことができる。

【００３６】本実施形態では、語彙は、以下の表１に示
されるＢＮＣタグセットを使用する入力テキストに対す
る品詞を生成する。

【表１】言語部分に対するタグ タグ カテゴリ AJO 形容詞 例 good, old AJC 比較形容詞 例 better, older AJS 最上級形容詞 例 best, oldest ATO 冠詞 例 the, a, an, no AVO 副詞 例 often, well, longer, furthest AVP 接尾副詞 例 up, off, out AVQ wh-副詞 例 when, how, why CJC 等位接続詞 例 and or not CJS 副序数接続詞 例 although, when CJT "the day that follows Christmas"のような関係詞
節を導入する場合の副序数接続詞 CRD 基数詞 例 one, 3, fifty-five DPS 所有冠詞形態 例 your, their, his DTO ＤTQでない一般冠詞 例 this both in "this is m
y house" and "this is mine" DTQ wh-冠詞 例 which, what, whose EXO 実存there, 単語"there" appearing in the const
ructions "there is..." "there are..." ITJ 感嘆詞あるいは他の独立詞 例 oh, yes, mhm NNO 普通名詞、自然数 例 aircraft, data, committe
e NN1 単一普通名詞 例 pencil, goose, time, revelat
ion NN2 複数普通名詞 例 pencils, geese, times, revel
ations NPO 固有名詞 例 London, Michael, Mars, IBM ORD 序数 例 first, sixth, 77th, next, last PNI 不定代名詞 例 none, everything PNP 人称代名詞 例 I, you, them, ours PNQ wh-代名詞 例 who, whoever, whom PNX 再帰代名詞 例 myself, yourself, itself, ours
elves POS 所有あるいは属格マーカ 's or ' PRF 前置詞 of PRP 例 about, at, in, on behalf of, with以外の前
置詞 TOO 不定詞マーカ to UNC 例えば、他国言語、印刷符号、式等の英語語彙の構
成要素として適切に分類されない非分類構成要素 VBB 動詞の現在時制形態 is以外のbe, あるいは 'm, 'r
e, be (仮定法の動詞あるいは命令法の動詞), ai (ain'
tとする)である's am, VBD be動詞の過去時制形態 was, were VBG be動詞の-ing形態, being VBl be動詞の不定形態, be VBN be動詞の過去分詞形態 been VBZ be動詞の-s形態 's VDB do動詞の定形形態 do VDO do動詞の過去時制形態 did VDG do動詞の-ing形態 doing VDI do動詞のの不定形態 do VDN do動詞の過去分詞形態 done VDZ do動詞の-s形態 does VHB have動詞の定形形態 have, 've VHD have動詞の過去時制形態 had, 'd VHG have動詞の-ing形態 having VHI have動詞の不定形態 have VHN have動詞の過去分詞形態 had VHZ have動詞の-s形態 has, 's VMO 法助動詞 例 can, could, will, 'll, 'd, wo (w
on'tとする) VVB 語彙動詞の定形形態 例 forget, send, live, re
turn VVD 語彙動詞の過去時制形態 例 forgot, sent, live
d, returned VVG 語彙動詞の-ing形態 例 forgetting, sending, l
iving, returning VVI 語彙動詞の不定形態 例 forget, send, live, re
turn VVN 語彙動詞の過去分詞形態 例 forgotten, sent, l
ived, returned VVZ 語彙動詞の-s形態 例 forgets, sends, lives, r
eturns XXO 否定不変化詞 not あるいは n't 句読点に対して使用されるタグ タグ カテゴリ PUL 左括弧 (即ち. ( あるいは [) PUN 任意の分割マーク (即ち ! ; : ? ...) PUQ 注釈マーク (即ち ' ' " ") PUR 右括弧 (即ち ) あるいは ]) CMA カンマ また、ＢＮＣタグセットは、２つの可能な解析間で不明
確な状態にあるタグを含んでいる。これらは、以下の表
２に示される。

【表２】２つの可能な解析間で不明な状態で使用される
タグ タグ カテゴリ AJO-AVO 形容詞あるいは副詞 AJO-NN1 形容詞あるいは単一共通名詞 AJO-VVD 形容詞あるいは過去時制動詞 AJO-VVG 形容詞あるいは動詞の-ing形態 AJO-VVN 形容詞あるいは過去分詞 AVP-PRP 副詞不変化詞あるいは前置詞 AVQ-CJS wh-副詞あるいは副序数接続詞 CJS-PRP 副序数接続詞あるいは前置詞 CJT-DTO 接続詞あるいは冠詞とするthat CRD-PN1 数詞あるいは代名詞とするone NN1-NPO 単一共通名詞あるいは固有名詞 NN1-VVB 単一狭つ名詞あるいは基本動詞形態 NN1-VVG 単一共通名詞あるいは動詞の-ing形態 NN2-VVZ 複数名詞あるいは語彙動詞の-s形態 VVD-VVN 過去時制動詞あるいは過去分詞 次に、語彙プロセッサによって生成されるタグは、タグ
付けを実行するためにタグ付け器へ入力される。タグ付
けは、２つのタグを有する出力を参照し、例えば、本願
の発明者による「品詞タグ付けにおける自動エラー検出
（Automatic Error Detection in Part of Speech Tagg
ing）」（編集人がEds. David Jones and Harold Somer
sで、ロングマン社から出版されている文献ページ２５
６からページ２６８にあるD Elworthyの言語処理の新方
法）という名称の論文に開示されているようなエラー検
出処理を使用し、これらを単一タグに置換する。また、
いくつかのタグは、識別、例えば、ＮＮ１及びＮＮ２を
ＮＮへ置換すること、を解析が行う必要がないより単純
なタグに置換する。タグ付けから得られるタグは、以下
の表３に示される。

【表３】タグ付けから得られるタグ タグ カテゴリ AJ-AV 形容詞あるいは副詞 AJ-DT 形容詞あるいは冠詞 AJ-NN 形容詞あるいは名詞 AJ-NN-VV 形容詞、名詞あるいは動詞 AJ-PR 形容詞あるいは前置詞 AJ-VV 形容詞あるいは語彙動詞 AV-CJ 副詞あるいは接続詞 AV-NN 副詞あるいは名詞 AV-PP 副詞あるいは前置詞 AV-VV 副詞あるいは動詞 NN 名詞 NN-VV 名詞あるいは動詞 上述したタグに加えて、アンカータグが解析対象のテキ
ストの最初と最後に付けるために使用することができ
る。表１から表３で与えられるタグは、ユニットカテゴ
リを構成する。

【００３７】各文法規則、例えば、処理ステージの各出
力はグループカテゴリである。グループカテゴリに対す
るタグは、以下の表４に示される。

【表４】グループカテゴリに対するタグ タグ カテゴリ NP 名詞句 PP 前置詞句 DP 冠詞句 adjP 副詞句 NG 名詞グループ name 固有名 prepp 合成及び接頭詞句 vmod 変則動詞句 pmod プレファイナル修飾句 top トップレベル合成 sink モップアップ合成 つまり、文法規則は、タグのシーケンスの識別と新規タ
グをもたらす。いくつかのタグは、統語意味を有する一
方で、コンピュータで便利になるように提供される。

【００３８】いくつかの文法規則に対し、いくつかのカ
テゴリは、同一の方法で処理される。つまり、文法規則
全体に対するすべてのカテゴリを把握しなければならな
いことを避けるために、エイリアスタグは、その文法規
則全体に対し使用される。エイリアスは、以下の表５に
よって与えられる文法規則で使用される。

【００３９】

【表５】

【００４０】つまり、文法規則においてタグＡTＯ及び
ＤTＯが使用できる場合、タグ「deｔ」は、例えば、自
身で使用される。

【００４１】文法規則は、処理ステージの各ステージに
対する１つ以上の文法規則として記述される。各規則
は、左辺には自身の出力グループカテゴリとそれに続く
（）で囲まれたその規則によって設定される変数リスト
を有している。右辺は、カテゴリのパターンである。同
じ出力グループカテゴリは１つ以上の規則で発生し得
る。

【００４２】右辺のカテゴリのパターンは、認識される
カテゴリのシーケンスを判定する。このカテゴリのパタ
ーンは正規表現として記述され、パターン要素から構成
される。最も簡単なパターン要素は、カテゴリ、即ち、
ユニットカテゴリあるいはグループカテゴリである。パ
ターン要素は、演算子？、*、あるいは＋によって変形
できる。

【００４３】？ 任意の要素であり、マッチング対象に
ふさわしい入力が１回あるいは全くない状態で発生する
ことができる要素であることを意味する * ゼロあるいは複数回発生することができる要素であ
ることを意味する ＋ ゼロあるいは複数回発生することができる要素であ
ることを意味する 垂直バー、例えば、p│qで結合される２つの要素は、p
あるいはqのどちらか一方を意味する。全パターン要素
は、それらがどのようにしてグループ化されるかを単に
示すために使用されるかっこ内に含ませることができ
る。以下は全て有効パターン要素である。

【００４４】 Det 冠詞 Det? 任意の冠詞 Det* ０ OR それ以上の冠詞 Det+ １つ OR それ以上の冠詞 Det│NN 冠詞 OR 名詞 (Det*│NN)? 任意、０ OR それ以上の冠詞 OR
名詞 ((Det│NN)+ │NG) １つ OR それ以上の冠詞 OR 名詞
群 (合成語を含む)、OR 単名詞グループいずれか一つ ＯＲ演算子は、順に並んだ単なる２つの要素より高い優
先度を有する。これは、例えば、「a│bc」という表現
が「cが続くa、あるいはcが続くb」として扱うことを意
味する。「a単独、あるいはcが続くb」としたい場合、
「a│（bc）」と記述しなければならない。

【００４５】文法規則において、１つ以上のパターンを
規則に対し与えることができる。例えば、 NG (head,mod)=Det? Adj* NN* NN│GER となる。等価表現としては、 NG (head,mod)=Det? Adj* NN* NN NG (head,mod)=Det? Adj* NN* GER となる。

【００４６】上記の規則は、要点を示すために示したも
のであり、実際に使用される規則ではない。

【００４７】変数における要素のマッチング結果を参照
すると、これらの要素には、コロンと変数名が後続す
る。これをアクションと称する。変数は、単にパターン
要素、即ち、ユニットカテゴリに適用するだけである。
全規則を適用する場合、即ち、入力の要素シーケンスと
規則内の要素シーケンス間で一致するものがある場合、
変数が、自身の元の順で対応要素と一致するすべての単
語に設定される。例えば、 NG (head,mod) = Det? Adj:mod* NN:head これは、名詞グループＮＧを０以上の修飾形容詞と最終
名詞に続く任意の冠詞として定義している。副詞単語は
変数「mod」に変換され、名詞単語は変数「head」に変
換される。変数の種類は、修飾関係の種類を示してい
る。「head」変数は、単語が句内で別の単語に修飾して
いないことを示している。変数「mod」は、先頭単語の
修飾句であることを示している。

【００４８】同一の変数は、文法規則の１つ以上の要素
で使用でき、例えば、 NG (head,mod) = Det? Adj:mod* NN:head これは、変数「mod」に記憶されるいくつかの単語が得
られる。この例では、句は、「the deep blue water」
である。この句の変数は、head=water, mod=deep,blue
である。

【００４９】単語は、必要であれば、１つ以上の変数に
記憶できる。例えば、 NG (head,mod,adjMod,nounMod)=Det? Adj:(mod,adjMod)
* NN:(mod,nounMod)* NN:head つまり、形容詞単語は、２つの変数modとadjmodに記憶
され、最終名詞単語の前の各名詞単語もまた、２つの変
数modとnounmodに記憶される。

【００５０】図３の機能図で示されるように、変数は、
処理ステージの各ステージで記憶される。メイン変数が
後続ステージで使用されるためには、メイン変数はその
ステージに渡されなければならない。これは、new-vari
able=old-variableという表記を使用して達成でき、こ
の表記のnew-variableは注目の規則（処理ステージ）に
属し、old-variableはその前の処理ステージに属する。
このやり方でコピーされない変数は破棄される。一例と
しては、 PP (head,pmod,prep)=Prep:prep NG:(pmod=mod,head=he
ad) である。

【００５１】この規則は、前置詞句（ＰＰ）が名詞グル
ープが後続する前置詞からなることを示している。前置
詞単語は変数「prep」に記憶され、名詞グループの変数
「mod」値は変数「pmod」にコピーされ、名詞グループ
の「head」変数は前置詞句の「head」変数にコピーされ
る。名詞グループがそれ以外の変数を持つ場合、それら
は破棄される。

【００５２】パターンに対するアクションにおいて符号
^を使用することによって、以前の処理ステージから現
在の処理ステージへすべての変数をコピーすることが可
能である。このようなアクションは、現在の規則におけ
る変数と同じ変数名を有するより下位のレベルでのすべ
ての変数をコピーする。つまり、この上記の規則は、以
下のように記述できる。

【００５３】 PP (head,pmod,prep)=Prep:prep NG:(pmod=mod,^) 加えて、いくつかの種類の変数、例えば、head, mod, p
mod, prep, adjMod, nounModが存在し、これらの使用さ
れる変数はインデックス化される。インデックス化変数
は、インデックス値が単語である配列のように機能す
る。この規則では、インデックス化変数は、変数リスト
内で変数名に続いて[]で示される。この規則の本体で
は、var[index]=another-var形式の表現で使用できる。
インデックスは、より下位の処理ステージの句の変数名
である。それらが必要とされる例としては、名詞グルー
プといくつかの前置詞句修飾語を組み合わせて名詞句を
生成する以下の規則が挙げられる。

【００５４】 NP (head,mod,pheads,pmods[],preps[])= NG:^ PP:(pheads=head,pmods[head]=pmod,preps[head]=prep)
* この規則は、いくつかの構成で示される。まず、名詞句
（ＮＰ）の「head」値と「mod」値は、^を使用する名詞
グループ（ＮＧ）からコピーされる。次に、「pmods」
と「prep」がインデックス変数として示される。これら
の両方は、前置詞句のhead値でインデックス化される。
これらは、ＰＰの変数として「pmods」と「prep」から
自身の値を得る。そして、ＰＰの「head」が「pheads」
にコピーされる。

【００５５】上述の例では、インデックス化は、前の処
理ステージでの句に対して生成される変数を使用して実
行される。一方で、現在の処理ステージで生成される変
数を使用して変数をインデックス化することもできる。
var{index}=another-varは、変数varが現在の処理レベ
ルで生成される変数「index」によってインデックス化
されることを意味し、この変数は、前の処理ステージの
「another-var」と等しくなる。この特別なインデック
ス化の形態は、文法規則がどのようにして記述されるか
においてより柔軟性を持たせることができる。例えば、
前置詞句は、その前置詞でインデックス化でき、以下の
ように記述できる。

【００５６】PP (head[],pmod[],prep)=Prep:prep NG(pmod{prep}=mod,head{prep}=head) また、以下の"=another-var"を持たないvar{index}の記
述によって、自身の変数上において同様の変数として振
る舞い、即ち、単語は「index」上でインデックス化さ
れたvarに割り当てられる。

【００５７】以下の表６は、文法規則において使用でき
る様々な種類の変数を簡単に説明するものである。

【００５８】

【表６】

【００５９】 FＳＰのステージに対する文法 本実施形態のFＳＰのステージに対する文法規則は以下に与えられる。 ステージ１ このステージは決定詞句と他の「小」頭句とをマッチングする。 name(head,mod[]) = (NPO:head)+ (num:mod{head})? dp(det) = det (num:det)? dp(det) = ATO DTO dp(det) = PNI PRF dp(det) = DPS dp(det) = num:det (PRF det)? adjp(head,mod[]) = (advj:mod{head})*advj:head((cma│conj│(cma conj)) (advj:mod{head})*advj:head)+ adjp(head,mod[]) = (adv:mod{head})+ adj:head prepp(prep) = prep:prep (conj prep:prep)+ ステージ２ このステージは単純に名詞グループとマッチングする。 ng(head,vmod[], mod[],prep[]) = dp:(mod{head}=det)?(NN?VV:mod{head})? ((adv:mod{head}│adjN:mod{head}│ name:(mod{head}=head, mod=mod)│ adjp:(mod{head}=head,mod=mod)) (POS│ppart:mod{head})?)* (adjN:head│name:^│adjp:(head=head,mod=mod)│NN-VV:head) ng(head,vmod[],mod[],prep[] = PNI:head ステージ３ このステージは名詞グループと密接範囲「of」句とをマッチングする。 ng(head,vmod[],mod[], prep[]) = (ng:(mod{head}=head,mod=mod) PRF)+ ng:^ ステージ４ このステージは結合名詞グループとマッチングする。 ng(head,vmod[],mod[],prep[]) = ng:^ ((cma │ conj │ (cma conj)) dp:(mod{head}=det)? ng:^)+ ステージ５ このステージは後続修飾動詞句の第１ラウンドと名詞グループの補集合とをマ ッチングする。 vmod(head,mod[],prep[]) = adv? ger:head ng:(mod{head}=head,mod= mod)+ adv? vmod(head,mod[],prep[]) = rel VVZ:head ng:(mod{head}=head,mod=mod) vmod(head,mod[],prep[]) = VBG adv? ppart:head ng:(mod{head}=head,mod=mod) ステージ６ このステージは名詞グループから構成される前置詞句をマッチングする。 pp(mod[], prep) = ((adv? prep* prep:prep)│PRF:prep) ng: (mod{prep}=head, mod=mod)trail? ステージ７ このステージは動詞型後続修飾句をマッチングする。 vmod(head,mod[],prep[]) = adv? ger:head(prep │ prepp)? adv? vmod(head,mod[],prep[]) = adv? ger:head pp:(prep{head}=prep,mod=mod)+ adv? vmod(head,mod[],prep[]) = (rel VHZ VBN)? adv? ppart:head (prep │ prepp)? pp: (prep{head}=prep,mod= mod) vmod(head,mod[],prep[]) = rel VVZ:head pp: (prep{head}=prep,mod-mod) vmod(head,mod[],prep[]) = VBG adv? ppart:head (prep │ prepp)? pp:(prep{head}=prep,mod= mod) vmod(head,mod[],prep[]) = VV AVO? ステージ８ このステージは「pollen covered stamen」のような組み合わせを識別するた めに試行する名詞グループを形成する。 ng(head,vmod[],mod[],prep[]) = ng:(mod{head}=head,mod=mod,prep=prep) ppart:mod{head} ng:^ ng(head,vmod[],mod[],prep[]) = ng:^ vmod: (vmod{head}=head,mod=mod,prep=prep)+ ((cma│conj│(cma conj))vmod:(vmod{head}=head, mod=mod, prep=prep))* ステージ９ このステージは「a fire breathing dragon」のような修飾名詞グループをマ ッチングする。 ng(head,vmod[],mod[],prep[] = ng:^ (vmod:(vmod{head}=head,mod=mod,prep=prep) │pp:(prep{head}=prep,mod=mod))+ ng(head,vmod[],mod[],prep[] = ng:^ ng:(mod{head}=head,mod=mod,prep=prep) (vmod:(vmod{head)=head, mod=mod, prep=prep)│pp:(prep {head}=prep,mod=mod))+ ステージ１０ このステージは単語の左をモップアップするために種々の句をマッチングする 。 sink = trail sink = PRP PNP? ステージ１１ このステージはカンマあるいは接続詞によって導かれるある修飾句を検索する 。そうすることによって、前置詞句は最終前修飾詞（pｍｏd）に確実に限定でき る。 pmod(mod[],prep) = (cma│conj│(cma conj))sink? pp:^ pp:(mod{prep}=prep, mod=mod)? ステージ１２ このステージはトップレベル結合詞とマッチングする。 top(head,vmod[],mod[],prep[]) = ng:^sink? (((cma│conj│(dma conj))(ng:^│vmod: (vmod{head}=head, mod=mod, prep=prep)))│pmod: (prep{head}=prep, mod=mod)│pp: (prep{head}=prep,mod=mod))* sink? top(head,vmod[],mod[],prep[]) = ng:^ rel DTQ ng:^ be VVG:mod{head} top(head,vmod[],mod[],prep[]) = ng:^ sink ng:^ top(head,vmod[],mod[],prep[]) = ng:^ pp:(prep{head}=prep, mod=mod) ng:^ top(head,vmod[],mod[],prep[]) = pp:^ (pp:^ │ vmod: (vmod{head}=head, mod=mod,prep=prep) │pmod:(prep{head}=prep, mod=mod))* ステージ１３ このステージは任意の開始及び任意のトークン（アンカー）及び句読点をモッ プアップする最終ステージである。 top(head,vmod[],mod[],prep[] = anchor top:^ PUN? anchor インデックス化変数の記憶方法 解析処理は入力自然言語の左から右へと処理を行うの
で、インデックス化変数は処理を進めることによって単
純に生成し記憶することができない。例えば、インデッ
クスとして使用されるhead単語は最終句まで現れず、こ
れに対し、head単語によってインデックス化されるべき
変数は、そのhead単語の前で判定される。即ち、そのhe
ad単語の左にある。つまり、変数のインデックス化は、
すべての変数が句に対し判定されるまで実行することが
できない。

【００６０】インデックス化変数を生成するために実行
できる解析には２つの方法がある。 第１方法 図４は解析が２回実行される第１方法を示している。第
１解析処理（変数nが１に設定される場合）では、非イ
ンデックス化変数が生成される。次に、インデックス化
変数は、第２解析処理（変数nが２に設定される場合）
において非インデックス化変数を使用して生成される。

【００６１】図４はＪステージを有するFＳＰに対する
上記の処理を示すフロー図である。ステップＳ１で、デ
ータが自然言語、即ち、句あるいは文で入力される。次
に、ステップＳ２で、語彙プロセッサを使用して語彙ユ
ニットが識別され、ステップＳ３で、品詞が判定され
る。これらは、ステップＳ４でユニットカテゴリを形成
するために使用され、解析処理に入力される。ステップ
Ｓ５で、解析処理の初期化を行い、ここで、カウンタn
に１が設定される。nは解析が行われた実行回数を計数
するために使用される。ステップＳ６で、処理内で第１
ステージを選択するために処理ステージカウンタｊに１
が設定される。

【００６２】ステップＳ７で、ステージｊでマッチング
を実行することによって有限状態マッチング処理が開始
する。n=１である場合には生成された非インデックス化
変数が記憶され、あるいはn=２である場合には生成され
たインデックス化変数が記憶される。また、ステップＳ
７で、ステージｊで一致しない任意のカテゴリとステー
ジｊで一致した任意のカテゴリが出力される。ステップ
Ｓ８で、有限状態解析のすべてのステージが実行された
かどうか、つまり、ｊ=Ｊであるかどうかが判定され、
ここで、Ｊは有限状態解析のステージ数である。すべて
のステージが実行されていない場合、ステップＳ９で、
ステージカウンタｊはインクリメントされ、ステップＳ
１０で、次のステージに対する入力は前のステージの出
力となり、処理はステップＳ７に戻る。つまり、ステッ
プＳ７からステップＳ１０は、有限状態解析が実現され
るまですべてのステージに対しＪ回実行されるループを
構成する。

【００６３】これらのステージのすべてが一度実行され
ると、即ち、ｊ=Ｊとなると、ステップＳ１１で、n=２
であるかどうか、即ち、解析処理が２回実行されたかど
うかが判定される。２回実行されていない場合、ステッ
プＳ１２で、解析処理カウンタnはインクリメントさ
れ、処理はステップＳ６に戻る。つまり、本実施形態で
は、非インデックス化変数、例えば、headを生成するた
めに第１解析処理が実行され、解析処理はインデックス
化変数を生成するために繰り返される。

【００６４】ステップＳ１３で、２回の解析処理が一度
完了すると、ステージＪで生成された変数がこれらの値
と統語データと一緒に出力される。

【００６５】ステップＳ７で実行される処理の詳細は、
図５を参照してより詳細に説明される。この図におい
て、iはカテゴリi=１、…、Ｉのシーケンスを示し、カ
テゴリは語彙、即ち、ユニットカテゴリであり、かつそ
れらに関連する単語を有し、あるいは句、即ち、グルー
プカテゴリであり、かつそれらに関連する変数セットを
有る。カテゴリのシーケンスは、有限状態解析のステー
ジに対する入力を構成する。その出力は、語彙及び句カ
テゴリの新規シーケンスを構成する。有限状態解析のス
テージ内では、F、例えば、ｆ=１、…、Fによってイン
デックス化されたF有限状態装置が存在する。

【００６６】ステップＳ２０で、シーケンスカウンタi
は１に設定される。ステップＳ２１で、有限状態装置カ
ウンタｆは１に設定される。ステップＳ２４で、有限状
態装置ｆは、入力単語あるいは句iでの開始を試行す
る。有限状態装置が失敗する場合、即ち、カテゴリiで
開始する一致するものがない場合、ステップＳ２２で、
有限状態装置はインクリメントされ、ステップＳ２４
で、最終有限状態装置に到達したかどうかが判定され
る。到達していない場合、処理はステップＳ２２に戻
り、再度試行する。最終有限状態装置が試行される場
合、ステップＳ２５で、シーケンス内のカテゴリは、入
力が変わらずに出力される。ステップＳ２６で、シーケ
ンスカウンタiはインクリメントされ、ステップＳ２７
で、カテゴリのシーケンスの最後に到達したかどうかが
判定される。到達した場合、ステップＳ２８で、ステー
ジｊに対する処理が終了する。ステップＳ２７で、シー
ケンス内のカテゴリの最後が処理されていない場合、処
理はステップＳ２１に戻る。

【００６７】ステップＳ２２で、一致するものがあり、
有限状態装置が遷移を実行可能である場合、ステップＳ
２９で、有限状態装置ｆに対する句カテゴリが出力さ
れ、n=１である場合、即ち、第１有限状態解析を行った
場合、非インデックス化変数が記憶され、n=２である場
合、即ち、第２有限状態解析を行った場合、インデック
ス化変数が記憶される。次に、ステップＳ３０で、有限
状態装置ｆによって最後の１つが認識された後に、シー
ケンスカウンタiが入力要素に対しインクリメントある
いは更新される。次に、処理はステップＳ２７へ進み、
そこで、シーケンスカウンタiがシーケンスの最後に到
達したかどうか、即ち、i=Ｉであるかどうかが判定され
る。最後に到達していない場合、処理はステップＳ３１
に戻り、最後に到達している場合、ステップＳ２８で、
ステージｊに対する処理が終了したかどうかが判定され
る。

【００６８】図５のステップＳ２２で実行されるステッ
プの詳細は図６を参照して詳細に説明される。有限状態
装置ｆは状態及び遷移から成り立っている。有限状態装
置が現在使用する状態は追跡され、変数が句カテゴリと
一緒に出力される。有限状態装置ｆは、カテゴリiのシ
ーケンスを介してインクリメントすることによって動作
する。ｓは現在の状態である。

【００６９】ステップＳ４０で、ｓが開始状態に設定さ
れる。ステップＳ４１で、要素iのカテゴリを使用して
状態ｓから新規状態ｔへの遷移があるかどうかが判定さ
れる。遷移がある場合、ステップＳ４２で、n=１である
場合、遷移に対する非インデックス化変数が記憶され
る。n=２である場合、遷移に対するインデックス化変数
が記憶される。ステップＳ４３で、状態ｓは新規状態ｔ
へ設定され、シーケンスカウンタiはインクリメントさ
れる。ステップＳ４４で、カテゴリのシーケンスの最後
に到達したかどうかが判定される。到達していない場
合、処理はステップＳ４１に戻る。カテゴリのシーケン
スの最後に到達した場合、処理はステップＳ４５に進
み、そこで、ｓが最終状態であるかどうかが判定され
る。最終状態でない場合、処理は、ステップＳ４７で失
敗したことが示される。最終状態である場合、ステップ
Ｓ４６で、処理が成功したことが判定される。

【００７０】ステップＳ４１で、要素iのカテゴリを使
用する現在の状態ｓから新規状態ｔへの遷移がない場
合、処理はステップＳ４５に進み、そこで、ｓが最終状
態であるかどうかが判定される。最終状態である場合、
処理はステップＳ４６で成功したことが示され、最終状
態でない場合、処理は、ステップＳ４７で失敗したこと
が示される。 第２方法 図７は、２回解析処理に代えて、単一解析処理中に、変
数をその変数のインデックス化に対する命令と一緒に記
憶する第２方法のフロー図である。

【００７１】ステップＳ５０で、データが自然言語で入
力され、ステップＳ５１で、語彙プロセッサは語彙ユニ
ットを識別する。ステップＳ５２で、品詞が判定され、
ステップＳ５３でユニットカテゴリが形成される。ステ
ップＳ５４で、処理ステージカウンタｊが１に設定さ
れ、第１ステージを開始する。ステップＳ５５で、ステ
ージｊでマッチングを実行することによって有限状態解
析処理が実現され、そのステージに対する変数を生成す
る命令を記憶する。また、ステージｊで一致しないカテ
ゴリと、ステージｊで一致したカテゴリとが出力され
る。ステップＳ５６で、有限状態解析の最終ステージに
到達したかどうか、即ち、ｊ=Ｊであるかどうかが判定
され、ここで、Ｊは有限状態解析におけるステージ数で
ある。最終ステージに到達していない場合、ステップＳ
５７で、ステージカウンタｊがインクリメントされ、ス
テップＳ５８で、注目ステージｊへの入力が、前のステ
ージｊ−１から出力されるカテゴリとして選択される。
次に、処理はステップＳ５５に戻る。つまり、ステップ
Ｓ５５からステップＳ５８は、有限状態解析における各
ステージに対しＪ回繰り返される。

【００７２】有限状態解析の最終ステージが実行された
場合、即ち、ステップＳ５６でｊ=Ｊである場合、ステ
ップＳ５７で、ステージｊで生成された変数を生成する
命令が統語データと一緒に出力される。

【００７３】図７のステップＳ５５で実行されるステッ
プの詳細は図８を参照して説明される。これは、１から
Ｉのカテゴリiのシーケンスの入力を有する単一有限状
態解析の動作を説明する。カテゴリは語彙、即ち、ユニ
ットカテゴリであり、それらに関連する単語を有し、あ
るいは句、即ち、グループカテゴリであり、それらに関
連する変数のセットを有する。出力は語彙及び句カテゴ
リの新規シーケンスである。このステージ内で、ｆ=
１、…、Fでインデックス化されるF有限状態装置が存在
する。

【００７４】ステップＳ６０で、カテゴリシーケンスイ
ンデックスiが１に設定され、ステップＳ６１で、有限
状態装置カウンタｊが１に設定される。ステップＳ６２
で、有限状態装置装置ｆが、入力単語あるいは句iでの
開始が試行される。試行が失敗した場合、即ち、一致す
るものがない場合、ステップＳ６３で、有限状態装置カ
ウンタｆがインクリメントされる。次に、ステップＳ６
４で、すべての有限状態装置が試行されたかどうか、即
ち、ｆ=Fであるかどうかが判定される。試行されていな
い場合、処理はステップＳ６２に戻る。すべての有限状
態装置が試行された場合、ステップＳ６５で、シーケン
スカウンタiによってインデックス化されたカテゴリが
入力と変わらずに出力される。次に、ステップＳ６６
で、シーケンスカウンタがインクリメントされ、ステッ
プＳ６７で、すべてのカテゴリのシーケンスが処理され
たかどうか、即ち、i=Ｉであるかどうかが判定される。
処理された場合、ステップＳ６８で、処理ステージｊが
完了していることが判定される。すべてのカテゴリのシ
ーケンスが処理されていない場合、処理はステップＳ６
１に戻る。

【００７５】ステップＳ６２で、有限状態装置ｆが入力
単語あるいは句iでの開始が試行され、成功、即ち、一
致するものがある場合、ステップＳ６９で、有限状態装
置ｆに対する句カテゴリが変数を設定する命令と一緒に
出力される。次に、ステップＳ７０で、最後の１つが有
限状態装置ｆで認識された後、シーケンスカウンタiで
入力カテゴリが更新される。次に、ステップＳ６７で、
シーケンス内の最終カテゴリに到達したかどうか、即
ち、i=Ｉであるかどうかが判定される。到達した場合、
ステップＳ６８で、ステージｊに対する処理が終了した
ことが判定判定される。到達していない場合、処理はス
テップＳ６１に戻る。

【００７６】図８のステップＳ６２で実行されるステッ
プの詳細は、図９を参照して詳細に説明される。

【００７７】有限状態装置は状態及び遷移を確立する。
有限状態装置の状態は、変数及び句カテゴリを設定する
出力命令と一緒に追跡される。ｓは現在の状態である。

【００７８】ステップＳ８０で、現在の状態ｓが開始状
態に設定される。ステップＳ８１で、要素iのカテゴリ
を使用して状態ｓから新規状態ｔへの遷移があるかどう
かが判定される。遷移がある場合、ステップＳ８２で、
遷移（どのような場合の）に対する命令が記憶される。
次に、ステップＳ８３で、有限状態が新規状態ｔに更新
され、シーケンスカウンタがインクリメントされる。ス
テップＳ８４で、シーケンスの最後に到達したかどう
か、即ち、i=Ｉであるかどうかが判定され、到達してい
ない場合、処理はステップＳ８１に戻る。シーケンスの
最後に到達した場合、処理はステップＳ８５に進み、そ
こで、有限状態装置が最終状態であるかどうかが判定さ
れる。最終状態である場合、処理はステップＳ８６で成
功を示しして終了し、最終状態でない場合、処理はステ
ップＳ８７で失敗を示して処理を終了する。

【００７９】ステップＳ８１で、要素iのカテゴリを使
用して状態ｓから新規状態ｔへの遷移がない場合、処理
はステップＳ８５に進み、そこで、有限状態装置の最終
状態に到達したかどうかが判定される。最終状態に到達
した場合、処理はステップＳ８６で成功を示して終了
し、最終状態に到達していない場合、処理はステップＳ
８７で失敗を示して終了する。

【００８０】変数のインデックス化に対する命令が実行
できる方法はいくつか存在する。図１０Ａ及び図１０Ｂ
は一つの方法である。

【００８１】図１０Ａでは、非インデックス変数に対す
る命令が、まず、ステップＳ１４０で実行され、続い
て、ステップＳ１４１でインデックス化変数に対する命
令が実行される。

【００８２】図１０Ｂでは、ステップＳ１６０で、第１
命令が選択され、ステップＳ１６１で、これが判定され
る。ステップＳ１６２でこの命令が実行されたかどう
か、即ち、変数のインデックス化が使用可能であるかど
うかが判定される。実行されない場合、ステップＳ１６
４で、次の命令が選択され、処理はステップＳ１６１に
戻る。命令が実行できる場合、ステップＳ１６３で、そ
の命令が実行され、ステップＳ１６５で、実行対象の命
令が存在するかどうかが判定される。存在する場合、処
理はステップＳ１６４に戻る。存在しない場合、処理は
ステップＳ１６６で終了する。 解析された句の例 解析によって生成された変数及び統語データの例を、英
語の「big red car inthe street」の入力句例を参照し
て説明する。 統語構造 テキスト big red car in street 品詞に 対するタグ AJO AJO NN1 PRP NN1 タグ付け後の タグ AJO AJO NN RPR NN エイリアスタグ advj advj adjN prep adjN ステップ1 [big red]_adjP (ステージ1) ステップ2 (ステージ2) [[big red]_adjP car]_NG [street]_NG ステップ3 (ステージ6) [in [street]_NG]_PP ステップ4 (ステージ12) [[[big red]_adjP car]_NG [in [str
eet]_NG]_PP]_TOP 上記及び図１１はグループカテゴリを形成するためにユ
ニットカテゴリと一緒にグループ化される統語構造を示
している。解析のステージ１で実行されるステップ１の
ように、形容詞「big」及び「red」は形容詞句（adjp）
を構成するものとして識別される。解析のステージ２で
実行される解析処理のステップ２では、形容詞句「big
red」及び名詞「car」が名詞グループとして認識され、
つまり、グループカテゴリ名詞グループ（NG）が生成さ
れる。また、単語「street」が名詞グループ（ＮＧ）と
して認識される。解析のステージ６で実行されるステッ
プ３では、前置詞「in」及び名詞グループ「street」が
前置詞句（PP）を形成するものとして認識される。解析
のステージ１２で実行される処理のステップ４では、名
詞グループ（NG）及び前置詞句（PP）がトップレベルグ
ループ（TOP）を形成するものとして認識される。

【００８３】以下に与えられる表７及び表８は、本例に
対し各ステージで変数がどのように判定されたかを示し
ている。

【００８４】

【表７】

【００８５】

【表８】

【００８６】形容詞句「big red」における第１ステー
ジでは、変数head=red及びmod[red]=bigが識別される。

【００８７】名詞グループにおける第２ステージでは、
変数head=car、mod[car]=red及びmod[red]=bigが識別さ
れ、名詞グループ「street」では、変数head=streetが
識別される。

【００８８】第３処理ステップでは、head=car、mod[ca
r]=red及びmod[red]=bigとして識別される名詞グループ
「big red car」に対する変数が記憶され、前置詞句「i
n street」に対し、変数prep=in及びmod[in]=streetが
生成される。

【００８９】完全な句に対する最終処理ステップでは、
変数head=car、mod[car]=red、mod[red]=big、prep[ca
r]=及びmod[in]=streetが記憶される。

【００９０】各ステージでかつ局所的な各句カテゴリに
対し変数は局所的に記憶される。処理における以後のス
テージによって使用されない変数は無視される、例え
ば、上述のステップ１のhead=red及びステップ３のhead
=streetが無視される（変数は以後のステージで使用さ
れないがその値がコピーされる、即ち、変数mod[car]に
値redが与えられ、変数mod[in]に値streetが与えられ
る）。

【００９１】上記で与えられた変数は、入力データの修
飾関係を定義することを明確に示すことができる。変数
が、他の単語を修飾する単語を定義するばかりでなく、
修飾関係の種類も定義することを示すことができる。修
飾関係の種類は、変数の種類によって定義される。これ
は図１２で示される。この図は、変数が句内の単語間の
関係を定義していることを示している。 多義性を有する解析句の例 インデックス化変数の使用は、意味に多義性がある入力
句を扱うことができる。例えば、句「man with a dog h
olding a big stick」では、manがbig stickをholding
するのか、あるいはdogがa big stickをholdingするの
かのように多義性が存在する。

【００９２】入力データ内で２つに分割される句のイン
デックス化が必要な変数が、変数を生成する処理ステー
ジの初期にはインデックス化されず、その処理ステージ
内で後でインデックス化されるように文法規則を記述す
ることによって、多義性は解析処理で扱うことができ
る。

【００９３】上述の入力データを解析するために使用で
きる文法規則は以下のように与えられる。 ステップ１ PP (prep,pmod)=Prep:prep Det? NN:pmod ステップ２ RC (rhead, obj, mod[])=Ger:rhead Det? adj:mod{obj}NN:obj ステップ３ NP (head,prep[], pmod[], mod[], obj[], X)= Det? NN:head PP:(prep{head}=prep, pmod[prep]=pmod, X=pmod RC: (mod{head}=rhead, obj[rhead]=obj, mod=mod, mod{ X}=rhead) これらの文法規則は、統語構造を得る解析を実行するた
めに使用することができる。 man with a dog holding a big stick タグ NN prep det NN Ger det advj NN ステップ１ [with a dog]_PP ステップ２ [holding a big stick]_RC ステップ３ [man[with a dog]_PP [holding a big
stick]_RC]_NP また、この統語構造は図１３に示される。ステップ１
で、前置詞句「with a dog」は、まず、グループカテゴ
リPPを生成するために識別される。次のステップでは、
関係詞節「holding a big stick」が、グループカテゴ
リRCを生成するために識別される。最終ステップでは、
前置詞句PP、関係詞節及び入力データの名詞が名詞句と
して識別され、そして、グループカテゴリＮＰが生成さ
れる。

【００９４】以下の表９は、この例に対し変数がどのよ
うに判定されるかを示している。

【００９５】

【表９】

【００９６】この例では、第１ステップで、変数prep及
びpmodがインデックス化されないことが知ることができ
る。最終ステージでのこれらの変数のインデックス化
は、ステップ１で生成された変数を参照することによっ
て実行される。変数pmod[prep]=pmodは、変数内容dogと
インデックス化されたwithとのインデックス化を実行す
るために使用される。また、変数_X=pmodを使用するこ
とによって、単語dogは、PP句で使用される変数からRC
句で使用される変数へと渡すことができ、そうすること
によって、変数mod{ X}=rheadは変数mod[dog]=holding
を得る。

【００９７】図１４は表９の変数によって与えられる修
飾関係を示している。これで示されるように、manがbig
stickをholdingしているかあるいはdogがbig stickをh
oldingしているかどうかに関して多義性が存在する。こ
れは、関係するhead「holding」で２つの修飾関係を与
えるhead「man」から２つの修飾関係を提供することに
よって扱える。

【００９８】複雑な修飾関係を識別するためにインデッ
クス化変数を使用して、複雑な語義情報を取得できるこ
とがこれから示される。 マッチング処理 コンピュータ使用可能形式のデータから構成される解析
処理の出力は、装置を制御する出力信号を生成するため
に使用することができる。図１で示したように、出力信
号生成器は入力／出力信号に基づくデータベースを含ん
でいる。このデータベースは、入力データとマッチング
されるデータのパターンから構成されるデータセットを
含み、マッチング対象がある場合に出力信号が得られ
る。例えば、データベースは句「switch on the ligh
t」を含むことができ、制御モジュールは、lightユニッ
トを構成できる。つまり、入力句がその意味と一致する
場合、生成される出力信号は所望の結果を生じさせる。
つまり、データベースは解析が必要である参照データを
記憶するか、あるいは変数の形式で解析されたデータを
記憶するかのどちらか一方が可能であり、そうすること
によって、このデータベースは解析から出力されるデー
タと直接比較することができる。

【００９９】マッチング技術の原理は、本願の出願人が
先に出願している出願番号ＧＢ ９８２１９６９．４の
出願に説明されており、この内容は、参照することによ
って本明細書に組み込まれる。

【０１００】上述した解析方法では、ユニットデータは
単語で構成するが、この技術は単語の使用だけに限定さ
れない。語彙ユニット、あるいはより耐性のあるマッチ
ング技術を提供する単語あるいは単語のグループの意味
表現のような任意の種類のユニットが使用できる。

【０１０１】図１５はマッチングプロセスのフロー図で
ある。ステップＳ１８０で、入力データ（クエリー）の
head及び参照データ（キー）が選択され、マッチングに
対するスコアが０に設定される。ステップＳ１８１で、
クエリー内のheadがキー内のheadと一致するかどうかが
判定される。一致しない場合、ステップＳ１８２で、ク
エリー内のheadがキー内の修飾句と一致するかどうかが
判定される。一致しない場合、マッチング処理は失敗
し、ステップＳ１８３で出力と一緒にマッチング処理を
終了する。累積スコアを、クエリーに対して可能な最高
スコアによって除した値がスコアとして出力される。ス
テップＳ１８１で、headが一致すると判定される場合、
ステップＳ１８５で、スコアは１増加し、ステップＳ１
８６で、クエリー内の修飾句とキー内の修飾句が一致す
るかどうかが判定される。ステップＳ１８２で、クエリ
ー内のheadとキー内のheadが同じであると判定される場
合、ステップＳ１８４で、スコアは０．３増加し、処理
はステップＳ１８６に進む。ステップＳ１８６で、修飾
句が一致すると判定される場合、ステップＳ１８７で、
スコアは０．５増加し、処理はステップＳ１８６へ戻
る。ステップＳ１８６で修飾句が一致しないと判定され
る場合、ステップＳ１８８で、クエリー内の変数vmodと
キーが一致するかどうかが判定される。一致する場合、
ステップＳ１８９で、スコアは０．５増加し、処理はス
テップＳ１８６に戻る。ステップＳ１８８で、vmod変数
が一致しないと判定される場合、ステップＳ１９０で、
キー内のvmodと一致しないクエリー内の変数vmodが存在
するかどうかが判定される。存在する場合、ステップＳ
１８９で、クエリー内のvmodはスキップされ、ステップ
Ｓ２００で、スコアは１増加する。次に、処理はステッ
プＳ１８６に戻る。ステップＳ１９０で、スキップ対象
のvmod変数が存在しない場合、ステップＳ１９２で、キ
ー内のprep変数と一致しないクエリー内のprep変数が存
在するかどうかが判定され、存在する場合、ステップＳ
１９３で、prep変数はスキップされ、ステップＳ２００
で、スコアは１増加する。次に、処理はステップＳ１８
６に戻る。ステップＳ１９２で、スキップできるクエリ
ー内のprep変数が存在しないと判定される場合、ステッ
プＳ１９４で、クエリー内のvmod変数に対応しないキー
内のvmod変数が存在するかどうかが判定される。存在す
る場合、ステップＳ１９５で、vmod変数がキー内でスキ
ップされ、ステップＳ２００で、スコアは１増加する。
次に、処理はステップＳ１８６に戻る。ステップＳ１９
４で、スキップ対象のキー内のvmod変数が存在しないと
判定される場合、スキップ１９６で、スキップできるキ
ー内のprep変数が存在するかどうかが判定される。存在
する場合、ステップＳ１９７で、キー内のprep変数がス
キップされ、ステップＳ２００で、スコアが１増加す
る。次に、処理はステップＳ１８６に戻る。ステップＳ
１９６で、キー内でスキップできるprep変数が存在しな
いと判定される場合、ステップＳ１９８で、キー内のmo
d変数に対応しないクエリー内のmod変数が存在するかど
うかが判定される。存在する場合、ステップＳ１９９
で、スコアは増加せず、処理はステップＳ１８１に戻
る。残っている修飾句が存在しない場合、ステップＳ１
９８で、新規headを検出するためにステップＳ１８１に
戻る。

【０１０２】マッチング処理の例を説明する。

【０１０３】クエリーが「big green car」である場
合、変数は、head=car、mod[car]=green及びmod[green]
=bigである。キーが「big car」である場合、変数は、h
ead=car、及びmod[car]==bigである。

【０１０４】ステップＳ１８１の結果は、head「car」
が一致し、そして、スコアが１増加することである。ク
エリー内の「green」と一致するキー内の修飾句は存在
せず、そして、ステップＳ１９８で、スコアは増加しな
い。次に、ステップＳ１８６で、修飾句「big」がキー
内のクエリー内で一致することが判定され、そして、ス
コアは０．５増加する。つまり、総スコアは１．５とな
る。次に、これは、一致に対して可能な総スコア２．５
によって除算されて６０％の一致度を与える。

【０１０５】つまり、スコアに対する閾値は、その閾値
が満足された場合に、出力におけるマッチングが十分な
結果となるように設定できる。

【０１０６】マッチング処理は多くのアプリケーション
に対し使用できる。アプリケーションに対する１つの特
定の使用例は、データベースからのデータ検索、例え
ば、自然言語キャプションを有する画像のデータ検索が
ある。キャプションはキーを形成し、入力データはクエ
リーを構成する。結果として得られる出力データは、ク
エリーとキーに対し最高の１または複数の一致結果を構
成する。つまり、図１の制御モジュールは最高一致結果
を表示するためにコンピュータ上にディスプレイを構成
し、例えば、画像に対し、ディスプレイはいくつかの表
示画像を構成できる。 有限状態装置とする文法規則の実行 図１６は有限状態解析を設計する方法のフロー図であ
る。文法は展開され、そして、文法規則は展開により正
規表現として記述される。ステップＳ１１１で、例え
ば、キーボードあるいは記憶されたファイルから正規表
現が入力される。次に、ステップＳ１１２で、正規表現
は非決定性有限状態装置へコンパイルされる。これは、
以下により詳細に説明される。非決定性有限状態装置は
使用できるが、以下のパターン例で問題が発生し得る。 X:a* X:b (X:c)* 非決定性有限状態装置は、様々な方法でＸ群の解析を得
ることができる。つまり、「ＸＸＸ」は、初めの２つの
Ｘ群がaに３番目がbに置換される、あるいはa内の１
つ、b内の１つ、c内の１つ、などと解析することができ
る。

【０１０７】上記の問題を回避するため、また、より高
速に実行するために、ステップＳ１１３で、有限状態装
置が決定される。これは、以下により詳細に説明され
る。

【０１０８】ステップＳ１１４で、変数設定、即ち、遷
移が判定され、ステップＳ１１５で、決定性有限状態装
置及び変数設定が出力される。これは、図１のメモリ
（６）に記憶された有限状態解析データを構成する。 非決定性有限状態装置に対する正規表現のコンパイル 図１７Ａから図１７Ｅはコンパイルアルゴリズムを示し
ている。これらの図において、１００は開始状態を含む
状態を構成し、１１０は最終状態である。遷移は、状態
間で発生する。この遷移は入力からの要素マッチングp
を使うことができ、全パターンがマッチングされる場合
に生じるアクションaをもたらす。アクションはケース
∈が状態間の空遷移を示す場合には省略されても良い。
これらの遷移は、入力を使うことなくあるいはアクショ
ンを生じることなく続けることができる。

【０１０９】用語「N(r)」は正規表現ｒをコンパイルし
て得られる有限状態装置を示すために使用される。新規
の遷移及び状態が追加て、ボックスは、前のコンパイル
ステージの結果を示すために開始及び終了状態と一緒に
使用される。基本要素（カテゴリ、単語あるいはカテゴ
リ／単語）に対し、アクションaを有するpは任意であ
り、有限状態装置遷移N(p:a)は図１７Ａに示される。

【０１１０】ｒが要素である場合、N(r?)に対する有限
状態装置は図１７Ｂを使用してN(r)から構築される。

【０１１１】ｒが要素である場合、有限状態装置N(r*)
は図１７Ｃを使用してN(r)から構築される。

【０１１２】ｒが要素である場合、有限状態装置N(r+)
は図１７Ｄを使用してN(r)から構築される。

【０１１３】ｒ及びｓが要素である場合、N(r|s)は図１
７Ｅを使用してN(r)及びN(s)から構築される。

【０１１４】ｒが要素である場合、(r)に対する有限状
態装置はｒに対するものと同じである。

【０１１５】全パターンに対する有限状態装置を作成す
るために、状態が別々にコンパイルされ、次に、各要素
の終了状態は、次のものの開始状態にするために作成さ
れる。

【０１１６】この処理結果は、非決定性有限状態装置で
ある。 有限状態装置の決定 非決定性有限状態から決定性装置への変換する実行する
アルゴリズムは、Aho、Sethi、Ullmanによる「コンパイ
ラ：原理、技術及びツール」（１９８６年、Addison-We
sley社のページ１１８−１１９）という名称の文献に開
示されるアルゴリズムを多少変形したものである。

【０１１７】このアルゴリズムは、以下に示すように簡
潔である。

【０１１８】まず、補助関数、∈−触集合が必要であ
る。 ∈−触集合 Input: a set of states T Output: a set of states U containing all states in T and all states wh ich can be reached from them by empty transitions method: push all states in T onto stack initialise U to T while stack is not empty { pop a state t from stack for each ∈-transition from t to a stage u { if u is not in U then { add u to U push u onto stack } } } メイン決定性アルゴリズムに対し、全FＳＭに対するす
べての開始状態を有するものと仮定し、これをs_oと呼
ぶ。変数状態は、状態セットのリストを保持するために
使用され、処理されたことを示すためにマーキングされ
ても良い。各状態セットは、決定されたFＳＭで単一の
状態を形成する。与えられた状態Sのセットに対し、入
力符号がpである場合に、TはＳのいくつかの状態から得
られる状態セットであることを示すペア＜ｐ，Ｔ＞を取
得できる。tran(S,p)が入力p上の状態sから得られる状
態セットのセットであるように、配列tranを生成するこ
とが目的である。注意したいのは、この（即ち、オリジ
ナル装置の状態セット）各々の数は新規装置の単一の状
態になることである。 initialise states to ∈-closure(S_o)(unmarked) while there is an unmarked state-set S in states{ mark S for each ＜ｐ，Ｔ＞ which can be reach from S{ let the set of states U =∈-closure(T) if U is not in states then { add U to states (unmarked) } tran(S,p):=U } } 結果として得られる装置では、新規状態を構成するオリ
ジナル状態のいずれかが最終としてマーキングされる場
合、新規状態は最終としてマーキングされ、開始状態に
対しても同様である。

【０１１９】次に、更なる決定性処理が、変数に関連す
る多義性を解決するために適用される。このアルゴリズ
ムは、E. Roche and Y. Schabesによる「有効性状態遷
移を有する品詞の決定性タグ付け」（１９９５年、コン
ピュータ言語の２１（２）のページ２２７−２５３）と
いう名称の論文から直接得られる以下の詳細で与えられ
る。

【０１２０】アルゴリズムは、以下に詳細に示される。

【０１２１】以下のように、w₁、w₂∈Σ*に対し、w₁∧w
₂は、w₁及びw₂の最長共通接頭辞を示している。

【０１２２】使用される有限状態遷移は、それらが決定
的になるという属性を有し、つまり、同じ機能を示す後
続の遷移が存在する。T=（Σ,Q,i,F,E）がそのような有
限状態遷移である場合、以下のように定義される後続遷
移T'=（Σ,Q',i',F',◎,*,ρ）はTと等しく、尚、◎
は、テンソル積を示す。

【０１２３】Tは、Q'⊂２^Q×Σ*である。事実、遷移の
決定論化は、累乗セット構成を含むという意味ではFＳ
Ａの決定論化に関連する。この差分は、システムに起こ
り得るオリジナル遷移の状態のセットはエミションが遅
延された単語と同様に記憶されていということである。
例えば、状態｛（q₁,w₁）,（q₁,w₁）｝は、この状態が
オリジナル遷移のq₁,q₂を導く経路に対応することを示
し、また、w₁のエミッシン（resp.w₂）がq₁に対し遅延
されていることを示している。

【０１２４】i'=｛（i,∈）｝である。初期状態で遅延
されたエミッションは存在しない。エミッション関数
は、以下のように定義され、 これは、与えられた符号に対し、可能なエミッションの
セットが、現在の状態でのエミッションと遅延されたエ
ミッションを連結することによって取得されることを意
味する。遷移が決定的であることを要求されるので、実
際のエミッションは、このセットの最長共通接頭辞とな
る。状態遷移関数は、以下のように定義され、 与えられたu、ｖ∈dΣ*に対して、u.ｖは、u及びvの連
結を示し、wがu.w=ｖである場合、u^-1v=wであり、その
ようなwが存在しない場合、u^-1v=0である。

【０１２５】F'=｛S∈Q'｜∃(q,u)∈S and q∈F｝ S∈F'である場合、p(S)=u s.ｔ. ∃q ∈ F, (q,u)
∈S. 以下に与えられる決定性アルゴリズムは上述の後続遷移
を計算する。

【０１２６】 アルゴリズムを適用する方法は、図１４の有限状態遷移
例を参照して説明する。

【０１２７】決定性アルゴリズムは、図１８の有限状態
遷移に適用され、図１９の後続遷移を構築する。そのア
ルゴリズムのライン１は第１状態を構築し、ペア｛(0,
∈)｝を有する第１状態を例示する。q及びnはそれぞ
れ、現在の状態及びこれまでに構築されている状態の数
を示している。ライン５で、可能な入力符号wを取得
し、この例では、aだけが可能である。ライン６のw'は
出力符号であり、 つまり、w'=δ(0,a,1)∧δ(0,a,2)=b∧c=∈である。ラ
イン８は、以下のように計算される。 つまり、S'={1,δ(0,a,1)}∪{2,δ(0,a,2)}={（1,b）,
(2,c)}である。ライン９上の状態を確認するｒがないの
で、遷移ラベル化a／w=a／∈が指示する新規状態eが生
成され、nがインクリメントされる。ライン１５では、
プログラムは状態１の遷移に対する構造に進む。ライン
１５で、プログラムは、状態２の遷移に対する構築に進
む。ライン５では、d及びeは可能な２つの符号である。
ライン６での第１符号hは、以下のようなw'になる。

【０１２８】 以降、ライン８の計算は、以下の式を導く。

【０１２９】 状態２のラベル化｛(2,∈)｝は追加され、状態２を示す
遷移ラベル化h／bhもまた追加される。入力符号∈に対
する遷移は、同様に計算される。 別実施形態及び変形例 本発明は、自然言語の入力データと処理使用可能形式で
出力されるデータ間のインタフェースとして動作する処
理装置を提供する。本発明は、あらゆる自然言語を適用
可能であり、自然言語のユニットは自然言語の単語に限
定されず、自然言語で構築でき、かつ異なるカテゴリへ
カテゴリ化することができる適切なユニット形式を構成
することができる。本発明の実施形態は、漢字及び仮名
で記述される日本語のような言語に適用されない単語の
言語を含む他の言語を処理するために構成されても良
い。

【０１３０】本実施形態の単語は、データユニットの情
報コンテンツとして使用されるが、単語の語幹を構成で
きる語彙ユニットを使用することができ、あるいはいく
つかの同義語を表す意味表現を使用することができる。
正確に単語をマッチングするよりも、入力句及び参照句
の意味のマッチングを可能にするので、特に、入力デー
タが参照データとマッチングされる場合に有効である。
例えば、入力「switch-on the light」と参照データ「t
urn-on the light」のマッチングを可能にすることが望
ましい。同じ意味表現を、用語「switch-on」と用語「t
urn-on」とから得ることができる。これは、同義語例を
含む語彙ユニットを生成する辞書を使用することによっ
て達成できる。つまり、データユニットは、ユニット識
別データを構成し、このユニット識別データは単語等の
データユニット、辞書ユニットあるいは意味表現、及び
品詞あるいはデータユニットの他のカテゴリ化形式等の
対応ユニットカテゴリデータを構成することができる。

【０１３１】本実施形態では、入力単語は単語のすべて
の語形変化を含む辞書とマッチングされる。一方、辞書
は、単語の語幹だけを含むことができ、語彙プロセッサ
は接頭辞及び接尾辞を取り除いて、語形変化を取り除く
ことができる。

【０１３２】本実施形態は決定性有限状態装置を構成し
て説明したが、本発明は非決定性有限状態装置を扱うこ
とも扱う。しかしながら、決定性有限状態装置の使用
は、計算効率の理由から好ましい。

【０１３３】本実施形態では、語彙プロセッサに加え
て、タグ付け器が使用される。しかしながら、このよう
なタグ付け器の使用は重要ではない。あらゆるユニット
カテゴリデータの生成方法が使用できる。例えば、語彙
プロセッサは、出力語彙ユニットに対する適切な品詞タ
グを決定するために、ある程度のコンテキスト処理を含
ませることができる。一方、ユニットカテゴリデータの
生成は、辞書から品詞を参照することと、語彙ユニット
に対し１つ以上の品詞が存在する場合の複合解析時に１
度に１つの品詞を使用することで構成できる。

【０１３４】有限状態解析の実施形態は標準的な多目的
コンピュータ上のソフトウェアで実行されることを示し
たが、本発明は特定の専用ハードウェアで実行すること
もできる。特に、有限状態装置は、有限状態装置の様々
なステージが論理的あるいは空間的に、一時的でなく連
続して実行される場合のロジックで実行することができ
る。

【０１３５】本発明の構成はカスケード化構成の有限状
態装置を利用する、これは、これらが効果的にかつコン
ピュータを使用して高速に実行することができるからで
ある。上記の実施上の限定は、必要とされるステージの
数を増加させて効率を下げることなく、かなり深くネス
ティングしている文を解析できないことによる。解析速
度を向上するためには、複雑な文法的構造の解析を成功
させるための解析能力とのトレードオフ必要がある。

【０１３６】本発明は上記の実施形態を参照して説明さ
れたが、本発明は上記実施形態に限定されず、本発明の
精神及び範囲内で変形が可能であることが当業者には明
らかであろう。

【図面の簡単な説明】

【図１】本発明の実施形態に従う処理装置の概要図であ
る。

【図２】コンピュータシステムとして実施される処理装
置の概要図である。

【図３】本発明の実施形態の処理システムの機能図であ
る。

【図４】本発明の第１方法の一般的なフロー図である。

【図５】図４のステップＳ７の詳細を示すフロー図であ
る。

【図６】図５のステップＳ２２の詳細を示すフロー図で
ある。

【図７】本発明の第２方法のフロー図である。

【図８】図７のステップＳ５５の詳細を示すフロー図で
ある。

【図９】図８のステップＳ６２の詳細を示すフロー図で
ある。

【図１０Ａ】図７の方法のインデックス化命令を実行す
る別の方法を示す図である。

【図１０Ｂ】図７の方法のインデックス化命令を実行す
る別の方法を示す図である。

【図１１】特定の自然言語入力の処理で実行される処理
ステップを示す図である。

【図１２】図１１の入力自然言語例の解析から生成され
る変数の概要図である。

【図１３】多義性を含む入力自然言語例の処理を示す図
である。

【図１４】図１３の入力自然言語に対して生成された変
数の概要図である。

【図１５】本発明の実施形態に従うクエリー及びキーに
対する変数データのマッチング処理のフロー図である。

【図１６】文法規則からの有限状態装置の形成において
実行されるステップのフロー図である。

【図１７Ａ】文法規則からの有限状態装置の構築におけ
るステージのコンパイルを示す図である。

【図１７Ｂ】文法規則からの有限状態装置の構築におけ
るステージのコンパイルを示す図である。

【図１７Ｃ】文法規則からの有限状態装置の構築におけ
るステージのコンパイルを示す図である。

【図１７Ｄ】文法規則からの有限状態装置の構築におけ
るステージのコンパイルを示す図である。

【図１７Ｅ】文法規則からの有限状態装置の構築におけ
るステージのコンパイルを示す図である。

【図１８】非決定性有限状態遷移図である。

【図１９】決定論化有限状態遷移図である。

Claims (36)

【特許請求の範囲】
1. 【請求項１】 複数の異なるカテゴリからなるユニット
   形式の自然言語の入力データからプロセッサ使用可能形
   式データを生成する処理装置であって、 ユニットデータ及び対応ユニットカテゴリデータからな
   るプロセッサ使用可能データユニットを生成するため
   に、入力データのユニットをそれぞれのカテゴリへカテ
   ゴリ化するデータユニット生成手段と、 カスケード化された複数のマッチング手段とを備え、該
   複数のマッチング手段の内の第１マッチング手段は、前
   記ユニットカテゴリデータとユニットカテゴリデータの
   少なくとも１つの所定パターンとをマッチングし、前記
   ユニットカテゴリデータの少なくとも１つの所定パター
   ンと一致した前記ユニットカテゴリデータに対するグル
   ープカテゴリデータを出力するために使用でき、前記カ
   スケード化された複数のマッチング手段の内の、前記第
   １マッチング手段以外のマッチング手段あるいはそれぞ
   れのマッチング手段は、前記ユニットかつ／あるいはグ
   ループカテゴリデータの少なくとも１つの所定パターン
   と前記ユニットかつ／あるいはグループカテゴリデータ
   とが一致したカテゴリデータの代わりに、前記カスケー
   ド化されたマッチング手段の少なくとも１つ前から一致
   しない前記ユニットカテゴリデータ及び前記グループカ
   テゴリデータを使用し、ユニットかつ／あるいはカテゴ
   リデータの前記少なくとも１つの所定パターンと一致し
   たユニットかつ／あるいはグループカテゴリデータに対
   し新規グループカテゴリデータを出力するために使用で
   き、 前記複数のマッチング手段の少なくとも１つは、一致し
   たユニットカテゴリデータに対応する前記ユニットデー
   タを複数の変数として出力するために使用され、前記変
   数の少なくとも１つはそれ以外の変数によってインデッ
   クス化されることを特徴とする処理装置。
2. 【請求項２】 前記複数のマッチング手段のそれぞれ
   は、前記自然言語に対する文法規則に従って構成された
   少なくとも１つの有限状態装置を構成することを特徴と
   する請求項１に記載の処理装置。
3. 【請求項３】 前記有限状態装置は、決定性があること
   を特徴とする請求項２に記載の処理装置。
4. 【請求項４】 前記有限状態装置は、該有限状態装置が
   ある状態から別の状態へ遷移する場合に前記変数を出力
   するように構成され、各遷移は、ユニットあるいは前記
   パターンのグループカテゴリデータを有する入力データ
   からのユニットあるいはグループカテゴリデータのマッ
   チングに対応することを特徴とする請求項２または請求
   項３に記載の処理装置。
5. 【請求項５】 前記複数のマッチング手段の少なくとも
   １つは、データユニットのセグメントのheadユニット及
   び修飾ユニットを定義する変数として前記ユニットデー
   タを出力するように適合され、前記インデックス化変数
   あるいは各インデックス化変数は修飾ユニットのユニッ
   トデータを定義することを特徴とする請求項１乃至請求
   項４のいずれか１項に記載の処理装置。
6. 【請求項６】 前記複数のマッチング手段の少なくとも
   １つは、修飾されるデータのユニットの前記ユニットデ
   ータを構成するインデックスを有する１つ以上の前記イ
   ンデックス化変数を出力するように適合されることを特
   徴とする請求項５に記載の処理装置。
7. 【請求項７】 前記複数のマッチング手段の少なくとも
   １つは、複数の異なる変数とする前記変数を出力するよ
   うに適合され、各変数は異なる統語修飾を定義すること
   を特徴とする請求項５または請求項６に記載の処理装
   置。
8. 【請求項８】 前記複数のマッチング手段の少なくとも
   １つは、前記マッチング手段から出力される変数によっ
   て前記インデックス化変数をインデックス化するために
   使用されることを特徴とする請求項１乃至請求項４のい
   ずれか１項に記載の処理装置。
9. 【請求項９】 前記複数のマッチング手段の少なくとも
   １つは、前記カスケード化された前のマッチング手段か
   ら出力される変数によってインデックス化変数をインデ
   ックス化するために使用可能であることを特徴とする請
   求項１乃至請求項８のいずれか１項に記載の処理装置。
10. 【請求項１０】 前記ユニットカテゴリデータは、品
    詞、単語及び語彙特徴を有するグループの１つを構成す
    ることを特徴とする請求項１乃至請求項９のいずれか１
    項に記載の処理装置。
11. 【請求項１１】 前記グループカテゴリデータは、前記
    入力データの統語構造を定義することを特徴とする請求
    項１乃至請求項１０のいずれか１項に記載の処理装置。
12. 【請求項１２】 前記データユニットは、単語、語彙ユ
    ニット及び語義ユニットを有するグループの１つを構成
    することを特徴とする請求項１乃至請求項１１のいずれ
    か１項に記載の処理装置。
13. 【請求項１３】 前記複数のマッチング手段は、前記入
    力データに対する非インデックス化変数を出力し、次
    に、前記入力データの前記インデックス化変数を出力す
    るように適合されることを特徴とする請求項１乃至請求
    項１２のいずれか１項に記載の処理装置。
14. 【請求項１４】 前記複数のマッチング手段は、前記入
    力データに対する前記インデックス化変数をインデック
    ス化する前記変数及び命令を記憶するために適合され、
    前記インデックス化変数をインデックス化するために前
    記命令を続いて実行することを特徴とする請求項１乃至
    請求項１３のいずれか１項に記載の処理装置。
15. 【請求項１５】 前記データユニット生成手段は、語彙
    ユニット及び対応品詞データを含む辞書と、テキスト単
    語の形式で前記入力データを受信する語彙プロセッサを
    含み、前記テキスト単語と単語ユニットをマッチング
    し、前記ユニットデータとして前記一致した語彙ユニッ
    トを出力し、前記ユニットカテゴリデータとして前記対
    応品詞データを出力することを特徴とする請求項１乃至
    請求項１４のいずれか１項に記載の処理装置。
16. 【請求項１６】 統語コンテキスト解析によって誤って
    割り当てられた品詞データを補正する手段とを含むこと
    を特徴とする請求項１５に記載の処理装置。
17. 【請求項１７】 システムの動作を制御する制御装置で
    あって、 上記請求項１乃至請求項１６のいずれか１項に従う処理
    装置と、 前記変数間の等価性を定義する関係に従って、前記入力
    データあるいは参照データの他の部分を修飾しない前記
    入力データあるいは参照データのheadであることが示さ
    れる変数から開始して変数を比較することによって、参
    照データから生成される変数とする前記入力データから
    生成される前記変数を比較する比較手段と、 前記比較結果に従うシステムの前記動作を制御する制御
    手段とを備えることを特徴とする制御装置。
18. 【請求項１８】 複数の異なるカテゴリからなるユニッ
    ト形式の自然言語の入力データからプロセッサ使用可能
    形式データを生成するプロセッサ実行方法であって、 ユニットデータ及び対応ユニットカテゴリデータからな
    るプロセッサ使用可能データユニットを生成するため
    に、入力データのユニットをそれぞれのカテゴリへカテ
    ゴリ化するカテゴリ化工程と、 前記ユニットカテゴリデータとユニットカテゴリデータ
    の少なくとも１つの所定パターンとをマッチングし、前
    記ユニットカテゴリデータの少なくとも１つの所定パタ
    ーンと一致した前記ユニットカテゴリデータに対するグ
    ループカテゴリデータを出力する第１マッチング工程
    と、 前記ユニットかつ／あるいはグループカテゴリデータの
    少なくとも１つの所定パターンと前記ユニットかつ／あ
    るいはグループカテゴリデータとが一致したカテゴリデ
    ータの代わりに、マッチング工程の少なくとも１つ前か
    ら一致しない前記ユニットカテゴリデータ及び前記グル
    ープカテゴリデータを使用し、ユニットかつ／あるいは
    カテゴリデータの前記少なくとも１つの所定パターンと
    一致したユニットかつ／あるいはグループカテゴリデー
    タに対し新規グループカテゴリデータを出力する少なく
    とも１つの追加マッチング工程とを備え、 前記マッチング工程の少なくとも１つは、一致したユニ
    ットカテゴリデータに対応する前記ユニットデータを複
    数の変数として出力し、前記変数の少なくとも１つはそ
    れ以外の変数によってインデックス化されることを特徴
    とする方法。
19. 【請求項１９】 前記マッチング工程のそれぞれは、前
    記自然言語に対する文法規則に従って構成された少なく
    とも１つの有限状態装置によって実行されることを特徴
    とする請求項１８に記載の方法。
20. 【請求項２０】 前記有限状態装置は、決定性があるこ
    とを特徴とする請求項１９に記載の方法。
21. 【請求項２１】 前記有限状態装置は、該有限状態装置
    がある状態から別の状態へ遷移する場合に前記変数を出
    力し、各遷移は、ユニットあるいは前記パターンのグル
    ープカテゴリデータを有する入力データからのユニット
    あるいはグループカテゴリデータのマッチングに対応す
    ることを特徴とする請求項１９または請求項２０に記載
    の方法。
22. 【請求項２２】 前記ユニットデータは、前記データユ
    ニットのセグメントのheadユニット及び修飾ユニットを
    定義する変数として出力され、前記インデックス化変数
    あるいは各インデックス化変数は対応修飾ユニットのユ
    ニットデータを定義することを特徴とする請求項１８乃
    至請求項２１のいずれか１項に記載の方法。
23. 【請求項２３】 前記マッチング工程の少なくとも１つ
    は、修飾されるデータのユニットの前記ユニットデータ
    を構成するインデックスを有する１つ以上の前記インデ
    ックス化変数を出力することを特徴とする請求項２２に
    記載の方法。
24. 【請求項２４】 前記更なるマッチング工程の少なくと
    も１つは、複数の異なる変数とする前記変数を出力し、
    各変数は異なる統語修飾を定義することを特徴とする請
    求項１８または請求項１９に記載の処理装置。
25. 【請求項２５】 前記マッチング工程の少なくとも１つ
    において、前記インデックス化変数は、前記マッチング
    工程から出力される変数によってインデックス化される
    ことを特徴とする請求項１８乃至請求項２４のいずれか
    １項に記載の方法。
26. 【請求項２６】 前記マッチング工程の少なくとも１つ
    において、前記インデックス化変数は、前のマッチング
    工程から出力される変数によってインデックス化される
    ことを特徴とする請求項１８乃至請求項２５のいずれか
    １項に記載の方法。
27. 【請求項２７】 前記ユニットカテゴリデータは、品
    詞、単語及び語彙ユニットを有するグループの１つを構
    成することを特徴とする請求項１８乃至請求項２６のい
    ずれか１項に記載の方法。
28. 【請求項２８】 前記グループカテゴリデータは、前記
    入力データの統語構造を定義することを特徴とする請求
    項１８乃至請求項２７のいずれか１項に記載の方法。
29. 【請求項２９】 前記データユニットは、単語、語彙ユ
    ニット及び語義ユニットを有するグループの１つを構成
    することを特徴とする請求項１８乃至請求項２８のいず
    れか１項に記載の方法。
30. 【請求項３０】 前記マッチング工程は、前記入力デー
    タに対する非インデックス化変数を出力し、次に、前記
    入力データに対するインデックス化変数を出力するため
    に反復することを特徴とする請求項１８乃至請求項２９
    のいずれか１項に記載の方法。
31. 【請求項３１】 前記マッチング工程は、前記入力デー
    タに対する前記インデックス化変数をインデックス化す
    る前記変数及び命令を記憶し、前記命令は、前記インデ
    ックス化変数をインデックス化するために続いて実行さ
    れることを特徴とする請求項１８乃至請求項３１のいず
    れか１項に記載の方法。
32. 【請求項３２】 前記データユニットは、テキスト単語
    として前記入力データを受信し、語彙ユニットを含む辞
    書の前記テキスト単語を参照し、前記ユニットデータと
    する一致した語彙ユニット及び前記ユニットカテゴリデ
    ータとする対応品詞データを出力するために品詞を対応
    させることによって生成されることを特徴とする請求項
    １８乃至請求項３１のいずれか１項に記載の方法。
33. 【請求項３３】 統語コンテキスト解析によって誤って
    割り当てられた品詞データを補正する工程とを含むこと
    を特徴とする請求項３２に記載の方法。
34. 【請求項３４】 上記請求項１８乃至請求項３３のいず
    れか１項の方法を有するシステムを制御する方法であっ
    て、 前記変数間の等価性を定義する関係に従って、前記入力
    データあるいは参照データの他の部分を修飾しない前記
    入力データあるいは参照データのheadであることが示さ
    れる変数から開始して変数を比較することによって、参
    照データから生成される変数と前記入力データから生成
    される前記変数を比較し、 前記比較結果に従うシステムの前記動作を制御すること
    を特徴とする方法。
35. 【請求項３５】 上記請求項１８乃至請求項３４のいず
    れか１項に記載の方法を実行するためのプロセッサを制
    御するプロセッサ実行可能命令を記憶する記憶媒体。
36. 【請求項３６】 上記請求項１８乃至請求項３４のいず
    れか１項に記載の方法を実行するためのプロセッサを制
    御するプロセッサ実行可能命令を転送する信号。