JPH11238068A - テキスト検索装置 - Google Patents

Abstract

(57)【要約】 【課題】 曖昧検索を行うテキスト検索装置において検
索もれを防ぐ。 【解決手段】 検索文字列展開部１０は、検索文字列の
一部を誤認識許容文字「＃」で置き換えた置換文字列を
生成する。誤認識許容文字の数は、入力部４にて指定さ
れる一致度に応じて定められる。マッチング部１２は
「＃」を任意の１文字とみなすことで、誤り文字を含ん
だ候補文字列を検出することができる。また「＃」を任
意の２文字とみなす、また「＃＃」を任意の１文字とみ
なすとすることで、検索対象テキストを生成する文字認
識において誤分割、誤結合を生じた候補文字列を検出す
ることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文字列が不正確で
あり得るテキストを対象とするテキスト検索装置であっ
て、特にその検索漏れの低減と検索結果における重み付
けに関する。

【０００２】

【従来の技術】従来より、検索文字列を指定し、文書や
文字列に含まれる当該検索文字列を探索するテキスト検
索装置があった。ワードプロセッサに搭載されている文
字列検索機能は、そのようなものの一例である。

【０００３】その検索対象である文書、文字列は、基本
的には誤りがないことが前提とされる。そしてその検索
においては、検索対象テキスト中に含まれる文字列が検
索文字列と完全に一致した場合のみ、関心のある文字列
が検索対象テキスト中に存在すると判断されていた。

【０００４】これに対し、検索対象テキストが光学文字
読取り装置（ＯＣＲ）で読み取られたテキストデータで
ある場合には、その読み取りにおける認識誤りにより、
不正確な文字列を含んだ不完全なテキストとなる確率が
高い。日本語ＯＣＲは精度が低いため、特にそのおそれ
が高い。この不完全テキストに対し、上述のような検索
文字列との完全一致による検索を行うと検索漏れが発生
するおそれがある。つまり、検索対象テキストが正しく
読み取られたものであるならばヒットしたはずである文
字列部分が、認識誤りによりヒットしないことが起こり
うる。

【０００５】そのような検索漏れを防止するために、検
索対象の曖昧さをある程度許容して検索を行う技術（以
下、曖昧検索という。）が存在する。特開昭６２−４４
８７８号公報に開示される第一の曖昧検索の従来技術
は、認識の結果、複数の候補が得られた場合、検索対象
テキスト中に候補文字を埋め込み、検索するものである
（例．文［字学］認［識織］による［本木］
文．．．）。特開平８−７０３３号公報に開示される第
二の曖昧検索の従来技術は、文字認識を行った各文字に
ついて複数の候補が得られた場合にはインデックスにそ
れらを残すものである。この場合、認識結果を各文字ご
とに格納したインデックスにおいて、認識対象の１文字
に対して複数の認識結果の文字候補が格納されうる。こ
の２つの技術は認識結果、すなわち検索対象テキストに
曖昧さを持たせるものである。一方、特開平６−１９５
３８７号公報、特開平７−１５２７７４号公報、特開平
８−６３４８７号公報に開示される第三の曖昧検索の従
来技術は、検索文字列の側に曖昧さを持たせるものであ
る。この方法は、検索文字列中の誤って認識されやすい
部分を、誤認識の可能性のある文字パターン（誤認識パ
ターン）で置き換えた不完全検索文字列を作成し、正し
い検索文字列だけでなく、不完全検索文字列によっても
探索を行うものである。誤認識パターンのタイプとして
は、文字誤り、誤分割、誤結合といったものがある。例
えば、「字」は「学」と認識されやすいが、このような
タイプが文字誤りである。また、「化」は「イヒ」と認
識されやすいが、このようなタイプが誤分割であり、一
方、「５１」は「引」と認識されやすいが、このような
タイプが誤結合である。

【０００６】曖昧検索を行うことにより、検索漏れの減
少を図ることができるメリットがある一方、逆に本来、
検索文字列とは異なる文字列が検索文字列と一致すると
される検索誤りが含まれる可能性もある。

【０００７】

【発明が解決しようとする課題】上述の第一の曖昧検索
の従来技術は、認識結果である検索対象テキストの容量
が増加する、認識結果に残らないと検索されないといっ
た問題があった。また、誤認識パターンのうち誤分割、
誤結合に対応できないという問題もあった。

【０００８】第二の曖昧検索の従来技術においても、認
識結果であるインデックスの容量が増加する、認識結果
に残らないと検索されないという問題があった。

【０００９】第三の曖昧検索の従来技術は、検索文字列
とは別に誤認識パターンを用意する必要があり、その容
量が増加するという問題があった。また例えば誤結合
は、連続する文字の組み合わせに依存して生じ、そのた
め多くのパターンが存在しうる。このように起こりうる
誤認識パターンを全て予め用意することは困難である。
そして予め用意されていない誤認識パターンが発生する
と、検索漏れとなるという問題があった。検索に用いら
れる検索対象テキスト、インデックス、誤認識パターン
などの容量が増加することは、単に記憶装置に大きな容
量を要するという問題だけでなく、検索処理に時間がか
かるという問題も引き起こしていた。

