JP5113863B2 - 用語抽出方法とその装置と、プログラム - Google Patents

Description

この発明は、テキストから用語を抽出する用語抽出方法と、その装置とプログラムに関する。

従来の用語抽出方法の最も簡単な例としては、予め用語リストを準備しておき、与えられたテキストと文字列が一致する用語を抽出する方法がある。この方法は、テキストと用語リストの各語とを逐一照合するので、用語リストの用語数に比例した抽出時間を必要とする。

その抽出時間を減らす目的で、例えば、トライ（trie）と呼ばれる木構造形式で辞書データを管理する方法が知られている（非特許文献１）。この方法は、長さがｋ文字の用語の場合、ｋ回の処理で登録されている用語を抽出できるので、単語リストの各語を逐一照合する方法に比較して抽出時間を短縮できる。また、テキストの全ての部分文字列と照合することを避ける目的で、不要な照合をしないように改良された方法も知られている（非特許文献２）。

長尾 真、佐藤 理史 編「岩波講座ソフトウェア科学 自然言語処理」岩波書店、p250 北 研二、津田 和彦 著「情報探索アルゴリズム」共立出版、2002年１月、p108

上記した従来の方法は、用語リストと完全に一致する用語しか抽出できないという課題を持つ。例えば、用語リストに「バイオリン」が登録されていた場合でも、表記揺らぎ「ヴァイオリン」を抽出することができない。また、「violin」といった異なる表記を抽出することもできないという課題があった。

用語リスト中の「バイオリン」と「ヴァイオリン」の照合を成功させるためには、例えば、両表記を動的計画法（参考文献：「日本語情報処理」p40、電子通信学会編）で照合することが考えられる。しかし、この方法では、従来の方法と同様に用語リスト中の用語数に比例した照合時間が必要であり現実的ではない。また、「violin」と照合するためには「バイ-vi」「オ-o」「リン-lin」といった音素毎の音訳確率を求めておき、「バイオリン-violin」全体の音訳確率が閾値を越えたら抽出する方法も考えられる。しかし、この方法でも用語リスト中の用語数に比例した照合時間が必要であり現実的ではない。

この発明は、このような課題に鑑みてなされたものであり、照合が高速に行え、且つ、表記ゆらぎを考慮した用語も抽出できる用語抽出方法とその装置と、プログラムを提供することを目的とする。この発明の用語抽出方法は、有限状態オートマトンを拡張した重み付き有限状態変換器（Weighted Finite-State Transducer、以降、ＷＦＳＴと称する）を利用する。

この発明の用語抽出方法は、用語ＷＦＳＴ作成過程と、ゆらぎＷＦＳＴ変換過程と、変換器合成過程と、ＷＦＳＴ記憶過程と、ＷＦＳＴ復号過程と、を含む。用語ＷＦＳＴ作成過程は、外部から入力される用語リストの各用語から、その各用語を文字毎に区切り各文字を入力文字としたＷＦＳＴ表現された用語リストである用語ＷＦＳＴを作成する。ゆらぎＷＦＳＴ変換過程は、用語のゆらぎ確率若しくは音訳のゆらぎ確率をゆらぎモデルであるゆらぎＷＦＳＴに変換する。変換器合成過程は、用語ＷＦＳＴとゆらぎＷＦＳＴを合成し、合成ＷＦＳＴを出力する。ＷＦＳＴ記憶過程は、合成ＷＦＳＴをＷＦＳＴ記憶部に記憶する。ＷＦＳＴ復号過程は、ＷＦＳＴ記憶部を参照して入力文字列に対する累積重みが最大になる遷移系列の文字列を復号し、状態番号が受理状態番号であれば当該受理状態を結果リストに登録する。

この発明の用語抽出方法によれば、用語のゆらぎ確率や音訳のゆらぎ確率をＷＦＳＴで表現し、その、ゆらぎＷＦＳＴと、用語リストの各用語から作成した用語ＷＦＳＴとを合成することで得られた合成ＷＦＳＴを用いることで、表記ゆらぎや異表記を含む用語を抽出する。したがって、この合成ＷＦＳＴには、用語の全候補が圧縮して格納されることになるので、１回の照合で高速に、且つ、表記ゆらぎ等を考慮した用語抽出が可能になる。

