(57)【要約】      （修正有）【課題】正規表現を照合条件とする文字列照合に対して、状態遷移表を格納するのに必要な記憶容量を削減する。【解決手段】正規表現で記述された照合条件２に基づいて状態遷移表を生成する状態遷移表生成部３と、前記状態遷移表生成部３により生成された状態遷移表に基づいて遷移するオートマトンとを備えるとともに、前記オートマトンは、前記照合条件２に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、入力文字を読み進めずに初期状態或いは所定の状態へ遷移することにより、状態遷移表を格納するのに必要な記憶容量を削減する。前記照合条件２に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、入力文字を読み進めずに所定の状態へ遷移する除外文字を設定して状態遷移表を作成する。【選択図】図１
2010225156.tif 000002
【特許請求の範囲】
【請求項１】
正規表現で記述された照合条件に基づいて状態遷移表を生成する状態遷移表生成部と、
前記状態遷移表生成部により生成された状態遷移表に基づいて遷移するオートマトンとを備えるとともに、
前記状態遷移表生成部は、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、所定の状態へ遷移する除外文字を設定して状態遷移表を作成することを特徴とする文字列照合装置。
【請求項２】
前記状態遷移表生成部は、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、初期状態へ遷移する状態遷移表を作成することを特徴とする請求項１記載の文字列照合装置。
【請求項３】
前記状態遷移表生成部は、複数の照合条件が入力された場合、状態の併合に基づいて出力記述の併合を行い、出力表作成し、
前記オートマトンは、前記出力表に基づいて出力することを特徴とする請求項１記載の文字列照合装置。
【請求項４】
前記状態遷移表生成部は、ある状態から任意文字による遷移先q1と所定の遷移文字σによる遷移先q2が存在するとき、前記任意文字を前記除外文字で置き換え、前記所定の遷移文字σによる遷移先をq1とq2を併合した状態で置き換えることを特徴とする請求項１記載の文字列照合装置。
【請求項５】
前記状態遷移表生成部は、ある状態から前記除外文字による遷移先の状態が複数存在するとき、それら複数の状態を併合した状態で置き換えることを特徴とする請求項１記載の文字列照合装置。
【請求項６】
前記状態遷移表生成部は、所定の状態q1,q2を併合する際に、q2から前記除外文字によりq3に状態遷移する場合、q1を起点とする状態遷移先とq3を併合することを特徴とする請求項１記載の文字列照合装置。
【請求項７】
前記状態遷移表生成部は、NFAを生成する際に、「.」による遷移を任意文字遷移とする状態遷移を生成することを特徴とする請求項１記載の文字列照合装置。
【請求項８】
前記状態遷移表生成部は、NFAを生成する際に、[^a]による遷移を、文字aによる遷移と除外文字σotherによる遷移とに置き換えることを特徴とする請求項１記載の文字列照合装置。
【請求項９】
前記状態遷移表生成部は、通常の文字と除外文字σotherが同一の状態に遷移するときに、通常の文字による状態遷移を削除することを特徴とする請求項１記載の文字列照合装置。
【請求項１０】
通常の文字と除外文字σotherとが同一の状態に遷移するときに、通常の文字による状態遷移を削除した後に、すべての文字に対して同一の状態に遷移する複数の状態を併合し、さらに、すべての文字に対して同一の状態に遷移する複数の状態を併合した後に、通常の文字と除外文字σotherとが同一の状態に遷移するときに、通常の文字による状態遷移を削除することを特徴とする請求項９記載の文字列照合装置。
【請求項１１】
前記状態遷移表生成部は、前記状態遷移表をハッシュ表により構成することを特徴とする請求項１記載の文字列照合装置。
【請求項１２】
前記オートマトンは、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、入力文字を読み進めずに初期状態へ遷移することを特徴とする請求項１記載の文字列照合装置。
【請求項１３】
前記状態遷移表生成部は、複数の照合条件が入力された場合、状態の併合に基づいて出力記述の併合を行い、出力表作成し、
前記オートマトンは、前記出力表に基づいて出力することを特徴とする請求項１２記載の文字列照合装置。
【請求項１４】
前記状態遷移表生成部は、状態遷移表を生成する際、初期状態q0から所定の遷移文字σにより所定の状態q1に遷移可能であり、かつ、任意の状態qから前記所定の遷移文字σにより遷移可能であるとき、前記任意の状態qから前記所定の遷移文字σによる前記所定の状態q1への状態遷移を追加することを特徴とする請求項１２に記載の文字列照合装置。
【請求項１５】
前記状態遷移表生成部は、前記状態遷移表をハッシュ表により構成することを特徴とする請求項１２記載の文字列照合装置。
【請求項１６】
コンピュータを制御して、文字列の照合を行うプログラムであって、
状態遷移表生成部により、正規表現で記述された照合条件に基づいて状態遷移表を生成するとともに、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、所定の状態へ遷移する除外文字を設定して状態遷移表を作成する処理と、
前記状態遷移表生成部により生成された状態遷移表に基づいて遷移する処理とを前記コンピュータに実行させることを特徴とする文字列照合プログラム。
【請求項１７】
前記状態遷移表生成部により生成された状態遷移表に基づいて遷移するとともに、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、入力文字を読み進めずに初期状態へ遷移する処理とを前記コンピュータに実行させることを特徴とする請求項１６記載の文字列照合プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、正規表現によって指定されたパターンと文章中のテキストの照合を行うための技術に関するものである。
【背景技術】
【０００２】
近年様々な分野で文書の電子化が進んでおり、文書の効率的な検索方法が求められている。検索の一方法として、正規表現によって指定されたパターンと文書中のテキストの照合を行う方法がある。正規表現とは、例えば非特許文献１に記載されており、正規言語と呼ばれる言語のクラスを表現する表記方法である。正規表現を検索条件とする文字列照合方式として、DFA(Deterministic Finite Automaton、決定性有限オートマトン)による方法が知られている。
【０００３】
DFAによる文字列照合方式は状態遷移機械（オートマトン）のモデルに基づいている。状態遷移機械は内部に状態と状態遷移関数を持つ。状態遷移関数は現在の状態と入力文字に対して次の状態を決定する関数である。DFAを用いた文字列照合方式では、入力テキストを１文字づつ読み出し、現在の状態と入力文字の組に対して状態遷移関数を適用して得られた次の状態に遷移する。この方法によるとテキストを後戻りすることなく１度走査することによって照合を行うことができ、高速な文字列照合が可能になる。複数の条件による照合を行う場合、照合に成功した条件を区別するため、DFAを拡張し各状態に出力を定義した出力つき有限オートマトン（Moore機械）も用いられている。
【０００４】
DFAの状態遷移関数は照合条件となる正規表現によって決まるが、従来から、正規表現を一度NFA（Non-deterministic Finite Automaton、非決定性有限オートマトン）に変換し、更にNFAをDFAに変換するその手順が知られており、例えば非特許文献１などに記載されている。DFAによる文字列照合方式は高速であるという特長を持つが、反面、DFAの状態遷移関数を実現するための状態遷移表が巨大になりやすいという欠点があった。
【０００５】
一例として、特許文献３に開示されている図５２の照合条件を例にとる。図５３は従来の出力つき有限オートマトンにおいて図５２の照合条件から生成される状態遷移表および失敗関数である。このように状態数１８と文字種別５種類に対し、９０通りの組を保持する状態遷移表を生成する必要がある。
【０００６】
このような課題を解決する方法として、特許文献１、特許文献２には、AC（Aho-Corasick）法に基づく状態遷移表をDFAに変換した後、初期状態への遷移操作および初期状態の次の状態への遷移操作を状態遷移表から除去することによって状態遷移表の記憶容量を削減する方法が示されている。しかし、特許文献１、特許文献２に示された文字列照合方法では、照合の対象を固定の文字列キーワードに限定しているため、一般の正規表現を照合の対象とすることはできない。
【０００７】
また、特許文献３には、DFAにおいて、失敗関数を定義することによって状態遷移表を削減する方法が示されている。しかし、特許文献３に示された方法では、一度失敗関数によって遷移した状態で再び遷移に失敗することがある。すなわち、遷移の失敗が連鎖的に発生することがある。このような場合は、繰り返し失敗関数を参照する必要があり照合速度が低下するという問題点があった。
【０００８】
一例として、特許文献３に開示されている図５２の照合条件を例にとる。図５４は図５２の照合条件から生成される状態遷移表および失敗関数であり、特許文献３に開示されている。
【０００９】
照合条件が図５２の条件であり、入力文字列が「aaca」の場合を例にとる。
【００１０】
特許文献３に開示されている方法では、まず、状態を状態１に初期化する。次にまず、１文字目の「a」を読み、状態遷移表の状態１の行で入力文字「a」の列に示されている状態３に遷移する。次に、２文字目の「a」を読み、同様に、状態３から状態６に遷移する。次に３文字目の「c」を読むことにより、状態６から状態１０に遷移する。ところが、次に４文字目の文字「a」が出現した場合は、状態10で文字「a」に該当する遷移先が存在しないことから、まず、状態10の失敗時の遷移先である状態5に遷移する。更に、状態5で文字「a」に該当する遷移先が存在しないことから、状態5の失敗時の遷移先である状態2に遷移する。しかし、状態2でも文字「a」に該当する遷移先が存在しないことから、状態2の失敗時の遷移先である状態1に遷移する。状態1では、文字「a」に該当する遷移先状態3が存在することから状態3に遷移する。このように、４文字目の入力文字に対しては合計４回の状態遷移表の参照と状態遷移を行っており、全体としては４文字の入力文字に対して、７回の状態遷移を必要とする。このように、特許文献３の方法では、状態遷移の失敗を繰り返し、その都度失敗時の遷移先を参照する動作が必要になる場合がある。このため、状態遷移表の参照回数が増加し、照合性能が低下すると言う問題点があった。
【００１１】
【非特許文献１】E.J.Hopcroft,  D.J.Ullman, "Formal Languages and their Relation to Automata", Addison Wesley (1969)
【特許文献１】特開2004-103035号公報
【特許文献２】特開2004-103034号公報
【特許文献３】特許第2994926号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
この発明は上記の問題点を解決するためになされたもので、正規表現を照合条件とする文字列照合に対して、状態遷移表を格納するのに必要な記憶容量を削減することを目的とする。
【００１３】
また、遷移の失敗による状態遷移表の参照回数を１文字当り２回以下とし、遷移の失敗が繰り返されることによる性能低下による性能低下を防止し、高速な文字列照合を可能にすることを目的とする。
【課題を解決するための手段】
【００１４】
本発明にかかわる文字列照合装置は、正規表現で記述された照合条件に基づいて状態遷移表を生成する状態遷移表生成部と、前記状態遷移表生成部により生成された状態遷移表に基づいて遷移するオートマトンとを備えるとともに、前記オートマトンは、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、入力文字を読み進めずに初期状態へ遷移するものである。
【発明の効果】
【００１５】
正規表現で記述された照合条件に基づいて状態遷移表を生成する状態遷移表生成部と、前記状態遷移表生成部により生成された状態遷移表に基づいて遷移するオートマトンとを備えるとともに、前記オートマトンは、前記照合条件に基づいて生成された状態遷移表において、現状態と入力文字の組に対する次の遷移先状態が存在しない場合、入力文字を読み進めずに初期状態へ遷移することにより、状態遷移表を格納するのに必要な記憶容量を削減することができる。
【図面の簡単な説明】
【００１６】
【図１】文字列照合装置の構成を示す説明図である。
【図２】照合条件２の構成を示す説明図である。
【図３】条件式１７の構成を示す説明図である。
【図４】状態遷移表生成部３の構成を示す説明図である。
【図５】状態遷移表格納部４の構成を示す説明図である。
【図６】出力表格納部５の構成を示す説明図である。
【図７】照合結果１０の構成を示す説明図である。
【図８】文字列照合装置の動作を示すフローチャートである。
【図９】照合条件のコンパイルの動作を示すフローチャート
【図１０】初期状態への失敗遷移の追加の手続きを示すフローチャート
【図１１】初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在しない場合）の手続きを示すフローチャート
【図１２】初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在する場合）の手続きを示すフローチャート
【図１３】非決定的遷移の除去の手続きを示すフローチャート
【図１４】状態集合の初期化の手続きを示すフローチャート
【図１５】Σに関する非決定的遷移の除去の手続きを示すフローチャート
【図１６】σotherに関する非決定的遷移の除去の手続きを示すフローチャート
【図１７】新状態の生成の手続きを示すフローチャート
【図１８】σotherによる状態遷移の補正の手続きを示すフローチャート
【図１９】未使用状態の除去の手続きを示すフローチャート
【図２０】冗長状態の除去の手続きを示すフローチャート
【図２１】冗長な状態遷移の削除の手続きを示すフローチャート
【図２２】状態遷移表と出力表の生成の手続きを示すフローチャート
【図２３】入力文書の照合の手続きを示すフローチャート
【図２４】メタキャラクタ「.」の置き換えを説明する説明図
【図２５】メタキャラクタ「^」の置き換えを説明する説明図
【図２６】初期状態へのε遷移を含むNFAを説明する説明図
【図２７】ε遷移の省略を説明する説明図
【図２８】失敗遷移の追加の必要な場合を説明する説明図
【図２９】失敗遷移の追加を説明する説明図
【図３０】初期状態からσanyによる遷移が存在する場合を説明する説明図
【図３１】初期状態からσanyによる遷移が存在する場合の失敗遷移の追加を説明する説明図
【図３２】非決定的遷移の除去（除去前）を説明する説明図
【図３３】非決定的遷移の除去（除去後）を説明する説明図
【図３４】非決定的遷移の除去（除去前）を説明する説明図
【図３５】非決定的遷移の除去（除去後）を説明する説明図
【図３６】非決定的遷移の除去（除去前）を説明する説明図
【図３７】非決定的遷移の除去（除去後）を説明する説明図
【図３８】非決定的遷移の除去（除去前）を説明する説明図
【図３９】非決定的遷移の除去（除去後）を説明する説明図
【図４０】非決定的遷移の除去（除去前）を説明する説明図
【図４１】非決定的遷移の除去（除去後）を説明する説明図
【図４２】冗長な状態遷移の削除を説明する説明図
【図４３】冗長な状態の併合を説明する説明図
【図４４】照合条件の構成を示す説明図
【図４５】状態遷移表の構成を示す説明図
【図４６】出力表の構成を示す説明図
【図４７】動作例を示す説明図
【図４８】照合条件の構成を示す説明図
【図４９】状態遷移表の構成を示す説明図
【図５０】出力表の構成を示す説明図
【図５１】動作例を示す説明図
【図５２】特許文献3に開示されている照合条件
【図５３】特許文献3による従来の出力付きDFAの状態遷移表
【図５４】特許文献3による従来の状態遷移表と出力表
【符号の説明】
【００１７】
１  文字列照合装置
２  照合条件
３  状態遷移表生成部
４  状態遷移表格納部
５  出力表格納部
６  入力文書
７  入力文字読み取り部
８  SDFAオートマトン
９  状態記憶部
１０  照合結果
１１  状態遷移
１２  出力記述
１３  現状態
１４  入力文字
１５  次状態
１６  条件番号
１７  条件式
１８  条件記述
２１  状態遷移表生成制御部
２２  NFA状態集合
２３  NFA状態遷移集合
２４  NFA出力記述集合
２５  状態集合
２６  状態遷移集合
２７  出力記述集合
３１  ハッシュ値計算部
３２  ハッシュ値
３３  状態遷移ハッシュポインタ
３４  状態遷移ハッシュチェイン
３５  状態遷移ハッシュ表
３６  比較部
４１  条件番号インデックス
４２  条件番号チェイン
【発明を実施するための最良の形態】
【００１８】
実施例１．
図１はこの発明の文字列照合装置を示す構成図である。
【００１９】
図１において、文字列照合装置１は、この発明における正規表現による文字列照合を行う装置であり、入力文書６の中に照合条件２を満たすものが含まれるかどうかを照合結果１０として出力する。照合条件２は文字列照合の条件を記述した条件であり、文字列照合装置１の入力となる。状態遷移表生成部３は照合条件２から状態遷移１１と出力記述１２を生成し、それぞれ状態遷移表格納部４、出力表格納部５に渡す。状態遷移表格納部は状態遷移１１の組を保持する。出力表格納部５は出力記述１２を保持する。入力文書６は照合の対象となる文書である。入力文字読み取り部７は入力文書６に含まれる文字を１文字づつ取り出し、入力文字１４としてSDFAオートマトン８に送る。SDFAオートマトン８は内部の状態記憶部９に現状態１３を記憶し、入力文字読み取り部７から入力文字１４を受け取り、状態遷移表格納部４、出力表格納部５を参照して状態記憶部９に格納された現状態１３の更新と照合結果１０の出力を行う。状態記憶部９はSDFAオートマトン８の内部に保持された状態を記憶する。１０は照合結果である。１１は状態遷移であり、現状態１３、入力文字１４、次状態１５の組である。１２は出力記述であり、現状態１３と条件番号１６の組である。１３は現状態である、１４は入力文字である。１５は次状態である。１６は条件番号である。
【００２０】
図２は、この発明における照合条件２の構成を示す図である。図において、条件式１７は、照合条件２を構成する個別の条件であり、照合条件２の中に１または複数の条件式１７が含まれる。
【００２１】
図３は、この発明における条件式１７の構成を示す図である。条件式１７は、条件番号１６と条件記述１８から構成され、条件番号１６は条件式を一意に区別するための番号であり、条件記述１８は正規表現によって記述された照合の条件である。
【００２２】
図４は、この発明における状態遷移表生成部３の構成を示す図である。図において、状態遷移表生成制御部２１は、状態遷移生成表の生成の動作手順を制御する。NFA状態集合２２、NFA状態遷移集合２３、NFA出力記述集合２４、状態集合２５、出力遷移集合２６、状態記述集合２７は状態遷移表生成制御部２１が参照するデータである。
【００２３】
図５は、この発明における状態遷移表格納部４の構成の一例を示す図である。図において、３１はハッシュ値計算部であり、現状態１３と入力文字１４からハッシュ値３２を計算する。ハッシュ値３２はハッシュ値計算部３１によって計算されたハッシュ値である。状態遷移ハッシュポインタ３３は状態遷移ハッシュチェイン３４のポインタを複数格納する表である。状態遷移ハッシュチェイン３４は状態遷移ハッシュチェイン３４へのポインタ、現状態１３、入力文字１４、次状態１５の組である。状態遷移ハッシュ表３５は状態遷移ハッシュポインタ３３と状態遷移ハッシュチェイン３４から成るデータ構造である。比較部３６は外部から入力された現状態１３ａと入力文字１４ａの組と、状態遷移ハッシュ表３５に格納された現状態１３ｂ、入力文字１４ｂを比較し、次状態１５を出力する。
【００２４】
図６は、この発明における出力表格納部５の構成を示す図である。条件番号インデックス４１は条件番号チェインへのポインタを複数格納する。条件番号チェイン４２は、条件番号チェイン４２へのポインタと条件番号１６の組である。
【００２５】
図７は、この発明における照合結果１０の一例を示す図である。照合結果１０には、入力文書６の照合に成功した条件番号１６が含まれる。
【００２６】
次に、本発明の動作説明に先立ち、以下の説明で用いる用語および記号の説明を行う。
【００２７】
非特許文献１などに記載されているように、従来から知られている出力付き決定性有限オートマトンは、(Q, Σ, Δ, δ, λ, q0)の組によって与えられる。ただしQは状態集合である。Σは入力アルファベットであり、空文字εを含む。Δは出力アルファベット、δは遷移関数（Q×Σ→Q）、λは出力関数（Q→Δ）、q0は初期状態である。
【００２８】
本発明のSDFAオートマトン８は(Qs, Σs, Δs, δs, λs, q0)の組によって与えられる。
【００２９】
ここで、Qsは状態集合２５であり、従来の出力つき有限オートマトンの状態集合Qに相当するものである。
【００３０】
Δsは出力アルファベットであり、本実施例では条件番号１６の集合の集合となる。
【００３１】
δsは状態遷移表格納部４によって実現される状態遷移関数であり、以下、現状態１３がqs、入力文字１４がσsのとき次状態１５がqdとなることを、
δs(qs, σs) = qd
と表記する。
【００３２】
q0は初期状態であり、その意味は従来から知られている出力つき決定性有限オートマトンと同じである。
【００３３】
Σsは従来の出力付き有限オートマトンの入力アルファベットΣに任意文字σany, 除外文字σotherを加えた拡張入力アルファベットである。すなわち、
Σs=Σ∪{σany, σother }
とする。
【００３４】
また、
δs (qs, σs) = qd
であるとき、状態遷移１１をtとすると、
t=trans(qs, qd, σs)
と表記するものとする。
【００３５】
現状態１３入力文字１４の組に対して次状態１５が存在する状態遷移１１の集合を状態遷移集合２６と呼び、Tと表記する。また、状態遷移t=trans(qs, qd, σs)に対して、qsを起点、qdを終点、σsを遷移文字と呼ぶ。更に、状態遷移tの起点を与える関数をSource、終点を与える関数をDestination、遷移文字を与える関数をCharと呼び、それぞれ
qs=Source(t)
qd=Destination(t)
σs=Char(t)
と表記する。
また、
λs(qs) = r
であるとき、出力記述１８をdとすると
d=desc(qs, r)
と表記するものとする。
【００３６】
現状態１３に対して出力アルファベットrが空でない出力記述１２の集合を出力記述集合２７と呼び、Dと表記する。出力記述d=desc(qs, r)に対して、qsを出力状態、rを出力結果と呼ぶ。更に、出力記述dの出力状態を与える関数をState、出力結果を与える関数をResultと呼び、それぞれ
qs =State(d)
r =Result(d)
と表記することにする。
【００３７】
本発明のSDFAオートマトン８を生成する過程でNFAが生成されるが、NFAは(Q(NFA), Σs, Δs, δs（NFA）, λs(NFA), q0(NFA))の組によって表される。
【００３８】
ここで、Q(NFA)はNFA状態集合２２を表す。状態集合２５はNFA状態の集合の集合となる。すなわち状態集合２５をQと表記するときQ=2Q(NFA)の関係にある。以下、NFAの状態をDFAの状態と区別するため、q(NFA)と表記し、NFAの初期状態をq0(NFA)と表記する。
【００３９】
δs(NFA)はNFAの状態遷移関数であり、現在のNFA状態１３がq(NFA)、入力文字１４がσsから次状態の集合への関数である。
【００４０】
λs(NFA)はNFAの出力関数であるり、現在のNFA状態１３がq(NFA)のとき、出力アルファベットがｒ∈Δsとなることを
λs(NFA) (q(NFA)) = ｒ
と表記する。
【００４１】
Δsは条件番号１６の集合、Σsは拡張入力アルファベットであり、その意味は本発明のSDFAオートマトン８と同じである。
【００４２】
NFAの状態について、NFA状態遷移を以下のように定める。NFAの状態qd(NFA)が
q d(NFA)∈δ(qs(NFA), σs)
のとき、NFA状態遷移３２を
t(NFA)=trans(qs(NFA), qd(NFA), σs)
と表記するものとする。NFA状態遷移の集合をNFA状態遷移集合とよび、T(NFA)と表記する。また、同様に状態遷移t(NFA)=trans(qs(NFA), qd(NFA), σs)に対して、qs(NFA)を起点、qd(NFA)を終点、σsを遷移文字と呼ぶ。更に、状態遷移t(NFA)の起点を与える関数をSource、終点を与える関数をDestination、遷移文字を与える関数をCharと呼び、それぞれ
qs(NFA)=Source(t(NFA))
qd(NFA)=Destination(t(NFA))
σs(NFA)=Char(t(NFA))
と表記することにする。
【００４３】
NFA状態q(NFA)と出力アルファベットｒの組をNFA出力記述と呼ぶことにする。
λs(q(NFA)) = ｒ
であるとき、NFA出力記述３４をd(NFA)とすると
d(NFA)=desc(qs(NFA), r)
と表記するものとする。
【００４４】
NFA状態１３に対して出力アルファベットpが空でないNFA出力記述の集合をNFA出力記述集合２４と呼び、D(NFA)と表記する。出力記述d(NFA)=desc(q(NFA), r)に対して、q(NFA)を出力状態、rを出力結果と呼ぶ。更に、出力記述dの出力状態を与える関数をState、出力結果を与える関数をResultと呼び、それぞれ
q(NFA) =State(d(NFA))
r(NFA) =Result(d(NFA))
と表記することにする。
【００４５】
以上で用語および記号の説明を終わり、次に、動作について説明する。
【００４６】
図８に、本発明の文字列照合装置１の動作を示す。
【００４７】
本発明の文字列照合装置１は、まず、照合条件２を受け取り状態遷移表生成部３により状態遷移１１と出力記述１２を生成する過程、すなわち、照合条件のコンパイルの手続きを実行する（ステップS51）。
【００４８】
次いで、入力文書６を受け取り、入力文字読み取り部７およびSDFAオートマトン８によって、状態遷移１１と出力記述１２を参照しながら照合結果１０を出力する手続きを順次実行する(ステップS52)。
【００４９】
なお、本実施の例では１回の「照合条件のコンパイル」に対して「入力文書の照合」を１回行うこととしているが、１回の「照合条件のコンパイル」の手続きで生成された、状態遷移１１と出力記述１２を用いて、複数個の入力文書に対して「入力文書の照合」を行っても良い。
【００５０】
次に、図９により、手続き「照合条件のコンパイル」について説明する。
【００５１】
まず「ε遷移を含むNFAの生成」の手続きにより、正規表現から、ε遷移を含むNFAを生成する（ステップS101）。
【００５２】
次いで、「ε遷移の除去」の手続きによりNFAに含まれるε遷移（空文字による遷移）の除去を行う（ステップS102）。
【００５３】
次いで、「初期状態への遷移の追加」の手続きにより、照合に失敗した際の初期状態への遷移を追加する（ステップS103）。
【００５４】
次いで、「非決定的遷移の除去」の手続きにより、非決定的な遷移を除去する（ステップS104）。
【００５５】
次いで、「未使用状態の除去」の手続きにより、これまでの手順で不要になった状態の除去を行う（ステップS105）。
【００５６】
次いで、「状態数の削減」の手続きにより、冗長な状態および冗長な状態遷移の除去を行う（ステップS106）。
【００５７】
次いで、「状態遷移表と出力表の生成」の手続きにより、状態集合から状態遷移表と出力表を生成する（ステップS107）。
【００５８】
以上の手順により手続き「照合条件のコンパイル」を実行することができる。
【００５９】
ステップS101の、「ε遷移を含むNFAの生成」の手順については、非特許文献１などに示されている公知の手順を使用することができる。
【００６０】
ただし、図２４に示すように正規表現中に含まれる任意の文字を表すメタキャラクタ「.」はσanyに置き換える。なお、以下、図２４〜図３１では状態q(NFA)を単にqと表記している。
【００６１】
また、図２５に示すように正規表現中に含まれる、特定文字集合以外を表すメタキャラクタ「^」はσotherに置き換え更に、該当する状態から初期状態q0(NFA)への状態遷移を追加するという手順を追加する。
【００６２】
ステップS102の、「ε遷移の除去」の手順についても、非特許文献１などに示されている公知の手順により、ε遷移（空文字による遷移）を遷移先集合への遷移で置き換えることにより、実現することができる。
【００６３】
次に、図１０によってステップS103の「初期状態への失敗遷移の追加」の手続きを示す。
【００６４】
まず、ステップS102によって生成されたNFAの初期状態q0(NFA)からσanyによる遷移が存在しない場合はステップS202に進む。それ以外の場合は、ステップS203に進む（ステップS201）。
【００６５】
「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在しない場合）」の手続きを実行し、終了する（ステップS202）。
【００６６】
ステップS201でNFAの初期状態q0(NFA)からσanyによる遷移が存在する場合は「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在する場合）」の手続きを実行し、終了する（ステップS203）。
【００６７】
なお、本実施例ではNFAの初期状態q0(NFA)からσanyによる遷移先が存在するか否かにより処理を分けているが、ステップS202の処理はステップS203によって代行することも可能である。ステップS202の処理はステップS203と比較すると適用可能な範囲が「初期状態からσanyによる遷移先が存在する」場合に限定されるが、より状態遷移の数を削減することができる。初期状態からσanyによる遷移先が存在するとは、照合条件となる正規表現の先頭に任意文字「.」が指定されるということであるが、実用上はこのような指定がされることは少ないため、多くの場合はステップS202の処理を適用することによって状態遷移の数を削減できる。
【００６８】
以上の手順に従って、手続き「初期状態への失敗遷移の追加」を行うことができる。
【００６９】
次に、ステップS202の「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在しない場合）」の手続きについて説明する。
【００７０】
一般に、連続的な文字列照合を行うNFAまたはDFAでは、すべての状態から初期状態へのε遷移を追加することにより、任意の文字位置からの文字列照合を実現できる。図２６に、正規表現(a|b|c(d|e))f  に対応するNFAにε遷移を追加した例を示す。本発明のSDFAオートマトン８では、遷移に失敗した際に入力文字を進めずに初期状態q0に戻って再度状態遷移を行うため、初期状態q0へのε遷移を省略できる。すなわち、図２７に示すNFAを構成すればよく、状態遷移の総数を大幅に削減することができる。しかし、初期状態q0(NFA)から遷移文字σにより状態q1(NFA)に遷移可能であるとき、状態q(NFA)からの遷移文字σによる遷移が存在するか、または、状態q(NFA)を起点とするいずれかの遷移文字σがσanyである場合は、σによる遷移が成功した場合にもσによりq1(NFA)にも遷移可能であるため、状態q(NFA)からσによる状態q1(NFA)への状態遷移を追加する。図２８に、正規表現(a|b|c(d|e))f  の場合の例を示す。図２８の例では初期状態q0(NFA)から遷移文字aにより状態q1(NFA)に遷移可能であり、状態q3(NFA)から遷移文字aによる遷移が存在するため、図２９のように遷移文字aによる状態q3(NFA)から状態q1(NFA)への遷移を追加する。状態q3(NFA)から遷移文字aによる遷移は非決定的な状態遷移となるが、後続の「非決定的遷移の除去」の手続きにより、この非決定的遷移は最終的に除去される。手続き「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在しない場合）」および「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在する場合）」はこの処理を行うためのものである。
【００７１】
図１１により、ステップS202の「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在しない場合）」の手続きについて説明する。
【００７２】
まず、t0(NFA) をステップS102によって生成されたNFAの初期状態q0(NFA)を起点とする最初の状態遷移とし、ステップS302に進む（ステップS301）。
【００７３】
NFAの初期状態q0(NFA)を起点とするすべての状態遷移t0(NFA)の処理を終了したら手続きを終了する。それ以外の場合はステップS303に進む（ステップS302）。
【００７４】
σをChar(t0(NFA))とし、ステップS304に進む（ステップS303）。
【００７５】
q(NFA)をNFA状態集合Q(NFA)に含まれる最初のNFA状態とし、ステップS305に進む（ステップS304）。
【００７６】
NFA状態集合Q(NFA)に含まれるすべてのNFA状態q(NFA)の処理を終了したらステップS313に進む。それ以外の場合はステップS306に進む（ステップS305）。
【００７７】
NFA状態q(NFA)が初期状態q0(NFA)の場合は、ステップS312に進む。それ以外の場合はステップS307に進む（ステップS306）。
【００７８】
t(NFA)を、q(NFA)を起点とする最初のNFA状態遷移とし、ステップS308に進む（ステップS307）。
【００７９】
q(NFA)を起点とするすべてのNFA状態遷移t(NFA)の処理を終了したらステップS312に進む。それ以外の場合はステップS309に進む（ステップS308）。
【００８０】
Char(t(NFA))=σ 、Char(t(NFA))= σanyのいずれかの条件が成立する場合はステップS310に進む。いずれの条件も成立しない場合はステップS311に進む（ステップS309）。
【００８１】
NFA状態遷移 trans(q(NFA), Destination(t0(NFA)), σ)がNFA状態遷移集合T(NFA)に含まれていなければTに加え、ステップS311に進む（ステップS310）。
【００８２】
t(NFA)をNFA状態q(NFA)を起点とする次のNFA状態遷移とし、ステップS305に進む（ステップS311）。
【００８３】
ステップS306にてNFA状態q(NFA)がNFAの初期状態q0(NFA)の場合、またはステップS308にてq(NFA)を起点とするすべてのNFA状態遷移t(NFA)を処理した場合はNFA状態q(NFA)をNFA状態集合QNFAに含まれる次のNFA状態とし、ステップS305に進む（ステップS312）。
【００８４】
ステップS305にてすべてのNFA状態q(NFA)の処理を終了した場合は、t0(NFA) をNFAの初期状態q0(NFA)を起点とする次のNFA状態遷移とし、ステップS302に進む（ステップS313）。
【００８５】
以上の手順に従って、手続き「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在しない場合）」を行うことができる。
【００８６】
次に、ステップS203の「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在する場合）」の手続きについて説明する。この手続きの目的はステップS202と同じであるが、図３０に示す正規表現(.|b|c(d|e))f  のように、初期状態からσanyによる遷移先q1(NFA)が存在する場合は、すべての状態に対して、遷移が成功した場合にもq1(NFA)にも遷移可能となるため、図３１に示すように、NFAの初期状態q0(NFA)を除くすべてのNFA状態q(NFA)とすべての遷移文字σに対して、q1(NFA)への遷移を追加する。
【００８７】
図１２により、ステップS203の「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在する場合）」の手続きについて説明する。
【００８８】
まず、t0(NFA) をステップS102によって生成されたNFAの初期状態q0(NFA)を起点とする最初のNFA状態遷移とし、ステップS352に進む（ステップS351）。
【００８９】
NFAの初期状態q0(NFA)を起点とするすべてのNFA状態遷移t0(NFA)の処理を終了したら手続きを終了する。それ以外の場合はステップS353に進む（ステップS352）。
【００９０】
σをChar(t0(NFA))とし、ステップS354に進む（ステップS353）。
【００９１】
qをNFA状態集合Q(NFA)に含まれる最初のNFA状態とし、ステップS355に進む（ステップS354）。
【００９２】
NFA状態集合Q(NFA)に含まれるすべてのNFA状態qの処理を終了したらステップS359に進む。それ以外の場合はステップS356に進む（ステップS355）。
【００９３】
NFA状態q(NFA)が初期状態q0(NFA)の場合は、ステップS356に進む。それ以外の場合はステップS357に進む（ステップS306）。
【００９４】
NFA状態遷移trans (q(NFA), Destination(t0(NFA)), σ(NFA))がNFA状態遷移集合T(NFA)に含まれていなければT(NFA)に加え、ステップS355に進む（ステップS358）。
【００９５】
ステップS355にてすべてのNFA状態q(NFA)の処理を終了した場合は、t0(NFA) をNFAの初期状態q0(NFA)を起点とする次のNFA状態遷移とし、ステップS352に進む（ステップS359）。
【００９６】
以上の手順に従って、手続き「初期状態への失敗遷移の追加（初期状態からσanyによる遷移先が存在する場合）」を行うことができる。
【００９７】
次にステップS104の「非決定的遷移の除去」の手続きについて説明する。本手続きは、NFAに含まれる非決定的な遷移を除去し、決定的な遷移を生成するものである。図３２に一例を示す。状態qsourceから遷移文字aによる状態遷移としてq1およびq2が存在する、すなわち非決定的であるため、遷移先の状態を併合する、すなわち図３３に示すように遷移先のNFA状態集合q1およびq2の和集合qn =q1∪q2への状態遷移とする。この手順は基本的に非特許文献１などに示されているDFAの生成手順と同様であるが、本実施の例では、更に、図３４のように、任意文字σanyによる状態遷移q2と遷移文字aによる状態遷移の終点q1を含む場合について、非決定的な遷移文字aに関する状態qn =q1∪q2への状態遷移の他に、除外文字σotherによる状態q1への遷移を生成する（図３５）。
【００９８】
図１３によって、ステップS104の「非決定的遷移の除去」の手続きについて説明する。本手続きおよび「σotherに関する非決定的遷移の除去」の手続きでは変数Retryを使用する。変数RetryはTRUEまたはFALSEのいずれかの値をとることができる。
【００９９】
まず「状態集合の初期化」の手続きを行い、ステップS402に進む（ステップS401）。
【０１００】
次いで、変数RetryをFALSEに初期化し、ステップS401に進む（ステップS402）。
【０１０１】
次いで、「Σに関する非決定的遷移の除去」の手続きを行い。ステップS404に進む（ステップS403）。
【０１０２】
次いで、「σotherに関する非決定的遷移の除去」の手続きを行い、ステップS405に進む（ステップS404）。
【０１０３】
変数RetryがTRUEの場合はステップS403に進む。FALSEの場合は終了する（ステップS405）。
【０１０４】
以上の手順に従って、手続き「非決定的遷移の除去」を行うことができる。
【０１０５】
次にステップS401の「状態集合の初期化」の手続きについて説明する。本手続きは、DFAの状態を生成するため、必要な状態集合を初期化するためのものであり、すべてのNFAの状態q(NFA)に対して、DFAの状態{q(NFA)}を関連する状態遷移ととともに生成することを目的とする。
【０１０６】
図１４によって、ステップS401の「状態集合の初期化」の手続きについて説明する。
【０１０７】
まず、状態集合Qを空に初期化しステップS502に進む（ステップS501）。
【０１０８】
次に、q(NFA)をNFA状態集合Q(NFA)に含まれる最初のNFA状態とし、ステップS502に進む（ステップS502）。
【０１０９】
NFA状態集合Q(NFA)に含まれるすべてのNFA状態q(NFA)を処理した場合はステップS506に進む。それ以外の場合は、ステップS504に進む（ステップS503）。
【０１１０】
状態集合QにNFA状態集合（すなわちDFAの状態）{q(NFA)}を加え、ステップS505に進む（ステップS504）。
【０１１１】
q(NFA)をNFA状態集合Q(NFA)に含まれる次のNFA状態とし、ステップS503に進む（ステップS505）。
【０１１２】
ステップS503においてNFA状態集合Q(NFA)に含まれるすべてのNFA状態(NFA)を処理した場合は、状態遷移集合Tを空にし、ステップS507に進む（ステップS506）。
【０１１３】
次に、t(NFA)をNFA状態遷移集合T(NFA)に含まれる最初のNFA状態遷移とし、ステップS508に進む（ステップS507）。
【０１１４】
NFA状態遷移集合T(NFA)に含まれるすべてのNFA状態遷移t(NFA)を処理したらステップS511に進む。それ以外の場合は、ステップS509に進む（ステップS508）。
【０１１５】
状態遷移集合Tにtrans({Source(t(NFA))}, {Destination(t(NFA))}, Char(t(NFA)))を加え、ステップS510に進む（ステップS509）。
【０１１６】
t(NFA)をNFA状態遷移集合T(NFA)に含まれる次のNFA状態遷移とし、ステップS508に進む（ステップS510）。
【０１１７】
ステップS508においてT(NFA)に含まれるすべてのNFA状態遷移t(NFA)を処理した場合は、出力記述集合Dを空にし、ステップS512に進む（ステップS511）。
【０１１８】
次に、d(NFA)をNFA出力記述集合D(NFA)に含まれる最初のNFA出力記述とし、ステップS508に進む（ステップS512）。
【０１１９】
NFA出力記述集合D(NFA)に含まれるすべてのNFA出力記述d(NFA)を処理したら終了する。それ以外の場合は、ステップS509に進む（ステップS513）。
【０１２０】
出力記述集合Dにdesc({State(d(NFA))}, Result(d(NFA)))を加え、ステップS510に進む（ステップS514）。
【０１２１】
d(NFA)をNFA出力記述集合D(NFA)に含まれる次のNFA出力記述とし、ステップS508に進む（ステップS515）。
【０１２２】
以上の手順によって、手続き「状態集合の初期化」を行うことができる。
【０１２３】
次に、ステップS403の「Σに関する非決定的遷移の除去」の手続きについて説明する。本手続きでは、図３２および図３４に示した例のように、一つの遷移文字σ∈Σに対して複数の遷移先が存在するとき、新たな状態への遷移で置き換えることにより、各遷移文字σによる遷移先を一意に確定することを目的とする。
【０１２４】
図１５によって、ステップS403の「Σに関する非決定的遷移の除去」の手続きについて説明する。本手続きでは変数Foundを使用する。変数RetryはTRUEまたはFALSEのいずれかの値をとることができる。
【０１２５】
まず、FoundをFALSEに初期化し、ステップS602に進む（ステップS601）。
【０１２６】
次に、qを状態集合Q中の最初の状態遷移とし、ステップS603に進む（ステップS602）。
【０１２７】
状態集合Q中のすべての状態qを処理した場合はステップS616に進む。それ以外の場合はステップS604に進む（ステップS603）。
【０１２８】
σを入力アルファベットΣ中の最初のアルファベットとし、ステップS605に進む（ステップS604）。
【０１２９】
入力アルファベットΣ中のすべてのアルファベットσを処理した場合はステップS610に進む。それ以外の場合はステップS606に進む（ステップS605）。
【０１３０】
qを起点とし、σを遷移文字とする状態遷移tが複数存在するか、またはσを遷移文字とする状態遷移tとσanyを遷移文字とする状態遷移tが存在する、すなわち、σによる遷移が非決定的である場合は、ステップS607に進む。それ以外の場合はステップS609に進む(ステップS606)。
【０１３１】
パラメータqsourceをq、σtをσに設定し手続き「新状態の生成」を行い、ステップS608に進む（ステップS607）。
【０１３２】
変数FoundにTRUEを設定し、ステップS609に進む（ステップS608）。
【０１３３】
σを入力アルファベットΣ中の次のアルファベットとし、ステップS605に進む（ステップS609）。
【０１３４】
ステップS605で入力アルファベットΣ中のすべてのアルファベットσを処理した場合は、tを状態qを起点とする最初の状態遷移とし、ステップS611に進む(ステップS610)。
【０１３５】
状態qを起点とするすべての状態遷移tを処理した場合はステップS615に進む。それ以外の場合はステップS612に進む（ステップS611）。
【０１３６】
tの遷移文字Char(t)がσanyの場合はステップS613に進む。それ以外の場合はステップS614に進む（ステップS612）。
【０１３７】
tの遷移文字をσotherで置き換える、すなわちtを (Source(t), Destination(t), σother)でおきかえ、ステップS614に進む（ステップS613）。
【０１３８】
tを状態qを起点とする次の状態遷移とし、ステップS611に進む(ステップS614)。
【０１３９】
ステップS611で状態qを起点とするすべての状態遷移tを処理した場合はqを状態集合Q中の次の状態遷移とし、ステップS603に進む（ステップS615）。
【０１４０】
ステップS603で状態集合Q中のすべての状態qを処理した場合は、変数FoundがTRUEであればステップS601に進む。それ以外の場合は終了する（ステップS616）。
【０１４１】
以上の手順により、手続き「Σに関する非決定的遷移の除去」を行うことができる。
【０１４２】
次に、ステップS404の手続き「σotherに関する非決定的遷移の除去」について説明する。本手続きでは、図３６に示すように、「Σに関する非決定的遷移の除去」によって生成された遷移文字σotherによる遷移について、状態qsourceから複数の状態q1およびq2への状態遷移が存在する場合、それらの和集合qn =q1∪q2の状態への遷移で置き換えることにより、図３７に示すように、遷移文字σotherによる非決定的な遷移を除去する。
【０１４３】
図１６により、ステップS404の手続き「σotherに関する非決定的遷移の除去」について説明する。本手続きでは変数Foundを使用する。変数FoundはTRUEまたはFALSEのいずれかの値をとることができる。また本手続きでは変数Counterを使用する。変数Counterは0以上の整数値を取ることができる。
【０１４４】
まず、変数FoundにFALSEを設定し、ステップS702に進む（ステップS701）。
【０１４５】
qを状態集合Q中の最初の状態とし、ステップS703に進む（ステップS702）。
【０１４６】
状態集合Q中のすべての状態qを処理した場合はステップS714に進む。それ以外の場合はステップS701に進む（ステップS703）。
【０１４７】
変数Counterに0を設定し、ステップS705に進む（ステップS704）。
【０１４８】
tにqを起点とする最初の状態遷移を設定しステップS706に進む（ステップS705）。
【０１４９】
qを起点とするすべての状態遷移tを処理した場合はステップS710に進む。それ以外の場合はステップS707に進む（ステップS706）。
【０１５０】
tの遷移文字Char(t)がσotherの場合はステップS708に進む。それ以外の場合はステップS709に進む（ステップS707）。
【０１５１】
変数Counterに１を加え、ステップS709に進む（ステップS708）。
【０１５２】
tに、qを起点とする次の状態遷移を設定し、ステップS705に進む（ステップS709）。
【０１５３】
ステップS706においてqを起点とするすべての状態遷移tを処理した場合は、変数Counterの値が2以上であればステップS711に進む。それ以外の場合はステップS713に進む（ステップS710）。
【０１５４】
パラメータqsourceをq、σtをσotherに設定し、手続き「新状態の生成」を呼び出し、ステップS712に進む（ステップS711）。
【０１５５】
変数FoundにTRUEを設定し、また変数RetryにTRUEを設定し、ステップS713に進む（ステップS712）。
【０１５６】
qを状態集合Q中の次の状態遷移とし、ステップS703に進む（ステップS713）。
【０１５７】
ステップS703にて状態集合Q中のすべての状態qを処理した場合は、変数FoundがTRUEの場合はステップS701に進む。それ以外の場合は終了する（ステップS714）。
【０１５８】
以上の手順により、手続き「σotherに関する非決定的遷移の除去」を行うことができる。
【０１５９】
次に、ステップS607およびステップS711の手続き「新状態の生成」の手順について説明する。本手順は、状態qsourceから遷移文字σtに関する個々の非決定的な状態遷移を除去する手順である。
【０１６０】
図１７によって、ステップS607およびステップS711の手続き「新状態の生成」の手順について説明する。手続き「新状態の生成」ではqsourceおよびσtをパラメータとする。
【０１６１】
まず、状態qsourceを起点とし、σtにより遷移可能な状態の集合を求め、それらのNFA状態に関する和集合を求め、状態qnとする。qnが状態遷移集合Tに含まれている場合はステップS817に進む。それ以外の場合はステップS802に進む（ステップS801）。
【０１６２】
次に、状態qnを状態集合Qに追加し、ステップS803に進む（ステップS802）。
【０１６３】
tをqsourceを起点とする最初の状態遷移とし、ステップS804に進む（ステップS803）。
【０１６４】
qsourceを起点とするすべての状態遷移tを処理した場合はステップS817に進む。それ以外の場合はステップS805に進む（ステップS804）。
【０１６５】
Char(t)=σtの場合、またはChar(t)=σanyの場合はステップS806に進む。それ以外の場合はステップS816に進む（ステップS805）。
【０１６６】
t1を、Destination(t)を起点とする最初の状態遷移とし、ステップS807に進む（ステップS806）。
【０１６７】
Destination(t)を起点とするすべての状態遷移t1を処理した場合はステップS812に進む。それ以外はステップS808に進む（ステップS807）。
【０１６８】
状態遷移trans(qn, Destination(t1), Char(t1))∈TでなければTにtrans(qn, Destination(t1), Char(t1))を追加し、ステップS809に進む（ステップS808）。
【０１６９】
Char(t1)=σotherであればステップS810に進む。それ以外であればステップS811に進む（ステップS809）。
【０１７０】
手続き「σotherによる状態遷移の補正」を呼び出し、ステップS811に進む。このとき、パラメータとして(qsource, qn, t1)を与える(ステップS810)。
【０１７１】
t1を、Destination(t)を起点とする次の状態遷移とし、ステップS807に進む（ステップS811）。
【０１７２】
ステップS807でDestination(t)を起点とするすべての状態遷移t1を処理した場合は、dをDestination(t)を出力状態とする最初の出力記述とし、ステップS813に進む(ステップS812)。
【０１７３】
Destination(t)を出力状態とするすべての出力記述dを処理した場合はステップS816に進む。それ以外の場合は、ステップS814に進む（ステップS813）。
【０１７４】
出力記述desc(qn,Result(d))∈DでなければDにdesc(qn,Result(d))を加え、ステップS815に進む（ステップS814）。
【０１７５】
dをDestination(t)を出力状態とする次の出力記述とし、ステップS813に進む（ステップS815）。
【０１７６】
tをqsourceを起点とする次の状態遷移とし、ステップS804に進む（ステップS816）。
【０１７７】
ステップS801でqnが状態遷移集合Tに含まれていない場合、およびステップS804でqsourceを起点とするすべての状態遷移tを処理した場合は、tをqsourceを起点とする最初の状態遷移とし、ステップS818に進む（ステップS817）。
【０１７８】
qsourceを起点とするすべての状態遷移tを処理した場合はステップS822に進む。それ以外の場合はステップS819に進む（ステップS818）。
【０１７９】
Char(t)=σtの場合はステップS820に進む。それ以外の場合はステップS821に進む（ステップS819）。
【０１８０】
状態遷移tを状態遷移集合Tから削除し、ステップS821に進む（ステップS820）。
【０１８１】
tをqsourceを起点とする次の状態遷移とし、ステップS818に進む（ステップS821）。
【０１８２】
ステップS818でqsourceを起点とするすべての状態遷移tを処理した場合は、状態遷移trans(qsource, qn, σt) ∈TでなければTにtrans(qsource, qn, σt)を追加し、終了する（ステップS822）。
【０１８３】
以上の手順により、手続き「新状態の生成」を行うことができる。
【０１８４】
次にステップS811の手続き「σotherによる状態遷移の補正」について説明する。本手続きは、図３８に示すように、非決定的遷移の除去の際に併合すべき状態q1, q2を起点とする状態遷移の中に遷移文字σotherによる状態遷移が含まれる場合の、状態q1, q2を起点とする状態遷移の終点となる状態の併合の手順を示すものである。図３８の状態q1, q2を併合すると図３９のようになり、状態qn =q1∪q2遷移文字bによる状態遷移の終点はq3∪q5となる。同様に、図４０に示す状態q1, q2を併合すると、図４１に示すように遷移文字b、c、σotherによる状態遷移の終点は、それぞれq3∪q6、q4∪q5、q4∪q6となる。
【０１８５】
図１８によって、ステップS811の手続き「σotherによる状態遷移の補正」について説明する。本手続きでは、拡張入力アルファベットσ∈Σsの集合、CharSetを用いる。
【０１８６】
まずCharSetを空に初期化し、ステップS902に進む（ステップS901）。
【０１８７】
次に、tをSource(tother)を起点とする最初の状態遷移とし、ステップS903に進む（ステップS902）。
【０１８８】
Source(tother)を起点とするすべての状態遷移を処理した場合は、ステップS907に進む。それ以外の場合は、ステップS904に進む（ステップS903）。
【０１８９】
Char(t)が入力アルファベットΣに含まれる、すなわち、Char(t)≠σanyかつChar(t)≠σotherの場合はステップS906に進む。それ以外の場合はステップS905に進む（ステップS904）。
【０１９０】
CharSetにChar(t)を加え、ステップS906に進む（ステップS905）。
【０１９１】
tをSource(tother)を起点とする次の状態遷移とし、ステップS903に進む（ステップS906）。
【０１９２】
ステップS903でSource(tother)を起点とするすべての状態遷移を処理した場合は、t を状態qを起点とする最初の状態遷移とし、ステップS908に進む（ステップS907）。
【０１９３】
状態qを起点とするすべての状態遷移qを処理した場合は終了する。それ以外の場合はステップS909に進む（ステップS908）。
【０１９４】
Destination(t)≠Source(tother )の場合はステップS910に進む。それ以外の場合はステップS916に進む（ステップS909）。
【０１９５】
t1 をDestination(t)を起点とする最初の状態遷移とし、ステップS911に進む（ステップS910）。
【０１９６】
Destination(t)を起点とするすべての状態遷移t1 を処理した場合はステップS916に進む。それ以外の場合はステップS912に進む（ステップS911）。
【０１９７】
Char(t1)が入力アルファベットΣに含まれる、すなわち、Char(t1)≠σanyかつChar(t1)≠σotherの場合はステップS913に進む。それ以外の場合はステップS915に進む（ステップS912）。
【０１９８】
Char(t1)がCharSetに含まれる場合はステップS915に進む。それ以外の場合はステップS914に進む（ステップS913）。
【０１９９】
状態遷移trans(qn, Destination(tother), Char(t1))∈TでなければTにtrans(qn, Destination(tother), Char(t1))を加え、ステップS915に進む（ステップS914）。
【０２００】
t1 をDestination(t)を起点とする次の状態遷移とし、ステップS911に進む（ステップS915）。
【０２０１】
ステップS909にてDestination(t)≠Source(tother )でなかった場合、あるいはステップS911にてDestination(t)を起点とするすべての状態遷移t1 を処理した場合は、t を状態qを起点とする次の状態遷移とし、ステップS908に進む（ステップS916）。
【０２０２】
以上の手順により、手続き「σotherによる状態遷移の補正」を行うことができる。
【０２０３】
次に、ステップS105の「未使用状態の除去」の手続きについて説明する。本手続きでは、これまでの処理の結果発生した、状態遷移の終点とならない状態、すなわち、どのような入力に対しても決して到達しない状態を削除する。
【０２０４】
図１９によって、ステップS105の「未使用状態の除去」の手続きについて説明する。本手続きでは変数Foundを用いる。変数FoundはTRUEまたはFALSEのいずれかの値をとることができる。
【０２０５】
まず、変数FoundをFALSEにし、ステップS1002に進む（ステップS1001）。
【０２０６】
次に、qを状態集合Qに含まれる最初の状態とし、ステップS1003に進む（ステップS1002）。
【０２０７】
状態集合Qに含まれるすべての状態qを処理した場合はステップS1017に進む。それ以外の場合はステップS1004に進む（ステップS1003）。
【０２０８】
qが初期状態q0の場合はステップS1016に進む。それ以外の場合はステップS1005に進む（ステップS1004）。
【０２０９】
qを終点とする状態遷移が存在する場合はステップS1016に進む。それ以外の場合はステップS1006に進む（ステップS1005）。
【０２１０】
変数FoundをTRUEにし、ステップS1007に進む（ステップS1006）。
【０２１１】
tをqを起点とする最初の状態遷移とし、ステップS1008に進む(ステップS1007)。
【０２１２】
qを起点とするすべての状態遷移tを処理した場合はステップS1011に進む。それ以外の場合はステップS1009に進む（ステップS1008）。
【０２１３】
状態遷移tを状態遷移集合Tから取り除き、ステップS1010に進む（ステップS1009）。
【０２１４】
tをqを起点とする次の状態遷移とし、ステップS1008に進む(ステップS1010)。
【０２１５】
ステップS1008でqを起点とするすべての状態遷移tを処理した場合は、dをqを出力状態とする最初の出力記述とし、ステップS1012に進む（ステップ1011）。
【０２１６】
qを出力状態とするすべての出力記述dを処理した場合はステップS1015に進む。それ以外の場合はステップ1013に進む（ステップ1012）。
【０２１７】
出力記述dを出力記述集合Dから削除し、ステップS1014に進む（ステップS1013）。
【０２１８】
dをqを出力状態とする次の出力記述とし、ステップS1012に進む（ステップS1014）。
【０２１９】
ステップS1012にてqを出力状態とするすべての出力記述dを処理した場合は、状態qを状態集合Qから削除し、ステップS1012に進む（ステップS1015）。
【０２２０】
qを状態集合Qに含まれる次の状態とし、ステップS1003に進む（ステップS1016）。
【０２２１】
ステップ1003にて状態集合Qに含まれるすべての状態qを処理した場合は、変数Foundを調べFoundがTRUEの場合はステップS1002に進む。それ以外の場合は終了する（ステップ1017）。
【０２２２】
以上の手順により、手続き「未使用状態の除去」を行うことができる。
【０２２３】
なお、手続き「未使用状態の除去」は、状態遷移表を格納するのに必要なメモリ容量を削減することを目的としている。従って、本手続きを省略しても手続き「入力文書の照合」を実行することは可能であり、省略することにより、「照合条件のコンパイル」に要する時間を短縮することができる。
【０２２４】
次に、図２０によって、ステップS106の「冗長状態の除去」の手続きについて説明する。本手続きでは、２種類の不要な状態を除去する。第1の場合は、σotherによる状態遷移と同一の終点の状態を持つ状態遷移である。図４２に一例を示す。図４２において、遷移文字bによるq3を終点とする状態遷移を削除してもSDFAオートマトンの動作は同じであり、この状態遷移を削除することにより、状態遷移の総数を削減し、状態遷移表を格納するのに必要なメモリ容量を削減することができる。第２の場合は、すべての遷移文字に対する状態遷移の終点が等しい複数の状態の併合である。図４３に一例を示す。図４３において、状態q1と状態q2ではすべての遷移文字に対する状態遷移の終点が等しいため、状態q1と状態q2を併合したqn＝q1∪q2で置換することができる。これらの２種類の場合の一方によって状態または状態遷移が削除されると、それにより他方による状態または状態遷移の削除が可能になる場合があるため、新たに状態または状態遷移が削除されなくなるまでこれら２種類を繰り返す。
【０２２５】
図２０によって、ステップS106の「冗長状態の除去」の手続きについて説明する。本手続きでは変数StateRemovedおよびTransitionRemovedを用いる。変数StateRemovedおよびTransitionRemovedはTRUEまたはFALSEのいずれかの値をとることができる。
【０２２６】
まず、StateRemovedにTRUEを設定し、ステップS1102に進む（ステップS1101）。
【０２２７】
手続き「冗長な状態遷移の削除」を呼び出し、ステップS1103に進む。本手続きの中でTransitionRemovedが設定される（ステップS1102）。
【０２２８】
TransitionRemoved=FALSEかつStateRemoved=FALSEの場合は終了する。それ以外の場合はステップS1104に進む（ステップS1103）
【０２２９】
手続き「冗長な状態の併合」を呼び出し、ステップS1105に進む（ステップS1104）。
【０２３０】
TransitionRemoved=FALSEかつStateRemoved=FALSEの場合は終了する。それ以外の場合はステップS1102に進む（ステップS1105）。
【０２３１】
以上の手順により、手続き「冗長状態の除去」を行うことができる。
【０２３２】
なお、手続き「冗長状態の除去」は、状態遷移表を格納するのに必要なメモリ容量を削減することを目的としている。従って、本手続きを省略しても手続き「入力文書の照合」を実行することは可能であり、省略することにより、「照合条件のコンパイル」に要する時間を短縮することができる。
【０２３３】
次に、ステップS1102の手続き「冗長な状態遷移の削除」について説明する。本手続きは、「冗長状態の除去」の第1の場合に相当し、図４２に示すような、σotherによる状態遷移と同一の終点の状態を持つ状態遷移を削除する。
【０２３４】
図２１によって、ステップS1102の手続き「冗長な状態遷移の削除」について説明する。
【０２３５】
まず、変数TransitionRemovedをFALSEに設定し、ステップS1202に進む（ステップS1201）。
【０２３６】
次に、tを状態遷移集合Tに含まれる最初の状態遷移とし、ステップS1203に進む（ステップS1202）。
【０２３７】
状態遷移集合Tに含まれるすべての状態tを処理した場合は終了する。それ以外の場合は、ステップS1204に進む（ステップS1203）。
【０２３８】
Char(t)がσotherである場合にはステップS1205に進む。それ以外の場合はステップS1210に進む（ステップS1204）。
【０２３９】
次に、t1をSource(t)を起点とする最初の状態遷移とし、ステップS1206に進む（ステップS1205）。
【０２４０】
Source(t)を起点とするすべての状態遷移t1を処理した場合はステップS1210に進む。それ以外の場合は、ステップS1207に進む（ステップS1206）。
【０２４１】
t1≠tかつDestination(t1)=Destination(t)の場合はステップS1208に進む。それ以外の場合はステップS1209に進む（ステップS1207）。
【０２４２】
状態遷移t1を状態遷移集合Tから削除し、ステップS1209に進む（ステップS1208）。
【０２４３】
t1をSource(t)を起点とする次の状態遷移とし、ステップS1206に進む（ステップS1209）。
【０２４４】
ステップS1204にてChar(t)がσotherでなかった場合、またはステップS1206にてSource(t)を起点とするすべての状態遷移t1を処理した場合は、tを状態遷移集合Tに含まれる次の状態遷移とし、ステップS1203に進む（ステップS1210）。
【０２４５】
以上の手順により、手続き「冗長な状態遷移の削除」を行うことができる。
【０２４６】
次に、ステップ1104の手続き「冗長な状態の併合」について説明する。本手続きは、「冗長状態の除去」の第２の場合、すなわち、図４３に示すような、すべての遷移文字に対する状態遷移の終点が等しい複数の状態を併合する。
【０２４７】
ステップ1104の手続き「冗長な状態の併合」は、例えば、非特許文献１などに記載されている公知の手順により実行可能である。この手順によって、１つ以上の状態が併合されたときは変数StateRemovedをTRUEに設定する。それ以外の場合は変数StateRemovedをFALSEに設定する。
【０２４８】
次に、図２２によりステップS107の「状態遷移表と出力表の生成」について説明する。本手続きでは、状態集合２５、状態遷移集合２６、および出力記述集合２７から、状態遷移１１と出力記述１２を取り出し、それぞれ状態遷移表格納部４、出力表格納部１２に格納する。
【０２４９】
まず、状態集合Qに含まれている状態の総数をNとするとき、各状態qに0〜N-1の一意の状態番号StateId(q)を対応づける（ステップS1301）。
【０２５０】
状態遷移集合Tから最初の状態遷移tを取り出す（ステップS1302）。
【０２５１】
状態遷移集合Tに含まれるすべての状態遷移tを処理したらステップS1307に進む。それ以外の場合はステップS1304に進む（ステップS1303）。
【０２５２】
現状態Source(t)、入力文字Char(t)の組に対してハッシュ値計算部３１でハッシュ値３２を計算し、ステップS1305に進む（ステップS1304）。
【０２５３】
ハッシュ値３２をオフセットとする状態遷移ハッシュポインタ３３に現状態Source(t)、入力文字Char(t) 、次状態Destination(t)の組から成る状態遷移ハッシュチェイン３４を追加し、ステップS1306に進む(ステップS1305)。
【０２５４】
tを状態遷移集合Tに含まれる次の状態遷移とし、ステップS1303に進む（ステップS1306）。
【０２５５】
ステップS1303にて状態遷移集合Tに含まれるすべての状態遷移を処理した場合は、出力記述集合から最初の出力記述dを取り出す（ステップS1307）。
【０２５６】
出力記述集合Dに含まれるすべての出力記述dを処理したら終了する。それ以外の場合はステップS130に進む（ステップS1308）。
【０２５７】
State(d)の状態番号StateId(State(d))に対応する条件番号インデックス４１に条件番号チェイン４２としてResult(d)を追加しステップS1310に進む（ステップS1309）。
【０２５８】
dを出力記述集合Dに含まれる次の出力記述とし、ステップS1308に進む（ステップS1310）。
【０２５９】
以上に示した手順により、手続き「状態遷移表と出力表の生成」を実行することができる。
【０２６０】
次いで、図２３によって、手続き「入力文書の照合」について説明する。
【０２６１】
まず、状態qに初期状態q0を設定し、ステップS2002に進む（ステップS2001）。
【０２６２】
出力表格納部５を探索し、qに関連する条件番号16を出力する。この手順は、条件番号インデックス４１の現状態１３の状態番号StateId(q)に対応する条件番号チェイン４２へのポインタを順に探索することによって実現される。すべての条件番号チェイン４２の探索が終わったらステップS2003に進む（ステップS2002）。
【０２６３】
入力がすべて終了したら終了する。それ以外の場合はステップS2004に進む（ステップS2003）。
【０２６４】
入力文字読み取り部7から次の入力文字14を受け取り、σとし、ステップS2005に進む（ステップS2004）。
【０２６５】
状態遷移表格納部４を探索し、状態qから遷移文字σによる遷移先qdが存在するか否か、すなわち、trans(q, qd, σ)∈Tなるqdが存在するかどうか調べ、ステップS2006に進む（ステップS2005）。
【０２６６】
遷移先qdが存在する場合はステップS2007に進む。それ以外の場合はステップS2008に進む（ステップS2006）。
【０２６７】
qに qdを設定し、ステップS2002に進む(ステップS2007)。
【０２６８】
ステップS2006でqdが存在しない場合は、状態qから遷移文字σotherによる遷移先qdが存在するか否か、すなわち、trans(q, qd, σother)∈Tなるqdが存在するかどうか調べ、ステップS2009に進む（ステップS2008）。
【０２６９】
遷移先qdが存在する場合はステップS2007に進む。それ以外の場合はステップS2010に進む（ステップS2009）。
【０２７０】
状態qにq0を設定し、ステップS2006に進む。
【０２７１】
以上の手順により、手続き「入力文書の照合」を行うことができる。
【０２７２】
以下、図４４に示す照合条件２と図５４に示す入力文字列の場合を例にとって、本実施の例の文字列照合装置の動作を説明する。図４４の照合条件は特許文献３に示されていた図５２の照合条件の表記を本実施の例の形式にあわせたものであり、図５２と論理的に等価な照合条件である。
【０２７３】
ステップS51に示した手続き「照合条件コンパイル」を実行することにより、図４４の照合条件２から、図４５に示す状態遷移表と、図４６に示す出力表が生成される。なお、初期状態の状態番号を０とする。
【０２７４】
図４５の状態遷移表は状態遷移表格納部４に格納される現状態１３、入力文字１４に対する次状態１５を表で表現したものであり、例えば、現状態の状態番号が６で入力文字「d」の時、次状態は10となることを示している。図中で「−」は、次状態１５が存在しないことを示しており、このような組み合わせに対しては状態遷移表格納部４はメモリを消費することなく格納することができる。従来の出力つき有限状態オートマトンでは図５３に示す通り、９０個の組み合わせを必要とするのに対し、図４５の例では、４６個の状態遷移につき情報を格納すればよく、状態遷移表を格納するのに必要なメモリを削減するという効果が得られている。
【０２７５】
図４６の出力表は出力表格納部５に格納される現状態１３に対応する条件番号１６の集合を表で表現したものであり、例えば、現状態が４のとき、条件番号０を出力することを示している。
【０２７６】
一例として入力文字列「aaca」を入力とした場合の動作を図４７に示す。まず、状態qを初期状態（状態０）に設定する。次いで１文字目の文字「a」を読み、状態０における文字「a」の遷移先である状態２に遷移する。文字「a」による遷移先が定義されているのでσotherの参照は不要であり、このことを図４７中では（不要）と表記している。次に、２文字目の文字「a」を読み、状態２における文字「a」の遷移先である状態５に遷移する。次に、３文字目の文字「c」を読み、状態５における文字「c」の遷移先である状態９に遷移する。次に、４文字目の文字「a」を読み、状態９における文字「a」の遷移先である状態１２に遷移する。ここで入力が終了する。
【０２７７】
特許文献３に記載された従来の技術では同等の条件に対して７回の状態遷移表の参照を必要としていたが、本実施の例では４回で済む。このように、本発明によれば、遷移の失敗による状態遷移表の参照回数を１文字当り２回以下とし、遷移の失敗が繰り返されることによる性能低下による性能低下を防止し、高速な文字列照合を可能にすることを目的とする。
【０２７８】
なお、図４４の照合条件は、特許文献３に記載の技術との比較のために記載したものであるが、初期状態からすべての文字による遷移が可能であると言う特殊な条件を持っている。図４４の照合条件の目的とするところは照合対象文字列「abcd」のうち一文字が変化してもその文字列を検出できるようにすることであるが、その目的および照合条件の意味をほとんど変更せずに図４８の照合条件に変換することができる。このような場合には、状態遷移に必要なメモリを更に削減し、本実施の例の効果をより発揮することができる。
【０２７９】
ステップS51に示した手続き「照合条件コンパイル」を実行することにより、図４８の照合条件２から、図４９に示す状態遷移表と、図５０に示す出力表が生成される。なお、初期状態の状態番号を０とする。
【０２８０】
図４９の状態遷移表の意味は図４５と同様であり、状態遷移表格納部４に格納が必要な状態遷移の数は２３個に削減され、更に必要なメモリを削減するという効果が得られている。
【０２８１】
また、図４８の照合条件２について、入力「xabxd」に対する動作を図５１に示す。状態０において１文字目の「x」の遷移先は定義されていないので、σotherを参照するが、それでも遷移先が定義されていないので次状態は初期状態、すなわち状態０とする。このとき状態遷移表の参照は２回行われる。以下、２文字目の「a」で状態３、３文字目の「b」で状態６に遷移する。４文字目の「x」では、「x」の遷移先は定義されていないので、σotherを参照し、次状態１を得る。このとき状態遷移表の参照は２回である。更に、５文字目の「d」で状態２に遷移する。状態２は出力となる条件番号１６として番号０が存在しているので、これを出力する。この場合、状態遷移表の参照回数は７回となる。
【０２８２】
なお、非特許文献１など記述されているように、出力を持たない一般のDFAは、出力アルファベットとして「受理した」「受理しない」という２種類の情報を出力する特殊なMoore機械とみなすことができる。本実施の例でも、単に照合結果に条件番号が存在するか否かを判定することにより、「受理した」「受理しない」という２種類の情報を出力する文字列照合装置を構成できる。
【０２８３】
なお、以上の実施の例では、入力および照合の対象は「文字」であるとしてきたが、「文字」は人間に可読な文字列に限定されず、任意の記号列、データ列に対して適用が可能である。例えば遺伝子配列やセンサなどにより計測されたデータの識別に適用しても良い。
【０２８４】
なお、以上の実施の例では、状態遷移表格納部４に状態遷移ハッシュ表３５を使用するものとしたが、配列、木構造、など２次元構造の表を論理的に表現可能ないかなるデータ構造によって実現しても良い。
【０２８５】
また、初期状態など使用頻度の高い状態に対してはアクセス速度の高速な配列などのデータ構造を使用し、使用頻度の低い状態に対してはメモリ容量の効率の高いハッシュ表や木構造などのデータ構造を併用しても良い。
【０２８６】
なお、以上の実施の例では、出力表格納部５に条件番号インデックス４１を使用するものとしたが、木構造やハッシュ表など、１次元構造の表を論理的に表現可能ないかなるデータ構造によって実現してもよい。
【産業上の利用可能性】
【０２８７】
この発明は、文字列照合装置に適用することが可能である。
【図１】
2010225156.tif 000003
【図２】
2010225156.tif 000004
【図３】
2010225156.tif 000005
【図４】
2010225156.tif 000006
【図５】
2010225156.tif 000007
【図６】
2010225156.tif 000008
【図７】
2010225156.tif 000009
【図８】
2010225156.tif 000010
【図９】
2010225156.tif 000011
【図１０】
2010225156.tif 000012
【図１１】
2010225156.tif 000013
【図１２】
2010225156.tif 000014
【図１３】
2010225156.tif 000015
【図１４】
2010225156.tif 000016
【図１５】
2010225156.tif 000017
【図１６】
2010225156.tif 000018
【図１７】
2010225156.tif 000019
【図１８】
2010225156.tif 000020
【図１９】
2010225156.tif 000021
【図２０】
2010225156.tif 000022
【図２１】
2010225156.tif 000023
【図２２】
2010225156.tif 000024
【図２３】
2010225156.tif 000025
【図２４】
2010225156.tif 000026
【図２５】
2010225156.tif 000027
【図２６】
2010225156.tif 000028
【図２７】
2010225156.tif 000029
【図２８】
2010225156.tif 000030
【図２９】
2010225156.tif 000031
【図３０】
2010225156.tif 000032
【図３１】
2010225156.tif 000033
【図３２】
2010225156.tif 000034
【図３３】
2010225156.tif 000035
【図３４】
2010225156.tif 000036
【図３５】
2010225156.tif 000037
【図３６】
2010225156.tif 000038
【図３７】
2010225156.tif 000039
【図３８】
2010225156.tif 000040
【図３９】
2010225156.tif 000041
【図４０】
2010225156.tif 000042
【図４１】
2010225156.tif 000043
【図４２】
2010225156.tif 000044
【図４３】
2010225156.tif 000045
【図４４】
2010225156.tif 000046
【図４５】
2010225156.tif 000047
【図４６】
2010225156.tif 000048
【図４７】
2010225156.tif 000049
【図４８】
2010225156.tif 000050
【図４９】
2010225156.tif 000051
【図５０】
2010225156.tif 000052
【図５１】
2010225156.tif 000053
【図５２】
2010225156.tif 000054
【図５３】
2010225156.tif 000055
【図５４】
2010225156.tif 000056