JPH077399B2

JPH077399B2 - 言語処理法

Info

Publication number: JPH077399B2
Application number: JP61273880A
Authority: JP
Inventors: 和彦尾関
Original assignee: Japan Broadcasting Corp
Current assignee: Japan Broadcasting Corp
Priority date: 1986-11-19
Filing date: 1986-11-19
Publication date: 1995-01-30
Anticipated expiration: 2010-01-30
Also published as: JPS63128467A

Description

【発明の詳細な説明】［産業上の利用分野］本発明は、日本語連続音声認識装置や、べた書き仮名漢
字変換方式の日本語ワードプロセッサなどに用いる言語
処理法に関するものであり、さらに詳しくは、様々な文
字位置を仮名表記始端および仮名表記終端とする複数の
文節候補、すなわち、いわゆる文節ラティスが与えられ
たとき、それらの候補の確実度と、文節間の係り受けの
整合度を考慮に入れ、日本語の句あるいは文として最適
な文節例が構成されるように文節候補から文節を選択す
ると共にその最適な構文を決定し、かつそれにより得ら
れる最適文節例上の最適構文の日本語の句あるいは文と
しての適格度を計算する技術に関するものである。

［従来の技術］日本語連続音声認識やべた書き仮名漢字変換方式日本語
ワードプロセッサにおいて、適切な最終的処理結果を得
るためには、（Ａ）形態素分割による多義性（Ｂ）同音語による多義性の２つの多義性を解消しなければならない。仮名文字列
が与えられたとき、それが文節をなすかどうかを判定す
ること、また文節をなすならば、その仮名文字列を仮名
表記として持つ同音文節を全て列挙することは、文節を
入力単位とする従来の日本語ワードプロセッサで既に行
われているように、単語辞書と文節内での単語接続規則
を用いて、自動的に行うことができる。従って、上述の
多義性は次のように言い換えてもよい。

（Ａ′）与えられた仮名文字列を文節単位に区切る区切
り方の多義性（Ｂ′）文節単位に区切られた各部分仮名文字列を仮名
表記とする同音文節が複数個存在することからくる多義
性以上のような多義性を解消し、妥当な文節単位の区切り
と、区切られた各部分文字列を仮名表記として持つ適切
な文節を定める問題は、これまで主に日本語ワードプロ
セッサの分野で研究されてきた。以下にかかる従来技術
について述べる。

（１）与えられた仮名文字列を文節単位に区切る方法と
して、二文節最長一致法がある（牧野寛、木沢誠：情報処理学会論文誌、vol.20,No.4,pp.337−345（197
9）。これは、連続する二文節の長さを分かち書きの尺
度とし、二文節形として最長の解釈を与える区切りを二
文節間の境界と認定する方法である。

（２）同じく仮名文字列を文節単位に区切る方法とし
て、文節数最小法が知られている（吉村賢治、日高達、
吉田将：文節数最小法を用いたべた書き日本語文の形態
素解析、情報処理学会論文誌、vol.24,No.1,pp.40−46
（1983）。これは、与えられた仮名文字列を文節単位に
区切ったときにできる文節の個数が最小になるような区
切り方を、最適な区切り方とする方法である。

以上の二つの方法は、いわゆるヒューリスティックな方
法であり、最適な区切り方の基準に明確な根拠があるわ
けではない。また、文節単位に区切られた仮名文字列を
仮名表記とする複数の文節候補から適切な文節を自動的
に選択する機能はなく、従来の、文節単位で分かち書き
して入力するワードプロセッサと同様に、単語の使用頻
度の情報を用いて、複数の文節候補に順位を付けて出力
し、後は使用者の選択に任せる等の処置が必要になる。

（３）与えられた仮名文字列を二文節最長一致法で文節
単位に区切った後、文節間の係り受け解析を行って、文
節候補の中から構文的に最も適切な文節を選択する方法
がある（牧野寛、木沢誠：べた書き文の仮名漢字変換シ
ステムとその同音語処理、情報処理学会論文誌、Vol.2
2,No.1,pp.59−67（1981））。この方法は、文節候補か
ら出力すべき文節を選択するに当たって、日本語の構造
を利用している点で、上記（１），（２）の方法より優
れている。しかし、二文節最長一致法自体がヒューリス
ティックな方法であり、常に最適な文節単位への区切り
方が得られるとは限らないこと、また、処理を簡単にす
るため、係り受けの関係は規則的に許される限り、最も
近い文節間で成立するという、現実には満たされないこ
ともあるヒューリスティックスを用いているという問題
がある。

上記（Ａ′），（Ｂ′）の多義性を解消するためには、
理想的には、与えられた仮名文字列を文節単位に区切る
あらゆる可能な区切り方、および、その際の文節単位に
区切られた部分仮名文字列を仮名表記とする文節からな
る、あらゆる可能な文節列の中から、日本語の文あるい
は句としての適格性と、単語の使用頻度などから得られ
る各文節の確実度の双方を考慮して、最適な区切り方
と、その区切り方における最適な文節例を選択すべきで
ある。この考え方を採ったものに次の論文がある。

（４）大島義光、阿部正博、湯浦克彦、武市宣之：格文
法による仮名漢字変換の多義解消、情報処理学会論文
誌、Vol.27,No.7,pp.679−687,（1986）。

しかし、この方法においては、枚挙法で処理を行おうと
しているため、計算量が膨大になってしまうので、結
局、構文解析を行う前に局所的な情報により文節列の数
を絞らなければならず、あらゆる可能性の中から最適な
ものを選択するという本来の考え方が生かされないとい
う問題があった。

文節集合の列が与えられた時、文節間の係り受けの整合
度と、各文節の確実度の双方を考慮して最適な文節例を
選択するアルゴリズムについては次の文献に記された方
法がある。

（５）尾関和彦：最適文節列を選択するための多段決定
アルゴリズム、電子通信学会音声研究会資料、SP86−3
2,（1986−７）このアルゴリズムを用いれば高速で最適文節列を選択す
ることができる。しかし、文節集合の列が与えられてい
るということは、仮名文字列の文節単位への区切りがた
だ一つに固定されている、ということと等価であるの
で、区切り方をも可能な範囲ですべて動かして最適解を
求める必要がある、ここでの問題にそのまま適用するこ
とはできない。

［発明が解決しようとする問題点］仮名文字列が与えられたとき、それから文節と認定でき
る部分仮名文字列をすべて切りだし、そのような各部分
列を仮名表記として持つ文節をすべて列挙すると、様々
な仮名文字位置を仮名表記始端、仮名表記終端とする文
節の集合が得られる。このような文節の集合は文節ラテ
ィスと呼ばれている。文節ラティスは、連続音声中から
文節として認められる区間を切り出す方式の連続音声認
識装置の出力としても得られる。文節ラティスという言
葉を用いると、本発明が取り扱う問題は、「文節ラティスが与えられたとき、その中の文節を、終
端と始端が仮名文字位置として連続するという条件を満
たすように並べてできるあらゆる文節列を作り、その中
から日本語の文、あるいは句としての適格性と、各文節
の確実度の双方を考慮して、最も妥当な文節列を選択せ
よ」と述べることができる。

