JPH077400B2

JPH077400B2 - 言語処理方法

Info

Publication number: JPH077400B2
Application number: JP62118338A
Authority: JP
Inventors: 和彦尾関
Original assignee: Japan Broadcasting Corp
Current assignee: Japan Broadcasting Corp
Priority date: 1987-05-15
Filing date: 1987-05-15
Publication date: 1995-01-30
Anticipated expiration: 2010-01-30
Also published as: JPS63282878A

Description

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

［従来の技術］ベタ書き仮名漢字変換方式日本語ワードプロセッサにお
いて、適切な最終的処理結果を得るためには、与えられ
た仮名文字列が持つ、形態素分割による多義性や同音語
による多義性などを解消しなければならない。

また、連続音声認識においては、結果がまず表音記号列
で出力されることを想定することができるが、認識の不
確実性を考慮して、通常一つの時間区間に対して複数の
認識候補を挙げることが行われる。従ってこの場合に
は、上記の多義性の解消に加えて、複数の候補の中から
適切なものを選択する処理が必要となる。

上のような問題を解決するため、日本語の文、あるいは
句として適格性の高い文節列を定める問題は、文節ラテ
ィスから最適文節列を選択する問題として研究されてい
る。文、あるいは句としての適格性の基準として、二文
節間の係り受けの整合度と、各文節の確実度の和を用い
る場合には、この問題を効率良く解く従来方法が次の文
献に述べられている。

尾関和彦：「文節ラティスから最適文節列を選択するた
めの多段決定アルゴリズム」、電子通信学会コンピュ
テーション研究会資料、COMP86−48（1986.11.20）［発明が解決しようとする問題点］表音記号列が与えられたとき、それから文節と認定でき
る部分表音記号列をすべて切りだし、そのような各部分
列を表音表記として持つ文節をすべて列挙すると、様々
な表音記号位置を表音表記始端、表音表記終端とする文
節の集合が得られる。このような文節の集合は文節ラテ
ィスと呼ばれている。文節ラティスは、連続音声中から
文節として認められる区間を切り出す方式の連続音声認
識装置の出力としても得られる。文節ラティスという言
葉を用いると、本発明が取り扱う問題は、「文節ラティスが与えられたとき、その中の文節を、終
端と始端が表音表記位置として連続するという条件を満
たすように並べてできるあらゆる文節列を作り、その中
から日本語の文、あるいは句としての適格性と、各文節
の確実度の双方を考慮して、最も妥当な文節列を選択せ
よ」と述べることができる。

従来技術に関する説明の中でも述べたように、日本語の
文あるいは句としての適格性が、二文節間の係り受けの
整合度の和で定義される場合には、この問題を効率良く
解く方法が既に知られている。しかし、このような適格
性の定め方では、一つの述語に係る文節の順序が不自然
な文や、一つの文節に係る文節の格が重複しているよう
な不自然な文でも、そのようなことのない自然な文と同
じ適格性を持つことがあるという問題がある。かかる不
都合を完全に解決するためには、日本語の文あるいは句
としての適格性を、二文節間の係り受けの整合度の和で
はなく、複数の文節が、ある順序で同時に他の一つの文
節に係ることの整合度の基にして定める必要があるが、
適格性をそのように定めると、上記の問題を解く方法は
枚挙法しか知られておらず、計算量が膨大になるという
問題のため、これを実行することはできなかった。

そこで、本発明の目的は、日本語の文、あるいは句とし
ての適格度が二文節間の係り受けの整合度ではなく、複
数の文節が、ある順序で同時に他の一つの文節に係るこ
との整合度に基づく場合に、与えられた文節ラティスか
ら、日本語の文あるいは句として最適な文節列を選択す
ると共にその上の構文を決定し、かつそれにより得られ
る文節列の日本語の句あるいは文としての適格度を枚挙
法に比べて格段に効率よく計算することのできる言語処
理方法を提供することにある。

［問題点を解決するための手段］（ａ）文節を単位とした日本語の構造本発明の構成について説明するにあたって、先ず文節を
単位とした日本語の構造について述べる。

