JP4470913B2 - 文字列検索装置およびプログラム - Google Patents

Description

本発明は、テキストデータからキーワードと一致する文字列を抽出する技術に関する。

現在、ＯＣＲ（Optical Charactor Reader）等、印刷物を読み取り、その情報を電子データ化する機器が普及している。このような電子データは、画像データとして生成される。このため、電子データの文字を検索する場合には、画像データを文字認識する処理をしてテキストデータを抽出し、画像データに透明データとしてあるいは検索用のデータとして埋め込むことが必要になる。

ただし、文字認識の認識率は、読取対象の画像の品質や読取の状況等に影響される。この点を、図９を用いて説明する。図９（ａ）は、汚れＡがある読取対象の画像を示す図である。図９（ｂ）は、図９（ａ）に示した画像をＯＣＲで読み取った場合の文書の認識状態を示す。図９（ｃ）は、図９（ｂ）に示した認識状態において発生する不具合を説明するための図である。

図９（ａ）に示した画像は、文書ブロック９０４と文書ブロック９０３を有し、各文書ブロックには４行の文字列がある。このような画像において、文書ブロック９０４上に汚れＡが存在すると、ＯＣＲは、文書ブロック９０４の１行を図９（ｂ）のように別の行として誤認識する場合がある。図９（ｂ）に示した例では、文書ブロック９０４の１行目が１行目と５行目と認識され、２行目が２行目と６行目に、３行目が４行目と７行目であると誤認識される。

行の誤認識が発生すると、図９（ｃ）に示したように、矢線ａで示す順番で本来文字列を認識すべきところ、矢線ｂで示す順番で認識される可能性が生じる。このような場合、当然のことながら、正しいテキスト情報を抽出することができなくなる。このため、抽出されたテキスト情報を使って文字列検索した場合、キーワードと一致する文字列にヒットしない、あるいはキーワードと異なる文字列にヒットするという不具合が発生し得る。

文字列検索の精度を高める従来技術としては、例えば、特許文献１が挙げられる。特許文献１は、キーワードに含まれる文字を検索し、検索の結果得られた文字の位置を抽出する。そして、この位置の情報に基づいてキーワード位置を推定し、さらに文字パターン照合などによって検索を行うことが記されている。
特開２００１−３３７９９３号公報

しかしながら、特許文献１の技術は、キーワード検索のための要する計算量が比較的大きく、ソフトウェア実行リソースが限られている簡易な機器に適用することに不向きである。すなわち、N文字からなる文書からm個の文字を使ってキーワード文字を抽出する場合、m×Nの計算量が必要になる（殆どヒットしないと仮定する）。
そして、さらに、特許文献１の発明では、抽出されたキーワード文字に基づいて、文字の領域を特定し、この領域にキーワードがあるか否か判定する。このため、文字数の多い文書で複数の文字を使って検索する場合、特許文献１の技術は、文字領域を特定する以前の処理ですでに計算にかかる負荷が大きくなる。

本発明は、このような点に鑑みてなされたものであり、より少ないソフトウェア実行リソースでも、検索漏れがより少ない文字列検索技術を提供することを目的とする。

以上の課題を解決するため、本発明は、ｎ個（ｎは自然数）の文字を含む文字列を示すテキストデータを記憶するテキスト記憶手段と、ｍ個（ｍはｍ≦ｎを満たす自然数）の文字を含むキーワードの入力を受け付ける受付手段と、前記キーワードに含まれる文字のうち、ａ個（ａはａ≦ｍを満たす自然数）の文字を判定対象文字として抽出する文字抽出手段と、前記テキスト記憶手段に記憶されたテキストデータにより示されるｎ個の文字のうちｂ個（ｂはｂ≧ａを満たす自然数）の文字を含む検索窓を設定する検索窓設定手段と、前記検索窓設定手段により設定された検索窓に含まれる文字を、前記判定対象文字と比較した比較結果に応じて、前記検索窓が前記キーワードを含むか判定する判定手段とを有する文字列検索装置を提供する。この文字列検索装置によれば、検索漏れを低減することができる。

好ましい態様において、この文字列検索装置は、文字と、その文字に対応する確度を示す情報とを含む確度テーブルを記憶したテーブル記憶手段をさらに有し、前記文字抽出手段が、前記キーワードに含まれる文字のうち、前記テーブル記憶手段に記憶された確度テーブルに含まれる確度があらかじめ決められた条件を満たす文字を判定対象文字として抽出してもよい。この文字列検索装置によれば、認識確度が条件を満たさない文字を判定対象文字から除外することができる。

別の好ましい態様において、この文字列検索装置は、あらかじめ決められたアルゴリズムに従って前記検索窓を更新する検索窓更新手段をさらに有してもよい。この文字列検索装置によれば、検索窓を順次更新することにより所望の順序で検索をすることができる。
さらに別の好ましい態様において、この文字列検索装置は、前記アルゴリズムが、更新前の検索窓の先頭文字の次の文字を更新後の検索窓の先頭文字とするアルゴリズムであってもよい。
さらに別の好ましい態様において、この文字列検索装置は、前記アルゴリズムが、更新前の検索窓の先頭文字から所定の文字数離れた文字を更新後の検索窓の先頭文字とするアルゴリズムでってもよい。
さらに別の好ましい態様において、この文字列検索装置は、前記アルゴリズムが、更新前の検索窓の先頭文字と更新後の検索窓の先頭文字との間に位置する文字がすべて前記判定対象文字と一致しなかった文字となるように更新後の検索窓を決定するアルゴリズムであってもよい。

さらに別の好ましい態様において、この文字列検索装置は、前記検索窓設定手段が、前記テキストデータにおける文字のサイズ、テキストデータが示す文字が描画される位置の少なくとも一方を使って検索窓生成のための文字の抽出範囲を決定してもよい。この文字列検索装置によれば、より適正に決定された抽出範囲から抽出された検索窓を用いて検索をすることができる。