【００１０】また、検索漏れを少なくしようとして、イ
ンデックスに複数候補を登録したり誤認識パターンを充
実させると、その一方で、検索文字列とは元来関係のな
い文字列まで、検索にてヒットするおそれがある。つま
り、検索結果に「ゴミ」（検索誤り）が多く含まれるこ
とになって、検索結果の信頼性が低くなるという問題も
あった。

【００１１】本発明は上記問題点を解消するためになさ
れたもので、曖昧検索に用いるためのデータを少なくす
る一方で、検索漏れを低減するとともに、検索誤りの影
響を軽減するテキスト検索装置を提供することを目的と
する。

【００１２】

【課題を解決するための手段】第一の本発明に係るテキ
スト検索装置は、検索文字列とその部分列との間の指定
された一致度に応じて前記検索文字列の部分列を発生す
る部分列発生手段と、発生された前記部分列と一致する
文字列パターンを含んだ候補文字列を検索対象テキスト
中に探索する候補探索手段とを有するものである。

【００１３】「一致度」は、検索文字列の部分列の当該
検索文字列に対する一致度であり、例えば検索文字列と
部分列とのそれぞれの文字数の比によって定義すること
ができる。指定される一致度は、数値の範囲指定であっ
てもよいし、閾値を示すものであってもよい。「部分
列」は、検索文字列の一部の文字をマスキングしたもの
であり、それを構成する文字は元の検索文字列における
位置の情報を保持している。例えば、検索文字列「キー
ワード」の部分列「キー＃＃ド」「キ＃＃ード」（＃は
マスキングされた文字を表す。）は互いに同一の文字の
組で構成されるが、マスキング位置が異なり、異なる部
分列として扱われる。また、この例に示されるように、
ある部分列を構成する文字は互いに連続する場合だけで
なく、構成する文字の間にマスキング位置が配される場
合もある。候補探索手段は、部分列を構成する各文字の
位置に同一の文字が配置される文字列を候補文字列とし
て、検索対象テキストから抽出する。つまり、候補文字
列の抽出において、検索文字列のうちマスキングされた
位置に来る文字の一致／不一致は問われない。

【００１４】第二の本発明に係るテキスト検索装置は、
検索対象テキストの生成で生じうる誤り文字列パターン
を登録した誤り文字列登録部と、検索文字列に基づいて
候補文字列を探索する候補探索手段と、前記候補文字列
中の前記検索文字列と異なる部分に、前記誤り文字列登
録部に登録された登録誤り文字列パターンを検出する誤
り文字列検出手段と、前記候補文字列に対し前記検索文
字列との一致可能性に応じた優先度を定める優先度付与
手段とを有し、前記優先度付与手段は、前記候補文字列
中における前記登録誤り文字列パターンの検出に応じて
当該候補文字列の前記優先度を定めることを特徴とする
ものである。

【００１５】文字認識等により生成される検索対象テキ
ストは、誤った文字列を含みうるが、その誤り文字列パ
ターンはランダムではなく、元の正しい文字、又は文字
列に対して発生しやすいパターンが存在し得る。誤り文
字列登録部には、主としてそのような発生しやすい誤り
文字列パターンが格納される。本発明は、候補文字列の
うち検索文字列と異なる部分に、誤り文字列登録部に格
納された誤りパターンを検知する。そして例えば、検知
された誤りパターンが当該検索文字列中の対応部分の文
字列に対するものである場合、誤りパターンの部分は検
索対象テキスト生成前においては正しい文字列であった
可能性が高いと判断して、一致可能性に応じた優先度を
高く定めることができる。

【００１６】本発明の好適な態様は、前記検索文字列と
その部分列との間の指定された一致度に応じて前記検索
文字列の部分列を発生する部分列発生手段を有し、前記
候補文字列は、発生された前記部分列と一致する文字列
パターンを含んだ文字列であるものである。

【００１７】第三の本発明に係るテキスト検索装置は、
上記発明において前記候補探索手段が、前記検索文字列
と前記部分列との差分を構成する曖昧文字を、前記検索
対象テキスト中の任意の１文字とみなす手段を有して前
記探索を行うことや、前記検索対象テキスト中の任意の
２文字とみなす手段を有して前記探索を行うことや、ま
た、前記検索文字列と前記部分列との差分を構成する曖
昧文字のうち連続する２つを、前記検索対象テキスト中
の任意の１文字とみなす手段を有して前記探索を行うこ
とのいずれか、またはいくつかを備えたことを特徴とす
るものである。

【００１８】これらにより、それぞれ文字誤り、誤結
合、誤分割を誤りパターンとする候補文字列を検索する
ことができる。

【００１９】第四の本発明に係るテキスト検索装置は、
前記優先度付与手段が、前記登録誤り文字列パターンの
検出頻度に応じて前記優先度を定めることを特徴とする
ものである。本発明によれば、例えば、検出頻度が高い
登録誤り文字列パターンに対する元の文字列はそのよう
な誤りを生じやすいと判断され、高い優先度を与えるこ
とができる。

【００２０】本発明の好適な態様は、前記誤り文字列登
録部が、前記登録誤り文字列パターンに加えてさらにそ
の検出頻度を格納するものである。

【００２１】第五の本発明に係るテキスト検索装置は、
前記優先度に応じて前記候補文字列を表示する候補文字
列表示手段を有するものである。本発明によれば、ユー
ザは、優先度に基づいて、複数の候補文字列における検
索文字列に一致する可能性を把握することができ、例え
ば、検索処理の結果をチェックする際に便利である。