これを実行する上での問題点と、本発明の目的を述べる
ために、まず、この問題の厳密な定式化を行う。

ここではminが入った数式にまぎれがないよう、通常用
いられている min f（ｘ）ｘに関する条件という記法の代りに、 min（ｘに関する条件）［ｆ（ｘ）］を用いる。但し、混乱の恐れがないときには［、］は省
略することもある。

argmin、Σ，∪，等についても同様の記法を用いる。

以下［E2］までは文献（尾関和彦：最適文節列を選択す
るための多段決定アルゴリズム、電子通信学会音声研究
会資料、SP86−32,（1986−７）に述べられていること
であるが、説明上必要なのでここに掲げておく。

日本語の文、あるいはまとまった句は、文節という単位
の間の広義の修飾関係によって成り立っていると考える
ことができる。文節ｘが文節ｙを修飾するとき、ｘはｙ
に係り、ｙはｘを受けるという。また、このような修飾
関係を係り受けという。文節列が日本語のまとまった
句、あるいは文を構成するためには、それらの文節間
に、次のような条件を満たす係り受けが存在することが
必要であると考えられている。

［C1］最後の文節以外の文節は、それより後ろにある文
節のいずれか一つに係る。

［C2］二つの文節間の係り受けは、他の二つの文節間の
係り受けと交差しない。

［C3］二つの文節間に係り受けが存在し得るためには、
それらの文節の種類や意味が互いに一定の関係を待たな
ければならない。

与えられた文節列が正しい日本語の場合には、このよう
な手法で構文解析を行なうことができるが、話し言葉
や、音声認識装置の出力にありがちな、誤りを含む文節
列に対しては、解析が行き詰まってしまうことがある。

そこで、上の条件［C3］を、もっと柔軟な条件［Ｃ′３］二つの文節x,yの組に対して、それらの文節
を構成する単語の品詞や意味によってｘがｙに代ること
の整合度を表わす数値が与えられている。

で置き換え、整合度の和が最大あるいは最小になる構文
を探索する方法がある。次はこれについて説明する。

条件［C1］，［C2］は、つぎのように定義される、「構
文」によって表わすことができる。

［D1］（１）ｘが文節のとき、（ｘ）は「構文」であ
る。

（２）X₁,X₂,…,Xmが「構文」、ｘが文節のとき、（X₁X
₂…Xmx）は「構文」である。

［D2］文節列x₁,x₂,…xnに適切に括弧を付け、構文にな
るようにしたものを、x₁x₂…xn上の構文という。文節列
x₁x₂…xn上の構文の全体をＫ（x₁x₂…xn）と表わすことにする。

条件［C3′］に関しては、文節ｘが文節ｙに係ることの
整合度が非負の値をとる関数 PEN（x,y）で表わされるものとする。PEN（x,y）の値は、０に近い
ほど整合度が高いことを表わすものと約束しておく。関
数PENをどうのように定めるかは、非常に重要な問題で
あるが、これは従来から既に考えられていることであ
り、本発明の主眼点ではないので、その説明を省く。

構文Ｘの適格度Ｐ（ｘ）を次のように再帰的に定める。

［D3］（１）Ｘ＝（ｘ），（ｘは文節）のとき、Ｐ
（Ｘ）＝0, （２）Ｘ＝（Y₁Y₂…Ymx）,Y₁＝（…y₁）,Y₂＝（…
y₂），…,Ym＝（…ym）のとき、Ｐ（Ｘ）＝Ｐ（Y₁）＋Ｐ（Y₂）＋…＋ｐ（Ym）＋PEN（y₁,x）＋PEN（y₂,x）＋…＋PEN（ym,x）このように定義されたＰ（Ｘ）の値は、Ｘの中のあらゆ
る係り受けに対するPENの値を加算したものになってい
る。

X,Yが構文で、Ｙ＝（Z₁Z₂…Zmy）、但し、Z₁,…,Zmは構
文で、ｘは文節）とするとき、ＸをＹの先頭に挿入して
できる構文（X Z₁Z₂…Zmy）をＸＹと書くと、［E1］Ｘ＝（…ｘ）,Y＝（…ｙ）に対して、Ｐ（ＸＹ）＝Ｐ（Ｘ）＋Ｐ（Ｙ）＋PEN（x,y）が成り立つ。また、［E2］任意の文節列x₁x₂…xnに対して（１）ｎ＝１のときＫ（x₁）＝（x₁）（２）ｎ＞１のときＫ（x₁x₂…xn）＝∪（１≦ｋ≦ｎ−１）｛ＸY|X∈Ｋ（x₁x₂…xk），Ｙ∈Ｋ（xk₊₁xk₊₂…xn）｝が成り立つ。

［D4］A₁,A₂,…,Amを文節の集合とするとき KB（A₁,A₂,…,Am）＝｛X|^∃x₁∈A₁,^∃x₂∈A₂,…，^∃xm∈Am,X∈Ｋ（x₁x₂…
xm）｝と定義する。KB（A₁,A₂,…,Am）は、A₁,A₂,…,Am
から一つずつ文節を選んでできるあらゆる文節列上のあ
らゆる構文の全体である。

［D5］（１）整数列i,i＋1,…,jのｍ分割とは、ｉ−１＝s₀＜s₁＜s₂＜…＜sm＝ｊを満たす整数の組（s₀,s₁,s₂,…,sm）をいう。

（２）整数列i,i＋1,…,jのｍ分割の全体をDm（i,j）と
書く： Dm（i,j）＝｛（s₀,s₁,s₂,…,sm）|i−１＝s₀＜s₁＜s₂
＜…＜sm＝ｊ｝（３）更に、整数列i,i＋1,…,jの分割の全体Ｄ（i,j）
を、次のように定義する。

Ｄ（i,j）＝∪（１≦ｍ≦ｊ−ｉ＋１）［Dm（i,j）］さて、次の状況を考える：［J1］１から自然数Ｎまでの仮名文字位置を考え、各i,
j（１≦ｉ≦ｊ≦Ｎ）に対してｉを仮名表記始端位置、
ｊを仮名表記終端位置とする文節の集合Ｂ（i,j）が与
えられている。また、各文節ｘに対して、非負の実数値
Ｓ（ｘ）が定められている。

同じ文節でも仮名表記始端位置あるいは仮名表記終端位
置が異なれば、別の文節として取り扱う。