日本語の文、あるいはまとまった句は、文節という単位
の間の広義の修飾関係によって成り立っていると考える
ことができる。例えば、［S1」「私は７時の電車で会社に行きます」という日本語の文において、「私は」、「７時の」、
「電車で」、「会社に」、「行きます」、はそれぞれ文
節であり、「私は」、「電車で」、「会社に」は、すべ
て「行きます」を修飾し、「７時の」は「電車で」を修
飾することにより一つのまとまった文を構成している。

文節ｘが文節ｙを修飾するとき、ｘはｙに係り、ｙはｘ
を受けるという。また、このような修飾関係を係り受け
という。

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

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

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

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

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

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

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

構文［X₁X₂…Xmx］,X₁＝［…x₁］,X₂＝［…x₂］，…,Xm
＝［…xm］において、x₁,x₂,…,xmはｘに係ることを表
わすと約束しておくと、上の意味での構文においては、
条件［C1］と［C2］が満たされ、逆に、条件［C1］と
［C2］を満たす文節列における係り受け関係は、必ず上
の意味での構文で表わすことができる。

さて、一つの文節列に対して、その上の構文は複数個存
在する。例えば、［［私は］［７時の］［電車で］［会社に］行
きます］［［［［［私は］７時の］電車で］会社に］行
きます］［［［私は］［７時の］電車で］［会社に］行
きます］［［［私は］［［７時の］電車で］会社に］行
きます］［［私は］［［７時の］電車で］［会社に］行
きます］などは全て例文［S1］の文節列上の構文である。このよ
うな多くの構文の中から、適格性の高い文節列を選択す
るためには、なんらかの評価関数が必要である。そこ
で、先ず係り受けの整合度が次のように定められるもの
とする。

［C3］文節x₁,x₂,…,xmが、文節ｘにこの順序で係るこ
との整合度は非負の値をとる関数 PEN（x₁,x₂,…,xm,x）で表わされる。

PENの値は、０に近いほど整合度が高いと約束してお
く。関数PENをどのように定めるかは、非常に重要な問
題であるが、これは本発明の主眼点ではないので説明を
省く。以上の準備のもとで、構文ｘの適格度Ｐ（Ｘ）
を、次のように再帰的に定める。

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

後の説明に用いるため、若干を記法を用意しておく。

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

（２）整数列i,i＋1,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）］［D5］文節集合列A₁,A₂,…,Amに対して KB（A₁A₂…Am）＝｛X|X∈Ｋ（x₁x₂…xm）,x₁∈A₁,x₂∈A₂,…,xm∈Am｝（ｂ）問題の設定以下では長い数式を読みやすくするための代りに Σ（ｉ≦ｍ≦ｊ）［ｆ（ｍ）］という記法を用いる。min,argmin,∪などについても同
様に記す。括弧［、］は混乱のおそれがなければ省略す
ることもある。

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

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

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

また、Ｓを構文にも適用できるよう拡張しておく。すな
わち、Ｘ∈Ｋ（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,s
m））［min（Ｘ∈Ｋ（x₁x₂…xm））［Ｐ（Ｘ）＋Ｓ
（Ｘ）］］］＝min（Ｘ∈∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［KB
（Ｂ（s₀,＋1,s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,s
m））］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］に注意して、上の問題を、次にように構文を変数とする
問題として書き直す。

［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₂），…,B（sm_-1
＋1,sm））］）［PX）＋Ｓ（Ｘ）］従来、この問題を解こうとすれば、枚挙法、すなわち、
集合 ∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［KB（Ｂ（s₀＋
1,s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,sm））］の全ての元Ｘに対してＰ（Ｘ）＋Ｓ（Ｘ）を逐一計算
し、最小値を与えるＸとそれに対する最小値を求めなけ
ればならなかった。しかし、第１表に示すように、この
集合の元の数は、Ｎと共に急速に増加し、たちまち膨大
なものになるので、枚挙法を実際問題に適用することは
不可能であった。

集合∪（（s₀,s₁,…,sm）∈Ｄ（1,N）［KB（Ｂ（s₀＋1,
s₁）,B（s₁＋1,s₂），…,B（sm_-1＋1,sm））］の元の数、ただし、任意のi,j（１≦ｉ≦ｊ≦Ｎ）に対
してＢ（i,j）の元の数をＭとした。

