(57)【要約】【課題】対象とする文字列が正規表現で記載された文字列の型に合致しているか否かを判定する場合にあって、本構成を有していない場合に比較して、高速に判定処理を行うようにした情報処理装置を提供する。【解決手段】情報処理装置の第１の受付手段は、対象とする文字列を受け付け、第２の受付手段は、正規表現で記載された文字列の型と該型内の文字列の集合である部分を受け付け、第１の判定手段は、第１の受付手段によって受け付けられた文字列（第１の文字列）が第２の受付手段によって受け付けられた集合内の文字列（第２の文字列）に合致しているか否かを判定し、第２の判定手段は、第１の文字列が第２の文字列以外の正規表現で記載された型に合致しているか否かを判定し、第３の判定手段は、両者の判定結果を用いて、第１の文字列が第２の文字列の型に合致しているか否かを判定する。【選択図】図１
2014021883.tif 000002
【特許請求の範囲】
【請求項１】
対象とする文字列を受け付ける第１の受付手段と、
正規表現で記載された文字列の型と該型内の文字列の集合である部分を受け付ける第２の受付手段と、
前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列に合致しているか否かを判定する第１の判定手段と、
前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、
前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段
を具備することを特徴とする情報処理装置。
【請求項２】
対象とする文字列を受け付ける第１の受付手段と、
正規表現で記載された文字列の型を受け付ける第２の受付手段と、
前記第２の受付手段によって受け付けられた文字列の型から文字列の集合である部分を抽出する抽出手段と、
前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列に合致しているか否かを判定する第１の判定手段と、
前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、
前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段
を具備することを特徴とする情報処理装置。
【請求項３】
前記第１の判定手段は、前記第１の受付手段によって受け付けられた文字列の先頭から連続する部分が前記抽出手段によって抽出された文字列に合致しているか否かを判定する
ことを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
複数の文字認識結果の各々の文字をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、
前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、
前記ノード内で前記請求項１から３のいずれか一項に記載の前記第３の判定手段による判定結果を記憶する記憶手段と、
前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段
を具備し、
前記限定手段は、リンクを限定する場合に、前記記憶手段内の判定結果が非合致であれば前記予め定められた文字列パターンと合致しているか否かの処理を行わない
ことを特徴とする情報処理装置。
【請求項５】
コンピュータを、
対象とする文字列を受け付ける第１の受付手段と、
正規表現で記載された文字列の型と該型内の文字列の集合である部分を受け付ける第２の受付手段と、
前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列に合致しているか否かを判定する第１の判定手段と、
前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、
前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段
として機能させるための情報処理プログラム。
【請求項６】
コンピュータを、
対象とする文字列を受け付ける第１の受付手段と、
正規表現で記載された文字列の型を受け付ける第２の受付手段と、
前記第２の受付手段によって受け付けられた文字列の型から文字列の集合である部分を抽出する抽出手段と、
前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列に合致しているか否かを判定する第１の判定手段と、
前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、
前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段
として機能させるための情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及び情報処理プログラムに関する。
【背景技術】
【０００２】
特許文献１には、不定ピッチで記入された単語文字列を、大幅な文字認識処理時間の増加を招くことなく正しく読み取る単語読み取り方式を提供することを目的とし、入力単語文字列パターンから個々のパターンを囲む矩形を抽出するパターン切出手段と、これらの矩形を組み合わせて、総矩形数が、読み取り対象単語の文字数の範囲内となる文字パターン矩形の並びを１つ以上生成する文字パターン矩形生成手段と、文字パターン矩形の並びを予め用意された標準文字パターンと比較して候補文字列を出力する文字認識手段と、候補文字列を予め用意された単語辞書と比較して候補単語を出力する単語検索手段とを備えていることが開示されている。
【０００３】
特許文献２には、書式制御情報の字種の指定に正規表現を使用することにより詳細な指定を可能にして、認識率を向上させることを目的とし、用紙に記録された文字等を読み取るために参照される書式制御情報を記憶するためのものであって、書式制御情報中の文字種を指定する情報が正規表現で表されている書式制御情報部と、書式制御情報部に記憶された書式制御情報中の正規表現を解析する正規表現解析部と、正規表現解析部による解析結果に基づいて認識辞書中の使用する辞書を選択する字種制御部と、字種制御部によって選択された辞書を用いて用紙に記録された文字等のパターンと照合し読み取り結果を求める照合部を備えていることが開示されている。
【０００４】
特許文献３には、文字認識結果の修正に必要な修正規則の機能拡張や保守が容易で、修正誤りを起こすことがない文字認識結果の修正方式を提供することを課題とし、入力文字列に対する文字認識結果である候補文字列を第１位から第ｎ位まで配列して候補文字マトリックスを形成し、このマトリックスを正規表現マッチング部に渡し、マッチング部は、種々の文字列記述形式に適合した種々の修正規則を蓄積した修正規則ファイルをプログラム外に有しており、入力されたマトリックスに適合可能な修正規則をファイルから選択し、そして、選択した修正規則に最も適合する候補文字列をマトリックス内の文字を選んで作成し、続いて、選択された修正規則に従って、文字列置き換え部が、候補文字列内の文字列をより正しい文字列に置換し、次に、文字置き換え部が、文字列置換された候補文字列内の個々の文字をより正しい文字に置換することが開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０１−２８１５８６号公報
【特許文献２】特開平０６−０３６０６９号公報
【特許文献３】特開平０９−１３８８３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、対象とする文字列が正規表現で記載された文字列の型に合致しているか否かを判定する場合にあって、本構成を有していない場合に比較して、高速に判定処理を行うようにした情報処理装置及び情報処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の発明は、対象とする文字列を受け付ける第１の受付手段と、正規表現で記載された文字列の型と該型内の文字列の集合である部分を受け付ける第２の受付手段と、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列に合致しているか否かを判定する第１の判定手段と、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段を具備することを特徴とする情報処理装置である。
【０００８】
請求項２の発明は、対象とする文字列を受け付ける第１の受付手段と、正規表現で記載された文字列の型を受け付ける第２の受付手段と、前記第２の受付手段によって受け付けられた文字列の型から文字列の集合である部分を抽出する抽出手段と、前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列に合致しているか否かを判定する第１の判定手段と、前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段を具備することを特徴とする情報処理装置である。
【０００９】
請求項３の発明は、前記第１の判定手段は、前記第１の受付手段によって受け付けられた文字列の先頭から連続する部分が前記抽出手段によって抽出された文字列に合致しているか否かを判定することを特徴とする請求項１又は２に記載の情報処理装置である。
【００１０】
請求項４の発明は、複数の文字認識結果の各々の文字をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、前記ノード内で前記請求項１から３のいずれか一項に記載の前記第３の判定手段による判定結果を記憶する記憶手段と、前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段を具備し、前記限定手段は、リンクを限定する場合に、前記記憶手段内の判定結果が非合致であれば前記予め定められた文字列パターンと合致しているか否かの処理を行わないことを特徴とする情報処理装置である。
【００１１】
請求項５の発明は、コンピュータを、対象とする文字列を受け付ける第１の受付手段と、正規表現で記載された文字列の型と該型内の文字列の集合である部分を受け付ける第２の受付手段と、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列に合致しているか否かを判定する第１の判定手段と、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた集合内の文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段として機能させるための情報処理プログラムである。
【００１２】
請求項６の発明は、コンピュータを、対象とする文字列を受け付ける第１の受付手段と、正規表現で記載された文字列の型を受け付ける第２の受付手段と、前記第２の受付手段によって受け付けられた文字列の型から文字列の集合である部分を抽出する抽出手段と、前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列に合致しているか否かを判定する第１の判定手段と、前記第１の受付手段によって受け付けられた文字列が前記抽出手段によって抽出された文字列以外の正規表現で記載された型に合致しているか否かを判定する第２の判定手段と、前記第１の判定手段による判定結果と前記第２の判定手段による判定結果を用いて、前記第１の受付手段によって受け付けられた文字列が前記第２の受付手段によって受け付けられた文字列の型に合致しているか否かを判定する第３の判定手段として機能させるための情報処理プログラムである。
【発明の効果】
【００１３】
請求項１の情報処理装置によれば、対象とする文字列が正規表現で記載された文字列の型に合致しているか否かを判定する場合にあって、本構成を有していない場合に比較して、高速に判定処理を行うことができる。
【００１４】
請求項２の情報処理装置によれば、対象とする文字列が正規表現で記載された文字列の型に合致しているか否かを判定する場合にあって、本構成を有していない場合に比較して、高速に判定処理を行うことができる。
【００１５】
請求項３の情報処理装置によれば、部分一致であるか否かについての判定も行うことができる。
【００１６】
請求項４の情報処理装置によれば、複数の文字認識結果の候補から文字認識結果を選択して出力する場合にあって、本構成を有していない場合に比較して、高速に文字認識結果を出力することができる。
【００１７】
請求項５の情報処理プログラムによれば、対象とする文字列が正規表現で記載された文字列の型に合致しているか否かを判定する場合にあって、本構成を有していない場合に比較して、高速に判定処理を行うことができる。
【００１８】
請求項６の情報処理プログラムによれば、対象とする文字列が正規表現で記載された文字列の型に合致しているか否かを判定する場合にあって、本構成を有していない場合に比較して、高速に判定処理を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】本実施の形態の構成例についての概念的なモジュール構成図である。
【図２】本実施の形態による処理例を示すフローチャートである。
【図３】本実施の形態の構成例についての概念的なモジュール構成図である。
【図４】対象とする帳票の例を示す説明図である。
【図５】正規表現表記規則の例を示す説明図である。
【図６】文字位置と文字候補の関係例を示す説明図である。
【図７】文字位置と文字候補の関係例を示す説明図である。
【図８】本実施の形態による処理例を示すフローチャートである。
【図９】記号例を示す説明図である。
【図１０】記号例を示す説明図である。
【図１１】記号例を示す説明図である。
【図１２】記号例を示す説明図である。
【図１３】記号例を示す説明図である。
【図１４】文字切り出し位置が複数ある場合の処理例を示す説明図である。
【図１５】記号例を示す説明図である。
【図１６】文字切り出し位置が複数ある場合の処理例を示す説明図である。
【図１７】文字列を構成するネットワークの例を示す説明図である。
【図１８】文字列を構成するネットワーク内のノードが接続されている例を示す説明図である。
【図１９】パス限定処理モジュール内のモジュール構成例を示す説明図である。
【図２０】パス限定処理モジュールによる処理例を示すフローチャートである。
【図２１】文字位置と文字候補の関係例を示す説明図である。
【図２２】限定文字列パターン検査処理モジュールが受け付けるデータと出力するデータの例を示す説明図である。
【図２３】文字列の羅列の例を示す説明図である。
【図２４】文字列集合を２分木構造とした例を示す説明図である。
【図２５】限定文字列パターン検査処理モジュールが受け付けるデータと出力するデータの例を示す説明図である。
【図２６】限定文字列パターン検査処理モジュールが受け付けるデータと出力するデータの例を示す説明図である。
【図２７】限定文字列パターン検査処理モジュールが受け付けるデータと出力するデータの例を示す説明図である。
【図２８】文字列を構成するネットワーク内のノードが接続されている例を示す説明図である。
【図２９】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【図３０】文字列画像の例を示す説明図である。
【図３１】文字境界候補の例を示す説明図である。
【図３２】外接矩形の例を示す説明図である。
【図３３】文字切り出し結果の例を示す説明図である。
【図３４】文字切り出し位置を示すネットワーク表現の例を示す説明図である。
【図３５】ネットワーク表現内のパターンの例を示す説明図である。
【図３６】ネットワークの例を示す説明図である。
【図３７】複数の文字候補がある場合のネットワーク例を示す説明図である。
【発明を実施するための形態】
【００２０】
本実施の形態は、複数の文字列を対象として、その中から予め定められた正規表現で記載された文字列の型に合致する文字列を出力するものである。例えば、文字列が含まれている画像に対する文字認識結果を対象としてもよく、その画像に対する文字認識の結果から予め定められた正規表現で記載された文字列の型に合致する文字列を出力する。より具体的には、文字認識を行うときに、複数の文字切り出し結果があり、さらに１つの文字画像に対しても複数の文字認識結果があり得るが、それらの文字の組み合わせである複数の文字列から、認識結果として正しい文字列を抽出しようとするものである。
まず、本実施の形態を説明する前に、その前提又は本実施の形態を利用する情報処理装置について説明する。なお、この説明は、本実施の形態の理解を容易にすることを目的とするものである。
【００２１】
例えば、図３０の例に示すような文字列画像を対象とする。まず、この文字列画像を文字セグメントに分割する。文字セグメントとは、文字そのもの、あるいは文字の一部となる可能性がある文字部分である。ここでは、図３０の例に示すような横書きの文字列画像を例にとる。横書きの画像では、垂直な線（あるいは垂直に近い線）で分割を行うことにより、文字セグメントに分割する。例えば図３１に示した縦線（切れ目候補３１１０、切れ目候補３１２０）で、文字列画像を分割して、３つの文字セグメント「イ」、「ヒ」、及び、「学」を得ることができる。図３１の例に示した縦線を切れ目候補と呼ぶこととする。切れ目候補３１１０が「イ」と「ヒ」を分け、切れ目候補３１２０が「ヒ」と「学」を分けている。
【００２２】
次に、図３２の例に示すように、各文字セグメントに対し、その外接矩形（外接矩形３２１０、外接矩形３２２０、外接矩形３２３０）を抽出する。
以下、特許文献２に記載されている技術内容を例にして説明する。なお、以下の説明で用いる用語は、特許文献２で用いる用語とは異なっている場合がある。ただし、内容は特許文献２と同じである。
前述の文字セグメントを統合して、文字画像を決定する。複数の文字セグメントを統合して１つの文字画像を形成する場合もあれば、１つの文字セグメントが１つの文字となる場合もある。文字画像を決定するとは、文字の切り出し位置を決定することと同値であるから、以下では文字切り出し位置の決定という場合もある。
文字セグメントの統合のパターンは複数存在する。複数存在するパターンの中で、最も文字画像として評価の高いものを選択することによって、最終的な文字切り出し位置を決定する。
図３２の例に対しては、すべての文字切り出しパターンは、図３３に示す例のようになる。つまり、図３３（ａ）の例では、パターン１として３つの文字画像（外接矩形３２１０、外接矩形３２２０、外接矩形３２３０）、図３３（ｂ）の例では、パターン２として２つの文字画像（外接矩形３２１０と３２２０、外接矩形３２３０）、図３３（ｃ）の例では、パターン３として１つの文字画像（外接矩形３２１０と３２２０と３２３０）、図３３（ｄ）の例では、パターン４として２つの文字画像（外接矩形３２１０、外接矩形３２２０と３２３０）を示している。
【００２３】
文字切り出し位置を示すネットワーク表現（グラフ表現ともいわれる）として、図３３の例に示した複数の切り出しパターンを表すことができる。図３４の例において、ネットワークは、始点ノード３４００、終点ノード３４９０、中間ノード３４１０（ノード１）、中間ノード３４２０（ノード２）の４つのノードと、ノード間を接続するアークで構成されている（ノード間の接続線をアークと呼ぶこととする）。始点は、文字列画像の左端、終点は文字列画像の右端にあたる。中間ノード３４１０（ノード１）、中間ノード３４２０（ノード２）は、それぞれ、文字の切れ目候補位置（すなわち、図３１の例に示した切れ目候補３１１０、切れ目候補３１２０）を示す。中間ノード３４１０（ノード１）は、切れ目候補３１１０に対応している。また、中間ノード３４２０（ノード２）は、切れ目候補３１２０に対応している。
【００２４】
始点から、各ノードを通って、終点に至る経路を以下、「パス」と呼ぶ。パスは、１又は複数のアークから構成される。通常、複数のパスが存在する。図３３の例に示した文字切り出しパターンは、これらの複数のパスに対応している。例えば、図３３（ｂ）の例に示したパターン２は、図３５の太線で示したパス（文字切り出しパターン３４０４、文字切り出しパターン３４２２）と対応している。
ここで、どれか１つのアークには、１つの文字画像の候補が対応している。例えば、始点ノード３４００と中間ノード３４２０（ノード２）を結ぶアークには、「化」という文字画像（文字切り出しパターン３４０４）が対応している。１つのアークに対応する文字に対して、その文字の評価値を決定することができる。これを「アーク評価値」と呼ぶこととする。
アーク評価値は、文字の形状情報や、文字認識における認識確度などから算出する。アーク評価値の算出方法はさまざまある。例えば、（１）特開平９−１８５６８１号公報、（２）特開平８−１６１４３２号公報、（３）特開平１０−１５４２０７号公報、（４）特開昭６１−１７５８７８号公報、（５）特開平３−３７７８２号公報、（６）特開平１１−２０３４０６号公報等に記載の従来技術に示されている手法等がある。
【００２５】
１つのパスは、複数のアークから構成されている。複数のアーク評価値を用いて、そのアークから構成されるパスの評価値を計算することができる。これを「パス評価値」と呼ぶこととする。
文字切り出し位置を決定するため、複数のパスの中で、最もパス評価値の高いパスを選択する。パスが選択できれば、文字切り出し位置が確定して、文字を切り出すことができる。そして、切り出した文字（文字画像）を文字認識した結果も確定することになる。
例えば、図３５の例で、太線のパスが選択されたとする。この場合、文字切り出し位置は、始点３４００と、中間ノード３４２０（ノード２）と、終点３４９０の３点となる。そして、確定した文字認識結果は、「化」（文字切り出しパターン３４０４）、「学」（文字切り出しパターン３４２２）となる。
【００２６】
ここで、パス評価値の算出方法について説明する。基本的には、パス評価値は、アーク評価値の重み付け和が用いられる。ｉ番目のアークのアーク評価値をＶｉとし、ｉ番目のアーク評価値に対する重みをｗｉとし、アークの数をＮ、パス評価値をＰとすると、Ｐは次の（１）式で与えられる。
【数１】
2014021883.tif 000003
パスの数が複数存在すると前述したが、実際の文字列には、多くの文字セグメントが存在しているため、存在するパスの数は膨大となる。
そこで、特開平３−２２５５７９号公報に記載の技術では、図３４の例に示されたようなネットワーク内の複数のパスから最も評価値の高いパスを探索する方法として、ダイナミックプログラミング手法を用いることが述べられている。
ここでは、ダイナミックプログラミング手法の中で、このようなネットワークの最良パスを探索するのに適したビタビ法の説明を行う。
【００２７】
図３６に示す例において、始点ノード３６００から終点ノード３６９０までのネットワークを説明する。なお、ノード間のリンク（アークともいわれる）は、図３６に示したものに限らず、さまざまな場合がある。図３６のように対称の結線でなくてもかまわない。
このネットワークにおいて、途中に複数のノード（中間ノード３６１１、中間ノード３６１２、中間ノード３６１３等）を介して始点ノードから終点ノードに達するとする。途中のノードを中間ノードと呼ぶこととする。
各ノードとノードの間にはリンクが張られている。このリンクにはそのリンク固有の評価値（リンク値）が割り当てられている。始点ノード３６００から終点ノード３６９０に向かうパスは複数存在する。パスは、複数のリンクから成り立つことになる。パスが含む複数のリンクのリンク値の和が、パスの評価値となる。
例えば、リンク値は、ノード間の距離であるとする。この場合、パス評価値が最小のパスは、始点ノードから終点ノードに向かうパスの中で、最小距離のパスということになる。あるいは、パス評価値が最大のパスを求める問題とすることも可能である。
【００２８】
ここで、ビタビ法は、あるノードにある方向から入力されるリンクを１に限定することによって、最適ではないパスを削減する。これにより、演算処理量と所要メモリ量を削減する手法である。
例えば、今、ノードｘ（中間ノード３６２１）に左から入力されるリンクがすでに、１に限定されているとする。同様に、ノードｙ（中間ノード３６２２）、ノードｚ（中間ノード３６２３）に関しても１に限定されているとする。このとき、ノードＸ（中間ノード３６３１）に左から入力されるリンクを限定する。ノードＸ（中間ノード３６３１）には、ノードｘ（中間ノード３６２１）、ノードｙ（中間ノード３６２２）、ノードｚ（中間ノード３６２３）の３つのノードからリンクが張られている。このとき、ノードＸ（中間ノード３６３１）を通るパスとして、最適な可能性があるのは、ノードｘ（中間ノード３６２１）、ノードｙ（中間ノード３６２２）、ノードｚ（中間ノード３６２３）からノードＸ（中間ノード３６３１）に向かうリンクのいずれかである。この３つのうちで最適なものだけを残し、残りの２つを削除する。このようにして、ノードＸ（中間ノード３６３１）に左から入力されるパス（リンク）を１に限定する。ノードＹ（中間ノード３６３２）、ノードＺ（中間ノード３６３３）に関しても同様に左から入力されるパスを１に限定する。
このような手順を左のノードＡ（中間ノード３６１１）、ノードＢ（中間ノード３６１２）、ノードＣ（中間ノード３６１３）から順に右の方向に行う。最終的にノードＰ（中間ノード３６８１）、ノードＱ（中間ノード３６８２）、ノードＲ（中間ノード３６８３）に入る３つのパスに限定する。この３つのパスの中で最適なものを選択すればよい。
このようなビタビ法を用いた最適パス選定方法を、図３４に例示のネットワークにも同様に適用し得る。文字切り出し位置をノードとする。また、アーク評価値を前述のリンク値とすればよい。
【００２９】
従来技術が扱っていた図３４に例示するようなネットワークは、１つのアークに対し、１つの文字候補が存在しているものである。しかし、実際には１つのアークに対して、複数の文字候補が存在している。つまり、文字認識結果が複数ある場合である。例えば、図３７のように、複数の文字候補を割り当てることになる。図３７は、複数の文字候補がある場合のネットワーク例を示す説明図である。図３７の例では、「化学」（文字画像３７０２）という画像を１文字として認識したときの認識結果が、文字候補３７０２Ａの「梢」、文字候補３７０２Ｂの「際」、文字候補３７０２Ｃの「傾」の３種類ある。「化」（文字画像３７０４）という画像を１文字として認識したときの認識結果が、文字候補３７０４Ａの「化」、文字候補３７０４Ｂの「比」、文字候補３７０４Ｃの「任」の３種類ある。同様に、他の文字画像に対しても文字認識結果としての文字候補が複数ある。なお、図３７の例では、各文字画像に対して３種類の文字候補があるが、異なる数の文字候補を割り当ててもよい。例えば、認識確度が予め定められた値以上である文字を文字候補とした場合は、各文字画像に対して文字候補の数が異なる場合がある。
従来技術では、このような場合に、ビタビ法（又は、一般的にはダイナミックプログラミング手法）を適用して、文字認識結果を得ることはされていない。
【００３０】
以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１、図３は、本実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、それらのモジュールとして機能させるためのコンピュータ・プログラム（コンピュータにそれぞれの手順を実行させるためのプログラム、コンピュータをそれぞれの手段として機能させるためのプログラム、コンピュータにそれぞれの機能を実現させるためのプログラム）、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能に一対一に対応していてもよいが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）の場合にも用いる。「予め定められた」とは、対象としている処理の前に定まっていることをいい、本実施の形態による処理が始まる前はもちろんのこと、本実施の形態による処理が始まった後であっても、対象としている処理の前であれば、そのときの状況・状態に応じて、又はそれまでの状況・状態に応じて定まることの意を含めて用いる。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等が通信回線（一対一対応、一対多対応、多対一対応、多対多対応の通信接続を含む）で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。もちろんのことながら、「システム」には、人為的な取り決めである社会的な「仕組み」（社会システム）にすぎないものは含まない。
また、各モジュールによる処理毎に又はモジュール内で複数の処理を行う場合はその処理毎に、対象となる情報を記憶装置から読み込み、その処理を行った後に、処理結果を記憶装置に書き出すものである。したがって、処理前の記憶装置からの読み込み、処理後の記憶装置への書き出しについては、説明を省略する場合がある。なお、ここでの記憶装置としては、ハードディスク、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、外部記憶媒体、通信回線を介した記憶装置、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）内のレジスタ等を含んでいてもよい。
【００３１】
本実施の形態である情報処理装置は、画像から文字を認識するものであって、図３の例に示すように、画像受付モジュール３１０、文字列抽出モジュール３２０、切出位置抽出モジュール３３０、文字候補抽出モジュール３４０、パス限定処理モジュール３５０、出力モジュール３６０を有している。
【００３２】
画像受付モジュール３１０は、文字列抽出モジュール３２０と接続されている。画像受付モジュール３１０は、画像を受け付けて、その画像を文字列抽出モジュール３２０へ渡す。画像を受け付けるとは、例えば、スキャナ、カメラ等で画像を読み込むこと、ファックス等で通信回線を介して外部機器から画像を受信すること、ハードディスク（コンピュータに内蔵されているものの他に、通信回線を介して接続されているもの等を含む）等に記憶されている画像を読み出すこと等が含まれる。画像は、２値画像、多値画像（カラー画像を含む）であってもよい。受け付ける画像は、１枚であってもよいし、複数枚であってもよい。また、画像の内容として、文字列が含まれているのであれば、ビジネスに用いられる文書、広告宣伝用のパンフレット等であってもよい。
【００３３】
文字列抽出モジュール３２０は、画像受付モジュール３１０、切出位置抽出モジュール３３０と接続されている。文字列抽出モジュール３２０は、画像受付モジュール３１０が受け付けた画像から文字列を抽出する。
切出位置抽出モジュール３３０が対象とする画像は横書きあるいは縦書きの、１列のみの文字列画像を対象としている。なお、ここで、列とは、横書きの場合は横に並ぶ列であり、縦書きの場合は縦に並ぶ列である。
したがって、文字列抽出モジュール３２０は、画像受付モジュール３１０が受け付けた画像が１列のみの文字列画像であれば、そのまま用いればよい。画像受付モジュール３１０が受け付けた画像が、複数の文字列が存在するものがあり、このような複数文字列を単一の文字列になるように分離する手法としては、従来よりさまざまものが提案されているため、それらを用いればよい。単一の文字列となるように分離する例としてもさまざまな方式があるため、そのうちのいずれかを用いればよい。例えば、（１）特開平４−３１１２８３号公報、（２）特開平３−２３３７８９号公報、（３）特開平５−７３７１８号公報、（４）特開２０００−９０１９４号公報、等を用いればよい。これ以外の方法であってもよい。
【００３４】
切出位置抽出モジュール３３０は、文字列抽出モジュール３２０、文字候補抽出モジュール３４０と接続されている。切出位置抽出モジュール３３０は、文字列抽出モジュール３２０が抽出した文字列画像から文字画像を切り出す位置を抽出する。つまり、文字列画像を複数の文字セグメントに分割する。この文字切り出し位置の抽出方法としてもさまざまな方式があるため、そのうちのどれかを用いればよい。例えば、（１）特開平５−１１４０４７号公報、（２）特開平４−１００１８９号公報、（３）特開平４−９２９９２号公報、（４）特開平４−６８４８１号公報、（５）特開平９−５４８１４号公報、（６）特開平９−１８５６８１号公報の００２１段落に記載の文字の境界候補抽出方式、（７）特開平５−１２８３０８号公報の０００５段落に記載の文字切り出し位置決定方法等を用いればよい。これ以外の方法であってもよい。なお、ここでの文字画像とは、いわば文字候補画像であり、必ずしもその文字画像が１つの文字を表す画像でなくてもよい。
【００３５】
また、切出位置抽出モジュール３３０は、複数の切り出し位置を抽出してもよい。複数の切り出し位置を抽出することによって、１つの文字列画像に対して、文字切出位置群が複数ある。文字切出位置群とは、１つの文字列画像に対して、１つ以上の文字切り出し位置があることをいう。例えば、２つの文字切り出し位置があれば、３つの文字画像に分けられることになる。また、文字切出位置群が複数あるとは、１つの文字列画像に対して、文字切出位置で分けられた文字画像列が複数あることをいう。例えば、２つの文字切り出し位置で３つの文字画像からなる文字画像列と、３つの文字切り出し位置で４つの文字画像からなる文字画像列となる。具体例で説明すると、「化学」という文字列に対して、「イ」「ヒ」「学」からなる文字画像列と「化」「学」からなる文字画像列を生成することである。
【００３６】
文字候補抽出モジュール３４０は、切出位置抽出モジュール３３０、パス限定処理モジュール３５０と接続されている。文字候補抽出モジュール３４０は、切出位置抽出モジュール３３０によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する。この抽出処理を行うために、文字認識処理を行ってもよい。そのために、文字候補抽出モジュール３４０内に文字認識モジュールを含んでいてもよい。文字認識処理による認識結果は、前述のように、１つの文字画像に対して複数の文字候補が対応する。つまり、その文字画像を文字認識して、第１位の認識確度を有している文字候補、第２位の認識確度を有している文字候補等のように、複数の文字候補を文字認識結果とする。そして、文字認識結果として、文字候補の他に、その文字候補の認識確度を有していてもよい。また、抽出するのに、１つの文字画像に対して予め定められた数の文字候補を抽出してもよいし、予め定められた値以上の認識確度を有している文字候補を抽出してもよい。なお、認識確度は、文字認識処理において、その認識結果としての信頼性を表す値であってもよいし、文字画像の外接矩形のサイズ、縦横比等によって定められる文字らしさを表す値であってもよい。
【００３７】
パス限定処理モジュール３５０は、文字候補抽出モジュール３４０、出力モジュール３６０と接続されている。パス限定処理モジュール３５０は、文字候補抽出モジュール３４０によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成する。隣接する文字画像のノード間とは、隣接する文字画像があり、その文字画像に対応するノード間ということである。
また、切出位置抽出モジュール３３０が複数の切り出し位置を抽出した場合は、パス限定処理モジュール３５０は、切出位置抽出モジュール３３０によって抽出された複数の切り出し位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するようにしてもよい。
そして、パス限定処理モジュール３５０は、生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する。
また、パス限定処理モジュール３５０は、限定されたリンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成してもよい。さらに、リンクを構成しているノードに対する文字らしさを表す値に基づいて、リンク値を生成するようにしてもよい。
そして、パス限定処理モジュール３５０は、生成されたリンク値に基づいて、ネットワーク内のパスを選択するようにしてもよい。
【００３８】
また、パス限定処理モジュール３５０は、最初のリンクから文字列パターンに合致していない場合、その合致していないリンクの次のリンクからその文字列パターンに合致するリンクに限定するようにしてもよい。
また、パス限定処理モジュール３５０は、文字列パターンに合致するリンクがない場合は、その文字列パターン内の一部分の文字列パターンに合致するリンクに限定するようにしてもよい。
【００３９】
出力モジュール３６０は、パス限定処理モジュール３５０と接続されている。出力モジュール３６０は、パス限定処理モジュール３５０によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する。また、出力モジュール３６０は、パス限定処理モジュール３５０によって選択されたパス内の文字候補列を文字認識結果として出力するようにしてもよい。文字認識結果を出力するとは、例えば、プリンタ等の印刷装置で印刷すること、ディスプレイ等の表示装置に表示すること、メモリーカード等の記憶媒体に記憶すること、他の情報処理装置へ渡すこと等が含まれる。
【００４０】
図３の例に示した実施の形態は、以下のように把握することもできる。
（１）画像から文字画像を切り出す位置を抽出する切出位置抽出手段と、前記切出位置抽出手段によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する文字候補抽出手段と、前記文字候補抽出手段によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段を具備することを特徴とする情報処理装置である。
この情報処理装置によれば、画像から文字を認識する場合にあって、本構成を有していない場合に比較して、精度が高い文字認識結果を出力することができる。
【００４１】
（２）前記限定手段によって限定されたリンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成するリンク値生成手段と、前記リンク値生成手段によって生成されたリンク値に基づいて、前記ネットワーク生成手段によって生成されたネットワーク内のパスを選択するパス選択手段を具備し、前記出力手段は、前記パス選択手段によって選択されたパス内の文字候補列を文字認識結果として出力することを特徴とする（１）に記載の情報処理装置である。
この情報処理装置によれば、各文字画像の１つだけの文字認識結果によって認識文字列を決定してしまうことを防止することができる。
【００４２】
（３）前記リンク値生成手段は、前記リンクを構成しているノードに対する文字らしさを表す値に基づいて、前記リンク値を生成することを特徴とする（２）に記載の情報処理装置である。
この情報処理装置によれば、文字列らしさを表す値と文字らしさを表す値を用いてリンク値を生成することができる。
【００４３】
（４）前記切出位置抽出手段は、複数の切り出し位置を抽出し、前記ネットワーク生成手段は、前記切出位置抽出手段によって抽出された複数の切り出し位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成することを特徴とする（２）又は（３）に記載の情報処理装置である。
この情報処理装置によれば、複数の切り出し位置に対しても文字認識結果を出力することができる。
【００４４】
（５）前記限定手段は、最初のリンクから前記文字列パターンに合致していない場合、該合致していないリンクの次のリンクから該文字列パターンに合致するリンクに限定することを特徴とする（１）から（４）のいずれか一項に記載の情報処理装置である。
この情報処理装置によれば、最初に誤った文字認識結果がある場合であっても、文字列パターンに合致する文字認識結果を出力することができる。
【００４５】
（６）前記限定手段は、前記文字列パターンに合致するリンクがない場合は、該文字列パターン内の一部分の文字列パターンに合致するリンクに限定することを特徴とする（１）から（５）のいずれか一項に記載の情報処理装置である。
この情報処理装置によれば、文字列パターン内の一部分の文字列パターンに合致する文字認識結果を出力することができる。
【００４６】
（７）コンピュータを、画像から文字画像を切り出す位置を抽出する切出位置抽出手段と、前記切出位置抽出手段によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する文字候補抽出手段と、前記文字候補抽出手段によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段として機能させるための情報処理プログラムである。
この情報処理プログラムによれば、画像から文字を認識する場合にあって、本構成を有していない場合に比較して、精度が高い文字認識結果を出力することができる。
【００４７】
図４は、対象とする帳票４００の例を示す説明図である。この帳票４００には、名前枠４１０、住所枠（市前）４２０と住所枠（市後）４３０が設定されている。この帳票４００への記載者は、名前枠４１０には名前を記入する。また、住所枠（市前）４２０と住所枠（市後）４３０には住所を記載する。その結果、名前枠４１０内には、名前のみが記入されていると仮定することができる。又は、住所枠（市前）４２０、住所枠（市後）４３０内には住所のみが記入されていると仮定することができる。
このように、枠に記載されるはずの文字、又は単語が限定される場合には、自由に記載可能な場合よりも認識率を上げることができる。例えば、住所などの場合で、図４の例のように、住所枠（市前）４２０内に市の名前を書くように指定されている場合を考える。市の名前は限定されているので、それに限定すれば、より精度が上がる。ここで、例えば、住所枠（市前）４２０内に記載される可能性のある市名が、下記３つに限定されているとする。
（１）横浜
（２）川崎
（３）横須賀
ここで、住所枠（市前）４２０内に記載される文字列は、この３パターンに限定されているということができる。
【００４８】
このような、文字列パターンの限定を指定する手法（限定文字列パターン１０８を指定する手法）の例として、正規表現がある。正規表現には種々の表記法があるが、一例として、正規表現の表記方法を図５に例示する。図５は、正規表現表記規則５００の例を示す説明図である。正規表現表記規則５００は、規則欄５１０内の表記を、意味欄５２０で説明している。
例えば、前記のように、「横浜」、あるいは、「川崎」、あるいは、「横須賀」のみを対象とする場合、正規表現としては、
「横浜｜川崎｜横須賀」
と記述すればよい。
【００４９】
特許文献２に記載の技術では、文字位置毎に、字種を限定させて、精度を上げる例が述べられている。
前述の市名の例では、
・１文字目には、「横」、「川」のみ
・２文字目には、「浜」、「崎」、「須」のみ
・３文字目には、「賀」のみ
しかあり得ない。この条件を利用する。例えば、１文字目には、「横」と、「川」しかあり得ないので、それのみを出力するように設定する。このようにすることによって、認識率の精度を上げることが可能となる。例えば、「横」は、「黄」と字が似ており、正解は「横」であるのに、「黄」と誤認識する可能性があるが、出力文字を、「横」と「川」に限定することで、「黄」の出力を禁ずることとなっている。
【００５０】
さらに、特許文献３に示すように、複数の文字候補を１文字目から見ていく方法もある。
１つの文字を認識する場合、複数の認識候補を得ることができる。複数の文字候補には、第１候補から、第ｎ候補までの、順位が付けられている。第１候補が最も確度の高い候補であり、数値が大きくなるに従って、認識の確度は低下する。特許文献３に記載の技術では、１文字目の第１候補から順に、正規表現にマッチするものを探索していく。ここで、決定するのは１文字目であるとする。１文字目の、第１候補が正規表現にマッチすれば、その候補を選択する。第１候補が正規表現にマッチしない場合、第２候補をチェックする。以降、正規表現にマッチするまで、第２、第３と、順に候補を探索する。正規表現にマッチする候補がない場合は、終了する。正規表現にマッチする候補がある場合その候補を選択する。候補を選択した後では、２文字目の選択を行う。ここではすでに１文字目の選択が行われているため、１文字目と合わせて、２文字の文字列が正規表現にマッチするような文字を選択する必要がある。ここで、１文字目と同様に、２文字目の第１候補から順に探索する。正規表現にマッチした段階で、その候補を選択する。
この方法であれば、複数の文字候補があっても、最終的に正規表現にマッチする文字列を選択することができる。
【００５１】
例えば、各文字と、その認識文字候補が、図６の例のようになっているとする。つまり、３つの各文字について、３つの文字認識候補がある例である。また、この場合の、正解は、「横須賀」であるとする。また、出力文字パターンとしての正規表現は、
「横浜｜川崎｜横須賀」
であるとする。
この例では、１文字目は第２候補、２文字目は第２候補、３文字目は第１候補を選択することで、正解出力を得ることができる。
特許文献２に記載の技術では、予め文字位置に応じて、出力される文字候補を決める。特許文献２に記載の技術での出力候補は、図７の例に示すハッチング部を除いた出力の中で、最も順位の高いもの（第１候補の方が第２候補よりも順位が高いとする）を出力することになる。結局、特許文献２に記載の技術では、「横浜賀」が出力されることとなる。
【００５２】
特許文献３に記載の技術では、１文字目では、正規表現に合致するのは「横」であるため、「横」が選択される。２文字目では、最も順位の高く、かつ正規表現に合致するのは、「浜」であるため、「浜」が出力される。３文字目では、正規表現に合致する文字はない。「横浜賀」という単語は、出力文字パターン「横浜｜川崎｜横須賀」の中にはないためである。そのため、特許文献３に記載の技術では、出力なしということになるか、あるいは、「横浜賀」の中で、最長一致の「横浜」が出力されることになる。
【００５３】
特許文献２、特許文献３に記載の技術では、文字列の１文字目、かつ、第１候補から、順に正規表現（あるいは、正規表現のような文字列パターン指示方法。以下、正規表現として示す）に合致する文字を選択している。
本実施の形態では、文字認識候補のあり得る文字列のうちから、正規表現に合致するパターンを探索するものである。そして、そのためにビタビ法を用いるようにしてもよい。
【００５４】
図８は、本実施の形態による処理例を示すフローチャートである。
ステップＳ８０２では、画像受付モジュール３１０が、対象となる画像を受け付ける。
ステップＳ８０４では、文字列抽出モジュール３２０が、画像から文字列画像を抽出する。
ステップＳ８０６では、切出位置抽出モジュール３３０が、文字列画像を対象として切り出し位置を抽出する。
ステップＳ８０８では、文字候補抽出モジュール３４０が、切り出された文字画像を文字認識する。
ステップＳ８１０では、文字候補抽出モジュール３４０が、複数の文字認識結果を文字画像の文字候補として抽出する。
ステップＳ８１２では、パス限定処理モジュール３５０が、ネットワークを生成し、その中のパスを限定する。
ステップＳ８１４では、出力モジュール３６０が、文字認識結果を出力する。
【００５５】
次に、図９から図２８を用いて、パス限定処理モジュール３５０による処理を説明する。
本実施の形態は、さらに、パス評価値の高いパスを出力することによって、文字切り出し位置の確定、又は文字認識を行うものである。また、パスの探索にダイナミックプログラミングの手法を用いてもよい。
本実施の形態のネットワークにおいては、始点ノード、終点ノード、複数の中間ノードがある。また、各ノード間のリンクには、リンク値を与える。始点ノードから１あるいは複数の中間ノードを介して、終点ノードに至るパスは、介するノードに依存したリンクを通ることになる。始点ノードから終点ノードに至るパスのパス評価値は、そのパスが通ったリンクのリンク値の重み付け和として表すことができる。
本実施の形態のパス限定処理モジュール３５０は、１つの文字画像に対して、複数の文字認識結果が存在しているときに、前述のノード、リンク、パスの構成（ネットワーク構造）を生成するものである。ネットワーク構造が与えられれば、パス限定処理モジュール３５０によってビタビ法などの手法を用いて、最適パスを探索することが可能となる。
【００５６】
＜Ａ１．文字切り出し位置が固定の場合＞
まず、切出位置抽出モジュール３３０の抽出する文字切り出し位置が固定（一種類）の場合について説明する。
図９は、記号例を示す説明図である。記号の種類として、長方形９１０、横棒である接続線９２０、９２２、９２４、９２７、９２８、円弧９３０、丸である文字候補９４２、９４４、９４６がある。
図９の例において、長方形９１０Ａ、９１０Ｂ、９１０Ｃ、９１０Ｄ（図１０に例示する長方形９１０）は、それぞれ文字セグメントを表す。
また、横棒である接続線９２０、９２２、９２４、９２６、９２８は、文字切り出し位置を示す（図１１に例示する接続線９２０、接続線９２２）。文字セグメントは文字切り出し位置を介して、隣接する文字セグメントにつながっている。
さらに、丸で表されている文字候補９４２Ａ、９４４Ａ等は、１つの文字セグメントを１文字として認識したときの、複数の文字候補を示す。円弧９３０Ａ、９３０Ｂ、９３０Ｃ、９３０Ｄは、下の１つの文字セグメントだけを対象に文字認識を行っていることを示している。
【００５７】
図１２の例では、文字候補９４２、９４４、９４６は、その下の長方形９１０が示す１文字の文字セグメントを認識したときの複数の文字候補であることを示している。また、円弧９３０は、その下の長方形９１０１つだけを対象に文字認識を行うことを示している。
本実施の形態では、文字セグメントの複数の文字候補をノードとして捉える。さらに、隣接する文字セグメントの文字候補と、リンクを接続する。図１３の例にリンクを太線で記入して示す。
ここでリンク値生成処理が生成するリンク値としては、リンク左右のノードの相互作用を示すものを使ってもよい。具体的には、リンクの左の文字候補とリンクの右の文字候補が連続して日本語の文章中に出現する確率（バイグラム）を用いる。
このようにノードとリンクを構成することによって、すべてのネットワーク構造が規定できる。ネットワーク構造が規定できれば、ビタビ法等により、最適パスを選択できる。
【００５８】
＜Ａ２．ノード内情報も用いる場合＞
前述では、リンク値として、ノード間の相互作用を示すもの（文章中に出現する確率）だけを用いたが、さらにノード単独の評価値を用いるようにしてもよい。ここでは、ビタビ法を用いて最適パスを探索するものとする。左から順にノードの左から入るリンクをノード毎に１つだけに限定していく処理を行う。
今、図１３の例で文字候補９４２Ｂ、９４４Ｂ、９４６Ｂのリンクを限定する段階であるとする。
ここで、文字候補９４２Ｂ、９４４Ｂ、９４６Ｂと、左側にある文字候補９４２Ａ、９４４Ａ、９４６Ａ間のリンク値を生成する。リンク値としては、各ノード間の相互作用を表すバイグラムなどの値と、各ノード内部の値の両方を用いる。ノード内部の値とは、例えば、文字候補９４２Ｂの文字の認識確度などがある。
【００５９】
ここで、リンクは、文字候補９４２Ｂ、９４４Ｂ、９４６Ｂと文字候補９４２Ａ、９４４Ａ、９４６Ａ間にあるため、リンク値としては、文字候補９４２Ｂ、９４４Ｂ、９４６Ｂと文字候補９４２Ａ、９４４Ａ、９４６Ａ間の評価値を算出するのが簡単である。しかし、ノード内部の値は、文字候補９４２Ｂ、９４４Ｂ、９４６Ｂと文字候補９４２Ａ、９４４Ａ、９４６Ａ間にあるのではなく、この場合、文字候補９４２Ｂ、９４４Ｂ、９４６Ｂに存在する。
つまり、ノード間情報はリンクの内部に存在していて、ノード内情報はリンクの端点に存在する。このような発生位置、又は概念が異なる値を一度に扱う。
【００６０】
従来では、図３４に示す始点ノード３４００、中間ノード３４１０（ノード１）、中間ノード３４２０（ノード２）、終点ノード３４９０など（つまり、文字切り出し位置）をノードとして、ノード間のアーク評価値を算出している。本実施の形態のように、複数の文字コードをノードとして、ノード間のリンク値を算出するわけではない。そのため、従来技術をそのまま用いることはできない。
本実施の形態では、リンクの評価値として、リンクの内部に存在する値（例えば、バイグラムの値）と、リンクの一方の端点のみに存在する値（例えば、文字候補９４２Ｂの文字認識確度）を用いる。他方の端点に存在する値（例えば、文字候補９４２Ａの文字認識確度）は用いない。このようにすることで、リンクの内部の値と、リンクの端点の値をともに用いる評価が可能となる。
最終的には、文字列の評価値（パス評価値）として、（１）式で、すべてのリンクの評価値を加算することになる。そのため、リンクの評価値の中に、リンクの内部の評価値と、リンクの一方の端点の評価値が含まれていれば、パス評価値の中にすべてのリンク内部の評価値とリンク端点の評価値が１つずつ含まれることになる。
【００６１】
リンク値生成処理では、前述のリンク内部の値と、リンク端点の値のように、複数の値（バイグラムや認識確度）などを特徴量として、リンク値を算出すればよい。このように複数の値から、１つのリンク値を算出する方法としては、（１）特開平９−１８５６８１号公報、（２）特開昭６１−１７５８７８号公報、（３）特開平３−３７７８２号公報、（４）特開平１１−２０３４０６号公報等に記載の技術を用いればよい。これ以外の方法であってもよい。
なお、複数の値を特徴量ベクトルとして把握し、リンク値は、特徴量ベクトルを対象として、リンク評価値（スカラー値）を出力する関数で実現できる。
【００６２】
＜Ａ３．リンク情報として２以上のノードを用いる場合＞
前述では、リンク左右のノードの相互情報としてバイグラムを用いていた。この場合、リンク情報として２つのノード間の関係情報を用いていることになる。
ビタビ法を用いる場合、例えば、ノードである文字候補９４２Ａ、９４４Ａ、９４６Ａの左側のリンク数はすでに１個に限定されていることになる。この場合には、２以上のノードの情報を用いてリンク情報を構築することが可能となる。
例えば、２つの連続する文字の生起確率であるバイグラムではなく、３つの連続する文字の生起確率であるトライグラムを用いることも可能となる。
今、リンク値生成処理では、ノードである文字候補９４２Ｂ、９４４Ｂ、９４６Ｂの左側のリンク値を生成しようとする。
例えば、文字候補９４２Ａ−文字候補９４２Ｂ間のリンク値を算出する。バイグラムであれば、文字候補９４２Ａと文字候補９４２Ｂが連続する生起確率を求めればよい。ここで、トライグラムを求める場合を説明する。文字候補９４２Ａの左側のリンクは１つに限定されているため、実は、文字候補９４２Ａの左の文字も確定していることになる。この文字を保持するノードをＧとする。トライグラムとしては、ノードＧ−ノード（文字候補９４２Ａ）−ノード（文字候補９４２Ｂ）の３つの文字に関する生起確率を求めればよい。
以上のように求めたトライグラムをノード（文字候補９４２Ａ）−ノード（文字候補９４２Ｂ）間のリンク値として生成すればよい。同様に、Ｎｇｒａｍであっても、求めることが可能となる。
【００６３】
＜Ａ４．文字切り出し位置が確定していない場合＞
文字切り出し位置が確定していない場合（つまり、切出位置抽出モジュール３３０が複数の文字切り出し位置を抽出した場合であり、具体的には、「化」のように、「イ」と「ヒ」、あるいは、「化」のどちらになるか分からない場合）、文字候補の選択と、文字切り出し位置の選択を行うようにしてもよい。文字切り出し位置が確定していない場合、文字候補の選択は、文字切り出し位置の選択となる。
図１４は、文字切り出し位置が複数ある場合の処理例を示す説明図である。ここでは、円弧の記号の意味が追加されている。円弧が下にある複数の文字セグメント（長方形）を指し示す場合、その円弧はその複数の文字セグメントを統合した画像を１文字とみなして認識することを示す。円弧１４１０Ａは、長方形９１０Ａと長方形９１０Ｂを統合した画像を１文字とみなして文字認識結果として文字候補１４２２Ａ、１４２４Ａ、１４２６Ａを有している。また、円弧１４１０Ｃは、長方形９１０Ａ、９１０Ｂ、９１０Ｃ、９１０Ｄを統合した画像を１文字とみなして文字認識結果として文字候補１４２２Ｃ、１４２４Ｃ、１４２６Ｃを有している。
図１５の例に示すように、円弧９３０Ａと円弧９３０Ｂの下に２つの文字セグメント（長方形９１０Ａ、長方形９１０Ｂ）「イ」と「ヒ」がある場合に、その２つを含む円弧１４１０の上の文字候補（文字候補１４２２、１４２４、１４２６）は、「イ」と「ヒ」を統合した１つの文字セグメント「化」を認識したときの複数の文字候補に相当する。
【００６４】
文字切り出し位置が確定していない場合のリンクの接続は、図１６の例に示すようになる。図１６は、文字切り出し位置が複数ある場合の処理例を示す説明図である。
ここでは、文字切り出し位置に注目する。今、図１６の矢印で示す文字切り出し位置に関連するノードのリンクを対象とする。この文字切り出し位置でリンクされるノードには、
（１）左側ノード：矢印の文字切り出し位置に円弧の右側が存在するノード（斜線でハッチングしたノード、文字候補１６４２Ａ、文字候補１６４４Ａ、文字候補１６６２Ａ、文字候補１６６４Ａ、文字候補１６７２Ａ、文字候補１６７４Ａ等）と、
（２）右側ノード：矢印の文字切り出し位置に円弧の左側が存在するノード（内部が白のノード、文字候補１６４２Ｂ、文字候補１６４４Ｂ、文字候補１６６２Ｂ、文字候補１６６４Ｂ、文字候補１６７２Ｂ、文字候補１６７４Ｂ等）
の２種類がある。このとき、左側ノードと、右側ノード間にリンクを形成することによって、グラフ構造を構築することができる。
例えば、すべての左側ノードが、すべての右側ノードに直接接続できるようにリンクを形成すればよい。さらに、すべての文字切り出し位置において、前述のように、左側ノードと右側ノードのリンクを形成し、さらに、左側が文字列の端点の場合には始点ノードに接続し、また、右側が文字列の端点の場合には終端ノードに接続すれば、すべてのグラフ構造を構築することができる。
【００６５】
この場合においても、リンク値は、リンク左右のノードの相互作用を示すものを使ってもよいし、ノード内部の評価値を用いてもよい。
特に、この場合には、文字切り出し位置が確定していないため、ノード内部の評価値として、文字の形状情報を用いることができる。文字形状情報の例として、文字の縦横比や、文字左右の空白量、等を用いることができる。
【００６６】
このようにすることによって、文字列の左端から、文字列の右端に至るすべてのパスを書き出すことができる。各パスは、認識出力文字列に該当する。つまり、文字列を構成するネットワークにおいて、左端ノードから、右端ノードへ至るパスを決定することによって、文字列を決定できることになる。
【００６７】
以上をまとめると、文字列を構成するネットワークは、例えば、図１７のようになる。図１７の例において、○は、ノードを示す。○と○を接続する実線は、ノード間の接続を示すアークあるいはリンクである。ノードＡは、文字列の左端を示し、ノードＢは、文字列の右端を示す。このネットワークにおいて、左端ノードＡから、右端ノードＢへ至るパスを決定することによって、文字列を決定できることになる。
【００６８】
これらのパスの中で、正規表現にマッチするものだけを出力するようにすればよい。しかしながら、パスの数は膨大であるので、すべてのパスに対して正規表現にマッチしているかどうかをチェックすることは現実的ではない。
そこで、ビタビ法を用いて高速化する。
前述したように、あるノードに左から接続されるリンクの本数を１本に限定するようにしていく。もちろんのことながら、あるノードに右から接続されるリンクの本数を１本に限定するようにしてもよいが、以下の例では、左から接続されるリンクについて説明する。
ここで、あるノードに左から接続されるリンクを決定すれば、そのノードに至る出力文字列が確定できる。この出力文字列が正規表現に部分一致しているかどうかをチェックすればよい。
【００６９】
まず、あるノードに左から接続されるリンクが、Ｎ本あるとする。Ｎ本のリンクのうち、正規表現に部分一致しているものだけを抽出し、部分一致していないものを捨てる。
図１８の例を用いて説明する。図１８は、文字列を構成するネットワーク内のノードが接続されている例を示す説明図である。
例えば、ノードＤ（文字候補「会」）に左から３本のリンクが接続されているとする。そして、そのリンクはそれぞれノードＡ（文字列候補「ヒ学」）、ノードＢ（文字列候補「化学」）、ノードＣ（文字列候補「ト学」）から接続されているとする。ここで、正規表現が、「化学会議」とされているとする。
ノードＡ、Ｂ、Ｃには、さらに左からノードが接続されているが、その部分は説明では省略している。ノードＡ、Ｂ、Ｃに関しては、すでに、左側のノードが１本に限定されているため、それらのノードに至るパスが確定している。そのため、それらのノードに至る文字列も確定している。ノードＡの文字列候補は「ヒ学」、ノードＢの文字列候補は「化学」、ノードＣの文字列候補は「ト学」となっている。
ここで、ノードＤに左から接続されるリンクを確定させる。ノードＡからのパスであれば、文字列は「ヒ学会」であり、ノードＢからのパスであれば、文字列は「化学会」であり、ノードＣからのパスであれば、文字列は「ト学会」となる。この中で、正規表現である文字列パターンに部分一致するものを選択する。
【００７０】
ここで、文字列が文字列パターンに部分一致するとは、文字列が、正規表現「化学会議」の先頭から連続する部分に一致すればよいというものである。例えば、「化学会」は、正規表現「化学会議」の最初から３文字目までは一致するので、部分一致しているとする。その他の、「ヒ学会」、「ト学会」は部分一致しない。
したがって、部分一致とは、文字列がＸであるとき、Ｘの後ろに任意の文字が続くとみなして、後ろに任意の文字が続く文字列が先頭から正規表現に一致しているかどうかを判断するとしてもよい。
【００７１】
ここで、部分一致しているものが複数ある場合には、正規表現を用いた方式とは別のやり方で最も評価値の高いものを選択すればよい。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。
さらに、部分一致しているものがない場合には、すべての候補の中から、正規表現とは異なる方法で最も評価値の高いものを選択すればよい。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。
以上のようにして、各ノードにおいて、左側のリンクを１つに絞る。最終的に、左端から右端に向かう複数のパスが残るので、その中から出力すべきパスを得ればよい。
【００７２】
＜パス限定処理モジュール３５０の例１＞
図１９は、パス限定処理モジュール３５０内のモジュール構成例を示す説明図である。パス限定処理モジュール３５０は、ネットワーク構築処理モジュール１９１０、ノード数限定処理モジュール１９２０、制御モジュール１９３０、出力決定処理モジュール１９４０を有している。
図２０は、パス限定処理モジュール３５０による処理例を示すフローチャートである。
ステップＳ２００２では、ネットワーク構築処理モジュール１９１０が、ネットワークを構築する。
ステップＳ２００４では、ノード数限定処理モジュール１９２０が、制御モジュール１９３０による制御によって、ネットワーク内のノードを限定する。
ステップＳ２００６では、出力決定処理モジュール１９４０が、出力すべきパスを決定する。
【００７３】
ネットワーク構築処理モジュール１９１０は、ノード数限定処理モジュール１９２０と接続されている。ネットワーク構築処理モジュール１９１０は、文字候補抽出モジュール３４０によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成する。つまり、前述したように、文字列の一方の端（例えば、左端）から他方の端（例えば、右端）に至るネットワークを構築する。
ノード数限定処理モジュール１９２０は、ネットワーク構築処理モジュール１９１０、制御モジュール１９３０、出力決定処理モジュール１９４０と接続されている。ノード数限定処理モジュール１９２０は、ネットワーク構築処理モジュール１９１０によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する。つまり、前述したように、各ノードにおいて、例えば左から接続されるノード数を限定する処理を行う。例えば、限定するノード数として１つである。
【００７４】
制御モジュール１９３０は、ノード数限定処理モジュール１９２０と接続されている。制御モジュール１９３０は、ノード数を限定するノード位置を左から順になるように制御するものである。
本実施の形態では、制御モジュール１９３０において、右端の終点ノードにおけるノード数を１本に限定する処理は行わない。すなわち、右端の終点ノードに入るリンク数（アーク数）が、Ｍ本であれば、最終的にＭ本のパスが残ることになる。Ｍ本のパスは、Ｍ個の文字列に相当している。
【００７５】
出力決定処理モジュール１９４０は、ノード数限定処理モジュール１９２０と接続されている。出力決定処理モジュール１９４０は、ノード数限定処理モジュール１９２０によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する。つまり、前述のＭ個の文字列の中から、出力すべき文字列を選択する。例えば、図１７の例では、右端の終点ノードＢに３つのリンクが接続されている場合、３本の文字列候補が残ることになる。この３つの候補から出力すべき文字列を選択する。
このようにするのは、途中の部分一致では、文字列の後ろ側に一致していない文字数を評価することができないためである。文字列全体として、文字列の前側と後ろ側の不一致数を合わせて不一致数の最も少ないものを選択するため、Ｍ個の文字列に関して、評価を行う。
また、制御モジュール１９３０において、右端の終点ノードにおける入力ノード数を１本になるまで選択してもよい。出力決定処理モジュール１９４０では、その１本化した文字列の中から、正規表現にマッチする最も長い部分がある文字列を選択する。
【００７６】
「出力すべき文字列」を選択する評価尺度は、さまざまあって、下記のいずれか等を選択すればよい。
（１）評価尺度１
正規表現に最長一致するものを選ぶ。
最長一致するものが複数ある場合には、最もパス評価値の高い文字列を選ぶ。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。
変形例として、最長一致するものの文字数が所定の文字数未満である場合は、リジェクトとする。
（１．１）変形例（その１）
文字列の左端や右端が正規表現に一致しない場合、その一致しない左端や右端を除いた部分を抜き出して、その部分のみを正規表現に一致したとして、出力する。例えば、正規表現が「化学会議」で、文字列が「ＡＢ化学会議Ｃ」の場合、「ＡＢ」と「Ｃ」を取り除いた「化学会議」を出力する。このとき、取り除いた左端「ＡＢ」と右端「Ｃ」の文字数は計３文字となる。この取り除いた文字数が最も少ない文字列を選択する。
（１．２）変形例（その２）
前述の例で、「化学会議」となっている画像中の文字列の長さ（例えば、画像の画素数や、スキャン前の紙におけるセンチ数など）が最も長いものを選択してもよい。つまり、除去するノイズの量が画像中で最も小さいものを選択する。
【００７７】
（２）評価尺度２
正規表現に合致する文字列の長さは規定せず、正規表現に合致するものの中で、最もパス評価値の高い文字列を選ぶ。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。
出力文字列の中に、正規表現にマッチする部分があればよい。例えば、正規表現が「化学会議」であるとして、文字列が、「前化学会議Ａ」であるとき、１文字目と６文字目を省いて、「化学会議」という部分だけを出力することになる。
また、正規表現に完全に一致するときのみ採用するとしてもよい。
【００７８】
（３）評価尺度３
左端から右端までの全文字列が正規表現に一致すれば、その文字列を出力する。複数のパスが合致する場合は、最もパス評価値の高い文字列を選ぶ。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。ただし、左端から右端までの全文字列の中で、正規表現に一致するものがない場合は、出力がない（リジェクト）とする。
【００７９】
＜パス限定処理モジュール３５０の例２＞
前述のパス限定処理モジュール３５０の例１では、文字列の左端から、部分一致するノードを選択することになる。
ところが、部分一致では、文字列の先頭から、正規表現に一致する必要がある。
文字列の先頭部分には、ノイズが発生する場合が多い。ノイズが発生した場合には、文字列の最初から部分一致する文字列が存在しない場合がある。例えば、文字列の最初に縦棒のノイズが存在している場合、多くの出力文字列の１文字目に、「１」という文字が入ってしまう場合がある。
このような場合、ネットワーク構築処理で構築されたすべてのパスが部分一致しないことになってしまい、正規表現のマッチングが不可能となる。部分一致とは、文字列の先頭から一致することであるためである。
そこで、文字列の最初にノイズが混入した場合の不安定性を排除することを行う。
【００８０】
そのために、ノード数を限定する処理として、各リンクに対して、下記の処理を行う。
（１）Ｉ＝１とする。
（２）文字列のＩ文字目から部分一致しているかどうかをチェックする。
（３）部分一致していれば終了。
（４）Ｉが文字列の最後であれば終了。
（５）部分一致していなければ、Ｉ＝Ｉ＋１として（２）に戻る。
そして、変数Ｉの値を用いて、各リンクに対して、何文字目から部分一致したかを計測する。その計測したＩを用いて、ノード数限定処理モジュール１９２０における処理では、下記の方法によって入力ノード数を限定する。
・部分一致しているパスの中で、Ｉの値が最も小さい入力ノードを選ぶ。
・部分一致しているパスの中で、最も小さいＩの値が複数ある場合（Ｉの値が同じ場合）、パス評価値が最も大きなノードを選ぶ。
・部分一致しているパスがない場合、パス評価値が最も大きなノードを選ぶ。
このようにすることで、文字列の最初にノイズが混入した場合の不安定性を排除する。
【００８１】
＜パス限定処理モジュール３５０の例３＞
また、パス限定処理モジュール３５０は、正規表現に完全に一致する文字列がない場合、部分一致文字列を出力するようにしてもよい。
前述のパス限定処理モジュール３５０の例１、２では、与えられた文字列パターン（正規表現）に一致するパス（文字列）を出力していた。ただし、一部でもよいから、一致するものを出力したいという場合もあり得る。例えば、前述の市名の例で、図２１の例のような認識結果が得られたとする。また、正解は「横浜」であるとする。
【００８２】
この場合、「横浜」となるパスは存在しないので、正規表現にマッチする文字列を出力することはできない。
文字認識後に、人間が認識結果を修正する場合がある。出力されない場合（リジェクトされる場合）、人間は「横浜」と２文字を入力する必要がある。ところが、「横」という文字は文字認識結果として存在している。「横」だけでも出力できれば、人間は、「浜」の１字だけを入力すればよいことになる。
パス限定処理モジュール３５０は以下の処理を行う。
（１）部分一致を検証するときに、部分一致する文字列の文字長が最長になる場合を記録しておく。文字列そのものか、パスの位置を記録しておけばよい。
（２）出力決定処理モジュール１９４０における処理において、正規表現にマッチする文字列があれば、それを出力する。
（３）出力決定処理モジュール１９４０における処理において、正規表現にマッチする文字列がない場合、部分一致文字長が最長となる文字列を出力する。
そして、文字認識結果を確認、修正する操作者には、部分一致でも出力するか否かの判断を表示装置に提示し、部分一致でも出力するが選択された場合は、（３）の処理を行うようにしてもよい。
【００８３】
以上、述べたように、図２２に示されるような、限定文字列パターン検査処理が行われる。つまり、前述のパス限定処理モジュール３５０に該当する限定文字列パターン検査処理モジュール２２００は、限定文字列パターン１０８と対象文字列１１８を受け付けて、検査結果１６２を出力する。
限定文字列パターン１０８は、文字列パターンを限定するための情報であり、典型的には、前述した正規表現が該当する。
限定文字列パターン検査処理モジュール２２００では、限定文字列パターン１０８と対象文字列１１８を受け付ける。対象文字列１１８が限定文字列パターン１０８に合致すれば、検査結果１６２として、「合致」を出力する。対象文字列１１８が限定文字列パターン１０８に合致しなければ、検査結果１６２として、「非合致」を出力する。
検査としては、以下の２種類がある。いずれかの検査を行う。
（検査１）文字列が完全に合致する場合のみを「合致」として、それ以外を「非合致」とする完全検査。
（検査２）文字列と限定文字列パターン（正規表現）が、従来技術で述べた部分一致する場合も、「合致」とし、それ以外を「非合致」とする部分一致検査。
【００８４】
例えば、限定文字列パターン１０８として正規表現を採用し、その内容を、
横浜｜川崎｜横須賀
とする。
完全検査の場合、「対象文字列１１８が、「横浜」であるときは、検査結果として、「合致」を出力する」、又は、「対象文字列１１８が「黄浜」のときや、対象文字列１１８が「横」のとき、検査結果１６２として、「非合致」を出力する」、等の動作を行う。
部分一致検査の場合、「対象文字列１１８が、「横浜」や、対象文字列１１８が「横」のときは、検査結果１６２として、「合致」を出力する」、又は、「対象文字列１１８が「黄浜」のとき、検査結果１６２として、「非合致」を出力する」、等の動作を行う。
「対象文字列１１８が「横」であるときは、検査結果１６２として、「合致」を出力する」、又は、「対象文字列１１８が「黄浜」のときは、検査結果１６２として、「非合致」を出力する」、等の動作を行う。
前述の処理を実現するためには、このような、限定文字列パターン検査処理を行う。
ここで、限定文字列パターン１０８が長大である場合がある。例えば、都道府県名を限定文字列パターン１０８として受け付ける場合、５０個程度の県名を、論理和を示す記号「｜」をはさんで記入する必要がある。市名であれば、１０００個程度オーダー数の市名を、論理和を示す記号「｜」をはさんで記入する必要がある。
このような長大な正規表現を処理することが必要である。特に図３６の例に示すような複数のパスの中から最適なパスを選ぶような処理を行う場合、限定文字列パターン検査処理の処理回数が多くなり、そのため、全体の処理量や処理時間も増大することとなる。
【００８５】
ここで、限定文字列パターン１０８を正規表現として、対象文字列１１８が正規表現に合致しているかどうかを検査する場合について説明する。正規表現は汎用的なパターンの記述方法であるため、パターンの記述の仕方によっては、合致／非合致の検査の処理が低速になる。
そこで、本実施の形態では、限定文字列パターン１０８の記述を分解する。
限定文字列パターン１０８が、文字列の単純な羅列で与えられた場合を対象とする。例えば、図２３の例に示すように、限定したい文字列（文字列（横浜）２３１０、文字列（川崎）２３２０、文字列（横須賀）２３３０）が単純に並んでいる場合（つまり、論理和として文字列が接続されている場合）について説明する。
以下、このような文字列の羅列を文字列集合と呼ぶ。
文字列集合は、前述したような、何かの記号で分離可能なテキストコードであってもよいし、文字列の配列であってもよいし、その他の、集合を表現可能なデータ形式であればよい。
データ集合Ａがあって、入力データｘが、集合Ａ内のデータと一致するかどうかを判定するようなアルゴリズムが種々存在している。このようなアルゴリズムを用いて、前述したような文字列集合との合致を判定することができる。
例えば、２分木検索、赤黒木検索、トライ木検索、ハッシュ法等などの方法を用いることができる。
【００８６】
一例をあげる。文字列は、辞書順に順番を付けることが可能である（つまり、ソートできる）。文字列集合をソートして、２分木構造とする。
図２４の例は、文字列集合を２分木構造として例を示す図である。図２４において、○は、ノードを示す。各ノードは最大２つの子ノードを持つ。例えば図２４において、ノード８は、ノード４とノード１２を子に持つ。
２分木探索では、例えば、左の子＜親≦右の子となるように、木構造を作る。
このようにすると、対象とする文字列との大小関係を一番上の親ノードから参照していくことによって、Ｎ個の集合の場合に、ｌｏｇ２Ｎの回数で集合内にデータが存在するか否かを検査することが可能となる（図２４の場合）。
以上のように、順番を付けることのできる文字列に関して、単純に探索をする場合（Ｎ回の判定が必要）よりも、高速に検査することが可能となる。
【００８７】
正規表現では、汎用性を必要とするため、このような高速アルゴリズムの導入を行う。
例えば、
横浜｜川崎｜横須賀
の正規表現の場合、前述の文字列集合に対するアルゴリズムをそのまま適用し得る。しかし、例えば、
横浜｜（別の正規表現）｜須賀
のように、論理和記号の間に、別の正規表現による複雑な式が入っている場合もあり得る。その場合には、その複雑な式を、文字列集合として、辞書順に並べることはできない。少なくとも、正規表現の入れ子構造になるため、その分、低速となる。そのため、論理和記号の間にある文字列をすべて、文字列集合として、前述の文字列探索の高速アルゴリズムを適用することはできない。
そこで、本実施の形態では、限定文字列パターン１０８中の、文字列集合部分を抽出することを行う。つまり、文字列集合部分だけを抜き出して、その部分は、例えば、２分木探索を行う。
また、高速探索アルゴリズムを部分一致検査に用いることもできる。
そのためには、
対象文字列＋任意文字列
が、文字列集合内に存在しているか否かを判定すればよい。
文字列が辞書順に並んでいることを前提とすれば、
対象文字列＋任意文字列
は、
対象文字列
の次以降に並ぶことになる。
そのため、文字列集合中の文字列で、辞書順が対象文字列以上の値の文字列を発見し、その文字列の最初から対象文字列の文字数分だけ完全一致を判定すればよい。
【００８８】
図１は、本実施の形態（具体的には図３に例示したパス限定処理モジュール３５０）の構成例についての概念的なモジュール構成図である。本実施の形態である情報処理装置は、複数の文字列を対象として、その中から予め定められた正規表現で記載された文字列の型に合致する文字列を出力するものであって、図１の例に示すように、限定文字列パターン受付モジュール１１０、対象文字列受付モジュール１２０、文字列集合抽出処理モジュール１３０、文字列集合検査処理モジュール１４０、正規表現検査処理モジュール１５０、検査結果統合処理モジュール１６０を有している。
【００８９】
限定文字列パターン受付モジュール１１０は、文字列集合抽出処理モジュール１３０と接続されており、正規表現で記載された文字列の型である限定文字列パターン１０８を受け付ける。限定文字列パターン１０８は、図４、図５等を用いて前述した文字列パターンに該当する。限定文字列パターン１０８は予め定められており、例えば、郵便番号であるならば、３桁の数字、「−」、４桁の数字で構成される文字列パターンであることを示す正規表現であり、住所であるならば、住所としてあり得る文字列の集合等が該当する。
対象文字列受付モジュール１２０は、文字列集合検査処理モジュール１４０、正規表現検査処理モジュール１５０と接続されており、対象とする文字列である対象文字列１１８を受け付ける。対象文字列１１８は、例えば、文字認識結果の文字列等であるが、これに限定されるものではなく、操作者がキーボード等を用いて打ち込んだ文字列等であってもよい。
【００９０】
文字列集合抽出処理モジュール１３０は、限定文字列パターン受付モジュール１１０、文字列集合検査処理モジュール１４０、正規表現検査処理モジュール１５０、検査結果統合処理モジュール１６０と接続されている。文字列集合抽出処理モジュール１３０は、は、限定文字列パターン受付モジュール１１０によって受け付けられた限定文字列パターン１０８から文字列の集合である部分（文字列集合領域１３２）を抽出する。そして、文字列集合領域１３２を文字列集合検査処理モジュール１４０へ渡し、正規表現領域１３４を正規表現検査処理モジュール１５０へ渡し、論理関係１３６を検査結果統合処理モジュール１６０へ渡す。なお、正規表現領域１３４は、限定文字列パターン１０８から文字列集合領域１３２を除いた残りの部分であり、論理関係１３６は、限定文字列パターン１０８における文字列集合領域１３２と正規表現領域１３４の論理関係である。
例えば、限定文字列パターン１０８の正規表現として、文字列の集合の領域を示す特別な記号を用意する。ここでは、特別な記号として、「＜＜」、「＞＞」の例を示す。例えば、限定文字列パターン１０８として、
＜＜横浜｜川崎｜横須賀＞＞｜（他の正規表現）
である場合は、「＜＜」と「＞＞」で囲まれた部分を、文字列集合領域１３２として抽出する。つまり、文字列集合領域１３２として、「横浜｜川崎｜横須賀」を取り出す。これは、「横浜」、「川崎」、「横須賀」のいずれかであることを示している。なお、文字列の集合の領域を示す特別な記号に囲まれた領域を抽出する例を示したが、文字列が「｜」によって羅列されている領域を抽出するようにしてもよい。
また、前述の例では、「（他の正規表現）」の部分が正規表現領域１３４に該当する。そして、文字列集合領域１３２と正規表現領域１３４の間にある「｜」が論理関係１３６に該当する。
【００９１】
文字列集合検査処理モジュール１４０は、対象文字列受付モジュール１２０、文字列集合抽出処理モジュール１３０、検査結果統合処理モジュール１６０と接続されている。文字列集合検査処理モジュール１４０は、対象文字列受付モジュール１２０によって受け付けられた対象文字列１１８が文字列集合抽出処理モジュール１３０によって抽出された文字列集合領域１３２に合致しているか否かを判定する。例えば、文字列集合領域１３２に対して、２分木探索等の処理を行う。
また、文字列集合検査処理モジュール１４０は、対象文字列受付モジュール１２０によって受け付けられた対象文字列１１８の先頭から連続する部分が文字列集合抽出処理モジュール１３０によって抽出された文字列集合領域１３２に合致しているか否かを判定するようにしてもよい。部分一致に対応する処理である。
【００９２】
正規表現検査処理モジュール１５０は、対象文字列受付モジュール１２０、文字列集合抽出処理モジュール１３０、検査結果統合処理モジュール１６０と接続されている。正規表現検査処理モジュール１５０は、対象文字列受付モジュール１２０によって受け付けられた対象文字列１１８が文字列集合抽出処理モジュール１３０によって抽出された文字列以外の正規表現で記載された型に合致しているか否かを判定する。前述の例では、正規表現領域１３４である「（他の正規表現）」に記載された部分を用いて、対象文字列１１８が正規表現領域１３４に合致するか否かについての通常の正規表現による検査処理を行う。
【００９３】
検査結果統合処理モジュール１６０は、文字列集合抽出処理モジュール１３０、文字列集合検査処理モジュール１４０、正規表現検査処理モジュール１５０と接続されており、検査結果１６２を出力する。検査結果統合処理モジュール１６０は、文字列集合検査処理モジュール１４０による判定結果と正規表現検査処理モジュール１５０による判定結果を用いて、対象文字列受付モジュール１２０によって受け付けられた対象文字列１１８が限定文字列パターン受付モジュール１１０によって受け付けられた限定文字列パターン１０８に合致しているか否かを判定する。具体的には、文字列集合領域１３２と他の正規表現の領域である正規表現領域１３４との論理関係１３６を用いて最終的な検査結果１６２を出力する。前述の例である、
＜＜横浜｜川崎｜横須賀＞＞｜（他の正規表現）
では、論理関係１３６は「｜」（ＯＲ（論理和））となる。
【００９４】
以下、論理関係１３６に応じた検査結果１６２統合処理モジュール１６０の動作を詳述する。
（１）正規表現検査（正規表現検査処理モジュール１５０による処理）と文字列集合検査（文字列集合検査処理モジュール１４０）の結果に対する論理関係１３６がＡＮＤ（論理積）であり、正規表現検査を文字列集合検査の先に行う場合
対象文字列が正規表現に合致しているか否かを判定する。
（ア）正規表現に合致している場合、
（ア−１）文字列集合に合致している場合、合致として検査結果１６２を出力する。
（ア−２）文字列集合に合致していない場合、非合致として検査結果１６２を出力する。
（イ）正規表現に非合致の場合、非合致として検査結果１６２を出力する。
【００９５】
（２）正規表現検査と文字列集合検査の結果に対する論理関係１３６がＯＲであり、正規表現検査を文字列集合検査の先に行う場合
対象文字列が正規表現に合致しているか否かを判定する。
（ア）正規表現に合致している場合には、合致として検査結果１６２を出力する。
（イ）正規表現に非合致の場合、
（イ−１）文字列集合に合致している場合、合致として検査結果１６２を出力する。
（イ−２）文字列集合に合致していない場合、非合致として検査結果１６２を出力する。
【００９６】
（３）正規表現検査と文字列集合検査の結果に対する論理関係１３６がＡＮＤであり、正規表現検査を文字列集合検査の後に行う場合
対象文字列が文字列集合に合致しているか否かを判定する。
（ア）文字列集合に合致している場合、
（ア−１）正規表現に合致していれば、合致として検査結果１６２を出力する。
（ア−２）正規表現に合致していなければ、非合致として検査結果１６２を出力する。
（イ）文字列集合に非合致の場合、非合致として、検査結果１６２を出力する。
【００９７】
（４）正規表現検査と文字列集合検査の結果に対する論理関係１３６がＯＲであり、正規表現検査を文字列集合検査の後に行う場合
対象文字列が文字列集合に合致しているか否かを判定する。
（ア）文字列集合に合致している場合には、合致として検査結果１６２を出力する。
（イ）文字列集合に非合致の場合、
（イ−１）正規表現に合致している場合、合致として検査結果１６２を出力する。
（イ−２）正規表現に非合致の場合、非合致として検査結果１６２を出力する。
【００９８】
図２は、本実施の形態による処理例を示すフローチャートである。
ステップＳ２０２では、限定文字列パターン受付モジュール１１０が、限定文字列パターン１０８を受け付ける。
ステップＳ２０４では、対象文字列受付モジュール１２０が、対象文字列１１８を受け付ける。
ステップＳ２０６では、文字列集合抽出処理モジュール１３０が、限定文字列パターン１０８から文字列集合領域１３２を抽出する。
ステップＳ２０８では、文字列集合抽出処理モジュール１３０が、限定文字列パターン１０８から文字列集合領域１３２を抽出した残りの部分である正規表現領域１３４を抽出する。
ステップＳ２１０では、文字列集合抽出処理モジュール１３０が、文字列集合領域１３２と正規表現領域１３４の論理関係１３６を抽出する。
ステップＳ２１２では、文字列集合検査処理モジュール１４０が、対象文字列１１８が文字列集合領域１３２に合致しているかの検査を行う。
ステップＳ２１４では、正規表現検査処理モジュール１５０が、対象文字列１１８が正規表現領域１３４に合致しているかの検査を行う。
ステップＳ２１６では、検査結果統合処理モジュール１６０が、論理関係１３６によって、文字列集合検査処理モジュール１４０の検査結果と正規表現検査処理モジュール１５０の検査結果とを統合して検査結果１６２を出力する。
【００９９】
前述の例では、限定文字列パターン１０８内のテキスト中から文字列集合領域１３２を抜き出すことを示したが、これに限らない。文字列集合領域１３２と正規表現領域１３４を分離できれば、その方法は問わない。
例えば、受け付ける際の時間間隔をあけて、文字列集合領域１３２と正規表現領域１３４を分離してもよい。正規表現入力関数と、文字列集合入力関数を別に設けて分離してもよい。
より具体的な例について図２５、図２６、図２７を用いて説明する。図２５の例における限定文字列パターン検査処理モジュール２５００は、正規表現２５０８（正規表現で記載された文字列の型）、文字列集合２５１８（正規表現２５０８内の文字列の集合である部分）、対象文字列１１８を受け付け、検査結果１６２を出力する。
対象文字列１１８が文字列集合２５１８内の文字列に合致しているか否かを判定する。そして、対象文字列１１８が文字列集合２５１８以外の正規表現２５０８に合致しているか否かを判定する。この２つの判定結果を用いて、対象文字列１１８が正規表現２５０８に合致しているか否かを判定する。前述の例では、正規表現から文字列の集合である部分を抽出したが、この例では、正規表現２５０８と文字列集合２５１８とが予め分離されており、それらを用いる処理である。
ここで、限定文字列パターン検査処理モジュール２５００が行う限定文字列パターン検査処理とは、前述した技術において、正規表現にマッチするか否かを調べる処理の代わりに用いるものである。このような限定文字列パターン検査処理を行うことによって、文字認識結果を、限定文字列パターンに合致した結果に限定することができる。
以下、「合致」「非合致」は、完全検査の場合と部分一致検査の場合のいずれかを指すものとする。
また、本実施の形態の場合、正規表現検査と文字列集合検査の論理関係と、正規表現検査を文字列集合検査の検査順序は、固定とする。
【０１００】
限定文字列パターン検査処理モジュール２５００が行う限定文字列パターン検査処理は、以下のものである。
（２５−１）正規表現検査と文字列集合検査の論理関係をＡＮＤとして、正規表現検査を文字列集合検査の先に行う場合について説明する。
対象文字列１１８が正規表現２５０８に合致しているか否かを判定する。
（ア）正規表現２５０８に合致している場合、
（ア−１）文字列集合２５１８に合致している場合、合致として検査結果１６２を出力する。
（ア−２）文字列集合２５１８に合致していない場合、非合致として検査結果１６２を出力する。
（イ）正規表現２５０８に非合致の場合、非合致として検査結果１６２を出力する。
【０１０１】
（２５−２）正規表現検査と文字列集合検査の論理関係をＯＲとして、正規表現検査を文字列集合検査の先に行う場合について説明する。
対象文字列１１８が正規表現２５０８に合致しているか否かを判定する。
（ア）正規表現２５０８に合致している場合には、合致として検査結果１６２を出力する。
（イ）正規表現２５０８に非合致の場合、
（イ−１）文字列集合２５１８に合致している場合、合致として検査結果１６２を出力する。
（イ−２）文字列集合２５１８に合致していない場合、非合致として検査結果１６２を出力する。
【０１０２】
（２５−３）正規表現検査と文字列集合検査の論理関係をＡＮＤとして、正規表現検査を文字列集合検査の後に行う場合について説明する。
対象文字列１１８が文字列集合２５１８に合致しているか否かを判定する。
（ア）文字列集合２５１８に合致している場合、
（ア−１）正規表現２５０８に合致していれば、合致として検査結果１６２を出力する。
（ア−２）正規表現２５０８に合致していなければ、非合致として検査結果１６２を出力する。
（イ）文字列集合２５１８に非合致の場合、非合致として、検査結果１６２を出力する。
【０１０３】
（２５−４）正規表現検査と文字列集合検査の論理関係をＯＲとして、正規表現検査を文字列集合検査の後に行う場合について説明する。
対象文字列１１８が文字列集合２５１８に合致しているか否かを判定する。
（ア）文字列集合２５１８に合致している場合には、合致として検査結果１６２を出力する。
（イ）文字列集合２５１８に非合致の場合、
（イ−１）正規表現２５０８に合致している場合、合致として検査結果１６２を出力する。
（イ−２）正規表現２５０８に非合致の場合、非合致として検査結果１６２を出力する。
【０１０４】
図２６の例における限定文字列パターン検査処理モジュール２６００は、論理関係２６０８、正規表現２５０８、文字列集合２５１８、対象文字列１１８を受け付け、検査結果１６２を出力する。つまり、図２５の例と比べて、正規表現検査と文字列集合検査の論理関係２６０８を加える。
ここで、限定文字列パターン検査処理モジュール２６００が行う限定文字列パターン検査処理とは、前述した技術において、正規表現にマッチするか否かを調べる処理の代わりに用いるものである。このような限定文字列パターン検査処理を行うことによって、文字認識結果を、限定文字列パターンに合致した結果に限定することができる。
以下、「合致」「非合致」は、完全検査の場合と部分一致検査の場合のいずれかを指すものとする。
また、本実施の形態の場合、正規表現検査を文字列集合検査の検査順序は固定とする。
論理関係２６０８として、「ＡＮＤ」か「ＯＲ」を受け付ける。
正規表現検査と文字列集合検査の検査順序は固定とする。
例えば、正規表現検査を先に行う場合、論理関係２６０８によって、限定文字列パターン検査処理の内部動作を変化させる。ＡＮＤであれば、前述の（２５−１）の動作を行う。ＯＲであれば、前述の（２５−２）の動作を行う。
その他、例えば、正規表現検査を後に行う場合、論理関係２６０８によって、限定文字列パターン検査処理の内部動作を変化させる。ＡＮＤであれば、前述の（２５−３）の動作を行う。ＯＲであれば、前述の（２５−４）の動作を行う。
【０１０５】
図２７の例における限定文字列パターン検査処理モジュール２７００は、検査順序２７０８、論理関係２６０８、正規表現２５０８、文字列集合２５１８、対象文字列１１８を受け付け、検査結果１６２を出力する。つまり、図２６の例と比べて、正規表現検査と文字列集合検査の検査順序２７０８を加える。
ここで、限定文字列パターン検査処理モジュール２７００が行う限定文字列パターン検査処理とは、前述した技術において、正規表現にマッチするか否かを調べる処理の代わりに用いるものである。このような限定文字列パターン検査処理を行うことによって、文字認識結果を、限定文字列パターンに合致した結果に限定することができる。
以下、「合致」「非合致」は、完全検査の場合と部分一致検査の場合のいずれかを指すものとする。
論理関係２６０８として、「ＡＮＤ」か「ＯＲ」を受け付ける。
検査順序２７０８として、「正規表現検査が先か」、「正規表現検査が後か」を受け付ける。
論理関係２６０８がＡＮＤで、検査順序２７０８が正規表現検査を先に行う場合、前述の（２５−１）の動作を行う。
論理関係２６０８がＯＲで、検査順序２７０８が正規表現検査を先に行う場合、前述の（２５−２）の動作を行う。
論理関係２６０８がＡＮＤで、検査順序２７０８が正規表現検査を後に行う場合、前述の（２５−３）の動作を行う。
論理関係２６０８がＯＲで、検査順序２７０８が正規表現検査を後に行う場合、前述の（２５−４）の動作を行う。
【０１０６】
さらにビタビアルゴリズムを用いた場合に適用してもよい。
図２８の例に示すように、ノードＡ、ノードＢ、ノードＣから、ノードＤへのパスがあるとする。
ここでは、限定文字列パターンが「化学会議」であるとする。この文字列パターンになるように、パスを限定していく場合について説明する。図２８は、その途中段階の例を示している。
前述したように、ビタビアルゴリズムでは、各ノードから左に接続されるノードを１つに限定していくことによって、最適パス選定処理を行う。
ノードＡ→ノードＤのパスでは、すでにノードＡから左に向かうパスが１つに限定されている。そのため、ノードＡ→ノードＤとなるパスを選択した場合には、先頭からノードＤに至るパスが決定されるので、入力文字列を決定することができる。この場合、入力文字列が「ヒ学会」となり、これが「化学会議」に部分一致するかどうかを判定する。
ノードＢ→ノードＤのパスでは、前述と同様に、対象文字列が「化学会」となり、これが「化学会議」に部分一致するかどうかを判定する。
ノードＣ→ノードＤのパスでは、前述と同様に、対象文字列が「ト学会」となり、これが「化学会議」に部分一致するかどうかを判定する。
ところが、ノードＡの左に向かうパスを決定した段階で、ノードＡに至る文字列が「ヒ学」であって、「化学会議」とは合致していないことが明らかである。そのため、「ヒ学会」を「化学会議」と比較する処理は不要である。
【０１０７】
したがって、本実施の形態では、下記処理を行うようにしてもよい。
１．ビタビアルゴリズムの各ノードに、限定文字列パターンに合致しているか／合致していないかを示す１ビットの情報（合致情報）を記憶させる。
（ア）合致しているとき：合致情報をＯＮとする。
（イ）合致していないとき：合致情報をＯＦＦとする。
２．対象ノードから、左側のノードに至るパスを評価する。この評価処理は、図３に例示のパス限定処理モジュール３５０（図１に例示の情報処理装置等）が行う。このとき、
（ア）左側のノードの合致情報がＯＦＦであれば、限定文字列パターン検査処理を行わない。
（ア−１）さらに、すべての左側のノードの合致情報がＯＦＦであれば、対象ノードの合致情報をＯＦＦとする。
（イ）左側のノードの合致情報がＯＮの場合のみ、限定文字列パターン検査処理を行う。
（イ−１）限定文字列パターン検査処理の結果が合致している場合、対象ノードの合致情報をＯＮとする。
（イ−２）限定文字列パターン検査処理の結果が合致していない場合、対象ノードの合致情報をＯＦＦとする。
（ウ）対象ノードの合致情報がＯＮとなるパスが１つだけのとき、そのパスを選定する。対象ノードの合致情報がＯＮとなるパスが２つ以上のときは、前述したように、正規表現とは異なる方法で最も評価値の高いものを選択すればよい。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。
（エ）対象ノードの合致情報がＯＦＦとなる場合も、前述したように、正規表現とは異なる方法で最も評価値の高いものを選択すればよい。ここでの評価値とは、例えば、特開２０１２−１１８６５０号公報に示した方法を用いればよい。
【０１０８】
図２９を参照して、本実施の形態の情報処理装置のハードウェア構成例について説明する。図２９に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部２９１７と、プリンタなどのデータ出力部２９１８を備えたハードウェア構成例を示している。
【０１０９】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２９０１は、前述の実施の形態において説明した各種のモジュール、すなわち、限定文字列パターン受付モジュール１１０、対象文字列受付モジュール１２０、文字列集合抽出処理モジュール１３０、文字列集合検査処理モジュール１４０、正規表現検査処理モジュール１５０、検査結果統合処理モジュール１６０、文字列抽出モジュール３２０、切出位置抽出モジュール３３０、文字候補抽出モジュール３４０、パス限定処理モジュール３５０、ネットワーク構築処理モジュール１９１０、ノード数限定処理モジュール１９２０、制御モジュール１９３０、出力決定処理モジュール１９４０、限定文字列パターン検査処理モジュール２２００、限定文字列パターン検査処理モジュール２５００、限定文字列パターン検査処理モジュール２６００、限定文字列パターン検査処理モジュール２７００等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムに従った処理を実行する制御部である。
【０１１０】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）２９０２は、ＣＰＵ２９０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２９０３は、ＣＰＵ２９０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス２９０４により相互に接続されている。
【０１１１】
ホストバス２９０４は、ブリッジ２９０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス２９０６に接続されている。
【０１１２】
キーボード２９０８、マウス等のポインティングデバイス２９０９は、操作者により操作される入力デバイスである。ディスプレイ２９１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）などがあり、各種情報をテキストやイメージ情報として表示する。
【０１１３】
ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）２９１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ２９０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクには、受け付けた画像、文字認識結果、文字列パターン、ネットワーク構造、対象文字列、限定文字列パターンなどが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【０１１４】
ドライブ２９１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体２９１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース２９０７、外部バス２９０６、ブリッジ２９０５、及びホストバス２９０４を介して接続されているＲＡＭ２９０３に供給する。リムーバブル記録媒体２９１３も、ハードディスクと同様のデータ記録領域として利用可能である。
【０１１５】
接続ポート２９１４は、外部接続機器２９１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート２９１４は、インタフェース２９０７、及び外部バス２９０６、ブリッジ２９０５、ホストバス２９０４等を介してＣＰＵ２９０１等に接続されている。通信部２９１６は、通信回線に接続され、外部とのデータ通信処理を実行する。データ読み取り部２９１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部２９１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。
【０１１６】
なお、図２９に示す情報処理装置のハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図２９に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２９に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【０１１７】
前述の実施の形態においては、対象として日本語の文字を示したが、中国語、英語等の文字を対象としてもよい。
前述の実施の形態においては、横書きの文字列を前提として、左が始点で右が終点であるような記述の仕方を行ってきた。しかし、前述の説明は、縦書きや、右から左に記述する文字列でも同様に成り立つ。例えば、縦書きの場合は、「左」を「上」、「右」を「下」とする変換を行えばよい。右から左に記述する文字列の場合は、「左」を「右」、「右」を「左」とする変換を行えばよい。
なお、数式を用いて説明したが、数式には、その数式と同等のものが含まれる。同等のものとは、その数式そのものの他に、最終的な結果に影響を及ぼさない程度の数式の変形、又は数式をアルゴリズミックな解法で解くこと等が含まれる。
【０１１８】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、ブルーレイ・ディスク（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ（登録商標））、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ（登録商標））、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）、ＳＤ（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリーカード等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【符号の説明】
【０１１９】
１０８…限定文字列パターン
１１０…限定文字列パターン受付モジュール
１１８…対象文字列
１２０…対象文字列受付モジュール
１３０…文字列集合抽出処理モジュール
１３２…文字列集合領域
１３４…正規表現領域
１３６…論理関係
１４０…文字列集合検査処理モジュール
１５０…正規表現検査処理モジュール
１６０…検査結果統合処理モジュール
１６２…検査結果
３１０…画像受付モジュール
３２０…文字列抽出モジュール
３３０…切出位置抽出モジュール
３４０…文字候補抽出モジュール
３５０…パス限定処理モジュール
３６０…出力モジュール
２２００…限定文字列パターン検査処理モジュール
２５００…限定文字列パターン検査処理モジュール
２５０８…正規表現
２５１８…文字列集合
２６００…限定文字列パターン検査処理モジュール
２６０８…論理関係
２７００…限定文字列パターン検査処理モジュール
２７０８…検査順序
【図１】
2014021883.tif 000004
【図２】
2014021883.tif 000005
【図３】
2014021883.tif 000006
【図４】
2014021883.tif 000007
【図５】
2014021883.tif 000008
【図６】
2014021883.tif 000009
【図７】
2014021883.tif 000010
【図８】
2014021883.tif 000011
【図９】
2014021883.tif 000012
【図１０】
2014021883.tif 000013
【図１１】
2014021883.tif 000014
【図１２】
2014021883.tif 000015
【図１３】
2014021883.tif 000016
【図１４】
2014021883.tif 000017
【図１５】
2014021883.tif 000018
【図１６】
2014021883.tif 000019
【図１７】
2014021883.tif 000020
【図１８】
2014021883.tif 000021
【図１９】
2014021883.tif 000022
【図２０】
2014021883.tif 000023
【図２１】
2014021883.tif 000024
【図２２】
2014021883.tif 000025
【図２３】
2014021883.tif 000026
【図２４】
2014021883.tif 000027
【図２５】
2014021883.tif 000028
【図２６】
2014021883.tif 000029
【図２７】
2014021883.tif 000030
【図２８】
2014021883.tif 000031
【図２９】
2014021883.tif 000032
【図３０】
2014021883.tif 000033
【図３１】
2014021883.tif 000034
【図３２】
2014021883.tif 000035
【図３３】
2014021883.tif 000036
【図３４】
2014021883.tif 000037
【図３５】
2014021883.tif 000038
【図３６】
2014021883.tif 000039
【図３７】
2014021883.tif 000040