【課題】従来の通常型フィルタリング解析方式における特定の入力原言語文に対して発生した、部分パターンに対する不適切なスコアの付与法、部分パターンが存在しない状態が発生しないようにして正しい解析結果を与える機械翻訳結果選択方式を提供することを目的とする。
【解決手段】入力原言語文の特定単語の出現順序と同一の特定単語出現順序を持つ文例を文例群の中から選び、その文例が持つその文例に対応する解析結果の全体またはその一部分を上記通常型フィルタリング解析方式の部分パターンとして用い、これに高いスコアを与えることにより結果として入力原言語文に特化した部分パターンを持つ解析結果を選ぶ。これにより正しい解析結果を得ることができる。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は機械翻訳方式において原言語文を解析してその結果である解析木を発生する原言語文解析部の改良に関するものである。
【背景技術】
【０００２】
従来の機械翻訳方式の解析部の構成法には、１つの入力原言語文に対し１つの解析木を発生しその部分を少しずつ変形して行き、希望の解析結果を発生する部分文法法という方法、または１つの入力原言語文に対して多くの解析結果を発生しその中より１つの解析結果を選択するフィルタリング法という方法の２つがある。
【０００３】
通常型フィルタリング解析方式では１つの入力原言語文に対する多くの解析結果のそれぞれにスコアが付属している。このスコアはその解析結果が複数の部分パターンにより構成されると考えた場合その部分パターンが持つスコアの総和として得られる。通常型フィルタリング解析方式では１つの解析結果に対する全ての部分パターンによる構成法を試み、その中で最大のスコアを発生する構成法のスコアの総和をその解析結果のスコアとする。この意味では解析結果のスコアはその解析結果の部分パターンによる最良の分析結果を示していると理解できる。
【０００４】
ここで用いる部分パターンのスコアはまれに発生する部分パターンに高いスコアが与えられ、頻繁に発生する部分パターンには低いスコアが与えられる。このようにスコアは平均的な場合について与えられたものであり、これが特定の入力原言語文に関する状態に最適に当てはまるものではない。この意味で通常型フィルタリング解析方式における各解析結果のスコアは特定の原言語文に関して正確とは言えず、このため正解とは異なる解析結果が高いスコアを得て通常型フィルタリング解析方式の出力となることがある。また特定の入力原言語文に関して必要な部分パターンが無いため、正しい解析結果が部分パターンで解析できず結果として正しい解析結果が選ばれないことがある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、上述したような通常型フィルタリング解析方式における特定の入力原言語文に対して発生した、部分パターンに対する不適切なスコアの付与法、部分パターンが存在しない状態が発生しないようにして正しい解析結果を与える機械翻訳結果選択方式を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明による文例駆動型フィルタリング解析方式では、入力原言語文の特定単語の出現順序と同一の特定単語出現順序を持つ文例を文例群の中から選び、その文例が持つその文例に対応する解析結果の全体またはその一部分を上記通常型フィルタリング解析方式の部分パターンとして用い、これに高いスコアを与えることにより結果として入力原言語文に特化した部分パターンを持つ解析結果を選ぶ。これにより正しい解析結果を得ることができる。
【発明を実施するための最良の形態】
【０００７】
本発明で提示する文例駆動型フィルタリング解析方式はフィルタリング法を用いる通常型フィルタリング解析方式の改良に関するものである。このためまず通常型フィルタリング解析方式の説明を１つの入力例に関する処理の説明を行うことにより行う。ここでは英語文を解析する場合について考える。図１は通常型フィルタリング解析方式の構成図であり、本発明の範囲外の構造である。図１では文データの流れを太線で制御または規則の流れを細線で示した。
【０００８】
図１に於いてR1は形態素解析部、R2は書き換え規則適用部、R3はフィルタリング部、R4は内蔵書き換え規則メモリ、R5は内蔵排他木メモリである。R31、R32、R33はフィルタリング部R3を構成する部分であり、R31は主相対フィルタリング部、R32は禁止木適用部、R33は副相対フィルタリング部である。
【０００９】
この解析方式に
There was an excitement about soccer games. (1)
という英文が入力する場合について考察する。すなわち図１における（入力原言語文）として示した位置にこの英文が入力する。この英文は図１に於ける最初の処理である「形態素解析部」R1の処理を受ける。この処理は入力英文の各単語の切り分け、単語の活用等の変化形を原形に戻す働きをする。この処理の結果式(1)の英文は
There be{past,sgl} a excitement about soccer game{pl}. (2)
と変換される。ここで{past,sgl}の表記はここでの動詞wasがBE動詞の過去時称(past)、単数対応(sgl)のものであることを示し、{pl}の表記はgamesがgameの複数形(pl)であることを示す。式(2)の形態素解析部R1出力が次の「書き換え規則適用部」R2に入力する。図１に示すとおりこの部分には形態素解析部R1出力の他に「内蔵書き換え規則メモリ」R4出力が入力している。
【００１０】
内蔵書き換え規則メモリR4が保持する内蔵書き換え規則は、通常型フィルタリング解析方式が常に保持する解析規則である。内蔵書き換え規則は統語規則と品詞規則から構成される。ここでは統語規則と品詞規則はそれぞれ図２、３の各図に示す規則から成り立つものである場合について考える。統語規則は解析のための規則であり、品詞規則は単語と品詞の間の関係を示すものである。
【００１１】
図２、図３のそれぞれ統語規則と品詞規則に於ける単語以外の各節点は範疇と呼ばれる。範疇とは品詞およびそれより大規模な文法上の構成単位を表す文法用語である。図３の各規則の上位の部分には品詞すなわち範疇が存在しているがこのうち、THERE、BE、DET、N、PはそれぞれTHERE、BE動詞、限定詞、名詞、前置詞という品詞を表現する。単語thereは形容詞であるが特殊な動作をするので一つの品詞THEREを割り当てている。図３の各統語規則に於ける範疇CL、NP、PPは文（clause）、名詞句（noun phrase）、前置詞句（prepositional phrase）を表現する。
【００１２】
図１の書き換え規則適用部R2では、まず式(2)の形態素解析部R1出力に図３の品詞規則を適用し、次に図２の統語規則を適用する。品詞規則適用により発生した中間結果は図４(a)に示す形態素解析部R1出力の各単語の上位に対応する品詞が存在する構造を持つ。
【００１３】
その後統語規則の適用が行われる。すなわちある統語規則の下位にある範疇並びがあればそれらをまとめてその統語規則の上位にある範疇を構成する動作を行う。この２つの書き換え規則適用部R2の動作を書き換え動作と呼ぶ。このように書き換え規則適用部R2は書き換え動作を行いつつ下位より上位に向けて解析木を成長させていく。
【００１４】
書き換え規則適用部R2に於いて、式(2)の形態素解析部R1出力に内蔵書き換え規則メモリR4出力である図３の品詞規則を用いて図４(a)の中間結果を得てさらに同じく内蔵書き換え規則メモリ出力R4である図２に示す統語規則を適用して書き換え動作を行った結果のOR木の図が図７である。このOR木の構成法は本発明の範囲外のものであり、「榊博史著；コンピュータ翻訳技術；電子情報通信学会；平成５年刊」にくわしい。
【００１５】
OR木とは節点名ORで表現されているOR節点という特別な節点を含む。この節点の直下位に配置された解析結果は同一の最上位節点を持つ同一の単語区間の異なる解析結果である。ただし、この文書ではOR節点を取り扱い得る場所に存在する木はOR木を含まなくてもOR木と呼ぶこととする。また以後に説明するOR木の展開結果の木を含めて形態素解析部出力R1の解析結果を解析木と呼ぶこととする。解析木はその最上位節点として文を表すCLを持たねばならず、また最下位節点として文の全単語を持たなければならない。もちろん解析木に於ける最下位節点の並びは形態素解析部R1出力と同一でなければならない。
【００１６】
図７の場合「a excitement about soccer game{pl}」の単語区間に対する解析結果がOR節点によりまとめられている。
【００１７】
OR木を展開して得た木を展開木と呼ぶ。図４(b)、(c)は図７のOR木中OR節点でとりまとめられた部分を展開して得た木であり図７の展開木である。図４(b)、(c)の展開木は解析過程の説明に有用であるので以下の説明ではこれを用いる。
【００１８】
図４(b)、(c)の２つの解析木が持つ単語節点以外の各節点にはそれらの節点を構成する際に用いた品詞規則、統語規則を括弧で囲んだ形式の注記が付属している。例えば図４(b)の節点BEには(３図b)の注記が付属している。この注記は単語be{past,sgl}が存在するので図３(b)の品詞規則が適用され節点BEが生成されたことを示している。また同じく図４(b)の節点CLには(２図a)の注記が付属しているが、これは節点THERE、BE、NPの並びが発生するためにこれに適用した図２(a)の統語規則が適用されこれらの節点をまとめて節点CLが発生することを示す。この注記は説明のため付加したものであり、実際は括弧を含めてデータとしては存在しないものである。
【００１９】
通常型フィルタリング解析方式の書き換え規則適用部R2では形態素解析部R1出力に対し内蔵書き換え規則メモリR4出力である品詞規則、統語規則が制限なく適用されるため一般に多くのOR節点でとりまとめられた部分すなわち複数の展開木が発生する。今回の例では２つの解析木に分類される展開木が発生している。
【００２０】
通常型フィルタリング解析方式ではもちろん一つの入力文に対する正しい解析木は一つでなければならないので、例えば図４(b)、(c)の複数の展開木のうちの１つを正しい解析木として選ばなければならない。これを行うのが図１に於いて書き換え規則適用部R2の後段に存在する「フィルタリング部」R3である。実際の通常型フィルタリング解析方式ではOR木に於いてOR節点の下位のいくつかの部分解析結果のうち一つを選択することによりこの選択を行う。図１に示されているフィルタリング部R3の構成については後述するがまずその動作を説明する。
【００２１】
図１に示されるようにフィルタリング部R3は２つの入力を受け入れる。その一つは書き換え規則適用部R2出力であり、もう一つは内蔵排他木メモリR5出力である。ここでの例の場合前者は図７に示す等価的に２つの解析木の性質を持つ展開木を表現するOR木である。これは図４(b)、(c)に示す２つの解析木に相当する。ただし単語節点以外の付属している品詞規則、統語規則を示す(３図b)等の注記は説明のためのものであるので、削除して考える。
【００２２】
理解を容易にするためにここに導入する被覆の操作は図４(b)、(c)の解析木の性質を持つ展開木に即して行う。
【００２３】
フィルタリング部R3では書き換え規則適用部R2出力である一般に複数個の解析木をもう一方の入力である内蔵排他木メモリR5出力を構成する多くの排他木で被覆する動作を行う。ここでの例の排他木を図５および図６に示す。このうち図５の排他木は単語に関係しない一般的な排他木であり、図６の排他木は単語に関係する排他木である。図５、図６中の各排他木の最上位節点には括弧で囲んでC、D、E、F、G、K、L、N等の大文字のアルファベットが示されている。これらはそれぞれの排他木が持つスコアである。
【００２４】
図８はフィルタリング部R3の一方の入力である書き換え規則適用部R2出力を構成する解析木をもう一方の入力である内蔵排他木メモリR5出力を構成する排他木で被覆した結果である。ここで被覆とは解析木のある部分が排他木と同一構造を持つことを明示する動作である。ここでは解析木を「被覆の重複なくしかも被覆されない部分なく」排他木により被覆する。ただし被覆の境界の節点は、その節点の上位および下位にそれぞれ存在する２つの排他木に重複して被覆されるものとする。
【００２５】
このように解析木を被覆する排他木を「被覆排他木」と呼ぶ。
【００２６】
図８では被覆の境界の１つの節点を上下に近接した２つの節点に分割することにより、排他木による被覆状況をわかりやすく表現したものである。すなわちここでは、実際の１つの節点を近接して表現した２つの節点で示す。このようにすると境界の節点も１つの排他木のみに被覆されるように記述できる。
【００２７】
被覆の境界の１つの節点を上下に近接して表現した図８の被覆状態に於いて近接した節点のうちの下側の節点に括弧で囲んで付属した注記はこの境界節点より下位の部分を被覆する排他木が持つスコアを示す。各排他木のスコアは図５、６に示されている。
【００２８】
各解析木のスコアをそれを被覆する排他木のスコアの総和であると定義する。この際、加算はアルファベットで表現されたスコアの種類ごとに独立に行い加算結果を＋記号で結合する方法で表現する。例えば図８(a)の被覆法による図４(b)の解析木のスコアは、4C+E+2F+G+3K+Lであり、図８(b)の被覆法による図４(c)の解析木のスコアは、4C+E+2F+G+2K+Nである。２つの解析木のスコアの大小の比較は「アルファベットの最初の文字Aより順次アルファベットで表現されたスコアの種類ごとに含まれる排他木の個数の比較を順次行い、どれかの文字の排他木を一方の解析木がより多く持てば以後の比較を行わずその解析木のスコアが大きい」という定義により行われる。この例の場合スコアの種類Kの排他木を図８(a)の解析木は３個持ち、図８(b)の解析木は２個しか持たないので以後の排他木の比較を行うことなく図８(a)のスコアが大きいと判定する。
【００２９】
このスコアの判定の結果図１のフィルタリング部R3は図８(a)の解析木すなわち図４(b)の解析木を出力として発生する。
【００３０】
上記の展開木の選択は図７のOR木中のOR節点の左側の構造が選択されることに対応する。これが式(1)の原言語入力に対する通常型フィルタリング解析方式の原言語文解析結果出力となる。フィルタリング部R3には、等価的には図７のOR節点より下位の部分を展開した結果である図４(b)、(c)の２つの解析木が入力する。
【００３１】
これらがフィルタリング部R3の動作の結果図８に示すとおり排他木により被覆される。さらにフィルタリング部R3動作により図８(a)すなわち図４(b)の解析木が原言語文解析結果として出力される。すなわちフィルタリング部R3はOR節点を含む等価的に複数の解析木を代表する１つのOR木の入力を受け入れこれよりただ一つの解析木を選ぶ動作を行う。
【００３２】
なお排他木のスコアは解析木中にその部分が存在することの確からしさを表す。一般に特殊でまれな排他木ほど高いスコアを持つ。これは特殊な部分構造は、ひとたび発生した場合はその存在が確かであるからである。
【００３３】
例えば図５(a)の排他木はGという高いスコアが与えられているが、これは英文のThere構文という特異な構文を代表するからである。これに対して図５(d)、(g)の排他木は低いスコアが与えられている。これらの排他木がNPという変異に富み一般的な部分と前置詞または冠詞との組み合わせを表現する一般的な構造を表現するからである。
【００３４】
図１に示されているとおりフィルタリング部R3は正副２つの相対フィルタリング部R31、R33と禁止木適用部R32から構成されている。主相対フィルタリング部R31はこれまで述べたようにスコアの高い展開木を原文解析結果として出力する。これをスコアの高い勝者が出力されるため、相対フィルタリングと呼び、それを行う部分を主相対フィルタリング部R31と呼ぶ。これに加えてフィルタリング部は絶対フィルタリング機能を持つ。これは「禁止木」として登録された木構造を部分木として持つ原文解析結果の発生を阻止する機能である。
【００３５】
この絶対フィルタリングを行う部分が「禁止木適用部」R32である。これは主相対フィルタリング部R31により呼び出され、暫定的な原文解析結果を渡される。禁止木適用部R32はこれに禁止木による絶対フィルタリングを施し、結果を主相対フィルタリング部R31に返す。
【００３６】
禁止木適用部R32はその動作の過程で別の相対フィルタリング部である副相対フィルタリング部R33を呼び出す。呼び出された副相対フィルタリング部R33は必要な結果を返す。
【００３７】
図１中Cは呼び出しを示しRは結果を返す動作を示す。これら２つの相対フィルタリング部は全く同じ構造のものであり、１つのプログラムを双方に用いることができる。
【００３８】
単語に関する図６に示す排他木は単語という構造を特定する部分を持つため、そのスコアは高い。このなかで図６(f)、(g)の排他木のスコアが低いのはこれらが含む単語が名詞とともに動詞とも解釈できるからである。
【００３９】
以上で在来技術である通常型フィルタリング解析方式の説明を終わる。本発明を構成する文例駆動型フィルタリング解析方式は通常型フィルタリング解析方式を改良して構成するものである。図９は文例駆動型フィルタリング解析方式の構成図である。
【００４０】
図９に於いてE1は形態素解析部、E2は書き換え規則適用部、E3は上位排他フィルタリング部、E4は内蔵書き換え規則メモリ、E5は内蔵排他木メモリ、E6は品詞規則適用部、E7は直線化部、E8は文例メモリ、E9は合致文例群抽出部、E10は規則分離部、E11は書き換え規則レジスタ、E12は上位排他木処理蓄積部、E13は排他木レジスタ、E14はインタフェース＃１、E15はインタフェース＃２である。E31、E32、E33は上位排他フィルタリング部E3を構成する部分であり、E31は主上位排他相対フィルタリング部、E32は禁止木適用部、E33は副上位排他相対フィルタリング部である。
【００４１】
この図でも図１と同じく文データの流れを太い線で、規則または制御の流れを細い線で示してある。
【００４２】
図中細い線で囲まれている形態素解析部E1、書き換え規則適用部E2、内蔵書き換え規則メモリE4、内蔵排他木メモリE5、禁止木適用部E32は通常型フィルタリング解析方式を構成する部分と全く同じ部分である。
【００４３】
このため図９の文例駆動型フィルタリング解析方式の構成に於いてインタフェース＃１E14、インタフェース＃２E15の２つのインタフェースの部分を切断し排他木レジスタE13を取り去り、上位排他フィルタリング部E3をフィルタリング部R3に入れ替えると通常型フィルタリング解析方式に帰着する。
【００４４】
太い線で囲まれた品詞規則適用部E6、文例メモリE8、直線化部E7、合致文例群抽出部E9、規則分離部E10、書き換え規則レジスタE11、上位排他木処理蓄積部E12、排他木レジスタE13は文例駆動型フィルタリング解析方式に於いて新たに導入された部分である。
【００４５】
上位排他フィルタリング部は主および副の上位排他相対フィルタリング部E31、E33と通常型フィルタリング解析方式と同一の禁止木適用部E32から成る。上位排他相対フィルタリング部E3は通常型フィルタリング解析方式の相対フィルタリング部に「上位排他木」に対応する機能を付加したものである。ただしこれまでの排他木に関する機能はフィルタリング解析方式の相対フィルタリング部R3と同一である。上位排他木については後に説明する。
【００４６】
上位排他相対フィルタリング部E3中の主上位排他相対フィルタリング部E31、副上位排他相対フィルタリング部E33は本方式で新たに導入された部分であるが、それぞれ既存の通常型フィルタリング解析方式の主相対フィルタリング部R31および副相対フィルタリング部E33に機能追加を行って構成した部分であるので太線の点線で囲んでその事態を表現してある。
【００４７】
以後通常型フィルタリング解析方式の説明に関して用いた式(1)の英文
There was an excitement about soccer games. (1)
が入力英文として導入された場合を例に取り本発明の解析方式である文例駆動型フィルタリング解析方式の説明を行う。式(1)の英文に対する図８中の形態素解析部E1の動作は図１中の形態素解析部R1の動作と全く同じであり入力英文の各単語の切り分け、単語の活用等の変化形を原形に戻す働きをする。ここでの処理の結果形態素解析部E1出力として
There be{past,sgl} a excitement about soccer game{pl}. (2)
の形態素解析結果を得る。もちろん{past,sgl}の表記はここでの動詞wasがBE動詞の過去時称(past)、単数対応(sgl)のものであることを示し、{pl}の表記はgamesがgameの複数形(pl)であることを示すことも通常型フィルタリング解析方式の形態素解析部R1出力と同じである。
【００４８】
図９の品詞規則適用部E6は図１の通常型フィルタリング解析方式に於ける書き換え規則適用部R2で用いられる品詞規則と統語規則のうち品詞規則のみを用いるように機能を縮小した処理部分である。文例駆動型フィルタリング解析方式の説明に於いても品詞規則と統語規則として通常型フィルタリング解析方式に於けるそれらと同じものを用いる。すなわち、品詞規則は図３に示されるものであり、統語規則は図２に示されるものである。
【００４９】
品詞規則適用部E6では式(2)の形態素解析部E1出力に図３の品詞規則を適用し適用結果を出力として発生する。これを品詞規則適用結果と称する。品詞規則適用結果は通常型フィルタリング解析方式の書き換え規則適用部R2に於いて品詞規則適用後発生する中間結果すなわち図４(a)の構造と同一の構造である。これを改めて図１０(a)に示す。
【００５０】
図１０(a)の品詞規則適用結果の各成分は形態素解析部出力の各単語の上位に対応する品詞が存在する構造を持ち、これらの上位節点にはそれらの節点を構成する際に用いた品詞規則を括弧で囲んだ形式の注記が付属している。図４(a)に於けると同様、この注記は説明のため付加したものであり、実際は括弧を含めてデータとしては存在しないものである。ここでの各成分の順序は文中に於ける単語出現順序と同様変更は不可能である。
【００５１】
図９に示すように図１０(a)に示す品詞規則適用結果は「直線化部」E7の入力となる。ここは図１０(a)の品詞規則適用結果を受け入れると、品詞規則適用結果の各成分に於いて上位の節点を括弧で囲んで下位の節点の後に付属させ、各成分の相対位置をそのままに直線的に配列する。結果として入力文の各単語に括弧で囲んだ品詞が付属したことになる。これを図１０(b)に示す。直線化部出力を「抽出用単語列」と称する。
【００５２】
合致文例群抽出部E9の他の一方の入力は「文例メモリ」E8出力である。ここには設計上膨大な量の文例が蓄積されるのであるが、その１つが図１１の文例であるとする。文例は、合致条件、書き換え規則、上位排他木の３つの部分から成っている。図１１の例の場合、図１１(a)が合致条件、図１１(b)が書き換え規則、図１１(c)が上位排他木をそれぞれ示す。
【００５３】
まず合致条件より説明する。図１１(a)に表現されている構造は合致条件の例である。合致条件は「単語束」の一次元配列として構成される。各単語束はいくつかの単語、品詞記号もしくは空標識-、任意の１単語の標識$および任意の任意個数の単語の標識*により構成される。品詞記号は括弧で囲んで品詞記号であることを示す。図１１(a)では１つの単語束を四角の枠で囲んで表現してある。
【００５４】
例えば左より２番目の単語束の*は任意個数の任意個数の単語に合致させることができる単語束である。また左から４番目の単語束は１個の任意の単語に合致させることができる単語束である。左から６番目の単語束は品詞(N)と空標識-から構成されており、同７番目の単語束は単語文字列skiingと名詞に対応する品詞(N)から構成されている。合致文例群抽出部E9の動作の記述を以下に示す。
【００５５】
合致文例群抽出部E9ではある文例が合致条件を満たすかどうかの判定を行い、満たせばその文例を「合致文例」に指定し蓄積する。このような動作を合致文例群抽出部E9が保有する全ての文例について行う。蓄積動作終了後、合致文例群を規則分離部に出力する。
【００５６】
合致の定義は以下の通りである。
【００５７】
ある文例が持つ合致条件と抽出用単語列のある連続する部分抽出用単語列との間で合致が成立するとき、その文例は合致文例の条件を満たすと判定する。またこの合致する部分抽出用単語列を「単語束合致抽出用単語列」と呼ぶ。
【００５８】
合致抽出用単語列中の各単語束に合致する部分を「単語束合致抽出用単語列」と名付ける。合致条件と部分抽出用単語列の間で合致が成立する状況、すなわち「合致状況」を以下の(a)項に示す単語束合致抽出用単語列の区間に関する制限と、(b)項に示す単語束とそれに合致する「単語束合致抽出用単語列」との関係の性質の２項目に分けて記述する。
(a)合致条件中の左より１番目の単語束に対して、部分抽出用単語列中の最も左の単語を含むある連続する部分単語列を単語束合致抽出用単語列に指定する。以後左よりi+1番目の単語束に対して、「左よりi番目の単語束に対して指定された単語束合致抽出用単語列中の最も右の単語のすぐ右に位置する単語を含むある連続する部分単語列」を対応する単語束合致抽出用単語列に指定する。このことがiの値が１から単語束番号の最大値から１を引いた値まで成立する。但しi番目の単語束に対応する単語束合致抽出用単語列がない場合は、「左よりi-1番目の単語束に対して指定された単語束合致抽出用単語列中の最も右の単語のすぐ右に位置する単語を含むある連続する部分単語列」を対応する単語束合致抽出用単語列に指定する。このことは後述するように左よりi番目の単語束が空記号-または記号*を持つ場合に生じる。
(b)合致条件中の各単語束のそれぞれに対して、その単語束と単語束合致抽出用単語列との間に以下に示す合致関係のどれかが存在する。
(b1)単語束に含まれる単語の一つが、その単語束に対して指定された１単語から構成される単語束合致抽出用単語列を構成する単語と一致する。
(b2)単語束に含まれる括弧で囲まれた形式で表現された品詞名の一つが、その単語束に対して指定された１単語から構成される単語束合致抽出用単語列を構成する単語の品詞と一致する。
(b3)空記号-のみを含む単語束に対して指定された単語束合致抽出用単語列は存在しない。
(b4)任意１文字記号$のみを含む単語束に対して１つの単語から構成される単語束合致抽出用単語列が指定可能である。
(b5)任意長任意*記号のみを含む単語束に対して任意の個数の単語で構成される単語束合致抽出用単語列が指定可能である。
【００５９】
ここで、図１１の文例が文例適用条件を満たすかどうかの判定を行うために、図１１の文例が持つ図１１(a)の合致条件と図１０(b)に示す抽出用単語列との間で合致が成立するかどうかを調べる。図１２がこの合致成立の様子を示す図である。図１２中下位の部分は合致条件であり、第１番から第７番までの単語束から構成される。単語束の番号は各単語束の上に示してある。上位の部分は抽出用単語列であり、これの要素である単語は単語文字列、場合によっては中括弧で囲まれた属性、括弧で囲まれた品詞から構成されており、左方よりこの順に間にスペースを置かず配列されている。
【００６０】
図１２に於いて各単語束の上位に配置された単語が、各単語束に対して指定された単語束合致抽出用単語列である。この対応関係は上記(a)項に示す部分単語列の区間に関する制限を満たしている。この場合それぞれの単語束合致抽出用単語列は１つの単語から構成されている。これに加えて左から第１番目、３番目、５番目の単語束とそれらに関して指定された単語束合致抽出用単語列の間には上記(b1)項に示す合致関係が成立する。左から第６番目と第７番目の単語束に関しては(b2)の合致関係が存在する。左から２番目の単語束に関しては(b5)の、また左から４番目の単語束に関しては(b4)の合致関係がそれぞれ存在する。結局図１１の文例が持つ図１１(a)の合致条件と図１０(b)に示す抽出用単語列中の左より１番目から７番目までの連続する部分単語列との間で合致が成立するため図１１の文例は合致条件を満たしていると判定され合致文例に指定される。
【００６１】
ここでは抽出用単語列の全ての部分が合致抽出用単語列となっている。図１２中には単語束を構成する単語の内でその単語束に対して指定された単語束合致抽出用単語列との合致関係成立に関与した単語または記号について#記号を付してこれを表示してある。
【００６２】
以下図１１に示す文例の記述に立ち戻り本発明の合致文例群抽出部の記述を続ける。もちろんこの文例は図９が示すとおり文例メモリより合致文例群抽出部に入力したものである。図１２に関して記述したとおり、この文例が含む図１１(a)に示す合致条件を持つ文例は同じく図９が示すとおり品詞規則適用部E6より発生した図１０(b)に示す抽出用単語列との間に合致が成立し従って合致文例に指定される。ここまでが合致文例群抽出部E9の入力部分に関する記述である。
【００６３】
以下合致文例群抽出部E9の出力部分に関する記述を行う。図１１はこれまでの動作により合致文例として蓄積された文例の構成内容である。これは、これまで合致文例への指定判定に用いた図１１(a)に示す合致条件に加えて図１１(b)に示す書き換え規則、図１１(c)に示す上位排他木から構成される。
【００６４】
これら合致文例に指定された文例は順次合致文例群抽出部E9に蓄積される。合致文例群抽出部E9は規則分離部E10に一般に複数の合致文例に指定された文例を出力する。規則分離部E10はそれぞれ合致文例に指定された文例が持つ書き換え規則を書き換え規則レジスタE11に向けて出力し、また上位排他木を上位排他木処理蓄積部E12に出力する。本例の場合規則分離部E10は図１１(b)に示す書き換え規則が書き換え規則レジスタE11に、図１１(c)に示す上位排他木と後述する単語状態スタック内容が上位排他木処理蓄積部E12に出力する。
【００６５】
すなわち、合致文例群抽出部E9は文例メモリE8に収容されている全ての文例に付き合致文例に指定できるかどうかの判定を行い、指定された合致文例を蓄積した後規則分離部E10に出力する。
【００６６】
この処理の終了により品詞規則適用部E6、文例メモE8リ、直線化部E7、合致文例群抽出部E9、規則分離部E10の動作は終了する。これらの部分の動作から発生した情報のうち書き換え規則は書き換え規則レジスタE11中に蓄積され、上位排他木は上位排他木処理蓄積部E12で後述する具体化変形を受けに蓄積される。さらに上位排他木レジスタに蓄積された上位排他木は排他木レジスタE13に導入される。排他木レジスタE13には内蔵排他木メモリE5より排他木が入来するので排他木レジスタE13はこれら２つの部分から入来した上位排他木排他木が混在することになる。
【００６７】
これら書き換え規則、上位排他木は、その後の動作に用いられる。
【００６８】
ここでの例では、適用文例に指定された文例は図１１もののみであり、このため書き換え規則メモリE11中には図１１(b)の書き換え規則が、また上位排他木処理蓄積部E12には図１１(c)の上位排他木のみが存在するとする。上位排他木の構造の説明は後の上位排他フィルタリング部の説明に関連して行う。
【００６９】
ここでの例では図９に示す文例駆動型フィルタリング解析方式の内蔵書き換え規則メモリE4には図１に示す通常型フィルタリング解析方式の内蔵書き換え規則メモリR4の場合と同様図２の各図に示す統語規則と図３の各図に示す品詞規則が収容されているものとする。このうち品詞規則は前に述べた図９中の品詞規則適用部E6に於いて図１０(a)に示す品詞規則適用結果を発生するためにすでに用いられている。
【００７０】
図９に示す文例駆動型フィルタリング解析方式の書き換え規則適用部E2は通常型フィルタリング解析方式の同名の部分と同一の動作をすることはすでに述べた。これに処理対象入力として形態素解析部E1出力が入力する。この例の場合形態素解析部E1出力は式(2)に示すものである。これを以下に再び示す。
There be{past,sgl} a excitement about soccer game{pl}. (2)
【００７１】
前述したとおり{past,sgl}の表記はここでの動詞wasがBE動詞の過去時称(past)、単数対応(sgl)のものであることを示し、{pl}の表記はgamesがgameの複数形(pl)であることを示す。
【００７２】
書き換え規則適用部E2の他方の入力である書き換え規則としては内蔵書き換え規則メモリE4に存在する品詞規則および統語規則の他に書き換え規則レジスタE11に存在する書き換え規則がインタフェース＃１E13を経由して入力する。本例の場合内蔵書き換え規則メモリE4に存在する品詞規則および統語規則はそれぞれ図２、図３にそれぞれ示すものであり、通常型フィルタリング方式のそれらと同一であるとする。書き換え規則レジスタE11に存在する書き換え規則は前述したとおり図１１(b)に示すものである。
【００７３】
これらの書き換え規則を上記式(2)の形態素解析部E1出力に適用した結果、文例駆動型フィルタリング解析方式の書き換え規則適用部E2では以下の図１３に示すOR木が発生する。これは同一の最上位節点を持つ同一の単語区間の異なる解析結果がOR節点でまとめられた形式の部分構造を持つ。もちろんこの際の同一の単語区間は「a excitement about soccer game{pl}」の部分である。前述したようにOR木の構成法は本発明の範囲外のものであり「榊博史著；コンピュータ翻訳技術；電子情報通信学会；平成５年刊」にくわしい。
【００７４】
図１３は図１４に示す３個の解析木の性質を持つ展開木をまとめて表現したものである。以後の説明には図１３に代わり図１４に於ける各図を用いる。
【００７５】
図１４の各図のうち図１４(a)、(b)は内蔵書き換え規則メモリE4収容の規則のみを適用した結果発生した解析木であり、通常型フィルタリング解析方式の書き換え規則適用部E2出力の説明図である図４(a)および(b)と同じものである。
【００７６】
図１４(c)は書き換え規則レジスタに存在する図１１(b)の書き換え規則を適用した発生した解析木である。単語節点以外の各節点にはそれらの節点を構成する際に用いた品詞規則、統語規則を括弧で囲んだ形式の注記が付属している。図１４(c)の解析木中の節点NPのうちの一つには(１１図b)の注記が付属しており、この節点の構成に図１１(b)の書き換え規則が用いられたことを示している。すなわち、この場合文例由来の書き替え規則が用いられたことになる。文例にはこの他図５(a)の書き替え規則も登録可能であるがこれは登録されていないものとする。前述したとおりこれらの注記は説明のため付加したものであり、実際は括弧を含めてデータとしては存在しないものである。
【００７７】
このように文例由来の書き換え規則があるため、文例駆動型フィルタリング方式では一般に内蔵書き換え規則レジスタE11中の書き換え規則で発生するよりも多くのOR節点でまとめられる部分木または展開木が発生する。
【００７８】
図９の文例駆動型フィルタリング解析方式の構成図に示されるように上位排他フィルタリング部は３種類の入力を受け入れる。これらは処理対象としての書き換え規則適用部E2出力である一般にOR節点を含む解析木、内蔵排他木メモリE5出力である排他木、上位排他木処理蓄積部E12出力でありインタフェース＃２E15を経由して到着する上位排他木である。これらのうち後の２つは排他木レジスタE13により蓄積された後入力する。
【００７９】
書き換え規則に関しては、書き換え規則適用部E2入力の場合は内蔵書き換え規則メモリE4出力と文例から発生する書き換え規則レジスタ出力E11は書き換え規則という同一種類の規則であった。排他木に関しては、実際の運用上内蔵排他木メモリE5出力は排他木を発生し文例から発生する上位排他木処理蓄積部E12出力は上位排他木を発生するため、この２つの種類は異なる。しかし機能的には内蔵排他木メモリE5、上位排他木処理蓄積部E12双方が排他木、上位排他木どちらも発生可能である。
【００８０】
上位排他フィルタリング部は排他木を取り扱う能力に加えて上位排他木を取り扱う能力を持つ。この能力は在来技術であるフィルタリング部中の主副の相対フィルタリング部R31、R33に機能追加を行って、主および副の上位排他相対フィルタリング部E31、E33を構成することにより追加された能力である。
【００８１】
上位排他フィルタリング部に於ける正または副の上位排他相対フィルタリング部E31、E33では書き換え規則適用部E2出力である１つのOR木を一般に複数個の解析木の性質を持つ展開木に展開したものを、他の２種類の入力である内蔵排他木メモリE5出力を構成する多くの排他木ならびに上位排他木処理蓄積部出力E12を構成するいくつかの上位排他木を混合して用いて被覆する動作を行う。後の２つの排他木レジスタE13を経由して入力する。これが主または副の上位排他相対フィルタリング部E31、E33の等価的な動作であり、以下この等価的動作に関して説明する。
【００８２】
文例駆動型フィルタリング解析方式の場合、被覆とは前述したようにOR節点を含まない解析木のある部分が排他木または上位排他木と同一構造を持つことを明示する動作であると定義できる。被覆に際して解析木を「被覆の重複なくしかも被覆されない部分なく」排他木または後述する被覆上位排他木により被覆し被覆の境界の節点はその節点の上位および下位にそれぞれ存在する２つの排他木または上位排他木に重複して被覆されるものとする。
【００８３】
ここでの例の排他木は通常型フィルタリング解析方式の場合と同じく図５および図６に示すものであるとする。このうち図５の排他木は単語に関係しない一般的な排他木であり、図６の排他木は単語に関係する排他木である。図５、図６中の各排他木の最上位節点には括弧で囲んでC、D、E、F、G、K、L、N等の大文字のアルファベットが示すスコアが付属している点も相対フィルタリング部の場合と同じである。ここで例として用いる上位排他木は上位排他木処理蓄積部E12出力である図１１(c)の構造である。
【００８４】
図１５の各図は書き換え規則適用部E2出力を構成する図１４に示す解析木を排他木および被覆上位排他木で被覆した結果である。図８のフィルタリング部の場合と同じく被覆の境界の１つの節点を上下に近接した２つの節点に分割することにより表現し、また近接した節点のうちの下側の節点に括弧で囲んでスコアを注記してある。排他木に関してはそのスコアは図５、６に示されている。図１４に示す解析木のうち図１４(a)、(b)の解析木はそれぞれ図１５(a)、(b)に示されるように排他木のみに被覆されている。図１４(c)の解析木は図１５(c)に示されるように排他木と被覆上位排他木双方により被覆されている。
【００８５】
ここで上位排他木の機能、被覆上位排他木について説明する。通常の排他木は通常の形式の節点により構成され、解析木の被覆に当たってはその節点の全てがそれぞれ解析木のどれかの節点を被覆しなければならない。図１１(c)で明らかなように上位排他木はこれら通常の節点の他に排他木にはない節点形式を持つ。その一つは同図中の節点Nのような#記号が後に付属した形式の節点であり他の一つはOR節点でまとめられた複数の単語節点である。
【００８６】
上位排他木による解析木の被覆に際しては、#記号が後に付属した形式の節点は上位排他木から削除可能である。#記号が後に付属した形式の節点は上位排他木の葉節点を含む木の下位部分に任意に配置可能であるから、#記号が後に付属した形式の節点の削除状況に応じて異なった木を排他木機能を持つ木として指定可能である。ただし上位排他木中の通常の節点は必ず上位排他木を持つ木に残存しなければならない。
【００８７】
またOR節点でまとめられた複数の単語節点はその内の任意の１つの単語を排他木機能を持つ木の一部として指定可能である。このように形態素解析部E1出力の解析結果である解析木だけではなく規則側にOR節点を持たせることも可能である。
【００８８】
このように１つの上位排他木は一般に複数の形式の排他木機能を持つ木として機能できる。この意味で上位排他木は排他木の機能拡張形である。運用上上位排他木は内蔵排他木メモリE5のなかには存在せず、図１１(c)に見られるように文例が発生する木として存在する。もちろん以後の議論からわかるように上位排他木を内蔵排他木メモリE5に記憶させても別に問題が生じない。
【００８９】
なお形態素解析部E1出力の解析結果である解析木を被覆可能なように上位排他木に於いて#記号が後に付属した形式の節点を適宜削除しOR節点でまとめられた複数の単語節点のうちの１つを選んで変形して得た上述した排他木機能を持つ構造を、「被覆上位排他木」と呼ぶ。
【００９０】
図１１(c)に示す上位排他木とこれによる被覆状態を示す図１５(c)とを比較することにより、この場合の被覆上位排他木は図１１(c)に示す上位排他木から、それぞれ#記号が後に付属した節点Nならびに単語skiingが削除された構造を持つことがわかる。またOR節点でまとめられた複数の単語節点のなかからそれぞれ、be{past,sgl}、aが選ばれている。
【００９１】
排他木と同様上位排他木を変形した被覆上位排他木もスコアを持つ。スコアは正式には「削除されたいくつかの節点のうちでルート節点に近いもの」の集合の関数と考えられるので、そのような節点とスコアの対照表を定義するのが最も一般的な方法である。本発明では被覆上位排他木のスコアは被覆上位排他木が持つ節点数に最上位スコアであるAを乗じたものであるとする。この結果必ず被覆上位排他木で被覆された解析木が文例駆動型フィルタリング解析方式の出力となる。すなわち文例より得られた解析結果が解析出力として発生する。図１５(c)に於いて節点CLを最上位節点とする被覆上位排他木のスコアは13Aであり、この値が括弧で囲まれて節点名CLに付属している。
【００９２】
通常型フィルタリング解析方式のフィルタリング部R3と同じく、各解析木のスコアをそれを被覆する排他木のスコアの総和であると定義する。この際、フィルタリング部R3と同様加算はアルファベットで表現されたスコアの種類ごとに独立に行い加算結果を+記号で結合する方法で表現する。例えば図１５(a)の被覆法による図１４(a)の解析木のスコアは、4C+E+2F+G+3K+Lであり、図１５(b)の被覆法による図１４(b)の解析木のスコア4C+E+2F+G+2K+Nである。また図１５(c)の被覆法による図１４(c)の解析木のスコアは13A+2F+Kである。
【００９３】
２つの解析木のスコアの大小の比較は「アルファベットの最初の文字Aより順次アルファベットで表現されたスコアの種類ごとに含まれる排他木の個数の比較を順次行い、どれかの文字の排他木を一方の解析木がより多く持てば以後の比較を行わずその解析木のスコアが大きい」という定義により行われることもフィルタリング部R3と同じである。このスコアの判定の結果図９のフィルタリング部E3は図１５(c)の解析木すなわち図１４(c)の解析木を出力として発生する。これが式(1)の原言語入力に対する上位排他フィルタリング部E3の原言語文解析結果出力となり、フィルタリング部R3が選定した図４(b)の解析木すなわち図１４(a)のそれとは異なった解析結果が発生する。この解析結果は文例がもたらした書き換え規則により発生したものである。
【００９４】
上位排他フィルタリング部E3の上位排他相対フィルタリング部E31には図１４に示す３つの解析木の集合と等価なOR節点を含む図１３のOR木が入力するが、この部分の動作の結果図１５(c)のそれが原言語文解析結果として出力される。図１５(c)の解析結果は図１３のOR中OR節点でまとめられた３つの部分のうち一番右側の部分構造を含む解析結果に相当する。
【００９５】
文例駆動型フィルタリング解析方式の上位排他フィルタリング部E3の主上位排他相対フィルタリング部E31に於ける上位排他木はその解析木の被覆段階で被覆に関する自由度があるが、いったん被覆排他木になり解析木を被覆する段階では通常の排他木と全く同じ機能を持つことがわかる。この意味で文例駆動型フィルタリング解析方式の主上位排他相対フィルタリング部E31はフィルタリング部の主相対フィルタリング部R31に上位排他木の被覆に対する変形の機能を付け加えたものであるということができる。
【００９６】
以上で本発明の動作の全般的な説明を終わる。次いで図９の文例駆動型フィルタリング解析方式の構成図中の合致文例群抽出部E9の動作を実現する方法を示す。
【００９７】
合致文例群抽出部E9の入力の一つは直線化部の出力である抽出用単語列であり、他の一つは文例メモリE8より発生する多くの個数の文例である。抽出用単語列は自然言語文が含む各単語の後に括弧で囲まれた品詞記号が付加された構造であり、図１２中の上側に例示された形式を持つものである。文例は図１１に例示された形式を持つ。これは図１１(a)に例示される合致条件、図１１(b)に例示される書き換え規則、図１１(c)に例示される上位排他木から構成される。
【００９８】
合致文例群抽出部E9は前に(a)項と(b)項に分けて示した合致状況を、文例が持ち上記図１１(a)に例示される合致条件が満たすことによりその文例が合致文例に指定できるかどうかを判定するものであり、指定された合致文例を蓄積した後規則分離部に出力する。
【００９９】
以下の図１６はこの合致文例群抽出部E9の動作フローチャートであり、以後これについて順次説明する。図に示すようにこれはA1からA47までの動作により構成されている。ここでの動作は以下の１０個のパラメターに支配される。すなわちこれらは(1)単語束番号、(2)単語番号、(3)抽出用単語列単語番号、(4)先行単語束*標識、(5)合致単語束番号、(6)文例単語、(7)抽出用単語列単語、(8)単語束の単語数、(9)単語束数、(10)抽出用単語列単語数である。これらのうち(6)の文例単語は(1)の単語束番号と(2)の単語番号より合致条件配列を参照することにより求められ、(7)抽出用単語列単語は(3)の抽出用単語列単語番号より抽出用単語列配列を参照することにより求められ、(8)の単語束の単語数は(1)の単語束番号より単語束配列を参照することにより求められる。またパラメター(9)は１つの文例取り扱い中は不変のパラメターであり、単語束配列の列数より求められ、またパラメター(10)は抽出用単語列配列の列数を測定することにより求められる。パラメター(5)は合致文例群抽出の動作そのものには関係しないパラメターであり、文例単語と抽出用単語が一致する際一致を発生した文例単語の単語束番号を記述するものである。これは他のどのパラメターとも独立したパラメターである。これは後述するように上位排他木の節点に属性を付加するために用いる。このため合致文例群抽出部E9の動作を記述するに必要な独立パラメターは最初の４つである。上述した合致条件配列、抽出用単語列配列、単語束配列についてはそれぞれ後述する。
【０１００】
上述したように前記４つのパラメターによりある時点に於ける合致文例群抽出部の動作状態を特定できる。すなわち上記の内パラメター(1)と(2)を統合することにより文例が持つ 合致条件中の処理対象である単語位置を特定し、パラメター(3)は入力文側の抽出用単語列中の処理対象である単語位置を特定できる。またパラメター(4)は処理時点の直前に処理された単語束の種類を保持する。合致文例群抽出部の動作は、しばしば過去の動作状態を再現する必要があるのでこれら４つのパラメターの値をまとめて単語情報値として取り扱う。単語情報値は「単語情報値スタック」と称するスタック中に収容され必要に応じてスタックへのプッシュ、スタックからのポップを行う。
【０１０１】
ここで例として用いる入力文は図１２に対応する式(2)の形態素解析部E1出力ではなく以下式(3)に示す出力を用いる。式(2)はこれまで用いられてきた入力文であるが、任意記号*と空記号-に対する合致文例群抽出部E9の動作を調べるためにここでは式(3)を用いる。式(2)、式(3)とも図１１(a)の合致条件を満たす。
But there be{past,sgl} a excitement about game{pl}. (3)
【０１０２】
図１６に於いて、A1は抽出用単語列導入動作、A2は配列化動作、A3は単語列単語数測定動作、A4は全文例文例メモリ導入動作、A5は文例取り出し動作、A6は合致条件分離動作、A7は配列化動作、A8は単語束測定と配列化動作、A9はパラメター初期設定動作、A10は文例単語番号比較動作、A11は抽出用単語番号比較動作、A12は文例単語更新動作、A13は先行単語束*判定動作、A14は文例単語抽出用単語更新動作、A15は文例対抽出用単語比較動作、A16は単語一致対応パラメター設定動作、A17は単語束単語数更新動作、A18は単語番号比較動作、A19は単語番号１増加動作、A20は抽出用単語番号比較動作、A21は単語ずらしパラメター設定動作、A22は文例単語*判定動作、A23は*対応パラメター設定動作、A24は文例単語$判定動作、A25は$対応パラメター設定動作、A26は文例単語-判定動作、A27は-対応パラメター設定動作、A28は文例単語抽出用単語更新動作、A29は文例対抽出用単語比較動作、A30は単語束単語数更新動作、A31は単語番号比較動作、A32は単語番号１増加動作、A33は文例単語更新動作、A34は単語一致対応パラメター設定動作、A35は単語状態値プッシュ動作、A36は単語状態値存在判定動作、A37は単語状態値ポップ動作、A38は文例単語更新動作、A39は先行単語束*判定動作、A40は文例単語*及び$判定動作、A41は文例スタック導入動作、A42は文例存在判定動作、A43は合致文例存在判定動作、A44は合致文例出力動作、A45は空フラッグ発生動作、A46は非合致単語状態値プッシュ動作、A47は合致単語状態値プッシュ動作である。
【０１０３】
図１６は図１６aと図１６bの２つの部分図から成り立っている。図１６中X1〜X7として示す点はこれら部分図の間の接続関係を示す接続点でありそれぞれの点自身は機能を持たない。部分図の一方に於ける接続点にはその接続点に接続する部分図の他の一方に於ける動作の見出し語が接続している。例えば接続点X1は図１６b中の動作A46に接続しており、このことが図１６aに於ける接続点X1に接続する見出し語A46で示されている。
【０１０４】
動作A1で図１２上側の抽出用単語列が合致文例群抽出部に入力し、次の動作A2にて１次元配列に配列化される。動作A2は直線状に配列された単語列を１次元配列に変換する部分である。この配列を「抽出用単語列配列」と呼ぶことにする。抽出用単語列と抽出用単語列配列を図１７(b)に示す。ここでCONJは接続詞の品詞をあらわす。
【０１０５】
次いで動作A3により抽出用単語列配列の列数を測定することにより抽出用単語列配列の単語数を測定する。この数は上述した合致文例群抽出部動作を規定するパラメターの一つパラメター(10)として指定された「抽出用単語列単語数」である。この値は合致文例群抽出部動作中一定に保持され随時参照される。この例の場合は抽出用単語列単語数の値は７である。この値を図１７(e)に示す。
【０１０６】
以下図１６のフローチャートに沿い合致文例群抽出部E9の動作を説明する。
【０１０７】
次いで動作A4により「文例メモリ」に合致文例群抽出部E9が持つ全ての文例を導入する。次の動作A5で文例メモリに導入された多くの文例の１つが取り出される。このように動作A5は文例メモリ中の文例を１つずつ取り出す動作である。
【０１０８】
本例の場合文例メモリに導入される文例は図１１に示す文例のみであり動作A5でこれが取り出される。図１１に例示されるように文例は合致条件、書き換え規則、上位排他木の３つの部分から構成される。動作A6ではこのうち図１１(a)に例示される合致条件のみを分離し処理対象とする。なお、文例全体は当該文例処理中保持される。
【０１０９】
動作A7は単語束毎に分離して存在する合致条件を２次元配列に変換する部分である。ここでは単語束を列に対応させ、単語束中の単語を行に対応させる。合致条件および合致条件の配列化結果を図１７(a)に示す。この様に配列化を行うと必要な要素の参照が容易となる。この配列を「合致条件配列」と称する。
【０１１０】
続く動作A8では前動作で得た合致条件配列の列数を測定することにより文例の単語束数を測定する。この数は上述した合致文例群抽出部E9動作を規定するパラメターの一つパラメター(9)として指定された「単語束数」である。この値は合致文例群抽出部動作中一定に保持され随時参照される。この例の場合は単語束数の値は７である。この値を図１７(d)に示す。
【０１１１】
また合致条件配列の各列毎の有意な要素の数を測定し配列化する。この配列を「単語束配列」と呼ぶ。この例に於ける単語束配列は図１７(c)のようになる。例えば第３単語束の単語数は２であるので図１７(c)の第３列には値２が存在する。
【０１１２】
続く動作A9は前述した４つの主要パラメターから構成される単語状態値に、当該文例に関する初期値を導入する部分である。ここでは(1)単語束番号に値1、(2)単語番号に値1、(3)抽出用単語列単語番号に値1、そして(4)先行単語束*標識に値Tが導入される。抽出用単語列単語番号は図１６中では抽出用単語番号と略記されている。
【０１１３】
パラメター(4)の値は一般的には直前に取り扱った単語束が値*のみからなる場合、そのことを表示するためにTの値を取るものである。ここでは合致条件を構成する単語束列の先頭単語も同様な取り扱いをするのでこの値をTとする。ここで導入した単語状態値を今後の合致文例群抽出部E9の動作状態に指定する。
【０１１４】
続く動作A10では現在の単語束番号値が図１７(d)に示される単語束数がより大きいかどうかの判断である。前者は直前に導入した１であり後者は７であるのでここでの判断はnoであり動作はA11に移る。動作A10は合致条件と抽出用単語列の合致が成立したかどうかの判断を行う部分である。すなわち今後取り扱う単語束の番号が合致条件中の最終の単語束の番号を越えると合致が成立するので、その場合の判断がyesとなり合致成功の動作である動作A41に移る。ここではまだ１番目の単語束を取り扱い中であり、この判断はnoとなる。
【０１１５】
次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。これは抽出用単語列全部を調べつくしたかどうかの判定である。なお抽出用単語列単語番号はパラメター(3)に相当し抽出用単語列単語数はパラメター(10)に相当する。これは図１７(e)に与えられているものであり合致文例群抽出部動作中は不変のものである。ここの場合は前者が１であり後者が７であるので不成立であり次の動作は動作A12である。なお成立の場合は後述するバックトラック動作を行う動作A36に移行する。
【０１１６】
次の動作A12は現在のパラメター(1)単語束番号と同パラメター(2)単語番号を合致条件配列に適用して、パラメター(6)の文例単語を抽出し以前の値に上書きする部分である。ここでの例の場合単語束番号、単語番号共に１であり、図１７(a)の合致条件配列の第１列、第１行の要素Thereが文例単語として抽出される。このように動作A12では単語束番号列、単語番号行の要素が抽出、上書きされる。
【０１１７】
次の動作A13では先行単語束*標識すなわちパラメター(4)の値がTかFかを判定する動作である。これは現在処理中の単語束の直前の単語束が*のみから成る場合はTそうでなければFである標識である。この例の場合前述した理由によりこの標識の値はTであり、動作A13の判定はyesであり、次動作は動作A14である。
【０１１８】
動作A14ではパラメター(1)と(2)および合致条件配列より現在取り扱い中のパラメター(6)の文例単語を抽出し以前の値に上書きすると共にパラメター(3)の抽出用単語列単語番号を用いて抽出用単語列配列よりパラメター(7)の抽出用単語列単語を抽出し以前の値に上書きする動作である。この動作の前半の動作は動作A12の動作と同じである。この例の場合はパラメター(3)の値は１であるので図１７(b)の抽出用単語列配列の第１列の値But(CONJ)が抽出用単語列単語となる。
【０１１９】
動作A15ではパラメター(6)の文例単語とパラメター(7)の抽出用単語列単語の比較を行い、一致か不一致の判定を行う。比較は文例単語が単語であれば抽出用単語列単語の括弧の左側の単語の部分との比較を行い、文例単語が括弧に囲まれた品詞であれば抽出用単語列単語の括弧の中の品詞の部分との比較を行う。この例の場合文例単語が単語Thereであるので単語としての一致が調査され、不一致の判定が発生し次の動作は動作A17である。
【０１２０】
動作A17は現在取り扱い中の単語束が含む単語の数を求める動作である。単語束とそれが含む単語の数の対応関係は図１７(c)の単語束配列で与えられているのでこの配列を参照する。この場合の単語束番号は１であるので同配列第１列の要素１がこの場合の単語束の単語数となる。なお単語束番号はパラメター(1)に相当し単語束の単語数はパラメター(8)に相当する。
【０１２１】
動作A18では現在の単語番号が単語束が含む単語の数すなわち単語束の単語数より小さいかどうかの判定である。この判定が不成立であればその単語束の単語を調べつくしたことを意味する。単語番号はパラメター(2)に相当し前述したように単語束の単語数はパラメター(8)に相当する。この場合は不成立であるので次の動作は動作A20である。
【０１２２】
動作A20は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より小さいかどうかの判定を行う。これは抽出用単語列全部を調べつくす寸前かどうかの判定である。この動作は動作A11と類似の動作である。この例の場合は前者が１であり後者が７であるので成立であり次の動作は動作A21である。なお不成立の場合は後述するバックトラック動作を行う動作A36に移行する。
【０１２３】
ここでは単語束番号はそのままで抽出用単語列単語番号を１つ増加させて抽出用単語列中の次の単語と現在の単語束の単語との比較を行う準備をする動作である。動作は再び動作A14に戻る。この場合抽出用単語列単語番号は２となる。
【０１２４】
動作A14ではパラメター(1)、(2)、(3)を参照して文例単語、抽出用単語列単語を抽出上書きする動作である。文例単語がthereであり抽出用単語列単語はthere(THERE)である。次の動作A15では単語が一致するので一致の判定が発生する。ここから抽出用単語列の連続した単語列合致抽出用単語列が始まる。
【０１２５】
以後動作は動作A16に移る。ここでは合致文例群抽出部E9の次回の動作状態を指定する次回の単語状態値を構成する。前述したようにこれは独立な４つのパラメターであるパラメター(1)、(2)、(3)、(4)から構成される。このうちパラメター(1)の単語束番号としては現在の単語束番号に１を加えた値が指定され、またパラメター(2)の単語番号としては、次の単語束番号の単語束が持つ単語の１番目のものを取り扱うために値１が指定される。またパラメター(3)の抽出用単語列単語番号としては現在の抽出用単語列単語番号に１を加えた値が指定される。またパラメター(4)の先行単語束*標識の値としてFが導入される。
【０１２６】
この動作により合致文例群抽出部E9は次回、現在の単語束の次の単語束と抽出用単語列中現在取り扱い中の単語の次の単語を取り扱うことになる。現在の単語束そのものは*のみから成る単語束ではないのでパラメター(4)の値はFとなる。ここでの例の場合パラメター(1)、(2)、(3)、(4)はそれぞれ２、１、３、Fとなる。
【０１２７】
次いで動作A47にて現在の合致文例群抽出部E9の動作状態を示す単語状態値すなわちパラメター(1)単語束番号、パラメター(2)単語番号、パラメター(3)抽出用単語列単語番号、パラメター(4)先行単語束*標識、(5)合致単語束番号の値それぞれ１、１、２、T、1を「単語状態値スタック」にプッシュする。最後のパラメター(5)合致単語束番号はパラメター(1)と同じものであるが文例、抽出用単語が一致する動作A16、A36に続く動作A47の場合有意な値を導入する。なお同じ単語状態値スタックのプッシュ動作でも文例、抽出用単語間の一致を得ない動作A23、A25、A27に続く動作A46の場合は空であることを示す-が導入される。
【０１２８】
単語状態値スタックはラストカムファーストアウト形式のスタックであり、ポップ時このスタックより発生するデータは最後にこのスタックに導入したものとなる。現在の合致文例群抽出部E9の動作状態を記録することは、その後の動作失敗時のバックトラックにおける動作の出発点を確保するため必要である。
【０１２９】
図１８はここでの例の場合の単語状態値スタックの経過を示す図である。このうち図１８(a)が現在の動作A47の後の単語状態値スタックの状態である。
【０１３０】
次いで動作は再び動作A10に戻る。ここでの動作の出発点は前回の動作で次回の単語状態値として指定されたパラメター(1)、(2)、(3)、(4)の値がそれぞれ２、１、３、Fの状態である。パラメター(1)値である現在の単語束番号値が２であり、単語束数は図１７(d)に示すように７であるのでここでの判断はnoであり動作は動作A11に移る。
【０１３１】
次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。この例の場合は前者が３であり後者が７であるので不成立であり次の動作は動作A12である。なお成立の場合は後述するバックトラック動作を行う動作A36に移行する。
【０１３２】
動作A12ではパラメター(1)、(2)値それぞれ２、１であるところから、図１７(a)の合致条件配列の第２列第１行の要素*が抽出されパラメター(6)の文例単語として上書きされる。次の動作A13ではパラメター(4)の値がFであるので判定はnoであり、次動作は動作A22である。
【０１３３】
前動作A12で計測したパラメター(6)の値である文例単語は*であるので、動作A22での判定はyesであり次動作はA23である。
【０１３４】
ここでは合致文例群抽出部E9の次回の動作状態を指定する次回の単語状態値を構成する。ここではパラメター(1)の単語束番号としては現在の単語束番号に１を加えた値が指定され、またパラメター(2)の単語番号としては、次の単語束番号の単語束が持つ単語の１番目のものを取り扱うために値１が指定される。またパラメター(3)の抽出用単語列単語番号としては現在の抽出用単語列単語番号と同一の値が指定される。またパラメター(4)の先行単語束*標識の値としてTが導入される。
【０１３５】
この動作により合致文例群抽出部E9は次回、現在の単語束の次の単語束と抽出用単語列中現在取り扱い中の単語と同一の単語を取り扱うことになる。これは*記号が合致動作に於いて抽出用単語列のどの単語とも対応しなくてもよいことを反映する。すなわち同一抽出用単語列単語を次の回の処理でも用いることを指定する。また今回の単語束単語が*であるので次回のパラメター(4)値はTとなる。ここでの例の場合パラメター(1)、(2)、(3)、(4)はそれぞれ３、１、３、Tとなる。
【０１３６】
次いで動作A46にて現在の合致文例群抽出部E9の動作状態を示す単語状態値を「単語状態値スタック」にプッシュする。この例の場合単語の合致が生じない動作A23を経由したのでパラメター(1)、(2)、(3)、(4)、(5)の値はそれぞれ、２、１、３、F、-であり、この値がプッシュされる。図１８(b)が現在の動作A46の後の単語状態値スタックの状態である。
【０１３７】
次いで動作は再び動作A10に戻る。ここでの動作の出発点は前回の動作で次回の単語状態値として指定されたパラメター(1)、(2)、(3)、(4)の値がそれぞれ３、１、３、Tの状態である。パラメター(1)値である現在の単語束番号値が３であり、単語束数は７であるのでここでの判断はnoであり動作は動作A11に移る。次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。この例の場合は前者が３であり後者が７であるので不成立であり次の動作は動作A12である。
【０１３８】
動作A12ではパラメター(1)、(2)値それぞれ３、１であるところから、図１７(a)の合致条件配列の第３列第１行の要素aが抽出されパラメター(6)の文例単語として上書きされる。次の動作A13ではパラメター(4)の値がTであるので判定はyesであり、次動作は動作A14である。
【０１３９】
動作A14ではパラメター(1)、(2)、(3)を参照して文例単語、抽出用単語列単語を抽出上書きする動作である。文例単語がaであり抽出用単語列単語はbe{past,sgl}(BE)である。次の動作A15では単語が一致しないので不一致の判定が発生し次の動作は動作A17である。
【０１４０】
動作A17は現在取り扱い中の単語束が含む単語の数を求める動作である。この例の場合の単語束番号は３であるので同配列第３列の要素２がこの場合の単語束の単語数となる。
【０１４１】
動作A18では現在の単語番号が単語束が含む単語の数すなわち単語束の単語数より小さいかどうかの判定である。この判定が不成立であればその単語束の単語を調べつくしたことを意味する。この場合は単語番号は１であり、成立の判定が発生する。すなわちこの単語束にはまだ調べていない単語があるという判定であり動作はA19に移行する。ここではパラメター(2)である単語番号の値を１だけ増加させる。この場合は２となり再び動作A14に至る。
【０１４２】
動作A14ではパラメター(1)、(2)、(3)を参照して文例単語、抽出用単語列単語を抽出上書きする動作である。この場合はパラメター(1)、(2)、(3)がそれぞれ３、２、３であるので文例単語がthe、抽出用単語列単語がbe{past,sgl}(BE)となる。次の動作A15では単語が一致しないので不一致の判定が発生し次の動作は動作A17である。
【０１４３】
動作A17は現在取り扱い中の単語束が含む単語の数を求める動作である。この例の場合は２となる。動作A18では現在の単語番号が、単語束が含む単語の数すなわち単語束の単語数より小さいかどうかの判定である。この場合単語番号は２であり、不成立の判定が発生し動作は動作A20に移る。
【０１４４】
動作A20は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より小さいかどうかの判定を行う。この例の場合は前者が３であり後者が７であるので成立であり次の動作は動作A21である。動作A21では単語束番号はそのままで抽出用単語列単語番号を１つ増加させて抽出用単語列中の次の単語と現在の単語束の単語との比較を行う準備をする。動作は再び動作A14に戻る。この場合抽出用単語列単語番号は４となる。次の処理対象の抽出用単語列単語番号が４であることは２番目の文例単語束の単語*が３番目の抽出用単語列単語be{past,sgl}(BE)と合致することを意味する。
【０１４５】
動作A14ではパラメター(1)、(2)、(3)の値それぞれ３、１、４を参照して文例単語、抽出用単語列単語を抽出上書きする動作である。文例単語がaであり抽出用単語列単語はa(DET)である。次の動作A15では単語が一致するので一致の判定が発生する。
【０１４６】
以後動作は動作A16に移る。ここでは合致文例群抽出部の次回の動作状態を指定する次回の単語状態値を構成する。パラメター(1)の単語束番号としては現在の単語束番号に１を加えた値が指定され、またパラメター(2)の単語番号としては、次の単語束番号の単語束が持つ単語の１番目のものを取り扱うために値１が指定される。またパラメター(3)の抽出用単語列単語番号としては現在の抽出用単語列単語番号に１を加えた値が指定される。またパラメター(4)の先行単語束*標識の値としてFが導入される。ここでのパラメター(1)、(2)、(3)、(4)値はそれぞれ４、１、５、Fである。
【０１４７】
次いで動作A47にて現在の合致文例群抽出部E9の動作状態を示す単語状態値を「単語状態値スタック」にプッシュする。この例の場合パラメター(1)、(2)、(3)、(4)、(5)の値はそれぞれ、３、１、４、T、3であるのでこの値がプッシュされる。図１８(c)が現在の動作A47直後の単語状態値スタックの状態である。
【０１４８】
次いで動作は再び動作A10に戻る。ここでの動作の出発点は前回の動作で次回の単語状態値として指定されたパラメター(1)、(2)、(3)、(4)の値がそれぞれ４、１、５、Fの状態である。パラメター(1)値である現在の単語束番号値が４であり、単語束数は７であるのでここでの判断はnoであり動作は動作A11に移る。次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。この例の場合は前者が５であり後者が７であるので不成立であり次の動作は動作A12である。
【０１４９】
動作A12ではパラメター(1)、(2)値それぞれ４、１であるところから、図１７(a)の合致条件配列の第４列第１行の要素$が抽出されパラメター(6)の文例単語として上書きされる。次の動作A13ではパラメター(4)の値がFであるので判定はnoであり、次動作は動作A22である。文例単語は*でないので動作A22の判定はnoであり、次の動作は動作A24である。文例単語は任意の１つの抽出用単語列単語に合致することを指定する$であるのでここでの判定はyesであり動作は動作A25に移行する。
【０１５０】
動作A22およびその後に続く動作A24、A26は文例単語がそれぞれ*、$、-であるか否かの判定をする。これらがyesの判定を発生する場合は現在の抽出用単語列単語を参照せずに文例単語と抽出用単語列単語間の合致が成立すると判定し合致発生後の動作であるそれぞれ動作A23、動作A25、動作A27を開始する。
【０１５１】
動作A25ではパラメター(1)の単語束番号としては現在の単語束番号に１を加えた値が指定され、またパラメター(2)の単語番号としては、次の単語束番号の単語束が持つ単語の１番目のものを取り扱うために値１が指定される。またパラメター(3)の抽出用単語列単語番号としては現在の抽出用単語列単語番号に１を加えた値が指定される。またパラメター(4)の先行単語束*標識の値としてFが導入される。ここでの動作は合致条件側、抽出用単語列側双方の単語の番号を１つ進める操作である。ここで発生するパラメター(1)、(2)、(3)、(4)値はそれぞれ５、１、６、Fである。
【０１５２】
次いで動作A46にて現在の合致文例群抽出部E9の動作状態を示す単語状態値を「単語状態値スタック」にプッシュする。この例の場合パラメター(1)、(2)、(3)、(4)、(5)の値はそれぞれ、４、１、５、F、-であるのでこの値がプッシュされる。図１８(d)が現在の動作A46直後の単語状態値スタックの状態である。
【０１５３】
次いで動作は再び動作A10に戻る。ここでの動作の出発点は前回の動作で次回の単語状態値として指定されたパラメター(1)、(2)、(3)、(4)の値がそれぞれ５、１、６、Fの状態である。パラメター(1)値である現在の単語束番号値が５であり、単語束数は７であるのでここでの判断はnoであり動作は動作A11に移る。次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。この例の場合は前者が６であり後者が７であるので不成立であり次の動作は動作A12である。
【０１５４】
動作A12ではパラメター(1)、(2)値それぞれ５、１であるところから、図１７(a)の合致条件配列の第５列第１行の要素aboutが抽出されパラメター(6)の文例単語として上書きされる。次の動作A13ではパラメター(4)の値がFであるので判定はnoであり、次動作は動作A22である。動作A22、A24、A26は文例単語がそれぞれ*、$、-であるかどうかの判定を行う。ここでの場合は文例単語がaboutあり、これらの記号でないのでこれらの動作を判定noで通過し動作A28に至る。
【０１５５】
動作A28は動作A14と同じ動作を行う部分であり、パラメター(1)と(2)よりパラメター(6)の文例単語を抽出し、パラメター(3)を用いてパラメター(7)の抽出用単語列単語を抽出し以前の値に上書きする部分である。この例の場合は文例単語の値はaboutであり、抽出用単語列単語の値はabout(P)である。
【０１５６】
次の動作のA29は動作A15と同じ動作を行う部分であり、文例単語の値と抽出用単語列単語の値の比較を行う。ここでの例の場合は単語に関する一致が生じるので一致の判定が行われ、次の動作は動作A34である。
【０１５７】
動作A34は動作A25と全く同一の動作を行う。すなわちパラメター(1)の単語束番号としては現在の単語束番号に１を加えた値が指定され、またパラメター(2)の単語番号としては、次の単語束番号の単語束が持つ単語の１番目のものを取り扱うために値１が指定される。またパラメター(3)の抽出用単語列単語番号としては現在の抽出用単語列単語番号に１を加えた値が指定される。またパラメター(4)の先行単語束*標識の値としてFが導入される。ここでの動作は合致条件側、抽出用単語列側双方の単語の番号を１つ進める操作である。ここで発生するパラメター(1)、(2)、(3)、(4)値はそれぞれ６、１、７、Fである。
【０１５８】
次いで動作A47にて現在の合致文例群抽出部の動作状態を示す単語状態値を「単語状態値スタック」にプッシュする。この例の場合パラメター(1)、(2)、(3)、(4)の値はそれぞれ、５、１、６、F、5であるのでこの値がプッシュされる。図１８(e)が現在の動作A47直後の単語状態値スタックの状態である。
【０１５９】
次いで動作は再び動作A10に戻る。ここでの動作の出発点は前回の動作で次回の単語状態値として指定されたパラメター(1)、(2)、(3)、(4)の値がそれぞれ６、１、７、Fの状態である。パラメター(1)値である現在の単語束番号値が６であり、単語束数は７であるのでここでの判断はnoであり動作は動作A11に移る。次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。この例の場合は前者が７であり後者が７であるので不等式は不成立であり次の動作は動作A12である。
【０１６０】
動作A12ではパラメター(1)、(2)値それぞれ６、１であるところから、図１７(a)の合致条件配列の第５列第１行の要素(N)が抽出されパラメター(6)の文例単語として上書きされる。次の動作A13ではパラメター(4)の値がFであるので判定はnoであり、次動作は動作A22である。動作A22、A24、A26は文例単語がそれぞれ*、$、-であるかどうかの判定を行う。ここでの場合は文例単語が(N)あり、これらの記号でないのでこれらの動作を判定noで通過し動作A28に至る。
【０１６１】
動作A28はパラメター(1)と(2)よりパラメター(6)の文例単語を抽出し、パラメター(3)を用いてパラメター(7)の抽出用単語列単語を抽出し以前の値に上書きする部分である。この例の場合は文例単語の値は(N)であり、抽出用単語列単語の値はgame{pl}(N)である。
【０１６２】
次の動作のA29は文例単語の値と抽出用単語列単語の値の比較を行う。ここでの例の場合は括弧に囲まれた品詞(N)に関する一致が生じるので一致の判定が行われ、次の動作は動作A34である。
【０１６３】
動作A34はパラメター(1)の単語束番号としては現在の単語束番号に１を加えた値が指定され、またパラメター(2)の単語番号としては、次の単語束番号の単語束が持つ単語の１番目のものを取り扱うために値１が指定される。またパラメター(3)の抽出用単語列単語番号としては現在の抽出用単語列単語番号に１を加えた値が指定される。またパラメター(4)の先行単語束*標識の値としてFが導入される。ここで発生するパラメター(1)、(2)、(3)、(4)値はそれぞれ７、１、８、Fである。
【０１６４】
次いで動作A47にて現在の合致文例群抽出部E9の動作状態を示す単語状態値を「単語状態値スタック」にプッシュする。この例の場合パラメター(1)、(2)、(3)、(4)、(5)の値はそれぞれ、６、１、７、F、6であるのでこの値がプッシュされる。図１８(f)が現在の動作A47直後の単語状態値スタックの状態である。
【０１６５】
次いで動作は再び動作A10に戻る。ここでの動作の出発点は前回の動作で次回の単語状態値として指定されたパラメター(1)、(2)、(3)、(4)の値がそれぞれ７、１、８、Fの状態である。パラメター(1)値である現在の単語束番号値が７であり、単語束数は７であるので不等式は成立せず、ここでの判断はnoであり動作は動作A11に移る。次の動作A11は現在取り扱い中の抽出用単語列の単語の番号が抽出用単語列単語数より大きいかどうかの判定を行う。この例の場合は前者が８であり後者が７であるので不等式は成立し合致失敗が発生するので動作はバックトラックの動作である動作A36に移る。ここでの合致失敗は合致条件中に未処理の単語束がある内に抽出用単語列が尽きてしまうことにより発生する。
【０１６６】
動作A36では単語状態値スタックに単語状態値が存在するかどうかを調べる。単語状態値スタック中の単語状態は以前の合致文例群抽出部E9の状態であるので、この状態が存在しなければバックトラックが不可能であるのでこの調査は必要である。図１８(f)に示されるように単語状態値が存在するので動作A36の判定は存在であり動作A37に移行する。
【０１６７】
動作A37では単語状態値スタックに最後にプッシュされた単語状態値であるパラメター(1)、(2)、(3)、(4)、(5)の値がそれぞれ、６、１、７、F、6の単語状態値がポップし、以後は合致文例群抽出部E9の状態がこの単語状態値が指示する状態に戻ることになる。この動作以後の単語状態値スタックの内容は図１８(g)のようになる。
【０１６８】
動作A38にてパラメター(1)の値６とパラメター(2)の値１よりパラメター(5)の文例単語(N)を再び抽出する。現在のパラメター(4)の値がFであるので動作A39の判定はnoであり、また文例単語が(N)であるので動作A40の判定もnoであり動作は動作A30に移行する。ここではパラメター(1)の値６と図１７(c)の単語束配列によりパラメター(7)の値である単語束の単語数の値を２に更新する。
【０１６９】
動作A31ではパラメター(2)の現在の単語番号１がパラメター(8)の単語束の単語数２より小さいので成立の判定が発生し動作A32によりパラメター(2)の値が１増加して２となる。動作A33に於いてパラメター(1)の値６とパラメター(2)の値２より、図１９(a)の合致条件配列の第６列第２行の要素である空要素-がパラメター(6)の文例単語の値となる。文例単語の値が空要素-であるところから動作A26はyesの判定を発生し動作は動作A27に移行する。
【０１７０】
動作A27では、次回の動作状態の値として１つ増加した単語束の番号と現在と同じ抽出用単語列単語番号を発生する。このことは動作A27が現在の単語束に対応する抽出用単語列単語が無いことを指定する動作を行うことを意味する。動作A27の動作は空記号-の機能を具体化する動作である。この結果次回の単語状態値のパラメター(1)、(2)、(3)、(4)の値がそれぞれ、７、１、７、Fとなる。次いで動作は動作A46に移行しパラメター(1)、(2)、(3)、(4)の値がそれぞれ、６、２、７、F、-である現在の単語状態値の値を単語状態値スタックにプッシュする。動作A46の後の単語状態値スタックの内容を図１８(h)に示す。
【０１７１】
動作は再び動作A10に戻る。この際のパラメター(1)、(2)、(3)、(4)の値はそれぞれ、７、１、７、Fである。現在の単語束番号はパラメター(1)値７であり、パラメター(9)値単語束番号は７であるので不等式は成立せず判定はnoであり動作は動作A11に移行する。ここでは、現在の抽出用単語列単語番号はパラメター(3)値７であり、抽出用単語列単語数は図１９(e)に示されるように７であるので判定は不成立であり動作A12に移行する。
【０１７２】
パラメター(1)、(2)の値がそれぞれ７、１であるところから動作A12では文例単語としてskiingが発生する。その後動作A13、動作A22、動作A24、動作A26を経由して動作は動作A28に移行する。ここではパラメター(1)、(2)、(3)より文例単語skiing、抽出用単語列単語game{pl}(N)が発生する。動作A29に於ける比較判定は不一致であり動作は動作A30に移る。パラメター(1)より単語束の単語数は２、単語番号は１であるところから動作A31の判定は成立であり動作A32に移行する。
【０１７３】
ここではパラメター(2)の単語数を２に増加させ、動作A33により文例単語を(N)に更新する。その後動作A26を経て動作A28に戻る。ここではパラメター(1)、(2)、(3)の値をもとに文例単語(N)と抽出用単語列単語game{pl}(N)を発生する。これらの品詞が一致するところから動作A29一致の判定を発生する。
【０１７４】
動作A34により次回のパラメター(1)、(2)、(3)、(4)の値としてそれぞれ８、１、８、Fが発生しまた動作A47によりパラメター(1)、(2)、(3)、(4)の値としてそれぞれ７、２、７、F、7を持つ今回の単語状態値を単語状態値スタックにプッシュする。このプッシュ後の単語状態値スタックの値を図１８(i)に示す。
【０１７５】
次いで状態は動作A10に移行する。現在のパラメター(1)値の文例単語束番号は８であり、図１６(d)に示す単語束数は７であるので判定はyesであり動作は動作A41に移る。動作A10は合致条件中の全ての単語束の処理が成功裏に終了したことを検出する動作であり、これがyesの判定を発生することは抽出用単語列と文例の合致条件の合致が発生することを意味する。このような合致条件を持つ文例を適用文例に指定する。
【０１７６】
動作A41では適用文例に指定された現在の文例を合致文例スタックに導入する動作である。現在の文例は図１１の形式を持つがこれ全体を合致文例スタックに導入する。続いて動作A42に移る。これは現在取り扱い中の文例の他に文例があるかどうかの判定を行う動作である。ここでは文例が図１１以外に無いのでここの判定はnoであり動作は動作43の合致文例スタックに値が存在するかどうかの判定に移る。ここでは直前にこのスタックに導入した図１１の文例が存在するので動作は動作A34に移り合致文例が存在することを示すフラッグとともに合致文例を図９に示す規則分離部E10に出力して、この合致文例群抽出部E9の動作を終了する。
【０１７７】
なお未処理の文例が存在する場合は動作A42で存在の判定が発生し、動作は動作A5の文例の取り出しに戻り、その文例に対しこれまでに述べたと同様な処理を行う。
【０１７８】
次に図１１(a)またはこれの配列化結果である図１７(a)が表現する合致条件に於いて合致が失敗する場合の合致文例群抽出部E9動作を調べてみる。この場合の合致条件、合致条件配列は図１９(a)に示されるこれまでの例のものであるとし、抽出用単語列および抽出用単語列配列は図１９(b)のものであるとする。この単語配列は図１７(b)に於いてabout(P)とgame{pl}(N)の間にgood(ADJ)を挿入することにより発生するものであり、合致条件と抽出用単語列は合致しないことが観察される例である。但しADJは形容詞の品詞を表現する。動作はこれまでと同様な部分が終了する第６番目の単語束に対する処理を開始する動作A10の記述より開始する。なおこの時点までに単語状態値スタックには図２０(a)の単語状態値がプッシュされており、次回の単語状態値としてパラメター(1)、(2)、(3)、(4)の値それぞれ６、１、７、Fのものを保持している。
【０１７９】
動作A10では現在のパラメター(1)で示される単語束番号は６であり、パラメター(9)の単語束数は図１９(a)、(d)に見られる７であるところからnoの判定が発生し、動作は動作A11に移る。ここでは、現在の抽出用単語列単語番号はパラメター(3)値７であり、抽出用単語列単語数は図１９(b)、(e)に示されるように８であるので判定は不成立であり動作A12に移行する。
【０１８０】
ここでは現在のパラメター(1)単語束番号と同パラメター(2)単語番号が６と１であるところから、図１９(a)の合致条件配列の第６列、第１行の要素(N)が文例単語として抽出、上書きされる。次いで先行単語束が*でなく、また文例単語が*、$、-のいずれでもないので動作A13、A22、A24、A26の判定は全てnoであり、動作は動作A28に移行する。
【０１８１】
動作A28はパラメター(1)と(2)よりパラメター(6)の文例単語を抽出し、パラメター(3)を用いてパラメター(7)の抽出用単語列単語を抽出し以前の値に上書きする部分である。この例の場合は文例単語の値は(N)であり、抽出用単語列単語の値はgood(ADJ)である。次の動作A29では合致条件側、抽出用単語列単語の単語、品詞双方が異なるので不一致の判定が発生し動作は動作A30に移る。
【０１８２】
動作A30ではパラメター(1)の値６と図１９(c)の単語束配列によりパラメター(8)の値である単語束の単語数の値を２に更新する。
【０１８３】
動作A31ではパラメター(2)の現在の単語番号１がパラメター(8)の単語束の単語数２より小さいので成立の判定が発生し動作A32によりパラメター(2)の値が１増加して２となる。動作A33に於いてパラメター(1)の値６とパラメター(2)の値２より、図１９(a)の合致条件配列の第６列第２行の要素である空要素-がパラメター(6)のある文例単語の値となる。文例単語の値が空要素-であるところから動作A26はyesの判定を発生し動作は動作A27に移行する。
【０１８４】
動作A27では、次回の動作状態の値として１つ増加した単語束の番号と現在と同じ抽出用単語列単語番号を発生する。この結果次回の単語状態値のパラメター(1)、(2)、(3)、(4)の値がそれぞれ、７、１、７、Fとなる。次いで動作は動作A46に移行しパラメター(1)、(2)、(3)、(4)、(5)の値がそれぞれ、６、２、７、F、-である現在の単語状態値の値を単語状態値スタックにプッシュする。動作A46の後の単語状態値スタックの内容を図２０(b)に示す。
【０１８５】
動作は再び動作A10に戻る。現在の単語束番号はパラメター(1)値７であり、パラメター(9)値単語束番号は７であるので判定はnoであり動作は動作A11に移行する。ここでは、現在の抽出用単語列単語番号はパラメター(3)値７であり、抽出用単語列単語数は図１９(e)に示されるように８であるので判定は不成立であり動作A12に移行する。
【０１８６】
パラメター(1)、(2)の値がそれぞれ７、１であるところから動作A12では文例単語としてskiingが発生する。その後動作A13、動作A22、動作A24、動作A26を経由して動作は動作A28に移行する。ここではパラメター(1)、(2)、(3)より文例単語skiing、抽出用単語列単語good(ADJ)が発生する。動作A29に於ける比較判定は不一致であり動作は動作A30に移る。パラメター(1)より単語束の単語数は２、単語番号は１であるところから動作A31の判定は成立であり動作A32に移行する。
【０１８７】
ここではパラメター(2)の単語数を２に増加させ、動作A33により文例単語を(N)に更新する。その後動作A26を経て動作A28に戻る。ここではパラメター(1)、(2)、(3)の値をもとに文例単語(N)と抽出用単語列単語good(ADJ)を発生する。ここでは単語、品詞とも一致が発生しないので動作A29は不一致の判定を発生し動作はまた動作A30に戻る。現在単語束の単語数は２、単語番号は２であるので動作A31の判定は不成立である。このことは今回のすなわち第７番目の単語束に対する合致条件と抽出用単語列の合致が失敗したことを意味する。
【０１８８】
動作はバックトラックに入り単語状態値スタックの内容の存在の調査をする。図２０(b)に示すように単語状態値が存在するので動作A36の判定は存在であり、最後に導入されたパラメター(1)、(2)、(3)、(4)がそれぞれ６、２、７、F、-の値を持つ単語状態値がポップされる。ポップ後の単語状態値スタックの内容は図２０(c)となる。パラメター(1)、(2)から動作A38により文例単語-が発生する。動作A39、動作A40がnoの判定を発生した後動作A30に移る。現在の単語束番号が６であるので動作A30により図１９(a)の合致条件配列から単語束の単語数値２を得る。この値は現在のパラメター(2)値２である単語番号と同じであるので動作A31の判定は不成立である。
【０１８９】
この場合はさらにバックトラックが深くなり、ふたたび動作A36に戻る。ここでは図２５(c)に於いて最後に導入された単語状態値がポップする。ポップアップされたパラメター(1)、(2)、(3)、(4)、(5)値はそれぞれ５、１、６、F、5であり、ポップアップ後の単語状態値スタックの内容は図２０(d)となる。
【０１９０】
以後動作A29、A15に於いて合致条件側の単語と抽出用単語列側の単語の合致が発生しないまま動作A37に於ける単語状態値のポップアップが続き、最後に単語状態スタックの内容が図２５(e)の状態で動作A36に動作が移る。ここでの判定は存在であり図２０(e)に於いて最後に存在した単語状態値がポップする。この場合のパラメター(1)、(2)、(3)、(4)値はそれぞれ１、１、２、T、1であり、この状態のポップアップの後は単語状態値スタックは空となる。この場合はパラメター(4)の値は先行単語束が*であることを示すTであるので動作は動作A17に移る。
【０１９１】
ここでは単語束番号が１であるので図１９(a)の合致条件配列より単語束の単語数の値１を得る。現在の単語番号がパラメター(2)の値１であるので動作A18は不成立であり動作は動作A20に移る。現在のパラメター(3)の抽出用単語列単語番号は２であり抽出用単語列単語数は図１９(e)に示されるように７であるのでここでの判定は成立であり動作A21に移行する。ここではパラメター(1)、(2)、(3)値をそれぞれ１、１、３として与え、パラメター(4)の値はTのままとして動作A14に動作を移す。
【０１９２】
その後動作A15に於いて合致条件側の単語と抽出用単語列側の単語の合致が発生しないまま動作A20を含むループを経由しながらパラメター(3)値のみを増加させる演算が続いたのち、パラメター(1)、(2)、(3)、(4)の値としてそれぞれ１、１、８、Tの単語状態値を伴って動作A20に移行する。抽出用単語列単語数は８でありパラメター(3)値も８であるのでここでの判定は不成立であり動作A36に移行する。今回は単語状態値スタックが空であるので動作は動作A42に移行する。今回の場合は文例が図１１のもの一つだけであるので動作は動作A43に移る。今回は状態A41を通過せず、合致文例が無いので動作A44に移り動作A45により合致文例群抽出部E9は動作合致文例が無いことを示すフラッグを発生して、本合致文例群抽出部E9の動作を終了する。
【０１９３】
以上詳細に説明したように図１６に示すフローグラフの動作を用いることにより、文例が持つ合致条件と入力文に由来する抽出用単語列との合致判定が可能となる。この合致判定は(a)項および(b)項として示した合致の条件を満足するものである。合致条件は複数の単語を含む単語束の列として記述するため、各単語位置に於いて一般に複数の可能性が記述できる。また文例と抽出用単語列の合致条件は、任意数の任意の単語に合致することを示す記号*、任意の１単語に合致することを示す記号$、対応する単語が無いことを示す空記号-を含むものである。
【０１９４】
図１６が含む動作に於いて、配列の記述およびこれに対する情報の書き込み、読み出しは通常の計算機言語が持つ配列の機能をそのまま用いることができる。また単語状態値スタックの記述に必要なスタックに対するプッシュおよびポップの機能はLisp言語に備わっているリストに対するプッシュならびにポップ機能をそのまま用いることができる。また単語の一致はどの計算機言語にも備わっている文字列の比較機能を用いることができる。また図１６が含む動作に多く存在する判定機能は通常の計算機言語がもついわゆるif-then-elseの判定機能をそのまま用いることができる。以上述べたように図１６が持つ文例が保有する合致条件と抽出用単語列の合致を判定し合致と判定された文例を蓄積する作用は通常の計算機を用いて、また通常の計算機言語を用いて「論理的実体」として構成することが可能である。
【０１９５】
なお、ここでは入力文として英語文を用いたが、他の言語でも状況は全く同じである。ただし、日本語、中国語のようにべた書きされる言語の場合、図１のR1や図９のE1の部分である形態素解析部で単語の切り出しを行う必要がある。これに関する技術は従来技術に属し、本発明の範囲外である。単語切り出しに関する説明は「榊博史著；コンピュータ翻訳技術；電子情報通信学会；平成５年刊」の第１１章に示されている。
【０１９６】
図２１に於いてB0は初期OR木入力動作、B1はOR木メモリ導入動作、B2は演算データ導入動作、B3は最上位節点一致判定動作、B4は調査メモリ空判定動作、B6は排他木被覆実行動作、B7は被覆木保存動作、B8は処理対象対取り出し動作、B9は入力文側子節点存在判定動作、B10は規則側子節点存在判定動作、B11は節点対応付け動作、B12は半構成節点判定動作、B13は上位排他木境界決定動作、B14は被覆失敗動作、B15は規則側子節点存在判定動作、B16は節点対応付け動作、B17は下位構造存在判定動作、B19はOR木準備動作、B20はOR節点検出動作、B21は並列分解動作、B22は一致構造存在判定動作、B23は半構成節点判定動作、B24は上位排他木境界決定動作、B25は下位構造存在判定動作、B27はOR木準備動作、B28は処理対象収容動作、B29は排他木発生完了動作、B30は被覆結果収容動作、B31はOR木存在判定動作、B32は前段終了動作、B33は排他木取り出し動作、B34は被覆セット取り出し動作、B35は下位接続判定動作、B36は被覆セット戻し動作、B37は節点融合動作、B38は配列構成動作、B39は被覆セット転換動作、B40は最大木値木発生動作、B41は被覆セット存在判定動作、B42は後段終了動作、B43はフィルタリング終了動作である。
【０１９７】
図２１は図２１aと図２１bの２つの部分図から成り立っている。図２１中Y1〜Y4として示す点はこれら部分図の間の接続関係を示す接続点でありそれぞれの点自身は機能を持たない。部分図の一方に於ける接続点にはその接続点に接続する部分図の他の一方に於ける動作の見出し語が接続している。例えば接続点Y1は図２１b中の動作B4に接続しており、このことが図２１aに於ける接続点Y1に接続する見出し語B4で示されている。
【０１９８】
ここでは図２１に示した上位排他フィルタリング部E3動作フローチャートに従って上位排他フィルタリング部E3の説明を行って行く。このフローチャートに於いて図２１aの右下隅のFOBと記した禁止木適用部E32およびSUBと記した副上位排他相対フィルタリング部E33を除く全ての部分が主上位排他相対フィルタリング部E31のフローチャートである。以下主上位排他相対フィルタリング部E31の動作を説明する。このため、図２１の動作B38より動作B40に動作が移行する場合について説明し動作B38よりFOBと記した禁止木適用部E32を経て動作B40に至る動作については後述する。
【０１９９】
図２２は上位排他相対フィルタリング部E31に於ける取り扱いデータを示す。
【０２００】
図２３は同じく図２１の大部分を占める主上位排他相対フィルタリング部E31のフローチャート動作により生起するメモリ間のデータの流れである。図２３に於いて矩形の部分はメモリまたはレジスタであり、角の丸い部分がデータ処理が行われるハードウエアを示す。また図中の(a)〜(f)はその場所に図２２の同一文字の部分図の形式のデータが存在することを示す。
【０２０１】
図２３に於いてD1はOR木メモリ、D2は排他木レジスタ、D3は調査メモリ、D4は保存メモリ、D5は境界節点メモリ、D6は接続メモリ、D7はOR木準備メモリ、D8は境界節点対スコア対照表、D9は被覆セットメモリ、D10は被覆可否決定演算部、D11は排他木被覆実行演算部、D12は前段メモリ、D13は接続動作部、D14は上位被覆下位最大木値状態メモリ、D15は禁止木適用演算部、D16は最大木値メモリである。
【０２０２】
まずこのメモリ間の信号の流れについて説明する。初期OR木として図２２(a)形式のOR節点による複数の代替木の表現を含みうる解析木すなわちOR木が主上位排他相対フィルタリング部E31に導入される。これがOR木メモリD1に導入され、さらに被覆可否決定演算を受ける。被覆可否決定演算ではここに入力するOR木が排他木レジスタD2より保存メモリD4を経て入力する複数の排他木のそれぞれに被覆されるかどうかを決定する。前記排他木はそれに関する処理が行われている間保存メモリD4に保存される。保存メモリD4は被覆演算のために変形されていく排他木の原形を保存するメモリであることから名付けられた。
【０２０３】
本特許では被覆可否決定演算部D10、排他木被覆実行演算部D11等で排他木または上位排他木を簡単のため（１側）と称し、OR木を（２側）と称する。
【０２０４】
被覆可否決定演算部D10では「調査メモリD3」に被覆可否判定の対象であり「処理対象対」と呼ぶ（１側）と（２側）の対を収容する。このため調査メモリD3と被覆可否決定演算部D10との間にデータのやりとりがある。上位排他木または排他木による被覆は排他木の最上位節点を含む部分木がOR木が代表する一般に複数の展開木の最上位節点を含む部分木と一致すると成功する。
【０２０５】
前述したように、この時OR木を被覆する上位排他木または排他木を「被覆排他木」と呼ぶ。OR木が代表する木の１つの最上節点を含む部分が被覆排他木により被覆され、被覆排他木の下位の部分にOR木の部分木が残存する形式の構造を「被覆状態」と呼ぶ。被覆状態に於いて被覆排他木と下位のOR木の部分木を切り離した後の被覆排他木もやはり被覆排他木と呼ぶ。
【０２０６】
１つのOR木は一般に複数の被覆排他木により被覆可能であるので、複数の被覆状態が発生し複数の被覆排他木が発生する。これら１つのOR木に対する被覆により発生する被覆排他木の集合を被覆セットと呼ぶ。
【０２０７】
被覆可否決定演算部D10では被覆が成功すると、上位排他木または排他木の最上位節点の番号とOR節点の番号の対照情報ならびに上位排他木または排他木の葉節点の番号と被覆排他木に被覆されないOR木の部分木の最上位節点番号の対照情報である「1-2対照対」を「接続メモリ」D6中に導入する。また上位排他木にて被覆する場合、排他木と異なり不定である上位排他木の境界の情報を「境界節点メモリ」D5に収容する。
【０２０８】
被覆可否決定演算部D10では被覆が成功すると被覆されないOR木の部分木を「OR木メモリD1」に導入する。被覆が成功しない間はOR木メモリD1に入れることができないので「OR木準備メモリ」D7に一時保管し被覆が失敗に終わると削除する。被覆されないOR木の部分木は以後初期OR木と同様な取り扱い、すなわち上位排他木または排他木による被覆の対象となる。
【０２０９】
排他木被覆実行演算部D11は被覆状態の構成を行う。被覆可否決定演算部D10により被覆排他木がOR木を被覆可能であることが判明しているので、被覆状態の構成は1-2対照対の情報にもとづき被覆排他木の最上位節点と葉節点にそれに接続するOR木の部分木の最上位節点の節点番号を属性として付加することにより行われる。この節点番号を「接続情報」と呼ぶ。その後この被覆排他木を被覆セットに加えるために被覆セットメモリD9に導入する。１つのOR木に対する全ての上位排他木または排他木による被覆の試みが終わった後被覆セットの内容は１つのセットとしてまとまった形で「前段メモリ」D12というメモリに導入される。このまとまりを「被覆セット」と呼ぶ。
【０２１０】
排他木被覆実行演算部D11はまた境界節点メモリD5の情報により上位排他木の被覆境界を確定し、また境界節点対スコア対照表D8により上位排他木のスコアを決める。
【０２１１】
図２２(a)のHとして示されたものはOR木である。図２２(b)はこのOR木に対する２つの被覆状態を示す。図２２(b)に於けるP1、P2は被覆セットを構成する２つの被覆排他木である。またこの場合の被覆セットは図２２(c)に示すものである。
【０２１２】
また図２２(b)の被覆状態に於いて被覆排他木より下位で被覆されずOR木メモリD1に導入されるOR木の部分木は図２２(d)に示す。
【０２１３】
被覆セットメモリD9は１つの排他木に関する被覆状態を被覆セットにまとめて保存する働きがあったが前段メモリD12は多くの種類のOR木、例えば図２２(d)に示したもの等に対する被覆セットを保持する。以上が前段動作の説明である。以下に後段動作の説明を行う。
【０２１４】
その後段動作に属する接続動作部D13は下位の最大木値木を上位の被覆排他木に被覆排他木の葉節点が持つ下位の節点番号に基づいて接続して「上位被覆下位最大木値状態」を構成する動作を行うハードウエアである。この動作は１つの被覆セットに属する被覆排他木を１つのセットとして行うので、この動作の結果１つの入力OR木に対する「上位被覆下位最大木値セット」が得られる。これをそれが持つ「木値」順に配列することにより「上位被覆下位最大木値配列」を得ることができる。木値は被覆排他木のスコアと下位に接続される最大木値木のスコアの和として得られる。これの先頭のものを選ぶことにより、入力OR木に対する最大木値木を得ることができる。図２２(e)が上位被覆下位最大木値配列、図２２(f)が最大木値木である。ただしここではX1+X3+X4>X2+X5+X6であるとする。
【０２１５】
この接続動作の出発点となる動作が１つの上位排他木または排他木にその全体を被覆されるOR木に対する被覆状態である。この場合は前段動作で得られる被覆状態は被覆排他木のみから構成される。この場合は被覆排他木はそのままで「上位被覆下位最大木値状態」となる結果、被覆排他木の集まりである被覆セットはそのままで「上位被覆下位最大木値セット」となる。これを木値順に配列することにより「上位被覆下位最大木値配列」を得る。その後その先頭の構造を抽出することにより、最大木値木が得られる。
【０２１６】
図２２(g)はこの状態を示すものであり、矢印で区切られた項目に於いて左端が処理対象となるOR木、中央が上位被覆下位最大木値配列、右端が最大木値木である。ただしh3max>h31であるとする。
【０２１７】
以後、図２３のデータの流れを発生する図２１の主上位排他相対フィルタリング部E31のフローチャートに沿って動作を説明する。
【０２１８】
図２４(d)の解析結果は図１３で与えられる文例駆動型フィルタリング解析方式の書き換え規則適用部E2出力例である。以後この例を入力OR木とする主上位排他相対フィルタリング部E31の動作の説明を行う。
【０２１９】
動作B0にてまずOR木メモリD1をリセットした後図２４(d)の初期OR木をOR木メモリD1に導入し、直後にOR木メモリD1より取り出しここでの処理対象とすることにより主上位排他相対フィルタリング部E31動作を開始する。動作B2にて排他木レジスタD2中の内蔵排他木メモリの最初に記録されている図２４(a)の上位排他木を保存メモリD4に導入する。
【０２２０】
排他木レジスタD2はスキャニングを行い記録されている上位排他木または排他木を順次出力する。ここでは図２４(a)の上位排他木、図２４(b-a)から(b-h)の一般的排他木、図２４(c-a)から(c-j)の単語排他木の順に記録されている。このためその先頭の図２４(a)の上位排他木がここで発生したわけである。動作B2ではさらに保存メモリD4に収容中の上位排他木の最上位節点に付属する属性の「OR木欄」に現在処理中のOR木を導入する。ここでは最上位節点CLに図２４(d)の初期OR木を導入する。この情報は図２１中の上位排他相対フィルタリング部に必要ではないが本特許の範囲外であり、図２１のフローグラフ中のFOBとして示した禁止木適用部E32に於いて必要である。
【０２２１】
保存メモリD4収容中の上位排他木または排他木の最上位節点に付属する属性として上記「OR木欄」の他に「排他木スコア欄」、「総和スコア欄」の２つの欄が存在する。このうち排他木については排他木のスコアは一定であるので、排他木の保存メモリD4導入時に「排他木スコア欄」が埋められているものとする。図２４(b-a)から(b-h)の一般的排他木、図２４(c-a)から(c-j)の単語排他木の最上位節点に括弧で囲んで付加した値がこれである。
【０２２２】
動作B2ではこれらの動作が終わると、保存メモリD4収容中の上位排他木または排他木と、処理対象となったOR木を対にまとめる。この処置はこの２つの組み合わせを対象として演算が行われるためである。この対を以後「処理対象対」と呼ぶ。記述の簡略化をはかるため処理対象対の成分の、上位排他木または排他木を（１側）と呼び後者、OR木を（２側）と呼ぶ。処理対象対は調査メモリD3に導入される。この時点に於ける調査メモリD3の内容を図２５(a)に示す。このように処理対象対の（１側）を上に（２側）を下にして示す。（２側）の節点番号は書き換え規則適用部E2に於ける統語規則適用時に与えられる。図２５(a)でもわかるように、同一区間、同一構造を支配する節点には同一の番号が割り当てられている。（１側）については保存メモリD4導入時にシステムより自動的に節点番号を与える。図２５(a)の節点記号の後に括弧で囲まれ、（１側）のtを含む番号または（２側）のnを含む番号がこれらである。
【０２２３】
同じく動作B2では（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を「接続メモリ」D6に導入する。これは（１側）の上位排他木または排他木に被覆される部分の最上位部分と対応する（２側）のOR木中の位置を記録する動作である。ここでの場合t1-n1という値が接続メモリに導入される。
【０２２４】
続く動作B3では（１側）と（２側）の最上位節点の比較を行う。これが不一致であれば被覆が不可能であるので動作B14の被覆失敗動作に移行する。最上位節点一致判定動作B3は被覆可否決定部D10にて行われる。この場合は図２５(a)に示す通り両者がCLであるので一致が生じ動作B4に移る。調査メモリD3が空でありyesの判定が発生することは、（１側）と（２側）の一致が最後まで保たれ被覆が成功したことを意味する。ここでは調査メモリD3中に直前に導入した図２５(a)の処理対象対があるためnoの判定が生じ動作B8に移る。
【０２２５】
動作B8により図２５(a)の上側の部分の（１側）と同じく下側の部分の（２側）からなる処理対象対を調査メモリD3より取り出す。これ以後の説明に於いて（１側）または（２側）の最上位節点を（１側）または（２側）の最上位節点、最上位節点の直下位に接続される一般に複数の節点を（１側）または（２側）の子節点と呼ぶ。
【０２２６】
次の動作B9は（２側）の子節点の有無の判定である。ここではnoの判定が発生し動作は動作B15に移る。動作B15は（１側）の子節点の有無の判定である。ここではnoの判定が発生し動作は動作B20に移る。動作B20は（１側）、（２側）の子節点が特別な節点であるOR節点であることの判定である。ここではnoの判定が生じ動作が動作B22に移る。
【０２２７】
動作B22は（１側）と（２側）の子節点が順序を含めて一致するかどうかの判定である。図２５(a)の上側である（１側）と同下側である（２側）の子節点は双方ともTHERE BE NPがこの順に並んだものであり一致するので判定はyesであり、動作B28に移行する。
【０２２８】
この時点で（１側）と（２側）の同一順番の子節点以下の構造をそれぞれ対にして調査メモリD3に導入する。この時点に於ける調査メモリD3内容は図２５(b)のようになり、最上位節点の被覆処理が終わり以後は子節点以下の構造の処理に移ることが理解できる。以後はそれぞれの対においてここでの子節点を最上位節点として取り扱う。
【０２２９】
動作は動作B4を経て動作B8に至る。ここでは図２５(b)の左端のTHEREを最上位節点とする処理対象対が取り出される。動作B9、B15、B20をnoで通過し、動作B22をyesで通過し動作B28に至る。ここでは２つの節点Thereのみから成る処理対象対を調査メモリのD3後ろに付加する。結果としてこの時点に於ける調査メモリD3の内容は図２５(b)に於いて左端のTHEREを最上位節点とする処理対象対が削除され右端に単語thereから成る処理対象対が付加されたものとなる。
【０２３０】
動作は動作B4を経て動作B8に至る。ここでは図２５(b)の左から２番目のBEを最上位節点とする処理対象対が取り出される。動作B9、B15をnoで通過し動作B20に至る。（１側）の子節点がOR節点であるので動作は動作B21に移る。
【０２３１】
ここではOR節点でまとめられた（１側）の構造を図２６(a)の上側の部分のように並列構造に分離する。下側に位置する（２側）には変化がない。続く動作B22では（１側）の右側の構造と（２側）の構造の子節点が一致するので、この２つの子節点be{past,sgl}から成る処理対象対を調査メモリD3の後ろに付加する。結果としてこの時点に於ける調査メモリD3の内容は図２５(b)に於いて左端のTHEREを最上位節点とする処理対象対と左から２番目のBEを最上位節点とする処理対象対が削除され右から２番目に単語Thereから成る処理対象対がまた右端に単語be{past,sgl}から成る処理対象対が付加されたものとなる。
【０２３２】
動作は動作B4を経て動作B8に至る。ここでは図２５(b)の右端のNPを最上位節点とする処理対象対が取り出される。動作B9、B15をnoで通過し動作B20に至る。（２側）の子節点がOR節点であるので動作は動作B21に移る。
【０２３３】
ここではOR節点でまとめられた（２側）の構造を図２６(b)の下側の部分のように並列構造に分離する。上側に位置する（１側）には変化がない。続く動作B22では（１側）と（２側）の右端の構造の子節点がDET N P NPと一致するのでyesの判定を発生し動作B28に移る。
【０２３４】
ここでは（１側）と（２側）の同一順番の子節点以下の構造をそれぞれ対にして調査メモリD3に導入する。この時点に於ける調査メモリD3内容は図２６(c)のようになる。
【０２３５】
動作は動作B4を経て動作B8に至る。ここでは図２６(c)の左端の（１側）、（２側）とも単語Thereのみからなる処理対象対が取り出される。動作B9でyesとなり、動作B10もyesの判定を発生し動作B11に至る。ここではt3-n3の1-2対照対が発生して接続メモリD6に導入される。その後動作B4に戻る。これにより単語Thereに関する被覆が完成した結果、図２６(c)の調査メモリD3内容より削除される。動作B4、B8、B9、B11を経由する操作は図２６(c)の左から２つ目の単語be{past,sgl}に関する処理対象対についても施され、動作B11でt6-n5の1-2対照対が接続メモリD6に導入される。その後この処理対象対も調査メモリD3より削除される。
【０２３６】
次の動作B4の後動作B8は、この時点で左端にある図２６(c)中左から３番目の処理対象対を処理するため取り出す。これについての処理は図２５(b)の左から２つ目のBEを最上位節点とする処理対象対を同様な処理であるのでその記述を省略する。ここでも動作B11によりt9-n9の1-2対照対が発生し接続メモリD6に導入される。
【０２３７】
以後図２６(c)の右端の処理対象対の処理に至るまでの処理はこれまで説明した処理と同様であるので省略する。図２６(c)の右端の処理対象対の処理の直前の調査メモリD3の内容は図２７(a)のようになっており動作は動作B4にある。
【０２３８】
次の動作B8にて図２７(a)の左端の処理対象対を抽出し処理対象とする。動作B9、B15、B20を判定noで通過して動作B22に至る。ここでは（１側）と（２側）の子節点が前者はN#１つであり、後者はNが２つ存在する形式であり、異なるため判定noが発生し動作23に至る。
【０２３９】
動作B23では（１側）の子節点以下の部分が全て#の付加された、上位排他木から削除可能な半構成節点であるのでここでの判定はyesであり動作は動作B24に移る。動作B24ではまず（１側）の最上位節点の節点番号を境界節点を記録する「境界節点メモリ」D5に導入する。この場合はt15を導入する。（１側）と（２側）の被覆成功部分の最も下位の部分である（１側）の最上位節点が被覆の境界となるためこれを記録する目的でこの処置を行う。境界節点は上位排他木に於いて排他木として機能する部分の境界を限定する情報である。この意味で排他木、上位排他木双方に於いて被覆境界を指示する1-2対照対とは異なる働きをする。
【０２４０】
同じく動作B24では（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を接続メモリD6に導入する。これはすでに述べたように（１側）の上位排他木または排他木の葉節点に被覆される部分と対応する（２側）のOR木中の位置を記録する動作である。ここでの場合t15-n15という値が接続メモリD6に導入される。
【０２４１】
次いで動作は動作B25に移る。これは現在の（２側）の最上位節点番号と同一の最上位節点番号を持つOR木か、または同一の節点番号がその最上位節点に「接続情報」として付加された「被覆排他木」を持つ「被覆セット」の存在を判定する部分である。このようなものが存在する際には、この最上位節点番号を最上位節点として持つOR木を新たに発生する必要がないのでこの調査が必要である。ここではn15という節点番号を持つOR木または被覆排他木が存在しないのでnoの判定が発生し動作は動作B27に移る。接続情報、被覆排他木、被覆セットについてはその発生に関連して後述する。
【０２４２】
ここではまず以前の動作B21でOR節点でまとめられた木を分解した場合はもとの構造に復元する。その後（２側）の構造を「OR木準備メモリ」D7に導入する。ここでは図２７(a)左端下側の構造をOR木準備メモリD7に導入する。これを図２８に示す。
【０２４３】
その後動作は動作B4に戻り図２７(a)の単語excitement、aboutの処理をするために動作B4、B8、B9、B10、B11を２回経由したのち動作B4に戻る。この過程で動作B11でt12-n11、t14-n14の1-2対照対が発生し接続メモリD6に導入される。この時点で調査メモリD3が空となっているので被覆が成功し、動作B6に至る。すなわち図２４(a)の上位排他木は#が付属した２つの節点を削除することにより図２４(d)のOR木の被覆に成功する。
【０２４４】
動作B6では以前の動作B2にて導入した現在取り扱い中の排他木または上位排他木の原形として保存メモリD4収容中の図２５(a)の上側の構造と同一の構造を処理対象とする。これに対して以下の４つの処理をする。まず動作B24で導入した境界節点メモリD5に存在する境界節点番号を持つ境界節点以下の部分を削除する。ここでは境界節点番号t15より下位の節点であるNとskiingを削除する。次にこの場合の被覆上位排他木のスコアを求める。ここでは被覆上位排他木の節点数倍だけのA値をこの値とする。従ってこの値は13Aとなる。このスコアは一般に複数の境界節点の状態とスコアとの対照表である「境界節点対スコア対照表」D8を各上位排他木毎に用意することにより簡略に得ることができる。
【０２４５】
次に動作B2、動作B24で導入し、接続メモリD6に収容中の1-2対照対を利用して、保存メモリD4が収容する構造に含まれるこの対の左側の節点番号を持つ節点にこの対の右側の節点番号を「接続情報」として付加する動作を行う。これは動作B2、動作B24に関して述べたように（１側）の上位排他木または排他木に被覆される部分と対応する（２側）のOR木中の位置を記録する動作である。接続メモリD6中には、t1-n1、t15-n15、t6-n5、t3-n3、t9-n9、t12-n11、t14-n14の７つの1-2対照対があるので、ここでは保存メモリ中の図２５(a)の上側の形式の上位排他木の節点番号t1、t15、t6、t3、t9、t12、t14を持つ節点にそれぞれn1、n15、n5、n3、n9、n11、n14という番号を付加する。
【０２４６】
動作B6ではこの付加を行い図３０の構造を得る。次にこの番号の付加の行われていない節点の削除をOR節点までを含めて行う。この処理の結果保存メモリD4中には図３１(a)の構造が存在されることとなる。ここでの、t1=n1、t15=n1等の節点番号は上述の接続情報を含んでいる。すなわち等号の右側の部分が接続情報である。
【０２４７】
動作B6ではまた、被覆成功が発生したので、前々動作B27にてOR木準備メモリD7に導入していた図２８の構造をOR木メモリD1に移す。
【０２４８】
なお図３１(a)の最上位節点にはこの被覆上位排他木のスコア13Aが示されている。動作B6から発生する構造は本上位排他フィルタリング部E31の前段の出力となる重要なものである。前述したとおり、ここから発生する構造は入力したOR木を被覆する排他木であるので「被覆排他木」と呼ぶ。
【０２４９】
次の動作B7では保存メモリD4の内容を「被覆セットメモリ」D9に導入する。ここではもちろん図３１(a)の被覆排他木が被覆セットメモリD9に移る。
【０２５０】
ついで動作は動作B29に移り排他木レジスタD2のスキャンの終了の判定に移るが、図２４(b-a)〜(b-h)、(c-a)〜(c-j)のスキャンがまだ終了していないので判定はnoであり動作B33に移り次の排他木を導入する。ここでは上位排他木、排他木が図２４(a)、(b-a)〜(b-h)、(c-a)〜(c-j)の順に排他木レジスタD2に配列されているので次の排他木として図２４(b-a)の排他木が処理対象として導入される。この後動作は動作B2に戻る。図２４(b-a)の最上位節点括弧で囲まれて付加されているGの値は、この排他木の最上位節点CLに付属する属性の「排他木スコア欄」の値を示す。
【０２５１】
現在（１側）の排他木は図２４(a)の上位排他木より同(b-a)の排他木に変わるが（２側）のOR木は未だ図２４(d)の初期OR木のままである。動作B2ではここで導入した排他木の最上位節点CLに付属する属性の「OR木欄」に図２４(d)の初期OR木を導入する。同じく動作B2では（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を接続メモリD6に導入する。ここでの場合t18-n1という値が接続メモリに導入される。
【０２５２】
動作B2ではこの動作が終わると、排他木レジスタD2から発生し、保存メモリD4に保存されている上位排他木または排他木と、処理対象となったOR木を処理対象対にまとめ調査メモリD3に導入する。この時点に於ける調査メモリD3の内容を図２７(b)に示す。これは保存メモリD4導入時にシステムより自動的に与えられた節点番号を含んでいる。
【０２５３】
続く動作B3では（１側）と（２側）の最上位節点の比較を行う。この場合は（１側）、（２側）ともにCLであり一致が生じ動作B4に移る。調査メモリD3中に直前に導入した図２７(b)の処理対象対があるためnoの判定が生じ動作B8に移る。
【０２５４】
動作B8により図２７(b)の上側の部分の（１側）と同じく下側の部分の（２側）からなる処理対象対を調査メモリより取り出す。
【０２５５】
次の動作B9は（２側）の子節点の有無の判定である。ここではnoの判定が発生し動作は動作B15に移る。動作B15は（１側）の子節点の有無の判定である。ここではnoの判定が発生し動作は動作B20に移りnoの判定が生じ動作が動作B22に移る。
【０２５６】
動作B22は（１側）と（２側）の子節点が順序を含めて一致するかどうかの判定である。図２５(a)の上側である（１側）と同下側である（２側）の子節点は双方ともTHERE BE NPがこの順に並んだものであり一致するので判定はyesであり、動作B28に移行する。
【０２５７】
この時点で（１側）と（２側）の同一順番の子節点以下の構造をそれぞれ対にして調査メモリD3に導入する。この時点に於ける調査メモリD3内容は図２９(a)のようになる。以後はそれぞれの対においてここでの子節点を最上位節点として取り扱う。
【０２５８】
動作は動作B4を経て動作B8に至る。ここでは図２９(a)の左端のTHEREを最上位節点とする処理対象対が取り出される。動作B9をnoで通過し動作B15の判定がyesであるので動作B16に移る。ここでは（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を接続メモリに導入する。ここでの場合t19-n2という値が接続メモリD6に導入される。
【０２５９】
次いで動作は動作B17に移る。これは前述した動作B25と同じく現在の（２側）の最上位節点番号と同一の最上位節点番号を持つOR木か、または同一の節点番号が接続情報として付加された最上位節点を持つ被覆排他木を含む被覆セットの存在を判定する部分である。ここではn2という節点番号が付加された最上位節点を持つOR木または被覆排他木の存在の調査を行う。この場合は存在しないのでnoの判定が発生し動作は動作B19に移る。
【０２６０】
ここでは（２側）のOR木をOR木準備メモリD7に導入する。ここでは図２９(a)の左端の処理対象対の下側の構造をOR木準備メモリD7に導入する。これは図３２の上段左より２番目の構造でもある。その後動作B4に戻る。
【０２６１】
現在調査メモリD3には図２９(a)中の２番目および３番目の処理対象対が残っているので判定はnoであり、動作B9を経て動作B15に至りさらに動作B16に至る。ここではt20-n4という1-2対照対の値が接続メモリD6に導入される。
【０２６２】
動作B17をnoで通過した後動作B19に移る。ここでは図２９(a)の左から２番目の処理対象対の下側の構造をOR木準備メモリD7に導入する。現在調査メモリD3には図２９(a)中の３番目の処理対象対が残っているので判定はnoであり、動作B9を経て動作B15に至りさらに動作B16に至る。ここではt21-n6という1-2対照対の値が接続メモリD6に導入される。
【０２６３】
動作B17をnoで通過した後動作B19に移る。ここでは図２９(a)の左から３番目の処理対象対の下側の構造をOR木準備メモリD7に導入する。その後動作B4に移り調査メモリD3が空であるので、今回の排他木の被覆が成功し動作B6に至る。
【０２６４】
動作B6では以前の動作B2にて導入した保存メモリD4収容中の図２７(b)の上側の構造と同一の構造を処理対象とする。ここでは前述した動作B6の４つの動作のうち最後の２つを行う。これは現在処理中の（１側）構造が排他木であり上位排他木でないからである。
【０２６５】
すなわち動作B2、B16で導入し、接続メモリD6に収容中の1-2対照対を利用して、保存メモリD4が収容する構造に含まれるこの対の左側の番号を持つ節点にこの対の右側の番号である接続情報を付加する動作を行う。現在接続メモリD6にはt18-n1、t19-n2、t20-n4、t21-n6の４つの1-2対照対が記録されている。ここでは保存メモリD4中の図２７(d)の上側の形式の排他木の節点番号t18を持つ節点にn1、t19を持つ節点にn2、節点番号t20を持つ節点にn4、節点番号t21を持つ節点にn6という番号を付加する。動作B6の処理の結果保存メモリD4中には図３１(b)の構造が存在することとなる。
【０２６６】
また動作B6では前動作B19でOR木準備メモリD7に導入した図２９(a)にある３つの処理対象対のそれぞれの下側の構造をOR木メモリD1に導入する。
【０２６７】
次の動作B7では保存メモリD4の内容を被覆セットメモリD9に導入する。ここでは図３１(b)の被覆排他木が導入され、結果として被覆セットメモリD9には図３１(a)の被覆排他木と図３１(b)の被覆排他木が存在することになる。
【０２６８】
ついで動作は動作B29に移り排他木レジスタD2のスキャンの終了の判定に移るが、図２４(b-b)〜(b-h)、(c-a)〜(c-j)のスキャンがまだ終了していないので判定はnoであり動作B33に移り次の排他木を導入する次の排他木として図２４(b-b)の排他木が処理対象として導入される。この後動作は動作B2に戻る。
【０２６９】
動作B2ではここで導入した排他木の最上位節点NPに付属する属性の「OR木欄」に図２４(d)の初期OR木を導入する。同じく動作B2では（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を接続メモリD6に導入する。ここでの場合t22-n1という値が接続メモリD6に導入される。
【０２７０】
動作B2ではさらに、排他木レジスタD2から発生している上位排他木または排他木と、処理対象となったOR木を処理対象対にまとめ調査メモリD3に導入する。この時点に於ける調査メモリD3の内容を図２９(b)に示す。これは調査メモリD3、保存メモリD4導入時にシステムより自動的に与えられた節点番号を含んでいる。
【０２７１】
続く動作B3では（１側）と（２側）の最上位節点の比較を行う。この場合は（１側）、（２側）がCLであり（２側）がNPであるので不一致が生じ動作B14を経てB29に移る。
【０２７２】
以後排他木レジスタD2に存在する図２４(b-c)〜(b-h)、(c-a)〜(c-j)の排他木についての処理が動作B14、動作B29、動作B2、動作B3の経路を巡回しながら行われる。いずれの排他木もそれらの最上位節点がCLでないので、これらに対する動作B3の判定はnoである。排他木レジスタ中の最後の排他木に関するB3に於けるnoの判定後動作は動作B14を経て動作B29に移る。
【０２７３】
被覆失敗動作を行うB14では調査メモリD3導入時に上位排他木または排他木に与えた節点番号は「回収」するものとする。従ってこの場合次に上位排他木または排他木に次に与えられる節点番号はt22である。
【０２７４】
動作B29では図２４(d)の初期OR木に対する排他木レジスタD2に存在する全ての上位排他木、排他木による被覆の調査が排他木レジスタスD2のスキャニング終了により完了したので、今回はnoの判定を発生し動作は動作30に移る。
【０２７５】
続くB30では被覆セットメモリD9の内容を１つのセットとして「前段メモリ」D12に導入する。前段メモリD12は本主上位排他相対フィルタリング部E31の前段の結果を入力する部分である。現在被覆セットメモリD9の内容はそれぞれ動作B7により導入された図３１(a)の構造と図３１(b)の構造であり、この順に存在している。これらが１つのセットとして前段メモリD12に導入される。このようなセットをすでに述べたように「被覆セット」と呼ぶ。
【０２７６】
続いて動作は動作B31に移る。現在OR木メモリD1には図３２に示すOR木が収容されている。収容順序は上段左端が最初の位置にあり下段が最後の位置にあるものとする。この内上段左端のものは図２５(a)上側の上位排他木の被覆外のものとして発生したものであり他の３個は図２７(b)上側の排他木の被覆外のものとして発生したものである。判定結果はnoであり動作は動作B1に移る。ここでは図３２の上段左端のOR木が処理対象として入力し動作は動作B2に戻る。
【０２７７】
動作B2は図２４に示した排他木配列の最初のものである図２４(a)の上位排他木（１側）を保存メモリD4に導入する。またここで導入した排他木の最上位節点CLに付属する属性の「OR木欄」に図３２の上段左端のOR木（２側）を導入する。同じく動作B2では（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を接続メモリD6に導入する。ここでの場合t22-n15という値が接続メモリD6に導入される。今後は煩雑にわたるので動作B2で行われる「OR木欄」への（２側）の導入については言及しないこととする。
【０２７８】
その後動作B2では、保存メモリD4中に存在する図２４(a)の上位排他木と、処理対象となった図３２の上段左端のOR木の対を処理対象対にまとめ調査メモリD3に導入する。
【０２７９】
この時点に於ける調査メモリD3の内容である処理対象対を図３３(a)に示す。これは調査メモリD3、保存メモリD4導入時にシステムより自動的に与えられた節点番号を含んでいる。
【０２８０】
この内（２側）については最初のB2動作の際に与えられた番号に変更はないが、（１側）については保存メモリD4に導入毎に異なった節点番号が与えられる。
【０２８１】
続く動作B3では（１側）と（２側）の最上位節点の比較を行う。この場合は（１側）、（２側）がCLであり（２側）がNPであるので不一致が生じ動作B14を経て動作B29に移る。前述したとおり動作B14は（１側）に与えられた節点番号を「回収」する。
【０２８２】
動作B29にて図２４(b-c)の排他木が導入されB2、B3、B14、B29の経路を再び経由し動作B33に至る。動作B33にて次に導入される排他木は図２４(b-b)である。この場合は動作B8を経由し動作B8、B15、B20をnoで通過し動作B22では子節点の並びの不一致が発生し動作B23をnoで通過し被覆失敗の動作B14を経て動作B29に戻る。
【０２８３】
以後の図２４(b-c)の排他木については動作B33、B2、B3、B4、B8、B15、B20、B23、B14の経路で被覆失敗が発生しまた図２４(b-d)の排他木については動作B33、B2、B3、B14の経路で被覆が失敗し動作は動作B29に戻る。
【０２８４】
図２４(b-e)の排他木について動作B2が発生する処理対象対を図３３(b)に示す。もちろん上側の部分は保存メモリD4に導入される。この場合動作B8、B9、B15、B20を判定noで通過する。動作B22の判定がyesであるので動作は動作B28に移る。
【０２８５】
動作B28では（１側）と（２側）の同一順番の子節点以下の構造をそれぞれ対にして調査メモリD3に導入する。この時点に於ける調査メモリD3内容は図３３(c)のようになる。以後はそれぞれの対においてここでの子節点を最上位節点として取り扱う。
【０２８６】
動作は動作B4を経て動作B8に至る。ここでは図３３(c)の左側の処理対象対が取り出される。動作B9をnoで通過し動作B15の判定がyesであるので動作B16に移る。ここでは1-2対照対を接続メモリD6に導入する。この場合t23-n16という値が接続メモリD6に導入される。
【０２８７】
次いで動作は動作B17に移りnoの判定が発生し動作は動作B19に移る。ここでは（２側）のOR木をOR木準備メモリD7に導入する。ここでは図３３(c)の左端の処理対象対の下側の構造をOR木準備メモリD7に導入する。その後動作B4に戻る。
【０２８８】
現在調査メモリD3には図３３(c)中の２番目の処理対象対が残っているので判定はnoであり、動作B9を経て動作B15に至りさらに動作B16に至る。ここではt24-n18という1-2対照対の値が接続メモリD6に導入される。
【０２８９】
動作B17をnoで通過した後動作B19に移る。ここでは図３３(c)の右側の処理対象対の下側の構造をOR木準備メモリD7に導入する。その後動作B4に移り調査メモリが空であるので、今回の排他木の被覆が成功し動作B6に至る。
【０２９０】
動作B6では以前の動作B2にて導入した保存メモリD4収容中の図３３(b)の上側の構造を処理対象とする。ここでは動作B2、B16で導入し、接続メモリD6に収容中の1-2対照対を利用して、保存メモリD6が収容する構造に含まれるこの対の左側の番号を持つ節点にこの対の右側の番号である接続情報を付加する動作を行う。
【０２９１】
現在接続メモリD6にはt22-n15、t23-n16、t24-n18の３つの1-2対照対が記録されている。ここでは保存メモリD4中の図３３(b)の上側の形式の排他木の節点番号t22を持つ節点にn15、t23を持つ節点にn16、t24を持つ節点にn18という節点番号を接続情報として付加する。動作B6の処理の結果保存メモリD4中には図３４(a)の構造が存在することとなる。
【０２９２】
また動作B6では前動作B19でOR木準備メモリD7に導入した図３３(c)の下側２つのOR木をOR木メモリD1に導入する。
【０２９３】
次の動作B7では保存メモリD4の内容である被覆排他木を被覆セットメモリD9に導入する。ここではもちろん図３４(a)の構造が導入される。
【０２９４】
ついで動作は動作B29に移り排他木レジスタD2のスキャンの終了の判定に移るが、図２４(b-f)〜(b-h)、(c-a)〜(c-j)のスキャンがまだ終了していないので判定はnoであり動作B33に移り次の排他木を導入する次の排他木として図２４(b-f)の排他木が処理対象として導入される。この後動作は動作B2に戻る。
【０２９５】
図２４(b-f)〜(b-h)、(c-a)〜(c-j)の全て排他木については動作B33、B2、B3、B4、B8、B15、B20、B23、B14の経路または動作B33、B2、B3、B14の経路で被覆が失敗し動作は動作B29に戻る。
【０２９６】
動作B29では排他木レジスタに存在する全ての上位排他木、排他木に関するスキャニングが終わったので、今回はnoの判定を発生し動作は動作B30に移る。
【０２９７】
続くB30では被覆セットメモリD6の内容を１つのセットとして「前段メモリ」に導入する。前段メモリは主上位排他相対フィルタリング部E31の前段の結果を入力する部分である。現在被覆セットメモリD9の内容は動作B7により導入された図３４(a)の構造であるのでこれ１つを１つのセットとして前段メモリに導入する。
【０２９８】
続いて動作は動作B31に移る。現在OR木メモリD1には図３５に示すOR木が収容されている。収容順序は上段左端が最初の位置にあり下段が最後の位置にあるものとする。この内下段のものが今回の図３３(b)上側の上位排他木の被覆外のものとして発生したものである。判定結果はnoであり動作は動作B1に移る。ここでは図３５の上段左端のOR木が処理対象として入力し動作は動作B2に戻る。
【０２９９】
動作B2は図２４に示した排他木配列の最初のものである図２４(a)の上位排他木を保存メモリD4に導入する。またここで導入した排他木の最上位節点CLに付属する属性の「OR木欄」に図３５の上段左端のOR木を導入する。同じく動作B2では（１側）の最上位節点番号と（２側）の最上位節点番号の対である1-2対照対を接続メモリD6に導入する。ここでの場合t25-n1という値が接続メモリに導入される。
【０３００】
その後動作B2では、排他木レジスタD2から発生している図２４(a)の上位排他木と、処理対象となった図３５の上段左端のOR木の対を処理対象対にまとめ調査メモリD3に導入する。その後動作B3、B14の経路で図２４(a)の上位排他木によるOR木の被覆が失敗する。
【０３０１】
その後図２４(b-a)〜(b-h)の各排他木に関して動作B29、B33、B2、B3、B14の経路で被覆が失敗し動作は動作B33に戻り図２４(c-a)の排他木を処理対象に導入し続く動作B2で図３６(a)の処理対象対を発生する。もちろん動作B2では図３６(a)の上側の構造が保存メモリD4に導入される。また動作B2では接続メモリD6にt25-n2という1-2対照対が導入される。その後動作B8、B9、B15、B20を判定noで通過する。動作B22の判定がyesであるので動作は動作B28に移る。
【０３０２】
動作B28では（１側）と（２側）の同一順番の子節点以下の構造をそれぞれ対にして調査メモリD3に導入する。この時点に於ける調査メモリD3内容は図３６(b)のようになる。以後はそれぞれの対においてここでの子節点を最上位節点として取り扱う。
【０３０３】
動作は動作B4を経て動作B8に至る。ここでは直前に発生した図３６(b)の処理対象対が取り出される。次の動作B9でyesの判定が発生し続く動作B10でもyesの判定が発生し、動作は動作B11に移る。ここではt26-n3の1-2対照対を発生して接続メモリに導入する。動作は動作B4に戻る。この時点で被覆が成功する。
【０３０４】
動作は動作B6に移る。ここでは接続メモリD6中にt25-n2、t26-n3の２つの1-2対照対があるので、保存メモリD4中の図３６(a)の上側の形式の排他木の節点番号t25、t26を持つ節点にそれぞれn2、n3という節点番号を接続情報として付加する。動作B6の処理の結果保存メモリD4中には図３４(b)の被覆排他木が存在することとなる。
【０３０５】
その後動作B7に移行する。ここでは保存メモリD4内容すなわち図３４(b)の被覆排他木を被覆セットメモリD9に導入する。
【０３０６】
その後図２４(c-b)〜(c-j)の各排他木に関して動作B29、B33、B2、B3、B14の経路で被覆が失敗し動作B29に至る。
【０３０７】
動作B29では図３６(a)の下側のOR木に対する全ての上位排他木、排他木での被覆の試みすなわち排他木レジスタのスキャニングが終わったので、今回はyesの判定を発生し動作は動作B30に移る。
【０３０８】
続くB30では被覆セットメモリD9の内容を１つのセットとして前段メモリD12に導入する。現在被覆セットメモリD9の内容は動作B7により導入された図３４(b)の構造であるのでこれ１つを１つのセットとして前段メモリに導入する。
【０３０９】
続いて動作は動作B31に移る。現在OR木メモリD1には図３５に示すOR木の内上段左端のものを削除したものが収容されている。判定結果はnoであり動作は動作B1に移る。ここでは図３５の上段左より２番目のOR木が処理対象として入力し動作は動作B2に戻る。
【０３１０】
以後の動作は図３５の左端のOR木に関する動作と同じであり、図２４(c-c)の排他木による被覆が成功し、図３４(c)の１つの被覆排他木からなる被覆セットが前段メモリに導入され動作は動作B31を経て動作B1に移る。
【０３１１】
現在OR木メモリD1には図３５の上段の２つのOR木が削除された状態でOR木が存在する。このため図３５の中段のOR木が処理対象として発生する。
【０３１２】
図２４(a)の上位排他木、(b-a)の排他木については最上位節点が異なるので動作B33、B2、B3、B29の経路を出力の発生なく２周する。次の動作B33で図２４(b-b)の排他木が導入される。動作B2でまず（１側）の排他木を保存メモリD4に導入する。（１側）と（２側）の最上位節点に関する1-2対照対t29-n6を接続メモリD6に導入する。また（１側）と（２側）の処理対象対を構成する。これを図３７(a)に示す。動作B3、B4、B9、B15をno判定で通過し動作B20がyes判定であるので、動作B21に至る。ここでの動作の結果処理対象対は図３７(b)のようになる。動作B22により（１側）と（２側）の左端の構造が一致するので、動作B28により一致する子構造間の処理対象対を調査メモリD3に導入する。結果として調査メモリ内容は図３７(c)のようになる。
【０３１３】
動作B4を経て動作B9をno判定で通過し、動作B15はyes判定であるので動作B16に移行する。ここではt30-n7という1-2対照対が接続メモリD6に導入される。動作B17をnoで通過した後動作B19に移る。ここでは図３７(c)の左の処理対象対の下側の構造をOR木準備メモリに導入する。
【０３１４】
現在調査メモリD7には図３７(c)中の右の処理対象対が残っているので判定はnoであり、動作B9を経て動作B15に至りさらに動作B16に至る。ここではt31-n12という1-2対照対の値が接続メモリD6に導入される。動作B17をnoで通過した後動作B19に移る。ここでは図３７(c)の右の処理対象対の下側の構造をOR木準備メモリD7に導入する。
【０３１５】
動作は動作B6に移る。ここでは接続メモリD6中にt29-n6、t30-n7、t31-n12という1-2対照対があるので、保存メモリD4中の図３７(a)の上側の形式の排他木の節点番号t29、t30、t31という節点番号を持つ節点にそれぞれn6、n7、n12の節点番号を接続情報として付加する。また２回の動作B19でOR木準備メモリD7に導入した図３９の上段左から３番目と４番目のOR木をOR木メモリD1に導入する。
【０３１６】
動作B6の処理の結果保存メモリD4中には図３８左側の被覆排他木が存在することとなる。その後動作B7に移行する。ここでは保存メモリD4内容すなわち図３８の左側の被覆排他木を被覆セットメモリD9に導入した後動作B29に至る。
【０３１７】
その後図２４(b-c)〜(c-j)の排他木について、動作B33、B2、B3、B29の経路または動作B33、B2、B3、B8、B9、B15、B20、B22、B23、B14、B29出力の発生なく周回した後動作B33にて図２４(b-f)が導入される。前図２４(b-b)の場合と同じくこれに関する被覆が成功し、被覆セットメモリD9に図３８右側の被覆排他木を導入した後動作B29に至る。その後図２４の他の排他木に関する被覆が失敗して動作B29がnoの判定を発生し動作B30にて図３８の被覆排他木全体を１つのセットとして前段メモリに導入する。
【０３１８】
この動作の後のOR木メモリの内容は図３９に示すものとなっている。これの最初の３つのOR木についての図２１の主上位排他相対フィルタリング部E31適用の結果図４０(a)、(b)、(c)に示す被覆セットが発生する。これらはそれぞれ１つの被覆排他木からなるものであり、これらのうち図４０(a)、(b)、(c)はそれぞれ図２４(c-g)、(c-h)、(b-c)の排他木による被覆の結果発生する。またこの間図４１中左の２つのOR木をOR木メモリD1に導入する。
【０３１９】
ここで図３９の最初の３つのOR木に関する動作が終了し、動作B1にて第４のOR木が処理対象として入力する。
【０３２０】
図２４(a)、(b-a)〜(b-e)の排他木について、動作B33、B2、B3、B29の経路を出力の発生なく周回した後動作B33にて図２４(b-d)が導入される。
【０３２１】
この際動作B2で調査メモリD3中に発生する処理対象対は図４２(a)の構造を持つ。また同じく動作B2でt43-n12の1-2対照対が発生し接続メモリD6に導入される。動作B3、B4、B9、B15、B20をno判定で通過した後動作B22でyes判定が発生し、動作B28で調査メモリD3に図４２(b)の構造の処理対象対が発生する。
【０３２２】
動作B8により左側の処理対象対を処理対象として取り出し動作B9をno判定で通過し動作B15をyes判定で通過し動作B16に至る。ここでt44-n13の1-2対照対を発生し接続メモリD6に入れる。動作B17の判定はnoであり、動作B19により図４２(b)左側下方の構造がOR木準備メモリに導入される。
【０３２３】
動作は動作B4を通過して動作B8により図４２(b)右側の処理対象対を入力する。動作B9をno判定で、また動作B15をyes判定で通過し動作B16に至る。ここではt44-n13の1-2対照対が発生し接続メモリD6に導入される。動作は動作B17に至る。ここでは現在の（２側）の最上位節点であるn15の節点番号を持つ被覆排他木が図３４(a)に示されているように既に存在するので、図４２(b)右側下方のOR木をOR木準備メモリD7に導入しない。このように既に存在するOR木と同一のものが作成しない。この動作を行う部分が前述したように図２１の動作B17および動作B25である。
【０３２４】
動作は動作B4に戻り被覆が成功したので動作B6にて接続メモリD6中の３つの1-2対照対の指示により保存メモリD4に存在する図４２(a)の上側の構造に（２側）の節点番号を導入する。またOR木準備メモリD7中の図４２(b)右側の構造をOR木メモリD1に導入する。結果として現在のOR木メモリD1の内容は図４１のようになる。
【０３２５】
また動作B7により図４０(d)の被覆排他木を被覆セットメモリD9に導入する。
【０３２６】
動作B17、B25の働きにより重複したOR木の発生がさけられるので結果として図３９上段のOR木の処理の結果図４０上段に示すいずれも１個の被覆排他木から構成される被覆セットが発生し、また図４１に示すOR木が新たに発生する。
【０３２７】
図４１に示すOR木についての図２１の主上位排他相対フィルタリング部E31の適用の結果図４３(a)、(b)、(c)に示す被覆セットが発生する。これらはそれぞれ１つの被覆排他木からなるものであり、これらのうち図４３(a)、(b)、(c)はそれぞれ図２４(c-d)、(c-e)、(c-f)の排他木による被覆の結果発生する。
【０３２８】
図４１右端のOR木に関する処理の終了後状態は動作B31に至るが、OR木メモリD1にもはやOR木が存在しないためここに主上位排他相対フィルタリング部E31動作の前段が終了したと判定し動作は主上位排他相対フィルタリング部E31動作の前段の終了を表現する動作B32に移る。
【０３２９】
動作B32では何の動作も行わず、動作は後段最初の動作である動作B34に移行する。
【０３３０】
この時点で前段メモリD12に導入されている被覆セットは図４４に示すものとなる。これは発生順に配列してあり、１つの被覆セットを構成する被覆排他木は同一図番にまとめて示してある。これらのうち図４４(a)は図３１、同(b)は図３４(a)、同(c)と(d)は図３４(b)と(c)、同(e)は図３８、同(f)〜(k)は図４０、同(l)〜(m)は図４３によりそれぞれ示されている。図４４に於いて各被覆排他木の最上位節点では、節点名に続いて括弧で囲んで節点番号が示されている。その後に括弧で囲んだ２つの部分がある。この内の左側の部分は従来より存在する被覆排他木が持つ排他木スコアを収容する部分であり最上位節点に付属する「排他木スコア欄」である。現在空欄になっている右側の部分は被覆排他木とその下位の部分から構成される「上位被覆下位最大木値状態」が持つスコアの総和を収容する「総和スコア欄」である。
【０３３１】
動作B34は前段メモリより１つの被覆セットを取り出す動作である。被覆セットは発生順に図４４に示す順序で配列されているが、本動作はその配列の後ろより順次取り出す動作を行う。
【０３３２】
まず図４４(m)の被覆排他木が取り出される。これは下位に接続する部分が無く「最大木値木による下位接続」が不要であるので動作B35にて「不要」との判断が発生し動作B39に移行する。動作B39では処理中の排他木の「排他木スコア欄」の値を「総和スコア欄」に導入する動作である。この結果図４５(a)の構造が得られる。動作B35は下位に接続する部分が無い被覆排他木を総和スコア欄に値を導入することにより「上位被覆下位最大木値状態」に変換する動作とみなされる。
【０３３３】
次の動作B38は上位被覆下位最大木値セット中に含まれる各上位被覆下位最大木値状態の総和スコア欄の値の大きな順に配列し「上位被覆下位最大木値配列」を構成し上位被覆下位最大木値配列メモリD14に導入する動作を行う。この場合は上位被覆下位最大木値セット中には図４５(a)の構造しか存在しないのでこれが上位被覆下位最大木値配列となる。上位被覆下位最大木値配列の先頭のものは最大木値木であるので動作B40では先頭の上位被覆下位最大木値状態すなわち図４５(a)の構造を最大木値木に選び「最大木値木メモリ」D16に導入する。
【０３３４】
最大木値木とは入力されたOR木を排他木で被覆した結果得られた「OR木が表現する一般に複数の木の中で最大の木値を発生するOR節点を含まない木」である。
【０３３５】
動作は動作B41に移り前段メモリD12が空であることを判定する動作B41に移る。これが空でないので状態は動作B34に戻る。ここでは図４４(l)の被覆排他木が導入され、上述した動作経路をたどり図４５(b)の上位被覆下位最大木値配列が発生しその先頭のものである図４５(b)の構造が最大木値メモリD16に導入される。
【０３３６】
動作B34では次に図４４(k)の被覆排他木が前段メモリより取り出される。この場合節点番号n10、とn13の節点についてはそれぞれ図４５(b)、(a)に示す最大木値木の融合が可能であるが節点番号n15の節点については融合するものがないのでここでの判定は「不能」であり図４４(k)の被覆排他木は前段メモリD12の先頭すなわち図４４(a)の被覆排他木の左に導入される。
【０３３７】
次の図４４(j)の被覆排他木は図４５(c)の最大木値木を発生する。
【０３３８】
動作B34では次に図４４(i)の被覆排他木が前段メモリD12より取り出される。この場合節点番号n13の節点については図４５(a)に示す最大木値木の融合が可能であるが節点番号n15の節点については融合するものがないのでここでの判定は「不能」であり図４４(i)の被覆排他木は前段メモリD12の先頭すなわち図４４(k)の被覆排他木の左に導入される。
【０３３９】
次に図４４(h)の被覆排他木が取り出される。これは下位に接続する部分があり、「最大木値木による下位接続」が可能であるので動作B35にて「可能」との判断が発生し動作B37に移行する。ここでは被覆排他木の葉節点に最大木値木の同一節点番号を持つ最大木値木を融合する。この場合図４４(h)の被覆排他木の節点番号n8を持つ節点に図４５(c)の最大木値木の同一節点番号を持つ最上位節点を融合し、また節点番号n10の節点に図４５(c)の最大木値木の最上位節点を融合する。さらに動作B37では被覆排他木の総和スコアの欄に、「被覆排他木の排他木スコア欄の値と融合した最大木値木の総和スコア欄の値の総和」を導入する。この場合はこの値はC+E+Kとなる。この操作を終えると被覆排他木は上位被覆下位最大木値木として取り扱われる。
【０３４０】
この場合得られた上位被覆下位最大木値木は図４５(d)の構造を持つ。融合された節点の排他木由来の節点番号は残存させるがスコアの表現は削除する。
【０３４１】
次の動作B38は上位被覆下位最大木値セット中に含まれる各上位被覆下位最大木値状態の総和スコア欄の値の大きな順に配列し「上位被覆下位最大木値配列」を構成し、上位被覆下位最大木値配列メモリD14に導入する動作を行う。この場合は上位被覆下位最大木値セット中には図４５(d)の構造しか存在しないのでこれが上位被覆下位最大木値配列となる。上位被覆下位最大木値配列の先頭のものは最大木値木であるので動作B40では先頭の上位被覆下位最大木値状態すなわち図４５(d)の構造を最大木値木に選び「最大木値木メモリ」D16に導入する。
【０３４２】
図４４(g)、(f)については前述の単語節点とその上位の節点の場合と同じくそれぞれ図４５(e)、(f)の最大木値木が発生する。その後再び動作B34に戻る。
【０３４３】
図４４(e)の上位被覆セットについてはこれまで発生した最大木値木が下位に接続できないので動作B35で下位接続が「不能」であるとの判定が発生しB36により前段メモリD12の先頭に導入される。その後再び動作B34に戻る。
【０３４４】
図４４(d)、(c)のそれぞれ被覆排他木１つから成る上位被覆セットについては前述の単語節点とその上位の節点の場合と同じくそれぞれ図４５(g)、(h)の最大木値木が発生する。その後再び動作B34に戻る。
【０３４５】
次に図４４(b)の被覆排他木が取り出される。これは下位に接続する部分があり、「最大木値木による下位接続」が可能であるので動作B35にて「可能」との判断が発生し動作B37に移行する。この場合図４４(b)の被覆排他木の節点番号n16を持つ節点に図４５(f)の最大木値木の同一節点番号を持つ最上位節点を融合し、また節点番号n18の節点に図４５(e)の最大木値木の最上位節点を融合する。さらに動作B37では被覆排他木の総和スコアの欄に2F+Kの値を導入する。この操作を終えると被覆排他木は上位被覆下位最大木値木として取り扱われる。以後実際の効果が発生しない際の動作B38、B39の動作の記述は省略する。この場合得られた上位被覆下位最大木値木は図４５(i)の構造を持つ。
【０３４６】
図４４(a)の左側の上位被覆木は下位接続可能であるが右のものが不能であるので動作B35で下位接続が「不能」の判定が発生しB36により前段メモリD12の先頭に導入される。このように上位被覆セットに含まれる排他木全体の下位に最大木値木が接続できない場合は「不能」と判定する。その後再び動作B34に戻る。
【０３４７】
現在前段メモリD12には図４４(a)、(e)、(i)、(k)の各上位被覆セットがこの順序で配列収容されている。動作B34は前段メモリ配列の後ろより順次取り出すので、次に図４４(k)の被覆排他木が取り出される。これは下位に接続する部分があり、「最大木値木による下位接続」が可能であるので動作B35にて「可能」との判断が発生し動作B37に移行する。この場合図４４(k)の被覆排他木の節点番号n10を持つ節点に図４５(b)の最大木値木の同一節点番号を持つ最上位節点を融合し、節点番号n13の節点に図４５(a)の最大木値木の最上位節点を融合し、節点番号n15の節点に直前に発生した図４５(i)の最大木値木の最上位節点を融合する。さらに動作B37では被覆排他木の総和スコアの欄にC+E+2F+2Kの値を導入する。この場合得られた最大木値木は図４５(j)の構造を持つ。
【０３４８】
次に図４４(i)の被覆排他木が取り出される。この場合動作B35にて「可能」との判断が発生し動作B37に移行する。図４４(i)の被覆排他木の節点番号n13を持つ節点に図４５(a)の最大木値木の同一節点番号を持つ最上位節点を融合し、また節点番号n15の節点に図４５(i)の最大木値木の最上位節点を融合する。さらに動作B37では被覆排他木の総和スコアの欄にC+2F+K+Lの値を導入する。この場合得られた最大木値木は図４５(k)の構造を持つ。
【０３４９】
次に図４４(e)の２つの被覆排他木から成る上位被覆セットが取り出される。この場合動作B35にて「可能」との判断が発生し動作B37に移行する。ここでは図４４(e)の左側の被覆排他木の節点番号n7、n12の節点にそれぞれ図４５(d)、(k)の最大木値木の最上位節点を融合する。また図４４(e)の右側の被覆排他木の節点番号n8、n20の節点にそれぞれ図４５(c)、(j)の最大木値木の最上位節点を融合する。
【０３５０】
さらに動作B37では被覆排他木の総和スコアの欄に、「被覆排他木の排他木スコア欄の値と融合した最大木値木の総和スコア欄の値の総和」を導入する。この場合左側の被覆排他木についての値は2C+E+2F+3K+Lであり、右側のものの値は2C+E+2F+2K+Nとなる。これらの融合結果を図４６に示す。上記融合の結果この図は上位被覆下位最大木値セットとなる。
【０３５１】
次の動作B38は上位被覆下位最大木値セット中に含まれる各上位被覆下位最大木値状態の総和スコア欄の値の大きな順に配列し「上位被覆下位最大木値配列」を構成し上位被覆下位最大木値配列メモリD14に導入する動作を行う。上位被覆下位最大木値セット中に含まれる各上位被覆下位最大木値状態の総和スコア欄の値の大小の比較は前に述べたように「アルファベットの最初の文字Aより順次アルファベットで表現されたスコアの種類ごとに含まれる排他木の個数の比較を順次行い、どれかの文字の排他木を一方の解析木がより多く持てば以後の比較を行わずその解析木のスコアが大きい」という定義により行われる。この例の場合スコアの種類Kの排他木を図４６(a)左側の上位被覆下位最大木値状態は３個持ち、同右側のそれは２個しか持たないので以後の排他木の比較を行うことなく左側の木のスコアが大きいと判定する。
【０３５２】
この結果動作B38の出力としてやはり図４６の配列が発生する。
【０３５３】
上位被覆下位最大木値配列の先頭のものは最大木値木であるので動作B40では先頭の上位被覆下位最大木値状態すなわち図４６左側の構造を最大木値木に選び「最大木値木メモリ」D16に導入する。
【０３５４】
次に図４４(a)の２つの被覆排他木から成る被覆セットが取り出される。この場合動作B35にて「可能」との判断が発生し動作B37に移行する。ここでは図４４(a)の左側の被覆排他木の節点番号n15の節点に図４５(i)の最大木値木の最上位節点を融合する。また図４４(a)の右側の被覆排他木の節点番号n2、n4、n6の節点にそれぞれ図４５(h)、(g)の最大木値木の最上位節点を融合し、また節点番号n6の節点に直前に発生した図４６左側の最大木値木の最上位節点を融合する。
【０３５５】
さらに動作B37では被覆排他木の総和スコアの欄の値を導入する。左側の被覆排他木についての値は13A+2F+Kであり、右側のものの値は3C+E+2F+G+3K+Lとなる。これらの融合結果を図４７に示す。上記融合の結果を表すこの図は上位被覆下位最大木値セットの図である。
【０３５６】
次の動作B38は上位被覆下位最大木値セット中に含まれる各上位被覆下位最大木値状態の総和スコア欄の値の大きな順に配列し「上位被覆下位最大木値配列」を構成し上位被覆下位最大木値配列メモリD14に導入する動作を行う。この場合図４７の上側の上位被覆下位最大木値状態の値が下側のものより大きいので図４７に示した上位被覆下位最大木値配列が発生する。但しより上側の構造が配列の最初のものであると規定する。
【０３５７】
上位被覆下位最大木値配列の先頭のものは最大木値木であるので動作B40では先頭の上位被覆下位最大木値状態すなわち図４７上側の構造を最大木値木に選び「最大木値木メモリ」D16に導入する。
【０３５８】
これまでの動作では前段メモリD12に値が存在したため、動作B41の判定はnoであったが、この時点で前段メモリD12は空となるためyesの判定が発生し動作は後半動作終了を示す動作B42に至り次いで主上位排他相対フィルタリング部E31全体の動作の終了の動作であるB43に移行する。ここでは最大木値木メモリD16の値を出力する。例えば文の全単語を含んでいるという条件や最上位節点が文全体を示すCLであるという条件で出力を制限すると、結局図４７の上側の構造が出力として発生する。
【０３５９】
図４７に示す２つの上位被覆下位最大木値状態では各部分を被覆する排他木の境界が３行から構成される節点属性で表現されている。この内３行目の右端の部分が当該節点より下位の部分を被覆する排他木のスコアである。
【０３６０】
この３行目のスコアとその節点より下位の排他木構造に着目すると図４７の上側の上位被覆下位最大木値状態は図１５(c)に示す解析木の排他木による被覆の状態を示しており、同下側の構造は図１５(a)の構造を表現している。ここでは図１５(c)すなわち図４７の上側の構造が出力として発生する。
【０３６１】
図１５(c)の構造と図１５(a)の構造の比較の前に、図１５(a)の構造と図１５(b)の構造の比較が行われ、図１５(b)の構造が削除される。このことは、これら構造の非共通部分の比較を行う図４６に関する動作で行われる。図４６の左側の構造が図１５(a)の構造の部分木であり、同右側の構造が図１５(b)の構造の部分木である。前者が最大木値木として選択される結果図１５(b)の構造が削除される。
【０３６２】
これまでの考察により図４７の上側の構造を出力として発生させることができたので、図１５に関連して示したスコアの高い図１５(c)の構造が出力として発生するという目的がここで達成されたわけである。
【０３６３】
式(1)の入力文が形態素解析部E1を経て式(2)の文になり、これが書き換え規則適用部E2により図２４(d)の複数の解析結果をまとめて示したOR木形式の解析木となったものが主上位排他相対フィルタリング部E31の入力であり、その出力が上述の図４７の上側の構造である。またこのような動作の全体が図９にそのフローチャートを示す文例駆動型フィルタリング解析方式である。
【０３６４】
ここで本発明の主上位排他相対フィルタリング部E31の構成、動作と従来型の相対排他フィルタリング部R31の構成動作の差異について述べる。従来型の相対フィルタリング部R31の場合、OR木とそれを被覆する排他木の間で構造上の差異があれば被覆不能の判定を出す。上位排他相対フィルタリング部E31では、OR木とそれを被覆する排他木の間で構造上の差異があっても、その差異の部分がOR木と上位排他木の半構成節点の間で発生する場合は差異が無いものとみなす。但し差異が発生する部分の半構成節点は排他木より取り除くものとする。
【０３６５】
この部分が従来型の相対フィルタリング部R31と上位排他相対フィルタリング部E31との間の差異の一つである。具体的な動作フローとしては、従来の相対フィルタリング部R31は図２１に示す上位排他相対フィルタリング部E31のフローチャートに於いてTB1点とTB2点の間とTB3点とTB4点の２箇所を短絡して短絡部分から派生する動作を消去することにより得られる。具体的には短絡とともに動作B12、B13、B23、B24、B25、B27を削除する。この削除された動作は上記半構成節点に関する取り扱いを行う部分である。
【０３６６】
また図２４(a)のように上位排他木にOR節点の存在を許す点も相対フィルタリング部R31には無く上位排他相対フィルタリング部E31に新しく導入された機能である。OR節点は当然排他木においても存在可能である。この部分に関しては動作B20、B21に於いて（１側）の記述を削除することにより相対フィルタリング部R31の表現が得られる。
【０３６７】
図４８は図２１に対して上記変更を加えたものであり、主相対フィルタリング部、副相対フィルタリング部E31、禁止木適用部E32を含むフィルタリング部のフローチャートの図である。すなわち図４８は本発明の方法を縮退した記述による本発明外の図１に示す通常型フィルタリング解析方式のフィルタリング部R3の構成法である。
【０３６８】
これまで主上位排他相対フィルタリング部E31の動作について述べてきた。この部分は上位被覆下位最大木値状態をスコアの順に配列し、最大のスコアを持つものを選択する。これは図２１の動作B38およびB40にて行われる。ここでの方法は競争の勝者を出力とするところから相対フィルタリングを行う部分である。ここで相対フィルタリングに加えて絶対フィルタリングを併用する方法について考察する。これは出力最大木値木が含んではならない部分木である禁止木を指定しそれを含むものは木値が高いものであっても削除するという方式である。
【０３６９】
図２１にFOBと記した部分がこの動作を行う禁止木適用部E32である。この部分は主上位排他相対フィルタリング部E31が発生する木値順に配列された上位被覆状態配列を入力とし、もしその中で最大の木値を持つものが禁止木を部分木として含むならばこの配列の状態を変更して出力する。このため最大木値を持つ上位被覆下位最大木値状態が禁止木適用部FOBが無い場合と異なることがある。
【０３７０】
図２１において動作B38と動作B40の間を結ぶ実線の経路を取り去り、この間に禁止木適用部FOBを介在させると、それまで相対フィルタリングを行うフィルタリング方式から相対フィルタリングおよび絶対フィルタリングを行う総合フィルタリング方式に方式変更できる。これは図９の上位排他フィルタリング部の動作を完全に実現する場合に相当する。
【０３７１】
前述したように絶対フィルタリングはフィルタリング出力として発生する最大木値木が、禁止木と呼ばれる最大木値木中に存在してはならない木をその部分木として持つ場合その最大木値木全体を削除する処理である。以下主上位排他相対フィルタリング部E31に、禁止木適用部E32ならびにこれがサブプログラムとして呼ぶ副上位排他相対フィルタリング部E33を加えた図２１の上位排他フィルタリング部E3全体の動作である総合フィルタリング動作について述べる。
【０３７２】
禁止木適用部E32は、主上位排他相対フィルタリング部E31の動作B38がもたらす上位被覆下位最大木値セット中の先頭の位置にある最大木値木に含まれる禁止木と同一構造を持つ部分が最大木値木の最上位部分を被覆する被覆排他木の範囲に限られる時は単に上位被覆状態配列の先頭のものを削除し、２番目のものを最大木値木に指定する。もしも、禁止木の範囲が最大木値木の最上位部分を被覆する被覆排他木の範囲の直下位の部分構造に及ぶ場合は、禁止木適用部E32はその部分の最大木値木を元のOR木に復元し、副上位排他相対フィルタリング部E33を呼ぶ。そしてそのOR木に対する上位被覆下位最大木値配列を構成させその配列の先頭にある最大木値木に禁止木の適用を行う。このため段落０２２０の説明中に示したように、各被覆排他木はその最上位節点の「OR木欄」に元のOR木を保持する必要がある。このOR木欄へのOR木の導入は図２１中の動作B2にて行われる。
【０３７３】
具体的な例で説明する。まず主上位排他相対フィルタリング部E31の動作B38で図４７に示す上位被覆下位最大木値状態配列を発生した後禁止木適用部E32の動作を呼ぶ。この呼び出しを含む移行を示すために図２１中では移行を示す矢印にCの注記を付してある。
【０３７４】
図４７の上位被覆下位最大木値状態配列を構成する２つの上位被覆下位最大木値状態が持つ節点のうち節点名の下に２行にわたる注釈が付された部分が被覆排他木の境界節点であり、これらは被覆の対象となったOR木を「OR木欄」に持つ。図４７上側のスコア最大の上位被覆下位最大木値状態すなわち最大木値木に於いて節点n15、n16、n18が被覆排他木の被覆境界となる。
【０３７５】
禁止木適用部E32での動作に於いて、もしも禁止木適用部E32で適用される禁止木が図４９(a)のものであれば禁止木が「最大木値木の最上位部分を被覆する被覆排他木の範囲」に限られるので、これを削除し２番目のスコアを持つ上位被覆下位最大木値状態すなわち図４７下側のものを最大木値木に指定し、これが禁止木を含まないならばこれを最大木値木に指定する。
【０３７６】
その後動作は主上位排他相対フィルタリング部E31の動作B40に移行する。この移行の矢印には返答であることを示す注記Rが付されている。
【０３７７】
しかしながらもし排他木適用部E32動作で適用される禁止木が図４９(b)のものであれば禁止木の範囲が「最大木値木の最上位部分を被覆する被覆排他木の範囲」を越えるという理由で図４７上側の構造を単純に削除することはできない。この場合は境界節点n15がその「OR木欄」に持つその節点以下の部分のOR木を利用しなければならない。このOR木は図２８に示されている。
【０３７８】
このOR木を入力として図２１の右隅に示す副上位排他相対フィルタリング部E33に加える。この際の移行が禁止木適用部E32より副上位排他相対フィルタリング部E33への移行であり、呼び出しを含む移行を示すために移行を示す矢印にCの注記を付してある。副上位排他相対フィルタリング部E33はこの入力OR木に対して、節点n15を最上位節点とする上位排他下位最大木値状態配列を構成し禁止木適用部E32に返す。この際の移行が副上位排他相対フィルタリング部E33より禁止木適用部E32への移行であり矢印に返答であることを示す注記Rが付されている。この移行を受けて禁止木適用部E32は、これのスコア最大のものに上記図４９(b)の下位の部分を適用する。
【０３７９】
節点n15を最上位節点とする上位被覆下位最大木値状態配列はただ１つの上位被覆下位最大木値状態を持つ図４５(i)の構造でありこれの「最大木値木の最上位部分を被覆する被覆排他木の範囲」を禁止木が越えずかつ被覆排他木の部分木となるので、禁止木適用部E32は初めて図４７の上側の上位被覆下位最大木値状態を削除できる。これを行ったのち禁止木適用部FOBより主上位排他相対フィルタリング部E31の動作B40に移行する。
【０３８０】
以上述べたように禁止木適用部E32から副上位排他相対フィルタリング部E33への移行は禁止木適用部E32に於ける演算処理に必要なデータを図２１中の相対フィルタリング動作をサブプログラムとして用いるためのものである。すなわち禁止木適用部E32が処理に必要であると判断したOR木を副上位排他相対フィルタリング部E33に与えて、それの排他木での被覆結果である上位被覆下位最大木値状態配列を得るための状態転移である。結果である上位被覆下位最大木値状態配列の出力は副上位排他相対フィルタリング部E32より禁止木適用部E32への転移により行われる。
【０３８１】
この上位排他フィルタリング部E3に於ける主上位排他相対フィルタリング部E31、禁止木適用部E32、副上位排他相対フィルタリング部E33の相互関係と同等な関係は、従来型である図４８のフローチャートを持つフィルタリング部に於ける主相対フィルタリング部R31、禁止木適用部R32、副相対フィルタリング部R33の相互関係として存在する。
【０３８２】
禁止木適用部R32、E32はいずれの場合も上位被覆下位最大木値状態配列を入力として受け入れ、それに禁止木を適用した結果である、上位被覆下位最大木値状態配列を出力として発生する。またこの間にOR木を副上位排他相対フィルタリング部E33または副相対フィルタリング部R33に与えてそのOR木に対する上位被覆下位最大木値状態配列を得る。この意味で禁止木適用部E32またはR32の構成、動作は上位排他フィルタリング部E3、フィルタリング部R3双方に於いて同一である。
【０３８３】
この禁止木適用部E32の動作は本特許の範囲外であり、従来型のフィルタリング部の動作の一部として上記「榊博史著：コンピュータ翻訳技術：平成５年 電子情報通信学会刊」の図7.16および図7.20に関連してその構成、動作が詳細に示されているのでここではこれ以上の説明は行わない。
【０３８４】
副上位排他相対フィルタリング部E33は主上位排他相対フィルタリング部R33と全く同一の構造、動作を持つ。この際の禁止木適用部E32よりの動作移行先は副上位排他相対フィルタリング部E33の動作B2に相当する部分であり、禁止木適用部E32への移行が発生する動作は副上位排他相対フィルタリング部E33の動作B38である。ただし副上位被覆相対フィルタリングE33動作の記述では排他木を禁止木と読み替える必要がある。これらのことを示すために図２１では点線で副上位排他相対フィルタリング部E33としての動作移行を示してある。また呼び出し、返答を示すC、Rの文字は括弧で囲んで付加してある。もちろん計算機上では副上位排他相対フィルタリング部E33を、主上位排他相対フィルタリング部E31をそのまま用いることにより又は複写することにより構成可能である。
【０３８５】
もし図４９の禁止木が存在しない場合は図９に示す構成を持つ文例駆動型フィルタリング解析方式は図４７上側の構造を解析結果として発生する。これに対して図１に示す通常型フィルタリング解析方式は図８(a)の構造すなわち図４７下側の構造を解析結果として発生する。文例駆動型フィルタリング解析方式の出力である図４７上側の構造は図１１(b)の書き換え規則、同(c)の上位排他木が優先して適用された結果発生したものである。このように文例駆動型フィルタリング解析方式は文例が持つ構造を優先して発生し結果として自然言語が持つ変異に文例を介して対応することができる。
【０３８６】
図１１(c)の上位排他木の半構成節点は#印の付された節点Nおよびskiingである。この場合半構成節点はあらかじめ指定されている。半構成節点を図９中の合致文例抽出部E9からの単語状態スタックの最終結果をもとに決定する方法がある。これを上位排他木の具体化演算と称することとしこれについて説明する。
【０３８７】
図５０は合致文例抽出部E9から規則分離部E10を経て上位排他木処理蓄積部E12にもたらされた上位排他木に関する情報である。図５０(a)は図１７(a)に示された合致条件配列である。また図５０(b)は図１８(i)に与えられる単語状態値スタックの最終結果である。また図５０(c)は図１１(c)の上位排他木である。
【０３８８】
具体化演算はまず図５０(b)に例示される単語状態値スタックの最終結果のうちからパラメター(5)合致単語束番号の欄に於ける有意な値を抽出する。この場合有意な合致単語束番号は1、3、5、7である。これは図５０(a)の合致条件配列に於いて第１番、３番、５番、７番の単語束それぞれThere、aまたはthe、about、skiingまたはNが入力文単語と合致することを意味する。第３番はaとtheあいまい性があり、どちらの単語が一致したのかわからない。しかしながらパラメター(5)値が3の単語状況に於けるパラメター(2)単語番号の値が１であるところから合致条件配列の３列目第１行のaが入力文と合致することがわかる。同様にパラメター(5)値が7の単語状況に於けるパラメター(2)単語番号の値が２であるところから合致条件配列の７列目第２行のNが入力文と合致することがわかる。
【０３８９】
図５０(c)の上位排他木が持つ単語または品詞節点のうち、上記パラメター(5)とパラメター(2)より入力文と合致することが判明したものに%記号を付加する。図５０(c)の上位排他木にはこの記号が付加されている。
【０３９０】
この%を持つ各節点を出発点に図５２に示す上位排他木の具体化手順に従って%記号の付け替え、付加を行う。その結果が図５１(a)である。その後%印の付加された節点からは%を取り去り、%記号の付加されない節点には#記号を付けることにより図５１(b)の半構成節点を含む被覆排他木を得ることができる。
【０３９１】
以下図５０(c)に示す上位排他木に関する情報の例について被覆排他木を求める手順を説明する。この場合「合致節点メモリ」というハードウエアを導入する。合致節点メモリには図５０(c)中の%記号の付加された節点が存在するものとする。
【０３９２】
まず動作C0で本動作を開始する。次の動作C1では合致節点メモリ中の節点の存在の判定を行う。ここでは、節点There、a、about、Nが存在するので判定はyesである。次の動作C2では合致節点メモリの先頭のものである節点Thereを取り出す。次に動作C3により取り出した節点が名詞の品詞を持つかどうかを判定する。もしこの判定がyesであると名詞性であることを示すNフラグをONにすることを含む動作C6に移る。この場合節点Thereは品詞THEREを持つので判定はnoである。次の動作C4は上位節点がOR節点かどうかを判定する。この場合は上位節点がTHEREであるので判定はnoである。
【０３９３】
次の動作C9で図５０(c)の上位排他木中１つ上位の節点THEREに移動する。次の動作は現節点であるTHEREに%記号が付加されていることの判定を行う。判定はnoであり次の動作C11で現節点が名詞句であるNPかどうかの判定を行う。判定はnoであり動作C13に移る。これは名詞性であることを示すNフラグがONになっていることの判定である。この場合は判定はnoであり動作C14に移る。この動作は現節点とその兄弟節点に%記号を付加する動作である。この結果節点THERE、BE、NPに%記号が付加される。
【０３９４】
次の動作C15は現節点が最上位節点かどうかの判定を行う。この場合の判定はnoである。次の動作C16は動作C4と同じく上位節点がOR節点かどうかを判定する。この場合は判定はnoであり。動作は動作C9に戻る。この場合動作C9により節点CLに移る。
【０３９５】
以下動作C10、C11、C13をnoで通過し動作C14で節点CLに%記号を付加する。次の動作C15により現節点が最上位節点かどうかの判定をする。この場合はyesであり動作はC1に戻る。
【０３９６】
合致節点メモリにまだ節点a、about、Nが存在するので動作C1の判定はyesである。次の動作C2で現在の先頭の節点aを取り出す。以後動作C3をnoで通過し動作C4に移る。これは現在の節点の上位の節点が節点ORであるかどうかの判定である。この場合は判定はyesであり動作はC5に移る。これは現節点の兄弟節点およびその下位の節点を全て削除し、また上位の節点ORも削除する動作である。この場合節点aの兄弟節点のtheを消去しまた節点aの上位の節点ORを削除する。結果として節点aは節点DETの直下位に接続されることになる。
【０３９７】
次の動作C9により１つ上の節点DETに移動する。次の動作C10、C11、C13をnoで通過し動作は動作C14に移る。動作C14では節点DET、N、P、NPに%記号を付加する。次に動作C15、C16をnoで通過し動作C9により節点NPに移る。次の動作C10では節点NPに既に%記号が付加されているので動作は動作C1に移る。
【０３９８】
合致節点メモリにまだ節点about、Nが存在するので動作C1の判定はyesである。次の動作C2で現在の先頭の節点aboutを取り出す。以後動作C3、C4をnoで通過し動作C9に移る。ここでは節点Pに移る。次の動作C10ではすでに節点Pに%記号が付加されているので動作は再び動作C1に移る。
【０３９９】
合致節点メモリにまだ節点Nが存在するので動作C1の判定はyesである。次の動作C2で現在の先頭の節点Nを取り出す。次の動作C3は品詞がNであるかどうかの判定を行う。この場合の判定はyesであり動作は動作C6に移る。動作C6は名詞性であることを示すNフラグをONにするとともに現節点自身すなわち節点Nが持つ%記号を削除する。動作C7は現節点の上位節点が節点ORかどうかの判定を行う動作である。この場合は判定はnoであり動作は動作C9に移る。動作C9により節点は節点NPに移る。節点NPにはすでに%記号が付加されているので動作C10により、動作は動作C1に移る。現在合致節点メモリは空であるので動作は動作C21に移る。
【０４００】
現在の上位排他木は図５１(a)に示す状態にある。動作C21は%記号の付加された節点よりこの記号を削除し、何も付加されていない節点に#記号を付加する動作である。動作C21の動作の結果図５１(b)の構造を得る。これが被覆排他木となる。
【０４０１】
図５２のフローチャートの中で現在の例で通過しなかった動作のうち動作C18、C19、C20はそれぞれ動作C15、動作C16、動作C9と同様な部分である。
【０４０２】
図５２のフローチャートは動作C3、動作C6、動作C11、動作C12、動作C13で名詞Nから上位の節点NPまでの間の節点に任意であることを示す#記号を付加する処理を行っている。名詞句を示す節点NPの下位にある節点Nの周辺の構造は非常に多様であるので、この部分を任意とする必要があるための処理である。
【０４０３】
このように、（１側）として記述してきた文例側と（２側）として記述してきた入力文側の一致単語が残存した形式の被覆排他木に対し上位排他木の具体化構成演算を適用することが可能である。
【０４０４】
本発明の主要部を構成する上位排他フィルタリング部E3は図２４に示すOR木、上位排他木、排他木を入力とし、これに対して図２１に示す種々の処理を加えて最終的な出力である図４７上側の最大木値木を解析木出力として発生する。これらの木構造は、節点を変数に対応させ、それら変数を括弧を用いてまとめることにより表現可能である。この形式の表現をここではS式と称することとする。
【０４０５】
S式は木構造の親節点と一般に複数の子節点からなる全体を括弧で囲んで表現する。括弧の中では親節点を左端に置き、その右側に木構造の兄弟節点を木構造に於ける順序を保ちつつ配列する。各節点の間はスペースで区切る。例えば図５３(a)の構造は式(3)で表現される。S式の表現法は入れ子式にすなわち再帰的に適用可能である。例えば図５３(b)の木構造は式(4)で表現できるが、これを式(3)のS式(D)に代入することにより図５３(c)の構造に対するS式である式(5)を構成できる。
(A (B) (C) (D) )
(3)
(D (E) (F))
(4)
(A (B) (C) (D (E) (F)))
(5)
【０４０６】
図４７上側の最高木値木の属性の記述を取り去った構造は図５３(d)のように書けるが、これのS式表現は以下の式(6)のようになる。
(CL (THERE (There) ) (BE (be{past, sgl} ) )
(NP (DET (a) ) (N (excitement) ) (P (about) ) (NP (N (soccer) ) (N (game{pl}) ) ) ) ) (6)
【０４０７】
S式の表現に於いて図２１中の動作B9、B15等の子節点が無いことの確認は括弧内に第２項以降の項が無いことの確認となり、動作B22に於ける子節点が順序を含めて一致することの確認は第２項以降の項のそれぞれの初項が順序を含めて一致することの確認となる。また動作B21に於ける並列構造への分解は単にOR節点である初項を削除することにより実現できる。このように図２１動作のすべての動作がS式の表現に於いても実現可能である。
【０４０８】
木構造から変換したS式の括弧は、リストを表現する括弧に対応させて取り扱うと便利である。また使用する言語としてリストを取り扱いデータの中心に置き、リストを直接取り扱う関数を豊富に持つ計算機言語Lispを使用すると木構造に関連する演算が非常に容易になる。Lisp関数にはリストの第１項を抽出する関数CARや第２項以下を抽出する関数CDRがあるので親節点と子節点を分離するのは簡単である。またリストから任意の位置の要素を抽出することも、構造体中の任意の欄の値を抽出することもLispの組み込み関数を組み合わせることにより可能である。
【０４０９】
なお図２１の動作B37に於ける節点の融合は上記式(3)に式(4)を代入する演算と同様な代入を行うことにより実現できる。
【０４１０】
各節点が持つ属性を収容する欄の構成は節点に対応する変数をLispが持つ機能の１つである構造体で表現することにより可能である。
【０４１１】
この様な手段を講じることにより、図２１で表現された木構造に対する全ての演算は計算機上の関数の組み合わせで実現可能である。すなわち図２１に示す各演算は論理的実体として構成可能である。
【０４１２】
データを蓄えるための図２３に示した排他木レジスタ、境界節点対スコア対照表以外の各種メモリに収容されるデータの個数および値は常時変化する。データの多くはリストの形式を持つ。これらメモリはリストとして構成することにより計算機上で論理的実体として実現可能である。排他木レジスタ、境界節点対スコア対照表D8は配列として構成するのが妥当である。
【０４１３】
なお図２３中の演算を示す部分である排他木被覆実行D11は図２１中の動作B6の動作が行われる現場である。接続動作D13は同じく同動作B37が行われる現場である。その他の部分は同被覆可否決定部D10に相当する。もちろん禁止木適用部E32では図２１のFOBとして示した禁止木適用部の動作が行われる。
【０４１４】
以上で図９に示した文例駆動型フィルタリング解析方式を構成する各部のうちその主要な部分である、合致文例群抽出部E9と上位排他フィルタリング部E3について詳細に説明した。図９において細い線で囲まれた部分は図１に示した通常型フィルタリング解析方式に含まれているものであり、「榊博史著；コンピュータ翻訳技術；電子情報通信学会；平成５年刊」にてその構成、動作が明らかにされている。
【０４１５】
品詞規則適用部E6は例えば式(2)に示す入力文の形態素解析結果に対して図１０(a)のような品詞規則適用結果を発生する部分である。この部分は図１に示す通常型フィルタリング解析方式に含まれる書き換え規則R2適用部の一部であり、その構成法動作は自明であるものである。
【０４１６】
この品詞規則適用部E6に続く直線化部E7は図１０(a)より図１０(b)の構成を行う部分である。品詞規則適用結果は図４９と式(3)〜(6)との関係に見られるごとくリストにより表現される。例えば図１０(a)の左端の構造は式(7)により表現される。
(THERE (There) ) (7)
There(THERE) (8)
【０４１７】
直線化部E7はまず式(7)から式(8)の変換に例示される変換を全ての品詞規則適用結果の要素について行う。ついで品詞規則適用結果の要素間の相互位置は保ちながら、これらを通常の文と同様な直線状に並べる動作を行う。この動作はLisp言語の関数を用いれば容易に実現可能である。
【０４１８】
文例メモリE8は文例を固定的に収容するメモリであり、計算機言語の配列として実現可能である。
【０４１９】
規則分離部E10は文例レジスタが保持する各文例が持つ書き換え規則と上位排他木を分離する機能を持つ部分である。これはあらかじめ各文例中のこれらの部分の先頭に書き換え規則であること、上位排他木であること、の標識を付しておくことにより簡単な関数の設計で実現可能である。
【０４２０】
書き換え規則レジスタE11、上位排他木処理蓄積部E12、排他木レジスタE13はそれぞれ計算機言語が取り扱うデータ構造である配列として実現可能である。
【０４２１】
以上の考察により図９の文例駆動型フィルタリング解析方式を構成する全ての部分が計算機上の論理的実体として構成可能であることが判明した。
【０４２２】
これまで合致文例が書き換え規則と上位排他木をもたらし、また内蔵排他木メモリE5が排他木を発生する場合について述べてきた。合致文例が書き換え規則と上位排他木以外に排他木、禁止木をもたらし、内蔵排他木メモリE5が排他木、禁止木以外に上位排他木を発生することも当然可能である。
【図面の簡単な説明】
【０４２３】
【図１】通常型フィルタリング解析方式の構成図である。
【図２】統語規則を示す図である。
【図３】品詞規則を示す図である。
【図４】通常型フィルタリング解析方式の解析過程を示す図である。
【図５】一般的排他木を示す図である。
【図６】単語関係排他木を示す図である。
【図７】解析結果のOR木表現を示す図である。
【図８】排他木による解析木の被覆を示す図である。
【図９】文例駆動型フィルタリング解析方式の構成図を示す図である。
【図１０】品詞規則適用結果を示す図である。
【図１１】文例を示す図である。
【図１２】合致条件と合致単語列との間の合致成立を示す図である。
【図１３】文例駆動型フィルタリング解析方式に於ける解析結果を示す図である。
【図１４】文例駆動型フィルタリング解析方式が発生する展開木を示す図である。
【図１５】排他木および上位排他木による解析木の被覆を示す図である。
【図１６ａ】合致文例群抽出部動作フローチャートを示す図である。
【図１６ｂ】合致文例群抽出部動作フローチャートを示す図である。
【図１７】合致文例群抽出部入力の配列化を示す図である。
【図１８】単語状態値スタック内容を示す図である。
【図１９】合致が成立しない場合の配列化を示す図である。
【図２０】合致が成立しない場合の単語状態値スタック内容を示す図である。
【図２１ａ】上位排他フィルタリング部動作フローチャートを示す図である。
【図２１ｂ】上位排他フィルタリング部動作フローチャートを示す図である。
【図２２】OR木に対する上位排他フィルタリング部動作の説明図である。
【図２３】OR木に対する上位排他相対フィルタリング部動作に於けるデータの流れを示す図である。
【図２４】OR木とそれを被覆する排他木および上位排他木を示す図である。
【図２５】調査メモリ中の処理対象対を示す図の第１番目のものである。
【図２６】調査メモリ中の処理対象対を示す図の第２番目のものである。
【図２７】調査メモリ中の処理対象対を示す図の第３番目のものである。
【図２８】OR木メモリの内容を示す図の第１番目のものである。
【図２９】調査メモリ中の処理対象対を示す図の第４番目のものである。
【図３０】並列構造からの選択を示す図である。
【図３１】被覆セットを示す図の第１番目のものである。
【図３２】OR木メモリの内容を示す図の第２番目のものである。
【図３３】調査メモリ中の処理対象対を示す図の第５番目のものである。
【図３４】被覆セットを示す図の第２番目のものである。
【図３５】OR木メモリの内容を示す図の第３番目のものである。
【図３６】調査メモリ中の処理対象対を示す図の第６番目のものである。
【図３７】調査メモリ中の処理対象対を示す図の第７番目のものである。
【図３８】被覆セットを示す図の第３番目のものである。
【図３９】OR木メモリの内容を示す図の第４番目のものである。
【図４０】被覆セットを示す図の第４番目のものである。
【図４１】OR木メモリの内容を示す図の第５番目のものである。
【図４２】調査メモリ中の処理対象対を示す図の第８番目のものである。
【図４３】被覆セットを示す図の第５番目のものである。
【図４４】全ての被覆セットを示す図である。
【図４５】最大木値木を示す図である。
【図４６】上位被覆下位最大木値状態配列を示す図の第１番目のものである。
【図４７】上位被覆下位最大木値状態配列を示す図の第２番目のものである。
【図４８ａ】フィルタリング部動作フローチャートを示す図である。
【図４８ｂ】フィルタリング部動作フローチャートを示す図である。
【図４９】禁止木の例を示す図である。
【図５０】上位排他木蓄積処理部に於ける上位排他木の被覆排他木への具体化過程の入力としての上位排他木に関する情報の図である。
【図５１】具体化過程の図である。
【図５２】上位排他木蓄積処理部に於ける具体化手順の図である。
【図５３】木構造のS式表現の図である。
【符号の説明】
【０４２４】
E1 形態素解析部
E2 書き換え規則適用部
E3 上位排他フィルタリング部
E4 内蔵書き換え規則メモリ
E5 内蔵排他木メモリ
E6 品詞規則適用部
E7 直線化部
E8 文例メモリ
E9 合致文例群抽出部
E10 規則分離部
E11 書き換え規則レジスタ
E12 上位排他木処理蓄積部
E13 排他木レジスタ
E14 インタフェース＃１
E15 インタフェース＃２
E31、E32、E33 上位排他フィルタリング部E3を構成する部分
E31 主上位排他相対フィルタリング部
E32 禁止木適用部
E33 副上位排他相対フィルタリング部

