JP5339236B2 - 要素列の近似的な照合又は検索及びその方法を実行するためのプログラムを格納した記録媒体 - Google Patents

Description

本発明は、要素列の近似的な照合又は検索及びその方法を実行するためのプログラムを格納した記録媒体に関する。特に、文章の要素列と複数の辞書語の要素列を比較する照合処理、あるいは、ある文章の要素列中からその文章の要素列より短い長さの要素列を探す検索処理を近似的に行う照合又は検索の効率化に関するものである。

今日、パーソナルコンピュータ等の普及に伴い、パーソナルコンピュータにインストールされた文書作成ソフトウェアを用いて、文章データが大量に作成され、利用されている。

ところで、大量に作成された文章データを活用する手段の一つとして、「検索」という方法があり、この方法は、パーソナルコンピュータや文書サーバ等内に文章データがあらかじめ蓄積されている状況で、利用者が「キーワード」を指定することで、蓄積された文章データから、文章中の部分文字列とキーワードの照合とを行って、キーワードを含む文章、あるいは当該文章中から一致するキーワードを探し出す処理を行うものである。

通常の検索は、一致するものを探す処理であるが、指定したキーワードと似ている綴りが文章中から検出できると便利な場合がある。このような目的のために不一致、すなわちエラーが許容される検索を「近似的」検索であるという。

近似的な文字列照合及び検索に関しては、二つの文字列の相違度を示す指標として「編集距離」というものがあり、また、ある文字列に対して、文字の挿入、削除、置換（違う文字への置き換え）又は転置（隣りあった文字の入れ替え）を行う操作として「編集操作」というものがある。１回の編集操作によって変形された文字列と元の文字列との編集距離を、その編集操作の「コスト」と呼び、ある文字列から編集操作を繰り返すことで別の文字列に変形することができ、二つの文字列の編集距離は各編集操作のコストの和で示される。以下では編集距離を「エラー値」と称することがある。

日本語の検索処理やその他の文章処理を実現するための最も基本的な技術に形態素解析がある。形態素解析は、英語等と異なって、日本語では語の区切りが明示されていないために、文章を単語に区切る処理のことである。形態素解析では、検索に準じた処理が行われるが、検索と異なる点は、文章の同一の部分文字列に対して複数のキーワードの同時照合を行って一致するキーワードを見出す点等である。すなわち、形態素解析は、キーワードに相当する語を、辞書データにあらかじめ複数蓄積しておき、処理のきっかけとして文章を与えるものであり、１対多の同時照合を行うものである。辞書データに登録されたキーワードは、辞書語と定義する。

ここで、誤りを含む文章とは、正しい文章とほとんどが同じで若干の部分が異なると考えれば、誤り検出も、検索に準じた処理が必要であるが、利用者が辞書語を指定する検索とは逆に、文章を指定し、その中から辞書データ中の辞書語と似ている部分文字列を探すもので、そのため、近似的に１対多の同時照合を行う必要があり、これは形態素解析を近似的に行うことに近い。

形態素解析のような１対多の同時照合に適したデータ構造として、複数の辞書語の先頭又は末尾から同じ文字を一つのノードに割り当てていくトライ（ｔｒｉｅ）という方法がある。トライは、木構造で表現され、木の各要素はノードと呼ばれる。

例えば、図１１は、「会社法」（平成１７年法律第８６号）と「会社計算規則」（平成１８年法務省令第１３号）という二つの法令名称とが含まれるトライの木構造の一部を示したものである。ノード０において“会”が入力されノード１に遷移したとき、入力された文字と、「会社法」の１文字目及び「会社計算規則」の１文字目との照合が１回で行われたことになり、処理の効率化が図られている。

１対多の近似的照合を行う場合は、Oflazerが示した方法が知られている（例えば、非特許文献１参照。）。この方法では、照合の対象として１個の語を与え、別に与えられた木構造のデータをバックトラック法で探索して得られる複数の文字列をもう一方の対象として各々の編集距離を計算し、編集距離の許容範囲内の文字列を結果として得るものである。

また、通信パケットのデータ（文字列）に対してパターン照合を行う技術に関するものとして、オリジナルパターンとオリジナルパターンの先頭からN文字（Nは自然数）ずつ削除してなる派生パターン、すなわち、接尾辞を用いて近似的照合を行うもの（例えば、特許文献１参照。）がある。

また、文章中から１個のキーワードを近似的に探す方法として、オートマトンという計算機の理論的モデルを用いるukkonenの方法がある（例えば、非特許文献２参照。）。

オートマトンとは、決められた規則に従って、いくつかの状態の間を移動（遷移）しながら計算を進める抽象的な機械である。状態とは、その物の内部の様子を表す言葉であり、一般的に状態数は有限である。また、遷移とは、ある状態から別の状態へ移り変わることをいい、ある状態の時にその状態に定められた遷移ルールと入力された文字との組み合わせによって定まる遷移先に状態が移り変わる。入力によって、あらかじめ「終了状態」と定められた状態に達した場合、入力が受理されたという。遷移ルールと入力された文字との組み合わせが未定義の場合は、特別な状態に遷移して停止する。なお一般に、後述する状態遷移図には特別な状態及び特別な状態への遷移を示さない。

オートマトンの状態の遷移を有向グラフで表したものを状態遷移図という。オートマトンの状態をグラフのノードに対応させ、遷移先を辺で示し、入力を辺ラベルに対応させて表す。以下では、入力を受け取って遷移した先のノードをアクティブなノードと称する。

図１２は、ukkonenによって提案された近似照合を行うオートマトン（以下「ukkonenのオートマトン」と称する。）の一例であり、文章中にキーワード「ＡＢＣ」と類似する部分文字列があるか否かを、エラー値の上限＝２まで許容して検索するオートマトンを示す図である。

ukkonenのオートマトンは、格子状に構成され、左上隅のノードが開始状態であり、右端の列の各ノードが終了状態である。最上行の各ノードはエラー値＝０の照合に、上から２行目はエラー値＝１の照合に対応する。エラー値の上限に応じて行が増やされる。
水平方向の遷移は文字どうしが一致する場合であり、垂直方向の遷移と斜め方向の遷移が不一致に対応する。
左上隅のノードに付けられたループ状の遷移は、照合が文章の任意の位置から開始できるようにするためのものである。

垂直方向の遷移は、文字の挿入に対応している。任意の文字の入力によって１行下のノードへ遷移する。図１２において、例えば、文章“ＡｘＢＣ”が入力されると、“Ａ”によって左上隅から１列右のノードに遷移し、“ｘ”によって１行下に遷移した後、“Ｂ”と“Ｃ”によって右端のノードまで水平に遷移して結果が出力される。“ＡｘＢＣ”を受理した際の経路を図１３に示す。