この発明の用語抽出方法を実現する構成例１００を示す図。 この発明の用語抽出方法の動作フローを示す図。 用語リスト１の例を示す図であり、（ａ）は用語のみ、（ｂ）は用語に識別ＩＤを付与した例を示す。 用語リスト１の用語ＷＦＳＴの例を示す図。 用語のゆらぎ確率２の例を示す図。 ゆらぎＷＦＳＴ（用語）の例を示す図。 音訳のゆらぎ確率３の例を示す図。 ゆらぎＷＦＳＴ（音訳）の例を示す図。 合成ＷＦＳＴの例を示す図。 ＷＦＳＴ復号部５０の処理の例を示す図。 この発明の用語抽出装置２００の機能構成例を示す図。 用語抽出装置２００の動作フローを示す図。

以下、この発明の実施の形態を図面を参照して説明する。複数の図面中同一のものには同じ参照符号を付し、説明は繰り返さない。

図１に、この発明の用語抽出方法を実現する機能構成例１００を示す。その動作フローを図２に示す。機能構成例１００は、用語ＷＦＳＴ作成部１０、ゆらぎＷＦＳＴ変換部２０、変換器合成部３０、ＷＦＳＴ記憶部４０、ＷＦＳＴ復号部５０、を具備する。これらの各部、若しくは全部の機能は、例えばＲＯＭ、ＲＡＭ、ＣＰＵ等で構成されるコンピュータに所定のプログラムが読み込まれて、ＣＰＵがそのプログラムを実行することで実現されるものである。

用語ＷＦＳＴ作成部１０は、外部から入力される用語リスト１の各用語から、その各用語を文字毎に区切り各文字を入力文字としたＷＦＳＴ表現された用語リストである用語ＷＦＳＴを作成する（ステップＳ１０）。

ゆらぎＷＦＳＴ変換部２０は、用語のゆらぎ確率２若しくは音訳のゆらぎ確率３をゆらぎモデルであるゆらぎＷＦＳＴに変換する（ステップＳ２０）。変換器合成部３０は、用語ＷＦＳＴ作成部１０で作成した用語ＷＦＳＴと、ゆらぎＷＦＳＴ変換部２０で変換したゆらぎＷＦＳＴを合成し、合成ＷＦＳＴを出力する（ステップＳ３０）。ＷＦＳＴ記憶部４０は、合成ＷＦＳＴを記憶する（ステップＳ４０）。ＷＦＳＴ復号部５０は、ＷＦＳＴ記憶部４０を参照して入力文字列に対する累積重みが最大になる遷移系列の文字列を復号する（ステップＳ５０）。
以上、説明した用語抽出方法によれば、入力文字列の中から特定の用語を、高速に、且つ、表記ゆらぎを考慮して抽出することができる。以降、用語ＷＦＳＴや、ゆらぎＷＦＳＴの具体例を示して更に詳しくこの発明の動作を説明する。

〔用語ＷＦＳＴ〕
図３に用語リスト１の例を示す。図３（ａ）に具体例として、「バイオリン」、「イアリング」、「ボーリング」を示す。図３（ｂ）に示すように各用語に識別ＩＤを付与してもよい。

図４に、図３の用語リスト１から、用語ＷＦＳＴ作成部１０で作成した用語ＷＦＳＴの例を示す。等価なＷＦＳＴは無数に存在するため図４はその一例である。図４において、円は状態を表し円中の数字は状態番号を表す。矢印は状態遷移を表す。矢印に付記された文字列は、「入力文字：出力文字/重み」を表す。なお、出力文字のεは空文字を意味する。

初期状態が状態（０）であり、受理状態が二重丸で示す状態（５）である。用語リスト１から用語ＷＦＳＴへの変換は、各用語を文字に区切り、各文字を入力文字とした状態遷移を設定することで行う。
初期状態（０）において入力文字「バ」が与えられると、状態（０）→状態（１）に状態遷移する。その時の状態遷移が、入力文字「バ」、出力文字「バイオリン」、重み１.０である。状態（１）→状態（２）の状態遷移の入力文字が「イ」、出力文字がε（空文字）、状態（２）→状態（３）の状態遷移の入力文字が「オ」、出力文字がε（空文字）、状態（３）→状態（４）の状態遷移の入力文字が「リ」、出力文字がε（空文字）、状態（４）→状態（５）の状態遷移の入力文字が「ン」、出力文字がε（空文字）で受理状態（５）にいたる。他の用語のボーリングとイアリングに対しても同様に、図４に示す用語ＷＦＳＴが作成される。