【特許請求の範囲】
【請求項１】
入力文を形態素解析し、形態素解析した結果に単語と品詞の関係を示す品詞規則を適用することで、抽出用単語列を生成する手段と、
複数の文例と、各文例に対する合致条件及び上位排他木を保存する文例メモリと、
品詞関係に対応する排他木を保存する内蔵排他木メモリと、
文例メモリに含まれる各文例について、前記抽出用単語列が文例の合致条件に一致するか否かを判定し、一致するものを抽出する合致文例群抽出手段と、
前記合致文例群抽出手段が抽出した文例に対応する上位排他木それぞれについて、前記抽出用単語列の各単語と一致する単語に対応する節点から最上位節点にたどる経路上に存在する第１の節点と、第１の節点の兄弟節点である第２の節点とを検索し、第１の節点及び第２の節点のどちらでもない半構成節点を求め、前記合致文例抽出手段が抽出した文例に対応する上位排他木と、該上位排他木の半構成節点を示す情報を排他木レジスタ手段に蓄積する、上位排他木具体化手段と、
前記入力文を形態素解析し、形態素解析した結果に、書換え規則を適用して複数の木を生成し、生成した複数の木をＯＲ節点により１つにまとめたＯＲ木を出力する手段と、
前記排他木レジスタ手段に蓄積された上位排他木及びその半構成節点を示す情報と、前記内蔵排他木メモリに保存された排他木に基づき、前記ＯＲ木から、機械翻訳に使用する最大値木を出力する上位排他フィルタリング手段と、
を備えている機械翻訳解析結果選択装置。
【請求項２】
前記上位排他フィルタリング手段は、
第２の木が、第１の木の部分木であり、かつ、第２の木の最上位節点が第１の木の最上位節点に相当する場合、第２の木は第１の木を上位被覆可能であると呼び、第２の木が第１の木を上位被覆可能であるか否かを、第２の木から半構成節点を削除しつつ判定し、上位被覆可能となった時点における第２の木と、第１の木の節点間の対応関係を記録して、上位被覆可能となった時点における第２の木を被覆セットに追加する処理を、第２の木による第１の木の上位被覆処理と定義し、第１の木のうち、第２の木に相当しなかった部分を、上位被覆されなかった木と定義し、排他木レジスタ手段に蓄積された各上位排他木と、内蔵排他木メモリに保存された各排他木とを、それぞれ、被覆木と定義したとき、各被覆木について、被覆木によるＯＲ木の上位被覆処理を行い、各上位被覆されなかった木について、被覆木による、上記被覆されなかった木の上位被覆処理を行うことを繰り返し、
前記繰り返しにより被覆セットに含まれた上位排他木と排他木のうち、ＯＲ木との節点の対応関係を維持したまま入力文に対応する木を構成できる組合せであって、そのスコアの合計が一番大きい組合せを最大値木として出力し、
前記各上位排他木には、節点数に第１の値を乗じたスコアが与えられ、前記各排他木には、第１の値未満のスコアがそれぞれ与えられている、
請求項１に記載の機械翻訳解析結果選択装置。