斜め方向の破線の遷移は、文字の削除に対応している。これはε遷移と呼ばれるもので、長さ０の語εの入力によって斜め右下のノードへ遷移する。図１２において、例えば、文章“ＡＣ”が入力されると、“Ａ”によって左上隅から１列右のノードに遷移するとともに、さらに斜め下のノードにも遷移する。この時、２個のノードが同時にアクティブになる（図１４（ａ））。“Ａ”の次に“Ｃ”が入力されると、２行目のノードにおいて１列右のノードに遷移し、結果が出力される。“ＡＣ”を受理した際の経路を図１４（ｂ）に示す。

斜め方向の実線の遷移は、文字の置換に対応している。任意の文字の入力によって斜め右下のノードへ遷移する。図１２において、例えば、文章“ＡｘＣ”が入力されると、“Ａ”によって左上隅から１列右のノードに遷移し、次に任意の文字“ｘ”が入力されると、１行目のノードから斜め右下のノードに遷移する。“ＡｘＣ”を受理した際の経路を図１５に示す。

ukkonenのオートマトンは、エラー値が上限に達した最下行のノードにおいては、右隣のノードへの遷移だけが可能であり、入力された文字が当該ノードの遷移ルールに明示された文字と一致しない場合にはオートマトンは停止する。

上記したような、複数のノードが同時にアクティブになるオートマトンを非決定性オートマトンという。ukkonenのオートマトンは、照合途中で正解候補が複数現れる非決定性オートマトンである。例えば、キーワード「ＡＢＣ」との近似的照合を行うukkonenのオートマトンに、文章“ＡＣＣ”が入力される状況を考える。照合は１文字ずつ順に行われるため、２文字目の“ＡＣ”までが入力された時点では、文章全体が、“ＡＢＣ”に“Ｃ”が挿入された“ＡＣＢＣ”なのか、“Ｂ”が削除された“ＡＣ”なのか、“Ｂ”が“Ｃ”に置換された“ＡＣＣ”なのかを判別することができない。そのため、可能性のある候補のノードがすべてアクティブになっている。

非決定性オートマトンの処理方法の一つを示すと、遷移先が複数ある場合、その時点までの経歴を同じくする機械（以下、「分身」と称す。）を作り、その後は各々が同時に手順通りの動作をし、その後も遷移先が複数あれば分身を作る。最終的に終了状態で終わった分身が一つでもあれば、文章はこの非決定性オートマトンで受理されたとする。

上記したように、ukkonenのオートマトンは、格子状に構成されて規則的であるので、同じ列のノードを重ねて一つに統合する変形は容易に考案される。

例えば、「ユーザーが間違った又は意図しない検索語を入力する」場合や、「原稿のテキスト、ＯＣＲ又は手動で入力されたキーワードにエラーがある場合」に対応する「ファジーな」検索を行うためにオートマトンを用いている技術が開示されている（例えば、特許文献２参照。）。

特開２００７−１４１０８４号公報 特開平８−２４１３３５号公報（図４、図乃至図１５）

Kemal Oflazer. Error-tolerant Finite-state Recognition with Applications to Morphologi cal Analysis and Spelling Correction. Computational Linguistics Vol.22, No.1 Gonzalo Navarro. A Guided Tour to Approximate String Matching. ACM Computing Surveys, Vol. 33, No. 1, March 2001, pp. 31-88.

しかしながら、非特許文献１のOflazerの方法は、１対多の照合が可能であるが、この場合は、語と語の照合であり、文章中からキーワードを探す検索は難しいという問題があった。例えば、文章“神奈川県の茅が崎市は、・・・”をOflazerの方法で検査しようとして形態素解析すると、“茅が崎”は「茅ヶ崎」の誤りであって形態素解析システム中の形態素データベースに存在しないため、同システムは“茅が崎”をデータベース中に存在する形態素に分解し、文章は「神奈川」「県」「の」「茅」「が」「崎」「市」「は」「、」「・・・」というように分解されてしまう。そのため、得られた各々の形態素と「茅ヶ崎」との近似的照合を行って誤りを発見することは難しいという問題があった。

また、特許文献１に開示されている技術は、１個のオリジナルパターンから枝分かれしたオートマトンが構成されるため、複数のオリジナルパターンから構成した複数のオートマトンをトライ構造に準じて結合することができず、本発明が目的とする複数の辞書語の同時照合は不可能であった。

また、特許文献２の図４、図６乃至図１５に記載されているオートマトンは、ukkonenのオートマトンにおいて同じ列のノードを重ねて一つに統合したものを基礎としていると推察されるので、このオートマトンを用いれば、文章とキーワードとの近似的照合が可能であるが、本発明が目的とする複数キーワードの同時照合を効率的に行うことができないという問題があった。なぜならば、前記オートマトンには、任意の文字の入力或いは長さ０の語εの入力による遷移があり、前記オートマトンは照合開始からすぐに状態遷移があり、さらに入力に従って多くのノードがアクティブになっていることから、複数のキーワードから構成した複数の前記オートマトンをトライ構造に準じて結合して、複数キーワードの同時照合を行った場合、すべてのキーワードに対する照合が実行されてしまうためである。

すなわち、上記した従来技術のいずれの方法においても、文章中から、あらかじめ登録しておいた複数の辞書語のいずれかと類似する部分文字列を効率的に検索することができないという問題があった。

本発明は、上記問題点を解決するためになされたものであり、オートマトンを変形した構成とすることであり、また、構成された複数のオートマトンを結合することである。このような構成のオートマトンを用いることで、実用上は重要でない遷移の発生を防止し、文章中から、あらかじめ登録しておいた複数の辞書語のいずれかと類似する部分文字列を効率的に検索することが可能となる要素列の近似的な照合又は検索及びその方法を実行するためのプログラムを格納した記録媒体を提供することを目的とする。

