図面 (/)

技術 曖昧性解消装置、方法、及びプログラム

出願人 日本電信電話株式会社
発明者 林克彦永田昌明
出願日 2014年8月27日 (5年7ヶ月経過) 出願番号 2014-173121
公開日 2016年4月7日 (3年11ヶ月経過) 公開番号 2016-048462
状態 特許登録済
技術分野 検索装置
主要キーワード 解消装置 ランク付き 優先度付きキュー 同値関係 数値ベクトル 状態集合 解消処理 有限状態オートマトン
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年4月7日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (7)

課題

曖昧性を解消した有限状態木オートマトンを生成することができるようにする。

解決手段

(1)A’の初期状態登録し、(2)A’の状態(p,s)の各々について、(2−1)状態pが、Aの終了状態であって、状態(p,s)と同値関係にある状態が、A’の終了状態として登録されていない場合、状態(p,s)を、A’の終了状態として登録し、(2−2)Aにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)状態の組み合わせを作成し、(2−2−2)作成された組み合わせの各々について、(2−2−2−1)状態(q、t)を作成すると共に辺を生成し、(2−2−2−2)生成された辺が、曖昧性を作らない場合に、A’の辺として登録し、状態(q、t)が、A’に登録されている状態の集合に含まれない場合に、状態(q、t)を、A’の状態として登録する。

概要

背景

非特許文献1では、有限状態オートマトン(Finite State Automaton;FSA) の曖昧性を解消する演算が提案されている。FSAが曖昧性を持つとは、同じ入力を受理できる2つ以上の異なる経路が存在するときをいう。FSAが曖昧性を持つと、オートマトンの動作は非効率的となる。非特許文献1のアルゴリズムでは、同じ記号列を読み込んで到達できる状態同士を関係Rとして定義し、そこから先の遷移合流がある場合、それらのうちどちらか一方の遷移を封鎖して曖昧性を解消する。

一方、FSAを一般化した有限状態木オートマトン(Finite State Tree Automaton;FTA) と呼ばれるものがある。FTAでは文字列ではなく、木を入力として受け取ることができる。FSAと同様に、FTAにも曖昧性の問題は存在する。従来、FTAにおいて、曖昧性を解消する方法に決定化(例えば、非特許文献2を参照。)と呼ばれる演算がある。決定化はある状態から同じ記号での遷移を排除する演算であり、その結果として、曖昧性を解消することができる。しかし、決定化によってできるFTAの状態数は、元のFTAの状態数Nに対して、2Nになることが知られている。

概要

曖昧性を解消した有限状態木オートマトンを生成することができるようにする。(1)A’の初期状態登録し、(2)A’の状態(p,s)の各々について、(2−1)状態pが、Aの終了状態であって、状態(p,s)と同値関係にある状態が、A’の終了状態として登録されていない場合、状態(p,s)を、A’の終了状態として登録し、(2−2)Aにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)状態の組み合わせを作成し、(2−2−2)作成された組み合わせの各々について、(2−2−2−1)状態(q、t)を作成すると共に辺を生成し、(2−2−2−2)生成された辺が、曖昧性を作らない場合に、A’の辺として登録し、状態(q、t)が、A’に登録されている状態の集合に含まれない場合に、状態(q、t)を、A’の状態として登録する。

目的

本発明では、上記事情に鑑みて成されたものであり、曖昧性を解消した有限状態木オートマトンを生成することできる曖昧性解消装置、方法、及びプログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、前記有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成する曖昧性解消装置であって、入力された有限状態木オートマンAを受け付ける入力部と、(1)前記有限状態木オートマンAの初期状態iと前記初期状態iからなる状態集合とのペアに対する、前記有限状態木オートマンA’の初期状態(i,{i})を登録し、(2)前記有限状態木オートマンA’に登録されている状態(p,s)の各々について、(2−1)前記状態pが、前記有限状態木オートマンAの終了状態であって、前記状態(p,s)と同値関係にある状態が、前記有限状態木オートマンA’の終了状態として登録されていない場合、前記状態(p,s)を、前記有限状態木オートマンA’の終了状態として登録し、(2−2)前記有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)前記状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)前記作成された組み合わせの各々について、(2−2−2−1)前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)前記生成された辺が、前記有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンA’の辺として登録し、前記作成された新たな状態(q、t)が、前記有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、前記新たな状態(q、t)を、前記有限状態木オートマンA’の状態として登録する曖昧性解消部と、前記有限状態木オートマンA’を出力する出力部と、を含む曖昧性解消装置。