また、本発明は、コンピュータ装置を、ｎ個（ｎは自然数）の文字を含む文字列を示すテキストデータを記憶するテキスト記憶手段と、ｍ個（ｍはｍ≦ｎを満たす自然数）の文字を含むキーワードの入力を受け付ける受付手段と、前記キーワードに含まれる文字のうち、ａ個（ａはａ≦ｍを満たす自然数）の文字を判定対象文字として抽出する文字抽出手段と、前記テキスト記憶手段に記憶されたテキストデータにより示されるｎ個の文字のうちｂ個（ｂはｂ≧ａを満たす自然数）の文字を含む検索窓を設定する検索窓設定手段と、前記検索窓設定手段により設定された検索窓に含まれる文字を、前記判定対象文字と比較した比較結果に応じて、前記検索窓が前記キーワードを含むか判定する判定手段として機能させるプログラムを提供する。このプログラムによれば、検索漏れを低減することができる。

＜１．第１実施形態＞
図１は、本発明の第１実施形態の文字列検索装置を説明するための機能ブロック図である。本実施形態では、文字列検索装置を電子ブック等として利用される電子文書のビューア（電子ペーパとも記す）に適用するものとした。

また、本実施形態では、ＯＣＲ等によって読み取られた文書の画像データからテキスト情報が抽出され、カードメディア１０８等にいったん保存される。そして、保存されたテキスト情報は電子ペーパに読み込まれ、表示される。そして、ユーザが電子ペーパにキーワードを入力し、電子ペーパが入力されたキーワードと一致する文字列を検索して抽出するものとする。

図示した文字列検索装置は、ｎ個（ｎは自然数）の文字を含む文字列を示すテキストデータから、ｍ個（ｍはｍ≦ｎを満たす自然数）の文字を含む文字列であるキーワードを抽出する文字列検索装置である。テキストデータは、各々ある文字を示す文字データをｎ個含む。また、テキストデータはある文字群（文書ブロック）を示す情報を含んでもよい。あるいは、文字列検索装置は、テキストデータとは別に、文書ブロックを示す情報を記憶してもよい。文字列検索装置は、キーワード（詳細には、キーワードを示すキーワードデータ）の入力を受け付ける入力装置１０１、入力されたキーワードの少なくとも一部をテキストデータと対照（比較）し、キーワードとテキストデータとの一致を判定する文字列検索部１００、文字列検索部１００による検索結果を表示する検索結果表示部１０６とでなる。なお、文字列検索装置を電子ペーパに適用した本実施形態では、検索結果表示部１０６を記憶性液晶でなるディスプレイとして構成する。

文字列検索部１００は、キーワードに含まれるｍ個の文字のうちａ個（ａはａ≦ｍを満たす自然数）の文字、すなわちキーワードの少なくとも一部を用いて、キーワードとテキストデータとの一致を、ｂ個（ｂはｂ≧ａを満たす自然数）の文字を含む検索窓ごとに判定する。また、検索処理部１０４は、この判定においてキーワードを構成する文字のうち少なくとも一部の文字（「一致判定対象文字」という）と検索窓に含まれるテキストデータとを対照する。
また、文字列検索部１００は、一致判定対象文字とテキストデータとの一致を検索窓ごとに判定するため、テキストデータから連続する文字を所定の数ずつ抽出して検索窓を生成する検索窓設定部１０３、一致判定対象文字と検索窓に含まれる文字との一致を判定（検索）する検索処理部１０４を備えている。さらに、文字列検索部１００は、検索の結果を検索結果表示部１０６に表示するまで一時的に保存しておく検索結果保持部１０５を備えている。

検索結果は、一致判定対象文字と一致した（ヒットした）文字の表示位置として得られる。文字の表示位置は、例えば、ヒットしたテキストデータと他のテキストデータとの検索結果表示部１０６における表示色を異ならしめる等の方法によって示される。
また、本実施形態の文字列検索部１００は、文字選出手段として機能する対象文字抽出部１０２を備え、対象文字抽出部１０２によってテキストデータとキーワードとの一致判定に使用される文字を選出している。本実施形態では、テキストデータは文字の画像をＯＣＲ等によって読み取って生成されたものである。対象文字抽出部１０２は、文字の読取時に文字が適正に認識される確率（認識確度）に基づいて、一致判定対象文字を決定する。

このような構成を実現するため、本実施形態では、文字の認識確度を示すデータである文字認識確度表１０７が電子ペーパに保存されており、対象文字抽出部１０２が文字認識確度表１０７を参照してキーワードの認識確度を判定する。そして、キーワードに含まれる文字のうち認識確度が所定のしきい値以上の一致判定対象文字を使ってキーワードと一致する文字列を検索するものとする。

図２は、検索窓設定部１０３による検索窓の生成について説明するための図である。図２の例では、「我国の特許は先願主義」の文字を含むテキストデータからキーワード「特許」の文字が検索される。本実施形態では、キーワード「特許」のうち、「特」のみが一致判定対象文字であって、「許」の文字は一致判定対象文字でないものとする。
この際、検索窓設定部１０３は、キーワード「特許」に１文字分をマージンとして付加し、検索窓の文字数を３文字に設定する。検索窓設定部１０３は、テキストデータから３文字を検索窓として抽出する。このような設定（決定）を、本実施形態では、「検索窓の設定（決定）」という。