【００２２】

【発明の実施の形態】次に、本発明の実施形態について
図面を参照して説明する。

【００２３】［実施形態１］図１は、本発明の実施形態
であるテキスト検索装置の概略のブロック構成図であ
る。本装置は、ＯＣＲによって文字認識されたテキスト
を検索の対象とし、インデックス記憶部２、入力部４、
検索部６、対象文字位置情報記憶部８、検索文字列展開
部１０、マッチング部１２、出力部１４を含んで構成さ
れる。

【００２４】インデックス記憶部２は、ＯＣＲにより得
られた検索対象テキストをインデックスの形式で、検索
に先立って格納している。インデックスは、検索対象テ
キストに出現する文字をキーとして、それに当該文字の
出現位置を対応付けたものである。

【００２５】入力部４は、検索文字列や一致度といった
検索条件をユーザから受け付ける。

【００２６】検索部６は、入力部４から検索文字列を得
て、それに含まれる各文字にてインデックス記憶部２に
記憶されたインデックスを検索して、検索文字列の各文
字の出現位置を対象文字位置情報記憶部８へ出力し、対
象文字位置情報記憶部８はこれを格納する。

【００２７】検索文字列展開部１０は、検索文字列の部
分列を発生する部分列発生手段であり、入力部４から検
索文字列と一致度を得て、その一致度に応じて、検索文
字列からその部分列を含んだ置換文字列を展開・生成す
る。置換文字列は、検索文字列の一部の文字を例えば記
号「＃」で置換して、元の文字をマスキングすることに
より生成される。置換文字列のうち「＃」で置換された
部分以外は、検索文字列の元の文字で構成された部分列
である。

【００２８】マッチング部１２は、検索文字列展開部１
０から出力される置換文字列を用いて、対象文字位置情
報記憶部８に格納された対象文字位置情報とのマッチン
グを行う。そのマッチング結果は出力部１４へ出力さ
れ、ＣＲＴ等の表示装置に検索結果として画面表示され
る。

【００２９】次に、具体的な例を用いて、各構成部の動
作を説明する。図２は、検索対象テキストのイメージを
示す模式図である。ここで例に用いる検索対象テキスト
は文書Ａ、文書Ｂ、文書Ｃの３つである。文書Ａにはそ
の先頭から１０文字目から文字列「ペルシャ」が存在す
る。同様に文書Ｂにはその先頭から５文字目から文字列
「ベルシャ」が存在し、文書Ｃにはその先頭から２１文
字目から文字列「ペノレシャ」が存在する。

【００３０】図３は、これらの検索対象テキストに対し
て生成され、インデックス記憶部２に格納されているイ
ンデックスのイメージを示す模式図である。インデック
スは、検索対象テキストに出現する文字の種類（図中、
左端に示す。）をキーとして、当該文字種が現れる文書
中の位置をキーごとに分類したものである。その文字の
出現位置は、図中、文書Ａ〜Ｃを区別する番号Ｎdoc
（文書Ａは“１”、文書Ｂは“２”、文書Ｃは“３”）
と、各文書の先頭からの文字数Ｎcharとの組（Ｎdoc，
Ｎchar）の形式で表されている。

【００３１】ユーザは検索条件として、検索文字列「ペ
ルシャ」、一致度７０％を、入力部４に対し入力する。
ここでは、一致度ηは、検索文字列に対する部分列の文
字数の比で定義される。つまり検索文字列の文字数を
Ｍ、置換文字列のうち置換されずに残っている文字数を
ｍとすると、一致度η＝ｍ／Ｍ×１００［％］となる。
入力部４に入力される一致度は、ηの閾値ηthであり、
本装置は検索対象テキスト中にηthを超える一致度を有
する文字列を探索する。なお、一致度の閾値ηthが低い
と検索結果に含まれる「ゴミ」が増えるため、閾値ηth
の好適な値は、一般に７０％程度若しくはそれを上回る
値である。一方、閾値ηthが必要以上に高いと検索漏れ
を生じる可能性が高くなる。その点も考慮して、ここで
はηth＝７０％に設定した。

【００３２】入力部４は、検索文字列「ペルシャ」を検
索部６へ通知する。検索部６はこの検索文字列を得る
と、それを構成する各文字「ペ」、「ル」、「シ」、
「ャ」をキーとしてインデックス記憶部２を検索し、そ
の結果を対象文字位置情報記憶部８に格納する。具体的
には、この例では文字「ペ」に対する出現位置（1,1
0）、（3,21）、文字「ル」に対する出現位置（1,1
1）、（2,6）、文字「シ」に対する出現位置（1,12）、
（2,7）、（3,24）、文字「ャ」に対する出現位置（1,1
3）、（2,8）、（3,25）が対象文字位置情報記憶部８に
格納される。図４は、対象文字位置情報記憶部８に格納
される対象文字位置情報のイメージを示す模式図であ
る。

【００３３】検索文字列展開部１０は、入力部４から検
索文字列と一致度の閾値ηthを受け取って、検索文字列
のうち、一致度に応じた数の文字を誤認識許容文字で置
換した置換文字列を生成する。誤認識許容文字（曖昧文
字）を、ここでは記号「＃」にて表わす。誤認識許容文
字が置かれた部分の検索文字列の文字はマスキングされ
る。マスキングとは、後述する置換文字列と検索対象テ
キストとのマッチングにおいて、両者の異同を問わない
ことを意味する。