請求項2

入力部、曖昧性解消部、及び出力部を含み、入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、前記有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成する曖昧性解消装置における曖昧性解消方法であって、前記入力部が、入力された有限状態木オートマンAを受け付けるステップと、前記曖昧性解消部が、(1)前記有限状態木オートマンAの初期状態iと前記初期状態iからなる状態集合とのペアに対する、前記有限状態木オートマンA’の初期状態(i,{i})を登録し、(2)前記有限状態木オートマンA’に登録されている状態(p,s)の各々について、(2−1)前記状態pが、前記有限状態木オートマンAの終了状態であって、前記状態(p,s)と同値関係にある状態が、前記有限状態木オートマンA’の終了状態として登録されていない場合、前記状態(p,s)を、前記有限状態木オートマンA’の終了状態として登録し、(2−2)前記有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)前記状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)前記作成された組み合わせの各々について、(2−2−2−1)前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)前記生成された辺が、前記有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンA’の辺として登録し、前記作成された新たな状態(q、t)が、前記有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、前記新たな状態(q、t)を、前記有限状態木オートマンA’の状態として登録するステップと、前記出力部が、前記有限状態木オートマンA’を出力するステップと、を含む曖昧性解消方法。

請求項3

入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、前記有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成するためのプログラムであって、コンピュータを、入力された有限状態木オートマンAを受け付ける入力部、(1)前記有限状態木オートマンAの初期状態iと前記初期状態iからなる状態集合とのペアに対する、前記有限状態木オートマンA’の初期状態(i,{i})を登録し、(2)前記有限状態木オートマンA’に登録されている状態(p,s)の各々について、(2−1)前記状態pが、前記有限状態木オートマンAの終了状態であって、前記状態(p,s)と同値関係にある状態が、前記有限状態木オートマンA’の終了状態として登録されていない場合、前記状態(p,s)を、前記有限状態木オートマンA’の終了状態として登録し、(2−2)前記有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)前記状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)前記作成された組み合わせの各々について、(2−2−2−1)前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)前記生成された辺が、前記有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンA’の辺として登録し、前記作成された新たな状態(q、t)が、前記有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、前記新たな状態(q、t)を、前記有限状態木オートマンA’の状態として登録する曖昧性解消部、及び前記有限状態木オートマンA’を出力する出力部として機能させるためのプログラム。

技術分野

0001

本発明は、曖昧性解消装置、方法、及びプログラム係り、特に、曖昧性を解消した有限状態木オートマトンを生成する曖昧性解消装置、方法、及びプログラムに関する。

背景技術

0002

非特許文献1では、有限状態オートマトン(Finite State Automaton;FSA) の曖昧性を解消する演算が提案されている。FSAが曖昧性を持つとは、同じ入力を受理できる2つ以上の異なる経路が存在するときをいう。FSAが曖昧性を持つと、オートマトンの動作は非効率的となる。非特許文献1のアルゴリズムでは、同じ記号列を読み込んで到達できる状態同士を関係Rとして定義し、そこから先の遷移合流がある場合、それらのうちどちらか一方の遷移を封鎖して曖昧性を解消する。

0003

一方、FSAを一般化した有限状態木オートマトン(Finite State Tree Automaton;FTA) と呼ばれるものがある。FTAでは文字列ではなく、木を入力として受け取ることができる。FSAと同様に、FTAにも曖昧性の問題は存在する。従来、FTAにおいて、曖昧性を解消する方法に決定化(例えば、非特許文献2を参照。)と呼ばれる演算がある。決定化はある状態から同じ記号での遷移を排除する演算であり、その結果として、曖昧性を解消することができる。しかし、決定化によってできるFTAの状態数は、元のFTAの状態数Nに対して、2Nになることが知られている。

先行技術

0004

Mehryar Mohri., “A disambiguation algorithm for finite automata and functional transducers.”, In Implementation and Application of Automata, Springer, 2012, p.265‐277
Jonathan May and Kevin Knight., “A better n-best list: Practical determinization of weighted finite tree automata.”, In In Proceedings of the HLT-NAACL, Association for Computational Linguistics, 2006, p.351‐358.