また、検索窓設定部１０３は、図２（ａ）から（ｈ）に示したように、検索窓として抽出される文字をテキストデータにおいて連続する順番で１文字ずつずらし、順次検索窓を設定する（「検索窓の更新」という）。なお、検索窓の設定は、具体的には、電子ペーパが備えるメモリに検索窓の文字数分だけ文字を記憶する領域を設け、この領域に記憶される文字を１文字ずつ図中の左方向から右方向の文字へ変更することをいう。なお、テキストデータが縦書きの場合、窓の設定は、メモリの領域に記憶される文字を１文字ずつ上方向から下方向の文字へ変更することによって行われる。

図２に示した例では、（ｂ）に示した検索窓に一致判定対象文字である「特」の文字が含まれる。詳細には、一致判定対象文字「特」１文字に対し検索窓中のヒット文字数１である。一致判定対象文字の文字数に対するヒット文字数の割合を「検索ヒット率」という。この場合、検索ヒット率は１００％である。検索処理部１０４は、検索ヒット率に基づいてキーワードがヒットしたか判定する。この場合、検索処理部１０４は、キーワード「特許」がヒットしたと結論付ける。検索処理部１０４は、「特」の文字の位置をヒット位置として検索結果保持部１０５に格納し、記憶させる。次に、検索窓設定部１０３は、（ｃ）に示したように検索窓を設定する。このときにも検索窓に「特」の文字が含まれているので、検索処理部１０４は、「特」の文字の位置をヒット位置として検索結果保持部１０５に格納するが、先に同位置が保存されているため実際は保存処理は行われない。

さらに、検索窓設定部１０３は、（ｄ）に示したように検索窓を設定する。このときにも検索窓に「特」の文字が含まれているので、検索処理部１０４は、「特」の文字の位置をヒット位置として検索結果保持部１０５に格納する。しかし、同様に、先に同位置が保存されているため実際は保存処理は行われない。そして、（ｅ）に示したように検索窓が設定された場合、検索窓に一致判定対象文字が含まれていないことから、検索処理部１０４はキーワードがヒットしたと判定しない。

なお、複数の一致判定対象文字がある場合、ヒットしたと判定される文字の種類が所定の数以上である場合にキーワードがヒットしたと判定するようにしてもよい。
図２に示したように、検索窓を１文字ずつずらして設定することにより、一致判定対象文字があるにも関わらずヒットとして検出されない、いわゆる検索の漏れが発生する可能性を低減することができる。

また、検索窓を更新するアルゴリズムは上述のものに限定されない。例えば、検索窓として抽出される文字をテキストデータにおいて連続する順番で、かつ所定の数ずつずらすようにしてもよい。あるいは、５文字分の検索窓中の文字列の最後の２文字だけがヒットしており検索対象文字が４文字あるためこの窓設定では検索ヒットとならなかったような場合、次の窓設定（窓のずらし）を３文字分進めることで窓の高速移動を実現しても良い。すなわち、更新前の検索窓の先頭文字と更新後の検索窓の先頭文字との間に位置する文字がすべて一致判定対象文字と一致しなかった文字となるように更新後の検索窓が設定されてもよい。このようにした場合、本実施形態は、検索のための計算量が低減し、検索処理にかかるリソースの負荷をより小さくし、さらにソフトウェアリソースが小型の装置を使って文字検索することができる。

図３は、以上述べた本実施形態の文字列検索方法をコンピュータに実行させるためのプログラムを説明するためのフローチャートである。このプログラムでは、先ず、オペレータが文字検索装置に入力装置１０１を使って検索したいキーワードを入力する（Ｓ３０１）。対象文字抽出部１０２は、文字認識確度表１０７を参照し、キーワードから一致判定対象文字列を選出する（Ｓ３０２）。

次に、検索窓設定部１０３は、選出された文字群を含むキーワードの文字数にマージンを加える等して文字窓長を決定する（Ｓ３０３）。そして、決定した文字窓長分の文字をテキストデータ３２から読み込み、検索窓を設定する（Ｓ３０４）。
検索処理部１０４は、設定された検索窓を単位にして検索マッチ判定を実行する（Ｓ３０５）。そして、１つの窓に対する検索マッチ判定が終了するたびに文書のすべてについて検索マッチの判定が終了したか否か判定する（Ｓ３０６）。判定の結果、文書すべての検索マッチが終了していない場合（Ｓ３０６：Ｎｏ）、ステップＳ３０４で設定された窓をシフトし（Ｓ３０８）、再度検索窓を設定する（Ｓ３０４）。

また、文書すべてについて検索マッチ判定が終了した場合（Ｓ３０６：Ｙｅｓ）、検索結果を出力して処理を終了する（Ｓ３０７）。

図４は、図３に示したステップＳ３０２の一致判定対象文字抽出の処理を説明するためのフローチャートである。一致判定対象文字抽出の処理では、対象文字抽出部１０２が、入力されたキーワードの文字数をｋｗｄ＿ｎｕｍに設定する（Ｓ４０１）。図２に示した例では、キーワードが「特許」であるから、ｋｗｄ＿ｎｕｍは２に設定される。

次に、対象文字抽出部１０２は、処理開始の設定として、変数ｉ＝０（Ｓ４０２）、変数ｋｅｙｃｈａｒ＿ｎｕｍ＝０とし（Ｓ４０３）、さらに配列ｋｅｙｃｈａｒ＿ｉｄｘを作成する（Ｓ４０４）。変数ｋｅｙｃｈａｒ＿ｎｕｍは、一致判定対象文字列の文字数を示す。配列ｋｅｙｃｈａｒ＿ｉｄｘは、キーワードにおける一致判定対象文字の位置を示す。そして、キーワードのうちのｉ番目の文字の認識度を文字認識度確度表１０７から求め、認識確度と予め設定されているしきい値とを比較する。文字認識度確度表１０７は、複数の文字について、文字と、その文字に対応する認識確度とを含むテーブルである。
そして、対象文字抽出部１０２は、認識確度がしきい値以上であるか否か判断し（Ｓ４０５）、しきい値以下であった場合には（Ｓ４０５：Ｎｏ）、ｉを１つカウントアップする（Ｓ４０８）。カウントアップされた後のｉがｋｗｄ＿ｎｕｍに満たない場合（Ｓ４０９：Ｙｅｓ）、再びｉ番目の文字の認識度をしきい値と比較する。また、ｋｗｄ＿ｎｕｍがｉよりも大きくない場合（Ｓ４０９：Ｎｏ）、処理を終了する。