【００３４】ここでは検索文字列の文字数Ｍ＝４である
ので、一致度の閾値ηth＝７０％を満たす部分列の文字
数ｍは３または４である。よって、検索文字列展開部１
０は、誤認識許容文字を全く含まない置換文字列（これ
は検索文字列に等しい。）と誤認識許容文字を１つだけ
含む置換文字列を生成する。具体的には、この例では置
換文字列として、「ペルシャ」、「＃ルシャ」、「ペ＃
シャ」、「ペル＃ャ」、「ペルシ＃」の５つが生成され
る。

【００３５】マッチング部１２は、この置換文字列と検
索対象テキストとのマッチングを行い、検索文字列に一
致する可能性を有する候補文字列を探索する候補探索手
段である。マッチングは、置換文字列中での相対的な文
字位置と、対象文字位置情報記憶部８に格納された出現
位置を照合することにより行われる。以下、α、βを置
換文字列に現れる通常の文字とする。

【００３６】例えば、置換文字列中に現れる２文字の部
分「αβ」のマッチングは以下のように行われる。まず
マッチング部１２はα、βをキーとして対象文字位置情
報記憶部８を検索する。ここでα、βに対応する出現位
置をそれぞれ（Ｎdoc(α)，Ｎchar(α)）、（Ｎdoc
(β)，Ｎchar(β)）とする。マッチング部１２は、文書
番号に関してＮdoc(α)＝Ｎdoc(β)であり、かつ文字位
置に関してＮchar(β)＝Ｎchar(α)＋１なる出現位置が
見出すことにより、連続する２文字「αβ」の存在を検
知する。

【００３７】次に、誤認識許容文字「＃」を含んだ文字
列部分「α＃β」、「α＃＃β」、「α＃＃＃β」、
「α＃＃＃…β」等に対するマッチング処理は以下のよ
うに行われる。誤認識許容文字「＃」に関する基本的な
マッチング規則は以下の３通りである。

【００３８】(i) 「＃」は任意の１文字と同一とみな
される、(ii) 「＃」は任意の２文字と同一とみなされ
る、(iii)「＃＃」は任意の１文字と同一とみなされ
る。

【００３９】(i)は文字誤りに対応した規則である。ま
た(ii)、(iii)はそれぞれ誤分割、誤結合に対応した規
則である。

【００４０】規則(i)は、Ｎdoc(α)＝Ｎdoc(β)かつＮc
har(β)＝Ｎchar(α)＋２なる出現位置の探索として実
現される。規則(ii)は、Ｎdoc(α)＝Ｎdoc(β)かつＮch
ar(β)＝Ｎchar(α)＋３なる出現位置の探索として実現
される。また規則(iii)は、Ｎdoc(α)＝Ｎdoc(β)かつ
Ｎchar(β)＝Ｎchar(α)＋２なる出現位置の探索により
実現される。これらの探索により、マッチング部１２は
「α＃β」等の文字列パターンの存在を検知する。

【００４１】マッチング部１２は、置換文字列の各部分
について上述のマッチング処理を行って、検索対象テキ
スト中における置換文字列の存在を検知する。例えば、
置換文字列「ペルシャ」に対しては「ペ（1,10）」、
「ル（1,11）」、「シ（1,12）」、「ャ（1,13）」が上
述の基本的なマッチング規則に適合し、マッチング部１
２はマッチング結果として、当該置換文字列とその先頭
文字の出現位置との組「ペルシャ（1,10）」を出力す
る。そして１度マッチしたものは別の置換文字列でマッ
チしないように対象から除いていく。また、置換文字列
「＃ルシャ」に対しては基本規則と規則(i)に基づいて
「ル（2,6）」に先行する任意の１文字と「ル（2,
6）」、「シ（2,7）」、「ャ（2,8）」が検知され、マ
ッチング部１２はマッチング結果として「＃ルシャ（2,
5）」を出力する。また、置換文字列「ペ＃シャ」に対
しては基本規則と規則(ii)に基づいて「ペ（3,21）」、
これに続く任意の２文字、この任意の２文字に後続する
「シ（3,24）」、「ャ（3,25）」が上述のマッチング規
則に適合し、マッチング部１２はマッチング結果とし
て、「ペ＃シャ（3,21）」を出力する。なお、置換文字
列「ペル＃ャ」、「ペルシ＃」に対しても探索は行われ
るが、この例ではそれらにヒットする文字列（候補文字
列）は存在しない。

【００４２】出力部１４は、マッチング部１２で得られ
たマッチング結果に基づいて、画面上に検索結果を表示
する。上述のマッチング部１２は、マッチング結果とし
て候補文字列の位置を出力するものであり、出力部１４
はそれを例えば、「文書Ａ：（1,10） 文書Ｂ：（2,
5） 文書Ｃ：（3,21）」と表示することができる。そ
の他、誤認識許容文字数によって、完全一致、１文字曖
昧、２文字曖昧というようにランキングを行い、それら
のグループごとに区分して表示してもよい。