発明が解決しようとする課題

0005

上記非特許文献1の曖昧性解消演算アルゴリズムでは、その適用範囲が有限状態オートマトン(FSA)だけに限定されていた。

0006

本発明では、上記事情に鑑みて成されたものであり、曖昧性を解消した有限状態木オートマトンを生成することできる曖昧性解消装置、方法、及びプログラムを提供することを目的とする。

課題を解決するための手段

0007

上記目的を達成するために、本発明に係る曖昧性解消装置は、入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、前記有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成する曖昧性解消装置であって、入力された有限状態木オートマンAを受け付ける入力部と、(1)前記有限状態木オートマンAの初期状態iと前記初期状態iからなる状態集合とのペアに対する、前記有限状態木オートマンA’の初期状態(i,{i})を登録し、(2)前記有限状態木オートマンA’に登録されている状態(p,s)の各々について、(2−1)前記状態pが、前記有限状態木オートマンAの終了状態であって、前記状態(p,s)と同値関係にある状態が、前記有限状態木オートマンA‘の終了状態として登録されていない場合、前記状態(p,s)を、前記有限状態木オートマンA’の終了状態として登録し、(2−2)前記有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)前記状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)前記作成された組み合わせの各々について、(2−2−2−1)前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)前記生成された辺が、前記有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンA’の辺として登録し、前記作成された新たな状態(q、t)が、前記有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、前記新たな状態(q、t)を、前記有限状態木オートマンA’の状態として登録する曖昧性解消部と、前記有限状態木オートマンA’を出力する出力部と、を含んで構成されている。

0008

本発明に係る曖昧性解消方法は、入力部、曖昧性解消部、及び出力部を含み、入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、前記有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成する曖昧性解消装置における曖昧性解消方法であって、前記入力部が、入力された有限状態木オートマンAを受け付けるステップと、前記曖昧性解消部が、(1)前記有限状態木オートマンAの初期状態iと前記初期状態iからなる状態集合とのペアに対する、前記有限状態木オートマンA’の初期状態(i,{i})を登録し、(2)前記有限状態木オートマンA’に登録されている状態(p,s)の各々について、(2−1)前記状態pが、前記有限状態木オートマンAの終了状態であって、前記状態(p,s)と同値関係にある状態が、前記有限状態木オートマンA’の終了状態として登録されていない場合、前記状態(p,s)を、前記有限状態木オートマンA’の終了状態として登録し、(2−2)前記有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)前記状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)前記作成された組み合わせの各々について、(2−2−2−1)前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)前記生成された辺が、前記有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンA’の辺として登録し、前記作成された新たな状態(q、t)が、前記有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、前記新たな状態(q、t)を、前記有限状態木オートマンA’の状態として登録するステップと、前記出力部が、前記有限状態木オートマンA’を出力するステップと、を含む。

0009

また、本発明のプログラムは、入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、前記有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成するためのプログラムであって、コンピュータを、入力された有限状態木オートマンAを受け付ける入力部、(1)前記有限状態木オートマンAの初期状態iと前記初期状態iからなる状態集合とのペアに対する、前記有限状態木オートマンA’の初期状態(i,{i})を登録し、(2)前記有限状態木オートマンA’に登録されている状態(p,s)の各々について、(2−1)前記状態pが、前記有限状態木オートマンAの終了状態であって、前記状態(p,s)と同値関係にある状態が、前記有限状態木オートマンA’の終了状態として登録されていない場合、前記状態(p,s)を、前記有限状態木オートマンA’の終了状態として登録し、(2−2)前記有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)前記状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)前記作成された組み合わせの各々について、(2−2−2−1)前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)前記生成された辺が、前記有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンA’の辺として登録し、前記作成された新たな状態(q、t)が、前記有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、前記新たな状態(q、t)を、前記有限状態木オートマンA’の状態として登録する曖昧性解消部、及び前記有限状態木オートマンA’を出力する出力部として機能させるためのプログラムである。

発明の効果

0010