一方、ステップＳ４０５において、ｉ番目の文字の認識確度がしきい値以上であると判断された場合（Ｓ４０５：Ｙｅｓ）、対象文字抽出部１０２は、ｉを配列ｋｅｙｃｈａｒ＿ｉｄｘに設定する（Ｓ４０６）。すなわち、ｋｅｙｃｈａｒ＿ｉｄｘ［ｋｅｙｃｈａｒ＿ｎｕｍ］＝ｉとする。続いて、対象文字抽出部１０２は、ｋｅｙｃｈａｒ＿ｎｕｍを１カウントアップした後（Ｓ４０７）、ｉを１つカウントアップする（Ｓ４０８）。
このような処理において、キーワードである「特許」の「特」の文字の認識確度がしきい値（例えば８０％）以上であり、「許」の文字の認識確度がしきい値以下であれば、ステップＳ４０５において、先ず「特」の文字の認識確度がしきい値以上であると判断される。このため、作成された配列ｋｅｙｃｈａｒ＿ｉｄｘ［０］＝０に設定され、ｋｅｙｃｈａｒ＿ｎｕｍが１になる。さらに、ｉが１にカウントアップされ、ｉがｋｗｄ＿ｎｕｍの２に満たないことからさらに「許」の文字の認識確度としきい値とが比較される。

次の処理では、「許」の認識確度がしきい値以下であるため、ｉがカウントアップされて２になる。ここで、ｉがｋｗｄ＿ｎｕｍより小さくないために処理が終了する。なお、認識確度がしきい値以上の文字である「特」は、本実施形態でいう一致判定対象文字である。また、認識確度がしきい値以下の文字である「許」は、本実施形態でいう一致判定対象外文字である。

図５は、図３のステップＳ３０３に示した文字窓長決定の処理を説明するためのフローチャートである。検索窓設定部１０３は、先ず、文字幅マージンを変数ｍａｒｇｉｎに設定する（Ｓ５０１）。なお、文字幅マージンは、予め検索窓設定部１０３に設定されるものであってもよいし、ユーザが任意に設定するものであってもよい。
さらに、検索窓設定部１０３は、次式（１）によって、検索窓となる文字数（Ｗｉｎｄｏｗ＿ｓｉｚｅ）を決定する（Ｓ５０２）。式（１）に示されるように、本実施形態において検索窓の文字数は、一致判定対象文字の文字数の関数である。

ここで、図２に示した「特許」をキーワードとした場合を例に挙げ、Ｗｉｎｄｏｗ＿ｓｉｚｅを決定する手順について述べる。この例では、文字幅マージンを１に固定するものとする。図４のフローチャートより、ｋｅｙｃｈａｒ＿ｎｕｍは１である。また、キーワード「特許」における「特」の位置を「０」と、「許」の位置を「１」と表す。したがって、ｋｅｙｃｈａｒ＿ｉｄｘ［０］＝０である。このような値を式（１）に代入すると、以下の結果を得る。

ｗｉｎｄｏｗ＿ｓｉｚｅ＝（ｋｅｙｃｈａｒ＿ｉｄｘ［ｋｅｙｃｈａｒ＿ｎｕｍ−１］＋ｍａｒｇｉｎ）−（ｋｅｙｃｈａｒ＿ｉｄｘ［０］−ｍａｒｇｉｎ）＋１
＝（０＋１）−（０−１）＋１＝３

図６は、図３のステップＳ３０４に示した検索窓設定の処理を説明するためのフローチャートである。検索窓設定部１０３は、Ｗｉｎｄｏｗ＿ｓｉｚｅ分の文字数の記憶領域（「Ｗｉｎｄｏｗ配列」という）をワークエリア等として動作する図示しないメモリ上に作成する（Ｓ６０１）。そして、検索対象となる文書のテキスト情報の先頭行から順にＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数を抽出する（Ｓ６０２）。なお、Ｗｉｎｄｏｗ配列は、本実施形態でいう検索窓に対応する。

次に、検索窓設定部１０３は、Ｗｉｎｄｏｗ配列に読み込まれた文字数がＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数に達したか否か判断する（Ｓ６０３）。この判断の結果、読み込まれた文字数がＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数に達している場合（Ｓ６０３：Ｎｏ）、Ｗｉｎｄｏｗ配列に読み込まれた文字数を変数ｓｅａｒｃｈｅｄ＿ｔｏｋｅｎ＿ｓｉｚｅの値とする（Ｓ６０７）。

一方、ステップＳ６０３において、Ｗｉｎｄｏｗ配列に読み込まれた文字数がＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数に満たないと判断された場合（Ｓ６０３：Ｙｅｓ）、検索候補となる次行が存在するか否かを検索する（Ｓ６０４）。そして、検索候補となる次行がある場合（Ｓ６０５：Ｙｅｓ）には次行の先頭から順に文字をＷｉｎｄｏｗ配列に読み込む（Ｓ６０６）。また、次行がない場合（Ｓ６０５：Ｎｏ）、Ｗｉｎｄｏｗ配列に読み込まれた文字数を変数ｓｅａｒｃｈｅｄ＿ｔｏｋｅｎ＿ｓｉｚｅとおく（Ｓ６０７）。