上記のＢ（i,j），（１≦ｉ≦ｊ≦Ｎ）全体を文節ラテ
ィスという。べた書き入力仮名漢字返換方式日本語ワー
ドプロセッサを例にとると、仮名文字列a₁a₂…a_Nが与え
られたとき、Ｂ（i,j）はその部分列aiai₊₁…ajを仮名
表記として持つ文節の全体である。Ｓ（ｘ）は、単語の
使用頻度などの情報から定まる、文節ｘの確実度を表わ
す数値で、０に近いほど確実度が高いとしておく。ま
た、連続音声認識を例にとれば、Ｂ（i,j）は仮名文字
位置i,jをそれぞれ始端位置、終端位置とする区間の認
識結果候補として装置が出力する文節の集合である。こ
の場合、Ｓ（ｘ）は認識装置が、ｘという認識結果をど
の程度の確からしさで認識したかという確実度を示す数
値であり、大抵の音声認識装置はそのような数値を認識
結果と共に出力するようになっている。いずれの場合
も、仮名文字位置i,jを始端，終端とする文節が存在し
ないことがあるので、Ｂ（i,j）は空集合になりうる。
この場合も特別な取扱いをしなくて済むように、Ｂ（i,
j）が空集合のときはダミー文節を加えておき、ダミー
文節に対するＳの値は∞と約束しておく。また、ｘある
いはｙの少なくとも一方がダミー文節のとき、PEN（x,
y）の値も∞と約束しておく。

また、Ｓを構文にも適用できるよう拡張しておく。すな
わち、Ｘ∈Ｋ（xixi₊₁…xj）に対してＳ（Ｘ）＝Σ（ｉ≦ｍ≦ｊ）［Ｓ（xm）］と定義する。

このような状況のもとで、本発明が取扱う問題は次のよ
うに述べることができる。仮名文字位置1,2,…,Nを固定
し、その分割（s₀,s₁,s₂,…,sm）∈Ｄ（1,N）を一つ選ぶ。この分割に対応して、文節の集合列Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,sm）が定まる。各文節集合Ｂ（sk_-1＋1,sk）から文節xkを一
つずつ選ぶと、その上の構文の全体Ｋ（x₁x₂…xm）が定まる。Ｋ（x₁x₂…xm）の中から構文Ｘを一つ選ぶ
と、その適格度と確実度の和Ｐ（Ｘ）＋Ｓ（Ｘ）が定まる。そこで、上記の分割、文節、および構文を可
能な範囲で全て動かし、Ｐ（Ｘ）＋Ｓ（Ｘ）を最小にす
るような分割、文節、および構文を選択する。すなわ
ち、 min（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［min（x₁∈Ｂ（s₀＋1,s₁）,x₂∈Ｂ（s₁＋1,s₂），…， xm∈Ｂ（sm_-1＋1,sm））［min（Ｘ∈Ｋ（x₁x₂…xm））［Ｐ（Ｘ）＋Ｓ（Ｘ）］］］を達成するような各変数の値と、それに対する最小値を
求めるというのが、ここでの問題である。

最適文節列を選ぶためには、文節列の日本語の文あるい
は句としての適格性を考慮しなければならないので、結
局は上記のように最適な構文をも求める問題になる。逆
に最適な構文が求まれば、それを構成する文節列は定ま
るので、 min（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N）） min（x₁∈Ｂ（s₀＋1,s₁）,x₂∈Ｂ（s₁＋1,s₂），…， xm∈Ｂ（sm_-1＋1,sm））min（Ｘ∈Ｋ（x₁x₂…xm））［Ｐ（Ｘ）＋Ｓ（Ｘ）］＝min（Ｘ∈∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,
sm））］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］に注意して、上の問題を、次のように構文を変数とする
問題として書き直す。

［P1］（１） min（Ｘ∈∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,
N））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,
sm））］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］と（２） argmin（Ｘ∈∪（（s₀,s₁,s₂,…,sm）∈ Ｄ（1,N））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），
…，Ｂ（sm_-1＋1,sm））］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］を求めよ。

従来、この問題を解こうとすれば枚挙法、すなわち、集
合 ∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,
sm））］）の全ての元Ｘに対してＰ（Ｘ）＋Ｓ（Ｘ）を逐一計算
し、最小値を与えるＸとそれに対する最小値を求めなけ
ればならなかった。枚挙法によると、各Ｂ（i,j）の文
節数をＪ、全体の仮名文字列長さをＮとするとき、必要
な加算演算回路数は、 Σ（１≦ｊ≦Ｎ）_N-1Cj_-1・Jj・Ｌ（ｊ）・（2j−１）または比較演算回数は Σ（１≦ｊ≦Ｎ）_N-1Cj_-1・Jj・Ｌ（ｊ）ま与えられる。ここで、_N-1Cj_-1は２項係数、また、Ｌ
（ｊ）は長さｊの文節列上の構文の数であり、で計算することができる。

上式をいくつかのＪおよびＮについて計算したものを第
１表に示す。これから分かるように、枚挙法において
は、計算量が文字列長に対して指数関数的に増加して、
たちまち膨大なものになるので、これを実際問題に適用
することは極めて困難であった。そこで、本発明の目的
は、このような従来技術の欠点を改善し、計算量が文字
列長および、各文節集合の元の数に関して多項式のオー
ダーであるような、従来法と比較して格段に効率の良い
言語処理法を提供することにある。

［問題点を解決するための手段］（５−１）基本的な再帰方程式本発明の構成について説明するにあたり、本発明におい
て基本的な役割を果たす再帰方程式について述べる。ま
ず、次の定義を設ける。

［D6］自然数Ｎを固定し、１≦ｉ≦ｍ≦ｊ≦N,X∈Ｂ
（m,j）に対して（１）OPTPS（i,j,m,x）＝min（Ｘ∈∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］但し、ｍ＝ｉのときはＤ（i,m−１）が定義されていな
いが ∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝］＝KB（｛ｘ｝）と約束しておく。

（２）OPTKS（i,j,m,x）＝argmin（Ｘ∈∪（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−
１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］上記（２）において、Ｐ（Ｘ）＋Ｓ（Ｘ）を最小にする
Ｘは一般に複数個あるので、OPTKS（i,j,m,x）は集合と
なる。

本発明において基本的な役割を果たすのは、OPTPSとOPT
KSが満たす次の２つの再帰方程式［T1］，［T2］であ
る。

［T1］１≦ｉ≦ｍ≦N,x∈Ｂ（m,j）に対して（１）ｉ＝ｍのとき OPTPS（i,j,m,x）＝Ｓ（ｘ）（２）ｉ＜ｍのとき OPTPS（i,j,m,x）＝min（ｉ≦ｎ≦ｋ≦ｍ−１）［min（ｙ∈Ｂ（n,k））［OPTPS（i,k,n,y）＋OPTPS（ｋ＋1,j,m,x）＋PEN（y,
x）］［T2］１≦ｉ≦ｍ≦ｊ≦N,X∈Ｂ（m,j）に対して（１）ｉ＝ｍのとき OPTKS（i,j,m,x）＝｛（ｘ）｝（２）ｉ＜ｍのとき、［T1］の（２）で最小値を与える
n,k,yの組（n,k,y）の集合を KTS（i,j,m,x）と書くと OPTKS（i,j,m,x）＝∪（n,k,y）∈KTS（i,j,m,x））［｛ＸY|X∈OPTKS（i,k,n,y），Ｙ∈OPTKS（ｋ＋1,j,m,x）｝］以下、これらの再帰方程式が成立することを説明する。
そのために、まず、次の［E3］を示す。

