JP6232390B2

JP6232390B2 - テキスト要約装置、方法、及びプログラム

Info

Publication number: JP6232390B2
Application number: JP2015024610A
Authority: JP
Inventors: 正彬西野
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2015-02-10
Filing date: 2015-02-10
Publication date: 2017-11-15
Anticipated expiration: 2035-02-10
Also published as: JP2016148946A

Description

本発明は、テキスト要約装置、方法、及びプログラムに係り、特に、与えられたテキストを要約するテキスト要約装置、方法、及びプログラムに関する。

自然言語処理における要約文書生成とは、与えられた入力文書又は入力文に対して、適切な要約文書を自動的に生成することである。既存の要約生成手法として、組合せ最適化問題を解くことによって要約文書を生成する手法がいくつか存在する。手法の一種として、入力文書又は文を、文書の構成要素である文又は単語の依存関係を表現する根つき木として表現したのちに、制約を満たしつつ、かつある評価指標を最大化するような木の部分木を求めることによって要約を生成する手法が存在する（非特許文献１〜非特許文献３）。

部分木の選択問題に基づいて文書要約を行うことによって、得られた要約文書においては、元の入力文書における構成要素間の依存関係が保存されることになり、結果と入力文書の適切な要約を生成することが可能である。

T. Hirao, Y. Yoshida and M. Nishino, N. Yasuda and M. Nagata,"Single-Document Summarization as a Tree Knapsack Problem", in proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, 2013. Y. Kikuchi, T. Hirao and H. Takamura, M. Okumura and M. Nagata,"Single document summarization based on nested tree structure", in Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, 2014. K. Filippova and M. Strube, "Dependency tree based sentence compression", in Proceedings of the Fifth International Natural Language Generation Conference, 2008. H. Hernault, H. Prendinger, D. duVerle, and M. Ishizuka, "HILDA:A discourse parser using support vector machine classication", Dialogue &Discourse, Vol. 1 No.3, 2010.

既存手法では要約を生成する際に、問題を整数線形計画問題として定式化して、定式化された問題について、整数線形計画問題ソルバーを用いて解くことによって解を求めていた。しかし、整数線形計画問題ソルバーは常に問題を解けることが保証されておらず、また、仮に問題を解けたとしても、問題を解けるまでにかかる時間を正確に見積もることが困難であるという問題があった。

本発明は、上記問題点を解決するために成されたものであり、計算時間の増大を抑制し、かつ、安定して要約の最適解を求めることができるテキスト要約装置、方法、及びプログラムを提供することを目的とする。

上記目的を達成するために、第１の発明に係るテキスト要約装置は、入力テキストに含まれる文字列単位を表すノードの各々から構成される木構造から、許容される部分木を選択することにより、前記入力テキストを要約するテキスト要約装置であって、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）を構築するＺＤＤ構築部と、前記木構造の各ノードについて入力された前記ノードのスコア及び長さと、入力された上限長さＬと、前記ＺＤＤ構築部によって構築された前記ゼロサプレス型二分決定グラフとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊ（０≦ｊ≦Ｌ）に対し、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶する最適値計算部と、前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記上限長さＬ以下となる許容される部分木のうち、前記許容される部分木の各ノードのスコアの和が最大となる許容される部分木を、前記入力テキストの要約として出力するバックトラック部とを含み、前記最適値計算部は、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を計算するとき、前記記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む前記部分木とのうち、各ノードのスコアの和が最大となる前記部分木を再帰的に計算するように構成されている。

また、第１の発明に係るテキスト要約装置において、前記ＺＤＤ構築部は、前記入力テキストに対して予め定められた複数の根候補ノードを根ノードとする、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフを構築するようにしてもよい。

また、第１の発明に係るテキスト要約装置において、前記木構造は、入力テキストに含まれる第１の文字列単位を表すノードの各々から構成される木構造であって、前記第１の文字列単位を表すノードを、前記第１の文字列単位に含まれ、かつ、前記第１の文字列単位より小さい文字列単位である第２の文字列単位を表すノードの各々から構成される木構造に置き換えた、入れ子構造で表現される木構造であるようにしてもよい。