図４において、各用語の文字列が初期状態（０）直後の状態遷移に記載されているが、同一用語中の何れの状態遷移に記載しても等価な用語ＷＦＳＴとなる。各用語に識別ＩＤ（図３（ｂ））を付与した場合、各用語に替えて識別ＩＤが初期状態（０）直後の状態遷移に記載される。
確率値を重みとして扱うと、重みの積算は乗算で行われる。その場合は重みを全て１としておく。対数確率を重みとして扱うと重みの積算は加算で行われる。その場合は重みを全て０とすればよい。

〔ゆらぎＷＦＳＴ〕
図５に、用語のゆらぎ確率２の例を示す。原表記「バ」に対する揺らぎ表記としては、例えば「バ」と「ヴァ」の２つが存在し、その出現確率が０．７と０．３である。この出現確率は、人が与えてもよいし、機械的に求めてもよい（例えば参考文献：特許第4084515号）。

図６に、用語のゆらぎ確率（図５）をゆらぎモデルであるゆらぎＷＦＳＴに変換した例を示す。ゆらぎＷＦＳＴは、揺らぎ表記を原表記に書き換える変換器（トランスデューサ）であり、初期状態（０）から受理状態（４）まで遷移した時の重みの積算が、図５に示す確率値となる。ゆらぎＷＦＳＴ変換部２０が行う用語のゆらぎ確率からゆらぎＷＦＳＴへの変換は、揺らぎ表記を文字単位で区切り、各文字列を１文字ずつ入力文字に持つ状態遷移を設定することで行う。

揺らぎ表記「バ」の入力文字に対して、出力文字「バ」を出力する重みが０.７の状態遷移（バ：バ/０.７）で、初期状態（０）→受理状態（４）で遷移する。また、揺らぎ表記「ヴァ」の入力文字に対して、出力文字「バ」を出力する重みが０.３で、初期状態（０）→受理状態（４）に遷移する状態遷移が並列に設けられている。同様に、揺らぎ表記「ア」に対して出力文字「ア」を出力する重みが０.９の状態遷移（ア：ア/０.９）、状態遷移（ヤ：ア/０.１）等が並列に設けられている。受理状態（４）→初期状態（１）には、入力なしで自動的に戻る（ε：ε）。

図７に、アルファベット文字の音訳のゆらぎ確率３の例を示す。原表記「バ」に対する音訳の揺らぎ表記としては、例えば「ba」と「va」の２つが存在し、その出現確率が０．７と０．３である。図８に、音訳のゆらぎ確率（図７）をゆらぎＷＦＳＴに変換した例を示す。音訳のゆらぎＷＦＳＴも、用語ゆらぎの場合と同様に、揺らぎ表記を文字単位で区切り、各文字列を１文字ずつ入力文字に持つ状態遷移を設定することで行う。アルファベット文字の入力文字列に対して、音訳ゆらぎのゆらぎＷＦＳＴが使われる。

〔合成ＷＦＳＴ〕
図９に、図４の用語ＷＦＳＴと図５のゆらぎＷＦＳＴ（用語）を合成した合成ＷＦＳＴの例を示す。合成（Composition）とは、ＷＦＳＴの代表的な演算の一つであり、２つのＷＦＳＴを１つのＷＦＳＴにすることである。合成演算については、例えば参考文献：著者「Fernando C.N.Pereira, Michael Riley」タイトル「Speech Recognition by Composition of Weighted Finite Automata」出典「In Emmanuel Roche and Yves Schabes, editors, Finite-State Devices for Natural Language Processing, chapter 15,pp.431-453.MIT Press, Cambridge, Massachusetts,1997.」に記載されている。
図９の状態（１４）は、用語ＷＦＳＴ（図４）の状態（０）から状態（１）への遷移に、ゆらぎＷＦＳＴ（図６）の状態（０）から入力文字「ヴ」で遷移する遷移確率０.３の状態遷移（（０）→（１）→（４））が、合成された結果追加された状態である。また、図９の状態（６）から状態（７）へ追加された状態遷移（ウ：ε/０.２）は、ゆらぎＷＦＳＴ（図６）の状態遷移（（０）→（３）→（４））が合成された結果である。