以上説明したように、本発明の曖昧性解消装置、方法、及びプログラムによれば、有限状態木オートマンA’に登録されている状態(p,s)の各々について、有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、作成された組み合わせの各々について、(2−2−2−1)組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、(2−2−2−2)生成された辺が、有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、生成された辺を、有限状態木オートマンA’の辺として登録し、作成された新たな状態(q、t)が、有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、新たな状態(q、t)を、有限状態木オートマンA’の状態として登録することにより、曖昧性を解消した有限状態木オートマトンA’を生成することができる、という効果が得られる。

図面の簡単な説明

0011

有限状態木オートマンと有限状態木オートマンに入力される木との例を示す図である。
本発明の実施の形態に係る曖昧性解消装置の機能的構成を示すブロック図である。
本発明の実施の形態に係る一般化曖昧性解消演算アルゴリズムの疑似コードを示す図である。
本発明の実施の形態に係る曖昧性解消装置における曖昧性解消処理ルーチンを示すフローチャート図である。
本発明の実施の形態に係る曖昧性解消装置における曖昧性解消処理ルーチンを示すフローチャート図である。
有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’の例を示す図である。

実施例

0012

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

0013

<本発明の実施の形態の概要
本発明の実施の形態では、上記非特許文献1に記載の曖昧性解消演算アルゴリズムを、有限状態木オートマトン(FTA)へも適用可能な形に一般化する。本発明の実施の形態における一般化曖昧性解消演算アルゴリズムは、有限状態木オートマトン(FTA)から同じ木構造を排除するためのアルゴリズムである。提案するアルゴリズムは、通常のFSAへも適用可能であるため、上記非特許文献1に記載の従来のアルゴリズムよりも適用範囲が広い。

0014

図1(A)に有限状態木オートマトン(FTA)の例を示す。図1(A)の状態1と状態2とから、状態4への遷移、状態1と状態3とから状態4への遷移のように、複数の状態で構成された始点から次の状態への遷移が許されるため、FTAでは木構造を表現することができる。図1(A)のFTAでは、図1(B)に示すような木構造を受理することができる。図1(A)のFTAには、図1(B)の左側の木構造D(A B)を受理できる経路が次のように2つ存在している。

0015

A(0)→1,B(0)→2,D(1,2)→4
A(0)→1,B(0)→3,D(1,3)→4

0016

よって、上記図1(A)に示すFTAは曖昧性を持つことがわかる。提案するアルゴリズムは、異なる経路は必ず異なる木構造を受理することが保証されるように変換を行う。また、変換後のFTAは、変換前のFTAで受理することができる全ての木構造を受理することができる(等価な表現能力を保持している)。また、変換後のFTAの状態数は、元のFTAの状態数Nに対して、最悪の場合でも、

0017

0018

に抑えられる。

0019

次に、本発明の実施の形態に係る曖昧性解消装置の構成について説明する。なお、本発明の実施の形態では、入力された有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成する曖昧性解消装置に、本発明を適用させた場合を例に説明する。

0020

<曖昧性解消装置の構成>
本発明の実施の形態に係る曖昧性解消装置について説明する。図2に示すように、本発明の実施の形態に係る曖昧性解消装置100は、CPUと、RAMと、後述する曖昧性解消処理ルーチンを実行するためのプログラムや各種データを記憶したROMと、を含むコンピュータで構成することが出来る。この曖昧性解消装置100は、機能的には図2に示すように入力部10と、曖昧性解消部20と、出力部30とを備えている。

0021

入力部10は、有限状態木オートマトン(FTA)Aを受け付ける。なお、本実施の形態では、有限状態木オートマトンA=(Σ,Q,i,F,E)を以下のように定義する。

0022

Σはランク付きアルファベットであり、Qは状態の有限集合であり、i∈Qは初期状態であり、F⊆Qは終了状態の集合であり、E⊆Q×・・・×Q×Σ(k)×Qはk個の状態から成るベクトルを入力にして次の状態へと遷移する辺の集合である。また、辺はσ(q1,...,qk)→q(q,q1,...,qk∈Q,σ∈Σ(k))として書く。

0023

例えば、上記図1(A)に示すオートマトンは、次の要素から構成される。

0024

Σ={A(1),B(1),C(1),D(2)},
Q={0,1,2,3,4}
i=0,
F={4},
E={A(0)→1,B(0)→2,C(0)→3,B(0)→3,D(1,2)→4,D(1,3)→4}