第２の発明に係るテキスト要約方法は、入力テキストに含まれる文字列単位を表すノードの各々から構成される木構造から、許容される部分木を選択することにより、前記入力テキストを要約するテキスト要約方法であって、ＺＤＤ構築部が、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）を構築するステップと、最適値計算部が、前記木構造の各ノードについて入力された前記ノードのスコア及び長さと、入力された上限長さＬと、前記ＺＤＤ構築部によって構築された前記ゼロサプレス型二分決定グラフとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊ（０≦ｊ≦Ｌ）に対し、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶するステップと、バックトラック部が、前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記上限長さＬ以下となる許容される部分木のうち、前記許容される部分木の各ノードのスコアの和が最大となる許容される部分木を、前記入力テキストの要約として出力するステップとを含んで、実行し、前記最適値計算部によって計算するステップは、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を計算するとき、前記記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む前記部分木とのうち、各ノードのスコアの和が最大となる前記部分木を再帰的に計算することを特徴とする。

また、第２の発明に係るテキスト要約方法において、前記ＺＤＤ構築部によってゼロサプレス型二分決定グラフを構築するステップは、前記入力テキストに対して予め定められた複数の根候補ノードを根ノードとする、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフを構築するようにしてもよい。

また、第２の発明に係るテキスト要約方法において、前記木構造は、入力テキストに含まれる第１の文字列単位を表すノードの各々から構成される木構造であって、前記第１の文字列単位を表すノードを、前記第１の文字列単位に含まれ、かつ、前記第１の文字列単位より小さい文字列単位である第２の文字列単位を表すノードの各々から構成される木構造に置き換えた、入れ子構造で表現される木構造であるようにしてもよい。

第２の発明に係るプログラムは、コンピュータを、上記第１の発明に係るテキスト要約装置を構成する各部として機能させるためのプログラムである。

本発明のテキスト要約装置、方法、及びプログラムによれば、木構造の許容される部分木の集合を表すＺＤＤを構築し、ノードのスコア及び長さと、入力された上限長さＬと、構築されたＺＤＤとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊに対し、ｎ番目のノードを根ノードとするゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる許容される部分木であって、かつ、部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算するときに、記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとするゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとする部分木ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む部分木とのうち、各ノードのスコアの和が最大となる部分木を再帰的に計算することにより、計算時間の増大を抑制し、かつ、安定して要約の最適解を求めることができる、という効果が得られる。

本発明の実施の形態に係るテキスト要約装置の構成を示すブロック図である。木構造と許容される部分木の一例を示す図である。木構造に対するＺＤＤの一例を示す図である。ＺＤＤを配列で表現したものの一例を示す図である。二次元配列Ｓ、及び二次元配列Ｂの値の表現の一例を示す図である。バックトラッキングの一例を示す図である。本発明の実施の形態に係るテキスト要約装置におけるテキスト要約処理ルーチンを示すフローチャートである。本発明の実施の形態に係るテキスト要約装置における最適解算出処理ルーチンを示すフローチャートである。複数の根候補ノードをもつ木構造により表現された文の一例を示す図である。根候補ノード集合をもつ木構造の一例を示す図である。木構造の根候補ノードを根ノードとしてもつ部分木、及びそれらのノードの集合を表現したＺＤＤの一例を示す図である。許容される部分木の一例を示す図である。入れ子構造の木構造により表現される文書の一例を示す図である。入れ子構造で表現される木構造の一例を示す図である。入れ子構造で表現される木構造の許容される部分木の集合を表現したＺＤＤの一例を示す図である。許容される部分木の一例を示す図である。

以下、図面を参照して本発明の実施の形態を詳細に説明する。

＜本発明の実施の形態に係る概要＞

まず、本発明の実施の形態における概要を説明する。

本発明の実施の形態では、部分木の選択問題を解くための動的計画法に基づく要約生成装置を用いる。本発明の実施の形態で示す要約生成装置を用いることで、部分木の選択問題において常に最適解を求められることが保証されている。また、処理時間も入力として与えられた木のノード数をＮ、生成する要約の最大長さをＬとしたときに、Ｏ（ＮＬｌｏｇＮ）となることが理論的に保証されている。