このように用語ＷＦＳＴとゆらぎＷＦＳＴとが合成された合成ＷＦＳＴは、ＷＦＳＴ記憶部４０に記憶される。音訳のゆらぎＷＦＳＴについても、用語のゆらぎと同様に合成された合成ＷＦＳＴが、ＷＦＳＴ記憶部４０に記憶される。

〔ＷＦＳＴ復号部〕
ＷＦＳＴ復号部５０は、入力文字列に対して累積重みが最大になる遷移系列の文字列が出力できるものであればどのようなものでも構わない。例えば、図１０に示す処理をＷＦＳＴ符号部５０が行う。
ここでは、入力文字列として、単語単位で入力される例で説明する。

まず、初期状態をキュー（Queue）に入れる（ステップＳ５１）。状態とは、（文字位置、状態番号、出力文字列、累積重み）で構成されるデータである。キューは単純なスタックやFIFOでも構わない。最尤解を一つだけ求める場合には優先度付きキューを用いる。初期状態とは、（文字列の先頭、開始状態番号、空文字列、初期重み）である。初期重みとは、重み積算が乗算であれば１、加算であれば０である。

次にキューから１状態候補を取得する（ステップＳ５２）。そして、取得した状態の文字位置に該当する文字を入力文字列から取得して次文字とする（ステップＳ５４）。

取得した次文字が入力文字と合致する全ての遷移を、ＷＦＳＴ記憶部４０を参照して取得する（ステップＳ５５）。合わせて入力文字が空文字（ε）である遷移と、現在の状態番号が受理状態番号かどうかもＷＦＳＴ記憶部４０から取得する。

現在の状態番号が受理状態番号であれば、その受理状態を結果リストに登録する（ステップＳ５７）。例えば、優先度付きキューを用いた場合で、最尤解を１つだけ求めれば良い場合は、ここで終了する（ステップＳ５８のＹｅｓ）。
受理判定（ステップＳ５６）では、入力文字列と前方一致する用語を抽出することになる。もしも、完全一致する用語のみを抽出したければ、文字位置が入力文字列の終端にあるかどうかを合わせて判定すればよい。

次に、得られた遷移先状態を全てキューに追加する（ステップＳ５９）。遷移先の状態のうち、次文字位置は、入力文字が空文字（ε）であれば現文字位置と同一、そうでなければ１文字進めた位置である。次状態番号はＷＦＳＴ記憶部４０から取得した遷移先状態番号である。出力文字列は、現出力文字列とＷＦＳＴ記憶部４０から取得した出力文字列を連結したものである。累積重みは、現累積重みとＷＦＳＴ記憶部４０から取得した累積重みを積算したものである。

ステップＳ５２〜Ｓ５９の処理を、状態候補が取得できなくなるまで繰り返す（ステップＳ５３のＮｏ）。状態候補が取得できなくなった時点の結果リストに蓄えられた文字列が、ＷＦＳＴ復号部５０の出力となる（ステップＳ５３のＹｅｓ）。この例のように、入力文字列として単語単位で入力される場合は、用語抽出というよりは用語照合といった方が実態と合う。このような用語照合方法は、例えば検索エンジンのキーワード入力のフィルタとして利用可能である。

〔用語抽出装置〕
図１２、この発明の用語抽出装置２００の機能構成例を示す。その動作フローを図１３に示す。用語抽出装置２００は、図１に示したＷＦＳＴ記憶部４０と、ＷＦＳＴ復号部５０とで構成される。
ＷＦＳＴ復号部５０は、前方一致するものを出力するように構成しておく。抽出した用語は結果リストに蓄えられる。同一の用語の複数回の抽出を禁止する場合は、最初に抽出した時点でその用語についての抽出を終了するようにすればよい。

ＷＦＳＴ復号部５０は、テキスト全体を構成する文字列を取り込む（ステップＳ２０１）。そして、ＷＦＳＴ復号部５０は、取り込んだ入力文字の先頭の文字から、入力文字を更新しながら入力文字列の終端まで、上記したＷＦＳＴ復号過程を実行する（ステップＳ５０，Ｓ２０２，Ｓ２０３）。そのＷＦＳＴ復号過程において、受理状態番号が検出される度に抽出された用語が結果リストに出力される（ステップＳ５０）。