本発明によれば、このような従来技術の欠点を改善し、
枚挙法と比較して格段に計算量の少ない言語処理方法を
提供することができる。

関数PENが PEN（x₁,x₂,…,xm,x）＝PEN（x₁,x）＋PEN（x₂x）＋…＋PEN（xm,x）と二文節間の係り受けの整合度の和で表わすことができ
る場合については、前記の従来法によってこの問題を効
率良く解くことができる。これに対して、本発明は、関
数PENがこのような和に分解できない場合を対称とする
ものである。

（ｃ）再帰方程式本発明の構成について説明するに当たり、本発明におい
て基本的な役割を果たす再帰方程式について述べる。ま
ず、次の定義を設ける。

［D6］（１）Ｂ（i,j）＝∪（ｉ≦ｍ≦ｊ）［Ｂ（m,
j）］（２）ｘ∈Ｂ（i,j）に対して、INIT（ｘ）をｘ∈Ｂ
（m,j）のときINIT（ｘ）＝ｍと定める。

［D7］自然数Ｎを固定し、１≦ｉ≦ｊ≦N,x∈Ｂ（i,j）
に対して（１）OPT（i,j;x）＝min（Ｘ∈∪（（s₀,s₁,s₂,…,s
p）∈Ｄ（i,INIT（ｘ）−１））［KB（Ｂ（s₀＋1,s₁）,
B（s₁＋1,s₂），…,B（sp_-1＋1,sp），｛ｘ｝）］）
［Ｐ（Ｘ）＋Ｓ（Ｘ）］（２）OPK（i,j;x）＝argmin（Ｘ∈∪（（s₀,s₁,s₂,…,
sp）∈Ｄ（i,INIT（ｘ）−１））［KB（Ｂ（s₀＋1,
s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,sp），
｛ｘ｝）］）［Ｐ（Ｘ）＋Ｓ（Ｘ）］上記（１），（２）において、INIT（ｘ）＝ｉのときは
Ｄ（i,INIT（ｘ）−１）が定義されていないが、この場
合には ∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,INIT（ｘ）−１））
［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］＝KB（｛ｘ｝）と約束しておく。また、Ｐ（Ｘ）＋Ｓ（Ｘ）を最小にす
るＸは一般に複数個あるので、OPK（i,j;x）は重合とな
る。

このように定義されたOPTとOPKに関して、次の再帰方程
式が成り立つ。

［E1］ｘ∈Ｂ（i,j）に対して、（１）INIT（ｘ）＝ｉのとき OPT（i,j;x）＝Ｓ（ｘ）（２）INIT（ｘ）＞ｉのとき OPT（i,j;x）＝min（（s₀,s₁,s₂,…,sm）∈Ｄ（i,INIT
（ｘ）−１）,x₁∈Ｂ（s₀＋1,s₁）,x₂∈Ｂ（s₁＋1,
s₂），…,xm∈Ｂ（sm_-1＋1,sm））［OPT（s₀＋1,s₁;
x₁）＋OPT（s₁＋1,s₂;x）＋…＋OPT（sm_-1＋1,sm;xm）
＋PEN（x₁,x₂,…,xm,x）］＋Ｓ（ｘ）［E2］ｘ∈Ｂ（i,j）に対して、（１）INIT（ｘ）＝ｉのとき OPK（i,j;x）＝［Ｘ］（２）INIT（ｘ）＞ｉのとき、［E1］の（２）で最小値
を与えるs₀,s₁,s₂,…,sm,x₁,x₂,…,xmをそれぞれs₀,s₁,
s₂,…,sm,x₁,x₂,…,xmとするとき OPK（i,j;x）＝［OPK（s₀＋1,s₁;x₁）OPK（s₁＋1,s₂;
x₂）…OPK（sm_-1＋1,sm;xm）ｘ］［E1］と［E2］は次の［E3］が成り立つことに注意すれ
ば容易に証明できるので詳細な説明は省略する。