0025

曖昧性解消部20は、入力部10によって受け付けた有限状態木オートマンAから、有限状態木オートマンAの曖昧性を解消した有限状態木オートマトンA’であって、有限状態木オートマンAの状態pと状態集合sとのペアに対する状態(p,s)を有する有限状態木オートマトンA’を生成する。

0026

曖昧性解消部20において実行される一般化曖昧性解消演算アルゴリズムの疑似コードを、図3に示す。図3に示したAlgorithm1は、有限状態木オートマトン(FTA)を適用可能な形に一般化した一般化曖昧性解消演算アルゴリズムである。このアルゴリズムはFTA[A]=(Σ,Q,i,F,E)を入力として、FTA[A’]=(Σ,Q’,i’; F’;E’) を出力する。なお、図3に示す筆記体の「Q」は、以下「Queue」と称する。

0027

図3に示したアルゴリズムではA’における2つの状態に対して、同値関係Rを定義する。Rは2つの状態が同じ木で到達できる実行を持つときに関係を持つ。疑似コードの2行目では、有限状態木オートマンAと有限状態木オートマンAとの積集合を計算し、その結果から終了状態へ到達できない状態を排除したFTAをBに代入する。なお、FTAの積集合演算はO(|Q|2)で計算でき、上記図3に示した疑似コード内のpruneUselessStates(・)は状態数に対して線形時間で計算できる。Bに存在する状態は(q,r)(q,r∈Q)の形をとり、qとrは同じ木で到達できる実行を持ち、そこから同じ木で終了状態に至る実行を共有するため、定数時間でこのことをチェックするのにBを使う。

0028

曖昧性解消部20は、まず、以下の処理(1)を行う。なお、疑似コードにおけるM及びcandは情報が格納されるリストを表し、Addはリストの最後尾への格納処理を表し、Get(M,v)はリストMのv番目の要素の読み出し処理を表す。
処理(1)では、有限状態木オートマンAの初期状態iと当該初期状態iからなる状態集合とのペアに対する状態(i,{i})を、有限状態木オートマンA’の初期状態i’として登録する。
具体的には、曖昧性解消部20は、上記図3に示した疑似コードの3行目において、A’の初期状態i’を状態(i,{i})として初期化する。また、A’の状態は(p,s)(p∈Q,s∈Q*)の形をとる。sは同じ木によって到達できる状態の集合とする。iはε遷移によって、iに到達すると考えることができる。なお、同値関係Rの記号について、例えば、疑似コードにおける(p’,s’)R(p,s)は、状態(p,s)と状態(p’,s’)とが同値関係にあることを示す。
上記図3に示した疑似コードの4行目では、新たな状態の集合Q’に、5行目ではキューQueueに状態i’を追加する。6行目では関係Rに(i’,i’)を追加する。7行目では、リストM(i)に状態i’を追加する。リストM(p)は(p,・)∈Q’を読み出すために構築する。

0029

次に、曖昧性解消部20は、以下の処理(2)を行う。
処理(2)では、有限状態木オートマンA’に登録されている状態(p,s)の各々について、以下の処理(2−1)、(2−2)を行う。
処理(2−1)では、状態pが、有限状態木オートマンAの終了状態であって、状態(p,s)と同値関係にある状態が、有限状態木オートマンA’の終了状態として登録されていない場合、当該状態(p,s)を、有限状態木オートマンA’の終了状態として登録する。

0030

具体的には、曖昧性解消部20は、上記図3に示した疑似コードの8行目から33行目において、新たな状態と辺を構築する繰り返し処理を行う。疑似コードの9行目から12行目では8行目でキューから取り出し状態(p,s)が終了状態であるかをチェックし、F’に登録する。ただし、(p’,s’)R(p,s)が存在する、すなわち、同じ木で終了状態に至る(p’,s’)がすでに存在する場合は(p,s)をF’に登録しない。

0031