本発明は、オートマトンによる照合対象である文章の要素列と、辞書語の要素列とを近似的な照合又は検索をコンピュータによって実施させる方法であって、あらかじめ近似的な照合又は検索を行うための、オートマトンの遷移ルールが付与された辞書語の要素列を登録するための工程と、近似的な照合又は検索を行うための、エラー値の上限値を設定するための工程と、照合対象となる文章の要素列を入力するための工程と、遷移ルールが付与された辞書語の要素及びエラー値の上限値に基づき、第１の命令手順及び第２の命令手順によって、辞書語の要素と文章の要素列において照合対象となった部分文字列の要素とを照合し、辞書語の最後に照合を行った要素の位置情報ｐと、照合の不一致のエラー値ｅの内部的変数の組を生成する工程と、生成された内部的変数の組（ｐ、ｅ）を記憶する工程と、内部的変数の組（ｐ、ｅ）をもとに、照合結果を出力する工程を有することを特徴とする要素列の近似的な照合又は検索方法である。

また、本発明は、オートマトンによる照合対象である文章の要素列と、辞書語の要素列とを近似的な照合又は検索をコンピュータによって実施させる装置であって、あらかじめ近似的な照合又は検索を行うための、オートマトンの遷移ルールが付与された辞書語の要素列を登録するための遷移ルール記憶部と、照合対象となる文章の要素列を入力するための入力部と、近似的な照合又は検索を行うための、エラー値の上限値を設定し、遷移ルールが付与された辞書語の要素及びエラー値の上限値に基づき、第１の命令手順及び第２の命令手順によって、辞書語の要素と文章の要素列において照合対象となった部分文字列の要素とを照合し、辞書語の最後に照合を行った要素の位置情報ｐと、照合の不一致のエラー値ｅの内部的変数の組を生成するプログラム記憶部と、生成された内部的変数の組（ｐ、ｅ）を記憶する内部的変数記憶部と、内部的変数の組（ｐ、ｅ）をもとに、照合結果を出力する出力部と、入力部、遷移ルール記憶部、プログラム記憶部、内部的変数記憶部及び出力部の処理を行う処理部を有してなることを特徴とする要素列の近似的な照合又は検索を行うための照合装置である。

また、本発明の第１の命令手順は、遷移ルールの内容を解釈し、要素の位置情報ｐ及び入力された要素との組み合わせによって遷移先を決め、内部的変数の組の生成、参照又は更新の操作を行って状態遷移させ、第２の命令手順は、遷移ルールの内容を解釈することなく、内部的変数の組の直接的な生成、参照又は更新の操作を行う手順を追加するものであり、挿入エラー及び／又は削除エラーに必要な処理であることを特徴とする。

また、本発明の遷移ルールは、文章の要素列と、辞書語の要素列の要素の一致を認識するために、開始ノードから終了ノードへ至る各ノードの遷移条件に、辞書語の要素列の要素を順番に１個ずつ割り当てる遷移ルールを持ち、さらに、部分文字列の要素の挿入エラーを認識するために、開始ノード以外の各ノードにおいて、遷移条件を辞書語の次の要素以外の要素、遷移先を自分自身とする遷移ルールと、部分文字列の要素の削除エラーを認識するために、各ノードにおいて、遷移条件を辞書語の次の要素以降の要素を１個以上飛び越した位置の要素、遷移先を飛び越した先のノードとする遷移ルールとのいずれか一方又は両方を持ち、挿入エラーを認識する状態遷移があった時、エラー値に挿入エラーのコストが加算され、又は、削除エラーを認識する状態遷移があった時、エラー値に削除エラーのコストが加算されることを特徴とする。

また、本発明の第２の命令手順は、置換エラー及び／又は転置エラーの認識並びに複数の辞書語との同時照合に必要な処理を更に含むことを特徴とする。

また、本発明は、削除エラーの認識の直前に、１回以上の連続した挿入エラーの認識の繰り返しがあった時に、削除エラーの認識で認識された連続する１個以上の削除された要素のならびと１回以上の連続した挿入エラーの認識の繰り返しで認識された１個以上の挿入された要素のならびにおいて、削除された要素のならびの個数と挿入された要素のならびの個数の小さい方の個数について、削除された要素のならびが同数の挿入された要素のならびによって置換されたとみなして、エラー値を変更する置換エラーの認識が追加されたことを特徴とする。

また、本発明は、挿入エラーの認識の直前に削除エラーの認識があり、さらに、挿入エラーの認識で認識された挿入された要素と削除エラーの認識で認識された削除された要素のならびの最後の要素が同一である時に、文章の要素列において挿入された要素とその直前の要素が転置されているとみなして、挿入エラーを認識した状態遷移に加えて転置エラーを認識した状態遷移を同時に行うために、挿入エラーを認識した内部的変数の組の複製を生成し、複製された内部的変数の組のエラー値を変更する転置エラーの認識が追加されたことを特徴とする。

また、本発明は、辞書語が複数の場合において、文章の要素列と、辞書語の要素列の一致を認識する遷移ルールによって状態遷移する時に、遷移前である現在のノードが、一致を認識する遷移ルールが複数ある場合に、内部的変数の組を複製し、複製された内部的変数の組において、オートマトンから文章の要素列と、辞書語の要素列の要素の一致を認識する遷移ルールによって状態遷移する時の遷移条件及び遷移先を遷移ルールから除外し、除外されたオートマトンに、文章の要素列を続けて入力させる方法を追加することで、複数の辞書語の同時照合を行うことを特徴とする。

また、本発明は、上記記載の方法をコンピュータに実行させるプログラムである。また、本発明は、上記記載の方法をコンピュータに実行させるプログラムを格納した記録媒体である。

本発明は、枝分かれのない構造を持ち、さらに入力された文字列の要素がオートマトンの遷移ルールに明示された要素と一致した場合のみ他のノードに遷移するオートマトンを構成することによって、構成された複数のオートマトンをトライ構造に準じて結合することが可能となり、実用上は重要でない遷移の発生が防止されることによって、文章中から、あらかじめ登録しておいた複数の辞書語のいずれかと類似する部分文字列を効率的に検索することが可能となるという効果を奏する。