［E3］ ∪（（s₀,s₁,s₂,…,sp）∈Ｄ（i,INIT（ｘ）−１）｝
［KB（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…,B（sp_-1＋1,
sp），｛ｘ｝）］＝∪（（t₀,t₁,t₂,…,tm）∈Ｄ（i,INIT（ｘ）−１）,x
₁∈Ｂ（t₀＋1,t₁）,x₂∈Ｂ（t₁＋1,t₂），…,xm∈Ｂ（t
m_-1＋1,tm））｛［X₁X₂…Xmx］｜ x₁∈∪（（ｓ_1,0,s_1,1,s_1,2，…,s_1,p1）∈Ｄ（t₀＋1,I
NIT（x₁）−１））［KB（Ｂ（ｓ_1,0＋1,s_1,1）,B（ｓ
_1,1＋1,s_1,2），…,B（ｓ_1,p1-1＋1,s_1,p1），
｛x₁｝）］， x₂∈∪（（ｓ_2,0,s_2,1,s_2,2，…,s_2,p2）∈Ｄ（t₁＋1,I
NIT（x₂）−１））［KB（Ｂ（ｓ_2,0＋1,s_2,1）,B（ｓ
_2,1＋1,s_2,2），…,B（ｓ_2,p2-1＋1,s_2,p2），
｛x₂｝）］，…， xm∈∪（（ｓ_m,0,s_m,1,s_m,2，…,s_m,pm）∈Ｄ（tm_-1＋
1,INIT（xm）−１））［KB（Ｂ（ｓ_m,0＋1,s_m,1）,B
（Ｓ_m,1＋1,s_m,2），…,B（ｓ_m,pm-1＋1,s_m,pm），｛x
m｝）］｝さて、構文［X₁X₂…Xmx］,X₁＝［…x₁］,X₂＝［…
x₂］，…,Xm＝［…xm］においては、x₁,x₂,…,xmがｘに
係る。すなわち、ｘはx₁,x₂,…,xmを受ける訳である
が、一つの文節が受ける文節の数には一定の上限がある
と考えてよい。この上限をＬとすると、［E1］において
は、１≦ｍ≦Ｌの範囲で最小化をすればよい。このような制限を設ける
と、［E1］は次のようになる。

［E1′］ｘ∈Ｂ（i,j）に対して、（１）INIT（ｘ）＝ｉのとき OPT（i,j;x）＝ｓ（ｘ）（２）INIT（ｘ）＞ｉのとき OPT（i,j;x）＝min（１≦ｍ≦L,（s₀,s₁,s₂…,sm）∈
（i,INIT（ｘ）−１）,x₁∈Ｂ（s₀＋1,s₁）,x₂∈Ｂ（_１
＋1,s₂），…,xm∈Ｂ（sm_-1＋1,sm））［OPT（s₀＋1,
s₁;x₁）＋OPT（s₁＋1,s₂;x₂）＋…＋OPT（sm_-1＋,sm;x
m）＋PEN（x₁,x₂,…,xm,x）］＋Ｓ（ｘ）このような制限を設けても、［E2］には影響はない。Ｎ
≦Ｌとすれば［E1′］は［E1］と同一となる。すなわ
ち、［E1′］は［E1］を特別の場合として含む。従っ
て、以後は［E1′］を用いて説明を進める。

［E1′］（２）において、最小値を与えるs₁,s₂,…,sm
をi,j,xに対する最適区分点、またx₁,x₂,…,xmをそれら
の区分点における最適文節と呼ぶことにする。

（ｄ）OPT、最適区分点、および最適文節の決定法［E1′］の（２）は、INIT（ｘ）＞ｉのとき、OPT（s,
t,y）（ｉ≦ｓ≦ｔ≦j,y∈Ｂ（s,t））が既に計算され
ていれば、それらの値を用いてOPT（i,j;x）が計算でき
ることを示している。また、INIT（ｘ）＝ｉのときに
は、［E1′］の（１）を用いると、OPT（i,j;x）＝Ｓ
（ｘ）としてOPT（i,j;x）の値が定まる。これらの事実
を用いると、OPT（i,j;x）の値をｊ−ｉが０の部分から
始めて、順次ｊ−ｉがより大きい部分へと計算を進め、
それと同時に最適区分点と最適文節の組を決定して行く
ことができる。OPT（1,N;x）、（ｘ∈Ｂ（1,N））が計
算されたとき、OPT、最適区分点、および最適文節番号
の組の計算が終了する。

