(57)【要約】  本発明は、誤字や脱字、想定したキーワードと少し異なる表現が入力文字列に含まれ、抽出したいキーワード数が多い場合であっても、高速に抽出可能とすることを課題とする。その課題を解決するために、スキップ辞書作成部１０により、抽出したいキーワードとして予めリストアップされたキーワード辞書について、キーワードそのものと、当該キーワードの全ての文字位置から少なくとも１つの文字を削除した文字列の集合とからなる削除キーワードを含むスキップ辞書を作成してスキップ辞書記憶部２０に格納し、キーワード抽出部３０により、入力文字列と前記スキップ辞書とを照合することにより、入力文字列から予め与えられたキーワード及び当該キーワードに近似したキーワードを抽出し、その出現位置とともに出力する。
2010026804.tif 000002
【特許請求の範囲】
【請求項１】
自然言語で記述された入力文字列と所定のキーワードとを照合し、一致したキーワードとその出現位置を出力する近似照合装置であって、
予め与えられたキーワードに対して、キーワードそのものと、当該キーワードの全ての文字位置から少なくとも１つの文字を削除した文字列の集合とからなる削除キーワードを含むスキップ辞書を記憶するスキップ辞書記憶手段と、
前記入力文字列と、前記スキップ辞書記憶手段に記憶された前記スキップ辞書とを照合することにより、入力文字列から予め与えられたキーワード及び当該キーワードに近似したキーワードを抽出し、その出現位置とともに出力するキーワード抽出手段とを備えた
ことを特徴とする近似照合装置。
【請求項２】
前記削除キーワードは、前記予め与えられたキーワードそのものと、当該キーワードの全ての文字位置ｐｋから連続するｗｋ字（但し１≦ｗｋ≦ＮであってＮはキーワードの削除最大文字数）を削除した文字列の集合とからなり、
前記スキップ辞書は、前記集合の中の各削除キーワード毎に、当該削除キーワードの値として、その削除文字位置ｐｋ、削除文字数ｗｋ及び当該削除キーワードの元となったキーワードである元キーワードの組を含むことを特徴とする請求項１に記載の近似照合装置。
【請求項３】
前記キーワード抽出手段は、
前記入力文字列と前記スキップ辞書記憶手段に格納されたスキップ辞書とを照合し、スキップ辞書と一致した全てのキーワード侯補について、削除キーワードの削除文字数ｗｋが０ならば「キーワードが入力文字列中に完全一致で出現」を表す一致タイプＥＭに分類し、削除キーワードの削除文字数ｗｋが０より大きければ「入力文字列に削除文字が存在する状態でキーワードと一致」を表す一致タイプＤＥＬに分類し、分類した結果を一致タイプとして、一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数、元キーワードを記憶手段に記憶し、
入力文字列の絶対スキップ位置ｐを一つずつ増加させながらスキップ幅ｗｉ字（但し１≦ｗｉ≦ＮであってＮは入力文字列の最大スキップ幅）をスキップさせた文字列であるスキップ入力を作成し、各スキップ入力と前記スキップ辞書とを照合し、スキップ辞書と一致した全てのキーワード侯補について、キーワード上での相対スキップ位置ｐｉを算出し、削除キーワードの削除文字数ｗｋが０ならば「入力文字列に挿入文字が存在する状態でキーワードと一致」を表す一致タイプＩＮＳに分類し、削除キーワードの削除文字数ｗｋが０より大きく、かつ入力文字列の相対スキップ位置ｐｉと削除キーワードの削除文字位置ｐｋが等しく、かつ入力文字列のスキップ幅ｗｉと削除キーワードの削除文字数ｗｋが等しければ「入力文字列に置換文字が存在する状態でキーワードと一致」を表す一致タイプＲＥＰに分類し、分類した結果を一致タイプとして、一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数及び元キーワードを記憶手段に記憶するスキップ入力／スキップ辞書照合手段を有する
ことを特徴とする請求項２に記載の近似照合装置。
【請求項４】
前記キーワード抽出手段は、前記記憶手段から前記スキップ入力／スキップ辞書照合手段が出力したキーワード侯補の集合を読み出し、重複するものを削除したキーワードの集合を生成して出力する重複削除手段を更に有することを特徴とする請求項３に記載の近似照合装置。
【請求項５】
前記スキップ辞書における削除キーワードは、トライ構造を有しており、前記スキップ辞書／スキップ辞書照合手段は、
前記入力文字列と前記スキップ辞書との照合では、前記入力文字列を先頭から１文字ずつずらしながら前記スキップ辞書と照合し、一致したキーワードを得るとともに入力文字列の各文字位置でのキーワード照合失敗位置の値を保存しておき、
前記スキップ入力と前記スキップ辞書との照合では、絶対スキップ位置の値が前記入力文字列の文字位置の値以上または文字位置の値とキーワード照合失敗位置の値を加算した値以下の場合のみ、照合を行う
ことを特徴とする請求項３又は４に記載の近似照合装置。
【請求項６】
前記スキップ辞書における削除キーワードは、トライ構造を有しており、前記スキップ辞書／スキップ辞書照合手段は、
前記入力文字列と前記スキップ辞書との照合では、入力文字列とスキップ辞書をＡＣ法で照合し、一致したキーワードを得るとともに入力文字列の各文字位置での前記トライ構造のノード番号を保存しておき、
前記スキップ入力と前記スキップ辞書との照合では、絶対スキップ位置からＡＣ法による照合を再開し、前記トライ構造のノードが根ノードに遷移するまで照合する
ことを特徴とする請求項３又は４に記載の近似照合装置。
【請求項７】
自然言語で記述された入力文字列と所定のキーワードとを照合し、一致したキーワードとその出現位置を出力する近似照合装置が実行する近似照合方法であって、
前記近似照合装置は、予め与えられたキーワードに対して、キーワードそのものと、当該キーワードの全ての文字位置から少なくとも１つの文字を削除した文字列の集合とからなる削除キーワードを含むスキップ辞書を記憶するスキップ辞書記憶手段を備え、前記近似照合方法は、
キーワード抽出手段が、前記入力文字列と、前記スキップ辞書記憶手段に記憶された前記スキップ辞書とを照合することにより、入力文字列から予め与えられたキーワード及び当該キーワードに近似したキーワードを抽出し、その出現位置とともに出力するキーワード抽出ステップを含む
ことを特徴とする近似照合方法。
【請求項８】
前記削除キーワードは、前記予め与えられたキーワードそのものと、当該キーワードの全ての文字位置ｐｋから連続するｗｋ字（但し１≦ｗｋ≦ＮであってＮはキーワードの削除最大文字数）を削除した文字列の集合とからなり、
前記スキップ辞書は、前記集合の中の各削除キーワード毎に、当該削除キーワードの値として、その削除文字位置ｐｋ、削除文字数ｗｋ及び当該削除キーワードの元となったキーワードである元キーワードの組を含むことを特徴とする
ことを特徴とする請求項７に記載の近似照合方法。
【請求項９】
前記キーワード抽出ステップは、
前記入力文字列と前記スキップ辞書記憶手段に格納されたスキップ辞書とを照合し、スキップ辞書と一致した全てのキーワード侯補について、削除キーワードの削除文字数ｗｋが０ならば「キーワードが入力文字列中に完全一致で出現」を表す一致タイプＥＭに分類し、削除キーワードの削除文字数ｗｋが０より大きければ「入力文字列に削除文字が存在する状態でキーワードと一致」を表す一致タイプＤＥＬに分類し、分類した結果を一致タイプとして、一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数、元キーワードを記憶手段に記憶し、
入力文字列の絶対スキップ位置ｐを一つずつ増加させながらスキップ幅ｗｉ字、但し１≦ｗｉ≦ＮであってＮは入力文字列の最大スキップ幅、をスキップさせた文字列であるスキップ入力を作成し、各スキップ入力と前記スキップ辞書とを照合し、スキップ辞書と一致した全てのキーワード侯補について、キーワード上での相対スキップ位置ｐｉを算出し、削除キーワードの削除文字数ｗｋが０ならば「入力文字列に挿入文字が存在する状態でキーワードと一致」を表す一致タイプＩＮＳに分類し、削除キーワードの削除文字数ｗｋが０より大きく、かつ入力文字列の相対スキップ位置ｐｉと削除キーワードの削除文字位置ｐｋが等しく、かつ入力文字列のスキップ幅ｗｉと削除キーワードの削除文字数ｗｋが等しければ「入力文字列に置換文字が存在する状態でキーワードと一致」を表す一致タイプＲＥＰに分類し、分類した結果を一致タイプとして、一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数及び元キーワードを記憶手段に記憶するスキップ入力／スキップ辞書照合ステップを含む
ことを特徴とする請求項８に記載の近似照合方法。
【請求項１０】
前記スキップ入力／スキップ辞書照合ステップは、記憶手段から前記スキップ入力／スキップ辞書照合ステップにおいて記憶されたキーワード侯補の集合を読み出し、重複するものを削除したキーワードの集合を生成して出力するステップを有する
ことを特徴とする請求項９に記載の近似照合方法。
【請求項１１】
前記スキップ辞書における削除キーワードは、トライ構造を有しており、前記スキップ辞書／スキップ辞書照合ステップにおいて、前記キーワード抽出手段は、
前記入力文字列と前記スキップ辞書との照合では、前記入力文字列を先頭から１文字ずつずらしながら前記スキップ辞書と照合し、一致したキーワードを得るとともに入力文字列の各文字位置でのキーワード照合失敗位置の値を保存しておき、
前記スキップ入力と前記スキップ辞書との照合では、絶対スキップ位置の値が前記入力文字列の文字位置の値以上または文字位置の値とキーワード照合失敗位置の値を加算した値以下の場合のみ、照合を行う
ことを特徴とする請求項９又は１０に記載の近似照合方法。
【請求項１２】
前記スキップ辞書における削除キーワードは、トライ構造を有しており、前記スキップ辞書／スキップ辞書照合ステップにおいて、前記キーワード抽出手段は、
前記入力文字列と前記スキップ辞書との照合では、入力文字列とスキップ辞書をＡＣ法で照合し、一致したキーワードを得るとともに入力文字列の各文字位置での前記トライ構造のノード番号を保存しておき、
前記スキップ入力と前記スキップ辞書との照合では、絶対スキップ位置からＡＣ法による照合を再開し、前記トライ構造のノードが根ノードに遷移するまで照合する
ことを特徴とする請求項９又は１０に記載の近似照合方法。
【請求項１３】
コンピュータを、自然言語で記述された入力文字列と所定のキーワードとを照合し、一致したキーワードとその出現位置を出力する近似照合装置として機能させるためのプログラムであって、
前記コンピュータは、予め与えられたキーワードに対して、キーワードそのものと、当該キーワードの全ての文字位置から少なくとも１つの文字を削除した文字列の集合とからなる削除キーワードを含むスキップ辞書を記憶するスキップ辞書記憶手段を備え、前記プログラムは、前記コンピュータを、
請求項１乃至６のいずれかに記載の近似照合装置のキーワード抽出手段として機能させるためのプログラム。
【請求項１４】
請求項１３に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語で記述された文章（入力文字列）から予め与えられたキーワードを抽出するための、入力文字列と所定のキーワードとを照合し、一致したキーワードとその出現位置を出力する技術に関する。
【背景技術】
【０００２】
＜キーワード抽出＞
キーワード抽出は、自然言語で記述された入力文字列から、辞書のような予めリストアップされたキーワードを抽出するタスクである。【０００３】
例えば、図１に示す入力文字列から、オリンピックに関するキーワードを抽出することを考える。この場合、図２に示すような、抽出したいキーワードとして予め人手によりリストアップされたキーワードの集合（以下、キーワード辞書と呼ぶ。）中の各キーワードが前記入力文字列に含まれているかどうかを照合することにより抽出を行う。【０００４】
しかし、
１．入力文字列は、人手により記述（入力）された文字列なので、誤字や脱字が含まれていたり、想定したキーワードと少し異なる表現が使われていることがしばしばある、
２．キーワード数が多くなると、高速に抽出するのが困難になり、大量の入力文字列を処理するのに時間がかかる、という問題点がある。【０００５】
図１の入力文字列から図２のキーワード辞書中の各キーワードを抽出する場合、
・文２では、誤字によって「オリンピック」が「オソンピック」になっている、
・文３，４では、「男子１００ｍ平泳ぎ」が「男子の１００ｍ平泳ぎ」、「金メダル」が「メダル」と、わずかに異なった表現で記述されている、ため、文２，３，４からはキーワードを抽出できず、結果的に、文１からキーワード「オリンピック」が抽出されるだけとなる。【０００６】
［従来技術］
（１）キーワードの近似照合
従来、キーワードの近似照合方法として、正規表現が使われてきた。正規表現は、照合したいキーワードを、有限オートマトンで表現することにより、文字列中からわずかに異なる部分文字列を抽出することができる。これはプログラミング言語Ｐｅｒｌなどで使われている。例えば、Ｐｅｒｌの場合、「オリンピック」というキーワードを／オ．｛１｝ンピック／と表現することによって、図１の文１から「オリンピック」を、文２から「オソンピック」を抽出することができる。【０００７】
しかし、正規表現によるキーワード近似照合は、１つのキーワード毎に照合を繰り返すことになるため、キーワード数に比例した時間がかかり、キーワードの数が膨大になると照合速度が低下する。そのため、大量の文書から全てのキーワードを抽出するようなタスクでは、処理時間がかかるという問題点がある。【０００８】
なお、正規表現以外に、２つの対象物間の類似度を計算するＤＰ（Dynamic Programming）によるマッチング法（非特許文献１参照）を用いることもできるが、キーワード毎にＤＰマッチングしなければならないため、大量のキーワード数では著しく処理速度が落ちるという問題点がある。【０００９】
（２）高速な完全一致照合：その１．トライ構造
キーワード数が膨大な場合、キーワード辞書をトライ構造（非特許文献２参照）にすることにより、全てのキーワードを同時に照合することができる。トライ構造は、各キーワードの共通接頭辞を併合した木構造である。図２のキーワード辞書をトライ構造にした辞書（トライ辞書）の例を図３に示す。キーワードの各文字は、トライの枝として表現される。図中の「＃」は、キーワードの終わりを表す終端記号で、トライのノードにはキーワード毎に異なる値を保持することができる。【００１０】
トライ辞書を用いたキーワード抽出は、入力文字列を先頭から１文字ずつずらしながらトライ辞書と照合することにより行う。なお、本明細書及び特許請求の範囲では、全ての文字列について、文字列の最初の文字を０文字目、次の文字を１文字目等と表記する。例えば、文字列の位置ｉは、当該文字列の最初の文字を０文字目としたｉ文字目の位置である。また、位置iなどにおけるｉは文字列の位置の値である。更に、"文字列の位置"のみで文字列の位置の値を表す場合もある。【００１１】
トライ構造による照合アルゴリズムを図４に示す。トライ構造による照合においては、図４に示すように、入力文字列の全ての文字位置ｉについて、ステップｓ１〜ステップｓ５の処理が繰り返される。【００１２】
まず、キーワード照合位置ｊを０とし、トライノードｎを根ノードとすることにより初期化が行われる（ステップｓ１）。次に、ノードｎの枝に終端記号＃があるかどうかの判定がなされ（ステップｓ２）、終端記号＃があれば、根ノードからの経路上の全枝ラベル、値、一致開始位置ｉが出力される（ステップｓ３）。【００１３】
ステップｓ２の判定において、ノードｎの枝に終端記号＃がない場合、入力文字列における位置ｉ＋ｊの文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにあるかどうかの判定がなさる（ステップｓ４）。【００１４】
ステップｓ４において、文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにない場合、入力文字列の次の文字位置について、ステップｓ１からの処理を繰り返す。ステップｓ４において、文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにある場合、ｊをｊ＋１とし、ｎを該当枝先のノードに更新してステップｓ２に進む（ステップｓ５）。【００１５】
例えば、図１の文１を図３のトライ辞書と照合する場合、入力文の６文字目（位置ｉ＝６）から照合を開始すると、ノード１，２，３，４，５，６，７を経由して値１に至るので、６文字目からキーワード「オリンピック」が抽出され、その値は値１であることがわかる。【００１６】
トライ辞書を用いると、全キーワードを同時に照合できるため、処理速度はキーワード数には依存しない。そのため、数が膨大でも高速に照合することができる。【００１７】
しかし、トライ辞書を用いたキーワード照合は、キーワードと完全一致した文字列しか抽出できないため、誤字や脱字、少し異なる表現を使われたキーワードが抽出できないという問題点がある。【００１８】
（３）高速な完全一致照合：その２．ＡＣ法
トライ構造を用いたキーワード照合を改良したものに、Ａｈｏ−Ｃｏｒａｓｉｃｋ法（以下、ＡＣ法と呼ぶ。）（非特許文献３参照）がある。ＡＣ法を用いると、照合速度は入力文字列の長さ（文字数）のみに依存するようになるため、さらに高速に照合することができる。【００１９】
ＡＣ法では、図３のようなトライ辞書（ＡＣ法では、ｇｏｔｏ関数と呼ばれる。）の他に、ｆａｉｌｕｒｅ関数、ｏｕｔｐｕｔ関数を用いて高速に照合を行う。ｆａｉｌｕｒｅ関数は、トライの照合が途中で失敗した際、失敗直前までの枝ラベル接尾辞と、トライの根ノードからの枝ラベル列の接頭辞とを比較して、最長一致するノードへ遷移するための関数である。ｏｕｔｐｕｔ関数は、トライの照合が途中まで成功したとき、その枝ラベルの接尾辞がキーワードである場合、全てのキーワードを出力するための関数である。これはトライ構造の場合とは異なり、後方一致した値を全て出力する。キーワード辞書が図２の場合のｆａｉｌｕｒｅ関数、ｏｕｔｐｕｔ関数の例を、それぞれ図５、図６に、ＡＣ法による照合アルゴリズムを図７に示す。【００２０】
図７に示すように、ＡＣ法による照合では、まず、入力文字列照合位置ｅを０とし、トライノードｎを１として初期化を行う（ステップｓ１１）。続いて、入力文字列照合位置ｅが入力文字列長以上であるか否かの判定が行われ（ステップｓ１２）、入力文字列照合位置ｅが入力文字列長以上であれば処理を終える。ステップｓ１２で、力文字列照合位置ｅが入力文字列長以上でない場合、入力文字列の位置ｅの文字と同じラベルがノードｎの枝にあるかどうかの判定がなされる（ステップｓ１３）。【００２１】
ステップｓ１３において、入力文字列の位置ｅの文字と同じラベルがノードｎの枝にない場合、ｎをｆａｉｌｕｒｅ関数の値とし（ステップｓ１４）、そのｎの値が１であれば、ｅをｅ＋１として（ステップｓ１５）、ステップｓ１７に進む。また、ステップｓ１３において、入力文字列の位置ｅの文字と同じラベルがノードｎの枝にある場合、ｎを該当枝先のノードに更新し、ｅをｅ＋１として（ステップｓ１６）、ステップｓ１７に進む。【００２２】
ステップｓ１７では、ｏｕｔｐｕｔ（ｎ）が空集合でなければ、ｏｕｔｐｕｔ（ｎ）中のキーワードと値、及び一致開始位置ｉ＝（ｅ−キーワード長）が出力され、ステップｓ１２に進む。【００２３】
例えば、入力文字列が「金メダリスト誕生」であった場合、まず、ノード１が、０文字目で「金」の枝ラベル先１６に遷移する。ここでは、ｏｕｔｐｕｔ関数の値は定義されていないので、何も出力しない。これを繰り返すと、２文字目でノード１８に至る。３文字目「リ」は、ノード１８から出る枝ラベルにないので、ｆａｉｌｕｒｅ関数を参照し、ノード１２に遷移する（ｆａｉｌｕｒｅ（１８）＝１２）。つまり、入力文字列の１〜２文字目「メダ」が既に照合終了した状態になる。ここから３文字目の照合を再開させると、結果的に入力文字列の１〜５文字目がキーワード「メダリスト」と一致することがわかる。【００２４】
このように、ＡＣ法を用いると、入力文字列の長さに比例した時間しかかからないため、高速にキーワード抽出を行うことができる。【００２５】
しかし、ＡＣ法も、キーワードと完全一致した文字列しか抽出できないため、トライ構造と同様に誤字や脱字、少し異なる表現を使われたキーワードが抽出できないという問題点がある。
【先行技術文献】
【非特許文献】
【００２６】
【非特許文献１】田中穂積  監修、「自然言語処理−基礎と応用−」、初版、社団法人電子情報通信学会、平成１１年３月２５日、ｐ．１２〜１５
【非特許文献２】松本裕治、影山太郎、永田昌明、齋藤洋典、徳永健伸、「岩波講座言語の科学  ３  単語と辞書」、岩波書店、１９９７、ｐ．７４〜７５
【非特許文献３】北研二、津田和彦、獅々堀正幹、「情報検索アルゴリズム」、共立出版、２００２、ｐ．１０８〜１２２
【発明の概要】
【発明が解決しようとする課題】
【００２７】
本発明は、誤字や脱字、想定したキーワードと少し異なる表現が入力文字列に含まれ、また、抽出したいキーワード数が多い場合であっても、高速に抽出可能とすることを目的とする。
【課題を解決するための手段】
【００２８】
上記問題点を解決するため、本発明を用いた技術では、以下の方法でＮ字連続（Ｎは任意の整数）までの挿入、削除、置換誤りを含む文字列と、大量のキーワードとを高速に照合する。【００２９】
１．キーワード辞書からトライ辞書を構築する際、各キーワード毎に、キーワードそのものと、当該キーワードの全ての文字位置ｐｋから連続するｗｋ字（１≦ｗｋ≦Ｎ）を削除した文字列の集合とからなる削除キーワードを生成し、トライ構造を作成する。これをスキップ辞書と呼ぶ。【００３０】
２．スキップ辞書の値には、各削除キーワード毎に、削除文字位置ｐｋ、削除文字数ｗｋ及び当該削除キーワードの元となったキーワード（元キーワード）を保持しておく。【００３１】
３．入力文字列とスキップ辞書とを照合する際、入力文字列そのものとスキップ辞書との照合だけでなく、当該入力文字列の全ての位置から連続するｗｉ字（１≦ｗｉ≦Ｎ）スキップした入力文字列（以下、スキップ入力と呼ぶ。）の集合とスキップ辞書との照合も行う。なお、スキップ入力は陽に作成しても良いし、照合時に直接、入力文字列をスキップしながら照合しても良い。【００３２】
４．得られた削除キーワードの削除文字位置ｐｋ、削除文字数ｗｋ、入力文字列のキーワード上での相対スキップ位置ｐｉ、スキップ幅ｗｉを比較してその削除キーワードを、
・ｗｉ，ｗｋがともに０（ｗｉ＝ｗｋ＝０）ならば、キーワードは完全一致としてキーワードを出力する、
・ｗｉが０で、ｗｋが１以上（ｗｉ＝０，ｗｋ＞０）であれば、入力文字列のスキップ位置にｗｉ字の削除文字が存在するものとしてキーワードを出力する、
・ｗｉが１以上で、ｗｋが０（ｗｉ＞０，ｗｋ＝０）であれば、入力文字列のスキップ位置にｗｉ字の挿入文字が存在するものとしてキーワードを出力する、
・ｗｉが１以上で、ｐｉとｐｋが等しく、ｗｉとｗｋ（ｗｉ＞０，ｐｉ＝ｐｋ，ｗｉ＝ｗｋ）が等しければ、入力文字列のスキップ位置にｗｉ＝ｗｋ字の置換文字が存在するものとしてキーワードを出力する、
の４種類に分類する。【００３３】
５．スキップ辞書にｆａｉｌｕｒｅ関数、ｏｕｔｐｕｔ関数を定義し、照合をＡＣ法で行うことにより、さらに高速に照合を行うこともできる。
【発明の効果】
【００３４】
本発明を用いた技術によれば、
・挿入、削除、置換誤りが含まれた入力文字列からも、連続したＮ文字以内の誤りであればキーワードを抽出することができ、
・トライ構造を用いて全キーワードを同時に照合しているため、キーワード数が増えても処理時間がほとんど増加せず、
・照合方式にＡＣ法を用いることにより、さらに高速に照合することもできる。【００３５】
また、本発明で出力するキーワードは、さらに文字の誤りやすさによってスコア付けすることもできる。従って、入力文字列の同じエリアに別のキーワード侯補があった場合、誤り文字を比較して、誤りにくい方だけを出力することもできる。【００３６】
また、本発明によれば、入力文字列に含まれるキーワード辞書に載ったキーワード（単語）を全て出力するため、単語同士のつながりやすさをｎ−ｇｒａｍモデル等でスコア付けすることにより、形態素解析器を作ることができる。
【図面の簡単な説明】
【００３７】
【図１】入力文字列の一例を示す説明図
【図２】キーワード辞書の一例を示す説明図
【図３】トライ辞書の一例を示す説明図
【図４】トライ構造による照合アルゴリズムを示す処理の流れ図
【図５】ｆａｉｌｕｒｅ関数の一例を示す説明図
【図６】ｏｕｔｐｕｔ関数の一例を示す説明図
【図７】ＡＣ法による照合アルゴリズムを示す処理の流れ図
【図８】本発明の近似照合装置の実施の形態の一例を示す構成図
【図９】削除キーワードとその値の一例を示す説明図
【図１０】スキップ入力／スキップ辞書照合アルゴリズムを示す処理の流れ図
【図１１】抽出されたキーワード候補の一例を示す説明図
【図１２】スキップ入力の一例を示す説明図
【図１３】抽出されたキーワード候補の他の例を示す説明図
【図１４】トライ構造による入力文字列照合アルゴリズムを示す処理の流れ図
【図１５】トライ構造によるスキップ入力照合アルゴリズムを示す処理の流れ図
【図１６】ＡＣ法による入力文字列照合アルゴリズムを示す処理の流れ図
【図１７】ＡＣ法によるスキップ入力照合アルゴリズムを示す処理の流れ図
【図１８】重複削除アルゴリズムを示す処理の流れ図
【図１９】重複削除後の抽出されたキーワードの一例を示す説明図
【図２０】重複削除後の抽出されたキーワードの他の例を示す説明図
【図２１】本発明の実施の形態に係るＷｅｂ情報フィルタリング装置の構成図
【図２２】本発明の実施の形態に係る自動校正装置の構成図
【図２３】本発明の実施の形態に係る自動校正装置が出力する画面例
【図２４】中国語の入力文字列の一例を示す説明図
【図２５】中国語のキーワード辞書の一例を示す説明図
【図２６】中国語の削除キーワードとその値の一例を示す説明図
【図２７】中国語の抽出されたキーワード候補の一例を示す説明図
【図２８】中国語のスキップ入力の一例を示す説明図
【図２９】中国語の抽出されたキーワード候補の他の例を示す説明図
【図３０】重複削除後の中国語の抽出されたキーワードの一例を示す説明図
【図３１】韓国語の入力文字列の一例を示す説明図
【図３２】韓国語のキーワード辞書の一例を示す説明図
【図３３】韓国語の削除キーワードとその値の一例を示す説明図
【図３４】韓国語の抽出されたキーワード候補の一例を示す説明図
【図３５】韓国語のスキップ入力の一例を示す説明図
【図３６】韓国語の抽出されたキーワード候補の他の例を示す説明図
【図３７】重複削除後の韓国語の抽出されたキーワードの一例を示す説明図
【発明を実施するための形態】
【００３８】
図８は本発明の近似照合装置の実施の形態の一例を示すもので、スキップ辞書作成部１０、スキップ辞書記憶部２０及びキーワード抽出部３０から構成される。なお、本明細書では、キーワードの最大削除文字数と入力文字列の最大スキップ幅は等しく、Ｎと表記する。
【００３９】
また、近似照合装置は、ＣＰＵや、メモリ等の記憶手段を備えたコンピュータに、スキップ辞書作成部１０、及びキーワード抽出部３０の機能を実現するためのプログラムを搭載することにより実現可能である。また、スキップ辞書を別の装置等で作成し、それをスキップ辞書記憶部２０に記憶することとすれば、コンピュータにキーワード抽出部３０の機能を実現するためのプログラムを搭載することによりキーワード抽出手段を備えた近似照合装置を実現できる。また、当該プログラムは、可搬メモリ等の記憶媒体に格納しておき、そこからコンピュータにインストールすることが可能である。
【００４０】
スキップ辞書作成部１０は、予め与えられたキーワードに対して、キーワード毎に、キーワードそのものと、当該キーワードの全ての文字位置から連続する少なくとも１つの文字を削除した文字列の集合とからなる削除キーワードを含むスキップ辞書を作成する。
【００４１】
スキップ辞書記憶部２０は、スキップ辞書作成部１０で作成されたスキップ辞書を記憶・保持する。
【００４２】
キーワード抽出部３０は、入力文字列とスキップ辞書記憶部２０に保持されたスキップ辞書とを照合することにより、入力文字列から予め与えられたキーワード及び当該キーワードに近似したキーワードを抽出し、その出現位置とともに出力する。
【００４３】
以下、前述した各部における処理の詳細について例を挙げて説明する。
【００４４】
≪スキップ辞書作成部≫
スキップ辞書作成部１０は、削除キーワード／値生成部１１、削除キーワード／値一時記憶部１２及びトライ辞書作成部１３からなり、抽出したいキーワードとして予め人手によりリストアップされたキーワードの集合であるキーワード辞書からスキップ辞書を作成し、スキップ辞書記憶部２０に格納する。
【００４５】
＜削除キーワード／値生成部＞
削除キーワード／値生成部１１では、予め用意されたキーワード辞書中の各キーワードに対して、まず、キーワードそのものと、当該キーワードの全ての文字位置ｐｋから連続するｗｋ字（１≦ｗｋ≦Ｎ：Ｎはキーワードの削除最大文字数）を削除した文字列の集合とからなる削除キーワードを作成し、削除キーワード／値一時記憶部１２に記憶する。
【００４６】
その際、削除文字位置ｐｋ、削除文字数ｗｋ及び当該削除キーワードの元となったキーワードである元キーワードの組を値として生成し、その削除キーワードに対応させて削除キーワード／値一時記憶部１２に記憶する。削除キーワードが元キーワードそのものである場合、ｗｋは０である。ｐｋは何を代入しても良いが、ここでは空欄とする。例えば、最大削除文字数Ｎ＝２の場合、「オリンピック」というキーワードからは、図９に示す１２個の削除キーワードとその値が生成される。
【００４７】
もちろん、これは全てのキーワードに対して行わなくても良く、ある一定の長さ以上（例えば、４文字以上）の長さのキーワードに対してのみ、削除キーワードを作成しても良い。
【００４８】
＜トライ辞書作成＞
トライ辞書作成１３では、削除キーワード／値一時記憶部１２から削除キーワード／値生成部１１が生成した削除キーワードと当該削除キーワードに対応する値を読み出し、トライ構造に変換して辞書を作成する。
【００４９】
すなわち、トライ辞書作成１３は、削除キーワード／値一時記憶部１２から削除キーワード／値生成部１１が生成した削除キーワードと当該削除キーワードに対応する値を読み出し、キーワードの各文字を枝とし、キーワード毎に異なる値を保持可能なノードを含む、キーワードの共通接頭辞を併合した木構造であるトライ構造に変換してスキップ辞書を作成する。
【００５０】
後述するスキップ入力／スキップ辞書照合部でＡＣ法を用いる場合、さらにｆａｉｌｕｒｅ関数、ｏｕｔｐｕｔ関数を定義する。これを全てのキーワードについて行い、スキップ辞書としてスキップ辞書記憶部２０に格納する。
【００５１】
≪キーワード抽出部≫
キーワード抽出部３０は、スキップ入力／スキップ辞書照合部３１、照合結果一時記憶部３２及び重複削除部３３からなり、誤字や脱字を含む入力文字列とスキップ辞書記憶部２０に格納されたスキップ辞書とからキーワードを抽出し、その出現位置及び値とともに出力する。
【００５２】
＜スキップ入力／スキップ辞書照合部＞
まず、スキップ入力／スキップ辞書照合部３１では、入力文字列とスキップ辞書記憶部２０に格納されたスキップ辞書とを照合して、キーワードの侯補を抽出する。スキップ入力／スキップ辞書照合のアルゴリズムを図１０に示す。なお、ここで抽出したキーワードは、
・ＥＭ：キーワードが入力文字列中に完全一致で出現
・ＤＥＬ：入力文字列に削除文字（脱字）が存在する状態でキーワードと一致
・ＩＮＳ：入力文字列に挿入文字が存在する状態でキーワードと一致
・ＲＥＰ：入力文字列に置換文字（誤字）が存在する状態でキーワードと一致
の４つの一致タイプに分類される。
【００５３】
（１）入力文字列とスキップ辞書の照合
まず、入力文字列とスキップ辞書を照合する（ステップｓ２１）。この照合アルゴリズムは、図４に示した通常のトライ辞書照合、図７に示したＡＣ法による照合のどちらを用いても良い。また、これら以外の照合アルゴリズムを用いることもできる。
【００５４】
次に、スキップ辞書と一致した全てのキーワード侯補について、以下のステップｓ２２とステップｓ２３の処理を繰り返す。
【００５５】
削除キーワードの削除文字数ｗｋが０ならば、一致タイプをＥＭとして、当該一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数、元キーワードを出力して照合結果一時記憶部３２に記憶する（ステップｓ２２）。
【００５６】
削除キーワードの削除文字数ｗｋが０より大きければ、一致タイプをＤＥＬとして、当該一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数、元キーワードを出力して照合結果一時記憶部３２に記憶する（ステップｓ２３）。
【００５７】
上記のステップｓ２２、ｓ２３において、一致タイプがＥＭであれば、誤り開始位置、誤り文字数はどちらも常に０となり、一致タイプがＤＥＬであれば、誤り開始位置、誤り文字数は、それぞれ削除キーワードの削除文字位置ｐｋ、削除文字数ｗｋである。
【００５８】
例えば、図１の文１と、図２から作成したスキップ辞書とを照合すると、図１１に示すキーワード侯補が得られる。
【００５９】
（２）スキップ入力とスキップ辞書の照合
ここでは、まず、入力文字列の全ての位置から少なくとも１つの文字をスキップ、詳細には絶対スキップ位置ｐを一つずつ増加させながらスキップ幅ｗｉ字（１≦ｗｉ≦Ｎ）をスキップさせた文字列を作成する（ステップｓ２４）。これをスキップ入力と呼ぶ。例えば、図１の文１についてスキップ入力を作成すると、図１２に示す文字列が得られる。
【００６０】
次に各スキップ入力とスキップ辞書とを照合する（ステップｓ２５）。照合アルゴリズムは、図４または図７のどちらを用いても良い。また、これら以外の照合アルゴリズムを用いることもできる。なお、スキップ入力を作成せず、スキップ辞書との照合時に、入力文字列を直接スキップしながら照合することも可能である。
【００６１】
続いて、スキップ辞書と一致した全てのキーワード侯補について、ステップｓ２６〜ｓ２９の処理を繰り返す。
【００６２】
まず、ステップｓ２６において、キーワードの一致開始位置ｉと絶対スキップ位置ｐから、キーワード上での相対スキップ位置ｐｉ＝ｐ−ｉを算出する。
【００６３】
そして、ｐｉ≧０かつｐｉ≦削除キーワードの文字列長であるか否かが判定され（ステップｓ２７）、ｐｉ≧０かつｐｉ≦削除キーワードの文字列長であればステップｓ２８に進み、ｐｉ≧０かつｐｉ≦削除キーワードの文字列長でなければ次のキーワード候補の処理を行う。
【００６４】
ｐｉ≧０かつｐｉ≦削除キーワードの文字列長である場合において、もし、削除キーワードの削除文字数ｗｋが０ならば、一致タイプをＩＮＳとして、当該一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数、元キーワードを出力して照合結果一時記憶部３２に記憶する（ステップｓ２８）。
【００６５】
もし、削除キーワードの削除文字数ｗｋが０より大きく、かつ入力文字列の相対スキップ位置ｐｉと削除キーワードの削除文字位置ｐｋが等しく、かつ入力文字列のスキップ幅ｗｉと、削除キーワードの削除文字数ｗｋが等しければ、一致タイプをＲＥＰとし、当該一致タイプ、入力文字列における一致開始位置、終了位置、誤り開始位置、誤り文字数、元キーワードを出力して照合結果一時記憶部３２に記憶する（ステップｓ２９）。
【００６６】
ステップｓ２８、ｓ２９において、誤り開始位置、誤り文字数は、それぞれスキップ入力の相対スキップ位置ｐｉ、スキップ幅ｗｉとなる。
【００６７】
ステップｓ２４から、ステップｓ２６〜ｓ２９の繰り返し処理までの処理が入力文字列の絶対スキップ位置ｐ＝０から（文字列長−ｗｉ）まで繰り返され、当該繰り返しの処理が、入力文字列のスキップ幅ｗｉ＝１からＮまで繰り返される。
【００６８】
例えば、図１２のスキップ入力と、図２のキーワード辞書から作成したスキップ辞書を照合すると、図１３に示すキーワード侯補が得られる。なお、一致タイプＲＥＰが１１個出現しているのは、元キーワードと同一の文字への置換が、各文字位置で出現したと解釈しているからである。
【００６９】
（３）トライ構造によるスキップ辞書照合の高速化
図１０では入力文字列、スキップ入力の２箇所（ステップｓ２１，ステップｓ２５）でスキップ辞書との照合を行っていた。通常のトライ構造を用いる場合、上記２箇所の照合アルゴリズムを図４から、それぞれ図１４，図１５に示すようなアルゴリズムに変更することにより、さらに高速にスキップ辞書との照合を行うことができる。
【００７０】
まず、入力文字列とスキップ辞書との照合（図１４）では、入力文字列の全ての文字位置（照合開始位置）ｉにおいて、入力文字列とスキップ辞書をトライ法で照合し、照合に成功したキーワード等を出力する（ステップｓ３１〜ステップｓ３５）とともに、照合に失敗した文字位置ｊをｉと組にして保存しておく（ステップｓ３６）。
【００７１】
つまり、図１４に示すように、入力文字列の全ての文字位置ｉについて、ステップｓ３１〜ステップｓ３６の処理が繰り返される。
【００７２】
まず、キーワード照合位置ｊを０とし、トライノードｎを根ノードとすることにより初期化が行われる（ステップｓ３１）。次に、ノードｎの枝に終端記号＃があるかどうかの判定がなされ（ステップｓ３２）、終端記号＃があれば、根ノードからの経路上の全枝ラベル、値、一致開始位置ｉが出力される（ステップｓ３３）。
【００７３】
ステップｓ３２の判定において、ノードｎの枝に終端記号＃がない場合、入力文字列における位置ｉ＋ｊの文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにあるかどうかの判定がなさる（ステップｓ３４）。
【００７４】
ステップｓ３４において、文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにない場合、文字位置ｉと、キーワード照合失敗位置ｊを対で保存し（ステップｓ３６）、入力文字列の次の文字位置について、ステップｓ３１からの処理を繰り返す。ステップｓ３４において、文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにある場合、ｊをｊ＋１とし、ｎを該当枝先のノードに更新してステップｓ２に進む（ステップｓ３５）。
【００７５】
ステップｓ３６の処理により、照合開始位置（一致開始位置）ｉ毎に、ｊ−１文字まで照合が成功したことが示される。
【００７６】
スキップ入力とスキップ辞書との照合（図１５）では、入力文字列の全ての文字位置（照合開始位置）ｉにおいて、スキップ入力とスキップ辞書をトライ法で照合する（ステップｓ４３〜ステップｓ４７）が、その際、位置ｉに対応する保存済みのキーワード照合失敗位置ｆを取得（正確には、ステップｓ３６で保存したｊをｆとして取得）する（ステップｓ４１）。
【００７７】
ここで、スキップ入力の絶対スキップ位置ｐがｐ＜ｉならば、もしキーワードが一致したとしても、入力文字列との照合で一致済みである。また、ｐ＞ｉ＋ｆならば、スキップ位置に至る前に照合が失敗することが明らかである。従って、ｐ＜ｉまたはｐ＞ｉ＋ｆであるかどうかの判定を行い（ステップｓ４２）、ｐ＜ｉまたはｐ＞ｉ＋ｆであれば何もせずに次の文字位置ｉ＋１に処理を移す。
【００７８】
ｐ＜ｉまたはｐ＞ｉ＋ｆでなければ、図４に示した処理と同様にして、まず、キーワード照合位置ｊを０とし、トライノードｎを根ノードとすることにより初期化が行われる（ステップｓ４３）。次に、ノードｎの枝に終端記号＃があるかどうかの判定がなされ（ステップｓ４４）、終端記号＃があれば、根ノードからの経路上の全枝ラベル、値、一致開始位置ｉが出力される（ステップｓ４５）。
【００７９】
ステップｓ４４の判定において、ノードｎの枝に終端記号＃がない場合、入力文字列における位置ｉ＋ｊの文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにあるかどうかの判定がなさる（ステップｓ４６）。
【００８０】
ステップｓ４６において、文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにない場合、入力文字列の次の文字位置について、ステップｓ４１からの処理を繰り返す。ステップｓ４６において、文字Ｃｉ＋ｊがトライノードｎから分岐する枝ラベルにある場合、ｊをｊ＋１とし、ｎを該当枝先のノードに更新してステップｓ４４に進む（ステップｓ４７）。
【００８１】
このように、トライ構造との照合アルゴリズムを変更することにより、スキップ入力の照合範囲を限定することができ、さらに高速な照合を行うことができる。
【００８２】
（４）ＡＣ法によるスキップ辞書照合の高速化
図１０では入力文字列、スキップ入力の２箇所（ステップｓ２１，ステップｓ２５）でスキップ辞書との照合を行っていた。ＡＣ法を用いる場合、上記２箇所の照合アルゴリズムを図７から、それぞれ図１６，図１７に示すようなアルゴリズムに変更することにより、さらに高速にスキップ辞書との照合を行うことができる。
【００８３】
まず、入力文字列とスキップ辞書との照合（図１６）では、入力文字列とスキップ辞書をＡＣ法で照合し、照合に成功したキーワード等を出力する（ステップｓ５１，ステップｓ５２，ステップｓ５４〜ｓ５８）とともに、入力文字列の各文字位置（照合位置）ｅにおける最初のトライノード番号ｎを保存しておく（ステップｓ５３）。これをトライノード関数ｎ＝ｔｒｉｅｎｏｄｅ（ｅ）と呼ぶ。トライノード関数は、入力文字列にスキップがない場合、入力文字列上で照合済みの文字位置とトライ上での状態を対応づける関数である。
【００８４】
より詳細には、図１６においてまず、入力文字列照合位置ｅを０とし、トライノードｎを１として初期化を行う（ステップｓ５１）。続いて、入力文字列照合位置ｅが入力文字列長以上であるか否かの判定が行われ（ステップｓ５２）、入力文字列照合位置ｅが入力文字列長以上であれば処理を終える。ステップｓ５２で、入力文字列照合位置ｅが入力文字列長以上でない場合、ｔｒｉｅｎｏｄｅ（ｅ）が保存されていなければ、ｔｒｉｅｎｏｄｅ（ｅ）にｎの値を代入し、入力文字列照合位置ｅとノードｎを記憶部に保存する（ステップｓ５３）。そして、入力文字列の位置ｅの文字と同じラベルがノードｎの枝にあるかどうかの判定がなされる（ステップｓ５４）。
【００８５】
ステップｓ５４において、入力文字列の位置ｅの文字と同じラベルがノードｎの枝にない場合、ｎをｆａｉｌｕｒｅ関数の値とし（ステップｓ５５）、そのｎの値が１であれば、ｅをｅ＋１として（ステップｓ５６）、ステップｓ５８に進む。また、ステップｓ５４において、入力文字列の位置ｅの文字と同じラベルがノードｎの枝にある場合、ｎを該当枝先のノードに更新し、ｅをｅ＋１として（ステップｓ５７）、ステップｓ５８に進む。
【００８６】
ステップｓ５８では、ｏｕｔｐｕｔ（ｎ）が空集合でなければ、ｏｕｔｐｕｔ（ｎ）中のキーワードと値、及び一致開始位置ｉ＝（ｅ−削除キーワード長）が出力され、ステップｓ５２に進む。
【００８７】
スキップ入力とスキップ辞書との照合（図１７）では、入力文字列の絶対スキップ位置ｐからＡＣ法による照合を開始する。即ち、初期状態をスキップ入力の照合位置ｅ＝ｐ、トライノードｎ＝ｔｒｉｅｎｏｄｅ（ｅ）として照合を再開する（ステップｓ６１〜ｓ６６）。
【００８８】
照合はスキップ入力の最後まで行うのではなく、ｆａｉｌｕｒｅ関数によって遷移するトライノードが根ノード（ｎ＝１）に遷移した時点で照合を終了する（ステップｓ６４）。これ以降は入力にスキップが存在しないため、入力文字列との照合で得られたキーワードと同一のものしか一致しないからである。
【００８９】
より詳細には、まず、スキップ入力の照合位置ｅ＝ｐ、トライノードｎ＝ｔｒｉｅｎｏｄｅ（ｅ）とし（ステップｓ６１）、スキップ入力の位置ｅの文字と同じラベルがノードｎの枝にあるかどうかの判定がなされる（ステップｓ６２）。
【００９０】
スキップ入力の位置ｅの文字と同じラベルがノードｎの枝にない場合、ｎをｆａｉｌｕｒｅ関数の値とし（ステップｓ６３）、そのｎの値が１であれば（ステップｓ６４のＹＥＳ）、処理を終了し、そのｎの値が１でなければ（ステップｓ６４のＮＯ）、ステップｓ６６に進む。
【００９１】
ステップｓ６２において、スキップ入力の位置ｅの文字と同じラベルがノードｎの枝にある場合、ｎを該当枝先のノードに更新し、ｅをｅ＋１として（ステップｓ６５）、ステップｓ６６に進む。
【００９２】
ステップｓ６６では、ｏｕｔｐｕｔ（ｎ）が空集合でなければ、ｏｕｔｐｕｔ（ｎ）中のキーワードと値、及び一致開始位置ｉ＝（ｅ−キーワード長）が出力され、ステップｓ６２に進む。
【００９３】
このようにＡＣ法による照合アルゴリズムを変更することにより、スキップ入力の照合範囲を限定することができ、さらに高速な照合を行うことができる。
【００９４】
＜重複削除部＞
重複削除部３３では、照合結果一時記憶部３２からスキップ入力／スキップ辞書照合部３１が出力したキーワード侯補の集合を読み出し、重複するものを削除したキーワードの集合を生成して出力する。ここでは、誤り文字数が最小のものだけを選択し、残りのもののうち、入力文字列上で一致したエリアが重なるものは重複と解釈する。重複削除アルゴリズムを図１８に示す。
【００９５】
１．まず、キーワード侯補集合Ｃに、照合結果一時記憶部３２から読み出したキーワード侯補の集合（スキップ入力／スキップトライ照合の出力）をセットし、最終的に出力するキーワード集合Ｋを空集合（Φ）とする（ステップｓ７１）。
【００９６】
２．次に、キーワード侯補集合Ｃから侯補を一つ（ｃとする）を取り出す（ステップｓ７４）。この候補ｃと元キーワードが一致するものを、キーワード侯補集合Ｃから全て取り出す（ステップｓ７５）。これをＣｋｅｙｓとする。
【００９７】
３．次に、Ｃｋｅｙｓから、誤り文字数が最小の侯補を全て取り出し（Ｃｍｉｎｓとする）、Ｃｍｉｎｓをキーワード集合Ｋに加える（ステップｓ７６）。
【００９８】
４．最後に、Ｃｋｅｙｓの全てのキーワード侯補について、Ｃｍｉｎｓ中の全てのキーワードの一致開始位置、終了位置と比較して、エリアが重なるものをキーワード侯補集合Ｃから削除する（ステップｓ７７）。
【００９９】
５．ステップｓ７２〜ｓ７４を、キーワード侯補集合Ｃが空集合になるまで繰り返す（ステップｓ７２）。
【０１００】
６．Ｋを、最終的なキーワード集合として出力する（ステップｓ７３）。
【０１０１】
このように重複を削除することにより、例えば、図１の文１と、図２のキーワード辞書から作成したスキップ辞書から、図１９に示すキーワードだけが残ることになる。つまり、入力文字列の６文字目から、「オリンピック」というキーワードが完全一致で出現したという意味になる。
【０１０２】
同様に、図１の文２〜４と、図２のキーワード辞書から作成したスキップ辞書を用いると、図２０に示すキーワードが得られる。
【０１０３】
本発明の実施の形態に係る近似照合装置により得られる一致タイプ・開始位置・終了位置・元キーワードの情報からは、各入力文中の、何文字目から何文字目が辞書のキーワードと一致したのか、その一致タイプが完全一致・置換・削除・挿入のいずれかであったのかがわかる。また、誤り開始位置・誤り文字数の情報からは、一致タイプが置換・挿入・削除の場合に、照合文字範囲で何文字目から何文字が誤りであったのかがわかる。
【０１０４】
本発明の実施の形態に係る近似照合装置によれば、例えば、図２０に示すように、文２では、「オソンピック」という誤字を含む文字列も「オリンピック」の１文字置換タイプとして検出できる。また、文３では、入力文の「男子の１００ｍ平泳ぎ」という範囲が辞書キーワード「男子１００ｍ平泳ぎ」と一字挿入のタイプとして検出できる。
【０１０５】
これにより、「オリンピック」や「男子１００ｍ平泳ぎ」に関する情報を検索する場面において、「オソンピック」や「男子の１００ｍ平泳ぎ」という誤字脱字・表記ゆれを含むテキストでも検索対象となり、その出現範囲とともにユーザーに提示可能となる。すなわち、本発明に係る近似照合装置は、誤字脱字や表記ゆれにも頑健な情報検索装置として利用できる。
【０１０６】
また、例えば、本発明に係る技術を、不適切な用語を含むＷｅｂページを表示させないようにするＷｅｂ情報フィルタリング装置に利用することもできる。不適切用語のフィルタリングでは、不適切表現を含むテキストの検出が必要であるが、そのようなテキストは故意に元の表記から一部の文字を変更した不適切表現として記載されることが往々にしてある。
【０１０７】
本発明に係る技術では、元のキーワードからＮ文字連続の変更が加えられた文字列でも検出することが可能であり、従来の不適切用語検出より幅広いテキストの出現に対処できる。
【０１０８】
図２１に本発明の実施の形態に係るＷｅｂ情報フィルタリング装置の構成例を示す。
【０１０９】
図２１に示すように、このＷｅｂ情報フィルタリング装置は、スキップ辞書作成部１０、スキップ辞書記憶部２０、キーワード抽出部３０、フィルタリング部４０、表示部（ディスプレイ）５０を備える。
【０１１０】
スキップ辞書作成部１０、スキップ辞書記憶部２０、キーワード抽出部３０は、これまでに説明した図８に示したものと同様の機能を有する。ただし、本例において、キーワード抽出部３０は、例えば通信ネットワークを介して、Ｗｅｂページに含まれるテキストデータを入力文字列として入力する機能を更に有している。
【０１１１】
図２１の構成において、フィルタをかけたい不適切用語のリストをキーワード辞書としてスキップ辞書作成部１０に与え、スキップ辞書作成部１０によりスキップ辞書が作成され、スキップ辞書記憶部２０に記憶される。
【０１１２】
そして、キーワード抽出部３０が、入力文字列に対してこれまでに説明したキーワード照合処理を行う。これにより、不適切用語の一部の文字が変更されたような文字列も削除キーワードとして抽出される。キーワード抽出部３０は、削除キーワード等の情報をＷｅｂページの情報とともにフィルタリング部４０に出力する。
【０１１３】
フィルタリング部４０はキーワード抽出部３０から受け取った情報に基づき、削除キーワードを含むＷｅｂページの情報を表示部（ディスプレイ）５０に渡さないように制御する。削除キーワードを含まないＷｅｂページについては、フィルタリング部４０は、そのまま表示部５０に出力し、表示部５０がＷｅｂページを表示する。
【０１１４】
また、例えば、本発明に係る技術をテキストデータの自動校正装置に適用することも可能である。
【０１１５】
図２２に本発明の実施の形態に係る自動校正装置の構成例を示す。図２２に示すように、この自動校正装置は、スキップ辞書作成部１０、スキップ辞書記憶部２０、キーワード抽出部３０、入力部（キーボード）６０、表示制御部７０、表示部５０を備える。
【０１１６】
スキップ辞書作成部１０、スキップ辞書記憶部２０、キーワード抽出部３０は、これまでに説明した図８に示したものと同様の機能を有する。ただし、本例においては、ユーザーが文字入力を行うための入力部６０が備えられ、キーワード抽出部３０は、ユーザーが入力部６０から入力する文字列を入力文字列として受け取る機能を更に備えている。
【０１１７】
図２２の構成において、一般的な辞書に掲載されている単語をキーワード辞書としてスキップ辞書作成部１０に与え、スキップ辞書作成部１０によりスキップ辞書が作成され、スキップ辞書記憶部２０に記憶される。そして、キーワード抽出部３０が、入力文字列に対してこれまでに説明したキーワード照合処理を行い、キーワード照合処理の結果により得られた削除キーワード等の情報と、入力文字列とを表示制御部７０に出力する。
【０１１８】
表示制御部７０は、キーワード抽出部３０で抽出された削除キーワードをハイライトして辞書キーワードとともに、表示を行うよう表示部５０を制御する。削除キーワードの部分をハイライトして辞書キーワードとともにユーザに提示することで、自動検出した誤り候補として当該部分の修正をユーザに促すことが可能となる。表示のイメージを図２３に示す。図２３に示す例では、削除キーワードに係る入力文字列での出現形の部分全体に対してハイライトを行っている。
【０１１９】
ここで、出現形全体をハイライトさせる代わりに、キーワード抽出部３０で抽出した誤りの出現位置を利用して、誤り文字範囲だけをハイライトしてもよい。また、一致タイプの情報を利用して、例えば、文２の照合範囲「オソンピック」の部分と誤り文字の範囲「ソ」の部分とを指摘する情報と、辞書キーワード「オリンピック」の１字置換であるという情報とを提示し、修正要否の最終判断をユーザーに促すこととしてもよい。
【０１２０】
以上の例は、いずれの場合も、誤字脱字や表記ゆれといった文字列を辞書検索の一致対象に含めることができる本技術の特性を活かした適用例であり、他にも誤字脱字を含んだテキストの単語分割を行う形態素解析など、様々な言語処理技術への適用を行うことができる。
【０１２１】
誤字脱字や表記ゆれといった現象は、人間が入力したテキストであれば必ず発生する可能性がある。本発明に係る技術により、これらの現象も含めて言語処理をターゲットとでき、より頑健で柔軟な言語処理アプリケーションを実現できる。
【実施例】
【０１２２】
（中国語における例）
本発明は、日本語のみでなく、他の言語についても同様に適用することができる。例えば、中国語の例として、図２４に示す入力文字列から、図２５に示すキーワードを抽出することを考える。【０１２３】
従来の完全一致によるキーワード抽出法では、文１からはキーワード「【０１２４】
【化１】
2010026804.tif 000003
」が抽出されるが、
●文２では、「【０１２５】
【化２】
2010026804.tif 000004
」が「【０１２６】
【化３】
2010026804.tif 000005
」と表記され、また、「男子１００米蛙泳」が「男子的１００米蛙泳」と、わずかに異なった表現で記述されている、
●文３では、「金牌得主」が「金靴得主」と記述されている、
ため、文２，３からはキーワードが抽出できない。【０１２７】
本発明に係る技術を用いると、キーワードが大量にあった場合でも、以下に説明するとおり、文２，３からもキーワードを抽出することが可能である。なお、以下の説明では、最大削除文字数Ｎ＝１として説明する。【０１２８】
《スキップ辞書作成部》
スキップ辞書作成部１０では、まず、削除キーワードとその値を生成する。例えば、最大削除文字数Ｎ＝１の場合、「【０１２９】
【化４】
2010026804.tif 000006
」というキーワードからは、図２６に示す４つの削除キーワードとその値が生成される。【０１３０】
次に、生成した削除キーワードとその値をトライ構造に変換して、スキップ辞書を作成する。スキップ入力／スキップ辞書照合でＡＣ法を用いる場合、さらにｆａｉｌｕｒｅ関数、ｏｕｔｐｕｔ関数を定義する。【０１３１】
《キーワード抽出部》
〈スキップ入力／スキップ辞書照合部〉
（１）入力文字列とスキップ辞書の照合
まず、入力文字列そのものとスキップ辞書を照合する。照合アルゴリズムは、図４、図７、図１４、図１６のいずれかを用いる。すると、図２４の各文からは、図２７に示すキーワード候補が得られる。【０１３２】
（２）スキップ入力とスキップ辞書の照合
入力文字列からスキップ入力を作成する。Ｎ＝１において、図２４の文１から作成したスキップ入力を図２８に示す。【０１３３】
次に、各スキップ入力をスキップ辞書と照合する。照合アルゴリズムは、「（１）入力文字列とスキップ辞書の照合」で用いた照合アルゴリズムにより、図４、図７、図１５、図１７のいずれかを用いる。【０１３４】
●（１）で図４を用いた場合は同じく図４のアルゴリズムを使用する。【０１３５】
●（１）で図７を用いた場合は同じく図７のアルゴリズムを使用する。【０１３６】
●（１）で図１４を用いた場合は図１５のアルゴリズムを使用する。【０１３７】
●（１）で図１６を用いた場合は図１７のアルゴリズムを使用する。【０１３８】
得られた全てのキーワード侯補について、一致タイプを分類すると、図２４の各文からは、図２９に示すキーワード侯補が得られる。【０１３９】
〈重複削除部〉
最後に、キーワード侯補集合から、図１８に示すアルゴリズムで重複を削除する。結果、各文からは、図３０に示すキーワードが得られる。【０１４０】
（韓国語における例）
次に、本発明を日本語以外の言語に適用する別の例として、韓国語の例を説明する。ここでは、図３１に示す入力文字列から、図３２に示すキーワードを抽出することを考える。【０１４１】
従来の完全一致によるキーワード抽出法では、文１からはキーワード「【０１４２】
【化５】
2010026804.tif 000007
」が抽出されるが、
●文２では、「【０１４３】
【化６】
2010026804.tif 000008
」が「【０１４４】
【化７】
2010026804.tif 000009
」と表記され、また、「【０１４５】
【化８】
2010026804.tif 000010
」が「【０１４６】
【化９】
2010026804.tif 000011
」と、わずかに異なった表現で記述されている、
●文３では、「【０１４７】
【化１０】
2010026804.tif 000012
」が「【０１４８】
【化１１】
2010026804.tif 000013
」と記述されている、
ため、文２，３からはキーワードが抽出できない。【０１４９】
本発明に係る技術を用いると、キーワードが大量にあった場合でも、以下に説明するとおり、文２，３からもキーワードを抽出することが可能である。なお、以下の説明では、最大削除文字数Ｎ＝１として説明する。【０１５０】
《スキップ辞書作成部》
スキップ辞書作成部１０では、まず、削除キーワードとその値を生成する。例えば、最大削除文字数Ｎ＝１の場合、「【０１５１】
【化１２】
2010026804.tif 000014
」というキーワードからは、図３３に示す４つの削除キーワードとその値が生成される。【０１５２】
次に、生成した削除キーワードとその値をトライ構造に変換して、スキップ辞書を作成する。スキップ入力／スキップ辞書照合でＡＣ法を用いる場合、さらにｆａｉｌｕｒｅ関数、ｏｕｔｐｕｔ関数を定義する。【０１５３】
《キーワード抽出部》
〈スキップ入力／スキップ辞書照合部〉
（１）入力文字列とスキップ辞書の照合
まず、入力文字列そのものとスキップ辞書を照合する。照合アルゴリズムは、図４、図７、図１４、図１６のいずれかを用いる。すると、図３１の各文からは、図３４に示すキーワード候補が得られる。【０１５４】
（２）スキップ入力とスキップ辞書の照合
入力文字列からスキップ入力を作成する。Ｎ＝１において、図３１の文１から作成したスキップ入力を図３５に示す。【０１５５】
次に、各スキップ入力をスキップ辞書と照合する。照合アルゴリズムは、「（１）入力文字列とスキップ辞書の照合」で用いた照合アルゴリズムにより、図４、図７、図１５、図１７のいずれかを用いる。【０１５６】
●（１）で図４を用いた場合は同じく図４のアルゴリズムを使用する。【０１５７】
●（１）で図７を用いた場合は同じく図７のアルゴリズムを使用する。【０１５８】
●（１）で図１４を用いた場合は図１５のアルゴリズムを使用する。【０１５９】
●（１）で図１６を用いた場合は図１７のアルゴリズムを使用する。【０１６０】
得られた全てのキーワード侯補について、一致タイプを分類すると、図３１の各文からは、図３６に示すキーワード侯補が得られる。【０１６１】
〈重複削除部〉
最後に、キーワード侯補集合から、図１８に示すアルゴリズムで重複を削除する。結果、各文からは、図３７に示すキーワードが得られる。【０１６２】
このように、日本語のみでなく、他の言語に関しても、Ｎ字連続までの挿入、削除、置換誤りを含む文字列と、大量のキーワードを高速に照合することが可能である。【０１６３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。【０１６４】
本国際出願は２００８年９月５日に出願された日本国特許出願第２００８−２２８３８２号に基づく優先権を主張するものであり、その全内容を本国際出願に援用する。
【符号の説明】
【０１６５】
１０：スキップ辞書作成部、１１：削除キーワード／値生成部、１２：削除キーワード／値一時記憶部、１３：トライ辞書作成部、２０：スキップ辞書記憶部、３０：キーワード抽出部、３１：スキップ入力／スキップ辞書照合部、３２：照合結果一時記憶部、３３：重複削除部、４０：フィルタリング部、５０：表示部、６０：入力部、７０：表示制御部
【図１】
2010026804.tif 000015
【図２】
2010026804.tif 000016
【図３】
2010026804.tif 000017
【図４】
2010026804.tif 000018
【図５】
2010026804.tif 000019
【図６】
2010026804.tif 000020
【図７】
2010026804.tif 000021
【図８】
2010026804.tif 000022
【図９】
2010026804.tif 000023
【図１０】
2010026804.tif 000024
【図１１】
2010026804.tif 000025
【図１２】
2010026804.tif 000026
【図１３】
2010026804.tif 000027
【図１４】
2010026804.tif 000028
【図１５】
2010026804.tif 000029
【図１６】
2010026804.tif 000030
【図１７】
2010026804.tif 000031
【図１８】
2010026804.tif 000032
【図１９】
2010026804.tif 000033
【図２０】
2010026804.tif 000034
【図２１】
2010026804.tif 000035
【図２２】
2010026804.tif 000036
【図２３】
2010026804.tif 000037
【図２４】
2010026804.tif 000038
【図２５】
2010026804.tif 000039
【図２６】
2010026804.tif 000040
【図２７】
2010026804.tif 000041
【図２８】
2010026804.tif 000042
【図２９】
2010026804.tif 000043
【図３０】
2010026804.tif 000044
【図３１】
2010026804.tif 000045
【図３２】
2010026804.tif 000046
【図３３】
2010026804.tif 000047
【図３４】
2010026804.tif 000048
【図３５】
2010026804.tif 000049
【図３６】
2010026804.tif 000050
【図３７】
2010026804.tif 000051
【国際調査報告】
2010026804.tif 000052
2010026804.tif 000053
2010026804.tif 000054