［E3］ ∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］＝∪（ｉ≦ｎ≦ｋ≦ｍ−１）∪（ｙ∈Ｂ（n,k））｛ＹX|Y∈∪（（u₀,u₁,u₂…uq）∈Ｄ（i,n−１））［KB（Ｂ（u₀＋1,u₁）,B（u₁＋1,u₂），…,B（uq_-1＋1,
uq），｛ｙ｝）］,X∈∪（（v₀,v₁,v₂…,vr）∈Ｄ（ｋ＋1,m＋
１））KB （Ｂ（v₀＋1,v₁）,B（v₁＋1,v₂），…,B（vr_-1＋1,v
r），｛ｘ｝）｝これは次のようにして示される。

Ｚ∈∪（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］とする。そうすると、（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−
１））と、x₁∈Ｂ（s₀＋1,s₁）,x₂∈Ｂ（s₁＋1,s₂），
…,xp∈Ｂ（sp_-1＋1,sp）が存在して、Ｚ∈Ｋ（x₁x₂…xpx）が成り立つ。［E2］により、１≦ｔ≦ｐとＹ∈Ｋ（x₁x₂
…xt）,X∈Ｋ（xt₊₁xt₊₂…xpx）が存在してＺはＺ＝ＹX, と書ける。

ｎ＝st_-1＋1,k＝st,y＝xt とおくとｉ≦ｎ≦ｋ≦ｍ−1,y_∈Ｂ（n,k），Ｙ∈∪（（u₀,u₁,u₂…,uq）∈Ｄ（i,n−１））［KB（Ｂ（u₀＋1,u₁）,B（u₁＋1,u₂），…,B（uq₊₁＋1,
uq），｛ｙ｝）］，Ｘ∈∪（（v₀,v₁,v₂…,vr）∈Ｄ（ｋ＋1,m＋１）［KB（Ｂ（v₀＋1,v₁）,B（v₁＋1,v₂），…,B（vr_-1＋1,
vr），｛ｘ｝）］従って、Ｚ∈∪（ｉ≦ｎ≦ｋ≦ｍ−１）∪（ｙ∈Ｂ（n,k））
｛ＹX| Ｙ∈∪（（u₀,u₁,u₂…,uq）∈Ｄ（i,n−１））［KB（Ｂ
（u₀＋1, u₁）,B（u₁＋1,u₂），…,B（uq_-1＋1,uq），
｛ｙ｝）］，Ｘ∈∪（（v₀,v₁,v₂…,vr）∈Ｄ（ｋ＋1,m＋１））［KB（Ｂ（v₀＋1,v₁）,B（v₁＋1,v₂），…,B（vr_-1＋1,
vr），｛ｘ｝）｝となり、左辺は右辺に含まれることが分かる。右辺が左
辺に含まれることを同様にして示される。

次に、［E3］を用いて、［T1］を示す。

OPTPS（i,j,m,x）＝min（Ｚ∈∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］）［Ｐ（Ｚ）＋Ｓ（Ｚ）］（定義による）＝min（ｉ≦ｎ≦ｋ≦ｍ−１）min（ｙ∈Ｂ（n,k））min
｛Ｙ∈∪ （（u₀,u₁,u₂…,uq）∈Ｄ（i,n−１））［KB（Ｂ（u₀＋
1,u₁）,B （u₁＋1,u₂），…,B（uq_-1＋1,uq），｛ｙ｝）］，Ｘ∈∪（（v₀,v₁,v₂…,vr）∈Ｄ（ｋ＋1,m−１））［KB（Ｂ（v₀＋1,v₁）,B（v₁＋1,v₂），…,B（vr_-1＋1,
vr），｛ｘ｝）］）［Ｐ（ＹＸ）＋Ｓ（ＹＸ）］（E3による）＝min（ｉ≦ｎ≦ｋ≦ｍ−１）min（ｙ∈Ｂ（n,k））min
｛Ｙ∈∪ （（u₀,u₁,u₂…,uq）∈Ｄ（i,n−１））［KB（Ｂ（u₀＋
1,u₁）,B （u₁＋1,u₂），…,B（uq_-1＋1,uq），｛ｙ｝）］，Ｘ∈∪（（v₀,v₁,v₂…,vr）∈Ｄ（ｋ＋1,m−１））［KB（Ｂ（v₀＋1,v₁）,B（v₁＋1,v₂），…,B（vr_-1＋1,
vr），｛ｘ｝）］）［Ｐ（Ｙ）＋Ｐ（Ｘ）＋PEN（y,x）＋Ｓ
（Ｙ）＋Ｓ（Ｘ）］（E1による）＝min（ｉ≦ｎ≦ｋ≦ｍ−１）［min（ｙ∈Ｂ（n,k））［OPTPS（i,k,n,y）＋OPTPS（ｋ＋1,j,m,x）＋PEN（y,
x）］これで［T1］が示された。次に［T2］を示す。（１）は
定義から明らかであるので（２）を示す。まず、Ｘ∈∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］に対して、Ｘ∈OPTKS（i,j,m,x）と（Ｐ（Ｘ）＋Ｓ（Ｘ）＝OPTPS
（i,j,m,x））は同値であることに注意しておく。

さて、（２）を示すには、（ａ）OPTKS（i,j,m,x） ⊃∪（（n,k,y）∈KTS（i,j,m,x））［｛ＹX|Y∈OPTKS（i,k,n,y），Ｘ∈OPTKS（ｋ＋1,j,m,x）｝］（ｂ）OPTKS（i,j,m,x） ⊂∪（（n,k,y）∈KTS（i,j,m,x））［｛ＹX|Y∈OPTKS（i,k,n,y），Ｘ∈OPTKS（ｋ＋1,j,m,x）｝］の２つを示せばよい。（ａ）は次のように示される。

Ｚ∈∪（（n,k,y）∈KTS（i,j,m,x））［｛ＹX|Y∈OPTKS（i,k,n,y），Ｘ∈OPTKS（ｋ＋1,j,m,x）｝］とすれば、（n,k,y）∈KTS（i,j,m,x），Ｙ∈OPTKS（i,k,n,y），Ｘ∈OPTKS（ｋ＋1,j,m,x）が存在してＺ＝ＹＸと書ける。当然、Ｚ∈∪（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］であり、Ｐ（Ｚ）＋Ｓ（Ｚ）＝Ｐ（ＹＸ）＋Ｓ（ＹＸ）＝Ｐ（Ｙ）＋Ｐ（Ｘ）＋PEN（y,x）＋Ｋ（Ｙ）＋Ｓ
（ｘ）＝Ｐ（Ｙ）＋Ｓ（Ｙ）＋Ｐ（Ｘ）＋Ｓ（Ｘ）＋PEN（y,
x）＝OPTPS（i,k,n,y）＋OPTPS（ｋ＋1,j,m,x）＋PEN（y,
x）＝OPTPS（i,j,m,x）従って、Ｚ∈OPTKS（i,j,m,x）（ｂ）は次のように示される。

Ｚ∈OPTKS（i,j,m,x）とする。