本発明の実施の形態における、図１２のオートマトンに施す一つ目の予備的変形を示す図である。 本発明の実施の形態における、図１２のオートマトンに施す二つ目の予備的変形を示す図である。 本発明の実施の形態における、図１２のオートマトンに施す二つ目の予備的変形を示す図である。 三つの予備的変形を行ったオートマトンを変形し、同じ列のノードを重ねて１個に統合する方法を示す図である。 実施例1及び実施例２における、近似的な照合又は検索をするための照合装置をコンピュータシステム上で実現した場合の概念的構成を示す図である。 文章中から、遷移ルール記憶部に登録している複数の辞書語のいずれかと類似する部分文字列を認識する処理の流れを示すフローチャートである。 図６のステップＳ００４において、一致、挿入エラー及び削除エラーを認識する手順を示すフローチャートである。 置換エラー、転置エラーの認識及び複数辞書語との同時照合に必要な手順を追加したフローチャートである。 辞書語「会社法」及び「会社計算規則」で構築したトライを元に作成したエラー値の上限＝１の辞書データの図である。 図９の辞書データを記憶させた照合装置に“会社法計算規則”（誤りを含む）を入力した時の内部的変数の状態及び照合装置の出力を表で示した図である。 辞書語「会社法」及び「会社計算規則」が含まれるトライの一部を示した図である。 文章中に辞書語「ＡＢＣ」と類似する部分文字列があるか判定するukkonenのオートマトンを示した図である。 図１２において、文章“ＡｘＢＣ”を受理した際の経路を示したものである。 図１２において２個のノードが同時にアクティブになる場合を示した図と、“ＡＣ”を受理した際の経路を示した図である。 図１２において、文章“ＡｘＣ”を受理した際の経路を示した図である。 文章の要素列と、辞書語の要素列とを近似的に照合又は検索をコンピュータによって実施させる方法の工程図である。

本発明を実施するための形態について、図面を用いて説明する。しかしながら、本発明は以下に述べる発明を実施するための形態に限定されるものではなく、特許請求の範囲に記載されている技術の範疇であれば、その他いろいろな実施の形態が含まれる。

本発明の実施の形態では、特に、要素列どうしを比較する照合処理、あるいは、ある要素列中からその要素列より短い長さの要素列を探す検索処理を近似的に行うための照合又は検索の効率化に関して述べる。

本発明において、ある集合の要素を順序付けて並べたものを要素列という。集合及び要素列の最も代表的なものとして文字及び文字列が挙げられる。その他には、形態素とその並びや、コンピュータの命令コードを並べて構成したプログラム等も該当し、あるいは通信路を流れるデータの列を対象としてもよい。以下の説明では、一例として文字列を取り上げ、要素を文字、要素列を文字列、語、文章又は辞書語と表記することもある。

本発明の実施の形態における、文章と複数の辞書語とで、１対１又は１対多の近似的な照合又は検索を行うための照合装置に用いられるオートマトンを構成する方法を説明する。

本発明の要素列の近似的な照合又は検索及びその方法を実行するためのプログラムを格納した記録媒体に用いるオートマトンは、ukkonenのオートマトンを変形することによって得られる。すなわち、ukkonenのオートマトンに三つの予備的変形を施し、予備的変形を施したオートマトンにおいて、同じ列のノードを重ねて一つに統合するという変形を行うものである。

ukkonenのオートマトンに施す三つの予備的変形は、入力された文字列の文字が、オートマトンの遷移ルールに明示された文字と一致した場合のみ他のノードに遷移させ、実用上は重要でない遷移の発生を防止することを目的としている。

一つ目の予備的変形は、文字置換に対応する斜め方向の実線の辺を除去するものである。置換エラーの存在は、後述のように挿入エラーと削除エラーの認識の並びから判断する。図１は、図１２に示したオートマトンに一つ目の予備的変形を施したものを示す図である。ukkonenのオートマトンから置換に対応する辺を除去したものである。

二つ目の予備的変形は、文字削除に対応するε遷移を、文字を飛び越す遷移に置き換えるものである。図２は、図１２に示したオートマトンに二つ目の予備的変形を施したものを示す図であり、１文字飛び越す場合の考え方を、図３は、２文字飛び越す場合の考え方を示した図である。ukkonenのオートマトンにおける１個の文字又は２個の文字の削除に対応するε遷移を、ノードを１個又は２個飛び越す遷移に置き換える場合である。

三つ目の予備的変形は、文字挿入に対応する垂直の辺において、遷移条件を「任意の文字」から「候補語の次の文字以外の文字」に変更するものである。

図４は、ukkonenのオートマトンに三つの予備的変形を行ったオートマトンを変形し、同じ列のノードを重ねて１個に統合する方法を示した図である。図４（ａ）は、ukkonenのオートマトンに三つの予備的変形を行ったオートマトンであり、図４（ｂ）は、図４（ａ）の三つの予備的変形を行ったオートマトンに、四つ目の変形を行った、本発明の近似的な照合又は検索を行うためのオートマトンである。つまり、図４（ａ）に示すオートマトンの同じ列のノードを重ねて１個に統合し、垂直方向及び斜め方向の遷移を、始点と終点の列位置が変わらないようにして付け替えたものである。

垂直方向に遷移する辺は、同じノードに戻るループ状の辺になり（以下、ループ辺と称する。）、斜め方向に遷移する破線の辺は、一つ以上のノードを飛び越す曲線の辺になる（以下、スキップ辺と称する。）。

すなわち、近似的な照合又は検索を行うために、本発明で構成したオートマトンは、辞書語との一致を認識するオートマトンに、ループ辺とスキップ辺を付加したものである。このオートマトンを、以下「線状のオートマトン」と称する。

本発明で構成したオートマトンについて、本実施の形態ではukkonenのオートマトンを出発点とした考え方を説明したが、必ずしもこれに限定されるものではなく、接尾辞木など別の出発点から考え方を展開することもできる。

ループ辺は、遷移によって同じノードに戻るので、実施の形態によっては、遷移先を示すデータを作成しなくてもよい場合がある。スキップ辺は、必要に応じてあらかじめデータを作成しておく。作成するデータの例として、例えば辞書データの構造にトライを用いている場合は有益である。

コンピュータに実行させるプログラムを格納した記録媒体としては、前述したフレキシブルディスク、ＣＤ-Ｒ、ＵＳＢメモリ、ハードディスクや、コンピュータシステム内のＲＡＭ等の揮発メモリを用いることが可能である。

実施例１では、文章の要素列と、辞書語の要素列の近似的な照合又は検索において、文章と複数の辞書語の１対１の同時照合に必要な手順を説明する。

図５は、実施例１に係わる本発明の文章の要素列と、辞書語の要素列の近似的な照合又は検索をするための照合装置１の一例を説明する図であり、照合装置１をコンピュータシステム上で実現した場合の概念的構成を示す図である。照合装置は、コンピュータシステムに限定されず、他の方法で構成してもよい。

照合装置１は、オートマトンを実行する機構をコンピュータシステム上で実現した場合の概念的構成に、内部的変数に対して直接的に生成又は参照、更新の操作を行って近似照合を実行する手順が追加される形態である。

照合装置１は、処理部２、遷移ルール記憶部３、内部的変数記憶部４及びプログラム記憶部５、入力部６、出力部７から構成される。