用語抽出装置２００は、ゆらぎＷＦＳＴと、用語リストの各用語から作成した用語ＷＦＳＴとを合成することで得られた合成ＷＦＳＴを用いて用語を抽出するので、高速に、且つ、表記ゆらぎや異表記を含む用語を抽出することができる。

上記装置における処理手段をコンピュータによって実現する場合、各装置が有すべき機能部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各装置における処理手段がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）/ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記録装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。また、各装置の機能構成部は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしても良い。

Claims (7)

1. 外部から入力される用語リストの各用語から、その各用語を文字毎に区切り各文字を入力文字としたＷＦＳＴ表現された用語リストである用語ＷＦＳＴを作成する用語ＷＦＳＴ作成過程と、
   用語のゆらぎ確率若しくは音訳のゆらぎ確率をゆらぎモデルであるゆらぎＷＦＳＴに変換するゆらぎＷＦＳＴ変換過程と、
   上記用語ＷＦＳＴと上記ゆらぎＷＦＳＴを合成し、合成ＷＦＳＴを出力する変換器合成過程と、
   上記合成ＷＦＳＴをＷＦＳＴ記憶部に記憶するＷＦＳＴ記憶過程と、
   上記ＷＦＳＴ記憶部を参照して入力文字列に対する累積重みが最大になる遷移系列の文字列を復号し、状態番号が受理状態番号であれば当該受理状態を結果リストに登録するＷＦＳＴ復号過程と、
   を含む用語抽出方法。
2. 外部から入力される用語リストの各用語から、その各用語を文字毎に区切り各文字を入力文字としたＷＦＳＴ表現された用語リストである用語ＷＦＳＴを作成する用語ＷＦＳＴ作成過程と、
   外来語を表記する際のカタカナ表記のゆらぎ確率をゆらぎモデルであるゆらぎＷＦＳＴに変換するゆらぎＷＦＳＴ変換過程と、
   上記用語ＷＦＳＴと上記ゆらぎＷＦＳＴを合成し、合成ＷＦＳＴを出力する変換器合成過程と、
   上記合成ＷＦＳＴをＷＦＳＴ記憶部に記憶するＷＦＳＴ記憶過程と、
   上記ＷＦＳＴ記憶部を参照して入力文字列に対する累積重みが最大になる遷移系列の文字列を復号するＷＦＳＴ復号過程と、
   を含む用語抽出方法。
3. 外部から入力される用語リストの各用語から、その各用語を文字毎に区切り各文字を入力文字としたＷＦＳＴ表現された用語リストである用語ＷＦＳＴを作成する用語ＷＦＳＴ作成過程と、
   カタカナ表記に対するアルファベット表記のゆらぎ確率をゆらぎモデルであるゆらぎＷＦＳＴに変換するゆらぎＷＦＳＴ変換過程と、
   上記用語ＷＦＳＴと上記ゆらぎＷＦＳＴを合成し、合成ＷＦＳＴを出力する変換器合成過程と、
   上記合成ＷＦＳＴをＷＦＳＴ記憶部に記憶するＷＦＳＴ記憶過程と、
   上記ＷＦＳＴ記憶部を参照して入力文字列に対する累積重みが最大になる遷移系列の文字列を復号するＷＦＳＴ復号過程と、
   を含む用語抽出方法。
4. 用語リストの各用語から作成された各文字を入力文字としてＷＦＳＴ表現された用語リストである用語ＷＦＳＴと、用語のゆらぎ確率若しくは音訳のゆらぎ確率であるゆらぎＷＦＳＴと、を合成した合成ＷＦＳＴを記憶したＷＦＳＴ記憶部と、
   上記ＷＦＳＴ記憶部を参照して入力文字列に対する累積重みが最大になる遷移系列の文字列を復号し、状態番号が受理状態番号であれば当該受理状態を結果リストに登録するＷＦＳＴ復号部と、
   を具備する用語抽出装置。
5. 請求項４に記載した用語抽出装置において、
   上記ゆらぎＷＦＳＴは、外来語を表記する際のカタカナ表記のゆらぎ確率をモデル化したものであることを特徴とする用語抽出装置。
6. 請求項４に記載した用語抽出装置において、
   上記ゆらぎＷＦＳＴは、カタカナ表記に対するアルファベット表記のゆらぎ確率をモデル化したものであることを特徴とする用語抽出装置。
7. 請求項１乃至３の何れかに記載した用語抽出方法を、コンピュータで処理するためのプログラム。

Images