Ｚ∈∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,m−１））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］であるから、［E3］によりｉ≦ｎ≦ｋ≦ｍ−1,y∈Ｂ（n,k），Ｙ∈∪（（u₀,u₁,u₂…,uq）∈Ｄ（i,n−１））［KB（Ｂ
（u₀＋1, u₁）,B（u₁＋1,u₂），…,B（uq_-1＋1,uq），
｛ｙ｝）］，Ｘ∈∪（（v₀,v₁,v₂…,vr）∈Ｄ（ｋ＋1,m−１））［KB（Ｂ（v₀＋1,v₁）,B（v₁＋1,v₂），…,B（vr_-1＋1,
vr），｛ｘ｝）］が存在して、Ｚ＝ＹＸと書ける。ところが、Ｐ（Ｚ）＋Ｓ（Ｚ）＝Ｐ（Ｙ）＋Ｐ（Ｘ）＋Ｓ（Ｙ）＋
Ｓ（Ｘ）＋PEN（y,z）であり、Ｚは左辺を最小とするから、ＹとＸも右辺を最
小にしなければならない。従って、［T1］の証明から分
るように、（n,k,y）∈KTS（i,j,m,x）Ｙ∈OPTKS（i,k,n,y）,E∈OPTKS（ｋ＋1,j,m,x）｝］よってＺ∈∪（（n,k,y）∈＝KTS（i,j,m,x））［｛ｘY|X∈＝OPTKS（i,k,n,y），Ｙ∈OPTKS（ｋ＋1,j,m,x）｝］これで［T2］が示された。

OPTPS（i,j,m,x）は４つの変数i,j,m,xを持っている。
しかし、ｍは文節ｘの始端位置であり、ｘを定めれば、
自動的に定まる。そこで、［D7］（１）Ｉ（ｘ）＝（文節ｘの始端位置）（２）Ｂ（i,j）＝∪（ｉ≦ｋ≦ｊ）Ｂ（k,j）（３）ｘ∈Ｂ（i,j）に対して OPT（i,j,x）＝OPTPS（i,j,I（ｘ）,x）と定義すると、［T1］は次のように書き直すことができ
る。

［T1′］１≦ｉ≦ｊ≦N,x∈Ｂ（i,j）に対して（１）ｉ＝Ｉ（ｘ）のとき OPT（i,j,x）＝Ｓ（ｘ）（２）ｉ＜Ｉ（ｘ）のとき OPT（i,j,x）＝min（ｉ≦ｋ≦Ｉ（ｘ）−１）［min（ｙ∈Ｂ（i,
k））［OPT（i,k,y）＋OPT（ｋ＋1,j,x）＋PEN（y,x）］また、OPTKSについても同様に［D8］１≦ｉ≦ｊ≦N,x∈Ｂ（i,k）に対して OPTK（i,j,k）＝OPTKS（i,j,I（ｘ）,x）と定義を直し、［D9］［T1′］（２）において最小値を与えるk,yの組
（k,y）の集合を、 KT（i,j,x）と書くと、［T2］も次のように書き直すことができる。

［T2′］１≦ｉ≦ｊ≦N,x∈Ｂ（i,k）に対して（１）ｉ＝Ｉのとき OPTK（i,j,x）＝｛（ｘ）｝（２）ｉ＜Ｉ（ｘ）のとき、 OPTK（i,j,x）＝∪（（k,y）∈KT（i,j,x））［｛ＹX|Y∈OPTK（i,k,y），Ｘ∈OPTK（ｋ＋1,j,x）｝］ KT（i,j,x）の元（k,y）について、ｋを、i,j,xに対す
る最適区分点、ｙを最適文節という。

（５−２）OPTおよび最適区分点と最適文節の組の決定
法［T1′］（１）はＩ（ｘ）＝ｉのとき、OPT（i,j,x）の
値がＳ（ｘ）として定まること、また、［T1′］（２）
は、Ｉ（ｘ）＞ｉのとき、OPT（i,k,y）とOPT（ｋ＋1,
j,x），（ｉ≦ｋ≦Ｉ（ｘ）−1,y∈Ｂ（i,k）がすでに
計画されていれば、１変数関数の最小化問題を２回解く
ことによりOPT（i,j,x）が計算できることを示してい
る。これらの事実を用いると、ｊ−１が０部分からOPT
（i,j,x）の計算を始めて、順次ｊ−ｉがより大きいOPT
（i,j,x）、（１≦ｉ≦ｊ≦N,x∈Ｂ（i,k））へと計算
を進め、それと同時に最適区分点と最適文節の組を決定
して行くことができる。OPT（1,N,x）、（ｘ∈Ｂ（i,
k））が計算されたとき、OPTおよび、最適区分点と最適
文節の組の計算が終了する。

（５−３）最適構文の計算法簡単のために、最適区分点と最適文節の組が常に一意的
に定まる場合について説明する。

このとき、OPTK（i,j,x）はただ一つの構文に等しい。

先ず、 min（Ｘ∈∪（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（Sm_-1＋1,
sm））］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］＝min（ｘ∈Ｂ（1,N））［OPT（1,N,x）］であるから、この右辺を計算することにより、最適な文
節列上の最適な構文に対する適格度が計算される。ま
た、 x₀＝argmin（ｘ∈Ｂ（1,N））［OPT（1,N,x）］とすれば、最適文節列とその上の最適構文は、 OPTK（1,N,x₀）で与えられる。これをさらに具体的に計算するには次の
ようにすればよい。もし、Ｉ（x₀）＝１ならば、［T
2′］の（１）によって OPTK（1,N,x₀）＝（x₀）であるから、これにより最適構文が決定される。

Ｉ（x₀）≠ならば、1,N,x₀に対する最適区分点と最適文
節番号の組をそれぞれ（k₁,x₁）とすれば、［T2′］の
（２）によって OPTK（1,N,x₀）＝OPTK（1,k₁,x₁）OPTK（k₁＋1,N,x₀）が成り立つ。もし、Ｉ（x₁）≠１ならば、さらにOPTK
（1,k₁,x）は1,k₁,xに対する最適区分点k₂と最適文節x₂
を用いて、 OPTK（1,k₁,x₁）＝OPTK（1,k₂,x₂）OPTK（k₂＋1,k₁,x₁）と分解できる。OPTK（k₁＋1,N,x₀）についてもＩ（x₀）
≠k₁＋１ならば同様にして、k₁＋1,N,x₀に対する最適区
分点k₃、最適文節x₃を用いて OPTK（k₁＋1,N,x₀ ＝OPTK（k₁＋1,k₃,x₃）OPTK（k₃＋1,N,x₀）と分解できる。したがって、 OPTK（1,N,x₀）＝（OPTK（1,k₂,x₂）OPTK（k₂＋1,N,x₁））（OPTK（k₁＋1,k₃,x₃）OPTK（k₃＋1,N,x₀））このような分解操作を、出現するOPTK（i,j,x）の全て
においてＩ（ｘ）＝ｉになるまで行い、Ｉ（ｘ）＝ｉに
なったところで［T2′］の（１）を用いて、ただ一つの
文節からなる構文に置き換え、分解の逆をたどって挿入
操作を行えば、最適な文節列と、その文節列の上の最適
な構文が同時に得られる。