（ｅ）最適構文の計算法簡単のため、最適区分点と最適文節番号の組が常に一意
的に定まる場合について説明する。このとき、OPK（i,
j;x）（１≦ｉ≦ｊ≦N,x∈Ｂ（i,j））はただ一つの構
文に等しい。

先ず、 min（Ｘ∈∪（（s₀,s₁,s₂,…,sm）∈Ｄ（1,N））［KB
（Ｂ（s₀＋1,s₁）,B（s₁＋1,s₂），…Ｂ（sm_-1＋1,s
m））］｝［Ｐ（Ｘ）＋Ｓ（Ｘ）］＝min（ｘ∈Ｂ（1,N））［OPT（1,N,x）］であるから、この右辺を計算することにより、最適な文
節列上の最適な構文に対する適格度と信頼度の和が計算
される。また、 x₀＝argmin（ｘ∈Ｂ（1,N））［OPT（1,N,x）］とすれば、最適文節列とその上の最適構文は、 OPK（1,N,x₀）で与えられる。これを更に具体的に計算するには次のよ
うにすればよい。

もし、INIT（x₀）＝１ならば、［E2］の（１）によって OPK（1,N,x₀）＝［x₀］であるから、これにより最適構文が決定される。

INIT（x₀）≠１ならば、1,N,x₀対する最適区分点を s₁,s₂,…,sm 対応する最適文節をそれぞれ x₁,x₂,…,xm とすると、［E2］の（２）によって OPK（1,N,x₀）＝［OPK（1,s₁;x₁）OPK（s₁＋1,s₂;x₂）…OPK（sm_-1＋
1,sm;xm）x₀］が成り立つ。もし、INIT（x₁）＝１ならば、 OPK（1,s₁;x₁）＝［x₁］であるから OPK（1,N,x₀）＝［［x₁］OPK（s₁＋1,s;x₂）…OPK（sm_-1＋1,sm;xm）x
₀］また、INIT（x₁）≠１ならば1,s₁,x₁に対する最適区分
点をt₁,t₂,…,tpに対応する最適文節をそれぞれy₁,y₂,
…,ypとするとき OPK（1,s₁;x₁）＝［［OPK（1,t₁;y₁）OPK（t₁＋1,t₂;y₂）…OPK（tp_-1
＋1,tp;yp）x₁ が成り立つので、OPK（1,N,x₀）は次のように書き直す
ことができる。

OPK（1,N,x₀）＝［［OPK（1,t₁;y₁）OPK（t₁＋1,t₂;y₂）…OPK（tp_-1
＋1,tp;yp）ｘ］₁OPK（s₁＋1,s₂;x₂）…OPK（sm_-1＋1,s
m;xm）x₀］このような操作を、現れるOPKがすべて唯一の文節から
構成される構文になるまで続ければ、OPK（1,N,x₀）、
すなわち最適文節列とその上の最適構文を同時に決定す
ることができる。

一組のi,j,x（１≦ｉ≦ｊ≦N,x∈Ｂ（i,j））に対して
最適区分点と対応する最適文節の組が複数個存在するこ
とがあるが、そのときは、それらの全ての組に対して上
記の操作を行い、得られる構文全てを列挙すればよい。

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

［作用］本発明によれば、与えられた文字列位置1,2,…,Nの部分
列i,i＋1,…,jの範囲内での、最後の文節を固定した時
の最適な文節列とその上の最適な構文、およびその適格
度を、長さの短い部分列に対応するものから順次求めて
それを記憶しておき、それらの部分列を含むより長い部
分列に対して同様のものを計算するときにそれらを利用
することによって、同じ計算を繰り返すことなく効率的
に所期の結果を得ることができる。

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

以下の説明において、表音記号位置を、1,2,…,Nとす
る。以下では、文節集合Ｂ（i,j）の元の数をNUM（i,
j）とし、Ｂ（i,j）の元をＢ（i,j）＝｛ｘ_i,j,1,x_i,j,2，…,x_i,j,NUM(i,j)｝と列挙して表す。