処理(2−2)では、有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、以下の処理(2−2−1)、(2−2−1)を行う。
処理(2−2−1)では、当該状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成する。
具体的には、疑似コードの13行目から32行目では、pから出る辺σ(k)(p1,...,p,...,pk)→qごとに処理が進む。14行目のGetCandidate関数では、p1,...,pkに対してすでに構築されたA’の状態をリストM(・)の先頭から読み出す(39から41行目)。ただし、pに対しては(p,s)を使う。40行目の1はk次元数値ベクトルで、各次元の値は全て1をとる。
また、疑似コードの30行目のAppendNext関数では、状態p1,...,p,...,pkのp 以外の状態に対して、リストMに登録された次の状態へ更新することで、A’におけるk個の状態集合とk次元の数値ベクトルの新たなペアを作り出す。AppendNext関数の48行目のbiはi次元目だけが1、その他の次元は全て0を持つk次元の数値ベクトルを表す。49行目から54行目では、i番目の状態をM(pi)に登録されている次の状態に置き換えることで、新たなペアをcandに追加している。

0032

処理(2−2−2)では、処理(2−2−1)で作成された組み合わせの各々について、以下の処理(2−2−2−1)、(2−2−2−2)を行う。
処理(2−2−2−1)では、当該組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、当該組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成する。
処理(2−2−2−2)では、処理(2−2−2−1)で生成された辺が、有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、生成された辺を、有限状態木オートマンA’の辺として登録し、処理(2−2−2−1)で作成された新たな状態(q、t)が、有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、新たな状態(q、t)を、有限状態木オートマンA’の状態として登録する。
具体的には、疑似コードの15行目から31行目の処理において、candに登録されたA’におけるk個の状態集合とk次元の数値ベクトルのペアがなくなるまで繰り返す。17行目にあるδ(s,σ)は、状態集合sに含まれる全ての状態から記号σで遷移できる状態の集合を表す。17行目で作られる状態集合tは各状態集合s1,...,s,...,skから記号σ(k)で遷移できる状態集合の積集合をとったものである。

0033

また、上記図3に示した疑似コードの18行目から29行目において、新たな状態(q,t)と辺σ(k)((p1,s1),...,(p,s),...,(pk,sk))→(q,t)の登録を行う。ただし、18行目で(p’1,s’1)R(p1,s1)...(p’,s’)R(p,s)...(p’k,s’k)R(pk,sk)を持つ辺σ(k)((p’1,s’1),...,(p’,s’),...,(p’k,s’k))→(q,t)がE’にすでに存在しないかをチェックし、存在しない場合のみ24行目でE’に登録を行う。19行目から23行目では(q,t)がQ’ に登録されていないとき、Q’,Queue,M(q)への登録を行う。

0034

25行目から28行目では(q,t)について関係Rを構築できるか調べる。((p’1,s’1)R(p1,s1)...(p’ ,s’)R(p,s)...(p’k,s’k)R(pk,sk))を持つ辺(k)((p’1,s’1),...,(p’ ,s’),...,(p’k,s’k))→(q’ ,t’) があるとき、(q,t)と(q’ ,t’)は同じ木で到達できることを意味する。よって、27行目でそれらを関係Rに登録する。

0035

出力部30は、曖昧性解消部20によって登録された有限状態木オートマンA’を結果として出力する。

0036

<曖昧性解消装置の作用>
次に、本発明の実施の形態に係る曖昧性解消装置100の作用について説明する。まず、入力部10により、有限状態木オートマンAが入力される。そして、曖昧性解消装置100のROMに記憶されたプログラムを、CPUが実行することにより、図4及び図5に示す曖昧性解消処理ルーチンが実行される。

0037

まず、ステップS100において、入力部10によって、有限状態木オートマトンAを受け付ける。

0038

次に、ステップS101において、上記ステップS100で受け付けた有限状態木オートマトンAに基づいて、有限状態木オートマトンAと有限状態木オートマトンAとの積集合を計算し、その結果から終了状態へ到達できない状態を排除したFTAをBに代入する。

0039

次に、ステップS102において、曖昧性解消部20によって、有限状態木オートマンA’の初期状態(i,{i})を、i’,Q’,Queue,M(i)へ登録する。また、{(i’,i’)}をRへ登録する。

0040

次に、ステップS104において、曖昧性解消部20によって、上記ステップS102で登録処理が行われたQueue又は後述するステップS124で前回登録処理が行われたQueueが空集合であるか否かを判定する。Queueが空集合である場合には、ステップS134へ移行する。一方、Queueが空集合でない場合には、ステップS106へ進む。

0041