最適区分点と最適文節の組が複数個存在するときは、そ
れらの組すべてについて同様の操作を行い、構成された
構文すべてをOPTK（1,N,x₀）の元とすればよい。

このように、本発明は、１からＮまでの自然数で決る仮
名文字位置と、仮名表記始端位置および仮名表記終端位
置が１からＮまでの範囲内の様々な位置にある文節の集
合と、それら文節の確実度を表わす数値が与えられたと
き、２文節間の係り受けの整合度と各文節の確実度を表
わす数値の総和を最小化あるいは最大化するという最適
基準の下で、最初の文節の仮名表記始端位置が１に等し
く、最後の文節の仮名表記終端位置がＮに等しく、か
つ、最終文節以外の文節の仮名表記終端位置に１を加え
た値が次の文節の仮名表記始端位置に等しいという条件
を満たすようにそれら文節を並べてできるあらゆる文節
列の中から、最適な文節列と、その文節列の最適構文、
およびその適格度を定める言語解析方式において、Ｎに
等しい行、列の数を持つ、２次元の上３角行列形の第１
表および第２表を用意し、第１表および第２表の各桝目
を、仮名表記終端位置がその列番号に等しく、かつ仮名
表記始端位置がその行番号以上であるような文節の数だ
けの項に分割して、第１表および第２表を３次元化し、
仮名表記始端位置が自然数ｉ以上であり、かつ仮名表記
終端位置が自然数ｊであるような文節集合中のｑ番目の
文節について、その仮名表記始端位置がｉに等しいとき
には第１表の第ｉ行，第ｊ列、第ｑ項にその文節の確実
度を格納し、自然数ｋがｉから始まって、仮名表記始端
位置がｉ以上で、かつ仮名表記終端位置がｊに等しいよ
うな文節の集合中の第ｑ番目の文節の仮名表記始端位置
より１を減じた値までを動くとき、第１表の第ｉ行，第
ｋ列の各項と、第１表の第ｋ＋１行，第ｊ列，第ｑ項に
計算済みの値を格納し、その格納がなされたならば、計
算済みの、第１表の第ｉ行，第ｋ列，第ｐ項の値と、第
１表の第ｋ＋１行，第ｊ列，第ｑ項の値と、仮名表記始
端位置がｉ以上であり、かつ仮名表記終端位置がｋであ
るような文節集合中の第ｐ番目の文節が、仮名表記始端
位置がｉ以上で、かつ仮名表記終端位置がｊであるよう
な文節集合中の第ｑ番目の文節に係ることの整合度を加
算し、その加算結果のｋおよびｐに関する最小値または
最大値を第１表の第ｉ行，第ｊ列，第ｑ項に格納し、最
小値または最大値を与える最適区分点であるところのｋ
および最適文節番号であるところのｐの値の組を第２表
の第ｉ行，第ｉ列，第ｑ項に格納し、第１表および第２
表を順次計算済みの値で埋めて行き、第１表および第２
表の第１行，第Ｎ列の各項に計算済みの値が格納される
に至ったときに、第１表の第１行，第Ｎ列の各項の中の
最小値または最大値を求めることにより最終的な適格度
と、最終文節の文節番号を得ると共に、最適構文を構成
するために必要な最適区分点および最適文節番号の組の
全体を第２表に得ることを特徴とする。

［作用］本発明では、仮名表記始端および仮名表記終端が１から
ある自然数Ｎまでの範囲の様々な位置にある文節の集
合、すなわち文節ラティス、および、それら各文節の確
実度を示す数値が与えられたとき、２文節間の係り受け
の整合度と、各文節の確実度にもとずいて、上記文節ラ
ティスから最適な文節列を選び、その文節列に対する最
適な構文を決定し、かつその構文の適格度を計算するに
あたって、与えられた２つの自然数決る文字位置をそれ
ぞれ仮名表記始端位置および仮名表記終端位置とし、最
後の文節が固定された文節列の全体の中から、日本語の
句として最も適格度の高い文節列が選ばれ、それに対す
る構文、およびその構文に対する適格度が計算されたな
らば、それを記憶しておき、それを上記の始端および終
端で定まる仮名文字区間を含むような、より長い仮名文
字区間に対して同様の計算を行なう際に利用することに
より、部分的に同じ計算が繰り返し行なわれることを組
織的に避ける。従って、本発明の計算法を、与えられた
文節ラティスに適用することにより、可能な全文節列の
中から、日本語の句、あるいは文として最も適格度の高
い文節列、その上の構文、およびその構文に対する適格
度を、従来法に比べて格段に少ない計算量で計算するこ
とができる。

本発明は、日本語を対象とする場合のみならず、韓国語
のように日本語と同様の文法構造を持つ外国語にも適用
できることは言うまでもない。

［実施例］以下に図面を参照して本発明を詳細に説明する。

以下の説明において、仮名文字位置を1,2,…,Nとする。
文節集合Ｂ（i,j）の元の数を＃（i,j）とし、Ｂ（i,
j）の元をxi,j,₁,xi,j,₂,…,xi,j,_＃（i,j）と表わす。
文節集合Ｂ（i,j）の元の数のi,jに関する最大値をＭと
する。

本発明を実施する装置の一実施例を第１図に示す。

第１図において、SCは入力端子i₁から入力される各文節
の確実度を表わす数値Ｓ（xi,j,q）を保持するRAM,BUF
は文節入力端子i₂から入力される文節集合を保持するRA
Mなどによるバッファメモリである。例えば、本発明を
音声認識に用いるときには、認識装置から出力される文
節ラティスの各文節を端子i₂から入力し、各文節に付随
した確実度を端子i₁から入力する。また、本発明をべた
書き入力仮名漢字変換方式日本語ワードプロセッサに適
用するときには、与えられた仮名文字列a₁,a₂,…a_Nをま
ず従来技術で形態素解析し、部分文字列ai,ai₊₁,…,aj
を仮名表記として持つ文節候補を各i,j（１≦ｉ≦ｊ≦
Ｎ）について全て列挙し、それらを端子i₂から入力す
る。その際、単語の使用頻度などから定まる、各文節の
確実度を端子i₁から入力する。

PEはバッファメモリBUFから読み出した２文節ｘとｙの
間の係り受けの整合度PEN（x,y）を計算する装置であ
る。

T1およびT2は第２図（Ａ）および（Ｂ）に示すフローチ
ャートのテーブルTABLE1およびTABLE2を実現するための
RAMである。

INITは文節xi,j,qの始端位置がｉに等しいか否か、すな
わちＩ（xi,j,q）＝ｉか否かを判定する文節始端位置検
出器である。

SELは、文節xi,j,qの始端位置がｉに等しいことを示す
信号をINITから受け取った時、SCに保持されているＳ
（xi,j,q）を選び出し、T1において実現されているTABL
E1（i,j,q）に書き込むデータ選択装置である。