本発明の実施の形態で示す要約生成装置では、入力により木構造が与えられた時に、部分木の集合をゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams：以下、ＺＤＤと記載する。）にまず変換する。ゼロサプレス型二分決定グラフは集合族を表現するためのデータ構造であり、集合族を有向非巡回グラフ（Directed Acyclic Graph：以下、ＤＡＧと記載する。）として表現する。部分木の集合をＺＤＤとして表現したのちに、ＺＤＤの構造を用いた動的計画法を実行することによって最適な部分木を得る。原理的には、木のノード数をＮ、各ノードをｅ_１，・・・，ｅ_Ｎ、ノードｅ_ｉのスコアをｗ_ｉ、長さをｌ_ｉとすると、以下（１）及び（２）式に示す問題を説くことに相当する。

ここでＴは部分木、Ｓは部分木の集合である。各部分木Ｔはそれに含まれるノードの集合として表現される。したがってＴ∈｛ｅ_１，・・・，ｅ_Ｎ｝である。

＜本発明の第１の実施の形態に係るテキスト要約装置の構成＞

次に、本発明の第１の実施の形態に係るテキスト要約装置の構成について説明する。第１の実施の形態に係るテキスト要約装置は文抽出問題を解く。図１に示すように、本発明の第１の実施の形態に係るテキスト要約装置１００は、ＣＰＵと、ＲＡＭと、後述するテキスト要約処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このテキスト要約装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。

入力部１０は、木構造として表現された入力文書、木構造の各ノードに対応付けられたスコア、長さ、及び要約の長さとして許容する上限長さＬを受け付ける。木構造の各ノードは、文書を構成する構成単位に相当し、本実施の形態では、文に相当する。入力として与えられる木構造の例を図２に示す。このような木構造は、上記非特許文献３に記載されている談話構造解析器に文書を入力することで得ることができる。

演算部２０は、ＺＤＤ構築部３０と、最適値計算部３２と、記憶部４０とを含んで構成されている。

ＺＤＤ構築部３０は、入力部１０で受け付けた、木構造として表現された入力文書に基づいて、木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むＺＤＤを構築する。

ＺＤＤ構築部３０の具体的な処理を以下に説明する。ＺＤＤ構築部３０は、まず、入力部１０により受け付けた、木構造として表現された入力文書を取得する。次に、ＺＤＤ構築部３０は、入力部１０により受け付けた、各ノードに対するスコアｗ_ｉおよび長さｌ_ｉ、要約の上限長さＬを取得する。スコアｗ_ｉは非負実数、長さ、及び上限長さは非負整数であるとする。スコア、及び長さの定義は任意であるが、例えば、非特許文献１と同様に、スコアを単語の出現頻度と木の構造より定め、長さは文に含まれる単語の個数で定義する。

次に、取得した木構造に含まれる部分木のうち、取得した木構造における根ノードと同じ根ノードを持つ根付き部分木の集合を、許容される部分木の集合として表現するＺＤＤを生成する。ここである部分木は、取得した木構造に含まれるノードの部分集合として表現されるものとする。図３は取得した木構造、木構造の根ノードと同じ根ノードをもつ部分木、及びそれらのノードの集合を表現したＺＤＤである。取得した木構造に基づいて、こうした木構造の根を含む部分木のすべてを、ノードの集合として列挙したのちに、列挙したノードの集合からなる集合族を表現するＺＤＤを生成する。ＺＤＤは、例えば非特許文献５（S. Minato, "Zero-suppressed BDDs for set manipulation in combinatorial problems", in Proceedings of the 30th conference on Design Automation,1993.）で示されているようなａｐｐｌｙ演算を繰り返し適用することで生成することができる。

また、ＺＤＤ構築部３０においてＺＤＤを構成する際には、取得した木構造のノード間の全順序関係をあらかじめ定める必要がある。ノード間の順序を変化させるとＺＤＤの構造も変化する。今回扱う問題では木を深さ優先で行き掛け順にたどったときの順序を採用する。例えば上記図２の木構造に対しては、順序ｅ_７，ｅ_３，ｅ_１，ｅ_２，ｅ_５，ｅ_４，ｅ_６が深さ優先の行き掛け順に対応する。上記図３は、深さ優先の行き掛け順でノードの全順序関係を定めたときのＺＤＤである。ＺＤＤはＤＡＧの形状をしており、ＺＤＤの終端ノード以外の各中間ノードは必ず２つの子ノードをもつ。それぞれの子供をＬＯ側子ノード（０−子）、ＨＩ側子ノード（１−子）と呼び、また子供を指すエッジをそれぞれ０−エッジ、１−エッジと呼ぶ。また、各ノードにはラベルが関連づけられている。各ラベルはＺＤＤのノードに対応する木構造のノードを表している。１つのＺＤＤは必ず２つの終端ノードを持ち、それらは