処理部２は、入力部６から要素列（文章）を受け取り、出力部７から結果を出力する。入力された要素列（文章）と辞書語との照合の処理に際し、遷移ルール記憶部３、内部的変数記憶部４及びプログラム記憶部５の各部に記憶された情報を用いる。

遷移ルール記憶部３は、認識させたい辞書語の辞書データが記憶され、辞書データは、近似的な照合又は検索を行うために構成した線状のオートマトンの遷移ルールであり、照合を行う前は変更可能であり、照合中は内容が参照されるのみで変更は行われない。

内部的変数記憶部４は、照合の処理中に処理部２によって生成された内部的変数の組（ｐ，ｅ）が複数同時に保持され、照合の処理中に組の数及び値が随時変化するものであり、内部的変数ｐは、遷移ルール記憶部３に記憶された各辞書語に対して、入力された文章の要素の最後に照合を行った場合、候補語の最後に照合を行った要素（文字）の位置情報を記録するものであり、内部的変数ｅは、要素（文字）の不一致に起因するエラー値を記録するものである。ここで候補語とは、辞書に登録された膨大な数の語のうち、照合の対象となった語のことである。つまり、照合のために内部的変数が生成された語のことである。例えば、辞書に「茅ヶ崎」と「小田原」が登録されていて、誤りを含む文章である「ここは茅ガ崎市。」が入力されると、「茅ヶ崎」は候補語となり、「小」、「田」、「原」、「小田原」等は候補語とはならない。よって、「小田原」は、照合を行う遷移が全く生じることがない。

プログラム記憶部５には、処理部２に対する命令手順が記憶され、オートマトンに相当する処理を行う第１の命令手順５ａと、内部的変数記憶部４に対して直接的に生成又は参照、更新の操作を行う第２の命令手順５ｂとに分類され、照合装置を構成した時点で処理に必要な命令手順が記憶され、以後は内容の変更は行われない。なお、検索範囲となるエラー値の上限値については、プログラム記憶部５で登録されている。上限値は、辞書語の文字数によってプログラム上で自動的に設定することも可能である。

第１の命令手順５ａは、オートマトンを実行する一般的な処理として、遷移ルール記憶部３の内容を解釈し、内部的変数ｐの値と入力された要素（文字）との組み合わせによって遷移先を決め、内部的変数記憶部４に対して、内部的変数の生成、参照又は更新の操作を行って状態遷移させる。

第２の命令手順５ｂは、装置側に追加する手順であり、遷移ルール記憶部３の内容に関わらず、内部的変数記憶部４に対して直接的に生成、参照又は更新の操作を行う手順を追加するものであり、挿入エラー及び／又は削除エラーに必要な処理の手順である。さらに、第２の命令手順は、置換エラー及び／又は転置エラーの認識並びに複数の辞書語との同時照合に必要な処理を含む手順である。

要素列の近似的な照合又は検索を行うための照合装置１は、オートマトンによる照合対象である文章の要素列と、辞書語の要素列とを近似的な照合又は検索をコンピュータによって実施させる装置であって、あらかじめ近似的な照合又は検索を行うための、オートマトンの遷移ルールが付与された辞書語の要素列を登録するための遷移ルール記憶部３と、照合対象となる文章の要素列を入力するための入力部６と、近似的な照合又は検索を行うための、エラー値の上限値を設定し、遷移ルールが付与された辞書語の要素及びエラー値の上限値に基づき、第１の命令手順５ａ及び第２の命令手順５ｂによって、辞書語の要素と文章の要素列において照合対象となった部分文字列の要素とを照合し、辞書語の最後に照合を行った要素の位置情報ｐと、照合の不一致のエラー値ｅの内部的変数の組を生成するプログラム記憶部５と、生成された内部的変数の組（ｐ、ｅ）を記憶する内部的変数記憶部４と、内部的変数の組（ｐ、ｅ）をもとに、照合結果を出力する出力部７と、入力部６、遷移ルール記憶部３、プログラム記憶部５、内部的変数記憶部４及び出力部７の処理を行う処理部２を有してなる。

図１６に示すように要素列の近似的な照合又は検索方法は、オートマトンによる照合対象である文章の要素列と、辞書語の要素列とを近似的な照合又は検索をコンピュータによって実施させる方法であって、あらかじめ近似的な照合又は検索を行うための、オートマトンの遷移ルールが付与された辞書語の要素列を登録するための辞書語要素列登録工程と、近似的な照合又は検索を行うための、エラー値の上限値を設定するための上限値設定工程と、照合対象となる文章の要素列を入力するための文章要素列入力工程と、遷移ルールが付与された辞書語の要素及びエラー値の上限値に基づき、第１の命令手順及び第２の命令手順によって、辞書語の要素と文章の要素列において照合対象となった部分文字列の要素とを照合し、辞書語の最後に照合を行った要素の位置情報ｐと、照合の不一致のエラー値ｅの内部的変数の組を生成する照合生成工程と、生成された内部的変数の組（ｐ、ｅ）を記憶する記憶工程と、内部的変数の組（ｐ、ｅ）をもとに、照合結果を出力する出力工程を有することを特徴とするである。

図６は、本発明の要素列の近似的な照合又は検索をするための照合装置１を用いて、入力された文章中から、遷移ルール記憶部３に登録している複数の辞書語のいずれかと類似する部分文字列を認識する処理の流れを示すフローチャートである。本実施例において、入力部６から文章が入力されるとソフトウェアは処理を実行することになる。

入力部６から文章が処理部２に入力されると照合が開始され、ステップＳ００１において、入力に続きがあるか判定し、入力が終了している場合はステップＳ００６に進んで後処理を行い、処理を終わる。

入力が終了していない場合は、ステップＳ００２に進んで文章から照合の対象とする文字を１文字取得する。以下、文章から取得した文字を入力文字と称する。

ステップＳ００３において、その時点で存在する内部的変数の組（ｐ，ｅ）のすべてにおいて入力文字との照合が行われたか調べ、行われている場合はステップＳ００５に進んで候補語検索を行い、ステップＳ００１に戻って次の入力文字の照合を行うというように、処理が終了するまで繰り返す。

照合が行われていない内部的変数の組（ｐ，ｅ）がある場合は、ステップＳ００４に進んで該当する組を一つ選び、入力文字と内部的変数が指す候補語の文字との照合を行い、ステップＳ００３に戻ってすべての組の照合を行う。照合の詳細は、図７を用いて後で説明する。すべての内部的変数の組について照合が行われた場合は、ステップＳ００５に進んで候補語検索を行い、ステップＳ００１に戻って次の入力文字の照合を行う。