【００４３】また、出力部１４は、マッチング部１２か
ら得た文書番号と文字位置を基に、検索対象テキストに
アクセスして、候補文字列を得てそれを表示してもよ
い。また、マッチング部１２自体が、候補文字列の位置
情報に基づいてインデックス記憶部２にアクセスし、候
補文字列をその位置情報と併せて出力部１４へ出力する
ように構成することもできる。このような構成により、
出力部１４は、候補文字列を含んだ内容、例えば「文書
Ａ：ペルシャ（1,10） 文書Ｂ：ベルシャ（2,5） 文
書Ｃ：ペノレシャ（3,21）」を表示することができる。

【００４４】ちなみに本装置は、汎用コンピュータを用
いて構成することができ、特に検索部６、検索文字列展
開部１０、マッチング部１２の機能は、中央演算処理部
（ＣＰＵ：Central Processing Unit）により実行され
うる。

【００４５】本実施形態にて説明した本発明によれば、
例えば文字認識において誤って認識されることにより、
ある文字又は文字列がどのような誤った文字又は文字列
に変換されて検索対象テキストが生成されるかという情
報を用いないのにも拘わらず、文字誤り、誤分割、誤結
合に対応することができ、検索文字列に一致する可能性
のある候補文字列をもれなく検索することができる。

【００４６】［実施形態２］図５は、本発明の第２の実
施形態であるテキスト検索装置の概略のブロック構成図
である。本装置の構成要素のうち上記実施形態と同様の
ものについては同一の符号を付し説明を簡単にする。本
装置は、上記装置の構成に加えて、テキスト記憶部２
０、誤り文字列登録部２４、ランキング部２６とをさら
に備えた点が主たる相違点である。

【００４７】テキスト記憶部２０は、検索対象テキスト
を格納しており、各文書は文書番号を付され互いに区別
されうる。

【００４８】マッチング部２２は、上記実施形態の装置
と同様の処理を行って、候補文字列の位置情報を得る。
本装置のマッチング部２２は、さらにその位置情報に基
づいて、テキスト記憶部２０にアクセスし、候補文字列
を取得し出力する。このとき、位置情報も併せて出力す
ることができる。

【００４９】誤り文字列登録部２４は、文字認識におい
て誤認識されやすい文字又は文字列である誤り文字列パ
ターンを格納している。

【００５０】ランキング部２６は、マッチング部２２か
ら候補文字列を得ると、当該候補文字列中に誤り文字列
登録部２４に登録された誤り文字列パターンを探索す
る。そして、ランキング部２６はその結果に応じて候補
文字列と検索文字列との一致可能性に応じた優先度を定
める（優先度付与手段）。ランキング部２６は、候補文
字列とその優先度とを出力部１４へ出力する。

【００５１】次に、具体的な例を用いて、本装置の動作
の特徴を説明する。図６は、検索対象テキストのイメー
ジを示す模式図である。ここで例に用いる検索対象テキ
ストは文書Ａ、文書Ｂ、文書Ｃの３つである。文書Ａに
はその先頭から１０文字目から文字列「スキャナ」が存
在する。同様に文書Ｂにはその先頭から５文字目から文
字列「スキャン」が存在し、文書Ｃにはその先頭から２
１文字目から文字列「スキヤナ」が存在する。

【００５２】図７は、これらの検索対象テキストに対し
て生成され、インデックス記憶部２に格納されているイ
ンデックスのイメージを示す模式図である。

【００５３】ユーザは検索条件として、検索文字列「ス
キャナ」、一致度７０％を、入力部４に対し入力する。

【００５４】入力部４は、検索文字列「スキャナ」を検
索部６へ通知する。検索部６はこの検索文字列を得る
と、上記実施形態と同様、それを構成する各文字をキー
としてインデックス記憶部２を検索し、その結果を対象
文字位置情報記憶部８に格納する。

【００５５】検索文字列展開部１０は、入力部４から検
索文字列と一致度の閾値ηthを受け取って、それに応じ
た置換文字列を生成する。

【００５６】ここでは検索文字列の文字数Ｍ＝４、及び
一致度の閾値ηth＝７０％に基づいて、検索文字列展開
部１０は、誤認識許容文字を全く含まない置換文字列と
誤認識許容文字を１つだけ含む置換文字列を生成する。
具体的には、この例では置換文字列として、「スキャ
ナ」、「＃キャナ」、「ス＃ャナ」、「スキ＃ナ」、
「スキャ＃」の５つが生成される。

【００５７】マッチング部２２は、この置換文字列と検
索対象テキストとのマッチングを行い、検索対象テキス
ト中における置換文字列の存在を検知する。例えば、置
換文字列「スキャナ」に対しては「ス（1,10）」、「キ
（1,11）」、「ャ（1,12）」、「ナ（1,13）」がマッチ
する。マッチング部２２は、この位置情報に基づいて、
テキスト記憶部２０に格納された検索対象テキストから
候補文字列「スキャナ」を取得し、これとその先頭文字
の出現位置との組「スキャナ（1,10）」を、ランキング
部２６へ出力する。また、置換文字列「スキャ＃」に対
しては上記実施形態で述べた基本規則と規則(i)に基づ
いて「ス（2,5）」、「キ（2,6）」、「ャ（2,7）」及
びこれに後続する任意の１文字がマッチする。マッチン
グ部２２は、この位置情報を基にテキスト記憶部２０に
アクセスして候補文字列「スキャン」を取得し、マッチ
ング結果として「スキャン（2,5）」を出力する。ま
た、置換文字列「スキ＃ナ」に対しては基本規則と規則
(i)に基づいて「ス（3,21）」、「キ（3,22）」、これ
に続く任意の１文字、この任意の１文字に後続する「ナ
（3,24）」がマッチする。マッチング部２２はこの位置
情報を基にテキスト記憶部２０にアクセスして候補文字
列「スキヤナ」を取得し、マッチング結果として「スキ
ヤナ（3,21）」を出力する。