次に、ステップS106において、曖昧性解消部20によって、上記ステップS102で登録処理が行われたQueue又は後述するステップS124で前回登録処理が行われたQueueから、状態(p,s)を取り出す。

0042

ステップS108において、曖昧性解消部20によって、上記ステップS106で取り出された状態(p,s)と同値関係にある有限状態木オートマンA’の状態(p’,s’)において、p∈Fかつ

0043

0044

であるか否かを判定条件とし、上記ステップS106で取り出された状態(p,s)を終了状態とすることができるか否かを判定する。上記判定条件を満たす場合には、状態(p,s)を終了状態とすることができると判定し、ステップS110へ進む。一方、上記判定条件を満たさない場合には、状態(p,s)を終了状態とすることができないと判定し、ステップS112へ移行する。

0045

ステップS110において、上記ステップS106で取り出された状態(p,s)をF’に登録する。

0046

ステップS112において、曖昧性解消部20によって、有限状態木オートマンAにおいて、上記ステップS106で取り出された状態(p,s)の状態pから出る1つの辺を設定する。

0047

ステップS114において、曖昧性解消部20によって、上記ステップS112で設定された辺の各始点に対応する状態の組み合わせ(p1,...,p,...,pk)に基づいて、上記ステップS102で登録処理が行われたM、又は後述するステップS124で前回登録処理が行われたMの先頭から、状態集合{(p1,s1),...,(p,s),...,(pk,sk)}を読み出し、状態集合{(p1,s1),...,(p,s),...,(pk,sk)}と数値ベクトルとのペアをcandに登録する。

0048

ステップS116において、曖昧性解消部20によって、上記ステップS114で登録処理が行われたcandが空であるか否かを判定する。candが空である場合には、ステップS132へ移行する。一方、candが空でない場合には、ステップS118へ進む。

0049

ステップS118において、曖昧性解消部20によって、上記ステップS114で登録処理が行われたcandから、状態集合{(p1,s1),...,(p,s),...,(pk,sk)}と数値ベクトルとのペアを取り出し、状態集合{(p1,s1),...,(p,s),...,(pk,sk)}と数値ベクトルとのペアに基づいて、新しい状態(q,t)及び新しい辺σ(k)((p1,s1),...,(p,s),...,(pk,sk))→(q,t)を構築する。

0050

ステップS120において、曖昧性解消部20によって、上記ステップS118で構築された新しい辺σ(k)((p1,s1),...,(p,s),...,(pk,sk))→(q,t)が曖昧性を作るか否かを判定する。新しい辺σ(k)((p1,s1),...,(p,s),...,(pk,sk))→(q,t)が曖昧性を作る場合には、ステップS130へ移行する。一方、新しい辺σ(k)((p1,s1),...,(p,s),...,(pk,sk))→(q,t)が曖昧性を作らない場合には、ステップS122へ進む。

0051

ステップS122において、曖昧性解消部20によって、上記ステップS118で構築された新しい状態(q,t)が、Q’に登録されているか否かを判定する。新しい状態(q,t)が、Q’に登録されていない場合には、ステップS124へ進む。一方、新しい状態(q,t)が、Q’に登録されている場合には、ステップS126へ移行する。

0052

ステップS124において、曖昧性解消部20によって、上記ステップS118で構築された新しい状態(q,t)をQ’、Queue、Mに登録する。

0053

ステップS126において、曖昧性解消部20によって、上記ステップS118で構築された新しい辺σ(k)((p1,s1),...,(p,s),...,(pk,sk))→(q,t)をE’に登録する。

0054

ステップS128において、曖昧性解消部20によって、上記ステップS118で構築された新しい状態(q,t)と、同値関係Rを構築することができる状態が存在する場合には、同値関係Rを構築する。

0055

ステップS130において、曖昧性解消部20によって、状態(p1,...,p,...,pk)のp 以外の状態について、Mに登録された次の状態へ更新することで、A’におけるk個の状態集合{(p1,s1),...,(p,s),...,(pk,sk)}とk次元の数値ベクトルの新たなペアを作成し、作成されたペアをcandへ登録する。

0056