と⊥のラベルが付与されている。ＺＤＤは親ノードをもたないノードを必ず１つだけもつ。このノードを根ノードとよぶ。ＺＤＤの根ノードから

終端ノードまでの１つのパスが、集合族に含まれる１つの集合に対応する。具体的には、ＺＤＤが表す集合族に含まれる１つの集合は、パス中に出現するノードのうち、１−エッジがパスに含まれているＺＤＤのノードに対応づけられているラベルの集合に対応する。

ＺＤＤ構築部３０において、以上のようにして構築したＺＤＤは配列として表現できる。配列はＺＤＤのノード数に応じた個数の要素をもち、各要素はラベル、０−子のアドレス、１−子のアドレスの３つ組からなる。図４は図３のＺＤＤを配列で表現したものである。ｉ番目の要素について、ノードに対するラベルをｖ（ｉ）、０−子のアドレスをｌｏ（ｉ）、１−子のアドレスをｈｉ（ｉ）とする。

最適値計算部３２は、木構造の各ノードについて入力されたノードのスコア及び長さと、入力された上限長さＬと、ＺＤＤ構築部３０によって構築されたＺＤＤとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊ（０≦ｊ≦Ｌ）に対し、ＺＤＤ構築部３０によって構築されたＺＤＤの少なくとも一部のＺＤＤであって、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部４０に記憶する。ここで、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、部分木の各ノードのスコアの和が最大となる部分木を計算するとき、記憶部４０に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む部分木とのうち、各ノードのスコアの和が最大となる部分木を再帰的に計算する。

最適値計算部３２における具体的な処理を以下に説明する。なお、最適化処理には動的計画法アルゴリズムを用いる。

最適値計算部３２は、まず、２つのＺ×（Ｌ＋１）要素からなる２次元配列Ｓ、及び２次元配列Ｂを用意する。ＺはＺＤＤ構築部３０で求めたＺＤＤのノードの個数である。配列Ｓの（ｉ，ｊ）要素（１≦ｉ≦Ｚ，０≦ｊ≦Ｌとする）をＳ［ｉ］［ｊ］と表す。１≦ｉ≦Ｚ，０≦ｊ≦Ｌについては、Ｓ［ｉ］［ｊ］に−∞を代入して、Ｓ［ｉ］［ｊ］を初期化する。そして、Ｓ［Ｚ−１］［０］に０を代入する。

配列Ｓの値Ｓ［ｉ］［ｊ］を、それぞれ、ｉ＝Ｚ−１，Ｚ−２，・・・，１、ｊ＝０，１，・・・，Ｌ＋１の順に、以下の（３）式に従って再帰的に更新する。

ただし、上記（３）式の下段の選択肢はｊ−ｌ_ｉ≧０を満たす場合にのみ選択可能であるとする。上記（３）式に従って更新したＳ［ｉ］［ｊ］は、ｉ番目のノードを根とするＺＤＤが表現する集合族に含まれる集合のうち、当該集合に含まれる木のノードの長さの和がｊであるものを取り出したときのスコアの和の最大値となっている。

配列Ｂ［ｉ］［ｊ］には、上記（３）式において、Ｓ［ｉ］［ｊ］を上段又は下段の解の候補のうちのどちらを用いて更新したかを示す記号を記録する。すなわち、上記（３）式の上段の選択肢を用いてＳ［ｉ］［ｊ］にＳ［ｌｏ（ｉ）］［ｊ］を代入して更新したならば、Ｂ［ｉ］［ｊ］にＬＯ側子ノードを表す「ＬＯ」と記録し、下段の選択肢を用いてＳ［ｉ］［ｊ］にＳ［ｈｉ（ｉ）］［ｊ−ｌ_ｉ］＋ｗ_ｉと代入して更新したならば、Ｂ［ｉ］［ｊ］にＨＩ側子ノードを表すＨＩと記録する。Ｂ［ｉ］［ｊ］に記録された値は後述するバックトラック部３４の処理で用いられる。そして、Ｓ［１］［ｊ］（０≦ｊ≦Ｌ）の最大値を与えるｊを取り出し、ｊ^＊とする。もし最大値が−∞ならば解なしとして処理を終了する。図５に実行途中のある時点での二次元配列Ｓ、及び二次元配列Ｂの値の表現を示す。図５の例では、ｉに関しては下から上にＮ８から順に更新し、ｊに関しては左から右に順に更新している。