候補語検索は、遷移ルール記憶部３中の辞書語を対象として、先頭の文字が入力文字と一致する辞書語、或いは先頭から文字を１個以上飛び越した位置の文字が入力文字と一致する辞書語を検索し、該当する辞書語を候補語とし、辞書データ３中で一致した文字の位置を内部的変数ｐに、飛び越した文字数の削除コストを内部的変数ｅに設定する。

照合装置１の機能としての、一致、挿入エラー及び削除エラーを認識する手順を図７のフローチャートを用いて説明する。

図６のフローチャートにおいて、入力文字と内部的変数ｐが指す候補語の文字との照合後に、ステップＳ００１及びステップＳ００２を実行して次の文字を取得し、照合を続ける状況であるとする。当該状況において、ステップＳ００３及びステップＳ００４の繰り返しにより、照合装置１が保持しているすべての内部的変数の組に対して、図７の処理を行う。

図７において、一致、挿入エラー及び削除エラーを認識する手順の流れは以下のとおりである。

ステップＳ１００は、入力文字と候補語の文字との一致を認識する手順であり、文字が一致する時は、ステップＳ１０１に進む。一致しない時は、ステップＳ２００に進む。

ステップＳ１０１は、文字が一致した時の内部的変数記憶部４に対する操作である。

ステップＳ２００は、削除エラーを認識する手順であり、削除エラーが認識された時は、ステップＳ２０１に進む。認識されなかった時は、ステップＳ３０１に進む。

ステップＳ２０１は、削除エラーが認識された時の内部的変数記憶部４に対する操作である。

ステップＳ２００において、削除エラーが認識された時、また、削除エラーが認識されなかった時のいずれの時も、最終的にはステップＳ３０１に進む。

ステップＳ３０１は、挿入エラーが認識された時の内部的変数記憶部４に対する操作である。

入力文字と候補語の文字との一致を認識する手順としては、ステップＳ１００において、入力文字と内部的変数ｐが指す候補語の文字の次の文字とを照合し、一致した場合はステップＳ１０１に進んで、文字の不一致に起因するエラー値を記録する内部的変数ｅは変えず、候補語において入力された文字との照合が行われた最後の文字の位置情報を記録する内部的変数ｐにはステップＳ１００において一致した文字を指す位置を記録する。

削除エラーを認識する手順としては、ステップＳ２００において、入力文字と内部的変数ｐが指す候補語の文字から文字を１個以上飛び越した位置の文字とを照合し、飛び越した位置の文字と一致した時はステップＳ２０１に進んで新たな内部的変数の組（ｐ'，ｅ'）を生成し、ｐ'にはステップＳ２００において一致した文字を指す位置を記録し、ｅ'にはｅの値に削除エラーのコストを加算した値を記録する。これはスキップ辺を遷移することに相当する。

挿入エラーを認識する手順としては、ステップＳ３０１において、内部的変数ｐは変えず、内部的変数ｅに挿入エラーのコストを加算する。これはループ辺を遷移することに相当する。

次に、図８のフローチャートを用いて照合装置１の更なる機能としての、置換エラー、転置エラー及び複数の辞書語との同時照合に必要な手順を説明する。図８のフローチャートは、図７のフローチャートに示す一致、挿入エラー及び削除エラーを認識する手順に、さらに、置換エラー、転置エラー及び複数の辞書語との同時照合に必要な手順を追加したフローチャートである。

図８のフローチャートにおける一致、挿入エラー及び削除エラーを認識する手順の考え方は、図７における場合と同じであり、図７及び図８におけるステップＳ１００、Ｓ１０１、Ｓ２００、Ｓ２０１、Ｓ３０１は同じ処理を行う。

照合装置１では、置換エラーの認識を、削除エラーとその直前の挿入エラーの並びを置換エラーに変換することで実現する。

例えば、辞書語「ＡＢＣ」との近似的照合を行うオートマトンに、文章“ＡｘｙＣ”が入力された場合、“Ａ”の後の“ｘｙ”の入力が挿入エラーとして認識され、その後の“Ｃ”の入力により「Ｂ」の削除エラーが認識される。これを、“ｘ”が挿入され、「Ｂ」が“ｙ”に置換されたと考える。

図８において、置換エラーが認識されるまでの手順の流れは以下のとおりである。

ステップＳ１００は、入力文字と候補語の文字との一致を認識する手順であり、文字が一致しない時は、ステップＳ２００に進む。

ステップＳ２００は、削除エラーを認識する手順であり、削除エラーが認識された時は、ステップＳ４００に進む。

ステップＳ４００は、置換エラーを認識する手順であり、置換エラーが認識された時は、ステップＳ４０１に進む。

ステップＳ４０１は、置換エラーが認識された時の内部的変数記憶部４に対する操作である。

なお、図８において置換エラーがないことが判明した時の各手順は以下のとおりである。

ステップＳ１００において、文字が一致する時は、ステップＳ６００に進む。

また、ステップＳ２００において、削除エラーが認識されなかった時は、ステップＳ５００に進む。

また、ステップＳ４００において、置換エラーが認識されなかった時は、ステップＳ２０１に進む。

置換エラーを認識する手順は、ステップＳ２００において削除エラーが認識された時に行われ、置換エラーを認識する手順としては、ステップＳ４００において、削除エラーの直前に挿入エラーが認識されていたかを調べ、挿入エラーが認識されていた時はステップＳ４０１に進んで新たな内部的変数の組（ｐ'，ｅ'）を生成し、ｐ'にはステップＳ２００において一致した文字を指す位置を記録し、ｅ'にはｅの値に置換エラーのコストを加算した値を記録する。

ステップＳ４０１における置換エラーのコストは、ｍ個の挿入エラーがｎ個の削除エラーの直前にある時に、ｍ≧ｎならば（ｍ−ｎ）個の挿入エラーとｎ個の置換エラーに、ｍ≦ｎならばｍ個の置換エラーと（ｎ−ｍ）個の削除エラーになるものとして算出する。

転置エラーの認識は、ukkonenのオートマトンではできないが、本発明の照合装置では置換エラーと同様な手順の追加で実現される。

例えば、辞書語「ＡＢＣ」の近似的照合を行うオートマトンに、文章“ＡＣＢ”が入力された場合、“Ａ”の後の“Ｃ”の入力により「Ｂ」の削除エラーが認識され、その後に“Ｂ”の入力があって挿入エラーが認識される。これを、「Ｂ」と「Ｃ」の転置と考える。