ADD1はTABLE1（i,k,p）とPEN（xi,k,p,xi,j,q）とを加
算する加算器である。

MIN1は加算器ADD1の出力の、上記ｐを変化させた時の最
小値と、その最小値を与えるｐを検出するための最小値
検出器である。

ADD2は最小値検出器MIN1の出力とTABLE1（ｋ＋1,j,q）
とを加算する加算器である。MIN2は加算器ADD2の出力の
上記ｋを変化させた時の最小値と、その最小値を与える
ｋを検出するための最小値検出器である。

CONTはこれら各部の動作順序を制御するための制御装置
であって、例えば中央処理装置CPUと、各部の制御手順
を予め記憶しておくためのROMの形態のメモリMEM1およ
び作業用のRAMの形態のメモリMEM2を有する。0₁および0
₂はRAM T1およびT2に書き込まれた結果をそれぞれ出力
する出力端子である。

第２図（Ａ）および（Ｂ）は、第１図示の実施例におけ
るメモリMEM1にあらかじめ格納しておく制御手順の一例
としての、最適文節列の上の最適構文の適格度、最適文
節列、およびその上の最適構文を定めるための最適区分
点と最適文節の組を順次求めるための手順を示すフロー
チャートである。以下、これについて説明する。

第２図（Ａ）および（Ｂ）のフローチャートに付随し
て、第３図（Ａ）および（Ｂ）に示すように、想定して
いる文字列の全長Ｎに等しい数の行および列、および文
節集合Ｂ（i,j）の元の数の最大値Ｍに等しい数の項を
持った２つの３次元テーブルTABLE1（i,j,q）,TABLE2
（i,j,q）（１≦ｉ≦ｊ≦N,1≦ｑ≦Ｍ）が必要である。
各テーブルの添字は左から順に行，列，項を表わす。TA
BLE1（i,j,q）はOPT（i,j,xi,j,q）の値を、またTABLE2
（i,j,q）はi,j,xi,j,qに対する最適区分点と最適文節
番号の組を記憶するためのものである。

第２図（Ａ）および（Ｂ）のフローチャートにおいて、
ステップS1からS13において、各テーブルの列番号ｊを
１から始めてＮまで１ずつ増加させ、各列に対して次の
処理を実行する。

ステップS2からS11において、ｉをｊから始めて１まで
１ずつ減少させ、次の処理を実行する。

ステップS3からS9において、ｑを１から始めて＃（i,
j）まで１ずつ増加させ、次の処理を実行する。

（１）ステップS4においてＩ（xi,j,q）＝ｉと判定され
たならば、ステップS7において次のことを実行する。

［F1］TABLE1（i,j,q）：＝Ｓ（xi,j,q）（２）ステップS4においてＩ（xi,j,q）＞ｉと判定され
たならば、ステップS5において次の［F2］、またステッ
プS6において次の［F3］を実行する。

［F2］min（ｉ≦ｋ≦Ｉ（xi,j,q）−１）［min（１≦ｐ
≦＃（i,k））［TABLE1（i,k,p）＋PEN（xi,k,p,xi,j,q）］＋TABLE1（ｋ＋1,j,q）］を求めて、それをTABLE1（i,j,q）に記憶する。［F3］
［F2］で最小値を与えるｋとｐの組（k,p）をTABLE2
（i,j,q）に記憶する。

以上の処理により、TABLE1とTABLE2の各行，列，項に上
述の計算を施し、その結果を順次テーブルに書き込んで
行く。

ステップS13においてｊ＞Ｎとなったとき計算が終了
し、TABLE1（1,N,q）にはOPT（1,N,x₁,_N,q）、（１≦ｑ
≦＃（1,N））が記憶されている。また、TABLE2には最
適区分点と最適文節番号の情報が記憶されているので、
（５−２）項および（５−３）項で述べた方法により、
この情報から最適な文節列と最適構文を構成することが
できる。

本発明を実際に使用するときには、第２図（Ａ）および
（Ｂ）のフローチャートの他にTABLE2の情報から最適な
文節例とその上の最適な構文を構成する機構が必要であ
るが、本発明の主眼点はTABLE1およびTABLE2の内容を計
算するところにあるので、これらの情報から最適な文節
列およびその上の最適な構文を構成する機構については
上記の説明にとどめる。

但し、TABLE1およびTABLE2の内容が計算できていれば、
与えられた文節の集合から最適な文節列およびその上の
最適な構文を構成するために必要な計算の内で最も計算
量の多い部分はもはや終了していることに注意してお
く。

［F2］において最小値を与えるｋおよびｐの組が複数個
存在することがあるが、そのときには、TABLE2（i,j,
q）に複数個の数値の組が記憶できるようにしておき、
［F3］においてそれらを全てTABLE2（i,j,q）に記憶す
るようにすればよい。このように第２図（Ａ）および
（Ｂ）のフローチャートを変更しても計算量には殆ど変
わりがない。

以上述べたように、本発明の特徴は、仮名文字位置i,j
に対応して与えられた文節の集合Ｂ（i,j）（＝１≦ｉ
≦Ｎ）から、最初の文節の仮名表記始端位置が１に等し
く、最後の文節の仮名表記終端位置がＮに等しく、最終
文節以外の文節の仮名表記終端位置に１を加えたものが
それに続く文節の仮名表記始端位置に等しいという条件
を満たすように文節を選んでできるあらゆる文節列の中
で、最終文節x₁,_N,q∈Ｂ（1,N）を一つ固定したときの
最適な文節列とその上の最適な構文およびそれに対する
適格度を求めるに当たって、最初の文節の仮名表記始端
位置がｉに等しく、最後の文節の仮名表記終端位置がｊ
に等しいという条件の下での上記と同様の最後の文節を
固定したときの最適な文節列とその上の最適な構文、お
よびその適格度を、ｊ−ｉが小さいものから順次求めて
それを記憶しておき、しかも最初の文節の仮名表記始端
位置がｉに等しく、最後の文節の仮名表記位置がｊに等
しいという条件の下での上記の諸数値を求めるに当たっ
ては、ｋ＝i,…,I（xi,j,q）−１に対して既に求められ
記憶されている、最初の文節の仮名表記始端位置がｉに
等しく、最後の文節の仮名表記終端位置がｋに等しいと
いう条件の下での上記の諸数値、最初の文節の仮名表記
始端位置がｋ＋１に等しく、最後の文節の仮名表記終端
位置がｊに等しいという条件の下での上記の諸数値、お
よび文節xi,k,p∈Ｂ（i,k）が文節xi,j,q∈Ｂ（i,j）に
係ることの整合度を表わす関数値のみを用いるところに
ある。