本発明を実施する装置の一実施例を第１図に示す。第１
図において、SCは第２図（Ａ）および（Ｂ）に示すフロ
ーチャートにつき説明するテーブルscoreを実現するた
めのRAMなどによるバッファメモリであり、入力端子i1
から入力される各文節ｘ_i,j,qの確実度Ｓ（ｘ_i,j,q）を
保持するためのものである。BUFは文節入力端子i2から
入力される文節集合を保持するRAMなどによるバッファ
メモリである。各文節はその表音記号列だけでなく、始
端、終端の情報も併せて記述しておく。例として、本発
明を音声認識に用いる時は、認識装置から認識結果とし
て出力される各文節候補を端子i2から入力し、それらの
文節に付随した確実度を端子i1から入力する。また、本
発明をべた書き入力仮名漢字変換方式日本語ワードプロ
セッサに適用する時は、与えられた仮名文字列a₁,a₂,
…,a_Nをまず従来技術で形態素解析し、部分仮名文字列a
i,ai₊₁,…,ajを仮名表記として持つ文節候補を各i,j
（１≦ｉ≦ｊ≦Ｎ）について全て列挙し、それら文節候
補を端子i2から入力する。その際、単語の使用頻度など
から定まる、各文節の確実度を端子i1から入力する。T1
およびT2はそれぞれ第３図（Ａ）および（Ｂ）に示すテ
ーブルtable1およびtable2を実現するためのRAMであ
る。COMBIは表音記号位置1,2,…,Nの中からその分割点０＝ｋ（０）＜ｋ（１）＜ｋ（２）＜…＜ｋ（ｍ）＝Ｎと、それによって定まる文節集合Ｂ（ｋ（０）＋1,k
（１））,B（ｋ（１）＋,k（２）），…,B（ｋ（ｍ−
１）＋1,k（ｍ））の中からそれぞれ文節ｘ
_{k(0)+1,k(1),p(1)},x_{k(1)+1,k(2),p(2)}，…ｘ
_{k(m-1)+1,k(m),p(m)}を選択する組合わせを発生する装置
である。SEL1はバッファメモリBUFから組合わせ発生装
置COMBIにより指定される特定の文節のみを選択する装
置である。PEはバッファメモリBUFから選択装置SEL1を
介して読み出された文節x₁,x₂,…,xmxに対して、PEN（x
₁,x₂,…,xm,x）を計算する装置である。INTは選択装置S
EL1によって読み出された文節ｘの始端を検出する装置
である。SEL2はメモリT1から、組合わせ発生装置COMBI
により指定される特定の情報のみを選択する装置であ
る。SEL3は文節始端検出装置INTから送られた信号に基
づいて、バッファメモリSCに記憶されている情報の中か
ら特定のものを選択する装置である。ADD1はPEN計算装
置PEの出力と、選択装置SEL2によってメモリT1から読み
出された数値とを加算する加算器である。MINは組合わ
せ発生装置COMBIが種々の組合わせを発生するときの加
算器ADD1の出力の最小値とそのときの組合わせを検知す
る最小値検出器である。ADD2は最小値検出器MINの出力
とバッファメモリSCの中の特定の数値とを加算する加算
器である。

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

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

第２図（Ａ）および（Ｂ）のフローチャートに付随し
て、第３図（Ａ）および（Ｂ）に示すように、想定して
いる文節列長Ｎに等しい数の行および列、および第ｉ行
第ｊ列において文節集合Ｂ（i,j）の元の数NUM（i,j）
に等しい項を持った２つの３次元のテーブルtable1（i,
j,q）およびtable2（i,j,q）（１≦ｉ≦ｊ≦N,1≦ｑ≦N
UM（i,j））が必要である。各テーブルの添字は左から
順に行、列、項を表す。