【００５８】ランキング部２６は、マッチング部２２か
らマッチング結果を得ると、候補文字列のランキングを
行う。ここでランキングは、候補文字列が検索文字列に
一致する可能性に応じた優先度を定める処理であり、候
補文字列が検索文字列と異なる部分（誤り文字列）の文
字数と誤り文字列登録部２４に誤り文字列パターンとし
て登録されているかどうかに基づいて定められる。

【００５９】図８は、誤り文字列登録部２４に登録され
た誤り文字列パターンの一例を示す模式図である。図
は、検索対象テキストを生成する際の文字認識におい
て、「→」の左側の文字又は文字列が、右側の文字又は
文字列と誤って認識されやすいことを示している。例え
ば、「ス」は「イ」に、「ャ」は「ヤ」や「ゃ」に、
「ナ」は「メ」に、「ル」は「ノレ」に誤って認識され
やすいことを示している。

【００６０】ランキング部２６は、例えば、候補文字列
が検索文字列と完全一致の場合には、優先度を表す数値
としてポイント「１００」を付与し、１文字不一致の場
合にはポイント「１０」を付与する。その上でランキン
グ部２６は、候補文字列と検索文字列との差分である誤
り文字列が、誤り文字列登録部２４に誤り文字列パター
ンとして登録されているかどうかを調べ、もし登録され
ている場合は、既に獲得しているポイントに、例えば
「４０」ポイントを加える。

【００６１】よって、例えば、候補文字列「スキャナ」
は完全一致であるので、ポイント「１００」を獲得し、
候補文字列「スキヤナ」は１文字不一致で、さらに誤り
文字列登録部２４に「ャ→ヤ」が登録されているので、
それぞれのポイント「１０」、「４０」を加算したポイ
ント「５０」を得る。一方、候補文字列「スキャン」は
１文字不一致であるが、誤り文字列登録部２４にその誤
り文字列が登録されていないので、ポイント「１０」の
みを得る。そして、ランキング部２６は、例えば、ラン
キング結果として、候補文字列とその位置情報とポイン
トの組、例えば「スキャナ（1,10,100）」、「スキヤナ
（2,5,50）」、「スキャン（3,21,10）」を出力部１４
へ出力する。

【００６２】出力部１４は、ランキング部２６からのラ
ンキング結果を得ると、それに含まれるポイントを用い
た表示を行うことができる。例えば、ポイントが高い、
すなわち検索文字列と一致する可能性が高い順に、候補
文字列を画面表示するといったことができる。また、出
力部１４は、ある値以上のポイントを得た候補文字列の
みを表示してもよいし、ポイントが指定された範囲内に
あるものをグループ化して表示してもよい。

【００６３】上述のランキング部２６は、誤り文字列登
録部２４に登録された誤り文字列パターンに対して一定
のポイントを付与したが、必ずしも付与されるポイント
は一律でなくてもよい。例えば、誤り文字列登録部２４
に各誤り文字列パターンの検出頻度などで表される誤り
やすさの度合いを格納し、これをランキングに反映させ
ることにより、より詳細なランキングを行うことができ
る。例えば、誤りやすさを０〜１の調整係数で設定し、
ポイントは、誤り文字列パターン共通のポイントに誤り
やすさの調整係数を乗じるといった方法がある。このよ
うな方法では、例えば、上述の例において候補文字列
「スキヤナ」の調整係数を０．８とすれば、そのポイン
トは１０＋４０×０．８＝４２となるわけである。ま
た、ユーザが検索結果に基づいて、誤り文字列パターン
の検出頻度を増減するように構成することができる。

【００６４】本実施形態にて説明した本発明によれば、
第一の実施形態で説明した発明と同様、検索処理のうち
マッチング自体は、誤り文字列登録部２４に登録された
誤り文字列パターンを必要とせずに、文字誤り、誤分
割、誤結合に対応することができ、検索文字列に一致す
る可能性のある候補文字列をもれなく検索することがで
きる。このもれなく検索することにより、検索文字列と
の一致可能性が低いものも候補文字列として検出され、
マッチング結果に含まれる「ゴミ」（検索誤り）の割合
が増加することは否めない。本発明は、もれなく検索す
るとともに、その検索結果をより確からしい順番にて表
示することを可能にし、これによりユーザが検索結果を
利用する際に各候補文字列の重要度（優先度）を把握す
ることが可能となり、検索誤りが生じても実際の利用に
おけるその影響を軽減することができる。従来の検索文
字列を誤り文字列パターンを用いて展開して検索を行う
方法では、誤り文字列パターンを登録した辞書がある程
度充実していないと検索もれが多くなり、信頼性が低く
なる。これに対し本発明では、誤り文字列登録部２４の
データが無い場合でも、もれなく検索でき、誤り文字列
登録部２４のデータを充実させていくことによりランキ
ングの精度を向上させていくことができる。