図８において、転置エラーが認識されるまでの手順の流れは以下のとおりである。

ステップＳ１００は、入力文字と候補語の文字との一致を認識する手順であり、文字が一致しない時は、ステップＳ２００に進む。

ステップＳ２００は、削除エラーを認識する手順であり、削除エラーの認識の成否に関わらずステップＳ５００に進む。

ステップＳ５００は、転置エラーを認識する手順であり、転置エラーが認識された時は、ステップＳ５０１に進む。

ステップＳ５０１は、転置エラーが認識された時の内部的変数記憶部４に対する操作である。

なお、図８において転置エラーがないことが判明した場合の各手順は以下のとおりである。

ステップＳ１００において、文字が一致する時は、ステップＳ６００に進む。

また、ステップＳ５００において、転置エラーが認識されなかった時は、ステップＳ３０１に進む。

転置エラーを認識する手順は、挿入エラーが認識された時の手順であるステップＳ３０１の前に行われ、転置エラーを認識する手順としては、ステップＳ５００において、挿入エラーの直前に削除エラーが認識され、かつ、隣り合った１個の挿入エラーとその直前の１個の削除エラーの並びにおいて挿入された文字と削除された文字とが同一であるかを調べ、同一である時にはステップＳ５０１に進んで新たな内部的変数の組（ｐ''，ｅ''）を生成し、ｐ''にはｐと同じ値を、ｅ''にはｅの値に転置エラーのコストを加算した値を記録する。

なお、転置エラーを認識する手順は、文章から文字を先読みで取得することが可能な場合は、削除エラーが認識された時、すなわち、ステップＳ２００とＳ４００の間において行ってもよく、削除エラーの直後の入力文字が削除された文字と同一である時には、ステップＳ５０１で行われる手順を行う。

前述した挿入、削除、置換及び転置の各エラーの認識手順には、エラー値を記録する内部的変数ｅの値が許容値を超えた場合に、照合を終了させる手順が含まれる。これは、本発明の照合装置に用いられるオートマトンの各ノードに付加されたループ辺により、入力文字と遷移ルールとの組み合わせが未定義となることがないため、オートマトンの停止が発生しないために必要である。

なお、エラー値の上限は、照合中の状況に応じて動的に、又、内部的変数の組ごとに別個に定めてもよい。

実施例１では、本発明の文章の要素列と、辞書語の要素列の近似的な照合又は検索をするために、文章と辞書語の１対１の照合の場合を説明したが、実施例２では、照合装置１において、文章と複数の辞書語との１対多の同時照合に必要な手順を説明する。

ここでは、遷移ルール記憶部３がトライ構造であるとする。図８のステップＳ１００において文字の一致があった時に、ステップＳ６００に進んで、現在のノードが複数の遷移ルールを持つか調べ、複数の遷移ルールを持つ時には、ステップＳ６０１に進んで内部的変数の組（ｐ，ｅ）の複製（ｐ'，ｅ'）を生成し、ステップＳ６０２に進み、ステップＳ６０２においては内部的変数の組（ｐ'，ｅ'）に対しステップＳ２００からＳ３０１までの処理を行う。

例えば、辞書語「会社法」及び「会社計算規則」を登録したトライを用いて、誤りを含む文章“会社法計算規則”の近似的照合を行う場合を考える。

図９は、辞書語「会社法」及び「会社計算規則」で構築したトライを元に作成したエラー値の上限＝１の辞書データを示す図である。

辞書語「会社法」及び「会社計算規則」が登録された図１１のトライに、ループ辺とスキップ辺を付加することによって、遷移ルール記憶部３に記憶させる辞書データが作成できる。これは容易であり、これにより複数の辞書語で近似的照合を行うことが可能となる。

図９において、３文字目の“法”が入力された時に、ノード３に遷移して照合が終了となるならば、文章“会社法計算規則”と辞書語「会社計算規則」との近似的照合が行われないことになる。そこで、一致によってノード２からノード３に遷移する際にノード２が複数の遷移ルールを持つか調べる。その結果、ノード２には「会社計算規則」との照合を行う他の遷移ルールがあったので内部的変数の組を新たに生成し、“法”が「会社計算規則」の３文字目と一致しなかったことに対応する。

図１０は、図５の照合装置１に、誤りを含む文章“会社法計算規則”を入力した時の、内部的変数の状態及び照合結果を出力部７から出力した図を示す。辞書語が複数の場合において、文章の要素列と、辞書語の要素列の一致を認識する遷移ルールによって状態遷移する時に、遷移前である現在のノードが、一致を認識する遷移ルールが複数ある場合に、内部的変数の組を複製し、複製された内部的変数の組において、オートマトンから文章の要素列と、辞書語の要素列の要素の一致を認識する遷移ルールによって状態遷移する時の遷移条件及び遷移先を遷移ルールから除外し、除外されたオートマトンに、文章の要素列を続けて入力させる方法を追加することで、複数の辞書語の同時照合を行う。

図５の照合装置１に、誤りを含む文章“会社法計算規則”を入力部６から入力した時の処理を説明する。

図１０において、照合を開始した時点においては、内部的変数はない。次に、入力文字“会”と関係する候補語が存在するか検索し、ノード１の文字と一致するので、内部的変数（ｐ，ｅ）＝（１，０）を生成して候補語とし、次の入力文字についての照合を行う。

入力文字“社”についての照合を行う。対象とする内部的変数は（ｐ，ｅ）である。

内部的変数（ｐ，ｅ）＝（１，０）は、図８のステップＳ１００において、ノード２の文字と一致するので、ステップＳ６００に進み、複数の遷移ルールがあるかを調べる。遷移ルールが１個であるのでステップＳ１０１に進み（ｐ，ｅ）＝（２，０）とする。

他に内部的変数がないので、次の入力文字についての照合を行う。

入力文字“法”についての照合を行う。対象とする内部的変数は（ｐ，ｅ）である。

内部的変数（ｐ，ｅ）＝（２，０）は、図８のステップＳ１００において、ノード３の文字と一致するので、ステップＳ６００に進み、複数の遷移ルールがあるかを調べる。
遷移ルールが２個あるので、ステップＳ６０１に進み（ｐ'，ｅ'）＝（２，０）を生成する。

内部的変数（ｐ'，ｅ'）＝（２，０）は、図８のステップＳ２００以降の処理が行われる。ステップＳ２００において、飛び越して一致するノードがないので、ステップＳ５００に進む。Ｓ５００の条件に適合しないのでステップＳ３０１に進み、（ｐ'，ｅ'）＝（２，１）とする。