table1（i,j,q）はOPT（i,j;x_i,i,q）の値を、またtabl
e2（i,j,q）は、i,j,x_i,j,qに対する最適区分点と最適
文節番号の組を記憶するためのものである。文節集合Ｂ
（i,j）の元の数NUM（i,j）は２次元のテーブルnum（i,
j）に入力され保持される。第ｋ文節集合Ｂ（i,j）内の
第ｐ文節ｘ_i,j,pの確実度は３次元のテーブルscore（i,
j,p）に入力され保持される。また、PEN（ｘ
_{k(0)+1,k(1),p(1)},x_{k(1)+1,k(2),p(2)}，…,x
_{k(m-1)+1,km,pm},x_i,j,q）を計算する関数を pen（（ｋ（０）＋1,k（１）,p（１））,k（１）＋1,k
（２）,p（２）），…，（ｋ（ｍ−１）,k（ｍ）,p
（ｍ）），（i,j,q））とする。INIT（ｘ_i,j,q）を計算する関数をinit（i,j,
q）とする。

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

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

ステップS3からステップS9において、各テーブルの項番
号ｑを１から始めてnum（i,j）まで１ずつ増加させ、第
ｑ項に対して次の処理を実行する。

（１）ステップS4において、init（i,j,q）≠ｉと判定
されたならば、ステップS5に進み、ここで次の［F1］を
実行し、ついでステップS6において［F2］を実行する。

［F1］ table1（i,j,q）：＝min（１≦ｍ≦min｛init（i,j,q）−1,L｝min（ｉ
−１＝ｋ（０）＜ｋ（１）＜Ｋ（２）＜…＜ｋ（ｍ）＝
init（i,j,q）−１）min（１≦ｐ（１）≦num（ｋ
（０）＋1,k（１））,1≦ｐ（２）≦mun（ｋ（１）＋1,
k（２）），…,1≦ｐ（ｍ）≦num（ｋ（ｍ−１）＋1,k
（ｍ））［table1（ｋ（０）＋1,k（１）,p（１））＋t
able1（ｋ（１）＋1,k（２）,p（２））＋…＋table1
（ｋ（ｍ−１）＋1,k（ｍ）,p（ｍ））＋pen（（ｋ
（０）＋1,k（１）,p（１）），（ｋ（１）＋1,k
（２）,p（２）），…，（ｋ（ｍ−１）＋1,k（ｍ）,p
（ｍ）），（i,j,q））］＋score（i,j,q）［F2］ table2（i,j,q）：＝（［F1］において最小値を与える（ｋ（１）,p
（１）），（ｋ（２）,p（２）），…，（ｋ（ｍ）,p
（ｍ））（２）ステップS4において、init（i,j,q）＝ｉと判定
されたならば、ステップS7に進み、ここで次の［F3］を
実行する。

［F3］ table1（i,j,q）：＝score（i,j,q）［F2］における区分点と文節の選び方の組合わせの発生
は第１図示の組合わせ発生装置COMBIで行われる。それ
らの組合わせに関する最小値と、最小値を与える組合わ
せの検知は最小値検出器MINで行われる。PEN計算装置PE
においてPENを計算するのに必要な文節の選択は選択装
置SEL1によって行われ、table1（ｋ（０）＋1,k（１）,
p（１））,table1（ｋ（１）＋1,k（２）,p（２）），
…,table1（ｋ（ｍ−１）＋1,k（ｍ）,p（ｍ））の値の
読み出しは選択装置SEL2によって行われる。init（i,j,
q）の計算とそれがｉに等しいか否かの判定は文節始端
検出装置INで行われる。また、テーブルnumはバッファB
UFの一部に記憶される。以上の処理により、table1およ
びtable2の各行、列、項に上述の計算を施し、その結果
を順次table1およびtable2に書込んで行く。

ステップS13においてｊ＞Ｎとなったときに計算が終了
し、table1（i,N,q）にはOPT（1,N,x_1,N,q）、（１≦ｑ
≦NUM（1,N））が記憶されている。また、table2には最
適区分点と最適文節番号の情報が記憶されているので、
（４）（ｅ）で述べた方法により、この情報から最適文
節列と最適構文を構成することができる。

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

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

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

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

［発明の効果］以上述べたように、本発明によれば、与えられた文字列
位置1,2,…,Nの部分列i,i＋1,…,jの範囲内での、最後
の文節を固定した時の最適な文節列とその上の最適な構
文、およびその適格度を、長さの短い部分列に対応する
ものから順次求めてそれを記憶しておき、それらの部分
列を含むより長い部分列に対して同様のものを計算する
ときにそれらを利用することによって、同じ計算を繰り
返すことなく効率的に所期の結果を得ることができる。