ステップS132において、曖昧性解消部20によって、上記ステップS112で設定された状態pから出る全ての辺について、上記ステップS112〜S130の処理を実行したか否かを判定する。状態pから出る全ての辺について、上記ステップS112〜S130の処理を実行した場合には、ステップS104へ戻る。一方、状態pから出る全ての辺について、上記ステップS112〜S130の処理を実行していない場合には、ステップS112へ戻る。

0057

ステップS134において、出力部30によって、曖昧性が解消された有限状態木オートマンA’を結果として出力して、曖昧性解消処理ルーチンを終了する。

0058

以上説明したように、本発明の実施の形態に係る曖昧性解消装置によれば、有限状態木オートマンA’に登録されている状態(p,s)の各々について、有限状態木オートマンAにおける、状態pを含む状態p1,・・・,pkの組み合わせを始点とする辺の各々に対し、(2−2−1)状態(p,s)を含む、状態(p1、s1),・・・,状態(pk、sk)の組み合わせを各々作成し、(2−2−2)作成された組み合わせの各々について、(2−2−2−1)組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺から遷移する新たな状態(q、t)を作成すると共に、前記組み合わせの状態(p1、s1),・・・,状態(pk、sk)を始点とする辺を生成し、生成された辺が、有限状態木オートマンA’に登録されている辺に対して、曖昧性を作らない場合に、生成された辺を、有限状態木オートマンA’の辺として登録し、作成された新たな状態(q、t)が、有限状態木オートマンA’に登録されている状態の集合に含まれない場合に、新たな状態(q、t)を、有限状態木オートマンA’の状態として登録することにより、曖昧性を解消した有限状態木オートマトンA’を生成することができる。

0059

また、本発明の実施の形態は、入力された有限状態木オートマトン(FTA)に対して、元のFTAと等価で、かつ曖昧性のないFTAを構築することができる。

0060

また、有限状態オートマトン(FSA)にも適用可能である(上記非特許文献1の従来法を包含している)。

0061

また、従来手法である決定化(上記非特許文献2を参照)では、最悪の場合、状態数が2Nに増幅するのに対し、本発明の実施の形態では

0062

0063

に抑えられる。

0064

また、本発明の実施の形態が従来法である上記非特許文献1のアルゴリズムと異なる点は、木が扱えることにある。木を扱うためには、辺の始点が複数あることをアルゴリズムに考慮する必要がある。そのため、本発明の実施の形態における一般化曖昧性解消演算アルゴリズムのGetCandidate関数、及びAppendNext関数は、従来法には存在しなかった。また、上記図3に示した疑似コード17、18、25行目の操作でも、始点が複数あることを考慮した処理になっている。

0065

[実施例]
図6に、上記図1に示したFTAに、一般化曖昧性解消演算アルゴリズムを適用してできるFTAを示す。点線で表された遷移は、どちらか一方のみが構築される。どちらの遷移が構築されるかは、一般化曖昧性解消演算アルゴリズムで使われている優先度付きキューQueueの設計に依存する。図6からもわかるように、同じ木構造を持つ経路は1つだけとなっている。

0066

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

0067

上述の曖昧性解消装置100は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。

0068

また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。

0069

10 入力部
20 曖昧性解消部
30 出力部
100 曖昧性解消装置

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 株式会社ソケッツの「 検索装置および方法」が 公開されました。( 2019/09/19)

    【課題】同一の感性ワードで加重的に絞り込み検索を行えるようにする。【解決手段】同一の感性ワードで加重的に絞り込み検索を行う場合、類似・関連ワード抽出部319が、感性ワードに類似・関連する別のワードを検... 詳細

  • ヤフー株式会社の「 情報処理装置、情報処理方法、及び情報処理プログラム」が 公開されました。( 2019/09/12)

    【課題】ユーザの移動の妨害に応じた適切な対応を可能にする。【解決手段】本願に係る情報処理装置は、取得部と、決定部とを有する。取得部は、ユーザの位置情報と、ユーザが位置するエリアにおいて発生する事象のう... 詳細

  • ヤフー株式会社の「 情報処理装置、情報処理方法、及び情報処理プログラム」が 公開されました。( 2019/09/12)

    【課題】類似のコンテンツを適切に抽出する。【解決手段】本願に係る情報処理装置は、取得部と、検索部とを有する。取得部は、複数のコンテンツの各々に対応する複数のノードが、複数のコンテンツの類似性に応じて連... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