図７は、図３のステップＳ３０５に示した検索マッチ判定の処理を説明するためのフローチャートである。検索処理部１０４は、検索マッチ判定のため、先ず、変数ｃｈａｒ＿ｍａｔｃｈ＿ｎｕｍ＝０（Ｓ７０１）、変数ｉ＝０（Ｓ７０２）、変数ｊ＝０（Ｓ７０３）に設定する。なお、ｃｈａｒ＿ｍａｔｃｈ＿ｎｕｍは、文書中の文字が一致判定対象文字と一致したと判定された回数を示す変数である。

次に、検索処理部１０４は、Ｗｉｎｄｏｗ配列に読み込まれた文字（Ｗｉｎｄｏｗ配列要素）のうち、ｊ＋１番目の文字とｋｅｙｃｈａｒ＿ｉｄｘ［ｉ］＋１番目の文字とが合致するか判断する（Ｓ７０４）。両者が合致した場合（Ｓ７０４：Ｙｅｓ）、合致した文字のテキストデータにおける位置を一時的に保存する（Ｓ７０５）。そして、ｃｈａｒ＿ｍａｔｃｈ＿ｎｕｍを１つカウントアップする（Ｓ７０６）。

次に、検索処理部１０４は、ｉを１つカウントアップし（Ｓ７０９）、カウントアップ後のｉがｋｅｙｃｈａｒ＿ｎｕｍ、すなわち一致判定対象文字の数に達したか否か判断する（Ｓ７１０）。判断の結果、ｊの値がＷｉｎｄｏｗ配列に読み込まれた文字数に満たない場合（Ｓ７１０：Ｙｅｓ）、検索処理部１０４は、処理をステップＳ７０４に移行する。ステップＳ７０４において、検索処理部１０４は、検索窓のｊ＋１番目の文字とｋｅｙｃｈａｒ＿ｉｄｘ［ｉ］＋１番目の文字とが合致するか判定する（Ｓ７０４）。

また、ステップＳ７１０において、ｊの値がＷｉｎｄｏｗ配列に読み込まれた文字数に達したと判断された場合（Ｓ７１０：Ｎｏ）、ｃｈａｒ＿ｍａｔｃｈ＿ｎｕｍ／ｋｅｙｃｈａｒ＿ｎｕｍで表される検索ヒット率を算出する。そして、しきい値（例えば０．８すなわち８０％）以上の確率が得られた場合（Ｓ７１１：Ｙｅｓ）、この検索窓がキーワードにマッチングするとして変数ｍａｔｃｈを１に設定する（Ｓ７１２）。変数ｍａｔｃｈは、検索窓がキーワードを含むことを示すフラグである。さらに、一時保存してあるテキストの位置を一括で保存する（Ｓ７１３）。この際、すでに保存されているテキスト位置と重複する場合には保存の必要は無い。

また、ステップＳ７１１の演算でしきい値以上の確率が得られなかった場合（Ｓ７１１：Ｎｏ）、検索窓がキーワードにマッチングしないとして変数ｍａｔｃｈを０に設定する（Ｓ７１３）。
図８は、図３のステップＳ３０８に示した窓シフトの処理を説明するためのフローチャートである。図７に示した処理によって１つの検索窓のマッチング判定が終了すると、検索処理部１０４は、図２に示したように、検索窓を１文字分シフトさせてキーワードと文書との一致を判定する。このため、検索処理部１０４は、先ず、先にＷｉｎｄｏｗ配列に読み込まれた文字をクリアする（Ｓ８０１）。

次に、検索処理部１０４は、現在検索の対象としている行において、前回Ｗｉｎｄｏｗ配列に読み込んだ検索窓の先頭の文字の次の文字からＷｉｎｄｏｗ＿ｓｉｚｅ分の文字を抽出する（Ｓ８０２）、抽出された文字をＷｉｎｄｏｗ配列に読み込む（Ｓ８０３）。そして、読み込まれた文字数がＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数に満たないか否かを判断する（Ｓ８０４）。この結果、読み込まれた文字数がＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数に達している場合（Ｓ８０４：Ｎｏ）、Ｗｉｎｄｏｗ配列に読み込まれた文字数を変数ｓｅａｒｃｈｅｄ＿ｔｏｋｅｎ＿ｓｉｚｅの値とする（Ｓ８０８）。

また、読み込まれた文字数がＷｉｎｄｏｗ＿ｓｉｚｅ分の文字数に満たない場合（Ｓ８０４：Ｙｅｓ）、検索処理部１０４は、次の行にあたる文字群があるか否か判断する（Ｓ８０６）。例えば、処理対象となっている行（文書ブロック）との位置関係に基づいて、次に処理対象となる行が存在するか判断される。そして、次行がある場合には次行の先頭からＷｉｎｄｏｗ配列の空き領域に文字を読み込む（Ｓ８０７：Ｙｅｓ）。また、次行がない場合には、Ｗｉｎｄｏｗ配列に読み込まれた文字数を変数ｓｅａｒｃｈｅｄ＿ｔｏｋｅｎ＿ｓｉｚｅの値とする（Ｓ８０８）。

Ｓ８０２においては、前回Ｗｉｎｄｏｗ配列に読み込んだ検索窓の先頭の文字の次の文字としたが、新しいＷｉｎｄｏｗ配列の先頭文字位置は前回の一致判定対象文字「特」に一致しなかった文字の位置を考慮してそれらをスキップするようにしても良い。つまり、前回のＷｉｎｄｏｗ状態が図２の（ａ）であった時、窓内に設定された文字でキーワード文字にヒットしなかった文字はスキップすることにより、次の窓設定を図２（ｄ）にするような計算を行っても良い。上記計算によればまた初期状態が図２（ｂ）であったときも同様に次の窓状態を図２（ｄ）にすることになる。