【図１】

【図２】

【図３】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

【図１１】

【図１２】

【図１３】

【図１４】

【図１５】

【図１６ａ】

【図１６ｂ】

【図１７】

【図１８】

【図１９】

【図２０】

【図２１ａ】

【図２１ｂ】

【図２２】

【図２３】

【図２４】

【図２５】

【図２６】

【図２７】

【図２８】

【図２９】

【図３０】

【図３１】

【図３２】

【図３３】

【図３４】

【図３５】

【図３６】

【図３７】

【図３８】

【図３９】

【図４０】

【図４１】

【図４２】

【図４３】

【図４４】

【図４５】

【図４６】

【図４７】

【図４８ａ】

【図４８ｂ】

【図４９】

【図５０】

【図５１】

【図５２】

【図５３】

【公開番号】特開２００８−１８１５５４（Ｐ２００８−１８１５５４Ａ）
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願番号】特願２００８−６９４７８（Ｐ２００８−６９４７８）
【出願日】平成２０年３月１８日（２００８．３．１８）
【分割の表示】特願２０００−８３８２０（Ｐ２０００−８３８２０）の分割
【原出願日】平成１２年３月２４日（２０００．３．２４）
【出願人】（５００１３２２１４）学校法人明星学苑 (23)
【出願人】（５００１３２２２５）
【Ｆターム（参考）】