文字列登録方法，文字列登録プログラム及び文字列探索装置
【課題】目的の文字列がテキスト中のどこにあるかを探索するための文字列探索装置に対し、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を登録する場合でも、できるだけ辞書の容量の増加を抑え、その結果として、探索速度の低下をできるだけ抑える。
【解決手段】互いの相違点が内部の文字を異体字に変えただけの複数の文字列を登録する場合に、異体字を持つ文字の直前の文字の文字ノードオブジェクト１３３において、その次文字がどの異体字であっても一個の文字ノードオブジェクト１３３のアドレスに対応付けられるようにすれば、異体字の数と同数の文字ノードオブジェクト１３３を用意しなくても、一個の文字ノードオブジェクト１３３で、異体字を含む文字列が全て探出されるようになる。
【解決手段】互いの相違点が内部の文字を異体字に変えただけの複数の文字列を登録する場合に、異体字を持つ文字の直前の文字の文字ノードオブジェクト１３３において、その次文字がどの異体字であっても一個の文字ノードオブジェクト１３３のアドレスに対応付けられるようにすれば、異体字の数と同数の文字ノードオブジェクト１３３を用意しなくても、一個の文字ノードオブジェクト１３３で、異体字を含む文字列が全て探出されるようになる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的の文字列（パターン）がテキスト中のどこにあるかを探索するための文字列探索装置に対して任意の文字列を登録する方法と、そのような文字列登録方法を実現する装置としてコンピュータを動作させる文字列登録プログラムと、そのような文字列登録プログラムが実現する機能と同等の機能が組み込まれた文字列探索装置とに、関する。
【背景技術】
【０００２】
周知のように、長い文章の中から所定のキーワードがある箇所を探したり、ＤＮＡ［Doexyribo Nucleic Acid］を構成する塩基配列を示したテキストの中から所定の組み合わせがある箇所を探したりするため、文字列探索という技術がある。
【０００３】
文字列探索には、ラビン＝カープ（ＲＫ）などの力任せ系のアルゴリズム、或いは、クヌース＝モリス＝プラット（ＫＭＰ）やボイヤー＝ムーア（ＢＭ）などのスキップ系アルゴリズムが、知られており、このうち、スキップ系に属するエイホ＝コラシック（ＡＣ）アルゴリズムは、目的の文字列が複数ある場合でも一度の走査で探索を終了できるものとして、知られている。
【０００４】
特許文献１及び特許文献２並びに非特許文献１には、そのＡＣアルゴリズムに従った文字列探索オートマトン（コンピュータ上で実現された機能）の動作についての解説がある。ＡＣアルゴリズムに従った文字列探索オートマトンは、探索されるべき目的文字列を利用者から事前に受け付けておき、探索対象となるテキストが指定されたときには、そのテキストの先頭から一文字ずつ順に取り出しながら、状態遷移関数（goto関数）と失敗関数（failure関数）とに従って、その取り出した文字と取り出した時の内部状態とに応じて内部状態を変化させたり初期状態に戻したりし、内部状態が最終状態に到達したときに、出力関数に従って、その最終状態に対して事前に対応付けられた文字列を出力するというものである。
【０００５】
なお、より具体的には、文字列探索オートマトンは、状態遷移関数や失敗関数の入力値（次の文字）と出力値（遷移すべき内部状態）との対応関係を定義したテーブルを内蔵する文字ノードを、探索されるべき目的文字列を構成する文字ごとに、有している。そして、内部状態とは、何れか一つの文字ノードを参照対象にしている状態を言い、探索されるべき目的文字列の登録とは、これら文字ノードのリンク関係を上記テーブルに定義することを言う。
【０００６】
このＡＣアルゴリズムは、仮名や漢字を含む日本語テキストに対しても有効なものである。従って、仮名や漢字を含む文字列を事前に登録しておけば、その種の文字列が探索対象テキストから確実に探索されることとなる。
【０００７】
【特許文献１】特開平０９−１９８３９８号公報（段落００１７〜００２０）
【特許文献２】特開２００４−０３０６８２号公報（段落０００３，０００４）
【非特許文献１】広瀬健他監訳、「コンピュータ基礎理論ハンドブック（第１巻）アルゴリズムと複雑さ」、丸善株式会社、平成６年３月、２８０頁〜２８４頁
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、漢字の中には、標準的な字形の代わりに、簡略化や一部置換などが施された字形で表すことができるものがある。このように同じ意味を持ちながら少しずつ字形の異なる文字は、異体字と称されているが、一般的には、幾つかの異体字の中の一種類が、通用の字体として利用されている。但し、人名や地名などにおいては、通用されていない異体字を持って正式な名称とされているものもある。従って、文字列探索の対象となるテキストにも、そのような通用されていない字体の文字を含む文字列が使用されている可能性がある。
【０００９】
前述したようなＡＣアルゴリズムに従った従来の文字列探索オートマトンにおいて、通用される字体の文字のみからなる文字列（例えば、渡辺）とは別に、通用されていない字体の文字を含む文字列（渡邉，渡邊）をも探索できるようにしておくためには、何れの文字列とも、事前に登録しておかねばならない。
【００１０】
しかしながら、通用される字体の文字のみからなる文字列に、更に、通用されていない字体の文字を含む文字列をも登録しておくようにすると、辞書の容量が膨大となってしまい、探索速度が遅くなってしまうという問題が生ずる。
【００１１】
本発明は、前述したような従来技術の有する問題点に鑑みてなされたものであり、その課題は、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を、何れも、探索されるべき目的文字列として登録する場合でも、できるだけ辞書の容量の増加を抑え、その結果として、探索速度の低下をできるだけ抑えることにある。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために案出された文字列登録方法は、エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録方法であって、登録対象として指定された文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成手順，前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手順，及び、前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手順からなることを、特徴としている。
【００１３】
また、上記の課題を解決するために案出された文字列登録プログラムは、エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録プログラムであって、コンピュータを、探索されるべき文字列を登録する指示を入力装置を通じて利用者から受け付ける受付手段，前記受付手段が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、メモリ上に生成する文字ノード生成手段，前記文字ノード生成手段がメモリ上に生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手段，及び、前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手段として機能させることを、特徴としている。
【００１４】
また、上記の課題を解決するために案出された文字列探索装置は、エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置であって、探索されるべき文字列を登録する指示を利用者から受け付ける受付部，前記受付部が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成部，前記文字ノード生成部が生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義部，及び、前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義部を備えることを、特徴としている。
【００１５】
これらのように、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を登録する場合に、異体字を持つ文字の直前の文字の文字ノードオブジェクトにおいて、その次文字がどの異体字であっても一個の文字ノードオブジェクトの所在情報に対応付けられるようにすれば、異体字の数と同数の組数の文字ノードオブジェクトを用意しなくても、一個の文字ノードオブジェクトで、異体字を含む文字列が全て探出されるようになる。これにより、異体字の文字ノードオブジェクトを用意せずに済む分だけ、辞書の容量の増加が抑えられることとなる。
【００１６】
なお、前述した本発明は、更に、文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトの所在情報とその文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものとを対応付けてテーブルに格納しておいて（候補生成手順）、文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものの末尾から一文字ずつ削除するごとに、削除後の文字群で前記テーブルを検索する処理，及び、何れかの検索によりそのテーブルからレコードが検出できたときに、その文字群の先頭文字を示す文字情報と、そのレコード内の所在情報とを対応付けて記録する処理を行う（失敗遷移先構築手順）ものであっても良い。
【００１７】
これらの処理を行うようにすれば、文字ノードオブジェクトに失敗遷移の遷移先を簡単に登録することができるようになる。
【００１８】
また、本発明に対し、前述したような手順を追加したものとした場合において、失敗遷移先構築手順で行う削除処理の結果、逆順に並び替えた文字群が残り一文字となったときには、その残りの一文字に対し、登録された文字列における先頭文字の文字ノード（ルートノード）を対応付けて、失敗遷移先として登録しておくと良い。こうすると、失敗遷移後の遷移ステップ数が従来技術に比して減ることとなるため、文字列探索の速度が向上することとなる。
【発明の効果】
【００１９】
従って、本発明によれば、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を、何れも、探索されるべき目的文字列として登録する場合でも、辞書の容量の増加を抑えることができ、その結果として、探索速度の低下を抑えることができるようになる。
【発明を実施するための最良の形態】
【００２０】
次に、本発明を実施するための最良の形態について、添付図面を参照しながら、詳細に説明する。
【００２１】
先ず、本実施形態の文字列探索装置の構成について説明する。
【００２２】
図１は、本実施形態の文字列探索装置１０の構成図である。
【００２３】
図１に示すように、文字列探索装置１０は、後述のプログラム群及びデータ群を一般的なパーソナルコンピュータに導入してなる装置である。この文字列探索装置１０を構成するパーソナルコンピュータは、周知のように、液晶ディスプレイ等の表示装置１０ａ，キーボードやマウス等の入力装置１０ｂ，及び、これら装置１０ａ，１０ｂが接続された本体とからなり、その本体は、ＨＤＤ［Hard Disk Drive］１０ｃ，ＣＰＵ［Central Processing Unit］１０ｃ，ＤＲＡＭ［Dynamic Random Access Memory］１０ｅ，その他のハードウエアを、内蔵している。このうち、ＨＤＤ１０ｃは、各種のプログラムやデータを記憶する記憶装置であり、ＣＰＵ１０ｄは、そのＨＤＤ１０ｃ内のプログラムに従って各種の処理を行う制御装置であり、ＤＲＡＭ１０ｅは、ＣＰＵ１０ｄがプログラムに従った処理を行う際に作業領域が展開される揮発性記憶装置である。
【００２４】
そして、この文字列探索装置１０のＨＤＤ１０ｃには、テキストデータ１１，アプリケーション１２，及び、文字列探索ソフトウエア１３が、格納されている。テキストデータ１１は、テキストを表示するためのテキストデータである。なお、本実施形態では、このテキストデータ１１には、仮名や漢字を含む日本語の文章を表示するためのテキストデータが含まれている。アプリケーション１２は、テキストデータ１１に基づいてテキストを表示装置１０ａに表示したりそのテキストの編集及び保存をするための機能を提供したりするためのソフトウエアである。文字列探索ソフトウエア１３は、そのアプリケーション１２からの要求を受けてテキストの中から所定の文字列を探索してその探索結果をアプリケーション１２に応答するためのソフトウエアである。
【００２５】
図２は、文字列探索ソフトウエア１３の内部構成とこれににより実現される機能とを示す概略図である。
【００２６】
図２に示すように、文字列探索ソフトウエア１３は、オブジェクト生成プログラム１３ａ，文字列探索オートマトンライブラリ１３ｂ，ルートノード管理機能ライブラリ１３ｃ，文字ノードライブラリ１３ｄ，失敗遷移機能ライブラリ１３ｅ，パターン登録プログラム１３ｆ，及び、失敗遷移先構築プログラム１３ｇを、含んでいる。
【００２７】
このうち、オブジェクト生成プログラム１３ａは、各ライブラリ１３ｂ〜１３ｅに基づいて、それぞれに対応するオブジェクトをＤＲＡＭ１０ｅ上に生成するためのプログラムである。なお、各オブジェクトの生成時において、各オブジェクトには、ＤＲＡＭ１０ｅ上の所定の大きさの領域が個別に割り当てられるようになっている。
【００２８】
また、文字列探索オートマトンライブラリ１３ｂは、事前に登録されている文字列を対象テキストの中から探索する機能を実現するオブジェクト１３１をＤＲＡＭ１０ｅ上に生成するためのライブラリである。図２には、このライブラリ１３ｂに基づいてＤＲＡＭ１０ｅ上に生成される文字列探索オートマトンオブジェクト１３１が、示されている。この文字列探索オートマトンオブジェクト１３１は、後述のオブジェクト１３２〜１３４を使用することによって、対象テキストの中から文字列を探索する。なお、文字列探索オートマトンライブラリ１３ｂは、各オブジェクト１３２〜１３４に割り当てられたＤＲＡＭ１０ｅ上領域のアドレスによって、使用すべきオブジェクトを特定する。この文字列探索オートマトンオブジェクト１３１が実行する文字列探索処理の内容については、図１７及び図１８を用いて後述する。
【００２９】
また、ルートノード管理機能ライブラリ１３ｃは、ルートノード管理機能オブジェクト１３２を生成するためのライブラリである。ルートノード管理機能オブジェクト１３２は、文字列探索オートマトンライブラリ１３ｂが対象テキストの中から一文字ずつ取り出したときにおいて、その取り出した文字が探索されるべき文字列の先頭文字であるか否かを判定する際に利用されるオブジェクトである。
【００３０】
図３は、このルートノード管理機能オブジェクト１３２の概念図である。
【００３１】
図３に示すように、ルートノード管理機能オブジェクト１３２は、ルートノード管理テーブル１３２ａを含んでいる。ルートノード管理テーブル１３２ａは、文字列探索オートマトンライブラリ１３ｂが処理対象としている文字が何れかの文字列の先頭文字であるか否かを検索する際に利用されるテーブルであり、探索されるべき各文字列の先頭文字が登録されている。より具体的には、このルートノード管理テーブル１３２ａ内の各レコードは、「文字」及び「ポインタ」の各フィールドを有しており、このうち、「文字」フィールドには、探索されるべき文字列の先頭文字が記録され、「ポインタ」フィールドには、その先頭文字に対応する後述の文字ノードオブジェクト１３３のアドレスが記録される。なお、これ以降において、先頭文字に対応する文字ノードオブジェクト１３３を、先頭でない文字に対応する文字ノードオブジェクト１３３と区別する必要がある場合、「ルートノードオブジェクト」と表記する。
【００３２】
また、図２の文字ノードライブラリ１３ｄは、ＤＲＡＭ１０ｅ上に文字ノードオブジェクト１３３を生成するためのライブラリである。この文字ノードライブラリ１３ｄは、複数存在し、ＤＲＡＭ１０ｅ上には、それら文字ノードライブラリ１３ｄ一つ一つに対応する文字ノードオブジェクト１３３が複数生成される。文字ノードオブジェクト１３３は、原則として、探索されるべき各文字列を構成する文字のそれぞれについて、生成される。但し、各文字列において、先頭文字から途中の文字までの文字の並びが共通する場合、それら共通する部分の文字に対応する文字ノードオブジェクト１３３は、共通のものが一つ生成される。例えば、「河原崎」と「河原田」という二つの文字列においては、「河原」が共通するので、この場合、「河」と「原」の文字ノードオブジェクト１３３は、「河原崎」と「河原田」とに共通するものとして一組生成される。なお、この場合において、例えば「原田」という文字列が探索されるべきものとして登録されているときには、その「原田」の「原」の文字ノードオブジェクト１３３は、「河原」の「原」の文字ノードオブジェクト１３３とは別途、存在する。文字ノードオブジェクト１３３は、そのオブジェクト１３３が対象テキストの中から取り出された一文字に対応するオブジェクトである場合において、その取り出された文字の次の文字が、次にくるべき文字（その文字を含む文字列内でのその文字の次に存在すべき文字）であるか否かを判別する際に利用されるオブジェクトである。
【００３３】
図４乃至図９は、この文字ノードオブジェクト１３３の概念図である。なお、図４乃至図９のうち、図４及び図８は、ルートノードオブジェクトを示している。
【００３４】
図４乃至図９に示すように、文字ノードオブジェクト１３３は、経緯情報１３３ａ，ハッシュマップテーブル１３３ｂ，及び、失敗時遷移先管理テーブル１３３ｃを、含んでいる。経緯情報１３３ａは、その文字ノードオブジェクト１３３に対応する文字を含む文字列における先頭文字からその文字までの文字群を示す情報である。例えば、「勅使河原」という文字列において、「河」の文字ノードオブジェクト１３３であれば、経緯情報１３３ａが示す文字群は、「勅使河」である（図６参照）。ハッシュマップテーブル１３３ｂは、文字列探索オートマトンオブジェクト１３１が探索対象から取り出した一文字（処理対象文字）が、その文字ノードオブジェクト１３３に対応する文字を含む文字列におけるその文字の次の文字と、一致するか否かを判断する際に利用されるテーブルである。具体的には、このハッシュマップテーブル１３３ｂ内の各レコードは、「文字」及び「ポインタ」の各フィールドを有しており、このうち、「文字」フィールドには、経緯情報１３３ａが示す文字群の次に存在し得る文字が記録され、「ポインタ」フィールドには、その文字に対応する文字ノードオブジェクト１３３のアドレスが記録される（図５及び図８参照）。失敗時遷移先管理テーブル１３３ｃは、処理対象文字がハッシュマップテーブル１３３ｂから検索されなかったときに使用されるテーブルである。具体的には、この失敗時遷移先管理テーブル１３３ｃ内の各レコードも、「文字」及び「ポインタ」の各フィールドを有しており、「文字」フィールドには、この文字ノードオブジェクト１３３に対応する文字と同じ文字が記録され、「ポインタ」フィールドには、同じ文字が対応付けられている別の文字ノードオブジェクト１３３のアドレスが記録される。さらに、文字ノードオブジェクト１３３の中には、終端情報１３３ｄを含むものもある。終端情報１３３ｄは、経緯情報１３３ａの示す文字群だけで、探索されるべき文字列が成立する場合に、その旨を示す情報である。
【００３５】
ここで、図１０は、図４乃至図９に示した文字ノードオブジェクト１３３のリンク状態を模式的に示す概略図である。
【００３６】
図１０では、丸で囲まれた文字が文字ノードを示しており、これら文字ノードうち、図１０において最も左側にある「勅」，「使」，「河」，「原」がルートノードとして示されている。なお、ルートノードは、ルートノード管理機能オブジェクト１３２のルートノード管理テーブル１３２ａに定義されている。そして、これらルートノードを起点として、「勅使河原」，「勅使川原」，「勅使ケ原」，「勅使」，「使河」，「河原」，「河原田」，「河原崎」，「河野」，「河合」，「河村」，「原田」，「原口」の文字列のリンク状態が、実線で示されている。なお、これら実線で示されるリンク状態は、各文字ノードオブジェクト１３３のハッシュマップテーブル１３３ｂにて定義されている。また、この図１０において、波線は、その文字を含む文字列（例えば「勅使河原」）における先頭以外の文字からその文字までの文字群（例えば「使河」）で別途文字列が成立している場合に、その別の文字列（「使河」）における対応する文字ノード（河）への遷移を、示している。また、一点鎖線は、その文字ノードの前方（図１０の右方）に遷移すべき文字ノードが無く、且つ、同一の文字に対応付けられている別の文字ノードへの遷移（波線で示される遷移）もできない場合の遷移方向を、示している。なお、これら波線及び一点鎖線で示されるリンク状態は、各文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに定義されており、本発明は、これら波線及び一点鎖線で示される遷移先を文字ノードオブジェクト１３３に簡単に登録できる手段について、提供するものである。
【００３７】
また、図２の失敗遷移機能ライブラリ１３ｅは、ＤＲＡＭ１０ｅ上に失敗遷移機能オブジェクト１３４を生成するためのライブラリである。失敗遷移機能オブジェクト１３４は、後述の失敗遷移先構築プログラム１３ｇによる処理において使用される情報を記録しておくためのオブジェクトである。
【００３８】
図１１は、この失敗遷移機能オブジェクト１３４の概念図である。
【００３９】
図１１に示すように、失敗遷移機能オブジェクト１３４は、遷移先候補管理テーブル１３４ａを含んでいる。遷移先候補管理テーブル１３４ａは、後述の失敗遷移先構築プログラム１３ｇによる処理において使用される情報を記録しておくためのテーブルである。具体的には、この遷移先候補管理テーブル１３４ａ内の各レコードは、「文字」及び「ポインタ」の各フィールドを有しており、このうち、「文字」フィールドには、経緯情報１３３ａを示す文字群を逆順にしたものが記録され、「ポインタ」フィールドには、その経緯情報１３３ａを持つ文字ノードオブジェクト１３３のアドレスが記録される。
【００４０】
図２のパターン登録プログラム１３ｆは、文字列探索オートマトンオブジェクト１３１に探索させる文字列を登録する機能を実現するためのプログラムである。なお、この文字列の登録とは、具体的には、文字ノードオブジェクト１３３のリンク関係を、各文字ノードオブジェクト１３３のハッシュマップテーブル１３３ｂに定義することである。このパターン登録プログラム１３ｆに従ってＣＰＵ１０ｄが実行する処理の内容については、図１２乃至図１４を用いて後述する。
【００４１】
図２の失敗遷移先構築プログラム１３ｇは、各文字ノードオブジェクト１３３において前方遷移（図１０の実線で示す遷移）ができないときに別途検索される遷移先を登録するためのプログラムである。なお、この遷移先の登録とは、具体的には、文字ノードオブジェクト１３３のリンク関係を、各文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに定義することである。この失敗遷移先構築プログラム１３ｇに従ってＣＰＵ１０ｄが実行する処理の内容については、図１５及び図１６を用いて後述する。
【００４２】
次に、本実施形態の文字列探索装置１０において実行される処理について、説明する。
【００４３】
文字列探索装置１０では、所定の時期（起動時或いは実行指示時）に文字列探索ソフトウエア１３が起動され、オブジェクト生成プログラム１３ａによってＤＲＡＭ１０ｅ上に各オブジェクト１３１〜１３４が生成されるようになっている。これにより、各オブジェクト１３１〜１３４が常駐した状態になる。
【００４４】
このような状態において、文字列探索装置１０の入力装置１０ｂを操作する操作者によって、探索されるべき文字列が登録対象として指定された後、パターン登録プログラム１３ｆが起動されると、パターン登録処理が開始される。
【００４５】
図１２乃至図１４は、このパターン登録処理の流れを示す図である。
【００４６】
パターン登録処理の開始後、最初のステップＳ１００１では、ＣＰＵ１０ｄは、登録対象として指定された文字列の先頭文字を検索条件として、図３のルートノード管理テーブル１３２ａを検索する処理を行う。
【００４７】
次のステップＳ１００２では、ＣＰＵ１０ｄは、当該文字列の先頭文字と同一の文字を含むレコードがルートノード管理テーブル１３２ａから検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字列の先頭文字と同一の文字を含むレコードがルートノード管理テーブル１３２ａから検出できなかった場合には、ステップＳ１００２からステップＳ１００３へ処理を進め、当該文字列の先頭文字と同一の文字を含むレコードがルートノード管理テーブル１３２ａから検出できた場合には、ステップＳ１００２から処理を分岐させ、ステップＳ１００４へ処理を進める。
【００４８】
ステップＳ１００３では、ＣＰＵ１０ｄは、ルートノードを生成する処理を行う。具体的には、ＣＰＵ１０ｄは、登録対象として指定された文字列の先頭文字に対応する文字ノードライブラリ１３ｄを生成してＨＤＤ１０ｃに保存する処理を行うとともに、オブジェクト生成プログラム１３ａによる機能を通じてその先頭文字に対応する文字ノードオブジェクト１３３をＤＲＡＭ１０ｅ上に生成する処理を行う。さらに、ＣＰＵ１０ｄは、その生成した文字ノードオブジェクト１３３のアドレスとこれに対応する文字とを含むレコードを図３のルートノード管理テーブル１３２ａに新規追加する処理を行う。これにより、生成された文字ノードオブジェクト１３３は、ルートノードオブジェクトとして設定されることとなる。ＣＰＵ１０ｄは、このような処理を行った後、ステップＳ１００４へ処理を進める。
【００４９】
ステップＳ１００４では、ＣＰＵ１０ｄは、ステップＳ１００１で検出したレコード内のアドレスにより示される領域にあるルートノードオブジェクト１３３，又は、ステップＳ１００３でルートノード管理テーブル１３２ａに登録したルートノードオブジェクト１３３を、処理対象ノードとして特定する。
【００５０】
次のステップＳ１００５では、ＣＰＵ１０ｄは、登録対象に指定された文字列の中から未処理の文字を検索する処理を行う。
【００５１】
次のステップＳ１００６では、ＣＰＵ１０ｄは、当該文字列から未処理の文字が検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字列から未処理の文字が検出できた場合、ステップＳ１００６から処理を分岐させ、ステップＳ１００７へ処理を進める。
【００５２】
ステップＳ１００７では、ＣＰＵ１０ｄは、未処理の文字のうち、先頭側の一つを処理対象文字として特定する。
【００５３】
次のステップＳ１００８では、ＣＰＵ１０ｄは、処理対象文字を検索条件として、処理対象ノードのハッシュマップテーブル１３３ｂを検索する処理を行う。
【００５４】
次のステップＳ１００９では、ＣＰＵ１０ｄは、処理対象文字と同一の文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、処理対象文字と同一の文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できなかった場合には、次文字ノード生成処理（ステップＳ１０１０乃至Ｓ１０１２）を実行し、処理対象文字と同一の文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できた場合には、ステップＳ１００９から処理を分岐させ、ステップＳ１０１４へ処理を進める。
【００５５】
次文字ノード生成処理の最初のステップＳ１０１０では、ＣＰＵ１０ｄは、登録対象として指定された文字列の先頭から処理対象文字までの文字群を、逆順に並べ替える処理を行う。
【００５６】
次のステップＳ１０１１では、ＣＰＵ１０ｄは、処理対象文字に対応する文字ノードを生成する処理を行う。具体的には、処理対象文字に対応する文字ノードライブラリ１３ｄを生成してＨＤＤ１０ｃに保存する処理を行うとともに、オブジェクト生成プログラム１３ａによる機能を通じてその先頭文字に対応する文字ノードオブジェクト１３３をＤＲＡＭ１０ｅ上に生成する処理を行う。ここで、生成される文字ノードオブジェクト１３３には、ステップＳ１０１０で逆順に並び替えられる前の文字群が、経緯情報１３３ａとして格納されるようになっている。なお、このステップＳ１０１１は、前述した文字ノード生成手順に相当し、このステップＳ１０１１を実行するＣＰＵ１０ｄは、前述した文字ノード生成手段及び文字ノード生成部に相当している。
【００５７】
次のステップＳ１０１２では、ＣＰＵ１０ｄは、ステップＳ１０１０で逆順に並び替えられた文字群と、ステップＳ１０１１で生成した文字ノードオブジェクト１３３のアドレスとを含むレコードを、図１１の遷移先候補管理テーブル１３４ａに新規登録する処理を行う。なお、このステップＳ１０１２は、前述した候補生成手順に相当している。
【００５８】
次のステップＳ１０１３では、ＣＰＵ１０ｄは、以上に説明した次文字ノード生成処理（ステップＳ１０１０乃至Ｓ１０１２）により生成した文字ノードオブジェクト１３３に対応するレコードを、処理対象ノードのハッシュマップテーブル１３３ｂに登録する処理を行う。なお、このステップＳ１０１３は、前述した前方リンク定義手順に相当し、このステップＳ１０１３を実行するＣＰＵ１０ｄは、前述した前方リンク定義手段及び前方リンク定義部に相当している。その後、ＣＰＵ１０ｄは、ステップＳ１０１４へ処理を進める。
【００５９】
ステップＳ１０１４では、ＣＰＵ１０ｄは、ステップＳ１００８で検出したレコード内のアドレス，又は、次文字ノード生成処理で生成した文字ノードオブジェクト１３３のアドレスを、取得する処理を行う。
【００６０】
次のステップＳ１０１５では、ＣＰＵ１０ｄは、処理対象文字の異体字を検索する処理を行う。なお、このステップＳ１０１５では、ＣＰＵ１０ｄは、例えば図示せぬ日本語入力支援ソフトウエアが有する辞書を検索する。
【００６１】
次のステップＳ１０１６では、ＣＰＵ１０ｄは、処理対象文字の異体字が検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、処理対象文字の異体字が検出できた場合には、第１の処理ループＬ１を実行し、処理対象文字の異体字が検出できなかった場合には、ステップＳ１０１６から処理を分岐させ、ステップＳ１０１８へ処理を進める。
【００６２】
第１の処理ループＬ１では、ＣＰＵ１０ｄは、検出された異体字のそれぞれについて、ステップＳ１０１７を実行する。
【００６３】
ステップＳ１０１７では、ＣＰＵ１０ｄは、処理対象の異体字と、処理対象文字に対応する文字ノードオブジェクト１３３のアドレスとを含むレコードを、処理対象ノードのハッシュマップテーブル１３３ｂに新規追加する処理を行う。なお、このステップＳ１０１７は、前述した異体字リンク定義手順に相当し、このステップＳ１０１７を実行するＣＰＵ１０ｄは、前述した異体字リンク定義手段及び異体字リンク定義部に相当している。
【００６４】
ＣＰＵ１０ｄは、このステップＳ１０１７を、ステップＳ１０１５で検出された異体字の全てについて実行した後、この第１の処理ループＬ１から離脱し、ステップＳ１０１８へ処理を進める。
【００６５】
ステップＳ１０１８では、ＣＰＵ１０ｄは、処理対象ノードを、ステップＳ１０１４で取得したアドレスが示す領域にある文字ノードオブジェクト１３３に、変更する処理を行う。その後、ＣＰＵ１０ｄは、ステップＳ１００５へ処理を戻す。
【００６６】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ１００５乃至Ｓ１０１８を繰り返し行う間に、登録対象として指定された文字列から未処理の文字が検出できなくなったときには、ステップＳ１００６からステップＳ１０１９へ処理を進める。
【００６７】
ステップＳ１０１９では、ＣＰＵ１０ｄは、処理対象ノードに終端情報１３３ｄを記録する処理を行い、その後、図１２乃至図１４に係るパターン登録処理を終了する。
【００６８】
このようなパターン登録処理が繰り返されることにより、探索されるべき文字列が複数登録された後、文字列探索装置１０の入力装置１０ｂを操作する操作者によって、失敗遷移先構築プログラム１３ｇが起動されると、失敗遷移先構築処理が開始される。
【００６９】
図１５及び図１６は、失敗遷移先構築処理の流れを示す図である。
【００７０】
失敗遷移先構築処理の開始後、最初のステップＳ２００１では、ＣＰＵ１０ｄは、図３のルートノード管理テーブル１３２ａからアドレスを順に読み出して、ＤＲＡＭ１０ｅ内に事前に確保した第１のスタックに記録する処理を行う。この処理により、第１のスタックには、ルートノード管理テーブル１３２ａ内の全てのアドレスが、読み出されることとなる。
【００７１】
次のステップＳ２００２では、ＣＰＵ１０ｄは、第１のスタックの中から末尾のアドレスを一つ取り出す処理を行う。
【００７２】
次のステップＳ２００３では、ＣＰＵ１０ｄは、ステップＳ２００２で取り出したアドレスが示す領域にある文字ノードオブジェクト１３３のハッシュマップテーブル１３３ｂからアドレスを順に読み出して、ＤＲＡＭ１０ｅ内に事前に確保した第２のスタックに記録する処理を行う。この処理により、第２のスタックには、ハッシュマップテーブル１３３ｂ内の全てのアドレスが、読み出されることとなる。
【００７３】
次のステップＳ２００４では、ＣＰＵ１０ｄは、第２のスタックの中から末尾のアドレスを一つ取り出す処理を行う。
【００７４】
次のステップＳ２００５では、ＣＰＵ１０ｄは、ステップＳ２００４で取り出したアドレスにある文字ノードオブジェクト１３３の経緯情報１３３ａを読み出し、この経緯情報１３３ａの示す文字群を逆順に並べ替える処理を行う。
【００７５】
次のステップＳ２００６では、ＣＰＵ１０ｄは、当該文字群から末尾の一文字を除去する処理を行う。
【００７６】
次のステップＳ２００７では、ＣＰＵ１０ｄは、ステップＳ２００６での除去によって当該文字群の文字が残り一文字になったか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字群が二文字以上からなる場合、ステップＳ２００７から処理を分岐させ、ステップＳ２００８へ処理を進める。
【００７７】
ステップＳ２００８では、ＣＰＵ１０ｄは、当該文字群を検索条件として、図１１の遷移先候補管理テーブル１３４ａを検索する処理を行う。
【００７８】
次のステップＳ２００９では、ＣＰＵ１０ｄは、当該文字群と同じ文字群を含むレコードが遷移先候補管理テーブル１３４ａから検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字群と同じ文字群を含むレコードが遷移先候補管理テーブル１３４ａから検出できなかった場合、ステップＳ２００９から処理を分岐させ、ステップＳ２００６へ処理を戻す。
【００７９】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ２００６乃至Ｓ２００９を繰り返し行う間に、当該文字群と同じ文字群を含むレコードが遷移先候補管理テーブル１３４ａから検出できたときには、ステップＳ２００９からステップＳ２０１０へ処理を進める。
【００８０】
ステップＳ２０１０では、ＣＰＵ１０ｄは、ステップＳ２００８で検出されたレコード内のアドレスと、当該文字群の先頭の文字とを含むレコードを、ステップＳ２００４で取り出したアドレスが示す領域にある文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに新規追加する処理を行う。
【００８１】
次のステップＳ２０１１では、ＣＰＵ１０ｄは、ステップＳ２０１０で失敗時遷移先管理テーブル１３３ｃに登録されたアドレスを、第２のスタックに格納する処理を行う。その後、ＣＰＵ１０ｄは、ステップＳ２０１３へ処理を進める。
【００８２】
また、ＣＰＵ１０ｄは、ステップＳ２００６乃至Ｓ２００９を繰り返し行う間に、当該文字群が残り一文字になってしまったときには、ステップＳ２００７からステップＳ２０１２へ処理を進める。
【００８３】
ステップＳ２０１２では、ＣＰＵ１０ｄは、当該一文字に対応するルートノードオブジェクト１３３のアドレスを、図１１の遷移先候補管理テーブル１３４ａから読み出し、続いて、当該一文字と当該アドレスとを含むレコードを、ステップＳ２００４で取り出したアドレスが示す領域にある文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに新規追加する処理を行う。その後、ＣＰＵ１０ｄは、ステップＳ２０１３へ処理を進める。
【００８４】
ステップＳ２０１３では、ＣＰＵ１０ｄは、第２のスタックを検索する処理を行う。
【００８５】
次のステップＳ２０１４では、ＣＰＵ１０ｄは、第２のスタックからアドレスが検出できたか否かを、判別する処理を行う。そして、ＣＰＵ１０ｄは、第２のスタックからアドレスが検出できた場合、ステップＳ２０１４から処理を分岐させ、ステップＳ２００４へ処理を戻す。
【００８６】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ２００４乃至Ｓ２０１４を繰り返す間に、第２のスタックからアドレスが検出できなくなったときには、ステップＳ２０１３からステップＳ２０１５へ処理を進める。
【００８７】
ステップＳ２０１５では、ＣＰＵ１０ｄは、第１のスタックを検索する処理を行う。
【００８８】
次のステップＳ２０１６では、ＣＰＵ１０ｄは、第１のスタックからアドレスが検出できたか否かを、判別する処理を行う。そして、ＣＰＵ１０ｄは、第１のスタックからアドレスが検出できた場合、ステップＳ２０１６から処理を分岐させ、ステップＳ２００２へ処理を戻す。
【００８９】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ２００２乃至Ｓ２０１６を繰り返す間に、第１のスタックからアドレスが検出できなくなったときには、図１４及び図１５に係る失敗遷移先構築処理を終了する。
【００９０】
このような失敗遷移先構築処理が行われることにより、探索すべき文字列が複数登録された際に生成された文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃの内容が、生成され、図１０において波線や一点鎖線で示すようなリンク構造が構築されることとなる。なお、この図１４及び図１５に係る失敗遷移先構築処理は、前述した失敗遷移先構築手順に相当している。
【００９１】
また、ＤＲＡＭ１０ｅ上に各オブジェクト１３１〜１３４が存在している状態において、文字列探索オートマトンオブジェクト１３１が、アプリケーション１２から、所定のテキストを探索対象とした指定とともに、文字列の探索の依頼を受けると、文字列探索処理を開始する。
【００９２】
図１７及び図１８は、文字列探索処理の流れを示す図である。
【００９３】
文字列探索処理の開始後、最初のステップＳ３００１では、文字列探索オートマトンオブジェクト１３１（を実現しているＣＰＵ１０ｄ）は、探索対象テキストから未処理で先頭側の一文字を読み出す処理を行う。
【００９４】
次のステップＳ３００２では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００１で読み出した文字を検索条件として、図３のルートノード管理テーブル１３２ａを検索する処理を行う。
【００９５】
次のステップＳ３００３では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００１で読み出した文字と同じ文字を含むレコードがルートノード管理テーブル１３２ａから検出できたか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００１で読み出した文字と同じ文字を含むレコードがルートノード管理テーブル１３２ａから検出できなかった場合には、ステップＳ３００３から処理を分岐させてステップＳ３００１へ処理を戻し、ステップＳ３００１で読み出した文字と同じ文字を含むレコードがルートノード管理テーブル１３２ａから検出できた場合には、ステップＳ３００３からステップＳ３００４へ処理を進める。
【００９６】
ステップＳ３００４では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００２で検出したレコード内のアドレスが示す領域にある文字ノードオブジェクト（ルートノードオブジェクト）１３３を、処理対象ノードに設定する処理を行う。
【００９７】
次のステップＳ３００５では、文字列探索オートマトンオブジェクト１３１は、処理対象ノードに終端情報１３３ｄが含まれているか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、処理対象ノードに終端情報１３３ｄが含まれていた場合には、ステップＳ３００５からステップＳ３００６へ処理を進め、処理対象ノードに終端情報１３３ｄが含まれていなかった場合には、ステップＳ３００５から処理を分岐させてステップＳ３００７へ処理を進める。
【００９８】
ステップＳ３００６では、文字列探索オートマトンオブジェクト１３１は、処理対象モードの経緯情報１３３ａの示す文字群を、探索結果として、アプリケーション１２１（図２参照）に出力する処理を行う。その後、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７へ処理を進める。
【００９９】
ステップＳ３００７では、文字列探索オートマトンオブジェクト１３１は、探索対象テキスト内の未処理の文字の中から先頭側の一文字を読み出す処理を行う。
【０１００】
次のステップＳ３００８では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字を検索条件として、処理対象ノードのハッシュマップテーブル１３３ｂを検索する処理を行う。
【０１０１】
次のステップＳ３００９では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できたか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できた場合、ステップＳ３００９から処理を分岐させ、ステップＳ３０１０へ処理を進める。
【０１０２】
ステップＳ３０１０では、文字列探索オートマトンオブジェクト１３１は、処理対象ノードを、ステップＳ３００８で検出したレコード内のアドレスにある文字ノードオブジェクト１３３に変更する処理を行う。その後、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００５へ処理を戻す。
【０１０３】
一方、ステップＳ３００９において、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できなかった場合、ステップＳ３００９からステップＳ３０１１へ処理を進める。
【０１０４】
ステップＳ３０１１では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字を検索条件として、処理対象ノードの失敗時遷移先管理テーブル１３３ｃを検索する処理を行う。
【０１０５】
次のステップＳ３０１２では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードの失敗時遷移先管理テーブル１３３ｃから検出できたか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードの失敗時遷移先管理テーブル１３３ｃから検出できた場合、ステップＳ３０１２から処理を分岐させ、ステップＳ３０１３へ処理を進める。
【０１０６】
ステップＳ３０１３では、文字列探索オートマトンオブジェクト１３１は、処理対象ノードを、ステップＳ３０１１で検出したレコード内のアドレスにある文字ノードオブジェクト１３３に変更する処理を行う。その後、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００５へ処理を戻す。
【０１０７】
一方、ステップＳ３０１３において、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できなかった場合、ステップＳ３０１３からステップＳ３０１４へ処理を進める。
【０１０８】
ステップＳ３０１４では、文字列探索オートマトンオブジェクト１３１は、探索対象テキスト内に未処理の文字が存在するか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、探索対象テキスト内に未処理の文字が存在していた場合には、ステップＳ３０１４から処理を分岐させ、ステップＳ３００１へ処理を戻す。
【０１０９】
文字列探索オートマトンオブジェクト１３１は、以上に説明したステップＳ３００１乃至Ｓ３０１４を繰り返し行う間に、探索対象テキスト内から未処理の文字がなくなると、図１７及び図１８に係る文字列探索処理を終了する。
【０１１０】
次に、本実施形態の文字列探索装置１０の作用及び効果について、説明する。
【０１１１】
文字列探索装置１０の操作者は、図１７及び図１８の文字列探索処理により探索対象テキストから探索されるべき目的文字列を登録する場合、文字列を指定してパターン登録プログラム１３ｆを実行させる。すると、従来技術と同様に、文字列を構成する文字のそれぞれについて、次文字の文字ノードの作成と次文字のハッシュマップテーブルへの登録とが、順に行われる（ステップＳ１００５〜Ｓ１０１３，Ｓ１０１８）。
【０１１２】
そして、このパターン登録処理において、順次処理対象とされる次文字について、異体字が存在していた場合（ステップＳ１０１６）、その異体字も全て、ハッシュマップテーブル１３３ｂに登録される（Ｌ１）。このとき、ハッシュマップテーブル１３３ｂ内で各異体字に対応付けられる文字ノードオブジェクト１３３は、図９に示されるように、全て共通の文字ノードオブジェクト１３３となっている。このため、操作者が登録しようとした文字列が通用される字体のみからなるものだけであったとしても、一部の文字が異体字に置換された文字列が、探索対象テキストに含まれていた場合には、図１７及び図１８の文字列探索処理において、その文字列も必ず探出されることとなる（図１０参照）。例えば、操作者が「渡辺」という文字列を指定してパターン登録プログラム１３ｆを実行すれば、その「渡辺」の文字列が探出されるようになるだけでなく、「渡邉」や「渡邊」も探出されるようになる。
【０１１３】
このように異体字が登録されることにより、異体字の数と同数の文字ノードオブジェクト１３３を用意する必要がなくなり（辺，邉，邊の三つの文字ノードを用意しなくても）、一個の文字ノードオブジェクトだけで文字列の登録が済むようになるので（辺の文字ノードだけで済むので）、異体字が多数あったとしても、文字ノードオブジェクト１３３の個数が増えないこととなる。このため、一部の文字を異体字に置換した文字列をも登録する場合であっても、辞書の容量の増加が抑えられることとなる。
【０１１４】
また、本実施形態の文字列探索装置１０では、探索されるべき文字列を登録し終えた後、失敗遷移先構築プログラム１３ｇを実行することにより、各文字ノードオブジェクト１３３における失敗遷移先の登録が、簡単に行える。
【０１１５】
この失敗遷移先の登録においては、その文字を含む文字列（例えば、勅使河原）のうち先頭文字以外の文字からその文字（河）までの文字群（例えば、使河）と同じ文字構成の別の文字列（使河）が登録されている場合には、従来と同様、その別の文字列（使河）の対応する文字（河）の文字ノードオブジェクト１３３が、前方遷移ができないとき（ハッシュマップテーブル１３３ｂで次文字が検出できないときに）の失敗遷移先として、登録される。
【０１１６】
さらに、本実施形態においては、失敗遷移先として、別の文字列の対応する文字がなかった場合には、同じ文字に対応付けられているルートノードオブジェクト１３３が登録される（ステップＳ２００７；ＹＥＳ，Ｓ２０１２）。
【０１１７】
このように、失敗遷移先として、同じ文字に対応付けられているルートノードオブジェクト１３３が、登録されると、図１７及び図１８の文字列探索処理において、失敗遷移先がなかったときに（ステップＳ３０１２；ＹＥＳ）、従来では、ステップＳ３０１４，Ｓ３００１〜Ｓ３００４を経なければならなかったものが、本実施形態によれば、ステップＳ３０１３だけを経るだけで済むようになる。これにより、失敗遷移処理を行う際のステップ数が従来技術に比して減ることとなるため、文字列探索処理に掛かる時間を短縮できるようになる。
【０１１８】
なお、以上の説明においては、漢字のみからなる文字列を、探索されるべき文字列の例として挙げたが、これに限定されるものではない。例えば、仮名のみからなる文字列であっても、仮名と漢字とが混ざった文字列であっても、仮名と漢字と算用数字とが混ざった文字列であってもよい。何れの場合も、文字列探索装置１０に登録でき、探索対象テキストから探出させることができる。
【図面の簡単な説明】
【０１１９】
【図１】本実施形態の文字列探索装置の構成図
【図２】文字列探索ソフトウエアの内部構成とこれににより実現される機能とを示す概略図
【図３】ルートノード管理機能オブジェクトの概念図
【図４】文字ノードオブジェクトの概念図
【図５】文字ノードオブジェクトの概念図
【図６】文字ノードオブジェクトの概念図
【図７】文字ノードオブジェクトの概念図
【図８】文字ノードオブジェクトの概念図
【図９】文字ノードオブジェクトの概念図
【図１０】図４乃至図９に示した文字ノードオブジェクトのリンク状態を模式的に示す概略図
【図１１】失敗遷移機能オブジェクトの概念図
【図１２】パターン登録処理の流れを示す図
【図１３】パターン登録処理の流れを示す図
【図１４】パターン登録処理の流れを示す図
【図１５】失敗遷移先構築処理の流れを示す図
【図１６】失敗遷移先構築処理の流れを示す図
【図１７】文字列探索処理の流れを示す図
【図１８】文字列探索処理の流れを示す図
【符号の説明】
【０１２０】
１０ 文字列探索装置
１０ｃ ＨＤＤ
１０ｄ ＣＰＵ
１０ｅ ＤＲＡＭ
１１ テキストデータ
１２ アプリケーション
１３ 文字列探索ソフトウエア
１３ｂ 文字列探索オートマトンライブラリ
１３ｃ ルートノード管理機能ライブラリ
１３ｄ 文字ノードライブラリ
１３ｅ 失敗遷移機能ライブラリ
１３ｆ パターン登録プログラム
１３ｇ 失敗遷移先構築プログラム
１３１ 文字列探索オートマトンオブジェクト
１３２ ルートノード管理機能オブジェクト
１３３ 文字ノードオブジェクト
１３４ 失敗遷移機能オブジェクト
【技術分野】
【０００１】
本発明は、目的の文字列（パターン）がテキスト中のどこにあるかを探索するための文字列探索装置に対して任意の文字列を登録する方法と、そのような文字列登録方法を実現する装置としてコンピュータを動作させる文字列登録プログラムと、そのような文字列登録プログラムが実現する機能と同等の機能が組み込まれた文字列探索装置とに、関する。
【背景技術】
【０００２】
周知のように、長い文章の中から所定のキーワードがある箇所を探したり、ＤＮＡ［Doexyribo Nucleic Acid］を構成する塩基配列を示したテキストの中から所定の組み合わせがある箇所を探したりするため、文字列探索という技術がある。
【０００３】
文字列探索には、ラビン＝カープ（ＲＫ）などの力任せ系のアルゴリズム、或いは、クヌース＝モリス＝プラット（ＫＭＰ）やボイヤー＝ムーア（ＢＭ）などのスキップ系アルゴリズムが、知られており、このうち、スキップ系に属するエイホ＝コラシック（ＡＣ）アルゴリズムは、目的の文字列が複数ある場合でも一度の走査で探索を終了できるものとして、知られている。
【０００４】
特許文献１及び特許文献２並びに非特許文献１には、そのＡＣアルゴリズムに従った文字列探索オートマトン（コンピュータ上で実現された機能）の動作についての解説がある。ＡＣアルゴリズムに従った文字列探索オートマトンは、探索されるべき目的文字列を利用者から事前に受け付けておき、探索対象となるテキストが指定されたときには、そのテキストの先頭から一文字ずつ順に取り出しながら、状態遷移関数（goto関数）と失敗関数（failure関数）とに従って、その取り出した文字と取り出した時の内部状態とに応じて内部状態を変化させたり初期状態に戻したりし、内部状態が最終状態に到達したときに、出力関数に従って、その最終状態に対して事前に対応付けられた文字列を出力するというものである。
【０００５】
なお、より具体的には、文字列探索オートマトンは、状態遷移関数や失敗関数の入力値（次の文字）と出力値（遷移すべき内部状態）との対応関係を定義したテーブルを内蔵する文字ノードを、探索されるべき目的文字列を構成する文字ごとに、有している。そして、内部状態とは、何れか一つの文字ノードを参照対象にしている状態を言い、探索されるべき目的文字列の登録とは、これら文字ノードのリンク関係を上記テーブルに定義することを言う。
【０００６】
このＡＣアルゴリズムは、仮名や漢字を含む日本語テキストに対しても有効なものである。従って、仮名や漢字を含む文字列を事前に登録しておけば、その種の文字列が探索対象テキストから確実に探索されることとなる。
【０００７】
【特許文献１】特開平０９−１９８３９８号公報（段落００１７〜００２０）
【特許文献２】特開２００４−０３０６８２号公報（段落０００３，０００４）
【非特許文献１】広瀬健他監訳、「コンピュータ基礎理論ハンドブック（第１巻）アルゴリズムと複雑さ」、丸善株式会社、平成６年３月、２８０頁〜２８４頁
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、漢字の中には、標準的な字形の代わりに、簡略化や一部置換などが施された字形で表すことができるものがある。このように同じ意味を持ちながら少しずつ字形の異なる文字は、異体字と称されているが、一般的には、幾つかの異体字の中の一種類が、通用の字体として利用されている。但し、人名や地名などにおいては、通用されていない異体字を持って正式な名称とされているものもある。従って、文字列探索の対象となるテキストにも、そのような通用されていない字体の文字を含む文字列が使用されている可能性がある。
【０００９】
前述したようなＡＣアルゴリズムに従った従来の文字列探索オートマトンにおいて、通用される字体の文字のみからなる文字列（例えば、渡辺）とは別に、通用されていない字体の文字を含む文字列（渡邉，渡邊）をも探索できるようにしておくためには、何れの文字列とも、事前に登録しておかねばならない。
【００１０】
しかしながら、通用される字体の文字のみからなる文字列に、更に、通用されていない字体の文字を含む文字列をも登録しておくようにすると、辞書の容量が膨大となってしまい、探索速度が遅くなってしまうという問題が生ずる。
【００１１】
本発明は、前述したような従来技術の有する問題点に鑑みてなされたものであり、その課題は、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を、何れも、探索されるべき目的文字列として登録する場合でも、できるだけ辞書の容量の増加を抑え、その結果として、探索速度の低下をできるだけ抑えることにある。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために案出された文字列登録方法は、エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録方法であって、登録対象として指定された文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成手順，前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手順，及び、前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手順からなることを、特徴としている。
【００１３】
また、上記の課題を解決するために案出された文字列登録プログラムは、エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録プログラムであって、コンピュータを、探索されるべき文字列を登録する指示を入力装置を通じて利用者から受け付ける受付手段，前記受付手段が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、メモリ上に生成する文字ノード生成手段，前記文字ノード生成手段がメモリ上に生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手段，及び、前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手段として機能させることを、特徴としている。
【００１４】
また、上記の課題を解決するために案出された文字列探索装置は、エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置であって、探索されるべき文字列を登録する指示を利用者から受け付ける受付部，前記受付部が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成部，前記文字ノード生成部が生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義部，及び、前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義部を備えることを、特徴としている。
【００１５】
これらのように、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を登録する場合に、異体字を持つ文字の直前の文字の文字ノードオブジェクトにおいて、その次文字がどの異体字であっても一個の文字ノードオブジェクトの所在情報に対応付けられるようにすれば、異体字の数と同数の組数の文字ノードオブジェクトを用意しなくても、一個の文字ノードオブジェクトで、異体字を含む文字列が全て探出されるようになる。これにより、異体字の文字ノードオブジェクトを用意せずに済む分だけ、辞書の容量の増加が抑えられることとなる。
【００１６】
なお、前述した本発明は、更に、文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトの所在情報とその文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものとを対応付けてテーブルに格納しておいて（候補生成手順）、文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものの末尾から一文字ずつ削除するごとに、削除後の文字群で前記テーブルを検索する処理，及び、何れかの検索によりそのテーブルからレコードが検出できたときに、その文字群の先頭文字を示す文字情報と、そのレコード内の所在情報とを対応付けて記録する処理を行う（失敗遷移先構築手順）ものであっても良い。
【００１７】
これらの処理を行うようにすれば、文字ノードオブジェクトに失敗遷移の遷移先を簡単に登録することができるようになる。
【００１８】
また、本発明に対し、前述したような手順を追加したものとした場合において、失敗遷移先構築手順で行う削除処理の結果、逆順に並び替えた文字群が残り一文字となったときには、その残りの一文字に対し、登録された文字列における先頭文字の文字ノード（ルートノード）を対応付けて、失敗遷移先として登録しておくと良い。こうすると、失敗遷移後の遷移ステップ数が従来技術に比して減ることとなるため、文字列探索の速度が向上することとなる。
【発明の効果】
【００１９】
従って、本発明によれば、互いの相違点が内部の文字を異体字に変えただけの複数の文字列を、何れも、探索されるべき目的文字列として登録する場合でも、辞書の容量の増加を抑えることができ、その結果として、探索速度の低下を抑えることができるようになる。
【発明を実施するための最良の形態】
【００２０】
次に、本発明を実施するための最良の形態について、添付図面を参照しながら、詳細に説明する。
【００２１】
先ず、本実施形態の文字列探索装置の構成について説明する。
【００２２】
図１は、本実施形態の文字列探索装置１０の構成図である。
【００２３】
図１に示すように、文字列探索装置１０は、後述のプログラム群及びデータ群を一般的なパーソナルコンピュータに導入してなる装置である。この文字列探索装置１０を構成するパーソナルコンピュータは、周知のように、液晶ディスプレイ等の表示装置１０ａ，キーボードやマウス等の入力装置１０ｂ，及び、これら装置１０ａ，１０ｂが接続された本体とからなり、その本体は、ＨＤＤ［Hard Disk Drive］１０ｃ，ＣＰＵ［Central Processing Unit］１０ｃ，ＤＲＡＭ［Dynamic Random Access Memory］１０ｅ，その他のハードウエアを、内蔵している。このうち、ＨＤＤ１０ｃは、各種のプログラムやデータを記憶する記憶装置であり、ＣＰＵ１０ｄは、そのＨＤＤ１０ｃ内のプログラムに従って各種の処理を行う制御装置であり、ＤＲＡＭ１０ｅは、ＣＰＵ１０ｄがプログラムに従った処理を行う際に作業領域が展開される揮発性記憶装置である。
【００２４】
そして、この文字列探索装置１０のＨＤＤ１０ｃには、テキストデータ１１，アプリケーション１２，及び、文字列探索ソフトウエア１３が、格納されている。テキストデータ１１は、テキストを表示するためのテキストデータである。なお、本実施形態では、このテキストデータ１１には、仮名や漢字を含む日本語の文章を表示するためのテキストデータが含まれている。アプリケーション１２は、テキストデータ１１に基づいてテキストを表示装置１０ａに表示したりそのテキストの編集及び保存をするための機能を提供したりするためのソフトウエアである。文字列探索ソフトウエア１３は、そのアプリケーション１２からの要求を受けてテキストの中から所定の文字列を探索してその探索結果をアプリケーション１２に応答するためのソフトウエアである。
【００２５】
図２は、文字列探索ソフトウエア１３の内部構成とこれににより実現される機能とを示す概略図である。
【００２６】
図２に示すように、文字列探索ソフトウエア１３は、オブジェクト生成プログラム１３ａ，文字列探索オートマトンライブラリ１３ｂ，ルートノード管理機能ライブラリ１３ｃ，文字ノードライブラリ１３ｄ，失敗遷移機能ライブラリ１３ｅ，パターン登録プログラム１３ｆ，及び、失敗遷移先構築プログラム１３ｇを、含んでいる。
【００２７】
このうち、オブジェクト生成プログラム１３ａは、各ライブラリ１３ｂ〜１３ｅに基づいて、それぞれに対応するオブジェクトをＤＲＡＭ１０ｅ上に生成するためのプログラムである。なお、各オブジェクトの生成時において、各オブジェクトには、ＤＲＡＭ１０ｅ上の所定の大きさの領域が個別に割り当てられるようになっている。
【００２８】
また、文字列探索オートマトンライブラリ１３ｂは、事前に登録されている文字列を対象テキストの中から探索する機能を実現するオブジェクト１３１をＤＲＡＭ１０ｅ上に生成するためのライブラリである。図２には、このライブラリ１３ｂに基づいてＤＲＡＭ１０ｅ上に生成される文字列探索オートマトンオブジェクト１３１が、示されている。この文字列探索オートマトンオブジェクト１３１は、後述のオブジェクト１３２〜１３４を使用することによって、対象テキストの中から文字列を探索する。なお、文字列探索オートマトンライブラリ１３ｂは、各オブジェクト１３２〜１３４に割り当てられたＤＲＡＭ１０ｅ上領域のアドレスによって、使用すべきオブジェクトを特定する。この文字列探索オートマトンオブジェクト１３１が実行する文字列探索処理の内容については、図１７及び図１８を用いて後述する。
【００２９】
また、ルートノード管理機能ライブラリ１３ｃは、ルートノード管理機能オブジェクト１３２を生成するためのライブラリである。ルートノード管理機能オブジェクト１３２は、文字列探索オートマトンライブラリ１３ｂが対象テキストの中から一文字ずつ取り出したときにおいて、その取り出した文字が探索されるべき文字列の先頭文字であるか否かを判定する際に利用されるオブジェクトである。
【００３０】
図３は、このルートノード管理機能オブジェクト１３２の概念図である。
【００３１】
図３に示すように、ルートノード管理機能オブジェクト１３２は、ルートノード管理テーブル１３２ａを含んでいる。ルートノード管理テーブル１３２ａは、文字列探索オートマトンライブラリ１３ｂが処理対象としている文字が何れかの文字列の先頭文字であるか否かを検索する際に利用されるテーブルであり、探索されるべき各文字列の先頭文字が登録されている。より具体的には、このルートノード管理テーブル１３２ａ内の各レコードは、「文字」及び「ポインタ」の各フィールドを有しており、このうち、「文字」フィールドには、探索されるべき文字列の先頭文字が記録され、「ポインタ」フィールドには、その先頭文字に対応する後述の文字ノードオブジェクト１３３のアドレスが記録される。なお、これ以降において、先頭文字に対応する文字ノードオブジェクト１３３を、先頭でない文字に対応する文字ノードオブジェクト１３３と区別する必要がある場合、「ルートノードオブジェクト」と表記する。
【００３２】
また、図２の文字ノードライブラリ１３ｄは、ＤＲＡＭ１０ｅ上に文字ノードオブジェクト１３３を生成するためのライブラリである。この文字ノードライブラリ１３ｄは、複数存在し、ＤＲＡＭ１０ｅ上には、それら文字ノードライブラリ１３ｄ一つ一つに対応する文字ノードオブジェクト１３３が複数生成される。文字ノードオブジェクト１３３は、原則として、探索されるべき各文字列を構成する文字のそれぞれについて、生成される。但し、各文字列において、先頭文字から途中の文字までの文字の並びが共通する場合、それら共通する部分の文字に対応する文字ノードオブジェクト１３３は、共通のものが一つ生成される。例えば、「河原崎」と「河原田」という二つの文字列においては、「河原」が共通するので、この場合、「河」と「原」の文字ノードオブジェクト１３３は、「河原崎」と「河原田」とに共通するものとして一組生成される。なお、この場合において、例えば「原田」という文字列が探索されるべきものとして登録されているときには、その「原田」の「原」の文字ノードオブジェクト１３３は、「河原」の「原」の文字ノードオブジェクト１３３とは別途、存在する。文字ノードオブジェクト１３３は、そのオブジェクト１３３が対象テキストの中から取り出された一文字に対応するオブジェクトである場合において、その取り出された文字の次の文字が、次にくるべき文字（その文字を含む文字列内でのその文字の次に存在すべき文字）であるか否かを判別する際に利用されるオブジェクトである。
【００３３】
図４乃至図９は、この文字ノードオブジェクト１３３の概念図である。なお、図４乃至図９のうち、図４及び図８は、ルートノードオブジェクトを示している。
【００３４】
図４乃至図９に示すように、文字ノードオブジェクト１３３は、経緯情報１３３ａ，ハッシュマップテーブル１３３ｂ，及び、失敗時遷移先管理テーブル１３３ｃを、含んでいる。経緯情報１３３ａは、その文字ノードオブジェクト１３３に対応する文字を含む文字列における先頭文字からその文字までの文字群を示す情報である。例えば、「勅使河原」という文字列において、「河」の文字ノードオブジェクト１３３であれば、経緯情報１３３ａが示す文字群は、「勅使河」である（図６参照）。ハッシュマップテーブル１３３ｂは、文字列探索オートマトンオブジェクト１３１が探索対象から取り出した一文字（処理対象文字）が、その文字ノードオブジェクト１３３に対応する文字を含む文字列におけるその文字の次の文字と、一致するか否かを判断する際に利用されるテーブルである。具体的には、このハッシュマップテーブル１３３ｂ内の各レコードは、「文字」及び「ポインタ」の各フィールドを有しており、このうち、「文字」フィールドには、経緯情報１３３ａが示す文字群の次に存在し得る文字が記録され、「ポインタ」フィールドには、その文字に対応する文字ノードオブジェクト１３３のアドレスが記録される（図５及び図８参照）。失敗時遷移先管理テーブル１３３ｃは、処理対象文字がハッシュマップテーブル１３３ｂから検索されなかったときに使用されるテーブルである。具体的には、この失敗時遷移先管理テーブル１３３ｃ内の各レコードも、「文字」及び「ポインタ」の各フィールドを有しており、「文字」フィールドには、この文字ノードオブジェクト１３３に対応する文字と同じ文字が記録され、「ポインタ」フィールドには、同じ文字が対応付けられている別の文字ノードオブジェクト１３３のアドレスが記録される。さらに、文字ノードオブジェクト１３３の中には、終端情報１３３ｄを含むものもある。終端情報１３３ｄは、経緯情報１３３ａの示す文字群だけで、探索されるべき文字列が成立する場合に、その旨を示す情報である。
【００３５】
ここで、図１０は、図４乃至図９に示した文字ノードオブジェクト１３３のリンク状態を模式的に示す概略図である。
【００３６】
図１０では、丸で囲まれた文字が文字ノードを示しており、これら文字ノードうち、図１０において最も左側にある「勅」，「使」，「河」，「原」がルートノードとして示されている。なお、ルートノードは、ルートノード管理機能オブジェクト１３２のルートノード管理テーブル１３２ａに定義されている。そして、これらルートノードを起点として、「勅使河原」，「勅使川原」，「勅使ケ原」，「勅使」，「使河」，「河原」，「河原田」，「河原崎」，「河野」，「河合」，「河村」，「原田」，「原口」の文字列のリンク状態が、実線で示されている。なお、これら実線で示されるリンク状態は、各文字ノードオブジェクト１３３のハッシュマップテーブル１３３ｂにて定義されている。また、この図１０において、波線は、その文字を含む文字列（例えば「勅使河原」）における先頭以外の文字からその文字までの文字群（例えば「使河」）で別途文字列が成立している場合に、その別の文字列（「使河」）における対応する文字ノード（河）への遷移を、示している。また、一点鎖線は、その文字ノードの前方（図１０の右方）に遷移すべき文字ノードが無く、且つ、同一の文字に対応付けられている別の文字ノードへの遷移（波線で示される遷移）もできない場合の遷移方向を、示している。なお、これら波線及び一点鎖線で示されるリンク状態は、各文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに定義されており、本発明は、これら波線及び一点鎖線で示される遷移先を文字ノードオブジェクト１３３に簡単に登録できる手段について、提供するものである。
【００３７】
また、図２の失敗遷移機能ライブラリ１３ｅは、ＤＲＡＭ１０ｅ上に失敗遷移機能オブジェクト１３４を生成するためのライブラリである。失敗遷移機能オブジェクト１３４は、後述の失敗遷移先構築プログラム１３ｇによる処理において使用される情報を記録しておくためのオブジェクトである。
【００３８】
図１１は、この失敗遷移機能オブジェクト１３４の概念図である。
【００３９】
図１１に示すように、失敗遷移機能オブジェクト１３４は、遷移先候補管理テーブル１３４ａを含んでいる。遷移先候補管理テーブル１３４ａは、後述の失敗遷移先構築プログラム１３ｇによる処理において使用される情報を記録しておくためのテーブルである。具体的には、この遷移先候補管理テーブル１３４ａ内の各レコードは、「文字」及び「ポインタ」の各フィールドを有しており、このうち、「文字」フィールドには、経緯情報１３３ａを示す文字群を逆順にしたものが記録され、「ポインタ」フィールドには、その経緯情報１３３ａを持つ文字ノードオブジェクト１３３のアドレスが記録される。
【００４０】
図２のパターン登録プログラム１３ｆは、文字列探索オートマトンオブジェクト１３１に探索させる文字列を登録する機能を実現するためのプログラムである。なお、この文字列の登録とは、具体的には、文字ノードオブジェクト１３３のリンク関係を、各文字ノードオブジェクト１３３のハッシュマップテーブル１３３ｂに定義することである。このパターン登録プログラム１３ｆに従ってＣＰＵ１０ｄが実行する処理の内容については、図１２乃至図１４を用いて後述する。
【００４１】
図２の失敗遷移先構築プログラム１３ｇは、各文字ノードオブジェクト１３３において前方遷移（図１０の実線で示す遷移）ができないときに別途検索される遷移先を登録するためのプログラムである。なお、この遷移先の登録とは、具体的には、文字ノードオブジェクト１３３のリンク関係を、各文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに定義することである。この失敗遷移先構築プログラム１３ｇに従ってＣＰＵ１０ｄが実行する処理の内容については、図１５及び図１６を用いて後述する。
【００４２】
次に、本実施形態の文字列探索装置１０において実行される処理について、説明する。
【００４３】
文字列探索装置１０では、所定の時期（起動時或いは実行指示時）に文字列探索ソフトウエア１３が起動され、オブジェクト生成プログラム１３ａによってＤＲＡＭ１０ｅ上に各オブジェクト１３１〜１３４が生成されるようになっている。これにより、各オブジェクト１３１〜１３４が常駐した状態になる。
【００４４】
このような状態において、文字列探索装置１０の入力装置１０ｂを操作する操作者によって、探索されるべき文字列が登録対象として指定された後、パターン登録プログラム１３ｆが起動されると、パターン登録処理が開始される。
【００４５】
図１２乃至図１４は、このパターン登録処理の流れを示す図である。
【００４６】
パターン登録処理の開始後、最初のステップＳ１００１では、ＣＰＵ１０ｄは、登録対象として指定された文字列の先頭文字を検索条件として、図３のルートノード管理テーブル１３２ａを検索する処理を行う。
【００４７】
次のステップＳ１００２では、ＣＰＵ１０ｄは、当該文字列の先頭文字と同一の文字を含むレコードがルートノード管理テーブル１３２ａから検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字列の先頭文字と同一の文字を含むレコードがルートノード管理テーブル１３２ａから検出できなかった場合には、ステップＳ１００２からステップＳ１００３へ処理を進め、当該文字列の先頭文字と同一の文字を含むレコードがルートノード管理テーブル１３２ａから検出できた場合には、ステップＳ１００２から処理を分岐させ、ステップＳ１００４へ処理を進める。
【００４８】
ステップＳ１００３では、ＣＰＵ１０ｄは、ルートノードを生成する処理を行う。具体的には、ＣＰＵ１０ｄは、登録対象として指定された文字列の先頭文字に対応する文字ノードライブラリ１３ｄを生成してＨＤＤ１０ｃに保存する処理を行うとともに、オブジェクト生成プログラム１３ａによる機能を通じてその先頭文字に対応する文字ノードオブジェクト１３３をＤＲＡＭ１０ｅ上に生成する処理を行う。さらに、ＣＰＵ１０ｄは、その生成した文字ノードオブジェクト１３３のアドレスとこれに対応する文字とを含むレコードを図３のルートノード管理テーブル１３２ａに新規追加する処理を行う。これにより、生成された文字ノードオブジェクト１３３は、ルートノードオブジェクトとして設定されることとなる。ＣＰＵ１０ｄは、このような処理を行った後、ステップＳ１００４へ処理を進める。
【００４９】
ステップＳ１００４では、ＣＰＵ１０ｄは、ステップＳ１００１で検出したレコード内のアドレスにより示される領域にあるルートノードオブジェクト１３３，又は、ステップＳ１００３でルートノード管理テーブル１３２ａに登録したルートノードオブジェクト１３３を、処理対象ノードとして特定する。
【００５０】
次のステップＳ１００５では、ＣＰＵ１０ｄは、登録対象に指定された文字列の中から未処理の文字を検索する処理を行う。
【００５１】
次のステップＳ１００６では、ＣＰＵ１０ｄは、当該文字列から未処理の文字が検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字列から未処理の文字が検出できた場合、ステップＳ１００６から処理を分岐させ、ステップＳ１００７へ処理を進める。
【００５２】
ステップＳ１００７では、ＣＰＵ１０ｄは、未処理の文字のうち、先頭側の一つを処理対象文字として特定する。
【００５３】
次のステップＳ１００８では、ＣＰＵ１０ｄは、処理対象文字を検索条件として、処理対象ノードのハッシュマップテーブル１３３ｂを検索する処理を行う。
【００５４】
次のステップＳ１００９では、ＣＰＵ１０ｄは、処理対象文字と同一の文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、処理対象文字と同一の文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できなかった場合には、次文字ノード生成処理（ステップＳ１０１０乃至Ｓ１０１２）を実行し、処理対象文字と同一の文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できた場合には、ステップＳ１００９から処理を分岐させ、ステップＳ１０１４へ処理を進める。
【００５５】
次文字ノード生成処理の最初のステップＳ１０１０では、ＣＰＵ１０ｄは、登録対象として指定された文字列の先頭から処理対象文字までの文字群を、逆順に並べ替える処理を行う。
【００５６】
次のステップＳ１０１１では、ＣＰＵ１０ｄは、処理対象文字に対応する文字ノードを生成する処理を行う。具体的には、処理対象文字に対応する文字ノードライブラリ１３ｄを生成してＨＤＤ１０ｃに保存する処理を行うとともに、オブジェクト生成プログラム１３ａによる機能を通じてその先頭文字に対応する文字ノードオブジェクト１３３をＤＲＡＭ１０ｅ上に生成する処理を行う。ここで、生成される文字ノードオブジェクト１３３には、ステップＳ１０１０で逆順に並び替えられる前の文字群が、経緯情報１３３ａとして格納されるようになっている。なお、このステップＳ１０１１は、前述した文字ノード生成手順に相当し、このステップＳ１０１１を実行するＣＰＵ１０ｄは、前述した文字ノード生成手段及び文字ノード生成部に相当している。
【００５７】
次のステップＳ１０１２では、ＣＰＵ１０ｄは、ステップＳ１０１０で逆順に並び替えられた文字群と、ステップＳ１０１１で生成した文字ノードオブジェクト１３３のアドレスとを含むレコードを、図１１の遷移先候補管理テーブル１３４ａに新規登録する処理を行う。なお、このステップＳ１０１２は、前述した候補生成手順に相当している。
【００５８】
次のステップＳ１０１３では、ＣＰＵ１０ｄは、以上に説明した次文字ノード生成処理（ステップＳ１０１０乃至Ｓ１０１２）により生成した文字ノードオブジェクト１３３に対応するレコードを、処理対象ノードのハッシュマップテーブル１３３ｂに登録する処理を行う。なお、このステップＳ１０１３は、前述した前方リンク定義手順に相当し、このステップＳ１０１３を実行するＣＰＵ１０ｄは、前述した前方リンク定義手段及び前方リンク定義部に相当している。その後、ＣＰＵ１０ｄは、ステップＳ１０１４へ処理を進める。
【００５９】
ステップＳ１０１４では、ＣＰＵ１０ｄは、ステップＳ１００８で検出したレコード内のアドレス，又は、次文字ノード生成処理で生成した文字ノードオブジェクト１３３のアドレスを、取得する処理を行う。
【００６０】
次のステップＳ１０１５では、ＣＰＵ１０ｄは、処理対象文字の異体字を検索する処理を行う。なお、このステップＳ１０１５では、ＣＰＵ１０ｄは、例えば図示せぬ日本語入力支援ソフトウエアが有する辞書を検索する。
【００６１】
次のステップＳ１０１６では、ＣＰＵ１０ｄは、処理対象文字の異体字が検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、処理対象文字の異体字が検出できた場合には、第１の処理ループＬ１を実行し、処理対象文字の異体字が検出できなかった場合には、ステップＳ１０１６から処理を分岐させ、ステップＳ１０１８へ処理を進める。
【００６２】
第１の処理ループＬ１では、ＣＰＵ１０ｄは、検出された異体字のそれぞれについて、ステップＳ１０１７を実行する。
【００６３】
ステップＳ１０１７では、ＣＰＵ１０ｄは、処理対象の異体字と、処理対象文字に対応する文字ノードオブジェクト１３３のアドレスとを含むレコードを、処理対象ノードのハッシュマップテーブル１３３ｂに新規追加する処理を行う。なお、このステップＳ１０１７は、前述した異体字リンク定義手順に相当し、このステップＳ１０１７を実行するＣＰＵ１０ｄは、前述した異体字リンク定義手段及び異体字リンク定義部に相当している。
【００６４】
ＣＰＵ１０ｄは、このステップＳ１０１７を、ステップＳ１０１５で検出された異体字の全てについて実行した後、この第１の処理ループＬ１から離脱し、ステップＳ１０１８へ処理を進める。
【００６５】
ステップＳ１０１８では、ＣＰＵ１０ｄは、処理対象ノードを、ステップＳ１０１４で取得したアドレスが示す領域にある文字ノードオブジェクト１３３に、変更する処理を行う。その後、ＣＰＵ１０ｄは、ステップＳ１００５へ処理を戻す。
【００６６】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ１００５乃至Ｓ１０１８を繰り返し行う間に、登録対象として指定された文字列から未処理の文字が検出できなくなったときには、ステップＳ１００６からステップＳ１０１９へ処理を進める。
【００６７】
ステップＳ１０１９では、ＣＰＵ１０ｄは、処理対象ノードに終端情報１３３ｄを記録する処理を行い、その後、図１２乃至図１４に係るパターン登録処理を終了する。
【００６８】
このようなパターン登録処理が繰り返されることにより、探索されるべき文字列が複数登録された後、文字列探索装置１０の入力装置１０ｂを操作する操作者によって、失敗遷移先構築プログラム１３ｇが起動されると、失敗遷移先構築処理が開始される。
【００６９】
図１５及び図１６は、失敗遷移先構築処理の流れを示す図である。
【００７０】
失敗遷移先構築処理の開始後、最初のステップＳ２００１では、ＣＰＵ１０ｄは、図３のルートノード管理テーブル１３２ａからアドレスを順に読み出して、ＤＲＡＭ１０ｅ内に事前に確保した第１のスタックに記録する処理を行う。この処理により、第１のスタックには、ルートノード管理テーブル１３２ａ内の全てのアドレスが、読み出されることとなる。
【００７１】
次のステップＳ２００２では、ＣＰＵ１０ｄは、第１のスタックの中から末尾のアドレスを一つ取り出す処理を行う。
【００７２】
次のステップＳ２００３では、ＣＰＵ１０ｄは、ステップＳ２００２で取り出したアドレスが示す領域にある文字ノードオブジェクト１３３のハッシュマップテーブル１３３ｂからアドレスを順に読み出して、ＤＲＡＭ１０ｅ内に事前に確保した第２のスタックに記録する処理を行う。この処理により、第２のスタックには、ハッシュマップテーブル１３３ｂ内の全てのアドレスが、読み出されることとなる。
【００７３】
次のステップＳ２００４では、ＣＰＵ１０ｄは、第２のスタックの中から末尾のアドレスを一つ取り出す処理を行う。
【００７４】
次のステップＳ２００５では、ＣＰＵ１０ｄは、ステップＳ２００４で取り出したアドレスにある文字ノードオブジェクト１３３の経緯情報１３３ａを読み出し、この経緯情報１３３ａの示す文字群を逆順に並べ替える処理を行う。
【００７５】
次のステップＳ２００６では、ＣＰＵ１０ｄは、当該文字群から末尾の一文字を除去する処理を行う。
【００７６】
次のステップＳ２００７では、ＣＰＵ１０ｄは、ステップＳ２００６での除去によって当該文字群の文字が残り一文字になったか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字群が二文字以上からなる場合、ステップＳ２００７から処理を分岐させ、ステップＳ２００８へ処理を進める。
【００７７】
ステップＳ２００８では、ＣＰＵ１０ｄは、当該文字群を検索条件として、図１１の遷移先候補管理テーブル１３４ａを検索する処理を行う。
【００７８】
次のステップＳ２００９では、ＣＰＵ１０ｄは、当該文字群と同じ文字群を含むレコードが遷移先候補管理テーブル１３４ａから検出できたか否かを、判別する。そして、ＣＰＵ１０ｄは、当該文字群と同じ文字群を含むレコードが遷移先候補管理テーブル１３４ａから検出できなかった場合、ステップＳ２００９から処理を分岐させ、ステップＳ２００６へ処理を戻す。
【００７９】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ２００６乃至Ｓ２００９を繰り返し行う間に、当該文字群と同じ文字群を含むレコードが遷移先候補管理テーブル１３４ａから検出できたときには、ステップＳ２００９からステップＳ２０１０へ処理を進める。
【００８０】
ステップＳ２０１０では、ＣＰＵ１０ｄは、ステップＳ２００８で検出されたレコード内のアドレスと、当該文字群の先頭の文字とを含むレコードを、ステップＳ２００４で取り出したアドレスが示す領域にある文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに新規追加する処理を行う。
【００８１】
次のステップＳ２０１１では、ＣＰＵ１０ｄは、ステップＳ２０１０で失敗時遷移先管理テーブル１３３ｃに登録されたアドレスを、第２のスタックに格納する処理を行う。その後、ＣＰＵ１０ｄは、ステップＳ２０１３へ処理を進める。
【００８２】
また、ＣＰＵ１０ｄは、ステップＳ２００６乃至Ｓ２００９を繰り返し行う間に、当該文字群が残り一文字になってしまったときには、ステップＳ２００７からステップＳ２０１２へ処理を進める。
【００８３】
ステップＳ２０１２では、ＣＰＵ１０ｄは、当該一文字に対応するルートノードオブジェクト１３３のアドレスを、図１１の遷移先候補管理テーブル１３４ａから読み出し、続いて、当該一文字と当該アドレスとを含むレコードを、ステップＳ２００４で取り出したアドレスが示す領域にある文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃに新規追加する処理を行う。その後、ＣＰＵ１０ｄは、ステップＳ２０１３へ処理を進める。
【００８４】
ステップＳ２０１３では、ＣＰＵ１０ｄは、第２のスタックを検索する処理を行う。
【００８５】
次のステップＳ２０１４では、ＣＰＵ１０ｄは、第２のスタックからアドレスが検出できたか否かを、判別する処理を行う。そして、ＣＰＵ１０ｄは、第２のスタックからアドレスが検出できた場合、ステップＳ２０１４から処理を分岐させ、ステップＳ２００４へ処理を戻す。
【００８６】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ２００４乃至Ｓ２０１４を繰り返す間に、第２のスタックからアドレスが検出できなくなったときには、ステップＳ２０１３からステップＳ２０１５へ処理を進める。
【００８７】
ステップＳ２０１５では、ＣＰＵ１０ｄは、第１のスタックを検索する処理を行う。
【００８８】
次のステップＳ２０１６では、ＣＰＵ１０ｄは、第１のスタックからアドレスが検出できたか否かを、判別する処理を行う。そして、ＣＰＵ１０ｄは、第１のスタックからアドレスが検出できた場合、ステップＳ２０１６から処理を分岐させ、ステップＳ２００２へ処理を戻す。
【００８９】
そして、ＣＰＵ１０ｄは、以上に説明したステップＳ２００２乃至Ｓ２０１６を繰り返す間に、第１のスタックからアドレスが検出できなくなったときには、図１４及び図１５に係る失敗遷移先構築処理を終了する。
【００９０】
このような失敗遷移先構築処理が行われることにより、探索すべき文字列が複数登録された際に生成された文字ノードオブジェクト１３３の失敗時遷移先管理テーブル１３３ｃの内容が、生成され、図１０において波線や一点鎖線で示すようなリンク構造が構築されることとなる。なお、この図１４及び図１５に係る失敗遷移先構築処理は、前述した失敗遷移先構築手順に相当している。
【００９１】
また、ＤＲＡＭ１０ｅ上に各オブジェクト１３１〜１３４が存在している状態において、文字列探索オートマトンオブジェクト１３１が、アプリケーション１２から、所定のテキストを探索対象とした指定とともに、文字列の探索の依頼を受けると、文字列探索処理を開始する。
【００９２】
図１７及び図１８は、文字列探索処理の流れを示す図である。
【００９３】
文字列探索処理の開始後、最初のステップＳ３００１では、文字列探索オートマトンオブジェクト１３１（を実現しているＣＰＵ１０ｄ）は、探索対象テキストから未処理で先頭側の一文字を読み出す処理を行う。
【００９４】
次のステップＳ３００２では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００１で読み出した文字を検索条件として、図３のルートノード管理テーブル１３２ａを検索する処理を行う。
【００９５】
次のステップＳ３００３では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００１で読み出した文字と同じ文字を含むレコードがルートノード管理テーブル１３２ａから検出できたか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００１で読み出した文字と同じ文字を含むレコードがルートノード管理テーブル１３２ａから検出できなかった場合には、ステップＳ３００３から処理を分岐させてステップＳ３００１へ処理を戻し、ステップＳ３００１で読み出した文字と同じ文字を含むレコードがルートノード管理テーブル１３２ａから検出できた場合には、ステップＳ３００３からステップＳ３００４へ処理を進める。
【００９６】
ステップＳ３００４では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００２で検出したレコード内のアドレスが示す領域にある文字ノードオブジェクト（ルートノードオブジェクト）１３３を、処理対象ノードに設定する処理を行う。
【００９７】
次のステップＳ３００５では、文字列探索オートマトンオブジェクト１３１は、処理対象ノードに終端情報１３３ｄが含まれているか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、処理対象ノードに終端情報１３３ｄが含まれていた場合には、ステップＳ３００５からステップＳ３００６へ処理を進め、処理対象ノードに終端情報１３３ｄが含まれていなかった場合には、ステップＳ３００５から処理を分岐させてステップＳ３００７へ処理を進める。
【００９８】
ステップＳ３００６では、文字列探索オートマトンオブジェクト１３１は、処理対象モードの経緯情報１３３ａの示す文字群を、探索結果として、アプリケーション１２１（図２参照）に出力する処理を行う。その後、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７へ処理を進める。
【００９９】
ステップＳ３００７では、文字列探索オートマトンオブジェクト１３１は、探索対象テキスト内の未処理の文字の中から先頭側の一文字を読み出す処理を行う。
【０１００】
次のステップＳ３００８では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字を検索条件として、処理対象ノードのハッシュマップテーブル１３３ｂを検索する処理を行う。
【０１０１】
次のステップＳ３００９では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できたか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できた場合、ステップＳ３００９から処理を分岐させ、ステップＳ３０１０へ処理を進める。
【０１０２】
ステップＳ３０１０では、文字列探索オートマトンオブジェクト１３１は、処理対象ノードを、ステップＳ３００８で検出したレコード内のアドレスにある文字ノードオブジェクト１３３に変更する処理を行う。その後、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００５へ処理を戻す。
【０１０３】
一方、ステップＳ３００９において、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できなかった場合、ステップＳ３００９からステップＳ３０１１へ処理を進める。
【０１０４】
ステップＳ３０１１では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字を検索条件として、処理対象ノードの失敗時遷移先管理テーブル１３３ｃを検索する処理を行う。
【０１０５】
次のステップＳ３０１２では、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードの失敗時遷移先管理テーブル１３３ｃから検出できたか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードの失敗時遷移先管理テーブル１３３ｃから検出できた場合、ステップＳ３０１２から処理を分岐させ、ステップＳ３０１３へ処理を進める。
【０１０６】
ステップＳ３０１３では、文字列探索オートマトンオブジェクト１３１は、処理対象ノードを、ステップＳ３０１１で検出したレコード内のアドレスにある文字ノードオブジェクト１３３に変更する処理を行う。その後、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００５へ処理を戻す。
【０１０７】
一方、ステップＳ３０１３において、文字列探索オートマトンオブジェクト１３１は、ステップＳ３００７で読み出した文字と同じ文字を含むレコードが処理対象ノードのハッシュマップテーブル１３３ｂから検出できなかった場合、ステップＳ３０１３からステップＳ３０１４へ処理を進める。
【０１０８】
ステップＳ３０１４では、文字列探索オートマトンオブジェクト１３１は、探索対象テキスト内に未処理の文字が存在するか否かを、判別する。そして、文字列探索オートマトンオブジェクト１３１は、探索対象テキスト内に未処理の文字が存在していた場合には、ステップＳ３０１４から処理を分岐させ、ステップＳ３００１へ処理を戻す。
【０１０９】
文字列探索オートマトンオブジェクト１３１は、以上に説明したステップＳ３００１乃至Ｓ３０１４を繰り返し行う間に、探索対象テキスト内から未処理の文字がなくなると、図１７及び図１８に係る文字列探索処理を終了する。
【０１１０】
次に、本実施形態の文字列探索装置１０の作用及び効果について、説明する。
【０１１１】
文字列探索装置１０の操作者は、図１７及び図１８の文字列探索処理により探索対象テキストから探索されるべき目的文字列を登録する場合、文字列を指定してパターン登録プログラム１３ｆを実行させる。すると、従来技術と同様に、文字列を構成する文字のそれぞれについて、次文字の文字ノードの作成と次文字のハッシュマップテーブルへの登録とが、順に行われる（ステップＳ１００５〜Ｓ１０１３，Ｓ１０１８）。
【０１１２】
そして、このパターン登録処理において、順次処理対象とされる次文字について、異体字が存在していた場合（ステップＳ１０１６）、その異体字も全て、ハッシュマップテーブル１３３ｂに登録される（Ｌ１）。このとき、ハッシュマップテーブル１３３ｂ内で各異体字に対応付けられる文字ノードオブジェクト１３３は、図９に示されるように、全て共通の文字ノードオブジェクト１３３となっている。このため、操作者が登録しようとした文字列が通用される字体のみからなるものだけであったとしても、一部の文字が異体字に置換された文字列が、探索対象テキストに含まれていた場合には、図１７及び図１８の文字列探索処理において、その文字列も必ず探出されることとなる（図１０参照）。例えば、操作者が「渡辺」という文字列を指定してパターン登録プログラム１３ｆを実行すれば、その「渡辺」の文字列が探出されるようになるだけでなく、「渡邉」や「渡邊」も探出されるようになる。
【０１１３】
このように異体字が登録されることにより、異体字の数と同数の文字ノードオブジェクト１３３を用意する必要がなくなり（辺，邉，邊の三つの文字ノードを用意しなくても）、一個の文字ノードオブジェクトだけで文字列の登録が済むようになるので（辺の文字ノードだけで済むので）、異体字が多数あったとしても、文字ノードオブジェクト１３３の個数が増えないこととなる。このため、一部の文字を異体字に置換した文字列をも登録する場合であっても、辞書の容量の増加が抑えられることとなる。
【０１１４】
また、本実施形態の文字列探索装置１０では、探索されるべき文字列を登録し終えた後、失敗遷移先構築プログラム１３ｇを実行することにより、各文字ノードオブジェクト１３３における失敗遷移先の登録が、簡単に行える。
【０１１５】
この失敗遷移先の登録においては、その文字を含む文字列（例えば、勅使河原）のうち先頭文字以外の文字からその文字（河）までの文字群（例えば、使河）と同じ文字構成の別の文字列（使河）が登録されている場合には、従来と同様、その別の文字列（使河）の対応する文字（河）の文字ノードオブジェクト１３３が、前方遷移ができないとき（ハッシュマップテーブル１３３ｂで次文字が検出できないときに）の失敗遷移先として、登録される。
【０１１６】
さらに、本実施形態においては、失敗遷移先として、別の文字列の対応する文字がなかった場合には、同じ文字に対応付けられているルートノードオブジェクト１３３が登録される（ステップＳ２００７；ＹＥＳ，Ｓ２０１２）。
【０１１７】
このように、失敗遷移先として、同じ文字に対応付けられているルートノードオブジェクト１３３が、登録されると、図１７及び図１８の文字列探索処理において、失敗遷移先がなかったときに（ステップＳ３０１２；ＹＥＳ）、従来では、ステップＳ３０１４，Ｓ３００１〜Ｓ３００４を経なければならなかったものが、本実施形態によれば、ステップＳ３０１３だけを経るだけで済むようになる。これにより、失敗遷移処理を行う際のステップ数が従来技術に比して減ることとなるため、文字列探索処理に掛かる時間を短縮できるようになる。
【０１１８】
なお、以上の説明においては、漢字のみからなる文字列を、探索されるべき文字列の例として挙げたが、これに限定されるものではない。例えば、仮名のみからなる文字列であっても、仮名と漢字とが混ざった文字列であっても、仮名と漢字と算用数字とが混ざった文字列であってもよい。何れの場合も、文字列探索装置１０に登録でき、探索対象テキストから探出させることができる。
【図面の簡単な説明】
【０１１９】
【図１】本実施形態の文字列探索装置の構成図
【図２】文字列探索ソフトウエアの内部構成とこれににより実現される機能とを示す概略図
【図３】ルートノード管理機能オブジェクトの概念図
【図４】文字ノードオブジェクトの概念図
【図５】文字ノードオブジェクトの概念図
【図６】文字ノードオブジェクトの概念図
【図７】文字ノードオブジェクトの概念図
【図８】文字ノードオブジェクトの概念図
【図９】文字ノードオブジェクトの概念図
【図１０】図４乃至図９に示した文字ノードオブジェクトのリンク状態を模式的に示す概略図
【図１１】失敗遷移機能オブジェクトの概念図
【図１２】パターン登録処理の流れを示す図
【図１３】パターン登録処理の流れを示す図
【図１４】パターン登録処理の流れを示す図
【図１５】失敗遷移先構築処理の流れを示す図
【図１６】失敗遷移先構築処理の流れを示す図
【図１７】文字列探索処理の流れを示す図
【図１８】文字列探索処理の流れを示す図
【符号の説明】
【０１２０】
１０ 文字列探索装置
１０ｃ ＨＤＤ
１０ｄ ＣＰＵ
１０ｅ ＤＲＡＭ
１１ テキストデータ
１２ アプリケーション
１３ 文字列探索ソフトウエア
１３ｂ 文字列探索オートマトンライブラリ
１３ｃ ルートノード管理機能ライブラリ
１３ｄ 文字ノードライブラリ
１３ｅ 失敗遷移機能ライブラリ
１３ｆ パターン登録プログラム
１３ｇ 失敗遷移先構築プログラム
１３１ 文字列探索オートマトンオブジェクト
１３２ ルートノード管理機能オブジェクト
１３３ 文字ノードオブジェクト
１３４ 失敗遷移機能オブジェクト
【特許請求の範囲】
【請求項１】
エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録方法であって、
登録対象として指定された文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成手順，
前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手順，及び、
前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手順
からなることを特徴とする文字列登録方法。
【請求項２】
前記文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトの所在情報とその文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものとを対応付けて第１のテーブルに格納する候補生成手順，及び、
前記文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものの末尾から一文字ずつ削除するごとに、削除後の文字群で前記テーブルを検索する処理，及び、何れかの検索によりそのテーブルからレコードが検出できたときに、その文字群の先頭文字を示す文字情報と、そのレコード内の所在情報とを対応付けて記録する処理を行う失敗遷移先構築手順
を更に含むことを特徴とする請求項１記載の文字列登録方法。
【請求項３】
前記文字ノード生成手順において生成された前記各文字ノードオブジェクトのうち、登録対象として指定された文字列における先頭の文字に対応する文字ノードオブジェクトの所在情報を、その先頭の文字に対応付けて、ルートノード情報として第２のテーブルに格納するルートノード定義手順
を更に含み、
前記失敗遷移先構築手順において、逆順に並び替えた文字群から一文字ずつ削除することにより残り一文字となった場合に、その残りの一文字が前記第２のテーブル内の何れかの文字と一致するときには、その第２のテーブル内でその文字に対応付けられている所在情報と、当該一文字とを対応付けて、その文字ノードオブジェクトに記録する
ことを特徴とする請求項２記載の文字列登録方法。
【請求項４】
エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録プログラムであって、
コンピュータを、
探索されるべき文字列を登録する指示を入力装置を通じて利用者から受け付ける受付手段，
前記受付手段が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、メモリ上に生成する文字ノード生成手段，
前記文字ノード生成手段がメモリ上に生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手段，及び、
前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手段
として機能させる
ことを特徴とする文字列登録プログラム。
【請求項５】
エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置であって、
探索されるべき文字列を登録する指示を利用者から受け付ける受付部，
前記受付部が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成部，
前記文字ノード生成部が生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義部，及び、
前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義部
を備えることを特徴とする文字列探索装置。
【請求項１】
エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録方法であって、
登録対象として指定された文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成手順，
前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手順，及び、
前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手順
からなることを特徴とする文字列登録方法。
【請求項２】
前記文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトの所在情報とその文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものとを対応付けて第１のテーブルに格納する候補生成手順，及び、
前記文字ノードオブジェクトのそれぞれについて、その文字ノードオブジェクトが持つ経緯情報が示す文字群を逆順に並び替えたものの末尾から一文字ずつ削除するごとに、削除後の文字群で前記テーブルを検索する処理，及び、何れかの検索によりそのテーブルからレコードが検出できたときに、その文字群の先頭文字を示す文字情報と、そのレコード内の所在情報とを対応付けて記録する処理を行う失敗遷移先構築手順
を更に含むことを特徴とする請求項１記載の文字列登録方法。
【請求項３】
前記文字ノード生成手順において生成された前記各文字ノードオブジェクトのうち、登録対象として指定された文字列における先頭の文字に対応する文字ノードオブジェクトの所在情報を、その先頭の文字に対応付けて、ルートノード情報として第２のテーブルに格納するルートノード定義手順
を更に含み、
前記失敗遷移先構築手順において、逆順に並び替えた文字群から一文字ずつ削除することにより残り一文字となった場合に、その残りの一文字が前記第２のテーブル内の何れかの文字と一致するときには、その第２のテーブル内でその文字に対応付けられている所在情報と、当該一文字とを対応付けて、その文字ノードオブジェクトに記録する
ことを特徴とする請求項２記載の文字列登録方法。
【請求項４】
エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置に対し、探索されるべき文字列を登録するための文字列登録プログラムであって、
コンピュータを、
探索されるべき文字列を登録する指示を入力装置を通じて利用者から受け付ける受付手段，
前記受付手段が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、メモリ上に生成する文字ノード生成手段，
前記文字ノード生成手段がメモリ上に生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義手段，及び、
前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義手段
として機能させる
ことを特徴とする文字列登録プログラム。
【請求項５】
エイホ＝コラシックアルゴリズムに従って探索対象テキストの中から文字列の探索を行う文字列探索装置であって、
探索されるべき文字列を登録する指示を利用者から受け付ける受付部，
前記受付部が受け付けた文字列を構成する文字のそれぞれについて、その文字列の先頭からその文字までの文字群を示す経緯情報を保持する文字ノードオブジェクトを、生成する文字ノード生成部，
前記文字ノード生成部が生成した前記文字ノードオブジェクトのそれぞれに対し、その文字ノードオブジェクトが保持する経緯情報が示す文字群の次に存在すべき文字を示す次文字情報と、その次文字情報が示す文字に対応する他の文字ノードオブジェクトの所在情報とを対応付けて記録する前方リンク定義部，及び、
前記次文字情報が示す文字に異体字がある場合に、その異体字を示す異体字情報と、その次文字情報に対応付けられている所在情報とを、対応付けて、その次文字情報を持つ文字ノードオブジェクトに記録する異体字リンク定義部
を備えることを特徴とする文字列探索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００８−３８５４（Ｐ２００８−３８５４Ａ）
【公開日】平成２０年１月１０日（２００８．１．１０）
【国際特許分類】
【出願番号】特願２００６−１７２８６７（Ｐ２００６−１７２８６７）
【出願日】平成１８年６月２２日（２００６．６．２２）
【出願人】（０００２３７１５６）株式会社エフ・エフ・シー (100)
【Ｆターム（参考）】
【公開日】平成２０年１月１０日（２００８．１．１０）
【国際特許分類】
【出願日】平成１８年６月２２日（２００６．６．２２）
【出願人】（０００２３７１５６）株式会社エフ・エフ・シー (100)
【Ｆターム（参考）】
[ Back to top ]