また、Ｓ８０５において次の行の候補を探す際には、図９（ｂ）行１に続く行の候補として行２と共に行５も含める処理を行うとしてもよい。これによって、図９に示すように読取ゆがみやよごれエラーに起因して発生する領域認識エラーに依存しにくい検索が可能になりヒット率が向上する。例えば、文書データにテキスト行の位置情報が含まれていれば、左から右に文字が進む言語体系の横書き文書の場合次の行候補は行位置の下位置にある行２と右位置にある行５を候補とすればよい。

さらに、本実施形態は、以上説明した処理に加え、検索窓設定部１０３が、テキストデータにおける文字のサイズ、テキストデータが示す文字が描画される位置の少なくとも一方を使って検索窓生成のための文字の抽出範囲を決定することもできる。
すなわち、文字サイズを考慮すれば、図９に示した行１と行５の間隔が１、２文字程度であるか否かを文字のサイズと行間隔とに基づいて判断する。そして、１、２行程度であった場合、行５を次行候補として採用する。また、次の行との間隔が２行分以上あった場合、この行が他の段落に含まれる行であると判定してもよい。

このような処理は、段落等の文書のブロック同士は一般的にブロック内の１行分以上の間隔を空けて描画されることに基づくものである。つまり、１、２行分程度の間隔に文字が存在しないとみなされた場合、本実施形態では、この間隔が文書のブロックの区切りではなく汚れ等によって文字認識ができなかったものとみなすものとする。
以上のように、本実施形態は、窓の範囲内にキーワード以上の文字を含ませておくことができるので、領域誤認識からもれた文字や汚れＡに隠れた文字、さらには本来１つの文字が複数の文字であるとＯＣＲ等によって誤認識された文字をも検索の対象とすることができる。なお、キーワードに付加される文字数は、スキャナの能力やＯＣＲの能力等に応じて変更可能にすることが望ましい。

また、文字が描画される位置を考慮する場合、例えば、複数の行のうちの行端の文字の描画開始、あるいは終了の位置が揃っている範囲を文書の１ブロックとみなすようにしてもよい。このような処理は、ブロックの開始行が多くの場合文字下げされることに基づいてなされるものである。

＜２．第２実施形態＞
続いて、本発明の第２実施形態について説明する。以下において、第１実施形態と共通する事項についてはその説明を省略し、第１実施形態との差異点を中心に説明する。また、第１実施形態と共通する要素については、共通の参照符号を用いて説明する。第２実施形態においては、検索対象のテキストが「日本の特許制度は、多くの国の制度と同様に先願主義を採用しています。」であり、キーワードが「特許制度」である場合を例にとり説明を行う。

第２実施形態においても、処理は基本的に図３に示されるフローに従って行われる。ステップＳ３０１において、キーワード「特許制度」が入力される。ステップＳ３０２において、対象文字抽出部１０２は、文字認識確度表１０７を参照し、キーワードから検索に使用する文字群を選出する。文字認識確度表１０７は、キーワードを構成する文字「特」、「許」、「制」および「度」のうち、文字「許」の認識確度がしきい値以下であることを示す情報を記憶している。したがって、一致判定対象文字として、「特？制度」が特定される。なお、ここで、記号「？」は、キーワードのうち、その位置の文字が一致判定対象文字ではないことを示す。すなわち、記号「？」はいわゆるワイルドカードを示す。

ステップＳ３０３において、検索窓設定部１０３は、式（１）に従って文字窓長を「６文字」と決定する。ステップＳ３０４〜Ｓ３０６およびＳ３０８において、検索窓設定部１０３および検索処理部１０４は、検索窓ごとに、その検索窓が一致判定対象文字を含むか判定する。

図１０は、第２実施形態における検索窓を例示する図である。まず、ステップＳ３０４において、テキストデータの先頭から文字窓長分（６文字）の文字列が、文字窓として設定される。図１０の例では、まず、文字列「日本の特許制」が文字窓として設定される（図１０（Ａ））。ステップＳ３０５において、検索処理部１０４は、検索マッチ判定を行う。ここでは検索窓のうち４文字目の「特」および６文字目の「度」が、一致判定対象文字に一致する。したがってｃｈａｒ＿ｍａｔｃｈ＿ｎｕｍ＝２である。また、ｋｅｙｃｈａｒ＿ｎｕｍ＝３である。したがって、図１０（Ａ）のケースでは、検索ヒット率＝６７％である。いま検索ヒット率のしきい値が８０％であるので、この場合はキーワードがヒットしなかったと判定される。まだテキストデータについて処理が完了していないので（Ｓ３０６：ＮＯ）、ステップＳ３０８において、検索窓が更新される。すなわち、検索窓が右に１文字シフトされる。

同様に、図１０（Ｂ）のケースでは、検索窓のうち３文字目の「特」、５文字目の「制」および６文字目の「度」が、一致判定対象文字に一致する。したがって検索ヒット率＝１００％である。図１０（Ｃ）のケースでも、検索窓のうち２文字目の「特」、４文字目の「制」および５文字目の「度」が、一致判定対象文字に一致する。したがって検索ヒット率＝１００％である。詳細は省略するが、（Ｄ）〜（Ｍ）のケースにおいて検索ヒット率はそれぞれ、１００％、６７％、６７％、３３％、０％、０％、０％、３３％、６７％、６７％である。

いまヒット率のしきい値が８０％であるので、キーワードがヒットしたと判定されるのは図１０（Ｂ）、（Ｃ）および（Ｄ）のケースである。一致判定対象文字の位置はメモリに記憶されている。検索処理部１０４は、記憶された位置に基づいて、テキストデータにおけるキーワードの位置を特定することができる。