【００６５】［実施形態３］本発明の第３の実施形態
は、他の検索文字列を用いた他の検索処理例に係るもの
であり、本実施形態に係るテキスト検索装置の構成は、
上記第二の実施形態の装置と同様である。

【００６６】図９は、検索対象テキストのイメージを示
す模式図である。ここで例に用いる検索対象テキストは
文書Ａ、文書Ｂ、文書Ｃの３つである。文書Ａにはその
先頭から１０文字目から文字列「アルタリア」が存在す
る。同様に文書Ｂにはその先頭から５文字目から文字列
「アル列ア」が存在し、文書Ｃにはその先頭から２１文
字目から文字列「アル夕リア」（“夕”は漢字）が存在
する。

【００６７】図１０は、これらの検索対象テキストに対
して生成され、インデックス記憶部２に格納されている
インデックスのイメージを示す模式図である。

【００６８】ユーザは検索条件として、検索文字列「ア
ルタリア」及び、一致度６０％を入力部４に対し入力す
る。

【００６９】入力部４は、検索文字列「アルタリア」を
検索部６へ通知する。検索部６はこの検索文字列を得る
と、上記実施形態と同様、それを構成する各文字をキー
としてインデックス記憶部２を検索し、その結果を対象
文字位置情報記憶部８に格納する。

【００７０】検索文字列展開部１０は、入力部４から検
索文字列と一致度の閾値ηthを受け取って、それに応じ
た置換文字列を生成する。

【００７１】ここでは検索文字列の文字数Ｍ＝５、及び
一致度の閾値ηth＝６０％から誤認識許容文字は２文字
許される。検索文字列展開部１０は具体的には、この例
では置換文字列として、「アルタリア」、「＃＃タリ
ア」、「＃ル＃リア」、「＃ルタ＃ア」、「＃ルタリ
＃」、「ア＃＃リア」、「ア＃タ＃ア」、「ア＃タリ
＃」、「アル＃＃ア」、「アル＃リ＃」、「アルタ＃
＃」を生成しマッチング部２２へ出力する。

【００７２】マッチング部２２は、この置換文字列と検
索対象テキストとのマッチングを行い、検索対象テキス
ト中における置換文字列の存在を検知する。例えば、置
換文字列「アルタリア」に対しては「ア（1,10）」、
「ル（1,11）」、「タ（1,12）」、「リ（1,13）」、
「ア（1,14）」がマッチする。マッチング部２２は、こ
の位置情報に基づいて、テキスト記憶部２０に格納され
た検索対象テキストから候補文字列「アルタリア」を取
得し、これとその先頭文字の出現位置との組「アルタリ
ア（1,10）」を、ランキング部２６へ出力する。また、
置換文字列「＃ル＃リア」に対しては任意の１文字、こ
れに続く「ル（3,22）」、これに続く任意の１文字、
「リ（3,24）」、「ア（3,25）」がマッチする。マッチ
ング部２２は、この位置情報を基にテキスト記憶部２０
にアクセスして候補文字列「アル夕リア」（“夕”は漢
字）を取得し、マッチング結果として「アル夕リア（3,
21）」を出力する。また、置換文字列「アル＃＃ア」に
対しては上記第一の実施形態で述べた規則(iii)から
「ア（2,5）」、「ル（2,6）」、これに続く１文字、及
び「ア（2,8）」がマッチする。マッチング部２２はこ
の位置情報を基にテキスト記憶部２０にアクセスして候
補文字列「アル列ア」を取得し、マッチング結果として
「アル列ア（2,5）」を出力する。

【００７３】ランキング部２６は、マッチング部２２か
らマッチング結果を得ると、候補文字列のランキングを
行う。本装置では、ランキング部２６が付与するポイン
トは、誤認識許容文字が２つの場合に拡張され、その場
合に生じ得るそれぞれのケースについて定められてい
る。例えば、以下のように定めることができる。

【００７４】 (a)検索文字列と完全一致の場合：ポイント「１０
０」、 (b)１文字不一致の場合 ：ポイント 「５
０」、 (b-1)不一致の１文字が誤り文字列パターンと一致する
場合：ポイント「３０」を加算、 (c)２文字不一致の場合 ：ポイント 「１
０」、 (c-1)不一致の１文字が誤り文字列パターンと一致する
場合：ポイント「３０」を加算、 (c-2)不一致の２文字が誤り文字列パターンと一致する
場合：ポイント「６０」を加算。

【００７５】また、誤り文字列登録部２４に登録された
誤り文字列パターンには、「タリ→列」、「タ（カタカ
ナ）→夕（漢字）」 が含まれているものとする。

【００７６】ランキング部２６は、候補文字列「アルタ
リア」に対しては完全一致の場合のポイント「１００」
を付与し、「アル列ア」は２文字不一致かつ誤り文字列
「タリ→列」が誤り文字列登録部２４に登録されている
ので、１０＋６０＝７０ポイントを付与される。また、
候補文字列「アル夕リア」（“夕”は漢字）は１文字不
一致かつ誤り文字列「タ→夕」が誤り文字列登録部２４
に登録されているので、５０＋３０＝８０ポイントを付
与される。そして、ランキング部２６は、例えば、ラン
キング結果として、候補文字列とその位置情報とポイン
トの組、例えば「アルタリア（1,10,100）」、「アル列
ア（2,5,70）」、「アル夕リア（3,21,80）」を出力部
１４へ出力する。