内部的変数（ｐ，ｅ）＝（２，０）は、図８のステップＳ１０１に進み（ｐ，ｅ）＝（３，０）とする。ノード３は終了状態であるので、「会社法」が受理され、結果が出力される。（ｐ，ｅ）は廃棄される。

他に内部的変数がないので、次の入力文字についての照合を行う。

入力文字“計”についての照合を行う。対象とする内部的変数は（ｐ'，ｅ'）である。

内部的変数（ｐ'，ｅ'）＝（２，１）は、図８のステップＳ１００において、ノード４の文字と一致するので、ステップＳ６００に進み、複数の遷移ルールがあるかを調べる。遷移ルールが１個であるので、ステップＳ１０１に進み（ｐ，ｅ）＝（４，１）とする。

他に内部的変数がないので、次の入力文字についての照合を行う。

内部的変数（ｐ'，ｅ'）は、入力文字“算”、“規”、“則”について同様の処理が行われ、（ｐ'，ｅ'）＝（７，１）となる。ノード７は終了状態であるので、「会社計算規則」が受理され、結果が出力される。

以上の手順に従って実行することで、複数の辞書語で、誤りを含む文章の近似的照合を行うことができる。

１ 照合装置
２ 処理部
３ 遷移ルール記憶部（辞書データ）
４ 内部的変数記憶部
５ プログラム記憶部
６ 入力部
７ 出力部

Claims (8)

1. オートマトンによる照合対象である文章の要素列と、辞書語の要素列とを近似的な照合又は検索をコンピュータによって実施させる方法であって、
   あらかじめ近似的な照合又は検索を行うための、オートマトンの遷移ルールが付与された辞書語の要素列を登録するための工程と、
   前記近似的な照合又は検索を行うための、エラー値の上限値を設定するための工程と、
   照合対象となる文章の要素列を入力するための工程と、
   前記遷移ルールが付与された辞書語の要素及びエラー値の上限値に基づき、第１の命令手順及び第２の命令手順によって、前記辞書語の要素と前記文章の要素列において照合対象となった部分文字列の要素とを照合し、前記辞書語の最後に照合を行った要素の位置情報ｐと、照合の不一致のエラー値ｅの内部的変数の組を生成する工程と、
   前記生成された内部的変数の組（ｐ、ｅ）を記憶する工程と、
   前記内部的変数の組（ｐ、ｅ）をもとに、照合結果を出力する工程を有することを特徴とする要素列の近似的な照合又は検索方法。
2. 前記第１の命令手順は、遷移ルールの内容を解釈し、要素の位置情報ｐ及び入力された要素との組み合わせによって遷移先を決め、内部的変数の組の生成、参照又は更新の操作を行って状態遷移させ、
   前記第２の命令手順は、遷移ルールの内容を解釈することなく、内部的変数の組の直接的な生成、参照又は更新の操作を行う手順を追加するものであり、挿入エラー及び／又は削除エラーに必要な処理であることを特徴とする請求項１記載の要素列の近似的な照合又は検索方法。
3. 前記遷移ルールは、
   前記文章の要素列と、前記辞書語の要素列の要素の一致を認識するために、開始ノードから終了ノードへ至る各ノードの遷移条件に、辞書語の要素列の要素を順番に１個ずつ割り当てる遷移ルールを持ち、
   さらに、前記部分文字列の要素の挿入エラーを認識するために、開始ノード以外の各ノードにおいて、遷移条件を辞書語の次の要素以外の要素、遷移先を自分自身とする遷移ルールと、前記部分文字列の要素の削除エラーを認識するために、各ノードにおいて、遷移条件を辞書語の次の要素以降の要素を１個以上飛び越した位置の要素、遷移先を飛び越した先のノードとする遷移ルールとのいずれか一方又は両方を持ち、
   前記挿入エラーを認識する状態遷移があった時、前記エラー値に挿入エラーのコストが加算され、又は、前記削除エラーを認識する状態遷移があった時、前記エラー値に削除エラーのコストが加算されることを特徴とする請求項１又は２記載の要素列の近似的な照合又は検索を行う方法。
4. 前記第２の命令手順は、置換エラー及び／又は転置エラーの認識並びに複数の辞書語との同時照合に必要な処理を更に含むことを特徴とする請求項２又は３記載の要素列の近似的な照合又は検索方法。
5. 前記削除エラーの認識の直前に、１回以上の連続した前記挿入エラーの認識の繰り返しがあった時に、前記削除エラーの認識で認識された連続する１個以上の削除された要素のならびと前記１回以上の連続した挿入エラーの認識の繰り返しで認識された１個以上の挿入された要素のならびにおいて、前記削除された要素のならびの個数と前記挿入された要素のならびの個数の小さい方の個数について、前記削除された要素のならびが同数の前記挿入された要素のならびによって置換されたとみなして、前記エラー値を変更する置換エラーの認識が追加されたことを特徴とする請求項３又は４記載の要素列の近似的な照合又は検索を行う方法。
6. 前記挿入エラーの認識の直前に前記削除エラーの認識があり、
   さらに、前記挿入エラーの認識で認識された挿入された要素と前記削除エラーの認識で認識された削除された要素のならびの最後の要素が同一である時に、
   前記文章の要素列において前記挿入された要素とその直前の要素が転置されているとみなして、前記挿入エラーを認識した状態遷移に加えて転置エラーを認識した状態遷移を同時に行うために、前記挿入エラーを認識した内部的変数の組の複製を生成し、複製された内部的変数の組のエラー値を変更する転置エラーの認識が追加されたことを特徴とする請求項３乃至５のいずれか一項記載の要素列の近似的な照合又は検索を行う方法。
7. 前記辞書語が複数の場合において、
   前記文章の要素列と、前記辞書語の要素列の一致を認識する遷移ルールによって状態遷移する時に、遷移前である現在のノードが、前記一致を認識する前記遷移ルールが複数ある場合に、
   前記内部的変数の組を複製し、前記複製された内部的変数の組において、前記オートマトンから前記文章の要素列と、前記辞書語の要素列の要素の一致を認識する遷移ルールによって状態遷移する時の遷移条件及び遷移先を遷移ルールから除外し、前記除外されたオートマトンに、前記文章の要素列を続けて入力させる方法を追加することで、複数の辞書語の同時照合を行うことを特徴とする請求項１乃至６のいずれか一項記載の要素列の近似的な照合又は検索を行う方法。
8. 請求項１乃至７のいずれか一項記載の方法をコンピュータに実行させるプログラムを格納した記録媒体。

Images