バックトラック部３４は、最適値計算部３２によって繰り返し計算された計算過程に基づいて、上限長さＬ以下となる許容される部分木のうち、許容される部分木の各ノードのスコアの和が最大となる許容される部分木を、入力文書の要約として出力部５０により出力する。

バックトラック部３４の具体的なバックトラッキング処理について以下に説明する。バックトラック部３４では、図６に示す二次元配列Ｂ［ｉ］［ｊ］におけるバックトラッキングを実行する。バックトラック部３４は、まず、

として、ｓを初期化する。ｓは最適解となる部分木のラベルｖ（ｉ）を格納する配列である。また、（ｉ，ｊ）に（１，ｊ^＊）を代入して、（ｉ，ｊ）を初期化する。次に、Ｂ［ｉ］［ｊ］＝ＬＯならば、（ｉ，ｊ）に（ｌｏ（ｉ），ｊ）を代入して更新する。Ｂ［ｉ］［ｊ］＝ＨＩならば、ｓをｓ∪ｖ（ｉ）に更新した上で、（ｉ，ｊ）に（ｈｉ（ｉ），ｊ−ｌ_ｉ）を代入して更新する。そして、（ｉ，ｊ）＝（Ｚ−１，０）ならばｓに格納されたラベルによる許容される部分木を最適解として出力して処理を終了し、そうでなければバックトラッキングの処理を繰り返す。

＜本発明の第１の実施の形態に係るテキスト要約装置の作用＞

次に、本発明の第１の実施の形態に係るテキスト要約装置１００の作用について説明する。入力部１０において木構造として表現された入力文書、木構造の各ノードに対応付けられたスコア、長さ、及び要約の長さとして許容する上限長さＬを受け付けると、テキスト要約装置１００は、図７に示すテキスト要約処理ルーチンを実行する。

まず、ステップＳ１００では、入力部１０において受け付けた、木構造として表現された入力文書、スコア、長さ、及び要約の長さとして許容する上限長さＬを取得する。

次に、ステップＳ１０２では、ステップＳ１００で取得した木構造として表現された入力文書に基づいて、ＺＤＤを生成する。

ステップＳ１０４では、ステップＳ１００で取得したスコア、長さ、及び要約の長さとして許容する上限長さＬと、ステップＳ１０２で生成したＺＤＤとに基づいて、各ノードの長さの和が、上限長さＬ以下であり、かつ、各ノードのスコアの和が最大となる許容される部分木を計算する。

ステップＳ１０６では、ステップＳ１０４で計算された、各ノードの長さの和が、上限長さＬ以下であり、かつ、各ノードのスコアの和が最大となる許容される部分木を、入力文書の要約として出力部５０により出力し、処理を終了する。

上記ステップＳ１０４の最適解算出処理ルーチンについて以下、詳細に説明する。

図８に示すステップＳ２００では、まず、２次元配列Ｓ、及び２次元配列Ｂを用意する。

次に、ステップＳ２０２では、ステップＳ２００で用意した２次元配列Ｓ、及び２次元配列Ｂを初期化する。

ステップＳ２０４では、２次元配列Ｓを上記（３）式に従って再帰的に更新し、配列Ｂに上記（３）式において、Ｓ［ｉ］［ｊ］を上段又は下段の解の候補のうちのどちらを用いて更新したかを示す記号を記録する。

ステップＳ２０６では、ステップＳ２０４で更新したＳ［１］［ｊ］（０≦ｊ≦Ｌ）の最大値を与えるｊを取り出し、ｊ^＊とする。

ステップＳ２０８では、配列ｓを初期化する。

ステップＳ２１０では、（ｉ，ｊ）に（１，ｊ^＊）を代入して、（ｉ，ｊ）を初期化する。