複数の文節x₁,x₂,…,xmが同時に、ある一つの文節ｘに
係ることの整合度PEN（x₁,x₂,…,xm,x）は、各文節を構
成する単語の属性や、実際の文章の中に現れる係り受け
の頻度などの統計情報などを予め乱書に記述しておき、
それに基づいて計算することができる。その計算量は言
語辞書の構成法などによっても変るが、一つの目安とし
て、次のような場合につき、本発明の計算方法と枚挙法
における加算と比較演算の回数を評価する。なお、ｍ個
の数値の総和を求めるのにはｍ−１回の加算演算が必要
であり、また、ｍ個の数値の最小値を求めるのにはｍ−
１回の比較演算が必要であるとした。

（１）PEN（x,y）を計算するためには、加算Ｊ回分の計
算量を必要とする。

（２）PEN（x₁,x₂,…,xm,x）を計算するためには、PEN
（x₁,x）＋PEN（x₂,x）＋…＋PEN（xm,x）を計算するの
と同じだけの計算量、すなわち加算（Ｊ＋１）・ｍ−１
回分の計算量を必要とする。

さらに、文節集合Ｂ（i,j）の元の数は、全てＭに等し
いとする。そうすると、解くべき問題の大きさを定める
パラメータは、全部で次のようになる。

M:各文節集合Ｂ（i,j）の元の数 N:文字列長 L:一つの文節に同時に係り得る文節数の上限 J:二文節間の係り受けの整合度計算量の、加算換算値以上の前提の下で、計算量は次のようになる。

（ａ）本発明関数Ｆ（n,k）をＦ（n,k）＝Σ（m₁＋m₂＋…,mk＝n,1≦mi≦ｎ）［m₁・m
₂…mk］と定義し、これを用いて加算回数と比較回数を表す。

（１）加算関数をｆ（ｎ）と定義すると（２）比較関数ｇ（ｎ）をと定義すると（ｂ）枚挙法 knum（n,L）を長さｎの文節列上の係り受け構造の中
で、一つの文節に同時に係る文節の数がＬ以下のものの
個数とし、_N-1Cnを二項係数とすると、加算回数と比較
回数は次のように表される。

（１）加算全加算回数＝Σ（０≦ｎ≦Ｎ−１）［_N-1Cn・｛knum
（ｎ＋1,L）・（Ｊ＋１）・ｎ＋ｎ｝・Mn⁺¹］（２）比較全比較回数＝Σ（０≦ｎ≦Ｎ−１）［_N-1Cn・｛knum
（ｎ＋1,L）・Mn⁺¹］−１ knum（n,L）は次の漸化式を用いて計算することができ
る。

これらの全加算回数および全比較回数をＪ＝１といくつ
かのM,N,Lについて計算した値を第２表および第３表に
掲げる。

これらの表によれば本発明の効果は明らかであり、例え
ば、Ｍ＝５、Ｎ＝20、Ｌ＝５のときの計算量は枚挙法の
約10¹³分の１に削減される。

【図面の簡単な説明】

第１図は本発明を実施する装置の一実施例を示すブロッ
ク図、第２図（Ａ）および（Ｂ）はその制御手順の一例を示す
フローチャート、第３図（Ａ）および（Ｂ）は第２図のフローチャートを
実行する際に必要となるテーブルの一例を示すテーブル
構造図である。 SC……文節確実度保持用RAM、 BUF……文節集合保持用RAM、 T1……table1用RAM、 T2……table2用RAM、 SEL1……データ選択装置、 SEL2……データ選択装置、 SEL3……データ選択装置、 PE……係り受け整合度計算装置、 COMBI……組合わせ発生装置、 INT……文節始端検出装置、 ADD1……加算器、 ADD2……加算器、 MIN……最小値検出器、 CPU……中央処理装置、 MEM1……制御手順記憶用ROM、 MEM2……CPU作業用RAM、 CONT……各部の動作順序を制御する制御装置、 i1……文節確実度入力端子、 i2……文節入力端子、 o1……メモリT1に得られた結果の出力端子、 o2……メモリT2に得られた結果の出力端子。

Claims

【特許請求の範囲】

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