【００７７】出力部１４は、ランキング部２６からのラ
ンキング結果を得ると、例えば、ポイントが高い順に、
候補文字列を画面表示する。また、出力部１４は、ある
値以上のポイントを得た候補文字列のみを表示してもよ
いし、ポイントが指定された範囲内にあるものをグルー
プ化して表示してもよい。

【００７８】なお、誤り文字列登録部２４を用いたラン
キングではなく、簡単に、完全一致、１文字曖昧、２文
字曖昧というランキングを行うことも可能である。

【図面の簡単な説明】

【図１】 本発明の第一の実施形態であるテキスト検索
装置の概略のブロック構成図である。

【図２】 第一の実施形態に係る検索対象テキストのイ
メージを示す模式図である。

【図３】 第一の実施形態に係る検索対象テキストのイ
ンデックスのイメージを示す模式図である。

【図４】 対象文字位置情報記憶部に格納される対象文
字位置情報のイメージを示す模式図である。

【図５】 本発明の第二の実施形態であるテキスト検索
装置の概略のブロック構成図である。

【図６】 第二の実施形態に係る検索対象テキストのイ
メージを示す模式図である。

【図７】 第二の実施形態に係る検索対象テキストのイ
ンデックスのイメージを示す模式図である。

【図８】 誤り文字列登録部に登録された誤り文字列パ
ターンの一例を示す模式図である。

【図９】 第三の実施形態に係る検索対象テキストのイ
メージを示す模式図である。

【図１０】 検索対象テキストに対して生成され、イン
デックス記憶部に格納されているインデックスのイメー
ジを示す模式図である。

【符号の説明】

２ インデックス記憶部、４ 入力部、６ 検索部、８
対象文字位置情報記憶部、１０ 検索文字列展開部、
１２，２２ マッチング部、１４ 出力部、２０ テキ
スト記憶部、２４ 誤り文字列登録部、２６ ランキン
グ部。

Claims (9)

【特許請求の範囲】
1. 【請求項１】 検索対象テキストに対し、検索文字列に
   基づいて検索処理を行うテキスト検索装置において、 前記検索文字列とその部分列との間の指定された一致度
   に応じて前記検索文字列の部分列を発生する部分列発生
   手段と、 発生された前記部分列と一致する文字列パターンを含ん
   だ候補文字列を前記検索対象テキスト中に探索する候補
   探索手段と、 を有することを特徴とするテキスト検索装置。
2. 【請求項２】 検索対象テキストから、検索文字列に一
   致する可能性を有する候補文字列を検索するテキスト検
   索装置において、 前記検索対象テキストの生成で生じうる誤り文字列パタ
   ーンを登録した誤り文字列登録部と、 前記検索文字列に基づいて前記候補文字列を探索する候
   補探索手段と、 前記候補文字列中の前記検索文字列と異なる部分に、前
   記誤り文字列登録部に登録された登録誤り文字列パター
   ンを検出する誤り文字列検出手段と、 前記候補文字列に対し前記検索文字列との一致可能性に
   応じた優先度を定める優先度付与手段と、 を有し、 前記優先度付与手段は、前記候補文字列中における前記
   登録誤り文字列パターンの検出に応じて当該候補文字列
   の前記優先度を定めること、 を特徴とするテキスト検索装置。
3. 【請求項３】 前記検索文字列とその部分列との間の指
   定された一致度に応じて前記検索文字列の部分列を発生
   する部分列発生手段を有し、 前記候補文字列は、発生された前記部分列と一致する文
   字列パターンを含んだ文字列であること、 を特徴とする請求項２記載のテキスト検索装置。
4. 【請求項４】 前記候補探索手段は、前記検索文字列と
   前記部分列との差分を構成する曖昧文字を、前記検索対
   象テキスト中の任意の１文字とみなす手段を有して前記
   探索を行うことを特徴とする請求項１又は請求項３記載
   のテキスト検索装置。
5. 【請求項５】 前記候補探索手段は、前記検索文字列と
   前記部分列との差分を構成する曖昧文字を、前記検索対
   象テキスト中の任意の２文字とみなす手段を有して前記
   探索を行うことを特徴とする請求項１又は請求項３記載
   のテキスト検索装置。
6. 【請求項６】 前記候補探索手段は、前記検索文字列と
   前記部分列との差分を構成する曖昧文字のうち連続する
   ２つを、前記検索対象テキスト中の任意の１文字とみな
   す手段を有して前記探索を行うことを特徴とする請求項
   １又は請求項３記載のテキスト検索装置。
7. 【請求項７】 前記優先度付与手段は、前記登録誤り文
   字列パターンの検出頻度に応じて前記優先度を定めるこ
   とを特徴とする請求項２又は請求項３記載のテキスト検
   索装置。
8. 【請求項８】 前記誤り文字列登録部は、さらに前記登
   録誤り文字列パターンの検出頻度を格納することを特徴
   とする請求項７記載のテキスト検索装置。
9. 【請求項９】 前記優先度に応じて前記候補文字列を表
   示する候補文字列表示手段を有することを特徴とする請
   求項２又は請求項３記載のテキスト検索装置。