ステップＳ２１２では、ステップＳ２０４で更新したＢ［ｉ］［ｊ］に基づいて、Ｂ［ｉ］［ｊ］＝ＬＯならば、（ｉ，ｊ）に（ｌｏ（ｉ），ｊ）を代入して更新し、Ｂ［ｉ］［ｊ］＝ＨＩならば、ｓをｓ∪ｖ（ｉ）に更新した上で、（ｉ，ｊ）に（ｈｉ（ｉ），ｊ−ｌ_ｉ）を代入して更新する。

ステップＳ２１４では、（ｉ，ｊ）＝（Ｚ−１，０）かを判定し、（ｉ，ｊ）＝（Ｚ−１，０）であれば最適解算出処理ルーチンを終了し、（ｉ，ｊ）＝（Ｚ−１，０）でなければ、ステップＳ２１２へ移行して処理を繰り返す。

以上説明したように、第１の実施の形態に係るテキスト要約装置によれば、木構造の許容される部分木の集合を表すＺＤＤを構築し、ノードのスコア及び長さと、入力された上限長さＬと、構築されたＺＤＤとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊに対し、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶するときに、記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む部分木とのうち、各ノードのスコアの和が最大となる部分木を再帰的に計算することにより、計算時間の増大を抑制し、かつ、安定して要約の最適解を求めることができる。

＜本発明の第２の実施の形態に係るテキスト要約装置の構成＞

次に、本発明の第２の実施の形態に係るテキスト要約装置の構成について説明する。第２の実施の形態に係るテキスト要約装置は文短縮問題を解く。なお、第１の実施の形態のテキスト要約装置１００と同様の構成となる部分については、同一符号を付して説明を省略する。

上記図１に示すように、本発明の第２の実施の形態に係るテキスト要約装置１００は、ＣＰＵと、ＲＡＭと、テキスト要約処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このテキスト要約装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。

第２の実施の形態に係る入力部１０は、木構造として表現された入力文、木構造の各ノードに対応付けられたスコア、長さ、及び要約の長さとして許容する上限長さＬを受け付ける。また、入力部１０は、当該入力文に対して予め定められた複数の根候補ノードを受け付ける。入力文は、文に含まれる単語の依存関係を表す根つき木として表現したものである。このような依存関係を表す根つき部分木は、文を非特許文献６（D. Chen and C. D. Manning, "A fast and accurate dependency parserusing neural networks", in Proceedings of the 2014 conference on Empirical Methods, in Natural Language Processing, 2014.）に示すような依存構造解析器に入力して出力された木に対して、上記非特許文献３に示す変換処理を適用することで得ることができる。入力として与えられる文の木構造の一例を図９に示す。

第２の実施の形態に係る演算部２０は、ＺＤＤ構築部３０と、最適値計算部３２と、記憶部４０とを含んで構成されている。

第２の実施の形態に係るＺＤＤ構築部３０では、以下に説明するように、入力部１０で受け付けた、木構造として表現された入力文書に基づいて、入力文に対して予め定められた複数の根候補ノードを根ノードとする、木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むＺＤＤを構築する。

第２の実施の形態に係るＺＤＤ構築部３０では、取得した木構造に含まれる部分木のうち、取得した木構造における根候補ノードのいずれかを根ノードとして持つ部分木の集合を、許容される部分木の集合として表現するＺＤＤを生成する。図１０は取得した木構造を示し、図１１は、木構造の根候補ノードを根ノードとしてもつ部分木、及びそれらのノードの集合を表現したＺＤＤの一例である。また、第２の実施の形態に係るＺＤＤ構築部３０では、第１の実施の形態と同様に、取得した木構造のノード間の全順序関係をあらかじめ定める必要がある。第２の実施の形態では、ノード間の全順序については、各ノードに対して順序スコアを定義し、順序スコアが高い子ノードの順序が先になるような深さ優先行きがけ順を採用する。ここで、ノードのスコアは、当該ノードの子孫ノードからなる部分木に含まれる、最大の許容される部分木のノード数とする。図１２に示す許容される部分木であれば、例えばｅ_１，ｅ_３，ｅ_６のスコアはそれぞれ６，４，０である。

なお、第２の実施の形態に係るテキスト要約装置の他の構成及び作用は、第１の実施の形態のテキスト要約装置１００と同様であるため詳細な説明を省略する。