＜３．第３実施形態＞
続いて、本発明の第３実施形態について説明する。以下において、第１実施形態と共通する事項についてはその説明を省略し、第１実施形態との差異点を中心に説明する。また、第１実施形態と共通する要素については、共通の参照符号を用いて説明する。第３実施形態においては、検索対象のテキストが「As in other countries, Japanese Patent Law adopts a so-called “First to File” policy.」であり、キーワードが「patent」である場合を例にとり説明を行う。

第３実施形態においても、処理は基本的に図３に示されるフローに従って行われる。ステップＳ３０１において、キーワード「patent」が入力される。ステップＳ３０２において、対象文字抽出部１０２は、文字認識確度表１０７を参照し、キーワードから検索に使用する文字群を選出する。文字認識確度表１０７は、キーワードを構成する文字「ｐ」、「ａ」、「ｔ」、「ｅ」、「ｎ」のうち、文字「ｔ」の認識確度がしきい値以下であることを示す情報を記憶している。したがって、一致判定対象文字として、「ｐａ？ｅｎ？」が特定される。なお、ここで、記号「？」は、キーワードのうち、その位置の文字が一致判定対象文字ではないことを示す。すなわち、記号「？」はいわゆるワイルドカードを示す。

ステップＳ３０３において、検索窓設定部１０３は、式（１）に従って文字窓長を「７文字」と決定する。ステップＳ３０４〜Ｓ３０６およびＳ３０８において、検索窓設定部１０３および検索処理部１０４は、検索窓ごとに、その検索窓が一致判定対象文字を含むか判定する。

図１１は、第３実施形態における検索窓を例示する図である。まず、ステップＳ３０４において、テキストデータの先頭から文字窓長分（７文字）の文字列が、文字窓として設定される。図１１の例では、文字列「Ａｓ ｉｎ ｏ」が文字窓として設定される（図１１（Ａ））。なお、ここでは単語と単語の間に挿入されるスペースも１文字としてカウントしている。スペース、句読点、引用符号などを１文字としてカウントするかどうかは任意設計事項である。ステップＳ３０５において、検索処理部１０４は、検索マッチ判定を行う。ここでは検索窓に一致判定対象文字に一致する文字は存在しない。したがってｃｈａｒ＿ｍａｔｃｈ＿ｎｕｍ＝０である。また、ｋｅｙｃｈａｒ＿ｎｕｍ＝４である。したがって、図１１（Ａ）のケースでは、検索ヒット率＝０％である。いま検索ヒット率のしきい値が８０％であるので、この場合はキーワードがヒットしなかったと判定される。まだテキストデータについて処理が完了していないので（Ｓ３０６：ＮＯ）、ステップＳ３０８において、検索窓が更新される。すなわち、検索窓が右に１文字シフトされる。

例えば、図１１（Ｇ）のケースでは、検索窓のうち４文字目の「ｐ」、５文字目の「ａ」、および７文字目の「ｅ」が、一致判定対象文字に一致する。したがって検索ヒット率＝７５％である。また、図１１（Ｈ）のケースでは、検索窓のうち３文字目の「ｐ」、４文字目の「ａ」、６文字目の「ｅ」、および７文字目の「ｎ」が、一致判定対象文字に一致する。したがって検索ヒット率＝１００％である。詳細は省略するが、（Ａ）〜（Ｌ）のケースにおいて検索ヒット率はそれぞれ、０％、０％、０％、２５％、５０％、５０％、７５％、１００％、１００％、１００％、７５％、５０％である。

いまヒット率のしきい値が８０％であるので、キーワードがヒットしたと判定されるのは図１１（Ｈ）〜（Ｊ）のケースである。一致判定対象文字の位置はメモリに記憶されている。検索処理部１０４は、記憶された位置に基づいて、テキストデータにおけるキーワードの位置を特定することができる。

＜４．他の実施形態＞
本発明は上述の実施形態に限定されるものではなく、種々の変形実施が可能である。
第１および第２実施形態においては日本語の文章を、第３実施形態においては英語の文章を検索の対象とする例について説明したが、検索の対象はこれらの言語に限定されるものではない。日本語および英語以外の他の言語で記述された文章に対し、本発明を適用してもよい。また、左から右に横書きする言語に限られず、日本語や中国語のように縦書きする言語や、アラビア語のように左から右に横書きする言語に対して本発明を適用してもよい。テキストデータから文字列を読み出す順番は、任意に設計されることができる。

検索窓を更新するアルゴリズムは、上述の実施形態で説明したものに限定されない。例えば、更新前の検索窓の先頭文字の次の文字を更新後の検索窓の先頭文字とするアルゴリズムが採用されてもよい。あるいは、更新前の検索窓の先頭文字から所定の文字数離れた文字を更新後の検索窓の先頭文字とするアルゴリズムが採用されてもよい。さらにあるいは、更新前の検索窓の先頭文字と更新後の検索窓の先頭文字との間に位置する文字がすべて前記判定対象文字と一致しなかった文字となるように更新後の検索窓を決定するアルゴリズムが採用されてもよい。

マージンや検索ヒット率のしきい値などのパラメータの値は、上述の実施形態で説明したものに限定されない。これらのパラメータは、任意に設計されることができる。また、検索窓の文字数（検索窓長）は、式（１）以外の数式を用いて決定されてもよい。例えば、検索窓の文字数は、キーワードの文字数の関数であってもよい。

上述の実施形態においては、キーワードに含まれる文字のうち、あらかじめ決められた条件を満たす文字を一致判定対象文字として抽出する例を説明した。しかし、一致判定対象文字を決定する処理は省略されてもよい。すなわち、条件によらず、キーワードに含まれる文字はすべて一致判定対象文字とされてもよい。

