(57)【要約】【課題】本発明は、入力文字列の集合をパターン表現に変換する過程において、特定の種類の記述集合に対する知見に基づく独自推論を再利用可能にする技法を提供することを目的とする。【解決手段】本発明は、入力文字列の集合をパターン表現に変換する過程において、当該変換の変換パターンを近似パターン表現式として取り出す技法を提供する、当該技法は、１）状態を表す複数のノードと、遷移を表す複数のエッジとを有する１つの構造体を準備すること、２）上記１つの構造体中の少なくとも１つの状態を上記１つの構造体から除去し、当該除去された状態に関連付けられたエッジを含む上記１つの構造体中の少なくとも２つのエッジをマージして、縮退された第１の構造体を生成すること、３）上記縮退された第１の構造体に基づいて第１の近似パターン表現式を生成すること、及び４）上記第１の近似パターン表現式を提示することを含む。【選択図】図３Ａ
2014006877.tif 000002
【特許請求の範囲】
【請求項１】
入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、前記入力文字列の集合から前記パターン表現に変換する変換パターンを近似パターン表現式として取り出す方法であって、コンピュータが、
状態を表す複数のノードと、遷移を表す複数のエッジとを有する１つの構造体を準備するステップであって、各エッジが前記入力文字列の集合中の部分文字列の集合（以下、「エッジが持つ文字列の集合」という）をラベルとして持つ、前記準備するステップと、
（Ａ）前記１つの構造体中の少なくとも１つの状態の除去によりマージされることになる少なくとも２つのエッジに関連付けられた前記１つの構造体中の部分構造体の変化量を評価する状態除去指標に基づいて、
（Ｂ）当該部分構造体と他の部分構造体との若しくは前記１つの構造体との包含関係に基づいて、又は、
（Ｃ）前記状態除去指標と前記包含関係の組み合わせに基づいて、
前記１つの構造体中の少なくとも１つの状態を前記１つの構造体から除去し、当該除去された状態に関連付けられたエッジを含む前記１つの構造体中の少なくとも２つのエッジをマージして、縮退された第１の構造体を生成するステップと、
前記縮退された第１の構造体に基づいて第１の近似パターン表現式を生成するステップと、
前記第１の近似パターン表現式を提示するステップと
を実行することを含む、前記方法。
【請求項２】
前記状態除去指標が、前記１つの構造体中のある状態を除去することによるエッジのマージ回数と、当該ある状態の除去によりマージされることになるエッジに関連付けられた各状態に到達する入力文字列の数とから求められる、請求項１に記載の方法。
【請求項３】
前記状態除去指標が、下記式：
前記ある状態の入力エッジ数（IN）・当該ある状態の出力エッジ数（OUT）＋当該ある状態よりも一つ前の遷移ステップにある状態と一つ後の遷移ステップにある状態との間にある直接のエッジの数（COM）
から求められる、請求項１に記載の方法。
【請求項４】
前記状態除去指標が、下記関数式Ｆ：
（１）F(N, IN・OUT＋COM) = N(IN・OUT+COM)、
（２）F(N, IN・OUT＋COM) = N・log(IN・OUT+COM)、又は
（３）上記（２）の関数式ＦにおいてCOMを無視した関数式F(N, IN・OUT)= N・log(IN・OUT)、
のいずれかによって求められ、ここでNは前記入力文字列の集合の数である、請求項３に記載の方法。
【請求項５】
前記１つの構造体を前記状態除去指標に基づいて除去することが、前記１つの構造体中の各状態のうちの前記状態除去指標が最小である状態を特定し、当該特定された状態を前記１つの構造体から除去することによって行われる、請求項１に記載の方法。
【請求項６】
前記状態除去指標が、前記１つの構造体中のある状態からエッジが分岐して合流する状態までの部分（以下、「抽象化単位」という）が前記１つの構造体中の他の抽象化単位を真に包含しない場合において、前記１つの構造体中の各状態のうち、到達する入力文字列の集合の数（N）が最小値をとる状態に対して定義されるメトリクスである、請求項１に記載の方法。
【請求項７】
前記状態除去指標が、前記１つの構造体中の状態sを端点とする共通コンテキスト内パス集合が前記１つの構造体中の他の共通コンテキスト内パス集合を真に包含しない場合において、前記１つの構造体中の各状態のうち、到達する入力文字列の集合の数（N）が最小値をとる状態に対して定義されるメトリクスであり、
前記１つの構造体中の状態ｓを端点とする共通コンテキスト内パス集合とは、状態sから出た２つ以上のパスが状態s’で合流する場合又はある状態s’から出た２つ以上のパスが状態sで合流する場合に、状態sから状態s’又は状態s’から状態sへのパスの集合である、請求項１に記載の方法。
【請求項８】
前記コンピュータが、前記状態を除去することを繰り返し実行し、当該除去の度に、前記提示するステップを実行する、請求項１に記載の方法。
【請求項９】
前記コンピュータが、
前記第１の近似パターン表現式をパターン表現推論関数として格納部に格納するステップであって、前記パターン表現推論関数は前記第１の近似パターン表現式を生成するために利用されうる、前記格納するステップ
をさらに実行することを含む、請求項７に記載の方法。
【請求項１０】
前記第１の近似パターン表現式を生成するステップが、前記格納部に格納された、前記第１の近似パターン表現式を包含する近似パターン表現式のうちから選択された近似パターン表現式を前記縮退された第１の構造体に適用するステップを含む、請求項９に記載の方法。
【請求項１１】
前記縮退された第１の構造体が、前記除去された状態に関連付けられたエッジが持つ文字列の集合を統合した文字列の集合を、前記状態を除去することによって統合されたエッジのラベルとして持つ、請求項１に記載の方法。
【請求項１２】
前記コンピュータが、
前記１つの構造体中の任意の少なくとも２つの状態について、当該少なくとも２つの状態の各当該状態よりも後のｋ遷移ステップ（ｋは１以上の整数である）以内のパスが持つラベル列の集合が同じである場合に、又は、
前記１つの構造体中の任意の少なくとも２つの状態について、当該少なくとも２つの状態のうちの一つの状態よりも後のｍ遷移ステップ（ｍは１以上の整数である）以内のパスが持つラベル列の集合が当該少なくとも２つの状態のうちの他の一つの状態よりも後のｎ遷移ステップ（ｎは１以上の整数である）以内のパスが持つラベル列の集合を包含する場合に、
前記同じであるラベル列の集合又は前記包含されるラベル列の集合のいずれかを持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退された第２の構造体を生成するステップと、
前記縮退された第２の構造体に基づいて第２の近似パターン表現式を生成するステップと、
前記第２の近似パターン表現式を提示するステップと
をさらに実行することを含む、請求項１に記載の方法。
【請求項１３】
前記コンピュータが、前記遷移の集合及び前記状態の集合をマージすることを繰り返し実行し、当該マージの度に、前記提示するステップを実行する、請求項１２に記載の方法。
【請求項１４】
前記縮退された第２の構造体が、前記マージされた状態に関連付けられたエッジが持つラベルの部分文字列の集合（以下、「エッジのラベル」という）を統合した部分文字列の集合を、前記状態をマージすることによって統合されたエッジのラベルとして持つ、請求項１２に記載の方法。
【請求項１５】
前記近似パターン表現式がパターン表現の記述の一部に０個以上の推論関数を表す記号を含むパターンである、請求項１に記載の方法。
【請求項１６】
前記準備するステップにおいて、前記１つの構造体が前記入力文字列から生成された１つの構造体、又は、前記入力文字列から生成された１つの構造体が縮退された構造体のいずれかである、請求項１に記載の方法。
【請求項１７】
入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する方法であって、コンピュータが、
請求項１〜１１及び１５〜１７のいずれか一項に記載の前記第１の近似パターン表現式を生成するステップを少なくとも１回実行するステップと、
前記第１の近似パターン表現式を当該第１の近似パターン表現式の生成の度に提示するステップと、
前記第１の近似パターン表現式に対応するパターン表現を提示するステップと
を実行することを含む、前記方法。
【請求項１８】
前記コンピュータが、
請求項１２〜１４のいずれか一項に記載の前記第２の近似パターン表現式を生成するステップを少なくとも１回実行するステップと、
前記第２の近似パターン表現式を当該第２の近似パターン表現式の生成の度に提示するステップと、
前記第２の近似パターン表現式に対応するパターン表現を提示するステップと
をさらに実行することを含む、請求項１７に記載の方法。
【請求項１９】
入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、前記入力文字列の集合から前記パターン表現に変換する変換パターンを近似パターン表現式として取り出すコンピュータであって、
状態を表す複数のノードと、遷移を表す複数のエッジとを有する１つの構造体を準備する第１の生成部であって、各エッジが前記入力文字列の集合中の部分文字列の集合（以下、「エッジが持つ文字列の集合」という）をラベルとして持つ、前記第１の生成部と、
（Ａ）前記１つの構造体中の少なくとも１つの状態の除去によりマージされることになる少なくとも２つのエッジに関連付けられた前記１つの構造体中の部分構造体の変化量を評価する状態除去指標に基づいて、
（Ｂ）当該部分構造体と他の部分構造体との若しくは前記１つの構造体との包含関係に基づいて、又は、
（Ｃ）前記状態除去指標と前記包含関係の組み合わせに基づいて、
前記１つの構造体中の少なくとも１つの状態を前記１つの構造体から除去し、当該除去された状態に関連付けられたエッジを含む前記１つの構造体中の少なくとも２つのエッジをマージして、縮退された第１の構造体を準備する第２の生成部と、
前記縮退された第１の構造体に基づいて第１の近似パターン表現式を生成する表現式生成部と、
前記第１の近似パターン表現式を提示する提示部と
を備えている、前記コンピュータ。
【請求項２０】
入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、前記入力文字列の集合から前記パターン表現に変換する変換パターンを近似パターン表現式として取り出すコンピュータ・プログラムであって、コンピュータに、請求項１〜１８のいずれか一項に記載の方法の各ステップを実行させる前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する手法に関する。特には、本発明は、上記入力文字列の集合から上記少なくとも１つのパターン表現に変換する過程において、上記入力文字列の集合から上記パターン表現に変換する変換パターンを近似パターン表現式として取り出す手法に関する。
【背景技術】
【０００２】
ソフトウェア開発における文書成果物を分析するツールではしばしば、ツール設定において、処理対象としたい文字列の部分を抽出するために正規表現が利用されている。当該抽出の対象は、プロジェクトに固有の特定の法則に従う類似の大量な文字列の集合でありうる。しかしながら、既存ツールにおいて当該法則を表すパターンは手作業で適切な正規表現として求められなければならない。従って、文字列の部分を抽出する処理の自動化又は上記ツールのアクセスビリティが著しく制限されている。
【０００３】
上流文書成果物を扱うツールにおける正規表現は、例えば下記に示す目的のために利用されうる：
・文書中から特定の部分を正規表現により取り出して利用する；
・ある処理を適用するファイルを正規表現で指定する；
・フォルダ中に含まれるファイルを正規表現により分類し、適した処理を行う；及び、
・テキスト群から共通部分又は可変部分を取り出すことによって、意味情報を取り出し利用する。
【０００４】
また、上流文書成果物の分析以外、例えばコンパイラの字句解析、ウェブ（Ｗｅｂ）などのテキストからのキーワード検索、及び、フォルダ中に存在するファイルに対して、ファイル毎に別々の処理を行いたい場合に、正規表現によるファイル名のマッチによってファイルを取り出し、特定の処理を特定のファイルに対しておこなうという場面において、正規表現が使用されうる。
【０００５】
下記特許文献１は、ユーザとの対話機能を有して、ユーザが情報要求を入力するたびに、ユーザとのやり取りの履歴を用いてユーザの情報要求内容を特定し、それに応じてユーザに対して応答する対話装置で実行される対話方法、対話装置、対話プログラム及び対話プログラムを記録した記録媒体を記載する（特許請求の範囲）。
【０００６】
下記特許文献２は、日常言語の意味の体系を構造化したセミオティックベースに基づいて言語テクストの処理を行う日常言語コンピュータシステムで用いられ、ユーザと日常言語コンピュータシステムとの間での言語テクストの対話的なやりとりを支援する秘書エージェントシステム及び秘書エージェントプログラム、並びに日常言語の意味の体系を構造化したセミオティックベースに基づいて言語テクストの処理を行う日常言語コンピュータシステムで用いられる対話プランニング方法を記載する（特許請求の範囲）。
【０００７】
下記特許文献３は、ソース言語文字列の翻訳に関連したウエイトをユーザが視認し変更することを可能とする方法、ソース言語の翻訳に関連したウエイトをユーザが視認し変更することを可能とする機械翻訳システム、及び翻訳のウエイトをユーザが視認し変更することを可能とするためのコンピュータ読み取り可能プログラム手段を有する製造物を記載する（特許請求の範囲）。
【０００８】
下記特許文献４は、決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と、終了状態か否かを表す終了性とが同じ状態毎に分類し、状態の集合を生成する状態分類部と、前記状態の集合毎に、当該状態の集合に含まれる各状態から遷移する遷移先状態の集合との積集合を算出し、この積集合に含まれる要素の数が１以下となるまで、当該積集合に含まれる各状態の入力記号毎の遷移先状態の集合を新たな状態の集合とみなして、前記積集合の算出を繰り返し実行する探索部と、前記積集合に含まれる要素数が１以下となった状態から、前記探索部が辿った遷移方向とは逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合する状態併合部と、を備えたことを特徴とする情報処理装置を記載する（請求項１）。
【０００９】
下記特許文献５は、不確定文字列の検索文字列による検索を行うが、この不確定文字列は、文字ごとの各候補文字を選択によって結合すると共に、各文字を連結によって結合した正規表現として表すことができるので、上記検索処理に代えて、この正規表現によって構成される有限オートマトンを用いた検索処理を行うことも可能となり、ただし、この場合には、文字ごとの各候補文字の状態に加えて、これらの候補文字以外の全ての文字を受理する状態を追加すると共に、各候補文字の状態に確度値を対応付けておき、部分文字列から文字を受理することにより実際に遷移した状態の確度値を順次加算するような処理とする必要があることを記載する（段落００６７）。
【００１０】
下記特許文献６は、構文解析技術を用いることなく、自然文から構造化された情報を抽出する技術を提供することを記載する（要約書）。
【００１１】
下記特許文献７は、入力文字列を正規化するシステムを記載する（請求項１）。
【００１２】
下記特許文献８は、知識ベースシステムおよび自然言語理解方式を記載する（特許請求の範囲）。
【００１３】
下記特許文献９は、対話処理を実行する情報処理装置及び情報処理方法を記載する（特許請求の範囲）。
【００１４】
下記特許文献１０は、任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する装置及び生成方法を記載する（特許請求の範囲）。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００４−３５４７８７号公報
【特許文献２】特開２００４−１３９４４６号公報
【特許文献３】特表２００４−５１３４５８号公報
【特許文献４】特開２０１０−７９７２３号公報
【特許文献５】特開平８−３０５７２２号公報
【特許文献６】特開２０１１−１２３７９４号公報
【特許文献７】特開２００２−２２９９８１号公報
【特許文献８】特開平１−１８００４６号公報
【特許文献９】特開２００５−３０１７８０号公報
【特許文献１０】特開２０１１−１４１６２７号公報
【非特許文献】
【００１６】
【非特許文献１】A. Biermann and J. Feldman, “On the synthesis of finite-state machines from samples of their behavior”, IEEE Transactions on Computers,21:591-597, 1972
【発明の概要】
【発明が解決しようとする課題】
【００１７】
既存手法の多くは、特定の基準のもとで正規表現を推論する汎用的な技法である。従って、独自記法を持つ記述パターン、例えば上流文書成果物の分析で必要となるプロジェクト固有の記述パターン、の処理において、ユーザが望む正規表現を機械的に推論することは既存の正規表現推論法の技法では難しい。また、特定の知見に基づいた独自の推論の対象の文字列集合の一部分に再利用することができない。その為に、汎用的で精度の悪い推論手法により正規表現が求められている。
【００１８】
そこで、本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現、例えば正規表現に変換する過程において、特定の種類の記述集合に対する知見に基づく独自推論を再利用可能にする技法を提供し、さらには、具体的なパターン表現への変換から抽象的なパターン表現への変換へと段階的にパターン表現の推論を可能にする技法を提供することを目的とする。特定の種類の記述集合とは、例えば、プログラム名のセット、仕様書名のセット、及び、パラメータに対する値の設定方法の記述セットである。
【００１９】
具体的には、本発明は、第１に、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、当該入力文字列の集合からのパターン表現の推論を段階的に行い、下記に示すような推論の変換パターンを再利用する機能を提供することを目的とする：
・一度行った推論を再利用可能な形で取り出し、獲得し、保存する機能；
・パターン表現の段階的な推論の過程において、特定の部分に独自の推論関数を適用することを可能にする機能；及び、
・パターン表現の推論方法の知見を保存するために、入力文字列の集合からパターン表現に変換する変換パターンを記述する機能。
【００２０】
具体的には、本発明は、第２に、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、入力文字列の集合に対するパターン表現のバリエーションが段階的に具体的なパターン表現から抽象的なパターン表現になるように、すなわち段階的に抽象度が高くなるようにパターン表現を推論してユーザに提示する機能を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する技法、当該変換過程において、当該入力文字列の集合からパターン表現に変換する変換パターンを近似パターン表現式として取り出す技法、特には入力文字列の集合を段階的に具体的なパターン表現への変換から抽象的なパターン表現への変換になるようにパターン表現を推論する技法を提供する。当該技法は、方法、コンピュータ、コンピュータ・プログラム及びコンピュータ・プログラム製品を包含しうる。
【００２２】
本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、当該入力文字列の集合から上記パターン表現に変換する変換パターンを近似パターン表現式として取り出す方法を提供する。当該方法は、
（１）状態を表す複数のノードと、遷移を表す複数のエッジとを有する１つの構造体を準備するステップと、
（２）上記１つの構造体中の少なくとも１つの状態を上記１つの構造体から除去し、当該除去された状態に関連付けられたエッジを含む上記１つの構造体中の少なくとも２つのエッジをマージして、縮退された第１の構造体を生成するステップと、
（３）上記縮退された第１の構造体に基づいて第１の近似パターン表現式を生成するステップと、
（４）上記第１の近似パターン表現式を提示するステップ
とを含む。上記ステップ（２）において、（Ａ）上記１つの構造体中の少なくとも１つの状態の除去によりマージされることになる少なくとも２つのエッジに関連付けられた上記１つの構造体中の部分構造体の変化量を評価する状態除去指標に基づいて、（Ｂ）当該部分構造体と他の部分構造体との若しくは上記１つの構造体との包含関係に基づいて、又は、（Ｃ）上記状態除去指標と上記包含関係の組み合わせに基づいて、上記１つの構造体中の少なくとも１つの状態が上記１つの構造体から除去され、当該除去された状態に関連付けられたエッジを含む上記１つの構造体中の少なくとも２つのエッジがマージされる。
【００２３】
上記ステップ（１）において準備される１つの構造体は、例えば、上記入力文字列から生成された１つの構造体、例えば有限オートマトンでありうる。よって、上記ステップ（１）は、上記入力文字列から上記１つの構造体を生成するステップを含みうる。
【００２４】
また、上記ステップ（１）において準備される１つの構造体は、例えば、上記入力文字列から生成された１つの構造体が縮退された構造体でありうる。上記ステップ（１）は、上記入力文字列から１つの構造体を生成し、当該生成された構造体を抽象化処理するステップを含みうる。当該抽象化処理するステップは、例えば、下記でいう操作Ｓ又は操作Ｔによる抽象化処理でありうる。
【００２５】
また、上記ステップ（４）でいう提示するステップは、上記第１の近似パターン表現式を画面上に表示するステップを含みうる。
【００２６】
また、本発明は、入力文字列の集合を上記少なくとも１つのパターン表現に変換する方法を提供する。当該方法は、
上記第１の近似パターン表現式を生成するステップを少なくとも１回実行するステップと、
上記生成された第１の近似パターン表現式を当該第１の近似パターン表現式の生成の度に提示するステップと、
上記生成された第１の近似パターン表現式に対応するパターン表現を提示するステップと
を含む。上記第１の近似パターン表現式を提示するステップは、上記第１の近似パターン表現式を画面上に表示するステップを含みうる。上記パターン表現を提示するステップは、当該パターン表現を画面上に表示するステップを含みうる。
【００２７】
また、入力文字列の集合を上記少なくとも１つのパターン表現に変換する方法は、
上記第２の近似パターン表現式を生成するステップを少なくとも１回実行するステップと、
上記生成された第２の近似パターン表現式を当該第２の近似パターン表現式の生成の度に提示するステップと、
上記第２の近似パターン表現式に対応するパターン表現を提示するステップと
をさらに実行することを含む。上記第２の近似パターン表現式を提示するステップは、上記第２の近似パターン表現式を画面上に表示するステップを含みうる。上記パターン表現を提示するステップは、当該パターン表現を画面上に表示するステップを含みうる。
【００２８】
また、本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、上記入力文字列の集合から上記パターン表現に変換する変換パターンを近似パターン表現式として取り出すコンピュータを提供する。当該コンピュータは、
状態を表す複数のノードと、遷移を表す複数のエッジとを有する１つの構造体を準備する第１の生成部であって、各エッジが上記入力文字列の集合中の部分文字列の集合（エッジが持つ文字列の集合）をラベルとして持つ、上記第１の生成部と、
上記１つの構造体中の少なくとも１つの状態を上記１つの構造体から除去し、当該除去された状態に関連付けられたエッジを含む上記１つの構造体が縮退された構造体中の少なくとも２つのエッジをマージして、縮退された第１の構造体を生成する第２の生成部と、
上記縮退された第１の構造体に基づいて第１の近似パターン表現式を生成する表現式生成部と、
上記第１の近似パターン表現式を画面上に表示する提示部と
を備えている。
【００２９】
また、本発明の一つの実施態様において、上記コンピュータは、
上記１つの構造体中の任意の少なくとも２つの状態について、当該少なくとも２つの状態の各当該状態よりも後のｋ遷移ステップ（ｋは１以上の整数である）以内のパスが持つラベル列の集合が同じである場合に、上記同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、又は、上記１つの構造体中の任意の少なくとも２つの状態について、当該少なくとも２つの状態のうちの一つの状態よりも後のｍ遷移ステップ（ｍは１以上の整数である）以内のパスが持つラベル列の集合が当該少なくとも２つの状態のうちの他の一つの状態よりも後のｎ遷移ステップ（ｎは１以上の整数である）以内のパスが持つラベル列の集合を包含する場合に、上記包含されるラベル列の集合のいずれかを持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた状態を有する縮退された第２の構造体を生成する第３の生成部
をさらに備えうる。上記表現式生成部が、上記縮退された第２の構造体に基づいて第２の近似パターン表現式を生成しうる。また、上記提示部が、上記第２の近似パターン表現式を提示しうる。
【００３０】
また、本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換するコンピュータを提供する。当該コンピュータにおいて、
上記第２の生成部が、上記第１の近似パターン表現式を少なくとも１回生成し、
上記提示部は、上記生成された第１の近似パターン表現式を当該第１の近似パターン表現式の生成の度に提示し、
上記提示部は、さらに、上記生成された第１の近似パターン表現式に対応するパターン表現を提示する。
【００３１】
また、入力文字列の集合を上記パターン表現に変換する上記コンピュータにおいて、
上記第３の生成部が、上記第２の近似パターン表現式を少なくとも１回さらに生成し、
上記提示部は、上記生成された第２の近似パターン表現式を当該第２の近似パターン表現式の生成の度にさらに提示し、
上記提示部は、さらに、上記生成された第２の近似パターン表現式に対応するパターン表現をさらに提示しうる。
【００３２】
また、本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、上記入力文字列の集合から上記パターン表現に変換するパターンを近似パターン表現式として取り出すコンピュータ・プログラムを提供する。当該コンピュータ・プログラムは、コンピュータに、本発明に従う、上記入力文字列の集合から上記パターン表現に変換する変換パターンを近似パターン表現式として取り出す上記方法の各ステップを実行させる。
【００３３】
また、本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換するコンピュータ・プログラムを提供する。当該コンピュータ・プログラムは、コンピュータに、本発明に従う、上記入力文字列の集合から上記パターン表現に変換する上記方法の各ステップを実行させる。
【００３４】
また、本発明は、入力文字列の集合から当該入力文字列の集合を文字列で表現する少なくとも１つのパターン表現に変換する過程において、上記入力文字列の集合から上記パターン表現に変換するパターンを近似パターン表現式として取り出すコンピュータ・プログラム製品、及び、上記入力文字列の集合から上記パターン表現に変換するコンピュータ・プログラム製品を提供する。
【００３５】
本発明の機能を実行するためのコンピュータ・プログラムは、フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ＢＤ、ハードディスク装置、ＵＳＢに接続可能なメモリ媒体、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。当該コンピュータ・プログラムは、記録媒体への格納のために、通信回線で接続する他のデータ処理システムからダウンロードしたり、又は他の記録媒体から複製したりすることができる。また、当該コンピュータ・プログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。また、様々な形態で、本発明を実施するコンピュータ・プログラム製品を提供することも勿論可能であることにも留意されたい。コンピュータ・プログラム製品は、例えば、上記コンピュータ・プログラムを記録した記憶媒体、又は、上記コンピュータ・プログラムを伝送する伝送媒体を包含しうる。
【００３６】
本発明の上記概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーション又はサブコンビネーションもまた、本発明となりうることに留意すべきである。
【００３７】
本発明の実施態様において使用されるコンピュータの各ハードウェア構成要素を、複数のマシンと組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００３８】
また、本発明は、ハードウェア、ソフトウェア、又は、ハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアとの組み合わせによる実行において、上記コンピュータ・プログラムがインストールされた装置における実行が典型的な例として挙げられる。かかる場合、該コンピュータ・プログラムが該装置のメモリにロードされて実行されることにより、該コンピュータ・プログラムは、該装置を制御し、本発明にかかる処理を実行させる。該コンピュータ・プログラムは、任意の言語、コード、又は、表記によって表現可能な命令群から構成されうる。そのような命令群は、該装置が特定の機能を直接的に、又は、１．他の言語、コード若しくは表記への変換、２．他の媒体への複製、のいずれか一方若しくは双方が行われた後に、実行することを可能にするものである。
【発明の効果】
【００３９】
本発明の実施態様に従うと、パターン表現への変換による知見を利用した望ましいパターン表現を推論可能であることから、文書解析の品質向上を図ることが可能である。
【００４０】
本発明の実施態様に従うと、必要なパターン表現の推論が自動的に行われ、さらに専門家によるパターン表現の推論の必要性が減少するために、コスト、例えば人件費又は開発費用を削減することが可能である。
【００４１】
本発明の実施態様に従うと、例えば文書成果物を分析するツールに当該発明を実装することによって、ツールの利用のし易さを向上することが可能である。ツールの利用のし易さが向上することによって、当該ツールの普及が期待される。
【００４２】
本発明の実施態様に従うと、上流の文書成果を扱う自動化ツールに本発明を適用することが可能になる。下流工程の自動化ツール群は、下流工程の自動化ツール群に比べてまた発展途上の分野である。本発明を上流の文書成果を扱う自動化ツールに適用することで、上流工程の自動化ツールの普及が期待される。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施態様に従うコンピュータを実現するためのハードウェア構成の一例を示した図である。
【図２】図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従うコンピュータの機能ブロック図の一例を示した図である。
【図３Ａ】本発明の実施態様に従い、入力文字列の集合を近似パターン表現式に変換する処理のためのフローチャートの例を示す。
【図３Ｂ】本発明の実施態様に従い、入力文字列の集合を近似パターン表現式に変換する処理のためのフローチャートの例を示す。
【図４】本発明の実施態様で使用されうる、入力文字列を受理する有限オートマトンの例を示す。
【図５Ａ】図４に示す有限オートマトン中の同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退されたオートマトンを生成する例（操作Ｓ）であり、k-バウンド・バイ−シミュレーション（k-bound bi-simulation）を使用する例である。
【図５Ｂ】図４に示す有限オートマトン中の同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退されたオートマトンを生成する例（操作Ｓ）であり、k-バウンド・ミューチュアル−シミュレーション（k-bound mutual-simulation）を使用する例である。
【図５Ｃ】有限オートマトン中の少なくとも２つの状態（ｓ，ｓ’）について状態ｓが状態ｓ’をシミュレートする場合に、当該状態（ｓ，ｓ’）のいずれかの状態をマージし、当該マージされた状態を有する縮退された有限オートマトンを生成する例（操作Ｓ）を示す。
【図６Ａ】本発明の実施態様に従い、図５Ａに示す有限オートマトン中の少なくとも１つの状態を除去し、当該除去された状態に関連付けられたエッジを含む少なくとも２つのエッジをマージして、縮退された有限オートマトンを生成する例（操作Ｔ）を示す。
【図６Ｂ】本発明の実施態様に従い、有限オートマトン中の少なくとも１つの状態を除去し、当該除去された状態に関連付けられたエッジを含む少なくとも２つのエッジをマージして、縮退された有限オートマトンを生成する例（操作Ｔ）を示す。
【図６Ｃ】本発明の実施態様に従う、エッジのマージ回数を説明するための図である。
【図７Ａ】本発明の実施態様に従い、有限オートマトンから正規表現パターンを獲得する例を示す。
【図７Ｂ】本発明の実施態様に従う、入力文字列を抽象化するために使用される文字クラス・ラティス（lattice）構造を示す。
【図８】本発明の実施態様に従い、有限オートマトンから正規表現を得て、さらに正規表現推論関数を近似パターン表現式として獲得する例を示す。
【図９Ａ】本発明の実施態様に従い、近似パターン表現式ストアから、バリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定する処理のためのフローチャートの例を示す。
【図９Ｂ】本発明の実施態様に従い、図９Ａに従うフローチャートを用いて、バリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定する例を示す。
【図９Ｃ】本発明の実施態様に従い、図９Ａに従うフローチャートを用いて、バリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定する例を示す。
【図１０Ａ】本発明の実施態様である実施例１であり、文字列集合を入力し、当該文字列集合から最初の１つの有限オートマトンを生成する処理を開始するための画面例である。
【図１０Ｂ】本発明の実施態様である実施例１であり、図１０Ａの処理によって生成され、下記図１１Ａに示す有限オートマトンに操作Ｓの抽象化処理を開始するための操作を示す画面例である。
【図１０Ｃ】本発明の実施態様である実施例１であり、図１０Ｂの処理によって生成され、下記図１１Ｂに示す有限オートマトンに操作Ｔ（１回目）の抽象化処理を開始するための操作を示す画面例である。
【図１０Ｄ】本発明の実施態様である実施例１であり、図１０Ｃに示す操作Ｔの抽象化処理から生成された有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
【図１０Ｅ】本発明の実施態様である実施例１であり、図１０Ｄに示すバリエーション・パターンを示す。図１０Ｄに示すバリエーション・パターン中の近似対象部分をフォーカスした際のバリエーション・パターン、及び、現在の近似パターン表現式ストア中にある近似パターン表現式を示す。
【図１０Ｆ】本発明の実施態様である実施例１であり、図１０Ｅに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
【図１０Ｇ】本発明の実施態様である実施例１であり、図１０Ｃに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア中に保存するための処理を示す画面例である。
【図１０Ｈ】本発明の実施態様である実施例１であり、図１０Ｆにおける近似パターン表現式を近似パターン表現式ストアに格納する画面例、及び近似パターン表現式を編集する処理を示す画面例である。
【図１０Ｊ】本発明の実施態様である実施例１であり、図１０Ｃの抽象化処理によって生成され、下記図１１Ｄに示す有限オートマトンに操作Ｔ（２回目）の抽象化処理を開始するための操作を示す画面例である。
【図１０Ｋ】本発明の実施態様である実施例１であり、図１０Ｊに示す操作Ｔの抽象化処理から生成された有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
【図１０Ｌ】本発明の実施態様である実施例１であり、図１０Ｋに示すバリエーション・パターン中の近似対象部分をフォーカスした際のバリエーション・パターン、及び、現在の近似パターン表現式ストア中にある近似パターン表現式を示す。
【図１０Ｍ】本発明の実施態様である実施例１であり、図１０Ｌに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
【図１０Ｎ】本発明の実施態様である実施例１であり、図１０Ｊに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア中に保存するための処理を示す画面例である。
【図１０Ｐ】本発明の実施態様である実施例１であり、図１０Ｊの抽象化処理によって生成され、下記図１１Ｅに示す有限オートマトンに操作Ｔ（３回目）の抽象化処理を開始するための操作を示す画面例である。
【図１０Ｑ】本発明の実施態様である実施例１であり、図１０Ｐに示す操作Ｔの抽象化処理から生成された有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
【図１０Ｒ】本発明の実施態様である実施例１であり、図１０Ｑに示すバリエーション・パターン中の近似対象部分をフォーカスした際のバリエーション・パターン、及び、現在の近似パターン表現式ストア中にある近似パターン表現式を示す。
【図１０Ｓ】本発明の実施態様である実施例１であり、図１０Ｒに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
【図１０Ｔ】本発明の実施態様である実施例１であり、図１０Ｒに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能である近似パターン表現式の例であり、ユーザが所望する近似パターン表現式が追加された近似パターン表現式が選択可能であることを示す画面である。
【図１０Ｕ】本発明の実施態様である実施例１であり、図１０Ｐに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア中に保存するための処理を示す画面例である。
【図１０Ｖ】本発明の実施態様であり、図１０Ａ〜図１０Ｕに示す実施例１の抽象化処理によって作成された近似パターン表現式ストア中に格納された近似パターン表現式を、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理において再利用可能であることを示す画面例である。
【図１１Ａ】本発明の実施態様である実施例１であり、図１０Ａの抽象化処理によって最初に生成される１つの有限オートマトンを示す。
【図１１Ｂ】本発明の実施態様である実施例１であり、図１０Ｂの抽象化処理によって生成される縮退された有限オートマトンを示す。
【図１１Ｃ】本発明の実施態様である実施例１であり、図１０Ｃの抽象化処理によって生成される有限オートマトン（下記図１１Ｄ）の途中経過の有限オートマトンを示す。
【図１１Ｄ】本発明の実施態様である実施例１であり、図１０Ｃの抽象化処理によって生成される有限オートマトンを示す。
【図１１Ｅ】本発明の実施態様である実施例１であり、図１０Ｊの抽象化処理によって生成される縮退された有限オートマトンの例を示す。
【図１１Ｆ】本発明の実施態様である実施例１であり、図１０Ｐの抽象化処理によって生成される縮退された有限オートマトンを示す。
【図１２Ａ】本発明の実施態様に従い、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように推論するための処理において、ユーザと対話的に正規表現を推論するためのインタラクション機能を示す。
【図１２Ｂ】本発明の実施態様に従い、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように推論するための処理において、ユーザと対話的に正規表現を推論するためのインタラクション機能を示す。
【図１３】本発明の実施態様である実施例１を例として、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように対話的に処理した場合の各正規表現パターンを示す。
【図１４】本発明の実施態様に従い、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように対話的に処理した場合の各正規表現パターンを示す。
【図１５Ａ】本発明の実施態様である実施例２であり、文字列集合を入力し、当該文字列集合から最初の１つの有限オートマトンを生成する処理を開始するための画面例である。
【図１５Ｂ】本発明の実施態様である実施例２であり、図１５Ａの処理によって生成され、下記図１６Ａに示す有限オートマトンに操作Ｓの抽象化処理を開始するための操作を示す画面例である。
【図１５Ｃ】本発明の実施態様である実施例２であり、図１５Ｂの処理によって生成され、下記図１６Ｂに示す有限オートマトンに操作Ｔ（１回目）の抽象化処理を開始するための操作を示す画面例である。
【図１５Ｄ】本発明の実施態様である実施例２であり、図１５Ｃに示す操作Ｔの抽象化処理から生成された有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
【図１５Ｅ】本発明の実施態様である実施例２であり、図１５Ｄに示すバリエーション・パターンを示す。図１５Ｄに示すバリエーション・パターン中の近似対象部分をフォーカスした際のバリエーション・パターン、及び、現在の近似パターン表現式ストア中にある近似パターン表現式を示す。
【図１５Ｆ】本発明の実施態様である実施例２であり、図１５Ｅに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
【図１５Ｇ】本発明の実施態様である実施例２であり、図１５Ｃに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア中に保存するための処理を示す画面例である。
【図１５Ｈ】本発明の実施態様である実施例２であり、図１５Ｆにおける近似パターン表現式を近似パターン表現式ストアに格納する画面例、及び近似パターン表現式を編集する処理を示す画面例である。
【図１５Ｊ】本発明の実施態様である実施例２であり、図１５Ｃの抽象化処理によって生成され、下記図１６Ｄに示す有限オートマトンに操作Ｔ（２回目）の抽象化処理を開始するための操作を示す画面例である。
【図１５Ｋ】本発明の実施態様である実施例２であり、図１５Ｊに示す操作Ｔの抽象化処理から生成された有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
【図１５Ｌ】本発明の実施態様である実施例２であり、図１５Ｋに示すバリエーション・パターン中の近似対象部分をフォーカスした際のバリエーション・パターン、及び、現在の近似パターン表現式ストア中にある近似パターン表現式を示す。
【図１５Ｍ】本発明の実施態様である実施例２であり、図１５Ｌに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
【図１５Ｎ】本発明の実施態様である実施例２であり、図１５Ｊに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア中に保存するための処理を示す画面例である。
【図１５Ｐ】本発明の実施態様である実施例２であり、図１５Ｊの抽象化処理によって生成され、下記図１６Ｅに示す有限オートマトンに操作Ｔ（３回目）の抽象化処理を開始するための操作を示す画面例である。
【図１５Ｑ】本発明の実施態様である実施例２であり、図１５Ｐに示す操作Ｔの抽象化処理から生成された有限オートマトンから正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
【図１５Ｒ】本発明の実施態様である実施例２であり、図１５Ｑに示すバリエーション・パターン中の近似対象部分をフォーカスした際のバリエーション・パターン、及び、現在の近似パターン表現式ストア中にある近似パターン表現式を示す。
【図１５Ｓ】本発明の実施態様である実施例２であり、図１５Ｒに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
【図１５Ｔ】本発明の実施態様である実施例２であり、図１５Ｒに示すバリエーション・パターン中の近似対象部分をフォーカスした際に適用可能である近似パターン表現式の例であり、ユーザが所望する近似パターン表現式が追加された近似パターン表現式が選択可能であることを示す画面である。
【図１５Ｕ】本発明の実施態様である実施例２であり、図１５Ｐに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア中に保存するための処理を示す画面例である。
【図１５Ｖ】本発明の実施態様であり、図１５Ａ〜図１５Ｕに示す実施例２の抽象化処理によって作成された近似パターン表現式ストア中に格納された近似パターン表現式を、実施例２以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理において再利用可能であることを示す画面例である。
【図１６Ａ】本発明の実施態様である実施例２であり、図１５Ａの抽象化処理によって最初に生成される１つの有限オートマトンを示す。
【図１６Ｂ】本発明の実施態様である実施例２であり、図１５Ｂの抽象化処理によって生成される縮退された有限オートマトンを示す。
【図１６Ｃ】本発明の実施態様である実施例２であり、図１５Ｃの抽象化処理によって生成される有限オートマトン（下記図１６Ｄ）の途中経過の有限オートマトンを示す。
【図１６Ｄ】本発明の実施態様である実施例２であり、図１５Ｃの抽象化処理によって生成される有限オートマトンを示す。
【図１６Ｅ】本発明の実施態様である実施例２であり、図１５Ｊの抽象化処理によって生成される縮退された有限オートマトンの例を示す。
【図１６Ｆ】本発明の実施態様である実施例２であり、図１５Ｐの抽象化処理によって生成される縮退された有限オートマトンを示す。
【図１７】本発明の実施態様である実施例２を例として、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように対話的に処理した場合の各正規表現パターンを示す。
【発明を実施するための形態】
【００４４】
以下に、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施態様は特許請求の範囲に係る発明を限定するものでなく、また実施態様の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。また、本発明は多くの異なる態様で実施することが可能であり、以下の実施態様において、種々の変更又は改良を加えることが可能であることが当業者に明らかである。
【００４５】
以下において、特に断らない限り、発明を実施するための形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００４６】
図１は、本発明の実施態様に従うコンピュータを実現するためのハードウェア構成の一例を示した図である。
【００４７】
コンピュータ（１０１）は、ＣＰＵ（１０２）とメイン・メモリ（１０３）とを備えており、これらはバス（１０４）に接続されている。ＣＰＵ（１０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＣｏｒｅ  ｉ（商標）シリーズ、Ｃｏｒｅ  ２（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ社のＯｐｔｅｒｏｎ（商標）シリーズ、Ｐｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ、Ｓｅｍｐｒｏｎ（商標）又はＡシリーズが使用されうる。バス（１０４）には、ディスプレイ・コントローラ（１０５）を介して、ディスプレイ（１０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。ディスプレイ（１０６）は、コンピュータの管理のために、通信回線を介してネットワークに接続されたコンピュータについての情報と、そのコンピュータ上で動作中のソフトウェアについての情報を、適当なグラフィック・インタフェースで表示するために使用される。バス（１０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ディスク（１０８）、例えばシリコン・ディスク又はハードディスクが接続されうる。また、バス（１０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、任意的に、ドライブ（１０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブが接続されうる。バス（１０４）にはさらに、任意的に、キーボード・マウスコントローラ（１１０）又はＵＳＢバス（図示せず）を介して、キーボード（１１１）及びマウス（１１２）が接続されうる。
【００４８】
ディスク（１０８）には、オペレーティング・システム、その他のプログラム、及びデータが、メイン・メモリ（１０３）にロード可能なように記憶されている。また、ディスク（１０８）には、文字列の入力乃至は編集を可能にするソフトウェア、文字変換処理ソフトウェアであるフロント・エンド・プロセッサ（ＦＥＰ）がメイン・メモリ（１０３）にロード可能なように記憶されている。オペレーティング・システムは、例えば、ＬＩＮＵＸ（登録商標）ディストリビュータが提供するＬＩＮＵＸ（登録商標）、マイクロソフト・コーポレーションが提供するＷｉｎｄｏｗｓ（登録商標）オペレーティング・システム、アップル・コンピュータ・インコーポレイテッドが提供するＭａｃＯＳ（登録商標）若しくはｉＯＳ（登録商標）、Ｘ  Ｗｉｎｄｏｗ  Ｓｙｓｔｅｍを備えるＵＮＩＸ（登録商標）系システム（たとえば、インターナショナル・ビジネス・マシーンズ・コーポレーション（登録商標）が提供するＡＩＸ（登録商標））でありうる。
【００４９】
ドライブ（１０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムをディスク（１０８）にインストールするために使用されうる。
【００５０】
通信インタフェース（１１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１１４）は、通信コントローラ（１１３）を介してバス（１０４）に接続され、コンピュータ（１０１）を通信回線（１１５）に物理的に接続する役割を担い、コンピュータ（１０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は、有線ＬＡＮ環境に基づくもの、又は、無線ＬＡＮ環境、例えば、ＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどのＷｉ−Ｆｉ規格に基づくものであってもよい。
【００５１】
以上から、本発明の実施態様において使用されるコンピュータは、特定のオペレーティング・システム環境に限定されるものではないことを理解することができるであろう。
【００５２】
図２は、図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従うコンピュータの機能ブロック図の一例を示した図である。
【００５３】
コンピュータ（２０１）は、図１に従うハードウェア構成を有しうる。コンピュータ（２０１）は、構造体生成部（２０２）、近似パターン表現式生成部（以下、「表現式生成部」ともいう）（２０３）、及びパターン表現推論関数生成部（以下、「推論関数生成部」ともいう）（２０４）を備えうる。また、コンピュータ（２０１）は、提示部（２０５）又は表示部（２０６）を内蔵しているか、又は、コンピュータ（２０１）外にある表示部（２０６）に有線的に又は無線的に接続されうる。また、コンピュータ（２０１）は記憶装置（２１１）を内蔵しているか、又は、コンピュータ（２０１）外にある記憶装置（２１１）に有線的に又は無線的に接続されうる。
【００５４】
構造体生成部（２０２）は、第１の生成部（２０２−１）、第２の生成部（２０２−２）、及び第３の生成部（２０２−３）を備えうる。本発明の実施態様において、構造体中の各エッジが上記入力文字列の集合中の部分文字列の集合（エッジが持つ文字列の集合）をラベルとして持つ。構造体は、例えば、有限オートマトン（finite automaton）でありうる。当該有限オートマトンの例は、例えば、下記図４を参照されたい。
【００５５】
構造体生成部（２０２）は、状態を表す複数のノードと、遷移を表す複数のエッジとを有する１つの構造体を準備しうる。各各エッジは、上記入力文字列の集合中の部分文字列の集合（エッジが持つ文字列の集合）をラベルとして持つ。
【００５６】
第１の生成部（２０２−１）は、入力文字列の集合から１つの構造体（以下、「初期構造体」ともいう）を生成する。第１の生成部（２０２−１）は、入力文字列の集合を記憶装置（２１１）から読み取るか、又は、ユーザ（２２１）がキーボード又は音声認識装置などの入力デバイスを介して入力した文字列の集合を受け取りうる（例えば、下記図１０Ａを参照）。
【００５７】
第２の生成部（２０２−２）は、（１）上記初期構造体又は当該初期構造体が縮退された構造体中の少なくとも１つの状態の除去によりマージされることになるエッジに関連付けられた当該初期構造体又は当該初期構造体が縮退された構造体中の部分構造体の変化量を評価する状態除去指標に基づいて、（２）当該部分構造体と上記初期構造体中の他の部分構造体との若しくは上記初期構造体又は当該初期構造体が縮退された構造体との包含関係に基づいて、又は（３）上記（１）及び（２）の組み合わせに基づいて、上記初期構造体又は当該初期構造体が縮退された構造体中の少なくとも１つの状態を上記初期構造体又は当該初期構造体が縮退された構造体から除去し、当該除去された状態に関連付けられたエッジを含む上記初期構造体又は当該初期構造体が縮退された構造体中の少なくとも２つのエッジをマージして、縮退された第１の構造体を生成しうる。
【００５８】
第３の生成部（２０２−３）は、上記初期構造体又は当該構造体が縮退された構造体中の任意の少なくとも２つの状態について、当該少なくとも２つの状態の各当該状態よりも後のｋ遷移ステップ（ｋは１以上の整数である）以内のパスが持つラベル列の集合が同じである場合に、上記同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた状態を有する縮退された第２の構造体を生成しうる（下記図５Ａ及び図５Ｂを参照）。
【００５９】
また、第３の生成部（２０２−３）は、上記初期構造体又は当該初期構造体が縮退された構造体中の任意の少なくとも２つの状態について、当該少なくとも２つの状態のうちの一つの状態よりも後のｍ遷移ステップ（ｍは１以上の整数である）以内のパスが持つラベル列の集合が当該少なくとも２つの状態のうちの他の一つの状態よりも後のｎ遷移ステップ（ｎは１以上の整数である）以内のパスが持つラベル列の集合を包含する場合に、当該包含されるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた状態を有する縮退された第２の構造体を生成しうる（下記図５Ｃを参照）。
【００６０】
表現式生成部（２０３）は、第２の生成部（２０２−２）において生成された縮退された第１の構造体に基づいて第１の近似パターン表現式を生成しうる。
【００６１】
また、表現式生成部（２０３）は、第３の生成部（２０２−３）において生成された縮退された第２の構造体に基づいて第２の近似パターン表現式を生成しうる。
【００６２】
推論関数生成部（２０４）は、縮退された第１の構造体（２１３）から、パターン表現、例えば正規表現の第１の推論関数を獲得しうる。
【００６３】
また、推論関数生成部（２０４）は、縮退された第２の構造体（２１３）から、パターン表現、例えば正規表現の第２の推論関数を獲得しうる。
【００６４】
提示部（２０５）は、近似パターン表現式、例えば例えば第１の近似パターン表現式又は第２の近似パターン表現式を、例えば当該コンピュータ（２０１）上で実行されているオペレーティング・システム、アプリケーション・ソフトウェアに提供しうる。また、提示部（２０５）は、表示部（２０６）の機能を有しうる。表示部（２０６）は、例えば表示装置（１０６）でありうる。
【００６５】
表示部（２０６）は、第１の生成部（２０２−１）において生成された構造体、第２の生成部（２０２−２）において生成された縮退された第１の構造体、及び第３の生成部（２０２−３）において生成された縮退された第２の構造体を画面上に表示しうる。
【００６６】
また、表示部（２０６）は、パターン表現式、例えば上記第１の近似パターン表現式又は上記第２の近似パターン表現式を画面上に表示しうる。
【００６７】
また、表示部（２０６）は、入力文字列の集合（２１２）、及び／又は、パターン表現推論関数（２１５）を表示しうる。パターン表現推論関数（２１５）は、例えば正規表現推論関数を包含する。以下、パターン表現推論関数（２１５）を正規表現推論関数（２１５）ともいう。
【００６８】
記憶装置（２１１）は、入力文字列の集合（以下、「文字列集合」ともいう）（２１２）、構造体又は縮退された構造体（２１３）、近似パターン表現式（２１４）、及び正規表現推論関数（２１５）を例えばファイルの形式で格納しうる。近似パターン表現式（２１４）を格納している記憶部（２０６）を、近似パターン表現式ストアをもいう。また、正規表現推論関数（２１５）を格納している記憶部（２０６）を、正規表現推論関数ストアをもいう。
【００６９】
文字列集合（２１２）は特定の種類の記述集合であり、具体的には特定の法則に従う大量の文字列の集合でありうる。文字列集合（２１２）は、例えば、文書中からの抽出候補列、フォルダ内のファイル名セット、プログラム名のセット、仕様書名のセット、及びパラメータに対する値の設定方法の記述子セットでありうるが、これらに限定されるものではない。
【００７０】
上記１つの構造体又は上記縮退された構造体（２１３）は、それぞれ、例えば有限オートマトン又は当該有限オートマトンが縮退された有限オートマトンでありうる。構造体は、第１の生成部（２０２−１）において生成された１つの構造体でありうる。縮退された構造体（２１３）は、第２の生成部（２０２−２）において生成された縮退された第１の構造体、及び第３の生成部（２０２−３）において生成された縮退された第２の構造体でありうる。
【００７１】
近似パターン表現式（２１４）は、パターン表現の記述の一部に０個以上の推論関数（または正規表現推論関数）を表す記号を含むパターンでありうる。パターン表現とは、文字列の集合を一つの文字列または一つの形式で表現する方法であり、その一つの方法が例えば正規表現である。以下、正規表現という語を使用するが、パターン表現が正規表現に限定されるものではないことを理解されたい。また、近似パターン表現式は、具体的には、正規表現の文法に、<α>, r1//r2を追加して拡張した文法である（αは文字列の集合から正規表現への関数であり、r1及びr2は正規表現である）。近似パターン表現式（２１４）は、上記第１の近似パターン表現式及び上記第２の近似パターン表現式でありうる。
【００７２】
正規表現推論関数（２１５）は、入力文字列の集合からの正規表現の推論パターンを表す。正規表現推論関数（２１５）は、入力文字列の集合からの正規表現の段階的な推論過程において、正規表現推論関数として獲得されたものである。正規表現推論関数（２１５）は、正規表現の第１の推論関数及び正規表現の第２の推論関数でありうる。
【００７３】
図３Ａ及び図３Ｂは、本発明の実施態様に従い、入力文字列の集合を近似パターン表現式に変換する処理のためのフローチャートの例を示す。
【００７４】
ステップ３０１では、コンピュータ（２０１）は、入力文字列の集合を近似パターン表現式に変換する処理を開始する。
【００７５】
ステップ３０２では、第１の生成部（２０２−１）は、記憶装置（２１１）から文字列集合（２１２）を含むファイルを読み出すか、又は、ユーザ（２２１）が例えばキーボード（１１１）を介して入力した文字列の集合を受け取り、メモリ（１０３）内に記憶する。ステップ３０２の処理を、以下において「ステップ１の処理」ともいう。
【００７６】
ステップ３０３では、第１の生成部（２０２−１）は、ステップ３０２で読み出した又は受け取った入力文字列の集合から１つの構造体、例えば有限オートマトン、をメモリ（１０３）内に生成する（下記図４を参照）。ステップ３０３の処理を、以下において「ステップ２の処理」ともいう。コンピュータ（２０１）は、ステップ３０３の処理が終わると、次にステップ３０４又はステップ３０６へ処理を進める。ステップ３０４又はステップ３０６のいずれのステップに進むかは、例えばユーザによりインタラクティブに指定されうる。第１の生成部（２０２−１）は、生成した１つの構造体を記憶装置（２１１）中に格納しうる（図２の構造体（２１３）を参照）。
【００７７】
ステップ３０４では、第３の生成部（２０２−３）は、ステップ３０３からの構造体、下記において述べるステップ３０６からの縮退された構造体、又はステップ３０３からの構造体をその他の慣用的な若しくは当業者に知られている縮退技法により処理（図示せず）して縮退された構造体（以下、まとめて「構造体Ａ」ともいう）中の共通パスの状態をマージして、縮退された構造体（特許請求の範囲でいう「第２の構造体」）を生成する（下記図５Ａ〜図５Ｃを参照）。詳細には、第３の生成部（２０２−３）は、上記構造体Ａ中の任意の少なくとも２つの状態について、当該少なくとも２つの状態の各当該状態よりも後のｋ遷移ステップ（ｋは１以上の整数である）以内のパスが持つラベル列の集合が同じである場合に、上記同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた状態を有する縮退された構造体（縮退された第２の構造体）を生成する。または、第３の生成部（２０２−３）は、上記構造体Ａ中の任意の少なくとも２つの状態について、当該少なくとも２つの状態のうちの一つの状態よりも後のｍ遷移ステップ（ｍは１以上の整数である）以内のパスが持つラベル列の集合が当該少なくとも２つの状態のうちの他の一つの状態よりも後のｎ遷移ステップ（ｎは１以上の整数である）以内のパスが持つラベル列の集合を包含する場合に、当該包含されるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた状態を有する縮退された構造体（第２の構造体）を生成する。ステップ３０４の処理を、以下において「ステップ３の処理」又は「操作Ｓ」ともいう。第３の生成部（２０２−３）は、ユーザからの操作Ｓの抽象化処理の指定によって、又は予め定められた自動化工程に従って、操作Ｓの抽象化処理を開始しうる。第３の生成部（２０２−３）は、生成した縮退された構造体をメモリ（１０３）又は記憶装置（２１１）に格納しうる（図２の構造体（２１３）を参照）。
【００７８】
ステップ３０４が終了することに応じて、コンピュータ（２０１）は、処理を図３Ｂに示す処理Ｑ（ステップ３０５）に進める。以下、図３Ｂに記載のフローチャートに従い、処理Ｑについて説明する。
【００７９】
ステップ３１１では、コンピュータ（２０１）は処理Ｑを開始する。
【００８０】
ステップ３１２では、表現式生成部（２０３）は、操作Ｓによって生成された縮退された構造体中の遷移上の部分文字列集合に近似パターン表現式を適用して正規表現の推論を行う。近似パターン表現式は、正規表現の記述の一部に０個以上の推論関数を表す記号を含むパターンでありうる。ステップ３１２の処理を、以下において「ステップ５の処理」ともいう。近似パターン表現式を適用して正規表現の推論を行う方法については、下記図７Ａの説明において詳細に述べる。
【００８１】
ステップ３１３では、表示部（２０６）は、ステップ３１２で推論された推論結果である正規表現候補を提示しうる。当該提示は、例えば表示部（２０６）を通じて画面上に表示され、又は、コンピュータ（２０１）上で実行されているオペレーティング・システム、アプリケーション・ソフトウェアに提供することによって行われうる。
【００８２】
ステップ３１９では、表現式生成部（２０３）は、ステップ３１２で推論された推論結果である近似パターン表現式を再利用のために記憶装置（２１１）に格納する。
【００８３】
ステップ３１４では、表現式生成部（２０３）は、操作Ｓによって生成された縮退された構造体と、デフォルトの近似パターン表現式  <prim>  又はユーザが選択若しくは入力した近似パターン表現式とから正規表現推論関数を近似パターン表現式として獲得する。ステップ３１４の処理を、以下において「ステップ６の処理」ともいう。但し、デフォルトの近似パターン表現式  <prim>  を適用しない場合は、コンピュータ（２０１）は、ステップ３１４の前に下記ステップ３１７を実施しうる。
【００８４】
ステップ３１５では、コンピュータ（２０１）は処理Ｑを終了するかどうかを判断する。処理Ｑを終了することに応じて、コンピュータ（２０１）は処理を終了ステップ３０８に進める。処理Ｑを終了して操作Ｓ（ステップ３０４）を縮退された有限オートマトンにさらに適用するということに応じて、コンピュータ（２０１）は処理をステップ３０４に戻す。処理Ｑを終了して操作Ｔ（ステップ３０６）により縮退された有限オートマトンにさらに適用するということに応じて、コンピュータ（２０１）は処理をステップ３０６に進める。正規表現推論関数を変更するという指示（変更指示）に応じて、コンピュータ（２０１）は処理をステップ３１６に進める。
【００８５】
ステップ３１６では、表示部（２０６）は、ステップ３０４で生成された構造体からのバリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を表示する。ステップ３１６の処理を、以下において「ステップ７の処理」ともいう。
【００８６】
ステップ３１７では、コンピュータ（２０１）は、ステップ３１７で画面上に表された上記適用可能な近似パターン表現式をユーザに選択することを許し、又は、ユーザが近似パターン表現式を入力することを許す。
【００８７】
ステップ３１８では、表現式生成部（２０３）は、上記バリエーション・パターン中の近似対象部分に、ステップ３１７で選択された又は入力された近似パターン表現式を適用して正規表現候補を獲得する。近似パターン表現式は、正規表現の記述の一部に０個以上の推論関数を表す記号を含むパターンでありうる。ステップ３１８の処理が終了することに応じて、コンピュータ（２０１）は、処理をステップ３１３に戻す。表示部（２０６）は、ステップ３１８で獲得された正規表現候補を提示しうる。当該提示は、例えば表示部（２０６）を通じて画面上に表示され、又は、コンピュータ（２０１）上で実行されているオペレーティング・システム、アプリケーション・ソフトウェアに提供することによって行われうる。
【００８８】
ステップ３０５では、コンピュータはステップ３０５の処理Ｑの処理結果に応じて、処理をステップ３０４（操作Ｓ）、ステップ３０６（操作Ｔ）、又は終了ステップ３０８に進める。
【００８９】
ステップ３０６では、第２の生成部（２０２−２）は、ステップ３０３からの１つの構造体、ステップ３０４からの縮退された構造体、又はステップ３０３からの構造体をその他の慣用的な若しくは当業者に知られている縮退技法により処理（図示せず）して縮退された構造体（以下、まとめて「構造体Ｂ」ともいう）中の状態を除去し、エッジをマージして、縮退された構造体（特許請求の範囲でいう「第１の構造体」）を生成する（下記図６Ａ〜図６Ｃを参照）。詳細には、第２の生成部（２０２−２）は、（１）上記構造体Ｂ中の少なくとも１つの状態の除去によりマージされることになるエッジに関連付けられた上記構造体Ｂ中の部分構造体の変化量を評価する状態除去指標に基づいて、（２）当該部分構造体と他の部分構造体との若しくは上記構造体Ｂとの包含関係に基づいて、又は（３）上記（１）に記載の状態除去指標及び上記（２）に記載の包含関係との組み合わせに基づいて、上記構造体Ｂ中の少なくとも１つの状態を上記構造体Ｂから除去し、当該除去された状態に関連付けられたエッジを含む上記構造体Ｂ中の少なくとも２つのエッジをマージして、縮退された構造体（特許請求の範囲でいう「縮退された第１の構造体」）を生成する。ステップ３０６の処理を、以下において「ステップ４の処理」又は「操作Ｔ」ともいう。第２の生成部（２０２−２）は、ユーザからの操作Ｔの抽象化処理の指定によって、又は予め定められた自動化工程に従って、操作Ｔの抽象化処理を開始しうる。第２の生成部（２０２−２）は、生成した縮退された構造体をメモリ（１０３）又は記憶装置（２１１）に格納しうる（図２の構造体（２１３）を参照）。
【００９０】
ステップ３０６が終了することに応じて、コンピュータは、処理を図３Ｂに示す処理Ｑ（ステップ３０７）に進める。
【００９１】
ステップ３１１では、コンピュータ（２０１）は処理Ｑを開始する。
【００９２】
ステップ３１２では、表現式生成部（２０３）は、操作Ｔによって生成された縮退された構造体構造体中の遷移上の部分文字列集合に近似パターン表現式を適用して正規表現の推論を行う。
【００９３】
ステップ３１３及び３１９は、上記に述べた通りである。
【００９４】
ステップ３１４では、推論関数生成部（２０４）は、操作Ｔによって生成された縮退された構造体と、デフォルトの近似パターン表現式  <prim>  又はユーザが選択若しくは入力した近似パターン表現式とから正規表現推論関数を近似パターン表現式として獲得する。正規表現推論関数を近似パターン表現式として獲得する手法については、下記図９Ａ及び図９Ｂの説明において詳細に述べる。
【００９５】
ステップ３１５、３１７及び３１８は、上記に述べた通りである。
【００９６】
ステップ３０７では、コンピュータは処理Ｑの処理結果に応じて、処理をステップ３０４（操作Ｓ）、ステップ３０６（操作Ｔ）、又は終了ステップ３０８に進める。
【００９７】
ステップ３０８では、コンピュータ（２０１）は、入力文字列の集合を近似パターン表現式に変換する処理を終了する。
【００９８】
図４は、本発明の実施態様で使用されうる、入力文字列を受理する有限オートマトンの例を示す。
第１の生成部（２０２−１）は、ステップ３０２で読み取った又は受け取った入力文字列の集合（４１１）を入力とし、当該入力された入力文字列の集合から１つの有限オートマトン（４０１）を出力として生成し、メモリ（１０３）内に格納する。図４では、入力文字列の集合（４１１）は、フォルダ中のファイル名の例である。有限オートマトン（４０１）は、各エッジが入力文字列の集合（４１１）中の部分文字列の集合（エッジが持つ文字列の集合）をラベルとして持つ。有限オートマトン（４０１）は、プレフィックス・ツリー・アクセプター（prefix tree acceptor）でありうる。有限オートマトンの生成方法は、既存の任意の手法を使用してプレフィックス木（prefix tree）を生成することによって行われうる。
【００９９】
有限オートマトン（４０１）の各状態中の［数字１，数字２］は下記を示す：数字１は、入力文字列の集合（４１１）のうち該状態に到達している入力文字列集合の数である。数字２は、入力文字列の集合（４１１）のうち該状態に受理されている入力文字列の数である。
【０１００】
有限オートマトン（４０１）の各状態中のＮで始まる数字は、当該有限オートマトン（４０１）中の状態を番号付けしたものであり、状態を特定するために有用なものであるが、なくてもよい。
【０１０１】
有限オートマトン（４０１）の各エッジには、入力文字列の集合（４１１）中の部分文字列の集合（エッジが持つ文字列の集合）がラベルとして付されている。すなわち、エッジは、文字列の集合を持つ。
【０１０２】
図５Ａ〜図５Ｃは、本発明の実施態様に従い、有限オートマトン中の同じであるラベル列の集合又は包含されるラベル列の集合のいずれかを持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退されたオートマトンを生成する例（操作Ｓ）を示す。
【０１０３】
操作Ｓでは、状態の段階的な抽象化のために、k-バウンド（バイ−）シミュレーション（k-bound (bi-)simulation）を用いる。以下にk-bound (bi-)simulationについて説明する。
操作Ｓは、有限オートマトン中の状態をマージすることで状態を抽象化する手続であり、有限オートマトン中の状態をある同値関係（＝上記k）の下でマージする操作である。
【０１０４】
操作Ｓでは、入力文字列の集合（すなわち、テキスト文字列である）のパターン化という特徴を考慮して実験をした結果、有用な同値関係（＝上記ｋ）として、オートマトンの状態間の以下に示す特定の関係１又は関係２のいずれかを利用しうる。
関係１：有限オートマトンの抽象化で用いられる関係
・バイ・シミュレーション（≡）とは、有限オートマトン中、今後、同じ遷移を行うことができる状態を同一とみなす関係である。有限オートマトンの全状態がUであるとき、U-バウンド・バイ・シミュレーションと等価である。
関係２：バイ・シミュレーションを改良して作り出した関係
・ミューチュアル−シミュレーション（mutual-simulation）（⇔）とは、有限オートマトン中、今後、どちらか一方が他方の遷移を模倣することができる状態を同一とみなす関係である。有限オートマトンの全状態数がUであるとき、U-バウンド・ミューチュアル−シミュレーションと等価である。
・k-バウンド・バイ・シミュレーション (≡k)とは、ｋステップの遷移で到達可能な範囲において、バイシミラー（bisimilar）な状態を同一と見なす関係である。k-バウンド・バイ・シミュレーションは、下記式で表されうる。
s1≡s2  iff s1→s2 and s2→s1
k-バウンド・バイ・シミュレーションの具体例は、下記の通りである：s1 sims2  を次で定義される状態間の関係とする。「もし  s1 -L->s11  を満たす s11が存在するなら、s2 -L-> s21 となる s21が存在し、s11 bsim s21 を満たす。」。バイ・シミュレーションという関係は、s1sim s2  且つ  s2 sim s1 で定義されうる。例えば、下記で述べる14-boundというのは、１４の長さのパスの範囲内で上記関係が満たされれば良いということである。
・k-バウンド・ミューチュアル−シミュレーション(⇔k)とは、ｋステップの遷移で到達可能な範囲において、ミューチュアル・バイシミラー（mutual-bisimilar）な状態を同一と見なす関係である。k-バウンド・ミューチュアル−シミュレーションは、直感的には、一方の状態が他方の状態を模倣できるという関係にあるときに、それら状態を同一とみなす関係である。k-バウンド・ミューチュアル−シミュレーションは、下記式で表されうる。
s1 n s2  iff   ∀L. δ(s2, L) =s’2 ⇒ ∃s’1. (δ(s1,L) = s’1  and  s’1 n s’2 )
or ∀L. δ(s1, L) = s’1 ⇒ ∃s’2. (δ(s2,L) = s’2  and  s’1 n s’2 )
但し、k-バウンド・バイ・シミュレーション及びk-バウンド・ミューチュアル−シミュレーションにおいて、以下の関係を利用している。
・  Simulation (→) 
s1→s2  iff ∀L. δ(s2,L) = s’2 ⇒ ∃s’1.(δ(s1,L) = s’1 and s’1 → s’2)
・  K-bound simulation (→k) 
s1→ks2  iff  ∀L. δ(s2,L) = s’2 ⇒ ∃s’1.(  δ(s1,L) =s’1 and s’1 →(k-1)s’2  )   if k>0
s1→0s2 hold for any s1 and s2
・  s1 ---> s2    ：  状態s1から状態s2にパスが在る。
・  δ(s, L)=s’  ：  状態sからラベルLを持つエッジのラベルがあり、その先の状態がs’である。
【０１０５】
操作Ｓの手順は、下記の通りであり、kを全状態数から一つずつ減少させながら、以下のステップ１〜３を段階的に繰り返す。操作Ｓの手順は、状態間の任意の同値関係＝について可能であるが、本発明の実施態様において、上記同値関係（＝）として、上記(≡k)又は上記(⇔k)のいずれかを用いる。
ステップ１：第３の生成部（２０２−３）は、有限オートマトンsaの状態の集合STについて、同値関係=kについての同値類  ST/=  を求める。
ステップ２：第３の生成部（２０２−３）は、[s]∈ ST/= を状態とし、δ([s],T) = δ(s,T)を遷移関係とする新しい有限オートマトン（操作Ｓにより縮退された有限オートマトン）を作成する。
ステップ３：第３の生成部（２０２−３）は、縮退されたオートマトン saを返す。本手順において、有限オートマトンは段階的に必ず縮退（抽象化）される。すなわち、有限オートマトン中において受理トークン列が増加する。
【０１０６】
図５Ａは、図４に示す有限オートマトン（４０１）中の同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退されたオートマトンを生成する例（操作Ｓ）を示す。
【０１０７】
図５Ａはbound bi-simulationを使用して、有限オートマトンを抽象化する例である。「有限オートマトン中の同じラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合」を共通パスともいう。ラベル列は、例えば、S1-L1-> S2 -L2 → S3  という２ステップのパスが持つのは、L1L2というラベル列である。
【０１０８】
有限オートマトン（４０１）はその最長パス長（すなわち、エッジ数）が１３である。第３の生成部（２０２−３）は、最長パス長１３を考慮して、長さ１３の範囲で同じ挙動をする状態の集合を13-bound bi-simulation関係（すなわち、k=13のbound bi-simulation）を利用して、マージする。すなわち、第３の生成部（２０２−３）は、同じ挙動をする状態が複数あれば、それら同じ挙動をする状態全てを一つの状態にマージする。第３の生成部（２０２−３）は、有限オートマトン（４０１）中にあり、Ｎ８及びＮ１３のラベルを持つ２つの状態よりも後の５遷移ステップのエッジが持つ文字列の集合が同じであるので、当該同じである文字列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合、すなわち点線四角線で囲まれている部分（４０２）をマージする。その結果、縮退された有限オートマトン（５０１）が生成される。有限オートマトン（５０１）中の符号（５０２）で示されている部分に見られるように、有限オートマトン（４０１）中の上記部分（４０２）がマージされている。
【０１０９】
図５Ａに示すマージの例は、上記したとおり、k-bound bi-simulationの関係にある状態をマージすることである。k-bound bi-simulationは、既存手法であるｋ−ｔａｉｌ法とほぼ同様である（非特許文献１を参照）。
【０１１０】
有限オートマトンの最長パスを段階的に抽象化（縮退）させることによって、抽象化（縮退）された有限オートマトンが段階的に得られうる。抽象化されるということは、状態がマージされること又は遷移がマージされることである。得られる有限オートマトンは、段階が進むにつれてより抽象化されているといえる。
【０１１１】
図５Ｂは、図４に示す有限オートマトン（４０１）中の同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退されたオートマトンを生成する例（操作Ｓ）を示す。また、図５Ｂはbound mutual-simulationを使用して、有限オートマトンを抽象化する例である。
【０１１２】
図５Ｂは、図５Ａに示す有限オートマトン（５０１）中の同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合をマージし、当該マージされた遷移及び状態を有する縮退されたオートマトンを生成する例（操作Ｓ  ２回目）を示す。
【０１１３】
図５Ｂ左側に示す有限オートマトン（５０１）は、図５Ａ右側に示す有限オートマトン（５０１）と同じである。有限オートマトン（５０１）は、その最長パス長が１３である。第３の生成部（２０２−３）は、最長パス長１３を考慮して、長さ１３の範囲で同じ挙動をする状態の集合を13-bound mutual-simulation関係（すなわち、k=13のbound mutual-simulation）を利用して、マージする。第３の生成部（２０２−３）は、有限オートマトン（５０１）中にあり、Ｎ９及びＮ１１のラベルを持つ２つの状態よりも後の１遷移ステップのエッジが持つ文字列の集合が同じであるので、当該同じであるラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合、すなわち点線四角線で囲まれている部分（５０２）をマージする。また、第３の生成部（２０２−３）は、有限オートマトン（５０１）中にあり、Ｎ１０及びＮ１２のラベルを持つ２つの状態よりも後の１遷移ステップのエッジが持つ文字列の集合がbound mutual-simulation関係を利用して、同一視されて、当該同一視されたラベル列の集合を持つ遷移の集合及び当該遷移の集合に含まれる状態の集合、すなわち点線四角線で囲まれている部分（５０３）をマージする。その結果、縮退された有限オートマトン（５１１）が生成される。有限オートマトン（５１１）中の符号（５１２）で示されている部分に見られるように、有限オートマトン（５０１）中の上記部分（５０２及び５０３）がマージされている。
【０１１４】
有限オートマトンの最長パスを段階的に抽象化（縮退）させることによって、抽象化（縮退）された有限オートマトンが得られうる。得られる有限オートマトンは、段階が進むにつれてより抽象化されているといえる。
【０１１５】
図５Ｃは、有限オートマトン中の少なくとも２つの状態（ｓ，ｓ’）について状態ｓが状態ｓ’をシミュレートする場合に、当該状態（ｓ，ｓ’）のいずれかの状態をマージし、当該マージされた状態を有する縮退された有限オートマトンを生成する例（操作Ｓ）を示す。
【０１１６】
第３の生成部（２０２−３）は、有限オートマトン中の任意の少なくとも２つの状態について、当該少なくとも２つの状態のうちの一つの状態よりも後のｍ遷移ステップ（ｍは１以上の整数である）以内のパスが持つ文字列の集合が当該少なくとも２つの状態のうちの他の一つの状態よりも後のｎ遷移ステップ（ｎは１以上の整数である）以内のパスが持つ文字列の集合を包含するかどうかを判断する。
【０１１７】
有限オートマトン（５２１）においてｍ＝３である場合、状態Ｓ２からの３遷移ステップパス上のラベル集合（集合１）と、状態Ｓ４からの３遷移ステップパス上のラベル集合（集合２）は下記関係にある。
集合１＝{aac, cac, zaac}  ⊇  集合２＝{aac}  
従って、第３の生成部（２０２−３）は、状態Ｓ２が状態Ｓ４をシミュレートしていることから、状態Ｓ２とＳ４をマージして状態Ｓ２４とし、縮退された有限オートマトン（５２２）を生成する。
【０１１８】
次に、有限オートマトン（５２２）においてｍ＝２である場合、状態Ｓ１からの２遷移ステップパス上のラベル集合（集合３）と、状態Ｓ３からの２遷移ステップパス上のラベル集合（集合４）は下記関係にある。
集合３＝{aa, ac, az}  ⊇  集合４＝{ac}  
従って、第３の生成部（２０２−３）は、状態Ｓ１が状態Ｓ３をシミュレートしていることから、状態Ｓ１とＳ３をマージして状態Ｓ１３とし、縮退された有限オートマトン（５２３）を生成する。
【０１１９】
次に、有限オートマトン（５２３）においてｍ＝１である場合、状態Ｓ２４からの１遷移ステップパス上の文字列の集合は{z, a, c}であり、状態Ｓ１３の文字列の集合は{a}であり、状態Ｓ５の文字列の集合は{c}であり、状態Ｓ６の文字列の集合は{}である。よって、状態Ｓ１３、状態Ｓ５及び状態Ｓ６の全ての文字列が、状態Ｓ２４からの１遷移ステップパス上の文字列の集合に含まれている。すなわち、状態Ｓ２４がその他の状態全てをシミュレートしている。従って、状態Ｓ２４以外の状態を除去し（すなわち、全ての状態を状態Ｓ２４にマージし）、縮退された有限オートマトン（５２４）を生成する。
【０１２０】
図６Ａ〜図６Ｃは、本発明の実施態様に従い、有限オートマトン中の少なくとも１つの状態を除去し、当該除去された状態に関連付けられたエッジを含む少なくとも２つのエッジをマージして、縮退された有限オートマトンを生成する例（操作Ｔ）を示す。
【０１２１】
第２の生成部（２０２−２）は、有限オートマトンを縮退するために、（Ａ）状態除去指標に基づいて、（Ｂ）有限オートマトン中の部分構造体と他の部分構造体との包含関係に基づいて、若しくは有限オートマトン中の当該部分構造体と当該有限オートマトンとの包含関係に基づいて、又は、（Ｃ）上記（Ａ）及び（Ｂ）の組み合わせに基づいて、有限オートマトン中の少なくとも１つの状態を除去しうる。
【０１２２】
以下に、上記（Ａ）〜（Ｃ）についてそれぞれ説明する。
【０１２３】
（Ａ）状態除去指標に基づいて状態を除去する手法
第２の生成部（２０２−２）は、状態を除去するための指標として、有限オートマトン中の各状態についてそれぞれ状態除去指標を求める。状態除去指標は、オートマトン中の部分構造体の変化を評価する指標である。
【０１２４】
状態除去指標は、有限オートマトン中のある状態を除去することによるエッジのマージ回数と、当該ある状態の除去によりマージされることになるエッジに関連付けられた各状態に到達する入力文字列の数とから求められうる。
【０１２５】
エッジのマージ回数について、図６Ｃを参照して具体的に説明する。
【０１２６】
まず、エッジについて説明する。エッジには、入力文字列の集合Ｌがラベルとして付加されている。エッジのマージには、L1；L2及びL1∪L2の２種類がある。
L1= {s_1,…,s_n}, L2={t_1,…,t_m} のとき、
L1；L2 = {s_i, t_j | si∈L1, tj∈L2 } であり、
L1∪L2= {s_1,…,s_n, t_1,…,t_m} である（通常の集合の和である）。
【０１２７】
図６Ｃに示す有限オートマトン（６６１）において、状態Ｓ２を除去する場合を考える。状態Ｓ２が除去された場合のエッジのマージ回数は、下記の通りである。
・状態Ｓ１から状態Ｓ３について、マージ回数は２回である：
({a, b};{c, d} ) ∪ {aa, bb}   =  {ac, ad, bc, bd, aa, bb}
・状態Ｓ４から状態Ｓ３について、マージ回数は１回である：
{z};{c, d} = {zc, zd} 
従って、有限オートマトン（６６１）が有限オートマトン（６６２）に縮退される場合のエッジのマージ回数は２回＋１回の合計３回である。
【０１２８】
また、状態除去指標は、下記式から求められうる：
有限オートマトン中のある状態の入力エッジ数（IN）・当該ある状態の出力エッジ数（OUT）＋当該ある状態よりも一つ前の遷移ステップにある状態と一つ後の遷移ステップにある状態との間にある直接のエッジの数（COM）。
【０１２９】
また、状態除去指標ｒＭは、具体的には下記に示す関数式Ｆのいずれかに従って求められうる。
（１）F(N, IN・OUT＋COM) = N(IN・OUT+COM)、
（２）F(N, IN・OUT＋COM) = N・log(IN・OUT+COM)、又は
（３）F(N, IN・OUT) = N・log(IN・OUT)
ここで、Nは、ある状態に到達する入力文字列の集合の数である。
【０１３０】
状態除去指標を求める場合に上記のいずれの関数式Ｆを使用するかは、予めユーザによって関数式Ｆが指定されているか、又は操作Ｔを行う際にユーザが動的に関数式Ｆを指定するようにしてもよい。
【０１３１】
代替的には、状態除去指標ｒＭは、有限オートマトン中のある状態からエッジが分岐して合流する状態までの部分（抽象化単位）が当該有限オートマトン中の他の抽象化単位を真に包含しない場合において、当該有限オートマトン中の各状態のうち、到達する入力文字列の集合の数（N）が最小値をとる状態に対して定義されるメトリクスでありうる。
【０１３２】
代替的には、状態除去指標ｒＭは、有限オートマトン中の状態sを端点とする共通コンテキスト内パス集合が当該有限オートマトン中の他の共通コンテキスト内パス集合を真に包含しない場合において、当該有限オートマトン中の各状態のうち、到達する入力文字列の集合の数（N）が最小値をとる状態に対して定義されるメトリクスでありうる。ここで、有限オートマトン中の状態ｓを端点とする共通コンテキスト内パス集合とは、状態sから出た２つ以上のパスが状態s’で合流する場合又はある状態s’から出た２つ以上のパスが状態sで合流する場合に、状態sから状態s’又は状態s’から状態sへのパスの集合をいう。このようなパスの集合をCP[s]とすると、ある状態に到達する遷移も、当該ある状態から出て行く遷移も一つの状態ｓについてはCP[s]=φである。有限オートマトン中の状態sを端点とする共通コンテキスト内パス集合が当該有限オートマトン中の他の共通コンテキスト内パス集合を真に包含しない場合に状態ｓを削除することは下記式によって表されうる。
【０１３３】
第２の生成部（２０２−２）は、状態sが下記の場合に当該状態ｓを削除しうる：
iff  ¬ (∀s’,∀path’ ∈ CP[s’]，∃path ∈CP[s]
ここで、iffは、if  and only If を意味し、pathは、path’のサブパスである。
【０１３４】
第２の生成部（２０２−２）は、有限オートマトン中の各状態のうちの状態除去指標が最小である状態を特定し、当該特定された状態を有限オートマトンから除去しうる。そして、第２の生成部（２０２−２）は、当該除去された状態に関連付けられたエッジを含む上記有限オートマトン中の少なくとも２つのエッジをマージして、縮退された有限オートマトンを生成しうる。
【０１３５】
（Ｂ）有限オートマトン中の部分構造体と他の部分構造体との包含関係に基づいて、又は有限オートマトン中の当該部分構造体と当該有限オートマトンとの包含関係に基づいて状態を除去する手法
第２の生成部（２０２−２）は、除去する状態を特定する為に、有限オートマトン中の部分構造体と他の部分構造体との包含関係、又は、有限オートマトン中の当該部分構造体と当該有限オートマトンとの包含関係を判断しうる。第２の生成部（２０２−２）は、上記包含関係に基づいて、有限オートマトン中の少なくとも１つの状態を当該有限オートマトンから除去しうる。そして、第２の生成部（２０２−２）は、当該除去された状態に関連付けられたエッジを含む上記有限オートマトン中の少なくとも２つのエッジをマージして、縮退された有限オートマトンを生成しうる。
【０１３６】
（Ｃ）（Ａ）及び（Ｂ）の組み合わせに基づいて状態を除去する手法
第２の生成部（２０２−２）は、上記（Ａ）及び上記（Ｂ）に示した手法を組み合わせて、有限オートマトン中の少なくとも１つの状態を当該有限オートマトンから除去しうる。そして、第２の生成部（２０２−２）は、当該除去された状態に関連付けられたエッジを含む上記有限オートマトン中の少なくとも２つのエッジをマージして、縮退された有限オートマトンを生成しうる。
【０１３７】
図６Ａは、本発明の実施態様に従い、有限オートマトン中の状態を除去して、縮退された有限オートマトンを生成する例（操作Ｔ）を示す。
【０１３８】
図６Ａに示す有限オートマトン（６０１）は、図５Ａに示す有限オートマトン（５０１）と同じである。すなわち、有限オートマトン（６０１）は、図４に示す有限オートマトン（４０１）が操作Ｓにより縮退された有限オートマトンである。
【０１３９】
第２の生成部（２０２−２）は、有限オートマトン（６０１）中の各状態の状態除去指標を求める。
【０１４０】
有限オートマトン（６０１）中の点線四角線で囲まれている部分（６２１）の状態、すなわちN7，N8，N14，N15の状態除去指標はいずれも０である（状態N7，N8，N14，N15の状態除去指標は、５・log(1・1)=5log(1) = 0と計算される）。従って、第２の生成部（２０２−２）は、状態除去指標が最小値をとる上記N7，N8，N14，N15の状態を除去し、当該除去された状態に関連付けられたエッジ、すなわちSet(Report)，Set(Validation)，Set(Data)，Set(comparison)の各ラベルが付された各エッジを１つのエッジにマージする。マージされて生成された一つのエッジには、Set(Data, comparison, Report, Validation)というラベルが付される。
【０１４１】
また、有限オートマトン（６０１）中の点線四角線で囲まれている部分（６２２）の状態、すなわちN11，N12の状態除去指標はいずれも０である（状態N11，N12の状態除去指標は、4・log(1・1) = 4log(1) = 0と計算される）。従って、第２の生成部（２０２−２）は、状態除去指標が最小値をとる上記N11，N12の状態を除去し、当該除去された状態に関連付けられたエッジ、すなわちSet(XLS, PDF, CSV)，Set(TC, SC)，Set(_)，Set(XLS)の各ラベルが付された各エッジを１つのエッジにマージする。マージされて生成された一つのエッジには、Set(XLS, PDF, CSV, SC_XLS, TC_XLS)というラベルが付される。
【０１４２】
上記処理の結果、縮退された有限オートマトン（６１１）が生成される。
【０１４３】
図６Ｂは、本発明の実施態様に従い、有限オートマトン中の状態を除去して、縮退された有限オートマトンを生成する例（操作Ｔ）を示す。
【０１４４】
図６Ｂの上段は、操作Ｔが繰り返し行われて、有限オートマトン（６３１）が順に縮退されていく様子を示す。図６Ｂの下段に示した有限オートマトン（６５１）は上記上段に示した有限オートマトン（６３１）の各状態の状態除去指標を付記したものである。各状態中の数字は、各状態に到達する入力文字列の集合の数である。
【０１４５】
有限オートマトン（６３１）中、点線で示す状態（６４１）の状態除去指標が０であり、且つ、状態除去指標の当該値は有限オートマトン（６３１）中で最小である。さらに、状態（６４１）は、有限オートマトン（６３１）中の他の抽象化単位を真に包含していない。従って、第２の生成部（２０２−２）は状態（６４１）を除去し（１回目の操作Ｔ）、当該除去された状態（６４１）に関連付けられたエッジ、すなわちラベルｚ及びｇをそれぞれ持つエッジをマージして、縮退された有限オートマトン（６３２）を生成する。マージされて生成された一つのエッジには、ｚｇというラベルが付される。
【０１４６】
有限オートマトン（６３２）中、点線で示す状態（６４５）の状態除去指標が２．１であり、且つ、状態除去指標の当該値は有限オートマトン（６３２）中で最小である。さらに、状態（６４５）は、有限オートマトン（６３２）中の他の抽象化単位を真に包含していない。従って、第２の生成部（２０２−２）は状態（６４５）を除去し（２回目の操作Ｔ）、そして当該除去された状態（６４５）に関連付けられたエッジ、すなわちラベルｃ及びｚｇをそれぞれ持つエッジを上記除去された状態よりも一つ前のある状態６４６のエッジをマージし、並びに、ラベルｄ及びｚｇをそれぞれ持つエッジを上記除去された状態よりも一つ前のある状態６４６のエッジをマージして、縮退された有限オートマトン（６３３）を生成する。マージされて生成された各エッジには、｛ｚｇｃ，ａ｝及び｛ｚｇｄ，ｂ｝というラベルがそれぞれ付される。
【０１４７】
有限オートマトン（６３３）中、点線で示す状態（６４９）の状態除去指標が０であり、状態（６５０）の状態除去指標が０である。すなわち、有限オートマトン（６３３）は、状態除去指標が０である２つの状態（６４９，６５０）を有する。そこで、第２の生成部（２０２−２）は、状態に到達する入力文字列の集合の数が低い方、すなわち当該入力文字列の集合の数が４である状態（６４９）を、当該入力文字列の集合の数が６である状態（６５０）よりも優先して、除去する（３回目の操作Ｔ）。すなわち、第２の生成部（２０２−２）は、入力文字列の集合の数を重みとして使用する。第２の生成部（２０２−２）は、引き続き操作Ｔを繰り返し（４回目の操作Ｔ）、状態（６５０）を除去する（４回目の操作Ｔ）。第２の生成部（２０２−２）は、３回目の操作Ｔ及び４回目の操作Ｔを通じて、状態（６４９）及び状態（６５０）を段階的に除去し、当該除去された状態（６４９）及び状態（６５０）に関連付けられたエッジ、すなわちラベル｛ｚｇｄ，ｂ｝及びｆ並びに｛ｚｇｃ，ａ｝及びｅをそれぞれ持つエッジを最終的に全てマージして、縮退された有限オートマトン（６３４）を生成する。マージされて生成された各エッジには、｛ｚｇｃｅ，ａｅ，ｚｇｄｆ，ｂｆ｝というラベルがそれぞれ付される。
【０１４８】
上記のとおり、操作Ｔを段階的に繰り返すことによって、有限オートマトン（６３１）が順に抽象化（縮退）されていく。
【０１４９】
以下に、図６Ｂの上段に記載の有限オートマトンの例を使用して、有限オートマトンを縮退するための上記（Ｂ）について説明する。
【０１５０】
有限オートマトン（６３１）中の状態（６４２）は、当該状態（６４２）から２つのエッジが分岐して合流する状態（６４３）までの部分（抽象化単位）が有限オートマトン（６３１）中の他の抽象化単位（６４４）を包含している。従って、状態（６４２）は、除去される対象でない。一方、有限オートマトン（６３１）中の状態（６４１）は、有限オートマトン（６３１）中の他の抽象化単位を包含していない。従って、第２の生成部（２０２−２）は、状態（６４１）を除去することができる。
【０１５１】
また、有限オートマトン（６３２）中の状態（６４６）は、当該状態（６４６）から２つのエッジが分岐して合流する状態（６４７）までの部分（抽象化単位）が有限オートマトン（６３２）中の他の抽象化単位（６４８）を包含している。従って、状態（６４６）は、除去される対象でない。一方、有限オートマトン（６３１）中の状態（６４５）は、有限オートマトン（６３１）中の他の抽象化単位を包含していない。従って、第２の生成部（２０２−２）は、状態（６４５）を除去することができる。
【０１５２】
図７Ａは、本発明の実施態様に従い、有限オートマトンから正規表現パターンを獲得する例を示す。
【０１５３】
正規表現パターンとは、幾つかの正規表現を区別したものであり、文字列集合を抽象化した場合に、ｎ個の正規表現パターンがあることをいう。例えば、下記図１０Ｄでは、正規表現パターンが３個ある（図１０Ｄの符号１００４を参照）。
【０１５４】
表現式生成部（２０３）は、縮退の各処理段階における有限オートマトンに、遷移（エッジ）上の部分文字列の集合に、近似似パターン表現式を適用し、正規表現を獲得する。近似パターン表現式は、正規表現推論の関数を表現した式であるが、デフォルトの正規表現推論の関数として、正規表現推論関数の基本関数である  prim  、  choice  の近似パターン表現式  <prim>  ，  <choice>  が用いられうる。
【０１５５】
まず、正規表現推論関数について以下に説明する。
【０１５６】
正規表現推論関数は、入力文字列の集合からの正規表現の推論パターンを表しており、推論パターンが獲得されると、システムに格納されて再利用されうる。正規表現推論関数は、入力文字列の集合からの正規表現の段階的な推論過程において、正規表現推論関数として獲得される。正規表現推論関数の基本関数は予め用意されている。また、ユーザは、正規表現推論関数を入力文字列セット（stringset）から正規表現（regexp）型（string set → regexp型）の関数として自由に定義しうる。
【０１５７】
予め用意されている正規表現推論関数の基本関数（プリミティブな関数ともいう）は、下記の通りである。
−  choice    文字列のchoiceによる結合をとり、何も近似（approximate）しない推論関数である。
−  prim    文字クラスのラティス構造による抽象化とプレフィックス（prefix）又はポストフィックス（postfix）の同定を組み込んだ近似（approximation）である。primは、文書解析の現場からの知見をアドホック（ad-hock）に組み込んで近似パターン表現式を推論する推論関数である。
−  表現式  その他に任意の表現式をプログラミングにより作成しておくことが可能である。
【０１５８】
choiceは、例えば、( che ({s1,..,sn)}= s1 | .. | sn )で表される。
【０１５９】
primは、入力文字列が例えば{AAB33b1C, ABC45BhC}である場合に、当該入力文字列をA[A-Z][A-Z][0-9][0-9][A-Z][.]C又はA[A-Z][A-Z][0-9][0-9][A-Z]\p{Alnum}Cに変換するために使用される。ここで、最初のAは共通プレフィックスであり、最後のCは共通ポストフィックスである。
【０１６０】
primのアルゴリズムについて、図７Ｂを参照しながら説明する。図７Ｂは、primのアルゴリズムにおいて使用されうる文字クラス・ラティス構造（７１１）を示す。primのアルゴリズムは、プレフィックス又はポストフィックスの同定と文字クラスの同定による繰り返し的な抽象化を特徴とする。
【０１６１】
primのアルゴリズムは、以下の通りである。
ステップ１：コンピュータは、入力文字列の集合の共通のプレフィックス及びポストフィックスを取り出す。
ステップ２：コンピュータは、残った文字列を１段階、図７Ｂに示す文字クラス・ラティス上で抽象化する。
ステップ３：コンピュータは、長さが同じならインデックスごとに、図７Ｂに示す文字クラス・ラティス上の最小上界をとる。
ステップ４：コンピュータは、全ての文字が. であれば  .{n} or .+ or .*   に変換する（長さを見て判断する）。そうでないなら、ステップ１に戻る。
【０１６２】
図７Ｂに示す文字クラス・ラティスにおいて、.  は、どのような文字でも良いことを示し、\S  は、空白以外を示し、\s  は、空白を示し、\d  は、数字を示し、[a-zA-Z]  は小文字大文字を示し、[a-z]  は小文字を示し、[A-Z]  は大文字を示す。
【０１６３】
有限オートマトン（７０１）から正規表現パターンの推論は、下記に示す方法に従い行われる。
【０１６４】
正規表現パターンの推論の処理のための入力は、ラベルが文字列集合である有限オートマトン、近似パターン表現式α，β，・・である。近似パターン表現式の指定が特にない場合には、正規表現推論関数の基本関数であるprimの近似表現式  <prim>  を入力として用いる。
正規表現パターンの推論の処理による出力は正規表現パターンである。正規表現パターンは、例えば、r1 | r2 | … | rk という形の正規表現候補でありうる。
【０１６５】
正規表現パターンの推論のためのステップは、下記の通りである。
ステップ１：表現式生成部（２０３）は、入力の有限オートマトンの開始状態から終了状態への全パスをもとめてPathとおく。パスは各遷移を一回通るもので十分であるので、ループがあってもよい。
ステップ２：表現式生成部（２０３）は、各path∈Path に対して、パターンP[path]を以下の手順で求める。
−  表現式生成部（２０３）は、path上のラベルを全てならべてS1…Skとし、Si.size>1の部分を部分パターン<#i>とし、Sj.size=1のものは、sj s.t. sｊ∈Ｓｊと置き直す。path上のラベルは、部分文字列の集合（トークンの集合）である。
−  表現式生成部（２０３）は、P[path] = u1,…, uk   where ui = si or <#i> ，各<#i> のバリエーションSをパターンとして得る。
ステップ３：各path∈Path に対して、P[path]の部分パターン<#i>を正規表現α(Si)で置き換えたもの<#i>のマッチング文字列を、Siに含まれていた文字列si∈Si とする。
【０１６６】
以下に、図７Ａに従って、有限オートマトン（７０１）から正規表現パターンの推論を行う処理を具体的に説明する。
表現式生成部（２０３）は、図７Ａに示す有限オートマトン（７０１）中の遷移上の部分文字列の集合｛ａ，ｇｃ｝及び｛ｂ，ｇｄ｝に正規表現推論関数αをそれぞれ適用する。表現式生成部（２０３）は、上記ステップ１の処理を行い、有限オートマトン（７０１）の開始状態から終了状態への全パスを求めて、Path｛ａ，ｇｃ｝ｅ及びPath｛ｂ，ｇｄ｝ｆを得る（７０２）。表現式生成部（２０３）は、上記ステップ２の処理を行い、P[path]＜＃１＞及びP[path]＜＃２＞ｆを得る（７０３）。表現式生成部（２０３）は、上記ステップ３の処理を行い、正規表現Ａｅ（７０４）及び正規表現Ｂｆ（７０５）を得る。
【０１６７】
図８は、本発明の実施態様に従い、有限オートマトンから正規表現を得て、さらに正規表現推論関数を近似パターン表現式として獲得する例を示す。
【０１６８】
正規表現推論関数の獲得の処理のための入力は、ラベルが文字列集合である有限オートマトン、近似パターン表現式α，β，・・である。近似パターン表現式の指定が特にない場合には、正規表現推論関数の基本関数であるprimの近似表現式  <prim>  を入力として用いる。
正規表現推論関数の獲得の処理による出力は、入力文字列セット（string set）から正規表現（regexp）型（string set → regexp型）の関数、又は、近似パターン表現式の表現式である。
【０１６９】
正規表現推論関数の獲得のためのステップは、下記の通りである。
ステップ１：表現式生成部（２０３）は、有限オートマトンの遷移ラベル上で複数の部分文字列を持つ部分を、選択された又は指定された近似パターン表現式名に置き換える。
ステップ２：表現式生成部（２０３）は、有限オートマトンから近似パターン表現式を表す記号を含む正規表現を得る。ステップ２では、表現式生成部（２０３）は、図３に記載のステップ５の手法を使用しうる。代替的には、表現式生成部（２０３）は、既存の方法を使用して、有限オートマトンから正規表現を得てもよい。
ステップ３：表現式生成部（２０３）は、上記近似パターン表現式名を含んだ正規表現を正規表現推論関数の表現式とみなす。当該正規表現において、−｜と // の区別の自由度があるが、１番外側の  |  を  //  にすればよい。
ステップ４：推論関数生成部（２０４）は、上記表現式から下記に示す解釈（Interpretation） Iappro を用いて正規表現推論関数を得る。
【０１７０】
以下に、図８に示す有限オートマトン（８０１）から得られる近似パターン表現式（８０３）から正規表現推論関数を獲得する処理を説明する。
表現式生成部（２０３）は、上記ステップ１の処理を行い、図８に示す有限オートマトン（８０１）中の遷移上の部分文字列の集合｛ａ，ｇｃ｝及び｛ｂ，ｇｄ｝に近似パターン表現式（正規表現推論関数の基本関数に対応する近似パターン表現式、又は任意の近似パターン表現式でありうる）<α>及び<β>をそれぞれ適用する。表現式生成部（２０３）は、上記ステップ２の処理を行い、部分文字列の集合｛ａ，ｇｃ｝を近似パターン表現式<α>に置き換え、且つ、部分文字列の集合｛ｂ，ｇｄ｝を近似パターン表現式<β>に置き換える（８０２）。推論関数生成部（２０４）は、上記ステップ３の処理を行い、正規表現推論関数の表現式を獲得する（８０３）。推論関数生成部（２０４）は、上記ステップ４の処理を行い、正規表現推論関数（８０４）を獲得する。
【０１７１】
近似パターン表現式ついて、以下に説明する。近似パターン表現式は、下記式Aの通りに定義される。式Aは、当該式Aによるマッチング時に近似パターン表現式<α>に該当する部分をαで近似する関数で表現する。
【０１７２】
A  ::=   str  |  <α>  |  A1A2  |  A1  |  A2  |  A1  //  A2  |  A* 
【０１７３】
・αは、正規表現推論関数の名前であり、<α>は、文字列集合を正規表現推論関数αにより正規表現に変換するという変換パターンを表す近似パターン表現式である。
・近似パターン表現式は、正規表現を、正規表現推論関数名αを用いた<α>と 構成子   //  で拡張したものである。
・近似パターン表現式は、入力文字列の集合を正規表現へと近似する、その近似パターンを表現している。
・段階的な正規表現推論器（操作Ｓ又は操作Ｔ）で推論を行った際に、その近似パターンを近似パターン表現式として獲得できる。そのために、コンピュータは、他の入力文字列の集合を近似パターン表現式に変換する処理において、当該獲得された近似パターン表現式を再利用可能である。
【０１７４】
近似パターン表現式から正規表現推論関数への変換について、以下に説明する。
・Aを入力文字列セット（string set）から正規表現（regexp）型（string set → regexp型）の関数と解釈できる。従って、推論関数生成部（２０４）は、式Aから正規表現推論関数を作り出すことができる。
・アルゴリズムの前提は、下記の通りである。
−  関数をλ計算で記述する。λx. Mは、仮引数 x、関数の本体がMであるような関数である。例えば、λx.(x+1)は、引数に対して＋１する関数である。
−  関数fの最小不動点を計算する関数を lfp(f) とする。
−  入力文字列を s1,…,sk などで表し、入力文字列の集合を S、又は、{s1,…,sk} などで表す。
−  ^を文頭文字、$を文末文字（それぞれ、文頭、文末のみにマッチする）とする。
−  文字列に対する正規表現のマッチャーアルゴリズムm を準備し固定する。
・  正規表現rと入力文字列sに対して、m(r,s)= if (r matches s ) then true else falseとする。
・  m(r,s) = true の場合に、正規表現のグループiにおいてキャプチャリングされた入力文字列をr[s][i]とおく。
−  正規表現rと入力文字列sに対して、関数M(r,S)を以下に示す式で定める。ここで、rがS（文字列の集合）に含まれる全入力文字列にマッチする場合にtrueとし、それ以外はfalseとする。：
・  M(r, {s1,..,sk}) =  if ( m(r, sj) for all j =1..k) then true else false
−  αは文字列集合から正規表現への関数の名前である。αが表す関数を《α》で表す。
−  入力文字列の集合から正規表現への関数prim及び関数choiceが既に定義されていると仮定する。
−  入力文字列の集合から正規表現への関数fと文字列集合Ｓに対して、f(S) =/= choice(S) の場合に、Abst(f, S) と書く。これは、関数fにより、文字列集合Ｓが抽象化されることを意味する。
【０１７５】
以下に、近似パターン表現式から正規表現推論関数を作成する為に使用される解釈Iapproの例を示す。
変換《・》  ：  A → (string set → regexp)
・  《A 》 = λx. M ならば、Aは、入力文字列の集合Sを受け取り、関数Mの中のxをSで置き換えた式 M[S/x] を評価する関数である。
・  Aは帰納的に定義されるので、《・》を帰納的に定義することが出来る。
−  《str 》 = λx .   if  M(^str$,x)
then  str  else choice(S)
−  《 <α> 》  =  《α》
−  《 A1 A2 》  = λx .   if  Abst( 《A1》, x)  and  Abst( 《A2》,  {  《A1》(x) (.*)  [s][1]  |s∈x } ) 
then   《A1》(x) 《A2》 ( {  《A1》(x)(.*)  [s][1]  | s∈x } )   else  choice(x)
・  《 A1 A2 》は、入力文字列の集合Sに対して初めにA1で推論して、その右側をA2で推論する関数である。
−  《A1 | A2 》 = λx .   if (  Abst( 《A1》, v1)  and  ¬Abst( 《A1》 , v2)   for  v1 ⊆x ,v1⊂v2⊆x ) and
(  Abst( 《A2》,  u1)  and  ¬Abst( 《A2》 , u2)  for   u1⊆x,  u1⊂u2⊆x ) 
then  《A1》(v1) |  《A2》(u1)  else choice(x) 
・  《A1 | A2 》は、入力文字列の集合Sのうち、A1で近似される部分集合のみをA1で推論し、A2で近似される部分集合のみをA2で推論し、|  で結合して返す関数である。
−  《A1 // A2 》 = λx .   If ( Abst( 《A1》,  v1) and  ¬Abst( 《A1》 , v2)   for  v1 ⊆x ,v1⊂v2⊆x )
then  《A1》(v1)  |   《A2》( x &#8211; v1)    else  《A2》(x)
・  《A1 // A2 》は、入力文字列の集合Sのうち、A1で近似される部分集合のみをA1で推論し、それ以外の部分集合をA2で推論し、|  で結合して返す関数である。
−  《 A* 》 =  lfp (λx .if   Abst( 《A1》,x)   and  Abst( 《A2》,  {  《A*》(x) (.*)  [s][1]  | s∈x } )
then   《A1》(x) 《A*》 ( {  《A1》(x)(.*)  [s][1]  |s∈x } )   else  choice(x) )
・  《 A* 》は、Aで近似できる最初の部分をAで推論し、残りの部分をまたA*で繰り返し推論する関数である。
【０１７６】
正規表現推論関数の基本関数は各々のシチュエーションごとに便利なものを予め定義して、再利用用に表現式を保存可能である。正規表現推論関数は、文字列集合から正規表現を求めるための再利用可能な推論（近似）のパターンを表している。
【０１７７】
以下に、シチュエーションごとに有用な正規表現推論関数の表現式の定義例を示す。
−  File-extensionを認識してprimを適用する正規表現推論関数:
fext =  《<prim> \. (?! .*\. .*)<prim>》
例：  {design.xls, data.csv. text.myext}
⇒  [a-z]+ \. [a-z]+）
−  括弧を持つFile名を認識する正規表現推論関数:
parenExt = 《<prim> \( <prim> \)  <fext>》
例：  {“金額確定制御（原本）.xls”, “外貨貯蓄口座処理（改定）.xls”}
⇒  (\kanj)+ \( \kanji{2} \) \.xls
（ただし、\kanji は \p{InCJKUnifiedIdeographs}の \kanji{3} は \kanji\kanji\kanjiの略記である）
−  括弧があるものとないもの区別して推論する正規表現推論関数:
parenFext = 《<parenExt> //<fext>》
例：  {“金額確定制御.xls”, “外貨貯蓄口座処理（改定）.xls”, “口座確定制御.xls, 金額確定制御（改定).xls}
⇒  (\kanj)+ \( \kanji{2} \) \.xls | (\kanji)+ \. xls 
・  parenFextは、括弧を持つものとそうでないものを別々のパターンとして取り出すような推論を表現する。
−  文書系Fileを分離して推論する正規表現推論関数：
docext = 《 <prim> \. (?! .* \..*)  (xls // doc // txt // ppt) 》
例：  {“TestCase1.xls,TestCase2.xls, readme.txt,test.txt, Proj1.ppt, Proj2.ppt, memo.txt, A.dot, B.myext}
⇒  TestCase\d\.xls | [a-z]+\.txt | Proj\d\.ppt | [a-z]+\.txt|[A-Z]\.[a-z]+
【０１７８】
図９Ａは、本発明の実施態様に従い、近似パターン表現式ストア（２１４）から、バリエーション・パターン中の特定の部分（以下、近似対象部分ともいう）、例えば場所<k>に適用可能な近似パターン表現式を判定する処理のためのフローチャートの例を示す。
【０１７９】
バリエーション・パターン（Var-Pattern）とは、抽象化の対象の部分と、当該抽象化の対象部分にマッチしている部分文字列を表すパターンである。まず、バリエーション・パターン（下記図９Ｂの符号９２１を参照）中の特定の部分（すなわち、近似対象部分）は例えば、バリエーション・パターン中の場所<k>である。バリエーション・パターン中の場所<k>をフォーカスした際に適用可能な近似パターン表現式を判定するアルゴリズム（以下、「近似パターン表現式判定プログラム」ともいう）を下記に示す。場所<k>は、抽象化の対象の部分である。なお、近似パターン表現式を格納する近似パターン表現式ストア（２１４）には、近似パターン表現式P1,…,Pmが存在するものとする。
ステップ１：表現式生成部（２０３）は、正規表現推論関数の基本関数を近似パターン表現式の候補とし、近似パターン表現式ストア（２１４）に近似パターン表現式が格納されていれば当該格納されている近似パターン表現式も近似パターン表現式の候補とする。近似パターン表現式の候補は、例えば、デフォルトでは、正規表現推論関数の基本関数primの近似パターン表現式  <prim>  である。
ステップ２：表現式生成部（２０３）は、バリエーション・パターン中の場所<1>…<n>部分を(.*)で置き換えて得られる正規表現をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（２１４）中の近似パターン表現式P1, ... ,Pmに対して正規表現でreg_vをマッチさせる。
ステップ４：表現式生成部（２０３）は、マッチが成功した近似パターン表現式Piについて、reg_vの<k>に対応する(.*)部分でキャプチャリングされた部分の近似パターンを
Psub_iとする。
ステップ５：表現式生成部（２０３）は、以下に従い、上記部分の近似パターンPsub_iから適応可能な近似パターン表現式を判定する。
−  Psub_iが<k>がまとめている部分文字列集合の全てにマッチする場合に、Psub_j を近似パターン表現式の候補として表示する。
−  Psub_iが<k>がまとめている部分文字列集合の一部にマッチする場合に、Psub_i | <choice>を近似パターン表現式の候補として表示する。
−  Psub_iが<k>がまとめている部分文字列集合のどれにもマッチしない場合に、近似パターン表現式を、<k>をフォーカスした際のバリエーション・パターンに適用不可能であり、近似パターン表現式の候補は作成されない。
【０１８０】
以下に、図９Ａに示すフローチャートについて説明する。
適用可能な近似パターン表現式を判定する処理のための入力は、PS={P1,…,Pm}；バリエーション・パターン（Var-Pattern）  vp；及び、vpにおいてフォーカスしている場所<k>である。ここで、PSは、現在の近似パターン表現式ストア（２１４）中の近似パターン表現式の集合である。
出力は、PAであり、適用可能な近似パターン表現式である。
【０１８１】
ステップ９０１では、表現式生成部（２０３）は、バリエーション・パターン中の場所<k>に適用可能な近似パターン表現式を近似パターン表現式ストア（２１４）中の近似パターン表現式の集合から判定する処理を開始する。
【０１８２】
ステップ９０２では、表現式生成部（２０３）は、PAを空集合にセットする。
【０１８３】
ステップ９０３では、表現式生成部（２０３）は、Sk＝vpの場所<k>にマッチしている部分文字列の集合を獲得する。ここで、Skは、バリエーション・パターンの<k>の部分にマッチしている部分文字列の集合である。例えば、下記図９Ｂでは、S_1  は  <1>=Set(…) で記されている文字列の集合である。
【０１８４】
ステップ９０４では、表現式生成部（２０３）は、PSに、現在の近似パターン表現式ストア（２１４）中の近似パターン表現式の集合を代入する。
【０１８５】
ステップ９０５では、表現式生成部（２０３）は、PS中の近似パターン表現式のうち、「正規表現推論関数の基本関数そのものからなる近似パターン表現式」、すなわち<prim>及び<choice>などの近似パターン表現式を集めてできる集合をPS_Fとする。
【０１８６】
ステップ９０６では、表現式生成部（２０３）は、PS中の近似パターン表現式のうち、「Skが含む全ての文字列にマッチする近似パターン表現式」を集めて出来る集合をPS_Skとする。
【０１８７】
ステップ９０７では、表現式生成部（２０３）は、PA= PA ∪ PS_Sk ∪PS_F  を求める。
【０１８８】
ステップ９０８では、表現式生成部（２０３）は、PS= PS − （PS_Sk ∪ PS_F）  を求める。
【０１８９】
ステップ９０９では、表現式生成部（２０３）は、reg_v= vp 中の場所<1>, …, <n>を、(.*)[1],…,(.*)[n]で置き換えて得られる正規表現([1],…, [k]はプレースホルダー）を獲得する。
【０１９０】
ステップ９１０では、表現式生成部（２０３）は、PS中の近似パターン表現式のうち、「reg_vにマッチする近似パターン表現式」を集めて出来る集合をPS_reg_vとする。
【０１９１】
ステップ９１１では、表現式生成部（２０３）は、PS_reg_vが空集合であるかどうかを判断する。PS_reg_v が空集合でないことに応じて、表現式生成部（２０３）は、処理をステップ９１２に進める。一方、PS_reg_vが空集合であることに応じて、表現式生成部（２０３）は、処理をステップ９１３に進める。
【０１９２】
ステップ９１２では、表現式生成部（２０３）は、Psub に、PS_reg_v から近似パターン表現式を一つ取り出し、代入する。
【０１９３】
ステップ９１３では、表現式生成部（２０３）は、PS_reg_v が空集合であることに応じて、PSを出力する。そして、表現式生成部（２０３）は、処理を、適用可能な近似パターン表現式を判定する上記処理を終了するステップ９２０に進める。
【０１９４】
ステップ９１４では、表現式生成部（２０３）は、Psub_i に、PS_reg_v のreg_vでのマッチングに際して、(.*)[k] でキャプチャリングされる部分に対応する近似パターン表現式を代入する。
【０１９５】
ステップ９１５では、表現式生成部（２０３）は、Psub_i がSkに含まれる全ての文字列にマッチするかどうかを判断する。Psub_i がSkに含まれる全ての文字列にマッチしないことに応じて、表現式生成部（２０３）は、処理をステップ９１６に進める。一方、
sub_iがSkに含まれる全ての文字列にマッチすることに応じて、表現式生成部（２０３）は、処理をステップ９１７に進める。
【０１９６】
ステップ９１６では、表現式生成部（２０３）は、Psub_i がSkに含まれる一部の文字列にマッチするかどうかを判断する。Psub_i がSkに含まれる一部の文字列にマッチしないことに応じて、表現式生成部（２０３）は、処理をステップ９１９に進める。一方、
sub_iがSkに含まれる一部の文字列にマッチすることに応じて、表現式生成部（２０３）は、処理をステップ９１８に進める。
【０１９７】
ステップ９１７では、表現式生成部（２０３）は、PＳ = PS ∪ {PSub_i}  を求め、処理をステップ９１９に進める。
【０１９８】
ステップ９１８では、表現式生成部（２０３）は、PＳ = PS ∪ {PSub_i|<choice>}  を求め、処理をステップ９１９に進める。
【０１９９】
ステップ９１９では、表現式生成部（２０３）は、PSに、PS − {PSub}
を代入し、処理をステップ９１１に戻す。PS は、ステップ９１７又はステップ９１８から得られるものでありうる。PSub は、ステップ９１６から得られるものでありうる。
【０２００】
ステップ９２０では、表現式生成部（２０３）は、上記近似パターン表現式を判定する処理を終了する。
【０２０１】
近似パターン表現式判定プログラムのステップ１〜５と、図９Ａに示したフローチャートの各ステップとの関係を以下に示す。
近似パターン表現式判定プログラム      図９Ａに示したフローチャート
ステップ１                ＝  ステップ９０５及び９０６
ステップ２                ＝  ステップ９０９
ステップ３                ＝  ステップ９１０
ステップ４                ＝  ステップ９１４
ステップ５                ＝  ステップ９１５、９１６、９１７、及び９１８
【０２０２】
図９Ｂは、本発明の実施態様に従い、図９Ａに従うフローチャートを用いて、英語及び数字の文字列からなるファイル名を例として、バリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定する例を示す。
符号９２１に示すバリエーション・パターン中の場所<1>（９３１）をフォーカスした場合に、当該場所<1>（９３１）において適用可能な近似パターン表現式を判定する処理を下記に説明する。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（２１４）中の近似パターン表現式  <prim>  ,  <choice>  を候補とする。
ステップ２：表現式生成部（２０３）は、正規表現  Sc(.*)>.xls  を得る。
ステップ３：表現式生成部（２０３）は、図９Ａに示すフローチャートのステップ９１０において示すように、近似パターン表現式  Sc1<prim>>.xls  がマッチする近似パターン表現式であると判定する。
ステップ４：表現式生成部（２０３）は、図９Ａに示すフローチャートのステップ９１４において示すように、キャプチャリングされる部分パターンは  1<prim>  であると判定する。
ステップ５：表現式生成部（２０３）は、図９Ａに示すフローチャートに従い、
1<prim>  は、A0_LiDiSc<AA  にはマッチせず（ステップ９１５）、
11_InSc<EF30  、及び  12_ItIpSc<EG43  にマッチするので（ステップ９１６）、
1<prim> | <choice>  が適用可能であると判定し、これらをバリエーション・パターン中の場所<1>に適用可能な近似パターン表現式の候補とする。
ステップ６：その結果、表現式生成部（２０３）は、近似パターン表現式  <prim>  ,   <choice>  ，  1<prim> | <choice>  を、バリエーション・パターン中の場所<1>（９３１）の部分の近似パターン表現式の候補とする。表示部（２０６）は、これら候補を画面上に表示しうる。代替的には、提示部（２０５）は、これら候補をアプリケーション（図示せず）に渡しうる。
【０２０３】
図９Ｃは、本発明の実施態様に従い、図９Ａに従うフローチャートを用いて、日本語（漢字）、英語及び数字の文字列からなるファイル名を例として、バリエーション・パターン中の近似対象部分に適用可能な近似パターン表現式を判定する例を示す。
符号９４１に示すバリエーション・パターン中の場所<1>（９５１）をフォーカスした場合に、当該場所<1>（９５１）において適用可能な近似パターン表現式を判定する処理を下記に説明する。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（２１４）中の近似パターン表現式  <prim>  ,  <choice>  を候補とする。
ステップ２：表現式生成部（２０３）は、正規表現  画面(.*)>.xls  を得る。
ステップ３：表現式生成部（２０３）は、図９Ａに示すフローチャートのステップ９１０において示すように、近似パターン表現式  画面1<prim>>.xls  がマッチする近似パターン表現式であると判定する。
ステップ４：表現式生成部（２０３）は、図９Ａに示すフローチャートのステップ９１４において示すように、キャプチャリングされる部分パターンは  1<prim>  であると判定する。
ステップ５：表現式生成部（２０３）は、図９Ａに示すフローチャートに従い、
1<prim>  は、A0_一覧表示画面<AA  にはマッチせず（ステップ９１５）、
11_初期画面<EF30  、及び  12_項目入力画面<EG43  にマッチするので（ステップ９１６）、  1<prim> | <choice>  が適用可能であると判定し、これらをバリエーション・パターン中の場所<1>に適用可能な近似パターン表現式の候補とする。
ステップ６：その結果、表現式生成部（２０３）は、近似パターン表現式  <prim>  ,   <choice>  ，  1<prim> | <choice>  を、バリエーション・パターン中の場所<1>（９５１）の部分の近似パターン表現式の候補とする。表示部（２０６）は、これら候補を画面上に表示しうる。代替的には、提示部（２０５）は、これら候補をアプリケーション（図示せず）に渡しうる。
【０２０４】
実施例１
入力文字列（英語及び数字の文字列からなるファイル名）の集合を近似パターン表現式に段階的に変換する各処理を、図１０Ａ〜図１０Ｕに示す画面例を用いて説明する。図１１Ａ〜図１１Ｆは、当該実施例１中において生成される各有限オートマトンを示す。また、図１０Ｖは、実施例１の処理によって正規表現推論関数ストア（２１５）に格納された正規表現推論関数を、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理において再利用可能であることを示す画面例である。実施例１において用いられているファイル名中の下記文字列は、下記英単語の略である：
文字列  ;  英単語
Sc    ;  Screen
In    ;  Initial
It    ;  Item
Ip    ;  Input
Li    ;  List
Di    ;  Display
Nw    ;  New
Cl    ;  Client
Or    ;  Order
Rp    ;  Report
【０２０５】
図１０Ａは、文字列集合を入力し、当該文字列集合から最初の１つの有限オートマトンを生成する処理を開始するための画面例である。
ユーザは、例えば、文字列集合（２１２）を含むファイルを記憶装置（２１１）から読み出す指示をコンピュータ（２０１）に送る（図示せず）。当該指示に応じて、第１の生成部（２０２−１）は、文字列集合（２１２）を含む上記ファイルを記憶装置（２１１）から読み出す（ステップ１の処理）。そして、表示部（２０６）は、当該読み出した文字列集合（２１２）をその画面上の所定のサブウィンドウ（１０２２）内に表示する。図１０Ａの例では、入力文字列の集合の数は５である。当該文字列集合は、フォルダ中のファイル名の例である。ユーザは、入力文字列の集合を近似パターン表現式に変換する処理の開始を指示するために、ウィンドウ（１０２１）内の「開始」ボタンをクリックする。第１の生成部（２０２−１）は、ステップ１の処理で読み出した入力文字列の集合から１つの有限オートマトンをメモリ（１０３）内に生成する（ステップ２の処理）。図１１Ａは、当該ステップ２の処理によって生成された有限オートマトン（１１０１）を示す。
【０２０６】
図１０Ｂは、図１１Ａに示す有限オートマトン（１１０１）に操作Ｓの抽象化処理を開始するための操作を示す画面例である。
表示部（２０６）は、ウィンドウ（１００１）内に、入力文字列の集合（１００２）及びその集合の数である５、入力文字列の集合を近似パターン表現式に変換する処理の状態（１００３）、並びに正規表現候補（１００４）を表示する。
状態（１００３）中の「起点」という文字で指し示す丸印は、当該実施例１での抽象化処理の起点（開始点）を示す。黒印は、直前に終えた抽象化処理の位置を示す。図１０Ｂにおいて、起点が黒丸になっていることから、最初の１つの有限オートマトン（１１０１）がすでに生成されていること、すなわちステップ２の処理が既に終了していることを示す。当該黒丸の下方向にある丸印は操作Ｓによる有限オートマトンの抽象化処理が可能であることを示す。なお、当該黒丸の右方向にある白丸（図１０Ｂでは図示されていない）がある場合には、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
図１０Ｂでは、当該黒丸（起点）から下方向に丸印が１つ示されている。この下方向にある白丸は、ユーザが、操作Ｓによる有限オートマトン（１１０１）の抽象化処理を選択することが可能であることを示す。
【０２０７】
ユーザが有限オートマトン（１１０１）に操作Ｓの抽象化処理を適用したいとする。ユーザは、状態（１００３）中の上記白丸をマウスでクリックし、有限オートマトン（１１０１）に対して操作Ｓの抽象化処理を開始することを指示する。上記白丸の左隣の数字（２４）は、操作Ｓの最初の抽象化処理前においては、有限オートマトン（１１０１）の最長の入力文字列の数を表す。しかし、最初の操作Ｓの抽象化処理が終了した後は、kを最小の入力文字列の数から減少させるが最長の入力文字列の数を表すとは限らない。kが小さくなるほど、操作Ｓによって大きく抽象化されるので、kを段階的に減らすことにより段階的に抽象化されていることを示す。
【０２０８】
第３の生成部（２０２−３）は、上記操作Ｓの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１１０１）に対して操作Ｓの抽象化処理を行う。第３の生成部（２０２−３）は、操作Ｓの抽象化処理によって図１１Ａに示す有限オートマトン（１１０１）中の共通パスの状態（符号１１１１及び１１１２の部分）をマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ３の処理）。符号１１１１で示される共通パスは、>.xls  という共通のラベル列の集合を持つ。符号１１１３で示される共通パスは、>.ppt  という共通のラベル列の集合を持つ。図１１Ｂは、当該ステップ３の処理によって生成された有限オートマトン（１１０２）を示す。有限オートマトン（１１０２）において、共通パスが持つラベル列の集合が持つ遷移の集合、及び当該集合に含まれる状態の集合がマージされている（符号１１１１について「>.xls」、及び符号１１１２について「>.ppt」）。
【０２０９】
図１０Ｂにおいて正規表現候補は、入力文字列そのものと同じである。なぜならば、図１１Ａに示す有限オートマトン（１１０１）はまだ抽象化されていないからである。
【０２１０】
図１０Ｃは、図１１Ｂに示す有限オートマトン（１１０２）に操作Ｔ（１回目）の抽象化処理を開始するための操作を示す画面例である。
状態（１００３）中の黒印は、直前に終えた処理である操作Ｓの抽象化処理（ステップ３）の位置を示す。図１０Ｃにおいて、起点直下の丸が黒丸になっていることから、最初の有限オートマトンに操作Ｓが適用されて縮退された有限オートマトンがすでに生成されていること、すなわちステップ３の処理が既に終了していることを示す。当該黒丸の下方向にある白丸は操作Ｓによる有限オートマトンの抽象化処理が可能であることを示し、当該黒丸の右方向にある白丸は、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
【０２１１】
ユーザが有限オートマトン（１１０２）に操作Ｔの抽象化処理を適用したいとする。ユーザは、状態（１００３）中の上記黒丸の右隣にある白丸をマウスでクリックし、有限オートマトン（１１０２）に操作Ｔの抽象化処理を開始することをコンピュータ（２０１）に指示する。
【０２１２】
第２の生成部（２０２−２）は、上記操作Ｔの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１１０２）に対して操作Ｔの抽象化処理を行う。第２の生成部（２０２−２）は、操作Ｔの抽象化処理によって図１１Ｂに示す有限オートマトン（１１０２）中の状態を除去し、エッジをマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ４の処理）。図１１Ｃは、当該ステップ４の処理によって生成される有限オートマトン（図１１Ｄ、１１０４）の途中経過の有限オートマトン（１１０３）を示す。図１１Ｄは、当該ステップ４の処理（１回目）によって生成される有限オートマトン（１１０４）を示す。
【０２１３】
図１０Ｄは、図１０Ｃに示す操作Ｔの抽象化処理から生成された有限オートマトン（１１０４）から正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の場所<1>及び場所<2>にそれぞれ適用可能な近似パターン表現式を判定するための操作を示す画面例である。
表示部（２０６）は、図１０Ｃに示す操作Ｔの処理終了後に、ウィンドウ（１００１）内に、入力文字列の集合（１００２）及びその集合の数である「５」、入力文字列の集合を段階的に近似パターン表現式に変換する処理の状態（１００３）、並びに正規表現候補（１００４）に加えて、バリエーション・パターン（１００５）及び当該バリエーション・パターン中の場所<k>に適用可能なデフォルトの近似パターン表現式（１００６）を表示する。
【０２１４】
ユーザは、バリエーション・パターン（１００５）中の場所<k>をフォーカスした際に適用可能な近似パターン表現式を、図９Ａに記載のフローチャートに従い判定する処理を開始するために、近似パターン表現式の選択というボタンをマウスでクリックする。図１０Ｄでは、バリエーション・パターン（１００５）中に場所<1>及び場所<2>があることを示し、当該場所<1>及び<2>のいずれにおいても、デフォルトの近似パターン表現式として指定されている  <prim>  が最初に表示されている。なお、prim  は正規表現推論関数（の名前）であり、<prim>  は、近似パターン表現式である。
【０２１５】
ユーザが場所<1>に適用可能な近似パターン表現式を判定する処理を開始するために、場所<1>に関連付けられた選択ボタンをマウスでクリックするとする。当該選択ボタンのクリックに応じて、近似パターン表現式判定プログラムが走り、図１０Ｆに示すサブウィンドウ（１０２３）が表示される。
【０２１６】
また、図１０Ｄは、図１１Ｄに示す有限オートマトン（１１０４）のバリエーション・パターン（１００５）、及び現時点での正規表現候補（１００４）を示す。現時点での正規表現候補（１００４）は、図１０Ｄに示すバリエーション・パターン（１００５）中の場所<1>及び<2>をそれぞれフォーカスした際に、それぞれに適用可能な近似パターン表現式（１００６）  <prim>  及び  <prim>  で推論した場合の正規表現候補を示す。
【０２１７】
図１０Ｅは、図１０Ｄに示すバリエーション・パターン（１００５）のうち場所<1>をフォーカスした際のバリエーション・パターン（１０４１）、及び、現在の近似パターン表現式ストア（１０４２）中にある近似パターン表現式  <prim>  、及び、  <choice>  を示す。
バリエーション・パターン（１０４１）中の場所<1>がフォーカスされている場合に、当該場所<1>において適用可能な近似パターン表現式を判定する処理は下記の通りである。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（１０４２）中の近似パターン表現式  <prim>  （１０４２−１）及び  <choice>  （１０４２−２）を候補とする。場所<1>がまとめている部分文字列集合の全てにマッチする近似パターン表現式が近似パターン表現式ストア（１０４２）中に格納されていないので候補とされない。
ステップ２：表現式生成部（２０３）は、場所<1>部分を(.*)で置き換えて得られる正規表現  Sc(.*)>.xls  をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（１０４２）中の基本関数に対応する近似パターン表現式（１０４２−１、１０４２−２）に対して正規表現でreg_vをマッチさせる。しかし、いずれの近似パターン表現式も、正規表現  
Sc(.*)>.xls  に一致しない。よって、場所<1>に適用可能な近似パターン表現式は、上記  <prim>  及び  <choice>  のみである。従って、表示部（２０６）は、上記場所<1>の部分の近似パターン表現式の候補として、近似パターン表現式  <prim>  及び  <choice>  の２種類のみを画面上に表示する（図１０Ｆを参照）。
【０２１８】
図１０Ｆは、図１０Ｅに示すバリエーション・パターン（１００５）のうち場所<1>をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
具体的には、図１０Ｆは、場所<1>に適用可能な近似パターン表現式が、  <prim>  又は  <choice>  であることを示す（１０２５）。また、図１０Ｆは、場所<1>に適用可能な近似パターン表現式それぞれに対応する正規表現（すなわち近似結果）を示す。ユーザは、場所<1>に適用可能な近似パターン表現式（１０２５）のいずれか一つを選択可能である。
【０２１９】
ユーザが近似パターン表現式  <prim>  を選択したいとする。ユーザは、近似パターン表現式  <prim>  の左横にある選択ボタンをマウスでクリックし、さらにＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、選択された近似パターン表現式  <prim>  に対応する正規表現を一部に含む正規表現候補（１００４）が、図１０Ｇに示すようにウィンドウ（１００１）上に表示される。
【０２２０】
ユーザは、場所<2>についても同様にして、当該場所<2>に適用可能な近似パターン表現式として  <prim>  を選択したとする（図示せず）。そうすると、場所<2>の部分を近似パターン表現式  <prim>  による正規表現推論関数で推論することによって得られる正規表現を一部に含む正規表現候補（１００４）が、ウィンドウ（１００１）上に表示される。
【０２２１】
図１０Ｇは、図１０Ｃに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア（１０４２）中に保存するための処理を示す画面例である。
具体的には、図１０Ｇは、操作Ｓ（ｋ＝２４）（図１０Ｂ）そして操作Ｔ（１回目）（図１０Ｃ）を行うことによって生成された有限オートマトンから得られたバリエーション・パターンに対して、当該バリエーション・パターン中の場所<1>及び<2>それぞれに近似パターン表現式  <prim>  を適用して（<1> = <prim>，<2> = <prim>）得られる近似パターン表現式を近似パターン表現式ストア（１０４２）中に保存する。
【０２２２】
ユーザが、場所<1>に近似パターン表現式  <prim>  を適用した近似パターン表現式  
Sc1<prim>>.xls  を近似パターン表現式ストア（１０４２）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１０Ｈに示すサブウィンドウ（１０２６）が表示される。
【０２２３】
また、ユーザが、場所<2>に近似パターン表現式  <choice>  を適用した近似パターン表現式  Rp<prim>>.ppt  を近似パターン表現式ストア（１０４２）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１０Ｈに示すサブウィンドウ（１０２６）が表示される。
【０２２４】
図１０Ｈは、図１０Ｆにおける近似パターン表現式を近似パターン表現式ストア（１０４２）に格納する画面例、及び近似パターン表現式を編集する処理を示す画面例である。
【０２２５】
サブウィンドウ（１０２６Ａ）は、図１０Ｇの近似パターン表現式  Sc1<prim>>.xls  を近似パターン表現式ストア（１０４２）中に格納する例を示す。
ユーザは、近似パターン表現式  Sc1<prim>>.xls  をファイルとして保存するために近似パターン表現式ファイル名を入力する。または、コンピュータ（２０１）は、近似パターン表現式ファイル名を近似パターン表現式から自動的に求めて、近似パターン表現式ファイル名として予め表示しうる。
また、ユーザは、近似パターン表現式  Sc1<prim>>.xls  を編集することが可能である（１０２９Ａ）。編集後に、ユーザは、当該編集後の近似パターン表現式を近似パターン表現式ストア（１０４２）中に保存しうる。
ユーザは、上記近似パターン表現式を保存する場合、マウスで保存ボタンをクリックしうる。当該保存ボタンのクリックに応じて、近似パターン表現式  Sc1<prim>>.xls  が近似パターン表現式ストア（１０４２）中に格納される。
【０２２６】
サブウィンドウ（１０２６Ｂ）は、図１０Ｇの近似パターン表現式  Rp<prim>>.ppt  を近似パターン表現式ストア（１０４２）中に格納する例を示す。
ユーザは、近似パターン表現式  Rp<prim>>.ppt  をファイルとして保存するために近似パターン表現式ファイル名を入力する。または、コンピュータ（２０１）は、近似パターン表現式ファイル名を近似パターン表現式から自動的に求めて、近似パターン表現式ファイル名として予め表示しうる。
また、ユーザは、近似パターン表現式  Rp<prim>>.ppt  を編集することが可能である（１０２９Ｂ）。編集後に、ユーザは、当該編集後の近似パターン表現式を近似パターン表現式ストア（１０４２）中に保存しうる。
ユーザは、近似パターン表現式を保存する場合、マウスで保存ボタンをクリックしうる。当該保存ボタンのクリックに応じて、近似パターン表現式  Rp<prim>>.ppt  が近似パターン表現式ストア（１０４２）中に格納される。
【０２２７】
図１０Ｊは、図１１Ｄに示す有限オートマトン（１１０４）に操作Ｔ（２回目）の抽象化処理を開始するための操作を示す画面例である。
状態（１００３）中の黒印は、直前に終えた処理である操作Ｔの抽象化処理（ステップ４）の位置を示す。図１０Ｊにおいて、最初の有限オートマトンに操作Ｓが適用され、次に操作Ｔ（黒丸）が適用されていることを示す。当該黒丸の右方向にある白丸は、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
【０２２８】
ユーザが有限オートマトン（１１０４）に操作Ｔの抽象化処理を適用したいとする。ユーザは、状態（１００３）中の上記黒丸の右隣にある白丸をマウスでクリックし、有限オートマトン（１１０４）に操作Ｔの抽象化処理を開始することをコンピュータ（２０１）に指示する。
【０２２９】
第２の生成部（２０２−２）は、上記操作Ｔの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１１０４）に対して操作Ｔの抽象化処理を行う。第２の生成部（２０２−２）は、操作Ｔの抽象化処理によって図１１Ｄに示す有限オートマトン（１１０４）中の状態を除去し、エッジをマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ４の処理）。図１１Ｅは、当該ステップ４の２回目の処理によって生成される有限オートマトン（１１０５）を示す。
【０２３０】
図１０Ｋは、図１０Ｊに示す操作Ｔの抽象化処理から生成された有限オートマトン（１１０５）から正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の場所<1>及び場所<2>にそれぞれ適用可能な近似パターン表現式を判定するための操作を示す画面例である。
ユーザは、バリエーション・パターン（１００５）中の場所<k>をフォーカスした際に適用可能な近似パターン表現式を、図９Ａに記載のフローチャートに従い判定する処理を開始するために、近似パターン表現式の選択というボタンをマウスでクリックする。図１０Ｋでは、バリエーション・パターン（１００５）中に場所<1>及び場所<2>があることを示し、当該場所<1>及び<2>いずれにおいても、デフォルトの近似パターン表現式として指定されている  <prim>  が表示されている。
【０２３１】
ユーザが場所<1>に適用可能な近似パターン表現式を判定する処理を開始するために、場所<1>に関連付けられた選択ボタンをマウスでクリックするとする。当該選択ボタンのクリックに応じて、近似パターン表現式判定プログラムが走り、図１０Ｍに示すサブウィンドウ（１０３０）が表示される。
【０２３２】
また、図１０Ｋは、図１１Ｅに示す有限オートマトン（１１０５）のバリエーション・パターン（１００５）、及び現時点での正規表現候補（１００４）を示す。現時点での正規表現候補（１００４）は、図１０Ｋに示すバリエーション・パターン（１００５）中の場所<1>及び<2>をフォーカスした際にそれぞれ適用可能な近似パターン表現式（１００６）  <prim>  及び  <prim>  で推論した場合の正規表現候補を示す。
【０２３３】
図１０Ｌは、図１０Ｋに示すバリエーション・パターン（１００５）のうち場所<1>をフォーカスした際のバリエーション・パターン（１０４３）、及び、現在の近似パターン表現式ストア（１０４４）中にある近似パターン表現式を示す。
バリエーション・パターン（１０４３）中の場所<1>がフォーカスされている場合に、当該場所<1>において適用可能な近似パターン表現式を判定する処理は下記の通りである。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（１０４４）中の近似パターン表現式  <prim>  （１０４４−１）及び<choice>（１０４４−２）を候補とする。なお、近似パターン表現式ストア（１０４４）は、図１０Ｅに示す近似パターン表現式ストア（１０４２）に、図１０Ｈに示す処理によって追加された近似パターン表現式  Sc1<prim>>.xls  及び近似パターン表現式  Rp<prim>>.ppt  が追加されたものである。
ステップ２：表現式生成部（２０３）は、場所<1>部分を(.*)で置き換えて得られる正規表現  Sc1(.*)>.xls  をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（１０４４）中の基本関数に対応しない近似パターン表現式（１０４４−３、１０４４−４）に対して正規表現でreg_vをマッチさせる。その結果、図１０Ｇに示した格納操作によって近似パターン表現式ストア（１０４２）中に格納した近似パターン表現式の２つ（１０４４−３、１０４４−４）のうち、  Sc1<prim>>.xls  （１０４４−３）が、上記正規表現  
reg_v  にマッチする。
ステップ４：表現式生成部（２０３）は、マッチが成功した近似パターン表現式  Sc1<prim>>.xls  （Pi）について、reg_vの場所<1>に対応する(.*)部分でキャプチャリングされた部分パターン  1<prim>  をPsub_iとする。
ステップ５：表現式生成部（２０３）は、近似パターン表現式  1<prim>  が、A0_LiDiSc<AA  にマッチせず、且つ、11_InSc<EF30  及び  12_ItIpSc＜EG43  にマッチするので、近似パターン表現式  1<prim> | <choice>  が適用可能であると判定する。従って、表示部（２０６）は、上記<1>の部分の近似パターン表現式の候補として、近似パターン表現式  <prim>  及び  <choice>  、並びに、近似パターン表現式  1<prim> | <choice>  の３種類を画面上に表示する（図１０Ｍを参照）。
【０２３４】
図１０Ｍは、図１０Ｌに示すバリエーション・パターン（１００５）のうち場所<1>をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
具体的には、図１０Ｍは、場所<1>に適用可能な近似パターン表現式が  <prim>  、  <choice>  又は  1<prim> | <choice>  の３種類であることを示す（１０３２）。また、図１０Ｍは、場所<1>に適用可能な近似パターン表現式それぞれに対応する正規表現（すなわち近似結果）を示す。ユーザは、場所<1>に適用可能な近似パターン表現式（１０３２）のいずれか一つを選択可能である。
【０２３５】
ユーザが近似パターン表現式  1<prim> | <choice>  を選択したいとする。ユーザは、近似パターン表現式  1<prim> | <choice>  の左横にある選択ボタンをマウスでクリックし、さらにＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、選択された近似パターン表現式  1<prim> | <choice>  に対応する正規表現を含む正規表現候補（１００４）がウィンドウ（１００１）上に表示される。
【０２３６】
ユーザは、場所<2>についても同様にして、当該場所<2>に適用可能な近似パターン表現式として<prim>を選択したとする（図示せず）。そうすると、場所<2>の部分を近似パターン表現式  <prim>  による正規表現推論関数で推論することによって得られる正規表現を一部に含む正規表現候補（１００４）が、ウィンドウ（１００１）上に表示される。
【０２３７】
図１０Ｎは、図１０Ｊに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア（１０４４）中に保存するための処理を示す画面例である。
具体的には、図１０Ｎは、操作Ｓ（ｋ＝２４）（図１０Ｂ）そして操作Ｔ（１回目）（図１０Ｃ）及び操作Ｔ（２回目）（図１０Ｊ）を行うことによって生成された有限オートマトンから得られたバリエーション・パターンに対して、当該バリエーション・パターン中の場所<1>に近似パターン表現式  1<prim> | <choice>  を適用して（ <1> = 1<prim> | <choice>   ）得られる近似パターン表現式を近似パターン表現式ストア（１０４４）中に保存する。
【０２３８】
ユーザが、場所<1>に近似パターン表現式  1<prim> | <choice>  を適用した近似パターン表現式  Sc(1<prim> | <choice>)>.xls  を近似パターン表現式ストア（１０４４）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１０Ｈに示すサブウィンドウ（１０２６）と同様のサブウィンドウ（図示せず）が表示部（２０６）上に表示される。ユーザは、近似パターン表現式を保存する場合、マウスで保存ボタン（図示せず）をクリックする。当該保存ボタンのクリックに応じて、近似パターン表現式  Sc(1<prim> | <choice>)>.xls  が近似パターン表現式ストア（１０４４）中に近似パターン表現式として格納される。
また、ユーザは、近似パターン表現式  Sc(1<prim> | <choice>)>.xls  を編集することが可能である。編集後に、ユーザは、当該編集後の近似パターン表現式を近似パターン表現式ストア（１０４４）中に保存しうる。
【０２３９】
図１０Ｐは、図１１Ｅに示す有限オートマトン（１１０５）に操作Ｔ（３回目）の抽象化処理を開始するための操作を示す画面例である。
状態（１００３）中の黒印は、直前に終えた処理である操作Ｔの抽象化処理（ステップ４）の位置を示す。図１０Ｐにおいて、最初の有限オートマトンに操作Ｓが適用され、次に操作Ｔ（白丸）、そしてさらに操作Ｔ（黒丸）が適用されていることを示す。当該黒丸の右方向にある白丸は、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
【０２４０】
ユーザが有限オートマトン（１１０５）に操作Ｔの抽象化処理を適用したいとする。ユーザは、状態（１００３）中の上記黒丸の右隣にある白丸をマウスでクリックし、有限オートマトン（１１０５）に操作Ｔの抽象化処理を開始することをコンピュータ（２０１）に指示する。
【０２４１】
第２の生成部（２０２−２）は、上記操作Ｔの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１１０５）に対して操作Ｔの抽象化処理を行う。第２の生成部（２０２−２）は、操作Ｔの抽象化処理によって図１１Ｅに示す有限オートマトン（１１０５）中の状態を除去し、エッジをマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ４の処理）。図１１Ｆは、当該ステップ４の３回目の処理によって生成される有限オートマトン（１１０６）を示す。
【０２４２】
図１０Ｑは、図１０Ｐに示す操作Ｔの抽象化処理から生成された有限オートマトン（１１０５）から正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の場所<1>に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
ユーザは、バリエーション・パターン（１００５）中の場所<k>をフォーカスした際に適用可能な近似パターン表現式、図９Ａに記載のフローチャートに従い判定する処理を開始するために、近似パターンの選択というボタンをマウスでクリックする。図１０Ｑでは、バリエーション・パターン（１００５）中に場所<1>があることを示し、当該場所<1>において、近似パターン表現式  1<prim> | <choice>  が表示されている。
【０２４３】
ユーザが場所<1>に適用可能な近似パターン表現式を判定する処理を開始するために、場所<1>に関連付けられた選択ボタンをマウスでクリックするとする。当該選択ボタンのクリックに応じて、近似パターン表現式判定プログラムが走り、図１０Ｓに示すサブウィンドウ（１０３４）が表示される。
【０２４４】
また、図１０Ｑは、図１１Ｆに示す有限オートマトン（１１０６）のバリエーション・パターン（１００５）、及び現時点での正規表現候補（１００４）を示す。
【０２４５】
図１０Ｒは、図１０Ｑに示すバリエーション・パターン（１００５）のうち場所<1>をフォーカスした際のバリエーション・パターン（１０４５）、及び、現在の近似パターン表現式ストア（１０４６）中にある近似パターン表現式を示す。
バリエーション・パターン（１０４５）中の場所<1>がフォーカスされている場合に、当該フォーカスされた場所<1>において適用可能な近似パターン表現式を判定する処理は下記の通りである。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（１０４６）中の基本関数  <prim>  （１０４６−１）及び  <choice>  （１０４６−２）を候補とする。なお、近似パターン表現式ストア（１０４６）は、図１０Ｌに示す近似パターン表現式ストア（１０４４）に、図１０Ｎに示す処理によって追加された近似パターン表現式  Sc(1<prim> | <choice>).xls  が追加されたものである。
ステップ２：表現式生成部（２０３）は、Var-Pattern中の<1>部分を(.*)で置き換えて得られる正規表現  (.*)  をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（１０４６）中の近似パターン表現式（１０４６−１、１０４６−２、１０４６−３、１０４６−４、１０４６−５）に対して正規表現でreg_vをマッチさせる。その結果、図１０Ｇ及び図１０Ｎにそれぞれ示した格納操作によって格納された近似パターン表現式の３つ（１０４６−３、１０４６−４、１０４６−５）の全てが、上記正規表現  reg_v  にマッチする。
ステップ４：表現式生成部（２０３）は、マッチが成功した近似パターン表現式、  Sc1<prim>>.xls  、  Rp<prim>>.ppt  、  Sc(1<prim> | <choice>)>.xls  について、reg_vの場所<1>に対応する(.*)部分でキャプチャリングされた部分パターン  Sc1<prim>>.xls  、  Rp<prim>>.ppt  、  Sc(1<prim> | <choice>) .xls  をPsub_iとする。
ステップ５：表現式生成部（２０３）は、上記載したPsub_iが、Sc11_InS<EF30>.xls  、  Sc12_ItIpSc<EG43>.xls  、  ScA0_LiDiSc<AA>.xls  、  Rp801_NwCIForm<FA03>.ppt  、  Rp9d3_OrForm<FP51>.ppt  の一部にマッチし且つ一部にマッチしないので、近似パターン表現式  Sc1<prim>>.xls | <choice>  、Rp<prim>>.ppt | <choice>  、  Sc1<prim> | <choice>)>.xls  が適用可能であると判定する。例えば、Sc1<prim>>.xls  は最初の２つにマッチして、残りの２つにマッチしない。よって、マッチしないPsub_iがあるので、近似パターン表現式中に<choice>が付けられる。従って、表示部（２０６）は、上記<1>の部分の近似パターン表現式の候補として、近似パターン表現式  <prim>  及び  <choice>  、並びに、近似パターン表現式  Sc1<prim>>.xls| <choice>  、  Rp<prim>>.ppt | <choice>  、  Sc(1<prim> |<choice>)>.xls | <choice>  の５種類を画面上に表示する（図１０Ｓを参照）。
【０２４６】
図１０Ｓは、図１０Ｒに示すバリエーション・パターン（１０４５）のうち場所<1>をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
具体的には、図１０Ｓは、場所<1>に適用可能な近似パターン表現式が、  <prim>  及び  <choice>  、  Rp<prim>>.ppt | <choice>  、  Sc1<prim>>.xls | <choice>  及び  Sc(1<prim> | <choice>)>.xls | <choice>であることを示す（１０３６）。また、図１０Ｓは、場所<1>に適用可能な近似パターン表現式それぞれに対応する正規表現（すなわち近似結果）を示す。ユーザは、場所<1>に適用可能な近似パターン表現式（１０３６）のいずれか一つを選択可能である。
【０２４７】
しかしながら、上記５種類のうちに、ユーザが所望する近似パターン表現式がなかったとする。その場合には、ユーザは、サブウィンドウ（１０３４）内の「近似パターン表現式の作成」のボタンを、マウスでクリックしてＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、ユーザは、マニュアル的に近似パターン表現式を入力して追加することができる（画面省略）。また、ユーザは、必要に応じて、不要な近似パターン表現式を削除しうる（画面省略）。
【０２４８】
図１０Ｔは、図１０Ｒに示すバリエーション・パターン（１００５）中の場所<1>をフォーカスした際に適用可能である近似パターン表現式の例であり、ユーザが所望する近似パターン表現式が追加された近似パターン表現式が選択可能であることを示す画面である。
図１０Ｔに示す近似パターン表現式では、図１０Ｓに示した近似パターン表現式と比べて、近似パターン表現式  Sc(1<prim> | <choice>)>.xls | <prim>  がユーザによって新たに追加されている。
【０２４９】
ユーザが近似パターン表現式  Sc(1<prim> | <choice>)>.xls | <prim>  を選択したいとする。ユーザは、近似パターン表現式  Sc1(<prim> | <choice>)>.xls | <prim>  の左横にある選択ボタンをマウスでクリックし、ＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、選択された近似パターン表現式  Sc(1<prim> | <choice>)>.xls | <prim>  に対応する正規表現を一部に含む正規表現候補（１００４）が、図１０Ｕに示すようにウィンドウ（１００１）上に表示される。
【０２５０】
図１０Ｕは、図１０Ｐに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア（１０４６）中に保存するための処理を示す画面例である。
具体的には、図１０Ｕは、操作Ｓ（ｋ＝２４）（図１０Ｂ）、操作Ｔ（１回目）（図１０Ｃ）、操作Ｔ（２回目）（図１０Ｊ）、そして操作Ｔ（３回目）（図１０Ｐ）を行うことによって生成された有限オートマトンから得られたバリエーション・パターンに対して、当該バリエーション・パターン中の場所<1>に近似パターン表現式  Sc(1<prim> | <choice>)>.xls |<prim>  を適用して（  <1> = <Sc(1<prim> | <choice>)>.xls | <prim>  ）得られる近似パターン表現式を近似パターン表現式ストア（１０４６）中に保存する。
【０２５１】
ユーザが、近似パターン表現式を近似パターン表現式ストア（１０４６）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１０Ｈに示すサブウィンドウ（１０２６）と同様のサブウィンドウ（図示せず）が表示部（２０６）上に表示される。ユーザは、近似パターン表現式を保存する場合、マウスで保存ボタン（図示せず）をクリックしうる。当該保存ボタンのクリックに応じて、近似パターン表現式  Sc(1<prim> | <choice>)>.xls | <prim>  が近似パターン表現式ストア（１０４６）中に格納されうる（図１０Ｖの１０４８を参照）。なお、近似パターン表現式  Sc(1<prim> | <choice>)>.xls | <prim>  が、図１０Ｔに示す近似パターン表現式のユーザによる追加処理によって既に近似パターン表現式ストア（１０４６）中に保存されているので、コンピュータ（２０１）は、例えば、同じ近似パターン表現式が近似パターン表現式ストア（１０４６）中に既にあることのエラー・メッセージ、又は、近似パターン表現式ストア（１０４６）中に既にある同じ近似パターン表現式のファイルを上書きすることの確認メッセージを表示しうる。
【０２５２】
図１０Ｖは、実施例１の抽象化処理によって作成された現在の近似パターン表現式ストア（１０４８）中に格納された近似パターン表現式を、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理においても再利用可能であることを示す画面例である。
近似パターン表現式ストア（１０４８）には、実施例１の抽象化処理によって基本関数に対応する近似パターン表現式である  <prim>  及び  <choice>  以外の近似パターン表現式が追加されている。当該追加された近似パターン表現式は、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理においても再利用可能である。
【０２５３】
図１２Ａ及び図１２Ｂは、本発明の実施態様に従い、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように推論するための処理において、ユーザと対話的に正規表現を推論するためのインタラクション機能を示す。
上記インタラクション機能には、機能Ａ〜Ｄがある。以下に、機能ＡからＤについてそれぞれ説明する。
【０２５４】
機能Ａは、ユーザに提示された「正規表現候補」をみて、（１）段階的な抽象化手順（操作Ｓ又は操作Ｔ）、及び、（２）バリエーション・パターン中の場所<k>（近似対象部分）に適用する近似パターン表現式を選択し又は指定することを可能にする機能である。
機能Ａにおいて、ユーザ入力１は、操作Ｓのパラメータk(k-bound のk、同一とみなす長さ）、又は、操作Ｔのパラメータｎ（操作Ｔの繰り返し回数）であり、ユーザ入力２は、近似対象部分に適用する近似パターン表現式である。デフォルトの近似パターン表現式は、正規表現推論関数の基本関数であるprimに対応する近似パターン表現式  <prim>  でありうる。
機能Ａの処理において、現在の有限オートマトンに対して、操作Ｓをk（ユーザ入力１）を使用して実行し、次に操作Ｔをｎ回（ユーザ入力１）実行し、そして操作Ｔの各段階で得られるバリエーション・パターン中の近似対象部分に近似パターン表現式（ユーザ入力２）を適用することによって、正規表現候補が得られる。
【０２５５】
機能Ｂは、ユーザに提示された「近似対象部分が明示されたバリエーション・パターン」に適用する近似パターン表現式を近似対象部分ごとに選択し又は指定することを可能にする機能である。
機能Ｂにおいて、ユーザ入力は、近似対象部分に適用する近似パターン表現式α1, α2，．．．である。
機能Ｂの処理において、近似対象部分がユーザに提示されるので、各近似対象部分に対して、選択又は指定された近似パターン表現式α1, α2，．．．が適用される。
【０２５６】
機能Ｃは、段階的に推論してき近似パターン表現式に対して又は特定の手順で推論される近似パターン表現式に対して、特定の条件で検索することを可能にする機能である。
機能Ｃにおいて、ユーザ入力は、操作Ｓの手順（kを含む）、操作Ｔの手順（パラメータｎを含む）、近似パターン表現式、近似対象部分の正規表現reg、又はバリエーション・パターンの個数ｎ（ｎは整数）である。
機能Ｃの処理は、指定手順で段階的に推論を行っていく際に推論される正規表現の集合に対して、現在の部分式に正規表現regを持つ部分表現を検索すること（例えば、図１０Ｄに示す  <[A-Z][A-Z]\d\d>  を一部に持つ正規表現を探すこと）、又は、バリエーション・パターンの個数がｎ以下である表現を検索することである。
【０２５７】
機能Ｄは、ユーザに提示された正規表現の特定部分を固定して（例えば、図１０Ｄに示す  <[A-Z][A-Z]\d\d>  の部分を固定）の有限オートマトンの抽象化又は具体化を行う処理である。有限オートマトンの抽象化又は具体化行うことは、正規表現の抽象化又は具体化につながる。正規表現の具体化とは、例えば、図１０Ｄに示す  <[A-Z][A-Z]\d\d>  の部分を<[A-Z][A-Z](3|4|5)(0|3|1)と具体化することである。
機能Ｄにおいて、ユーザ入力は、正規表現の固定された特定部分、又はその手順、例えば操作Ｓの手順（kを含む）、操作Ｔの手順（パラメータｎを含む）、近似パターン表現式である。
機能Ｄの処理は、ユーザによって指定された正規表現中のある部分を固定した上で、ユーザによって入力された手順に従い、抽象化又は具体化する機能である。
【０２５８】
図１２Ａは、機能Ａ及びＢの一例を示す。
【０２５９】
画面（１２０１）は、バリエーション・パターン（１２０１）を示す。バリエーション・パターン（１２０１）は、２つのバリエーション・パターンを示しており、各バリエーション・パターンは、その中に近似対象部分<1>及び<2>、並びに<3>及び<4>を有している。対話機能実現部（図示せず）は、<1>，<2>，<3>，<4>を近似する近似パターン表現式を選択又は入力するようにユーザに促す。対話機能実現部は、例えば、「<1>，<2>，<3>，<4>に適用する近似パターン表現式を指定してください。」というメッセージを表示部（２０６）上に表示する。当該メッセージは、機能Ｂに対応する。
ユーザは、上記メッセージに対して、<1>，<2>，<3>及び<4>について、例えば、近似パターン表現式のリストから適用したい近似パターン表現式を選択し、又は近似パターン表現式を入力することが可能である。ユーザが、<1>，<2>，<3>及び<4>の全てについて、近似パターン表現式  <prim>  を選択したとする。
【０２６０】
画面（１２０２）は、<1>，<2>，<3>及び<4>の全てに、近似パターン表現式  <prim>  を適用することによって得られる正規表現候補[RegExp]を示す。また、画面（１２０２）は画面（１２０２）に示されているバリエーション・パターンと同じバリエーション・パターンを示す。対話機能実現部は、例えば、「抽象化ステップ＝？、適用可能な近似パターン表現式＝？」というメッセージを表示部（２０６）上に表示する。当該メッセージは、機能Ａに対応する。
ユーザは、上記メッセージに対して、「操作=T(1)」、及び、近似パターン表現式  <prim>  を選択又は入力したとする。「操作=T(1)」は、抽象化処理を操作Ｔで１回行うということを意味する。
【０２６１】
画面（１２０３）は、画面（１２０２）に記載のバリエーション・パターンに対応する有限オートマトンに操作Ｔを１回して得られる有限オートマトンに対応するバリエーション・パターン、及び、当該操作Ｔの適用によって得られる有限オートマトンに対応するバリエーション・パターン中の近似対象部分に近似パターン表現式  <prim>  を適用することによって得られる正規表現を示す。
【０２６２】
図１２Ｂは、機能Ｃ及びＤの一例を示す。
図１２Ｂの符号１２１１は、操作Ｓ及び操作Ｔを用いて抽象化中（推論中）の有限オートマトン履歴を示す。「部分文字列の並びに基づくマージ」とは操作Ｓを意味し、「部分文字列の出現位置に基づくマージ」とは操作Ｔを意味する。ＦＡは、有限オートマトンである。
図１２Ｂの符号１２１２は、有限オートマトン履歴（１２１１）に対応する推論された正規表現ストアを意味する。
正規表現ストア（１２１２）中の矢印（１２２１）は、機能Ｃを用いてユーザが特定の部分表現を指定し、そして当該指定された特定の部分表現を持つ正規表現を全て求めることを示す。ＲＥ（１２３２、１２３３、及び１２３４）は、求められた正規表現を示す。
正規表現ストア（１２１２）中の矢印（１２３１）は、機能Ｄを用いてユーザが特定の部分表現を固定し、そして当該固定された部分表現から戻ることを示す。
【０２６３】
図１３は、本発明の実施態様である実施例１を例として、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように対話的に処理した場合に生成される各正規表現を示す。
画面（１３０１）は、入力文字列の集合を示す。当該入力文字列の集合は、図１０Ａに示すサブウィンドウ（１０２２）内に表示された入力文字列の集合と同じである。
画面（１３０２）は、本発明の実施態様に従い操作Ｓ、次に操作Ｔで抽象化した場合に得られるバリエーション・パターン[Var-Pattern]、及び当該バリエーション・パターン中の近似対象部分すべてに近似パターン表現式  <prim>  を適用して得られる正規表現
[Reg-Exp]を示す。画面（１３０２）で示される正規表現は、Sc<数字>，Sc<英字>，Rpで始まる文字列を区別して処理するための正規表現である。
画面（１３０３）は、本発明の実施態様に従いさらに１段階操作Ｔで抽象化した場合に得られるバリエーション・パターン、及び当該バリエーション・パターン中の近似対象部分すべてに近似パターン表現式を適用して得られる正規表現[Reg-Exp]を示す。なお、画面（１３０３）に示すバリエーション・パターンは、実施例１における操作Ｔによる抽象化処理と異なる方法（適用される近似パターン表現式が異なる）で抽象化した一例である。画面（１３０３）で示される正規表現は、例えば、フォルダ中のファイルを文字列
「Sc」及び「Rp」によって振り分けて処理するためのものでありうる。
画面（１３０４）は、本発明の実施態様に従い、画面（１３０３）で実現されている正規表現の推論方法を表している近似パターン表現式である。当該近似パターン表現式は、画面（１３０１）に示す文字列集合から画面（１３０３）に示す[Reg-Exp]に表示されている正規表現を推論する方法を表現している近似パターン表現式（すなわち、正規表現推論関数）を構築したものである。当該近似パターン表現式は、画面（１３０１）に示される入力文字列の集合以外の入力文字列の集合を抽象化する際に再利用されうる。
【０２６４】
図１４は、本発明の実施態様に従い、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように対話的に処理した場合の各正規表現パターンを示す。
画面（１４０１）は、入力文字列の集合を示す。当該入力文字列は、入力文字列の集合は、図４に示す入力文字列の集合（４１１）と同じである。
画面（１４０２）は、本発明の実施態様に従い操作Ｓ、次に操作Ｔで抽象化した場合に得られるバリエーション・パターン[Var-Pattern]、及び当該バリエーション・パターン中の近似対象部分すべてに近似パターン表現式  <prim>  を適用して得られる正規表現
[Reg-Exp]を示す。画面（１４０２）で示される正規表現は、例えば、フォルダ中のファイルの分類による個別ファイル処理の自動化のための正規表現でありうる。
画面（１４０３）は、本発明の実施態様に従いさらに１段階操作Ｔで抽象化した場合に得られるバリエーション・パターン、及び当該バリエーション・パターン中の近似対象部分すべてに近似パターン表現式を適用して得られる正規表現[Reg-Exp]を示す。画面（１４０３）で示される正規表現は、例えば、フォルダ中のファイル（例えばテストケースとその説明文書）が対象とするデータ形式（XLS,PDF,CSV）を取り出す処理のための正規表現でありうる。
画面（１４０４）は、本発明の実施態様に従い、画面（１４０３）で実現されている正規表現の推論方法を表している近似パターン表現式である。当該近似パターン表現式は、画面（１４０１）に示す文字列集合から画面（１４０３）に示す[Reg-Exp]に表示されている正規表現を推論する方法を表現している近似パターン表現式（すなわち、正規表現推論関数）を構築したものである。当該近似パターン表現式は、画面（１４０１）に示される入力文字列の集合以外の入力文字列の集合を抽象化する際に再利用されうる。
【０２６５】
実施例２
入力文字列（日本語（漢字及びカタカナ）、英語及び数字の文字列からなるファイル名）の集合を近似パターン表現式に段階的に変換する各処理を、図１５Ａ〜図１５Ｕに示す画面例を用いて説明する。図１６Ａ〜図１６Ｆは、当該実施例１中において生成される各有限オートマトンを示す。また、図１５Ｖは、実施例１の処理によって正規表現推論関数ストア（２１５）に格納された正規表現推論関数を、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理において再利用可能であることを示す画面例である。
【０２６６】
図１５Ａは、文字列集合を入力し、当該文字列集合から最初の１つの有限オートマトンを生成する処理を開始するための画面例である。
ユーザは、例えば、文字列集合（２１２）を含むファイルを記憶装置（２１１）から読み出す指示をコンピュータ（２０１）に送る（図示せず）。当該指示に応じて、第１の生成部（２０２−１）は、文字列集合（２１２）を含む上記ファイルを記憶装置（２１１）から読み出す（ステップ１の処理）。そして、表示部（２０６）は、当該読み出した文字列集合（２１２）をその画面上の所定のサブウィンドウ（１５２２）内に表示する。図１５Ａの例では、入力文字列の集合の数は５である。当該文字列集合は、フォルダ中のファイル名の例である。ユーザは、入力文字列の集合を近似パターン表現式に変換する処理の開始を指示するために、ウィンドウ（１５２１）内の「開始」ボタンをクリックする。第１の生成部（２０２−１）は、ステップ１の処理で読み出した入力文字列の集合から１つの有限オートマトンをメモリ（１０３）内に生成する（ステップ２の処理）。図１６Ａは、当該ステップ２の処理によって生成された有限オートマトン（１６０１）を示す。
【０２６７】
図１５Ｂは、図１６Ａに示す有限オートマトン（１６０１）に操作Ｓの抽象化処理を開始するための操作を示す画面例である。
表示部（２０６）は、ウィンドウ（１５０１）内に、入力文字列の集合（１５０２）及びその集合の数である５、入力文字列の集合を近似パターン表現式に変換する処理の状態（１５０３）、並びに正規表現候補（１５０４）を表示する。
状態（１５０３）中の「起点」という文字で指し示す丸印は、当該実施例１での抽象化処理の起点（開始点）を示す。黒印は、直前に終えた抽象化処理の位置を示す。図１５Ｂにおいて、起点が黒丸になっていることから、最初の１つの有限オートマトン（１６０１）がすでに生成されていること、すなわちステップ２の処理が既に終了していることを示す。当該黒丸の下方向にある丸印は操作Ｓによる有限オートマトンの抽象化処理が可能であることを示す。なお、当該黒丸の右方向にある白丸（図１５Ｂでは図示されていない）がある場合には、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
図１５Ｂでは、当該黒丸（起点）から下方向に丸印が１つ示されている。この下方向にある白丸は、ユーザが、操作Ｓによる有限オートマトン（１６０１）の抽象化処理を選択することが可能であることを示す。
【０２６８】
ユーザが有限オートマトン（１６０１）に操作Ｓの抽象化処理を適用したいとする。ユーザは、状態（１５０３）中の上記白丸をマウスでクリックし、有限オートマトン（１６０１）に対して操作Ｓの抽象化処理を開始することを指示する。上記白丸の左隣の数字（２４）は、操作Ｓの最初の抽象化処理前においては、有限オートマトン（１６０１）の最長の入力文字列の数を表す。しかし、最初の操作Ｓの抽象化処理が終了した後は、kを最小の入力文字列の数から減少させるが最長の入力文字列の数を表すとは限らない。kが小さくなるほど、操作Ｓによって大きく抽象化されるので、kを段階的に減らすことにより段階的に抽象化されていることを示す。
【０２６９】
第３の生成部（２０２−３）は、上記操作Ｓの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１６０１）に対して操作Ｓの抽象化処理を行う。第３の生成部（２０２−３）は、操作Ｓの抽象化処理によって図１６Ａに示す有限オートマトン（１６０１）中の共通パスの状態（符号１６１１及び１６１２の部分）をマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ３の処理）。符号１６１１で示される共通パスは、>.xls  という共通のラベル列の集合を持つ。符号１６１３で示される共通パスは、>.ppt  という共通のラベル列の集合を持つ。図１６Ｂは、当該ステップ３の処理によって生成された有限オートマトン（１６０２）を示す。有限オートマトン（１６０２）において、共通パスが持つラベル列の集合が持つ遷移の集合、及び当該集合に含まれる状態の集合がマージされている（符号１６１１について「>.xls」、及び符号１６１２について「>.ppt」）。
【０２７０】
図１５Ｂにおいて正規表現候補は、入力文字列そのものと同じである。なぜならば、図１６Ａに示す有限オートマトン（１６０１）はまだ抽象化されていないからである。
【０２７１】
図１５Ｃは、図１６Ｂに示す有限オートマトン（１６０２）に操作Ｔ（１回目）の抽象化処理を開始するための操作を示す画面例である。
状態（１５０３）中の黒印は、直前に終えた処理である操作Ｓの抽象化処理（ステップ３）の位置を示す。図１５Ｃにおいて、起点直下の丸が黒丸になっていることから、最初の有限オートマトンに操作Ｓが適用されて縮退された有限オートマトンがすでに生成されていること、すなわちステップ３の処理が既に終了していることを示す。当該黒丸の下方向にある白丸は操作Ｓによる有限オートマトンの抽象化処理が可能であることを示し、当該黒丸の右方向にある白丸は、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
【０２７２】
ユーザが有限オートマトン（１６０２）に操作Ｔの抽象化処理を適用したいとする。ユーザは、状態（１５０３）中の上記黒丸の右隣にある白丸をマウスでクリックし、有限オートマトン（１６０２）に操作Ｔの抽象化処理を開始することをコンピュータ（２０１）に指示する。
【０２７３】
第２の生成部（２０２−２）は、上記操作Ｔの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１６０２）に対して操作Ｔの抽象化処理を行う。第２の生成部（２０２−２）は、操作Ｔの抽象化処理によって図１６Ｂに示す有限オートマトン（１６０２）中の状態を除去し、エッジをマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ４の処理）。図１６Ｃは、当該ステップ４の処理によって生成される有限オートマトン（図１６Ｄ、１６０４）の途中経過の有限オートマトン（１６０３）を示す。図１６Ｄは、当該ステップ４の処理（１回目）によって生成される有限オートマトン（１６０４）を示す。
【０２７４】
図１５Ｄは、図１５Ｃに示す操作Ｔの抽象化処理から生成された有限オートマトン（１６０４）から正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の場所<1>及び場所<2>にそれぞれ適用可能な近似パターン表現式を判定するための操作を示す画面例である。
表示部（２０６）は、図１５Ｃに示す操作Ｔの処理終了後に、ウィンドウ（１５０１）内に、入力文字列の集合（１５０２）及びその集合の数である「５」、入力文字列の集合を段階的に近似パターン表現式に変換する処理の状態（１５０３）、並びに正規表現候補（１５０４）に加えて、バリエーション・パターン（１５０５）及び当該バリエーション・パターン中の場所<k>に適用可能なデフォルトの近似パターン表現式（１５０６）を表示する。
【０２７５】
ユーザは、バリエーション・パターン（１５０５）中の場所<k>をフォーカスした際に適用可能な近似パターン表現式を、図９Ａに記載のフローチャートに従い判定する処理を開始するために、近似パターン表現式の選択というボタンをマウスでクリックする。図１５Ｄでは、バリエーション・パターン（１５０５）中に場所<1>及び場所<2>があることを示し、当該場所<1>及び<2>のいずれにおいても、デフォルトの近似パターン表現式として指定されている  <prim>  が最初に表示されている。なお、prim  は正規表現推論関数（の名前）であり、<prim>  は、近似パターン表現式である。
【０２７６】
ユーザが場所<1>に適用可能な近似パターン表現式を判定する処理を開始するために、場所<1>に関連付けられた選択ボタンをマウスでクリックするとする。当該選択ボタンのクリックに応じて、近似パターン表現式判定プログラムが走り、図１５Ｆに示すサブウィンドウ（１５２３）が表示される。
【０２７７】
また、図１５Ｄは、図１６Ｄに示す有限オートマトン（１６０４）のバリエーション・パターン（１５０５）、及び現時点での正規表現候補（１５０４）を示す。現時点での正規表現候補（１５０４）は、図１５Ｄに示すバリエーション・パターン（１５０５）中の場所<1>及び<2>をそれぞれフォーカスした際に、それぞれに適用可能な近似パターン表現式（１５０６）  <prim>  及び  <prim>  で推論した場合の正規表現候補を示す。
【０２７８】
図１５Ｅは、図１５Ｄに示すバリエーション・パターン（１５０５）のうち場所<1>をフォーカスした際のバリエーション・パターン（１５４１）、及び、現在の近似パターン表現式ストア（１５４２）中にある近似パターン表現式  <prim>  、及び、  <choice>  を示す。
バリエーション・パターン（１５４１）中の場所<1>がフォーカスされている場合に、当該場所<1>において適用可能な近似パターン表現式を判定する処理は下記の通りである。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（１５４２）中の近似パターン表現式  <prim>  （１５４２−１）及び  <choice>  （１５４２−２）を候補とする。場所<1>がまとめている部分文字列集合の全てにマッチする近似パターン表現式が近似パターン表現式ストア（１５４２）中に格納されていないので候補とされない。
ステップ２：表現式生成部（２０３）は、場所<1>部分を(.*)で置き換えて得られる正規表現  画面(.*)>.xls  をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（１５４２）中の基本関数に対応する近似パターン表現式（１５４２−１、１５４２−２）に対して正規表現でreg_vをマッチさせる。しかし、いずれの近似パターン表現式も、正規表現  画面(.*)>.xls  に一致しない。よって、場所<1>に適用可能な近似パターン表現式は、上記  <prim>  及び  <choice>  のみである。従って、表示部（２０６）は、上記場所<1>の部分の近似パターン表現式の候補として、近似パターン表現式  <prim>  及び  <choice>  の２種類のみを画面上に表示する（図１５Ｆを参照）。
【０２７９】
図１５Ｆは、図１５Ｅに示すバリエーション・パターン（１５０５）のうち場所<1>をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
具体的には、図１５Ｆは、場所<1>に適用可能な近似パターン表現式が、  <prim>  又は  <choice>  であることを示す（１５２５）。また、図１５Ｆは、場所<1>に適用可能な近似パターン表現式それぞれに対応する正規表現（すなわち近似結果）を示す。ユーザは、場所<1>に適用可能な近似パターン表現式（１５２５）のいずれか一つを選択可能である。
【０２８０】
ユーザが近似パターン表現式  <prim>  を選択したいとする。ユーザは、近似パターン表現式  <prim>  の左横にある選択ボタンをマウスでクリックし、さらにＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、選択された近似パターン表現式  <prim>  に対応する正規表現を一部に含む正規表現候補（１５０４）が、図１５Ｇに示すようにウィンドウ（１５０１）上に表示される。
【０２８１】
ユーザは、場所<2>についても同様にして、当該場所<2>に適用可能な近似パターン表現式として  <prim>  を選択したとする（図示せず）。そうすると、場所<2>の部分を近似パターン表現式  <prim>  による正規表現推論関数で推論することによって得られる正規表現を一部に含む正規表現候補（１５０４）が、ウィンドウ（１５０１）上に表示される。
【０２８２】
図１５Ｇは、図１５Ｃに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア（１５４２）中に保存するための処理を示す画面例である。
具体的には、図１５Ｇは、操作Ｓ（ｋ＝２４）（図１５Ｂ）そして操作Ｔ（１回目）（図１５Ｃ）を行うことによって生成された有限オートマトンから得られたバリエーション・パターンに対して、当該バリエーション・パターン中の場所<1>及び<2>それぞれに近似パターン表現式  <prim>  を適用して（<1> = <prim>，<2> = <prim>）得られる近似パターン表現式を近似パターン表現式ストア（１５４２）中に保存する。
【０２８３】
ユーザが、場所<1>に近似パターン表現式  <prim>  を適用した近似パターン表現式  画面１<prim>>.xls  を近似パターン表現式ストア（１５４２）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１５Ｈに示すサブウィンドウ（１５２６）が表示される。
【０２８４】
また、ユーザが、場所<2>に近似パターン表現式  <choice>  を適用した近似パターン表現式  帳票<prim>>.ppt  を近似パターン表現式ストア（１５４２）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１５Ｈに示すサブウィンドウ（１５２６）が表示される。
【０２８５】
図１５Ｈは、図１５Ｆにおける近似パターン表現式を近似パターン表現式ストア（１５４２）に格納する画面例、及び近似パターン表現式を編集する処理を示す画面例である。
【０２８６】
サブウィンドウ（１５２６Ａ）は、図１５Ｇの近似パターン表現式  画面１<prim>>.xls  を近似パターン表現式ストア（１５４２）中に格納する例を示す。
ユーザは、近似パターン表現式  画面１<prim>>.xls  をファイルとして保存するために近似パターン表現式ファイル名を入力する。または、コンピュータ（２０１）は、近似パターン表現式ファイル名を近似パターン表現式から自動的に求めて、近似パターン表現式ファイル名として予め表示しうる。
また、ユーザは、近似パターン表現式  画面１<prim>>.xls  を編集することが可能である（１５２９Ａ）。編集後に、ユーザは、当該編集後の近似パターン表現式を近似パターン表現式ストア（１５４２）中に保存しうる。
ユーザは、上記近似パターン表現式を保存する場合、マウスで保存ボタンをクリックしうる。当該保存ボタンのクリックに応じて、近似パターン表現式  画面１<prim>>.xls  が近似パターン表現式ストア（１５４２）中に格納される。
【０２８７】
サブウィンドウ（１５２６Ｂ）は、図１５Ｇの近似パターン表現式  帳票<prim>>.ppt  を近似パターン表現式ストア（１５４２）中に格納する例を示す。
ユーザは、近似パターン表現式  帳票<prim>>.ppt  をファイルとして保存するために近似パターン表現式ファイル名を入力する。または、コンピュータ（２０１）は、近似パターン表現式ファイル名を近似パターン表現式から自動的に求めて、近似パターン表現式ファイル名として予め表示しうる。
また、ユーザは、近似パターン表現式  帳票<prim>>.ppt  を編集することが可能である（１５２９Ｂ）。編集後に、ユーザは、当該編集後の近似パターン表現式を近似パターン表現式ストア（１５４２）中に保存しうる。
ユーザは、近似パターン表現式を保存する場合、マウスで保存ボタンをクリックしうる。当該保存ボタンのクリックに応じて、近似パターン表現式  帳票<prim>>.ppt  が近似パターン表現式ストア（１５４２）中に格納される。
【０２８８】
図１５Ｊは、図１６Ｄに示す有限オートマトン（１６０４）に操作Ｔ（２回目）の抽象化処理を開始するための操作を示す画面例である。
状態（１５０３）中の黒印は、直前に終えた処理である操作Ｔの抽象化処理（ステップ４）の位置を示す。図１５Ｊにおいて、最初の有限オートマトンに操作Ｓが適用され、次に操作Ｔ（黒丸）が適用されていることを示す。当該黒丸の右方向にある白丸は、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
【０２８９】
ユーザが有限オートマトン（１６０４）に操作Ｔの抽象化処理を適用したいとする。ユーザは、状態（１５０３）中の上記黒丸の右隣にある白丸をマウスでクリックし、有限オートマトン（１６０４）に操作Ｔの抽象化処理を開始することをコンピュータ（２０１）に指示する。
【０２９０】
第２の生成部（２０２−２）は、上記操作Ｔの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１６０４）に対して操作Ｔの抽象化処理を行う。第２の生成部（２０２−２）は、操作Ｔの抽象化処理によって図１６Ｄに示す有限オートマトン（１６０４）中の状態を除去し、エッジをマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ４の処理）。図１６Ｅは、当該ステップ４の２回目の処理によって生成される有限オートマトン（１６０５）を示す。
【０２９１】
図１５Ｋは、図１５Ｊに示す操作Ｔの抽象化処理から生成された有限オートマトン（１６０５）から正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の場所<1>及び場所<2>にそれぞれ適用可能な近似パターン表現式を判定するための操作を示す画面例である。
ユーザは、バリエーション・パターン（１５０５）中の場所<k>をフォーカスした際に適用可能な近似パターン表現式を、図９Ａに記載のフローチャートに従い判定する処理を開始するために、近似パターン表現式の選択というボタンをマウスでクリックする。図１５Ｋでは、バリエーション・パターン（１５０５）中に場所<1>及び場所<2>があることを示し、当該場所<1>及び<2>いずれにおいても、デフォルトの近似パターン表現式として指定されている  <prim>  が表示されている。
【０２９２】
ユーザが場所<1>に適用可能な近似パターン表現式を判定する処理を開始するために、場所<1>に関連付けられた選択ボタンをマウスでクリックするとする。当該選択ボタンのクリックに応じて、近似パターン表現式判定プログラムが走り、図１５Ｍに示すサブウィンドウ（１５３０）が表示される。
【０２９３】
また、図１５Ｋは、図１６Ｅに示す有限オートマトン（１６０５）のバリエーション・パターン（１５０５）、及び現時点での正規表現候補（１５０４）を示す。現時点での正規表現候補（１５０４）は、図１５Ｋに示すバリエーション・パターン（１５０５）中の場所<1>及び<2>をフォーカスした際にそれぞれ適用可能な近似パターン表現式（１５０６）  <prim>  及び  <prim>  で推論した場合の正規表現候補を示す。
【０２９４】
図１５Ｌは、図１５Ｋに示すバリエーション・パターン（１５０５）のうち場所<1>をフォーカスした際のバリエーション・パターン（１５４３）、及び、現在の近似パターン表現式ストア（１５４４）中にある近似パターン表現式を示す。
バリエーション・パターン（１５４３）中の場所<1>がフォーカスされている場合に、当該場所<1>において適用可能な近似パターン表現式を判定する処理は下記の通りである。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（１５４４）中の近似パターン表現式  <prim>  （１５４４−１）及び<choice>（１５４４−２）を候補とする。なお、近似パターン表現式ストア（１５４４）は、図１５Ｅに示す近似パターン表現式ストア（１５４２）に、図１５Ｈに示す処理によって追加された近似パターン表現式  画面１<prim>>.xls  及び近似パターン表現式  帳票<prim>>.ppt  が追加されたものである。
ステップ２：表現式生成部（２０３）は、場所<1>部分を(.*)で置き換えて得られる正規表現  画面1(.*)>.xls  をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（１５４４）中の基本関数に対応しない近似パターン表現式（１５４４−３、１５４４−４）に対して正規表現でreg_vをマッチさせる。その結果、図１５Ｇに示した格納操作によって近似パターン表現式ストア（１５４２）中に格納した近似パターン表現式の２つ（１５４４−３、１５４４−４）のうち、  画面１<prim>>.xls  （１５４４−３）が、上記正規表現  reg_v  にマッチする。
ステップ４：表現式生成部（２０３）は、マッチが成功した近似パターン表現式  画面１<prim>>.xls  （Pi）について、reg_vの場所<1>に対応する(.*)部分でキャプチャリングされた部分パターン  1<prim>  をPsub_iとする。
ステップ５：表現式生成部（２０３）は、近似パターン表現式  1<prim>  が、A0_一覧表示画面<AA  にマッチせず、且つ、11_初期画面<EF30  及び  12_項目入力画面＜EG43  にマッチするので、近似パターン表現式  1<prim> | <choice>  が適用可能であると判定する。従って、表示部（２０６）は、上記<1>の部分の近似パターン表現式の候補として、近似パターン表現式  <prim>  及び  <choice>  、並びに、近似パターン表現式  1<prim> | <choice>  の３種類を画面上に表示する（図１５Ｍを参照）。
【０２９５】
図１５Ｍは、図１５Ｌに示すバリエーション・パターン（１５０５）のうち場所<1>をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
具体的には、図１５Ｍは、場所<1>に適用可能な近似パターン表現式が  <prim>  、  <choice>  又は  1<prim> | <choice>  の３種類であることを示す（１５３２）。また、図１５Ｍは、場所<1>に適用可能な近似パターン表現式それぞれに対応する正規表現（すなわち近似結果）を示す。ユーザは、場所<1>に適用可能な近似パターン表現式（１５３２）のいずれか一つを選択可能である。
【０２９６】
ユーザが近似パターン表現式  1<prim> | <choice>  を選択したいとする。ユーザは、近似パターン表現式  1<prim> | <choice>  の左横にある選択ボタンをマウスでクリックし、さらにＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、選択された近似パターン表現式  1<prim> | <choice>  に対応する正規表現を含む正規表現候補（１５０４）がウィンドウ（１５０１）上に表示される。
【０２９７】
ユーザは、場所<2>についても同様にして、当該場所<2>に適用可能な近似パターン表現式として<prim>を選択したとする（図示せず）。そうすると、場所<2>の部分を近似パターン表現式  <prim>  による正規表現推論関数で推論することによって得られる正規表現を一部に含む正規表現候補（１５０４）が、ウィンドウ（１５０１）上に表示される。
【０２９８】
図１５Ｎは、図１５Ｊに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア（１５４４）中に保存するための処理を示す画面例である。
具体的には、図１５Ｎは、操作Ｓ（ｋ＝２４）（図１５Ｂ）そして操作Ｔ（１回目）（図１５Ｃ）及び操作Ｔ（２回目）（図１５Ｊ）を行うことによって生成された有限オートマトンから得られたバリエーション・パターンに対して、当該バリエーション・パターン中の場所<1>に近似パターン表現式  1<prim> | <choice>  を適用して（ <1> = 1<prim> | <choice>   ）得られる近似パターン表現式を近似パターン表現式ストア（１５４４）中に保存する。
【０２９９】
ユーザが、場所<1>に近似パターン表現式  1<prim> | <choice>  を適用した近似パターン表現式  画面(1<prim> | <choice>)>.xls  を近似パターン表現式ストア（１５４４）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１５Ｈに示すサブウィンドウ（１５２６）と同様のサブウィンドウ（図示せず）が表示部（２０６）上に表示される。ユーザは、近似パターン表現式を保存する場合、マウスで保存ボタン（図示せず）をクリックする。当該保存ボタンのクリックに応じて、近似パターン表現式  画面(1<prim> | <choice>)>.xls  が近似パターン表現式ストア（１５４４）中に近似パターン表現式として格納される。
また、ユーザは、近似パターン表現式  画面(1<prim> | <choice>)>.xls  を編集することが可能である。編集後に、ユーザは、当該編集後の近似パターン表現式を近似パターン表現式ストア（１５４４）中に保存しうる。
【０３００】
図１５Ｐは、図１６Ｅに示す有限オートマトン（１６０５）に操作Ｔ（３回目）の抽象化処理を開始するための操作を示す画面例である。
状態（１５０３）中の黒印は、直前に終えた処理である操作Ｔの抽象化処理（ステップ４）の位置を示す。図１５Ｐにおいて、最初の有限オートマトンに操作Ｓが適用され、次に操作Ｔ（白丸）、そしてさらに操作Ｔ（黒丸）が適用されていることを示す。当該黒丸の右方向にある白丸は、操作Ｔによる有限オートマトンの抽象化処理が可能であることを示す。
【０３０１】
ユーザが有限オートマトン（１６０５）に操作Ｔの抽象化処理を適用したいとする。ユーザは、状態（１５０３）中の上記黒丸の右隣にある白丸をマウスでクリックし、有限オートマトン（１６０５）に操作Ｔの抽象化処理を開始することをコンピュータ（２０１）に指示する。
【０３０２】
第２の生成部（２０２−２）は、上記操作Ｔの抽象化処理の開始の指示を受信することに応じて、有限オートマトン（１６０５）に対して操作Ｔの抽象化処理を行う。第２の生成部（２０２−２）は、操作Ｔの抽象化処理によって図１６Ｅに示す有限オートマトン（１６０５）中の状態を除去し、エッジをマージして、縮退された有限オートマトンをメモリ（１０３）内に生成する（ステップ４の処理）。図１６Ｆは、当該ステップ４の３回目の処理によって生成される有限オートマトン（１６０６）を示す。
【０３０３】
図１５Ｑは、図１５Ｐに示す操作Ｔの抽象化処理から生成された有限オートマトン（１６０５）から正規表現候補を求めるために、当該有限オートマトンから生成されたバリエーション・パターン中の場所<1>に適用可能な近似パターン表現式を判定するための操作を示す画面例である。
ユーザは、バリエーション・パターン（１５０５）中の場所<k>をフォーカスした際に適用可能な近似パターン表現式、図９Ａに記載のフローチャートに従い判定する処理を開始するために、近似パターンの選択というボタンをマウスでクリックする。図１５Ｑでは、バリエーション・パターン（１５０５）中に場所<1>があることを示し、当該場所<1>において、近似パターン表現式  1<prim> | <choice>  が表示されている。
【０３０４】
ユーザが場所<1>に適用可能な近似パターン表現式を判定する処理を開始するために、場所<1>に関連付けられた選択ボタンをマウスでクリックするとする。当該選択ボタンのクリックに応じて、近似パターン表現式判定プログラムが走り、図１５Ｓに示すサブウィンドウ（１５３４）が表示される。
【０３０５】
また、図１５Ｑは、図１６Ｆに示す有限オートマトン（１６０６）のバリエーション・パターン（１５０５）、及び現時点での正規表現候補（１５０４）を示す。
【０３０６】
図１５Ｒは、図１５Ｑに示すバリエーション・パターン（１５０５）のうち場所<1>をフォーカスした際のバリエーション・パターン（１５４５）、及び、現在の近似パターン表現式ストア（１５４６）中にある近似パターン表現式を示す。
バリエーション・パターン（１５４５）中の場所<1>がフォーカスされている場合に、当該フォーカスされた場所<1>において適用可能な近似パターン表現式を判定する処理は下記の通りである。
ステップ１：表現式生成部（２０３）は、近似パターン表現式ストア（１５４６）中の基本関数  <prim>  （１５４６−１）及び  <choice>  （１５４６−２）を候補とする。なお、近似パターン表現式ストア（１５４６）は、図１５Ｌに示す近似パターン表現式ストア（１５４４）に、図１５Ｎに示す処理によって追加された近似パターン表現式  画面(1<prim> | <choice>).xls  が追加されたものである。
ステップ２：表現式生成部（２０３）は、Var-Pattern中の<1>部分を(.*)で置き換えて得られる正規表現  (.*)  をreg_vとする。
ステップ３：表現式生成部（２０３）は、現在の近似パターン表現式ストア（１５４６）中の近似パターン表現式（１５４６−１、１５４６−２、１５４６−３、１５４６−４、１５４６−５）に対して正規表現でreg_vをマッチさせる。その結果、図１５Ｇ及び図１５Ｎにそれぞれ示した格納操作によって格納された近似パターン表現式の３つ（１５４６−３、１５４６−４、１５４６−５）の全てが、上記正規表現  reg_v  にマッチする。
ステップ４：表現式生成部（２０３）は、マッチが成功した近似パターン表現式、  画面１<prim>>.xls  、  帳票<prim>>.ppt  、  画面(1<prim> | <choice>)>.xls  について、reg_vの場所<1>に対応する(.*)部分でキャプチャリングされた部分パターン  画面１<prim>>.xls  、  帳票<prim>>.ppt  、  画面(1<prim> | <choice>) .xls  をPsub_iとする。
ステップ５：表現式生成部（２０３）は、上記載したPsub_iが、画面11_初期画<EF30>.xls  、  画面12_項目入力画面<EG43>.xls  、  画面A0_一覧表示画面<AA>.xls  、  帳票801_新規顧客フォーム<FA03>.ppt  、  帳票9d3_注文フォーム<FP51>.ppt  の一部にマッチし且つ一部にマッチしないので、近似パターン表現式  画面１<prim>>.xls | <choice>  、帳票<prim>>.ppt | <choice>  、  画面１<prim> | <choice>)>.xls  が適用可能であると判定する。例えば、画面１<prim>>.xls  は最初の２つにマッチして、残りの２つにマッチしない。よって、マッチしないPsub_iがあるので、近似パターン表現式中に
<choice>が付けられる。従って、表示部（２０６）は、上記<1>の部分の近似パターン表現式の候補として、近似パターン表現式  <prim>  及び  <choice>  、並びに、近似パターン表現式  画面１<prim>>.xls | <choice>  、  帳票<prim>>.ppt | <choice>  、  画面(1<prim> |<choice>)>.xls | <choice>  の５種類を画面上に表示する（図１５Ｓを参照）。
【０３０７】
図１５Ｓは、図１５Ｒに示すバリエーション・パターン（１５４５）のうち場所<1>をフォーカスした際に適用可能であると判定された近似パターン表現式をユーザが選択することを可能にするための処理を示す画面例である。
具体的には、図１５Ｓは、場所<1>に適用可能な近似パターン表現式が、  <prim>  及び  <choice>  、  帳票<prim>>.ppt | <choice>  、  画面１<prim>>.xls | <choice>  及び  画面(1<prim> | <choice>)>.xls | <choice>であることを示す（１５３６）。また、図１５Ｓは、場所<1>に適用可能な近似パターン表現式それぞれに対応する正規表現（すなわち近似結果）を示す。ユーザは、場所<1>に適用可能な近似パターン表現式（１５３６）のいずれか一つを選択可能である。
【０３０８】
しかしながら、上記５種類のうちに、ユーザが所望する近似パターン表現式がなかったとする。その場合には、ユーザは、サブウィンドウ（１５３４）内の「近似パターン表現式の作成」のボタンを、マウスでクリックしてＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、ユーザは、マニュアル的に近似パターン表現式を入力して追加することができる（画面省略）。また、ユーザは、必要に応じて、不要な近似パターン表現式を削除しうる（画面省略）。
【０３０９】
図１５Ｔは、図１５Ｒに示すバリエーション・パターン（１５０５）中の場所<1>をフォーカスした際に適用可能である近似パターン表現式の例であり、ユーザが所望する近似パターン表現式が追加された近似パターン表現式が選択可能であることを示す画面である。
図１５Ｔに示す近似パターン表現式では、図１５Ｓに示した近似パターン表現式と比べて、近似パターン表現式  画面(1<prim> | <choice>)>.xls |<prim>  がユーザによって新たに追加されている。
【０３１０】
ユーザが近似パターン表現式  画面(1<prim> | <choice>)>.xls | <prim>  を選択したいとする。ユーザは、近似パターン表現式  画面1(<prim>| <choice>)>.xls | <prim>  の左横にある選択ボタンをマウスでクリックし、ＯＫボタンをクリックする。当該ＯＫボタンのクリックに応じて、選択された近似パターン表現式  画面(1<prim> | <choice>)>.xls | <prim>  に対応する正規表現を一部に含む正規表現候補（１５０４）が、図１５Ｕに示すようにウィンドウ（１５０１）上に表示される。
【０３１１】
図１５Ｕは、図１５Ｐに示す処理によって作成された有限オートマトンから作成された近似パターン表現式を近似パターン表現式ストア（１５４６）中に保存するための処理を示す画面例である。
具体的には、図１５Ｕは、操作Ｓ（ｋ＝２４）（図１５Ｂ）、操作Ｔ（１回目）（図１５Ｃ）、操作Ｔ（２回目）（図１５Ｊ）、そして操作Ｔ（３回目）（図１５Ｐ）を行うことによって生成された有限オートマトンから得られたバリエーション・パターンに対して、当該バリエーション・パターン中の場所<1>に近似パターン表現式  画面(1<prim> | <choice>)>.xls |<prim>  を適用して（  <1> = <画面(1<prim> | <choice>)>.xls | <prim>  ）得られる近似パターン表現式を近似パターン表現式ストア（１５４６）中に保存する。
【０３１２】
ユーザが、近似パターン表現式を近似パターン表現式ストア（１５４６）中に格納したいとする。ユーザは、マウスで保存ボタンをクリックする。当該保存ボタンのクリックに応じて、図１５Ｈに示すサブウィンドウ（１５２６）と同様のサブウィンドウ（図示せず）が表示部（２０６）上に表示される。ユーザは、近似パターン表現式を保存する場合、マウスで保存ボタン（図示せず）をクリックしうる。当該保存ボタンのクリックに応じて、近似パターン表現式  画面(1<prim> | <choice>)>.xls | <prim>  が近似パターン表現式ストア（１５４６）中に格納されうる（図１５Ｖの１５４８を参照）。なお、近似パターン表現式  画面(1<prim> | <choice>)>.xls | <prim>  が、図１５Ｔに示す近似パターン表現式のユーザによる追加処理によって既に近似パターン表現式ストア（１５４６）中に保存されているので、コンピュータ（２０１）は、例えば、同じ近似パターン表現式が近似パターン表現式ストア（１５４６）中に既にあることのエラー・メッセージ、又は、近似パターン表現式ストア（１５４６）中に既にある同じ近似パターン表現式のファイルを上書きすることの確認メッセージを表示しうる。
【０３１３】
図１５Ｖは、実施例１の抽象化処理によって作成された現在の近似パターン表現式ストア（１５４８）中に格納された近似パターン表現式を、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理においても再利用可能であることを示す画面例である。
近似パターン表現式ストア（１５４８）には、実施例１の抽象化処理によって基本関数に対応する近似パターン表現式である  <prim>  及び  <choice>  以外の近似パターン表現式が追加されている。当該追加された近似パターン表現式は、実施例１以外の入力文字列の集合を近似パターン表現式に段階的に変換する各処理においても再利用可能である。
【０３１４】
図１７は、本発明の実施態様である実施例２を例として、入力文字列の集合を段階的に具体的な正規表現から抽象的な正規表現になるように対話的に処理した場合に生成される各正規表現を示す。
画面（１７０１）は、入力文字列の集合を示す。当該入力文字列の集合は、図１５Ａに示すサブウィンドウ（１５２２）内に表示された入力文字列の集合と同じである。
画面（１７０２）は、本発明の実施態様に従い操作Ｓ、次に操作Ｔで抽象化した場合に得られるバリエーション・パターン[Var-Pattern]、及び当該バリエーション・パターン中の近似対象部分すべてに近似パターン表現式  <prim>  を適用して得られる正規表現
[Reg-Exp]を示す。画面（１７０２）で示される正規表現は、画面<数字>，画面<英字>，帳票で始まる文字列を区別して処理するための正規表現である。
画面（１７０３）は、本発明の実施態様に従いさらに１段階操作Ｔで抽象化した場合に得られるバリエーション・パターン、及び当該バリエーション・パターン中の近似対象部分すべてに近似パターン表現式を適用して得られる正規表現[Reg-Exp]を示す。なお、画面（１７０３）に示すバリエーション・パターンは、実施例１における操作Ｔによる抽象化処理と異なる方法（適用される近似パターン表現式が異なる）で抽象化した一例である。画面（１７０３）で示される正規表現は、例えば、フォルダ中のファイルを文字列「画面」及び「帳票」によって振り分けて処理するためのものでありうる。
画面（１７０４）は、本発明の実施態様に従い、画面（１７０３）で実現されている正規表現の推論方法を表している近似パターン表現式である。当該近似パターン表現式は、画面（１７０１）に示す文字列集合から画面（１７０３）に示す[Reg-Exp]に表示されている正規表現を推論する方法を表現している近似パターン表現式（すなわち、正規表現推論関数）を構築したものである。当該近似パターン表現式は、画面（１７０１）に示される入力文字列の集合以外の入力文字列の集合を抽象化する際に再利用されうる。 
【図１】
2014006877.tif 000003
【図２】
2014006877.tif 000004
【図３Ａ】
2014006877.tif 000005
【図３Ｂ】
2014006877.tif 000006
【図４】
2014006877.tif 000007
【図５Ａ】
2014006877.tif 000008
【図５Ｂ】
2014006877.tif 000009
【図５Ｃ】
2014006877.tif 000010
【図６Ａ】
2014006877.tif 000011
【図６Ｂ】
2014006877.tif 000012
【図６Ｃ】
2014006877.tif 000013
【図７Ａ】
2014006877.tif 000014
【図７Ｂ】
2014006877.tif 000015
【図８】
2014006877.tif 000016
【図９Ａ】
2014006877.tif 000017
【図９Ｂ】
2014006877.tif 000018
【図９Ｃ】
2014006877.tif 000019
【図１０Ａ】
2014006877.tif 000020
【図１０Ｂ】
2014006877.tif 000021
【図１０Ｃ】
2014006877.tif 000022
【図１０Ｄ】
2014006877.tif 000023
【図１０Ｅ】
2014006877.tif 000024
【図１０Ｆ】
2014006877.tif 000025
【図１０Ｇ】
2014006877.tif 000026
【図１０Ｈ】
2014006877.tif 000027
【図１０Ｊ】
2014006877.tif 000028
【図１０Ｋ】
2014006877.tif 000029
【図１０Ｌ】
2014006877.tif 000030
【図１０Ｍ】
2014006877.tif 000031
【図１０Ｎ】
2014006877.tif 000032
【図１０Ｐ】
2014006877.tif 000033
【図１０Ｑ】
2014006877.tif 000034
【図１０Ｒ】
2014006877.tif 000035
【図１０Ｓ】
2014006877.tif 000036
【図１０Ｔ】
2014006877.tif 000037
【図１０Ｕ】
2014006877.tif 000038
【図１０Ｖ】
2014006877.tif 000039
【図１１Ａ】
2014006877.tif 000040
【図１１Ｂ】
2014006877.tif 000041
【図１１Ｃ】
2014006877.tif 000042
【図１１Ｄ】
2014006877.tif 000043
【図１１Ｅ】
2014006877.tif 000044
【図１１Ｆ】
2014006877.tif 000045
【図１２Ａ】
2014006877.tif 000046
【図１２Ｂ】
2014006877.tif 000047
【図１３】
2014006877.tif 000048
【図１４】
2014006877.tif 000049
【図１５Ａ】
2014006877.tif 000050
【図１５Ｂ】
2014006877.tif 000051
【図１５Ｃ】
2014006877.tif 000052
【図１５Ｄ】
2014006877.tif 000053
【図１５Ｅ】
2014006877.tif 000054
【図１５Ｆ】
2014006877.tif 000055
【図１５Ｇ】
2014006877.tif 000056
【図１５Ｈ】
2014006877.tif 000057
【図１５Ｊ】
2014006877.tif 000058
【図１５Ｋ】
2014006877.tif 000059
【図１５Ｌ】
2014006877.tif 000060
【図１５Ｍ】
2014006877.tif 000061
【図１５Ｎ】
2014006877.tif 000062
【図１５Ｐ】
2014006877.tif 000063
【図１５Ｑ】
2014006877.tif 000064
【図１５Ｒ】
2014006877.tif 000065
【図１５Ｓ】
2014006877.tif 000066
【図１５Ｔ】
2014006877.tif 000067
【図１５Ｕ】
2014006877.tif 000068
【図１５Ｖ】
2014006877.tif 000069
【図１６Ａ】
2014006877.tif 000070
【図１６Ｂ】
2014006877.tif 000071
【図１６Ｃ】
2014006877.tif 000072
【図１６Ｄ】
2014006877.tif 000073
【図１６Ｅ】
2014006877.tif 000074
【図１６Ｆ】
2014006877.tif 000075
【図１７】
2014006877.tif 000076