以上説明したように、本発明の第２の実施の形態に係るテキスト要約装置によれば、予め定められた複数の根候補ノードを根ノードとする、木構造の許容される部分木の集合を表すＺＤＤを構築し、ノードのスコア及び長さと、入力された上限長さＬと、構築されたＺＤＤとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊに対し、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶するときに、記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む部分木とのうち、各ノードのスコアの和が最大となる部分木を再帰的に計算することにより、計算時間の増大を抑制し、かつ、安定して要約の最適解を求めることができる。

＜本発明の第３の実施の形態に係るテキスト要約装置の構成＞

次に、本発明の第３の実施の形態に係るテキスト要約装置の構成について説明する。第３の実施の形態に係るテキスト要約装置は文抽出及び文短縮を同時に行う問題を解く。なお、第１及び第２の実施の形態のテキスト要約装置１００と同様の構成となる部分については、同一符号を付して説明を省略する。

上記図１に示すように、本発明の第３の実施の形態に係るテキスト要約装置１００は、ＣＰＵと、ＲＡＭと、テキスト要約処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このテキスト要約装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。

第３の実施の形態に係る入力部１０は、木構造として表現された文書、文書に含まれる各文であって、かつ、木構造として表現された各文、木構造の各ノードに対応付けられたスコア、長さ、及び要約の長さとして許容する上限長さＬを受け付ける。文書の木構造は、文書に含まれる各文をノードとし、文の木構造は、文に含まれる各単語をノードとする。

なお、本実施の形態では、文書を表す木構造、及び各文を表す木構造を、文をノードとする木構造の各ノードを、単語のノードとする木構造で置き換えた、入れ子構造で表現される木構造で表現する（図１３参照）。

また、文書の第１の文字列単位として、文を用い、第１の文字列単位より小さい文字列単位である第２の文字列単位として、単語を用いる場合を例に説明したが、これに限定されるものではなく、他の文字列単位を用いてもよい。

第３の実施の形態に係る演算部２０は、ＺＤＤ構築部３０と、最適値計算部３２と、記憶部４０とを含んで構成されている。

第３の実施の形態に係るＺＤＤ構築部３０では、以下に説明するように、入力部１０で受け付けた、木構造として表現された文書、及び木構造として表現された各文に基づいて、入れ子構造で表現される木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むＺＤＤを構築する。

具体的には、入れ子構造で表現される木構造の許容される部分木の集合として、外側の木構造についての根ノードを持つ部分木と、外側の木構造における当該部分木の各ノードに対する、当該ノードの内側の木構造についての、当該文について予め定められた複数の根候補ノードの何れかを根ノードを持つ部分木とからなる根付き部分木の集合を表現するＺＤＤを生成する。図１４は取得した入れ子構造で表現される木構造を示し、図１５は、入れ子構造で表現される木構造の許容される部分木の集合を表現したＺＤＤである。また、第３の実施の形態に係るＺＤＤ構築部３０では、第１の実施の形態と同様に、取得した、入れ子構造で表現される木構造のノード間の全順序関係をあらかじめ定める必要がある。第３の実施の形態では、ノード間の全順序については、各ノードに対して順序スコアを定義し、順序スコアが高い子ノードの順序が先になるような深さ優先行きがけ順を採用する。ここで、ノードのスコアは、当該ノードが含まれる内側の木での子孫ノードからなる部分木に含まれる、最大の許容される部分木のノード数とする。図１６に示す部分木であれば、例えばｅ_１，ｅ_３，ｅ_６，ｅ_１２のスコアは、それぞれ５，０，４，３である。

なお、第３の実施の形態に係るテキスト要約装置の他の構成及び作用は、第１及び第２の実施の形態のテキスト要約装置１００と同様であるため詳細な説明を省略する。

以上説明したように、本発明の第３の実施の形態に係るテキスト要約装置によれば、入れ子構造で表現された木構造の許容される部分木の集合を表すＺＤＤを構築し、ノードのスコア及び長さと、入力された上限長さＬと、構築されたＺＤＤとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊに対し、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶するときに、記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとするＺＤＤが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む部分木とのうち、各ノードのスコアの和が最大となる部分木を再帰的に計算することにより、計算時間の増大を抑制し、かつ、安定して要約の最適解を求めることができる。

なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

１０入力部
２０演算部
３０ＺＤＤ構築部
３２最適値計算部
３４バックトラック部
４０記憶部
５０出力部
１００テキスト要約装置

Claims

入力テキストに含まれる文字列単位を表すノードの各々から構成される木構造から、許容される部分木を選択することにより、前記入力テキストを要約するテキスト要約装置であって、
前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）を構築するＺＤＤ構築部と、
前記木構造の各ノードについて入力された前記ノードのスコア及び長さと、入力された上限長さＬと、前記ＺＤＤ構築部によって構築された前記ゼロサプレス型二分決定グラフとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊ（０≦ｊ≦Ｌ）に対し、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶する最適値計算部と、
前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記上限長さＬ以下となる許容される部分木のうち、前記許容される部分木の各ノードのスコアの和が最大となる許容される部分木を、前記入力テキストの要約として出力するバックトラック部とを含み、
前記最適値計算部は、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を計算するとき、前記記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む前記部分木とのうち、各ノードのスコアの和が最大となる前記部分木を再帰的に計算する
テキスト要約装置。
前記ＺＤＤ構築部は、前記入力テキストに対して予め定められた複数の根候補ノードを根ノードとする、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフを構築する請求項１記載のテキスト要約装置。
前記木構造は、入力テキストに含まれる第１の文字列単位を表すノードの各々から構成される木構造であって、前記第１の文字列単位を表すノードを、前記第１の文字列単位に含まれ、かつ、前記第１の文字列単位より小さい文字列単位である第２の文字列単位を表すノードの各々から構成される木構造に置き換えた、入れ子構造で表現される木構造である請求項１又は２記載のテキスト要約装置。
入力テキストに含まれる文字列単位を表すノードの各々から構成される木構造から、許容される部分木を選択することにより、前記入力テキストを要約するテキスト要約方法であって、
ＺＤＤ構築部が、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）を構築するステップと、
最適値計算部が、前記木構造の各ノードについて入力された前記ノードのスコア及び長さと、入力された上限長さＬと、前記ＺＤＤ構築部によって構築された前記ゼロサプレス型二分決定グラフとに基づいて、各ノードの順序に従って、ｎ番目のノードについて、各長さｊ（０≦ｊ≦Ｌ）に対し、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を繰り返し計算して記憶部に記憶するステップと、
バックトラック部が、前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記上限長さＬ以下となる許容される部分木のうち、前記許容される部分木の各ノードのスコアの和が最大となる許容される部分木を、前記入力テキストの要約として出力するステップとを含み、
前記最適値計算部によって計算するステップは、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木であって、かつ、前記部分木の各ノードのスコアの和が最大となる部分木を計算するとき、前記記憶部に記憶した、各ノードのスコアの和の最大値を呼び出して、ＬＯ側子ノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなる部分木と、ｎ番目のノードを根ノードとする前記ゼロサプレス型二分決定グラフが表す部分木の集合のうち、各ノードの長さの和が長さｊと等しくなるＨＩ側子ノードを含む前記部分木とのうち、各ノードのスコアの和が最大となる前記部分木を再帰的に計算する
テキスト要約方法。
前記ＺＤＤ構築部によってゼロサプレス型二分決定グラフを構築するステップは、前記入力テキストに対して予め定められた複数の根候補ノードを根ノードとする、前記木構造の許容される部分木の集合を表し、かつ、２つの終端ノード、及び前記木構造の各ノードに対応する、ＨＩ側子ノード及びＬＯ側子ノードを有する根ノード又は中間ノードを含むゼロサプレス型二分決定グラフを構築する請求項４記載のテキスト要約方法。
前記木構造は、入力テキストに含まれる第１の文字列単位を表すノードの各々から構成される木構造であって、前記第１の文字列単位を表すノードを、前記第１の文字列単位に含まれ、かつ、前記第１の文字列単位より小さい文字列単位である第２の文字列単位を表すノードの各々から構成される木構造に置き換えた、入れ子構造で表現される木構造である請求項４又は５記載のテキスト要約方法。
コンピュータを、請求項１〜請求項３の何れか１項に記載のテキスト要約装置を構成する各部として機能させるためのプログラム。