(57)【要約】【課題】対話型の要約生成において、ユーザの状態に応じて要約を再度作成する際に、ＺＤＤを再構築することなく要約を生成することができる。【解決手段】木構造生成部２６が、要約対象の文書の各単語の依存関係に基づく木を生成し、生成された木の部分木の集合を表すＺＤＤを生成する。要約生成部３０が、予め設定された長さ上限と、文書の各単語の重要度と、ＺＤＤとに基づいて、要約対象の文書の要約を生成する。伝達制御部３２が、要約をユーザに提示し、要約対象の文書の各単語がユーザへ伝達されたか否かを表す伝達の状態を更新する。伝達済み範囲判定部３４が、伝達の状態に基づいて、要約対象の文書のうち、ユーザへ伝達された範囲を表す伝達済み箇所と、ユーザへ伝達されていない範囲を表す非伝達済み箇所とを判定する。部分木更新部３８が、伝達済み箇所に基づいて、伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新する。【選択図】図１
2018097669.tif 000002
【特許請求の範囲】
【請求項１】
要約対象の文書のうちの各単語を各頂点とし、依存関係を有する前記各単語間に対応する頂点間を辺で結合した、前記文書の各単語の依存関係に基づく木を生成し、生成された前記木の部分木の集合を表すＺＤＤ（Zero-suppressed Binary Decision Diagrams）を生成する木構造生成部と、
予め設定された長さ上限と、前記文書の各単語の重要度と、前記木構造生成部によって生成された前記ＺＤＤとに基づいて、前記文書の要約を生成する要約生成部と、
前記要約生成部によって生成された前記要約をユーザに提示し、前記文書の各単語が前記ユーザへ伝達されたか否かを表す伝達の状態を更新する伝達制御部と、
前記伝達制御部によって更新された前記伝達の状態に基づいて、前記文書のうち、前記ユーザへ伝達された範囲を表す伝達済み箇所と、前記ユーザへ伝達されていない範囲を表す非伝達済み箇所とを判定する伝達済み範囲判定部と、
前記伝達済み範囲判定部によって判定された前記伝達済み箇所に基づいて、前記伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新する部分木更新部と、
を含み、
予め定められた反復終了条件を満たすまで、前記要約生成部による生成、前記伝達制御部による提示及び更新、前記伝達済み範囲判定部による判定、並びに前記部分木更新部による更新を繰り返し、
前記要約生成部は、前記長さ上限と、前記更新されたＺＤＤに基づいて、前記文書の要約を生成する
要約生成装置。
【請求項２】
前記部分木更新部は、前記伝達済み箇所の前記単語の各々について、前記単語に対応する前記ＺＤＤの各頂点に対し、前記各頂点の親頂点の各々について、前記親頂点から前記頂点に対する枝の指し先を、前記頂点が前記部分木に含まれないことを表す枝の指し先の頂点へ指し換えることにより、前記ＺＤＤを更新する
請求項１に記載の要約生成装置。
【請求項３】
前記伝達制御部は、提示した前記要約が不明であるとの前記ユーザの意思表示を受け付けた場合、前記要約の文字数に対する前記文書の文字数の比率を表す要約率を減少させるように設定し、
前記要約生成部は、前記伝達制御部によって設定された前記要約率に応じた前記長さ上限に基づいて、前記文書の要約を生成する
請求項１又は請求項２に記載の要約生成装置。
【請求項４】
木構造生成部、要約生成部、伝達制御部、伝達済み範囲判定部、及び部分木更新部を含む要約生成装置における要約生成方法であって、
前記木構造生成部が、要約対象の文書のうちの各単語を各頂点とし、依存関係を有する前記各単語間に対応する頂点間を辺で結合した、前記文書の各単語の依存関係に基づく木を生成し、生成された前記木の部分木の集合を表すＺＤＤ（Zero-suppressed Binary Decision Diagrams）を生成するステップと、
前記要約生成部が、予め設定された長さ上限と、前記文書の各単語の重要度と、前記木構造生成部によって生成された前記ＺＤＤとに基づいて、前記文書の要約を生成するステップと、
前記伝達制御部が、前記要約生成部によって生成された前記要約をユーザに提示し、前記文書の各単語が前記ユーザへ伝達されたか否かを表す伝達の状態を更新するステップと、
前記伝達済み範囲判定部が、前記伝達制御部によって更新された前記伝達の状態に基づいて、前記文書のうち、前記ユーザへ伝達された範囲を表す伝達済み箇所と、前記ユーザへ伝達されていない範囲を表す非伝達済み箇所とを判定するステップと、
前記部分木更新部が、前記伝達済み範囲判定部によって判定された前記伝達済み箇所に基づいて、前記伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新するステップと、
を含み、
予め定められた反復終了条件を満たすまで、前記要約生成部による生成、前記伝達制御部による提示及び更新、前記伝達済み範囲判定部による判定、並びに前記部分木更新部による更新を繰り返し、
前記要約生成部は、前記長さ上限と、前記更新されたＺＤＤに基づいて、前記文書の要約を生成する
要約生成方法。
【請求項５】
コンピュータを、請求項１〜請求項３の何れか１項に記載の要約生成装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、要約生成装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来より、入力された文書を機械によって自動的に要約する技術が知られており、テキスト自動要約技術と呼ばれている。要約技術は大きく２種類に分けることができる。ひとつは、文書の中から重要だと思われる文を抽出して要約とする重要文抽出型要約であり、もうひとつは文内の不要な単語を除き、短い文を生成する文圧縮技術である。重要文抽出と文短縮の統合的な手法として、文書が持つ構造（たとえば修辞構造から得られる依存関係、具体的には理由となる文と結論となる文などの関係）から木を構成し、この木の根を含むような部分木を要約として生成することにより、文書・文が持つ構造を破壊することなく要約を生成する種類の木狩り込み型要約手法が存在する（例えば、非特許文献１〜２）。この技術によって、重要文抽出・文短縮の区分けなく、文書全体について文の持つ構造を尊重した要約を木刈込み型要約として捉えることが可能になっている。
【０００３】
木刈込み型要約では、依存関係を保持したま要約を生成できるため、文書や文が持つ構造に対して破綻しない要約を生成できる。しかし、いくら文の構造に対して破綻していなかったとしても、出力する要約として求められる長さが短い場合や、入力文書が長く、より高い要約率での要約を行う必要がある場合、大幅な木刈込みが必要となるため、利用者に対して意味が通じないような要約を生成してしまうおそれがある。かといって、あまり要約率を上げずに少量の木刈込みのみを行ってしまっては要約の意味がなく冗長となってしまう。これに対して、音声による聞き返しを通じた割込みや、画面からのポイントが行えることを想定し、利用者が不明に感じた部分をシステムに指示した際には、システムは当該箇所の意味がより伝わりやすいように、より低い要約率での要約を生成する方法が先行技術として存在する（例えば、特許文献１〜３）。このようなユーザからの反応に応じて適宜要約率を変更して要約の提示をやり直すような要約を対話型要約と呼ぶ。
【０００４】
対話型要約において、システムの入力として与えられた文書中の各部分（文や単語）は、システム動作中には以下の１）〜３）の３種類の状態のいずれかに分類されるであろう。
【０００５】
１）その部分に対応する要約文をシステムから利用者に対して未だ提示していない「未伝達」。
２）その部分に対応する要約文をシステムから利用者に対して提示済みであるが、利用者が理解可能であったかは未確定していない「伝達中」。
３）その部分に対応する要約文をシステムから利用者に対して提示済みであり、利用者から不明である旨の要求がなかったため、あるいは利用者から了解の旨の反応があったため利用者に対して情報が伝わったとみなすことができる「伝達済み」。
【０００６】
対話型要約では、伝達中の箇所について利用者が不明の意志表示を行った場合にその部分に関してのより低い要約率、すなわちより冗長で元文に近い要約を生成し、利用者に提示する。利用者がなお不明の意志表示を行った場合にはさらに低い要約率での提示を繰り返す。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１４−０４４５３９号公報
【特許文献２】特開２０１４−０４４５３８号公報
【特許文献３】特開２０１４−０５６４９９号公報
【非特許文献】
【０００８】
【非特許文献１】菊池悠太, 平尾努, 高村大也, 奥村学, 永田昌明, 「入れ子依存木の刈り込みに基づく単一文書要約手法」，自然言語処理, Vol.22, No.3, pp.197-217, 2015.
【非特許文献２】西野正彬, 安田宜仁, 平尾努, 湊真一, 永田昌明, 「木刈込みに基づく文書要約のためのZDDを用いた動的計画法」，言語処理学会第21 回年次大会発表論文集, 2015
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述のように対話型の要約においては、入力文書中での同一部分に対して、異なる要約率での要約を多数生成する必要が生じる。しかし、従来法では、異なる要約率での要約を生成する際には、初回の要約を生成するのと同じ手順を行う必要があり、要約生成のための計算時間が大きく、結果として即応的な要約を生成することができないため、利用者の待ち時間が生じてしまう。
【００１０】
本発明は、上記問題点を解決するために成されたものであり、対話型の要約生成において、ユーザの状態に応じて要約を再度作成する際に、ＺＤＤを再構築することなく要約を生成することができる要約生成装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、第１の発明に係る要約生成装置は、要約対象の文書のうちの各単語を各頂点とし、依存関係を有する前記各単語間に対応する頂点間を辺で結合した、前記文書の各単語の依存関係に基づく木を生成し、生成された前記木の部分木の集合を表すＺＤＤ（Zero-suppressed Binary Decision Diagrams）を生成する木構造生成部と、予め設定された長さ上限と、前記文書の各単語の重要度と、前記木構造生成部によって生成された前記ＺＤＤとに基づいて、前記文書の要約を生成する要約生成部と、前記要約生成部によって生成された前記要約をユーザに提示し、前記文書の各単語が前記ユーザへ伝達されたか否かを表す伝達の状態を更新する伝達制御部と、前記伝達制御部によって更新された前記伝達の状態に基づいて、前記文書のうち、前記ユーザへ伝達された範囲を表す伝達済み箇所と、前記ユーザへ伝達されていない範囲を表す非伝達済み箇所とを判定する伝達済み範囲判定部と、前記伝達済み範囲判定部によって判定された前記伝達済み箇所に基づいて、前記伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新する部分木更新部と、を含み、予め定められた反復終了条件を満たすまで、前記要約生成部による生成、前記伝達制御部による提示及び更新、前記伝達済み範囲判定部による判定、並びに前記部分木更新部による更新を繰り返し、前記要約生成部は、前記長さ上限と、前記更新されたＺＤＤに基づいて、前記文書の要約を生成する。
【００１２】
また、第２の発明に係る要約生成方法は、木構造生成部、要約生成部、伝達制御部、伝達済み範囲判定部、及び部分木更新部を含む要約生成装置における要約生成方法であって、前記木構造生成部が、要約対象の文書のうちの各単語を各頂点とし、依存関係を有する前記各単語間に対応する頂点間を辺で結合した、前記文書の各単語の依存関係に基づく木を生成し、生成された前記木の部分木の集合を表すＺＤＤ（Zero-suppressed Binary Decision Diagrams）を生成するステップと、前記要約生成部が、予め設定された長さ上限と、前記文書の各単語の重要度と、前記木構造生成部によって生成された前記ＺＤＤとに基づいて、前記文書の要約を生成するステップと、前記伝達制御部が、前記要約生成部によって生成された前記要約をユーザに提示し、前記文書の各単語が前記ユーザへ伝達されたか否かを表す伝達の状態を更新するステップと、前記伝達済み範囲判定部が、前記伝達制御部によって更新された前記伝達の状態に基づいて、前記文書のうち、前記ユーザへ伝達された範囲を表す伝達済み箇所と、前記ユーザへ伝達されていない範囲を表す非伝達済み箇所とを判定するステップと、前記部分木更新部が、前記伝達済み範囲判定部によって判定された前記伝達済み箇所に基づいて、前記伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新するステップと、を含み、予め定められた反復終了条件を満たすまで、前記要約生成部による生成、前記伝達制御部による提示及び更新、前記伝達済み範囲判定部による判定、並びに前記部分木更新部による更新を繰り返し、前記要約生成部は、前記長さ上限と、前記更新されたＺＤＤに基づいて、前記文書の要約を生成する。
【００１３】
前記部分木更新部は、前記伝達済み箇所の前記単語の各々について、前記単語に対応する前記ＺＤＤの各頂点に対し、前記各頂点の親頂点の各々について、前記親頂点から前記頂点に対する枝の指し先を、前記頂点が前記部分木に含まれないことを表す枝の指し先の頂点へ指し換えることにより、前記ＺＤＤを更新するようにすることができる。
【００１４】
前記伝達制御部は、提示した前記要約が不明であるとの前記ユーザの意思表示を受け付けた場合、前記要約の文字数に対する前記文書の文字数の比率を表す要約率を減少させるように設定し、前記要約生成部は、前記伝達制御部によって設定された前記要約率に応じた前記長さ上限に基づいて、前記文書の要約を生成するようにすることができる。
【００１５】
本発明に係るプログラムは、コンピュータを、上記の要約生成装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明の要約生成装置、方法、及びプログラムによれば、要約対象の文書の各単語の依存関係に基づく木の部分木の集合を表すＺＤＤを生成し、ＺＤＤに基づいて生成された要約をユーザに提示し、要約対象の文書の各単語がユーザへ伝達されたか否かを表す伝達の状態を更新し、文書のうち、ユーザへ伝達された範囲を表す伝達済み箇所に基づいて、伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新し、予め定められた反復終了条件を満たすまで、要約の生成、ユーザへの提示及び伝達の状態の更新、並びにＺＤＤの更新を繰り返すことにより、対話型の要約生成において、ユーザの状態に応じて要約を再度作成する際に、ＺＤＤを再構築することなく要約を生成することができる、という効果が得られる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態に係る要約生成装置の構成を示すブロック図である。
【図２】単語重要度データベースに格納されるデータの一例を示す図である。
【図３】要約対象の文書から生成される木の一例を示す図である。
【図４】ＺＤＤの一例を示す図である。
【図５】情報伝達管理表の一例を示す図である。
【図６】更新されたＺＤＤの一例を示す図である。
【図７】本発明の実施の形態に係る要約生成装置における要約生成処理ルーチンを示すフローチャートである。
【図８】本発明の実施の形態に係る要約生成装置における部分木更新処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１９】
＜本発明の実施の形態に係る要約生成装置の構成＞
本発明の実施の形態に係る要約生成装置の構成について説明する。図１に示すように、本発明の実施の形態に係る要約生成装置１００は、ＣＰＵと、ＲＡＭと、後述する要約生成処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この要約生成装置１００は、機能的には図１に示すように第１入力部１０と、第２入力部１２と、演算部２０と、出力部４０とを備えている。本発明の実施の形態に係る要約生成装置は、計算機を用いて自動的に言語を処理する分野に属し、特に計算機によって与えられた文書又は文書群を自動的に要約する自動機械要約の技術分野に属する。
【００２０】
第１入力部１０は、要約対象の文書を入力として受け付ける。要約対象の文書は、自然言語で記述された文書である。
【００２１】
第２入力部１２は、後述する要約生成部３０によって生成された要約がユーザに対して提示された場合に、提示された要約に対する、ユーザの了解の反応又は不明の意思表示を受け付ける。ユーザへの要約の提示については後述する。
【００２２】
演算部２０は、入力解析部２２と、単語重要度データベース２４と、木構造生成部２６と、部分木保持データベース２８と、要約生成部３０と、情報伝達管理表記憶部３１と、伝達制御部３２と、伝達済み範囲判定部３４と、部分木更新部３８とを備えている。
【００２３】
入力解析部２２は、第１入力部１０により受け付けた文書を取得する。そして、入力解析部２２は、後段の処理で当該文書を利用するために、計算機中のメモリあるいはディスク（図示省略）へ文書を格納する。もし、文書の言語において単語の区切りが文字列だけからは自明ではない場合は（例えば、文書が日本語で記述されている場合）、必要に応じて当業者に公知の技術（例えば公開されている形態素解析器など）を用いて文書を分かち書きすることにより、文書を単語に分割する。
【００２４】
次に、入力解析部２２は、文書の各単語の重要度を算出する。単語の重要度の算出には、当業者に公知の技術を用いることができる。単語の重要度の算出の一例としては、当業者に公知のＴＦ―ＩＤＦを用いることができる。そして、入力解析部２２は、文書の各単語の重要度を単語重要度データベース２４に格納する。
【００２５】
単語重要度データベース２４には、入力解析部２２によって算出された各単語の重要度が格納される。単語重要度データベース２４の例を図２に示す。図２に示すように、単語重要度データベース２４には、文書中の単語位置と重要度とが対応付けられて格納される。
【００２６】
木構造生成部２６は、入力解析部２２により得られた文書の各単語に基づいて、文書のうちの各単語を各頂点とし、依存関係を有する各単語間に対応する頂点間を辺で結合した、当該文書の各単語の依存関係に基づく木を生成する。木構造生成部２６により、入力解析部２２によって得られた文字列である単語を入力として、文書全体を表現した木構造が出力される。
【００２７】
木構造生成部２６による文書の各単語の依存関係に基づく木の生成には、当業者に公知の技術を用いることができ、例えば、上記非特許文献１に示された手法を用いることができる。木構造生成部２６による処理の結果、文書に対して頂点が単語で辺が依存関係を示しているような木が得られる。
【００２８】
次に、木構造生成部２６は、生成された木の部分木の集合を表すゼロサプレス型二分決定グラフＺＤＤ（ＺＤＤ：Zero-suppressed Binary Decision Diagrams，以下、単にＺＤＤと称する。）を生成する。ＺＤＤは、生成された木の中の部分木のうち全ての根つき部分木を表現するようなデータ構造である。ＺＤＤの生成には、以下の非特許文献３に示された手法を用いることができる。
【００２９】
図３に、木構造生成部２６によって生成される木の一例を示す。また、図４に、図３の木から生成されるＺＤＤの一例を示す。なお、図４では、ＺＤＤの図示の慣例に従い、実線は１‐枝（その変数で示される単語を含むことを選択する枝）を示し、破線は０‐枝（その変数で示される単語を含まないことを選択する枝）を示す。
【００３０】
また、図４の
【００３１】
【数１】
2018097669.tif 000003
【００３２】
は１‐終端、
【００３３】
【数２】
2018097669.tif 000004
【００３４】
は０‐終端を示す。根節点（図４に示す例では「１」）からＴまでの任意のパスは、上記図４のＺＤＤによって保持されている集合を示す。たとえば、パス「１‐実線‐２‐破線‐３‐実線‐４‐破線‐６‐破線‐８‐実線‐Ｔ」は集合｛１，３，８｝を示す。ＺＤＤの各段で示す先の単語をどういう順序にするかによってＺＤＤの形は変化する。この順序については、本実施の形態では、以下の非特許文献４に示されている順序に従うとする。
【００３５】
非特許文献３：Nishino, M., Yasuda, N., Hirao, T., Minato, S., Nagata, M. "A dynamic programming algorithm for tree trimming-based text summarization.", In Proceedings of NAACL HLT (pp.462-471). 2015.
【００３６】
非特許文献４：Norihito Yasuda, Masaaki Nishino, and Shin-ichi Minato. "On the size of the zero-suppressed binary decision diagram that represents all the subtrees in a tree.", In Trends and Applications in Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, pages 504-510. 2014.
【００３７】
そして、木構造生成部２６は、生成されたＺＤＤを部分木保持データベース２８に格納する。
【００３８】
部分木保持データベース２８には、木構造生成部２６によって生成されたＺＤＤが格納される。また、部分木保持データベース２８に格納されたＺＤＤは、後述する部分木更新部３８によって更新される。
【００３９】
要約生成部３０は、後述する伝達制御部３２によって設定される要約率に応じて予め設定された長さ上限と、単語重要度データベース２４に格納された各単語の重要度と、部分木保持データベース２８に格納されたＺＤＤとに基づいて、文書の要約を生成する。要約生成部３０によって行われる処理は、「０‐１ナップサック問題」として広く知られている問題の亜種を解くことに相当する。
【００４０】
０‐１ナップサック問題とは、それぞれ重さと価値を持つ複数のアイテムと、ナップサック問題の重さ上限が与えられた場合に、各アイテムは高々１度しか選択できないという条件下で、ナップサックの価値が最大となるようにナップサック問題に詰めるアイテムを選択する問題である。
【００４１】
本実施の形態でのアイテムは、単語の出現位置を示すＺＤＤの変数であり、価値は単語重要度データベース２４中の重要度の値であり、重さは単語の文字数である。さらに、通常の０‐１ナップサック問題とは異なり、要約として可能な部分木が、ＺＤＤが表す部分木の集合に含まれるという制約が更に加わる。
【００４２】
したがって、要約生成部３０は、部分木制約つきのナップサック問題を解くことになる。部分木制約つきのナップサック問題を解くためには、例えば上記非特許文献３に示された手法のような当業者に公知の技術を用いることができる。この結果、制限を満たす中でもっとも単語重要度の和が高いような部分木を得ることができる。
【００４３】
次に、要約生成部３０は、得られた部分木に含まれる各単語について、単語の文書中での出現順に並び替え、並び替えられた単語を要約として出力する。
【００４４】
情報伝達管理表記憶部３１には、第１入力部１０により受け付けた文書の各単語が、ユーザへ伝達されたか否かを表す伝達の状態に対応付けられて格納される。本実施の形態では、後述する伝達制御部３２により要約がユーザに対し提示されると、要約対象の文書の各単語がユーザへ伝達されたか否かを表す伝達の状態が更新されるため、各単語の伝達の状態を管理する必要がある。そのため、本実施の形態では、各単語の「伝達済み」「伝達中」「未伝達」の伝達の状態を、例えば図５に示すような情報伝達管理表として管理する。情報伝達管理表の初期状態は全ての単語について「未伝達」である。
【００４５】
なお、要約生成部３０が参照する部分木保持データベース２８のＺＤＤには、後述の部分木更新部３８の更新処理により「伝達済み」の単語のノードは含まれていない。そのため、要約生成部３０が生成する要約は、「未伝達」「伝達中」の部分に相当する要約である。
【００４６】
伝達制御部３２は、要約生成部３０によって生成された要約をユーザに提示する。そして、伝達制御部３２は、文書の各単語がユーザへ伝達されたか否かを表す伝達の状態を更新する。伝達制御部３２は、提示された要約に対する、ユーザの不明の意思表示を受け付けた場合、必要に応じて要約の要約率を下げるように設定する。本実施の形態では、要約率は、要約の文字数に対する要約対象の文書の文字数の比率を表す。以下、詳しく説明する。
【００４７】
まず、伝達制御部３２は、初期要約率ｒを予め定められた値（例えば、２０）に設定する。要約生成部３０は、文書中の文字数に１／ｒを乗じた値を、要約の長さの上限として要約を生成する。
【００４８】
そして、伝達制御部３２は、要約生成部３０によって生成された要約のうち、先頭から事前に決められた文数又は文字数を出力部４０により出力し、ユーザに提示する。要約の出力先である出力部４０としては、利用目的に応じて、声や画面等事前に指定されたデバイスとすることができる。なお、一度にユーザに提示する単位は、要約を出力するデバイスに応じて適宜変更可能である。例えば、音声での出力であれば要約のうち最初の１文が適切だと考えられ、要約を出力するデバイスが画面であれば、当該画面に収まる範囲の文字数で決定して良い。伝達制御部３２は、上記の基準によって決められた文字数を満たす範囲で、要約生成部３０によって生成された要約を出力部４０により出力する。
【００４９】
次に、伝達制御部３２は、提示された要約に関する単語の伝達の状態を「伝達中」に変更する。具体的には、まず、伝達制御部３２は、出力した要約に含まれる各単語について、当該単語の、要約を表す部分木中での単語位置を参照する。そして、伝達制御部３２は、参照した単語位置の単語及び部分木中で当該単語の子孫となる節に対応する単語のうち、伝達の状態が「伝達済み」でない全ての単語について、情報伝達管理表記憶部３１に格納された情報伝達管理表での当該単語の伝達の状態を「伝達中」に変更する。「伝達済み」の箇所がある場合は、後述する部分木更新部３８によってＺＤＤが更新される。
【００５０】
伝達済み範囲判定部３４は、伝達制御部３２によって取得された、ユーザの了解の反応又は不明の意思表示に基づいて、第１入力部１０により受け付けた文書のうち、ユーザへ伝達された範囲を表す伝達済み箇所と、ユーザへ伝達されていない、又は伝達中である範囲を表す「非伝達済み」箇所とを判定する。伝達済み範囲判定部３４により、要約対象の文書のうちどの部分（例えば、文又は単語）が既にユーザに対して伝達が完了しているかが判定される。
【００５１】
なお、要約を出力する出力部４０のデバイスが音声の場合であれば、これまで出力した要約に対して、ユーザから了解の反応があったり、システムから引き続き次の文の提示をしてもユーザが不明に感じていることを指摘されなかった部分を伝達が成功したと判定する。また、要約を出力する出力部４０のデバイスが画面の場合であり、ユーザが不明箇所を伝える手段がマウスや指差しでのポイントであればポイントされた箇所より手前に含まれる部分を伝達が成功したと判定する。
【００５２】
そして、伝達済み範囲判定部３４は、伝達済み箇所と非伝達済み箇所との判定結果に基づいて、情報伝達管理表記憶部３１の情報伝達管理表を更新する。具体的には、伝達済み範囲判定部３４は、ユーザに対して提示された要約の伝達済み箇所に含まれる各単語について、当該単語の、要約を表す部分木中での単語位置を参照し、当該単語及び部分木中での当該単語の子孫となる頂点に対応する全ての単語について、情報伝達管理表での状態を「伝達済み」に変更する。
【００５３】
部分木更新部３８は、伝達済み範囲判定部３４によって判定された伝達済み箇所に基づいて、部分木保持データベース２８に格納されたＺＤＤを、伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新する。
【００５４】
部分木更新部３８により、伝達済み範囲判定部３４よって新たに「伝達済み」と判定された単語の単語位置を入力として、部分木保持データベース２８に格納されたＺＤＤが更新される。更新後のＺＤＤは、「伝達済み」の単語を含まないような全ての部分木を含むＺＤＤとなる。
【００５５】
具体的には、部分木更新部３８は、情報伝達管理表記憶部３１の情報伝達管理表の「伝達済み」の単語の各々について、単語に対応するＺＤＤの各頂点に対し、各頂点の親頂点の各々について、親頂点から当該頂点に対する枝の指し先を、当該頂点が部分木に含まれないことを表す枝の指し先の頂点へ指し換えることにより、部分木保持データベース２８に格納されたＺＤＤを更新する。
【００５６】
より詳細には、部分木更新部３８は、全ての単語の単語位置について、以下の処理を行う。まず、部分木更新部３８は、単語の単語位置を変数番号（段数）とするような部分木保持データベース２８のＺＤＤ上の頂点集合を取得し、当該頂点集合をＮとする。次に部分木更新部３８は、頂点集合Ｎの全ての頂点ｎについて、頂点ｎの親頂点を調べ、親頂点からｎに向かう枝を張り替える。張り替える先は、頂点ｎの０‐枝の指し先頂点とする。
【００５７】
図６に、上記図４のＺＤＤにおいて５番の頂点が「伝達済み」である場合の、更新後のＺＤＤを示す。図６に示すように、親頂点１から頂点５への枝である１−枝の指し先を、頂点５の親頂点１から、頂点５の０‐枝の指し先頂点２へ指し換える。
【００５８】
なお、部分木更新部３８による当該処理は、木構造生成部２６によって得られた木を走査してＺＤＤを再構築する必要がないため、高速である。
【００５９】
伝達制御部３２は、予め定められた反復終了条件を満たすまで、要約生成部３０による生成、伝達制御部３２による提示及び取得、伝達済み範囲判定部３４による判定、並びに部分木更新部３８による更新を繰り返すように制御する。
【００６０】
具体的には、伝達制御部３２は、提示された要約に対する、ユーザの不明の意思表示を受け付けた場合に、要約率を減少させるように設定する。そして、要約生成部３０は、伝達制御部３２によって設定された要約率に応じた長さ上限に基づいて、文書の要約を生成する。
【００６１】
より詳細には、伝達制御部３２は、提示された要約に対する、ユーザの不明の意思表示を受け付けた場合、要約率ｒを事前に定められた分だけ減らすように設定する。要約率ｒが事前に定められた下限値（例えば１．２）を下回った場合、伝達制御部３２は、更なる要約は行わないように要約生成部３０を制御し、「未伝達」箇所に関する原文（要約対象の文書の該当文）を出力し、処理を終えるように制御する。一方、伝達制御部３２は、要約率ｒが下限を下回らない場合には要約生成部３０を用いて要約を再度生成するように制御し、処理を繰り返す。
【００６２】
また、提示された要約に対する、ユーザの不明の意思表示を受け付けなかった場合であって、「伝達済み」の範囲が要約対象の文書全体、又は「伝達済み」として判定された範囲に木の根節点を含む場合は、全ての単語を「伝達済み」として、演算部２０の処理を終了する。そして、出力部４０は、要約生成部３０によって生成された要約を結果として出力する。
【００６３】
＜本発明の実施の形態に係る要約生成装置の作用＞
【００６４】
次に、本発明の実施の形態に係る要約生成装置１００の作用について説明する。第１入力部１０において要約対象の文書を受け付けると、要約生成装置１００は、図７に示す要約生成処理ルーチンを実行する。
【００６５】
まず、ステップＳ１００において、第１入力部１０は、要約対象の文書を取得する。
【００６６】
次に、ステップＳ１０２において、入力解析部２２は、上記ステップＳ１００で取得された要約対象の文書を単語へ分割し、各単語の重要度を算出する。そして、入力解析部２２は、算出した単語の重要度を単語重要度データベース２４に格納する。
【００６７】
ステップＳ１０４において、木構造生成部２６は、上記ステップＳ１０２で得られた文書の各単語に基づいて、文書のうちの各単語を各頂点とし、依存関係を有する各単語間に対応する頂点間を辺で結合した、当該文書の各単語の依存関係に基づく木を生成する。そして、木構造生成部２６は、生成された木の部分木の集合を表すＺＤＤを生成し、部分木保持データベース２８に格納する。
【００６８】
ステップＳ１０６において、伝達制御部３２は、情報伝達管理表記憶部３１の情報伝達管理表の各単語の状態を「未伝達」に設定する。
【００６９】
ステップＳ１０８において、要約生成部３０は、初期要約率に応じて予め設定された長さ上限と、単語重要度データベース２４に格納された各単語の重要度と、部分木保持データベース２８に格納されたＺＤＤとに基づいて、要約対象の文書の要約を生成する。
【００７０】
ステップＳ１１０において、伝達制御部３２は、上記ステップＳ１０８で生成された要約の一部を出力部４０により出力し、ユーザに提示する。このとき、ユーザから、了解の反応や不明の意思表示を受け付ける。
【００７１】
ステップＳ１１２において、伝達制御部３２は、上記ステップＳ１１０で提示された要約に関する各単語の状態を「伝達中」とするように、情報伝達管理表記憶部３１の情報伝達管理表を更新する。
【００７２】
ステップＳ１１４において、伝達済み範囲判定部３４は、上記ステップＳ１００で受け付けた要約対象の文書のうち、ユーザへ伝達された範囲を表す伝達済み箇所と、ユーザへ伝達されていない範囲を表す非伝達済み箇所とを判定する。そして、伝達済み範囲判定部３４は、伝達済み箇所と非伝達済み箇所との判定結果に基づいて、情報伝達管理表記憶部３１の情報伝達管理表を更新する。
【００７３】
ステップＳ１１６において、部分木更新部３８は、上記ステップＳ１１４で判定された「伝達済み」箇所に基づいて、部分木保持データベース２８に格納されたＺＤＤを、「伝達済み」箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新する。ステップＳ１１６は、図８に示す部分木更新処理ルーチンによって実現される。
【００７４】
＜部分木更新処理ルーチン＞
【００７５】
ステップＳ２００において、部分木更新部３８は、情報伝達管理表記憶部３１の情報伝達管理表の「伝達済み」箇所の単語ｗに対応する単語位置の各々を設定する。
【００７６】
ステップＳ２０２において、部分木更新部３８は、上記ステップＳ２００で設定された単語位置の各々に対応するＺＤＤの頂点集合Ｎを設定する。
【００７７】
ステップＳ２０４において、部分木更新部３８は、上記ステップＳ２０２で設定された頂点集合Ｎから、１つの頂点ｎを設定する。
【００７８】
ステップＳ２０６において、部分木更新部３８は、上記ステップＳ２０４で設定された頂点ｎの親頂点集合Ｐを、部分木保持データベース２８に格納されたＺＤＤから取得する。
【００７９】
ステップＳ２０８において、部分木更新部３８は、上記ステップＳ２０６で取得された親頂点集合Ｐから、１つの親頂点ｐを設定する。
【００８０】
ステップＳ２１０において、部分木更新部３８は、上記ステップＳ２０８で設定された親頂点ｐから、上記ステップＳ２０４で設定された頂点ｎに向かう枝の指し先を、ｎの０−枝の先へ張替えるようにして、部分木保持データベース２８に格納されたＺＤＤを更新する。
【００８１】
ステップＳ２１２において、部分木更新部３８は、上記ステップＳ２０６で設定された親頂点集合Ｐの全ての親頂点について、上記ステップＳ２０８〜ステップＳ２１０の処理が実行されたか否かを判定する。親頂点集合Ｐの全ての親頂点について、上記ステップＳ２０８〜ステップＳ２１０の処理が実行された場合には、ステップＳ２１４へ進む。一方、上記ステップＳ２０８〜ステップＳ２１０の処理が実行されていない親頂点が存在する場合には、ステップＳ２０８へ戻る。
【００８２】
ステップＳ２１４において、部分木更新部３８は、上記ステップＳ２０２で設定された頂点集合Ｎの全ての親頂点について、上記ステップＳ２０４〜ステップＳ２１２の処理が実行されたか否かを判定する。頂点集合Ｎの全ての親頂点について、上記ステップＳ２０４〜ステップＳ２１２の処理が実行された場合には、ステップＳ２１６へ進む。一方、上記ステップＳ２０４〜ステップＳ２１２の処理が実行されていない頂点が存在する場合には、ステップＳ２０４へ戻る。
【００８３】
ステップＳ２１６において、部分木更新部３８は、上記ステップＳ２００で設定された全ての単語位置について、上記ステップＳ２０２〜ステップＳ２１４の処理が実行されたか否かを判定する。全ての単語位置について、上記ステップＳ２０２〜ステップＳ２１４の処理が実行された場合には、部分木データベース更新処理を終了する。一方、上記ステップＳ２０２〜ステップＳ２１４の処理が実行されていない単語位置が存在する場合には、ステップＳ２０２へ戻る。
【００８４】
次に、図７に示す要約生成処理ルーチンに戻り、ステップＳ１１８において、伝達制御部３２は、上記ステップＳ１１０で提示した要約が不明であるとのユーザの意思表示を受け付けたか否かを判定する。提示した要約が不明であるとのユーザの意思表示を受け付けた場合、ステップＳ１２２へ進む。一方、提示した要約が不明であるとのユーザの意思表示を受けていない場合、ステップＳ１２０へ進む。
【００８５】
ステップＳ１２０において、伝達制御部３２は、情報伝達管理表記憶部３１に格納された情報伝達管理表の全ての単語が「伝達済み」であるか否かを判定する。全ての単語が「伝達済み」である場合には、ステップＳ１２６へ進む。一方、「伝達中」又は「未伝達」の単語が情報伝達管理表に存在する場合には、ステップＳ１１０へ戻る。
【００８６】
ステップＳ１２２において、伝達制御部３２は、上記ステップＳ１０８で生成された要約よりも冗長な要約が生成可能であるか否かを判定する。既に生成された要約よりも冗長な要約が生成可能である場合には、ステップＳ１２４へ進む。一方、既に生成された要約よりも冗長な要約が生成可能でない場合には、ステップＳ１２６へ進む。冗長な要約が生成可能であるか否かについては、要約率の下限値に応じて判定される。
【００８７】
ステップＳ１２４において、伝達制御部３２は、要約率ｒを事前に定められた分だけ減少させるように設定する。そして、要約生成部３０は、伝達制御部３２によって設定された要約率に応じた長さ上限に基づいて、文書の要約を生成する。
【００８８】
ステップＳ１２６において、出力部４０は、上記ステップＳ１２０において全ての単語が「伝達済み」であると判定された場合には、要約生成部３０によって生成された要約を結果として出力する。一方、上記ステップＳ１２２において冗長な要約が生成可能でないと判定された場合には、要約生成部３０によって生成された要約と、「未伝達」箇所に関する原文（要約対象の文書の該当文）を結果として出力して、要約生成処理ルーチンを終了する。
【００８９】
以上説明したように、本発明の実施の形態に係る要約生成装置によれば、要約対象の文書の各単語の依存関係に基づく木の部分木の集合を表すＺＤＤを生成し、ＺＤＤに基づいて生成された要約をユーザに提示し、要約対象の文書の各単語がユーザへ伝達されたか否かを表す伝達の状態を更新し、文書のうち、ユーザへ伝達された範囲を表す伝達済み箇所に基づいて、伝達済み箇所に対応する単語を含まない部分木の集合を表すＺＤＤに更新し、予め定められた反復終了条件を満たすまで、要約の生成、ユーザへの提示及び伝達の状態の更新、並びにＺＤＤの更新を繰り返すことにより、対話型の要約生成において、ユーザの状態に応じて要約を再度作成する際に、ＺＤＤを再構築することなく要約を生成することができる。
【００９０】
また、対話型の要約生成において、同じ文書に対して異なる要約率の要約を複数生成したり、文書のうちの一部が既に伝達済みである場合に残りの部分について繰り返し要約する場合において、要約生成のために必要な時間を少なくすることができるため、ユーザの待ち時間を減らすことができる。
【００９１】
また、可能な要約になりうるＺＤＤをデータベースに保持しておくことで、要約生成のための前処理や複雑な計算を避けることができる。
【００９２】
また、文書内の一部の情報が伝達済みである場合に、部分木のＺＤＤ全体を作ることなく、最小限の枝の張り替えのみを行うことで計算時間を削減することができる。
【００９３】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９４】
例えば、上述の要約生成装置１００は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００９５】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体、例えばＣＤ−ＲＯＭやメモリーカード等に格納して提供することも可能である。
【符号の説明】
【００９６】
１０   第１入力部
１２   第２入力部
２０   演算部
２２   入力解析部
２４   単語重要度データベース
２６   木構造生成部
２８   部分木保持データベース
３０   要約生成部
３１   情報伝達管理表記憶部
３２   伝達制御部
３４   伝達済み範囲判定部
３８   部分木更新部
４０   出力部
１００ 要約生成装置
【図１】
2018097669.tif 000005
【図２】
2018097669.tif 000006
【図３】
2018097669.tif 000007
【図４】
2018097669.tif 000008
【図５】
2018097669.tif 000009
【図６】
2018097669.tif 000010
【図７】
2018097669.tif 000011
【図８】
2018097669.tif 000012