OPT（i,j,x）の定義から分かるように、列番号ｊはＮで
あるか、または、あるダミーでない文節の最終文字位置
であり、かつ、あるダミーでない文節の最初の文字位置
から１を減じた値になっているような値以外は意味がな
い。もし、このような意味のない列番号があらかじめ分
かっている時は、そのような列を取り除き、残りの列に
対して、あらためて１から番号を付け直した上で、上記
の処理を行うことにより、更に計算量を減らすことがで
きる。同様にして、行番号ｉは１であるか、または、あ
るダミーでない文節の最初の文字位置であり、かつある
ダミーでない文節の最終文字位置に１を加えた値になっ
ているような値以外は意味がない。もし、このような意
味のない行番号が予め分かっているときは、そのような
行を取り除き、残りの行に対して、あらためて１から番
号を付け直した上で、上記の処理を行うことにより、更
に計算量を減らすことができる。

なお、上述した実施例では、最小値を求める処理の場合
を示したが、これはＳの値が小さいほど確実度が高く、
PENの値が小さいほど係り受けの整合度が高いとしたた
めである。Ｓの値が大きいほど確実度が高く、PENの値
が大きいほど係り受けの整合度が高い場合には、最小値
の変りに最大値を求める処理を行えばよい。

［発明の効果］係り受けの整合度を示す関数PENについては、一度計算
したものを記憶しておくことにすると、従来法と本発明
とで計算量は同じになる。従って、この部分を除外する
と、基本演算は、実数の加算と比較演算であるので、従
来法と本発明を、これらの演算の回数で比較する。

与えられた仮名文字列の全長をＮ、Ｂ（i,j）の元の数
をＪとすると、本発明の上記実施例における加算回数は
次式で与えられる。

２・Ｊ・［Σ（１≦ｊ≦Ｎ）Σ（１≦ｉ≦ｊ−１）Σ
（ｉ＋１≦ｒ≦ｊ）Σ（ｉ≦ｍ≦ｒ−１）［Ｊ・（ｍ−
ｉ＋１）＋１］］また、比較回数は次式で与えられる。

Ｊ・［Σ（１≦ｊ≦Ｎ）Σ（１≦ｉ≦ｊ−１）Σ（ｉ＋
１≦ｒ≦ｊ）Σ（ｉ≦ｍ≦ｒ−１）［ｊ・（ｍ−ｉ＋
１）＋１］］＋２・Ｊ・［Σ（１≦ｊ≦Ｎ）Σ（１≦ｉ
≦ｊ）［ｊ−ｉ＋１］］これらの式は、Ｊに関して２乗、Ｎに関して５乗のオー
ダの多項式になる。

これらの式をいくつかのＪおよびＮについて計算したも
のが第２表である。

第１表と、第２表とを比較するとわかるように、Ｊおよ
びＮが大きいほど、本発明の効果は大きく、Ｊ＝５で、
Ｎ＝10のとき加算回数は約10⁷分の１、比較演算回数は
約10⁶分の１に、またＪ＝10、Ｎ＝40のときには加算回
数は約10⁵⁵分の１、比較演算回数は約10⁵³分の１に改善
される。

【図面の簡単な説明】

第１図は本発明を実施する装置の一実施例を示すブロッ
ク図、第２図（Ａ）および（Ｂ）はその制御手順の一例を示す
フローチャート、第３図（Ａ）および（Ｂ）は第２図のフローチャートを
実行する際に必要となるテーブルの一例を示す構造図で
ある。 SC……各文節の確信度を表わす数値保持用RAM、 BUF……文節集合保持用バッファメモリ、 PE……２文節間整合度計算装置、 INIT……文節仮名表記始端位置検出器、 SEL……データ選択装置、 T1……TABLE1用RAM、 T2……TABLE2用RAM、 ADD1……加算器、 MIN1……最小値検出装置、 ADD2……加算器、 MIN2……最小値検出装置、 CPU……中央処理装置、 MEM1……制御手順記憶用ROM、 MEM2……CPU作業用RAM、 CONT……各部の動作順序を制御する制御装置、 i₁……文節確実度入力端子、 i₂……文節入力端子、 o₁……T1に得られた結果の出力端子、 o₂……T2に得られた結果の出力端子。

Claims

【特許請求の範囲】

【請求項１】１からＮまでの自然数で決る仮名文字位置
と、仮名表記始端位置および仮名表記終端位置が１から
Ｎまでの範囲内の様々な位置にある文節の集合と、それ
ら文節の確実度を表わす数値が与えられたとき、２文節
間の係り受けの整合度と各文節の確実度を表わす数値の
総和を最小化あるいは最大化するという最適規準の下
で、最初の文節の仮名表記始端位置が１に等しく、最後
の文節の仮名表記終端位置がＮに等しく、かつ、最終文
節以外の文節の仮名表記終端位置に１を加えた値が次の
文節の仮名表記始端位置に等しいという条件を満たすよ
うにそれら文節を並べてできるあらゆる文節列の中か
ら、最適な文節列と、その文節列の最適構文、およびそ
の適格度を定める言語処理法において、前記Ｎに等しい行、列の数を持つ、２次元の上３角行列
形の第１表および第２表を用意し、前記第１表および前記第２表の各桝目を、仮名表記終端
位置がその列番号に等しく、かつ仮名表記始端位置がそ
の行番号以上であるような文節の数だけの項に分割し
て、前記第１表および前記第２表を３次元化し、仮名表記始端位置が自然数ｉ以上であり、かつ仮名表記
終端位置が自然数ｊであるような文節集合中のｑ番目の
文節について、その仮名表記始端位置がｉに等しいとき
には前記第１表の第ｉ行，第ｊ列、第ｑ項にその文節の
確実度を格納し、自然数ｋがｉから始まって、仮名表記始端位置がｉ以上
で、かつ仮名表記終端位置がｊに等しいような文節の集
合中の第ｑ番目の文節の仮名表記始端位置より１を減じ
た値までを動くとき、前記第１表の第ｉ行，第ｋ列の各
項と、前記第１表の第ｋ＋１行，第ｊ列，第ｑ項に計算
済みの値を格納し、その格納がなされたならば、当該計算済みの、前記第１
表の第ｉ行，第ｋ列，第ｐ項の値と、前記第１表の第ｋ
＋１行，第ｊ列，第ｑ項の値と、仮名表記始端位置がｉ
以上であり、かつ仮名表記終端位置がｋであるような文
節集合中の第ｐ番目の文節が、仮名表記始端位置がｉ以
上で、かつ仮名表記終端位置がｊであるような文節集合
中の第ｑ番目の文節に係ることの整合度を加算し、その加算結果のｋおよびｐに関する最小値または最大値
を前記第１表の第ｉ行，第ｊ列，第ｑ項に格納し、前記最小値または最大値を与える最適区分点であるとこ
ろのｋおよび最適文節番号であるところのｐの値の組を
前記第２表の第ｉ行，第ｊ列，第ｑ項に格納し、前記第１表および前記第２表を順次計算済みの値で埋め
て行き、前記第１表および前記第２表の第１行，第Ｎ列の各項に
計算済みの値が格納されるに到ったときに、前記第１表
の第１行，第Ｎ列の各項の中の最小値または最大値を求
めることにより最終的な適格度と、最終文節の文節番号
を得ると共に、最適構文を構成するために必要な最適区
分点および最適文節番号の組の全体を前記第２表に得る
ことを特徴とする言語処理法。