図１に示される機能構成は、ハードウェアとして実現されてもよいし、ソフトウェアとして実現されてもよい。例えば、文字列検索装置（電子ペーパ）は、各機能構成要素に相当する電子回路を有してもよい。あるいは、文字列検索装置（電子ペーパ）は、ＣＰＵ（Central Processing Unit）およびメモリなどを有するコンピュータ装置であってもよい。この場合、ＣＰＵが文字列検索プログラムを実行することにより、図１に示される機能構成が実現される。

上述の実施形態において、文字認識確度表１０７は、文字と、その文字に対応する確度を含むテーブルであった。しかし、文字認識確度表１０７のデータ構成はこれに限定されるものではない。文字認識確度表１０７は、例えば、文字と、その文字の確度があるしきい値を超えているかを示す情報とを含むものであってもよい。

検索ヒット率の定義は、一致判定対象文字の文字数に対するヒット文字数の割合に限定されない。「一致判定対象文字の種類に対するヒット文字数の種類」が検索ヒット率の定義として用いられてもよい。

第１実施形態の文字列検索装置の機能ブロック図である。 検索窓の生成について説明するための図である。 文字列検索処理を示すフローチャートである。 一致判定対象文字抽出の処理を示すフローチャートである。 文字窓長決定の処理のフローチャートである。 検索窓設定の処理のフローチャートである。 検索マッチ判定の処理のフローチャートである。 窓シフトの処理のフローチャートである。 従来技術を説明する図である。 第２実施形態における検索窓を例示する図である。 第３実施形態における検索窓を例示する図である。

符号の説明

３２…テキストデータ、１００…文字列検索部、１０１…入力装置、１０２…対象文字抽出部、１０３…検索窓設定部、１０４…検索処理部、１０５…検索結果保持部、１０６…検索結果表示部、１０７…文字認識確度表、１０８…カードメディア

Claims (4)

1. ｎ個（ｎは自然数）の文字を含む文字列を示すテキストデータを記憶するテキスト記憶手段と、
   ｍ個（ｍはｍ≦ｎを満たす自然数）の文字を含むキーワードの入力を受け付ける受付手段と、
   前記キーワードに含まれる文字のうち、ａ個（ａはａ＜ｍを満たす自然数）の文字を判定対象文字として抽出する文字抽出手段と、
   前記テキスト記憶手段に記憶されたテキストデータにより示されるｎ個の文字のうちｂ個（ｂはｂ≧ａを満たす自然数）の文字を含む検索窓を設定する検索窓設定手段と、
   前記検索窓設定手段により設定された検索窓に含まれる文字を、前記判定対象文字と比較した比較結果に応じて、前記検索窓が前記キーワードを含むかの判定をする判定手段と、
   前記判定手段による前記判定において前記検索窓に含まれる連続する２文字以上の文字が前記判定対象文字と一致しなかった場合、更新前の検索窓の先頭文字と更新後の検索窓の先頭文字との間に位置する文字がすべて前記判定対象文字と一致しなかった文字となるように前記検索窓を更新する検索窓更新手段と
   を有し、
   前記判定手段は、前記検索窓更新手段により前記検索窓が更新された後に、更新後の検索窓について前記判定をし、
   前記検索窓の文字数ｂは、
   b = (keychar_idx[a - 1] + margin) - (keychar_idx[0] - margin) + 1
   （ここで、keychar_idx[i]は、前記判定対象文字のi番目の文字が前記キーワードの何番目の文字であるかを示す配列であり、marginは文字幅のマージンを示す）
   である
   ことを特徴とする文字列検索装置。
2. 文字と、その文字に対応する確度を示す情報とを含む確度テーブルを記憶したテーブル記憶手段をさらに有し、
   前記文字抽出手段が、前記キーワードに含まれる文字のうち、前記テーブル記憶手段に記憶された確度テーブルに含まれる確度があらかじめ決められた条件を満たす文字を判定対象文字として抽出する
   ことを特徴とする請求項１に記載の文字列検索装置。
3. 前記検索窓設定手段が、前記テキストデータにおける文字のサイズ、テキストデータが示す文字が描画される位置の少なくとも一方を使って検索窓生成のための文字の抽出範囲を決定することを特徴とする請求項１に記載の文字列検索装置。
4. コンピュータ装置を、
   ｎ個（ｎは自然数）の文字を含む文字列を示すテキストデータを記憶するテキスト記憶手段と、
   ｍ個（ｍはｍ≦ｎを満たす自然数）の文字を含むキーワードの入力を受け付ける受付手段と、
   前記キーワードに含まれる文字のうち、ａ個（ａはａ＜ｍを満たす自然数）の文字を判定対象文字として抽出する文字抽出手段と、
   前記テキスト記憶手段に記憶されたテキストデータにより示されるｎ個の文字のうちｂ個（ｂはｂ≧ａを満たす自然数）の文字を含む検索窓を設定する検索窓設定手段と、
   前記検索窓設定手段により設定された検索窓に含まれる文字を、前記判定対象文字と比較した比較結果に応じて、前記検索窓が前記キーワードを含むかの判定をする判定手段と、
   前記判定手段による前記判定において前記検索窓に含まれる連続する２文字以上の文字が前記判定対象文字と一致しなかった場合、更新前の検索窓の先頭文字と更新後の検索窓の先頭文字との間に位置する文字がすべて前記判定対象文字と一致しなかった文字となるように前記検索窓を更新する検索窓更新手段と
   して機能させ、
   前記判定手段は、前記検索窓更新手段により前記検索窓が更新された後に、更新後の検索窓について前記判定をし、
   前記検索窓の文字数ｂは、
   b = (keychar_idx[a - 1] + margin) - (keychar_idx[0] - margin) + 1
   （ここで、keychar_idx[i]は、前記判定対象文字のi番目の文字が前記キーワードの何番目の文字であるかを示す配列であり、marginは文字幅のマージンを示す）
   である
   ことを特徴とするプログラム。

Images