JP2003288366A

JP2003288366A - 類似テキスト検索装置

Info

Publication number: JP2003288366A
Application number: JP2002090099A
Authority: JP
Inventors: Taro Fujimoto; 太郎藤本; Atsushi Arima; 淳有馬
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2002-03-28
Filing date: 2002-03-28
Publication date: 2003-10-10

Abstract

(57)【要約】【課題】複数のテキストが完全に一致していない場合で
もどの程度一致しているのかを高速に判別すること。【解決手段】たのため、本発明では、テキストが入力さ
れる入力インタフェース手段１０１と、入力されたテキ
ストに対する前処理を行う前処理手段１０３と、テキス
トに対するＮグラム要素を作成するＮグラム化手段１０
４と、複数のテキストに関するＮグラム要素の一致度を
演算する類似度演算手段１０５と、この類似度演算手段
１０５の演算結果を出力する出力インタフェース手段１
０８を具備したことを特徴とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は類似テキスト検索装
置に係り、特に複数のテキストが完全に一致していない
場合でもどの程度類似しているのかを高速に判別するも
のに関する。

【０００２】

【従来の技術】テキストに対する検索装置として、キー
ワードの完全一致検索が行われているが、これは検索者
が入力した検索キーに完全に一致するテキストのみを出
力している。しかし「テキスト」と「テクスト」のよう
に完全に一致していないものでも一致するというように
判断する「あいまい検索」が要求されている。例えばＷ
ｉｎｄｏｗｓ（登録商標）に関する表現は、個人によ
り、バージョンによりＷｉｎｄｏｗｓ−ＮＴと表現され
たりＷＩＮＮＴ４と表現されたり色々な表現が行われ
ているが、これらは類似のものであると判定することが
必要なことが多い。

【０００３】

【発明が解決しようとする課題】従来の検索装置は、検
索者が入力した検索キーに完全に一致するテキストのみ
を出力しており、高精度のあいまい検索は時間がかかる
と考えられており、検索システムとしてあまり整備され
ていなかった。

【０００４】したがって本発明の目的は、前記「Ｗｉｎ
ｄｏｗｓ−ＮＴ」や「ＷＩＮＮＴ４」のように、表記
にゆれがあるキーワードを高速に検索するための装置を
提供することである。

【０００５】

【課題を解決するための手段】本発明の原理図を図１に
示す。図１において１は類似テキスト検索装置、１０１
は入力インタフェース手段、１０３は前処理手段、１０
４はＮグラム化手段、１０５は類似度算出手段、１０８
は出力インタフェース手段である。

【０００６】本発明の前記目的は下記（１）〜（５）に
より達成される。

【０００７】（１）テキストが入力される入力インタフ
ェース手段１０１と、入力されたテキストに対する前処
理を行う前処理手段１０３と、テキストに対するＮグラ
ム要素を作成するＮグラム化手段１０４と、複数のテキ
ストに関するＮグラム要素の一致度を演算する類似度演
算手段１０５と、この類似度演算手段１０５の演算結果
を出力する出力インタフェース手段１０８を具備したこ
とを特徴とする類似テキスト検索装置。

【０００８】（２）テキストが入力される入力インタフ
ェース手段と、類似度演算対象となるテキストが保持さ
れるテキスト・データベース手段と、テキストに対する
前処理を行う前処理手段と、テキストに対するＮグラム
要素を作成するＮグラム化手段と、複数のテキストに関
するＮグラム要素の一致度を演算する類似度演算手段
と、前記一致度の高い順から演算結果を出力するソート
手段と、このソート手段のソート結果を出力する出力イ
ンタフェース手段を具備したことを特徴とする類似テキ
スト検索装置。

【０００９】（３）テキストが入力される入力インタフ
ェース手段と、類似度演算対象となるテキストが保持さ
れるテキスト・データベース手段と、テキストに対する
前処理を行う前処理手段と、テキストに対するＮの値が
異なる複数種類のＮグラム要素を作成する複数のＮグラ
ム化手段と、前記異なる複数種類のＮグラム要素につい
て、それぞれのＮグラム要素の頻度により類似度を算出
する類似度算出手段と、それぞれのＮグラム要素の頻度
により類似度を算出した値を加算する類似度加算手段
と、この類似度加算手段の出力を大きい順から出力する
ソート手段と、このソート手段のソート結果を出力する
出力インタフェース手段を具備したことを特徴とする類
似テキスト検索装置。

【００１０】（４）テキストが入力される入力インタフ
ェース手段と、類似度演算対象となるテキストが保持さ
れるテキスト・データベース手段と、テキストに対する
前処理を行う前処理手段と、テキストに対するＮグラム
要素を作成するＮグラム化手段と、テキスト・データベ
ース手段に保持されたテキストに対して作成されたＮグ
ラム要素をインデクス保持するインデクス・データベー
ス手段と、このインデクス・データベース手段に対する
アクセス手段と、複数のテキストに関するＮグラム要素
の一致度を演算する類似度演算手段と、前記一致度の高
い順から演算結果を出力するソート手段と、このソート
手段のソート結果を出力する出力インタフェース手段を
具備したことを特徴とする類似テキスト検索装置。

【００１１】（５）テキストが入力される入力インタフ
ェース手段と、類似度演算対象となるテキストが保持さ
れるテキスト・データベース手段と、テキストに対する
前処理を行う前処理手段と、テキストに対するＮの値が
異なる複数種類のＮグラム要素を作成する複数のＮグラ
ム化手段と、テキスト・データベース手段に保持された
テキストに対して作成された、異なる複数種類のＮグラ
ム要素をインデクス保持するインデクス・データベース
手段と、このインデクス・データベース手段に対するア
クセス手段と、前記異なる複数種類のＮグラム要素につ
いて、それぞれのＮグラム要素の頻度により類似度を算
出する類似度算出手段と、それぞれのＮグラム要素の頻
度により類似度を算出した値を加算する類似度加算手段
と、この類似度加算手段の出力を大きい順から出力する
ソート手段と、このソート手段のソート結果を出力する
出力インタフェース手段を具備したことを特徴とする類
似テキスト検索装置。

【００１２】これにより下記の作用効果を奏する。

【００１３】（１）テキストをそれぞれＮグラム要素を
作成してそのマッチングを行うので、表現のぶれを吸収
した形でテキストのマッチングを検索できるので、あい
まい検索を正確に実行することができる。

【００１４】（２）あらかじめ比較すべき一方のテキス
トをテキスト・データベースに保持しているので、検索
の度に比較すべき全テキストを入力する必要がなく、高
速に類似テキストを検索できる。

【００１５】（３）一方のテキストをデータベースに保
持するとともに、Ｎの値が異なる複数種類のＮグラム要
素を作成してその頻度によって類似度を演算するので、
例えばＮ＝２つまり２グラム要素の場合に助詞の部分の
一致により見かけ上の類似度の上がるようなテキストに
対しても３グラム要素の場合にはこれを抑制することが
でき、類似度の判定結果の速度及び精度を向上すること
ができる。

【００１６】（４）あらかじめテキスト・データベース
に保持していたテキストのＮグラム要素を作成し、これ
をインデクス・データベースに保持しているので、テキ
ストの比較に際し、このインデクス・データベースに保
管していたＮグラム要素を使用して入力されたテキスト
に対する類似度を算出することを高速に行うことができ
る。

【００１７】（５）入力テキストをＮの値の異なる複数
種類のＮグラム要素を作成し、またテキスト・データベ
ースに保持していたテキストについてもこれまたＮの異
なる複数種類のＮグラム要素を作成してインデクス・デ
ータベースに保持しているので、Ｎグラム要素の頻度に
よる類似度を高速に行うことができ、しかもその類似度
の精度を向上したものとすることができる。

【００１８】

【発明の実施の形態】本発明の実施の形態を説明する。

【００１９】Ａ．本発明の第一の実施の形態本発明の第一の実施の形態を図１にもとづき説明する。
図１（Ａ）は本発明の第一の実施の形態を示し、同
（Ｂ）はそのＮグラム化装置の動作説明図である。

【００２０】図１において、類似テキスト検索装置１
は、入力インタフェース手段１０１、前処理手段１０
３、Ｎグラム化手段１０４、類似度算出手段１０５、出
力インタフェース手段１０８を具備している。

【００２１】入力インタフェース手段１０１は、類似度
を検索されるテキストが入力されるものであり、いまテ
キスト「ＷｉｎＮＴ４」と「Ｗｉｎｄｏｗｓ−ＮＴ」
の類似度を求める場合、これらのテキストが入力される
ものである。そしてこの入力を行うため、例えばパーソ
ナル・コンピュータ（以下パソコンという）の如き端末
装置が接続される。

【００２２】前処理手段１０３は、テキストがアルファ
ベットの場合は大文字で統一したり、空白を除去した
り、ハイフォンを除去したり、句読点や括弧等を除去し
たり、半角文字を全角文字にするものである。

【００２３】Ｎグラム化手段１０４はテキストをＮグラ
ム化つまりＮ文字ずつの要素に分けるものである。例え
ばＷＩＮＮＴ４を２グラム化（２文字ずつの要素に分け
る）する場合の動作について、図１（Ｂ）により説明す
る。

【００２４】まずＷＩＮＮＴ４の最初の２文字ＷＩを
取る。

【００２５】次に先頭から１文字ずらして２文字取
る。これによりＩＮが取れる。

【００２６】それからさらに１文字ずらして２文字取
る。これによりＮＮが取れる。

【００２７】このような処理を繰返し行うことによりＷ
ＩＮＮＴ４を、図１（Ｂ）に示す如く、ＷＩ、ＩＮ、Ｎ
Ｎ、ＮＴ、Ｔ４に２グラム要素（バイグラム要素）とし
て分割することができる。

【００２８】類似度算出手段１０５は、２つのテキスト
の例えばバイグラム要素の一致不一致を比較して類似度
を算出するものである。例えば類似度を測りたい２つの
テキストをそれぞれバイグラム要素に分けて、その共通
集合の個数を和集合の個数で割ることにより、類似度を
算出する。図１（Ｂ）に示す如く、ＷＩＮＮＴ４とＷＩ
ＮＤＯＷＳＮＴ（登録商標）との類似度を求めるとき、
共通集合は３（ＷＩ、ＩＮ、ＮＴ）、和集合は１０（Ｗ
Ｉ、ＩＮ、ＮＮ、ＮＴ、Ｔ４、ＮＤ、ＤＯ、ＯＷ、Ｗ
Ｓ、ＳＮ）であり、この場合の２つのテキストの類似度
は０．３となる。

【００２９】また２つのテキストの長さが極端に異なる
場合は、短い方のテキストのバイグラム要素の個数で共
通集合の個数を割る方法もある。この例では短い方のテ
キストＷＩＮＮＴ４の類似度は、共通集合の個数が３、
短い方のテキストのバイグラム要素数が５のため、類似
度は０．６となる。

【００３０】出力インタフェース手段１０８は、類似度
算出手段１０５において算出された類似度を、例えば入
力インタフェース手段１０１に対しテキストを入力した
端末装置に出力するものである。

【００３１】図１の動作についてテキスト「ＷｉｎＮＴ
４」と「Ｗｉｎｄｏｗｓ−ＮＴ」の類似度を求める場合
について説明する。

【００３２】（１）まずユーザは、図示省略した端末装
置よりテキスト「ＷｉｎＮＴ４」と「Ｗｉｎｄｏｗｓ−
ＮＴ」を入力する。前処理手段１０３は、これらのテキ
ストを前処理してこれらをＷＩＮＮＴ４、ＷＩＮＤＯＷ
ＳＮＴとして、Ｎグラム化手段１０４に送出する。

【００３３】（２）この例ではＮグラム化手段１０４は
２グラム化手段として動作する例について説明する。Ｎ
グラム化手段１０４は、まずＷＩＮＮＴ４を図１（Ｂ）
に示す如く２グラム要素に断片し、得られたＷＩ、Ｉ
Ｎ、ＮＮ、ＮＴ、Ｔ４を類似度算出手段１０５に送出
し、次にＷＩＮＤＯＷＳＮＴを図１（Ｂ）に示す如く２
グラム要素に断片し、得られたＷＩ、ＩＮ、ＮＤ、Ｄ
Ｏ、ＯＷ、ＷＳ、ＳＮ、ＮＴを類似度算出手段１０５に
送出する。このとき同一テキストで同一の２グラム要素
が複数存在したとき、１つの要素のみ残し、重複した２
グラム要素を削除する。Ｎ（Ｎ≠２）グラム化でも同様
である。

【００３４】（３）類似度算出手段１０５では、これら
の２グラム要素より共通集合（ＷＩ、ＩＮ、ＮＴ）と和
集合（ＷＩ、ＩＮ、ＮＮ、ＮＴ、Ｔ４、ＮＤ、ＤＯ、Ｏ
Ｗ、ＷＳ、ＳＮ）を求める。そして共通集合の要素数３
を和集合の要素数１０で商し、得られた値０．３を出力
インタフェース１０８を経由して、前記テキストを入力
した端末装置にこれを出力、表示する。これによりユー
ザは２つのテキストの類似度が０．３であることを認識
する。

【００３５】Ｂ．本発明の第二の実施の形態本発明の第二の実施の形態を図２、図３にもとづき説明
する。図２は本発明の第二の実施の形態を示し、図３は
その動作説明図である。

【００３６】図２において、類似テキスト検索装置２
は、テキストからＮの値が異なる複数種類のＮグラム要
素を作成し、それぞれのＮグラムの頻度に対して類似度
を算出した値を加算し、その加算結果で類似度を認識す
るものである。例えばテキストを２グラム要素と３グラ
ム要素の２つの種類のものを作成し、２グラム要素で算
出した類似度と、３グラム要素で算出した類似度とを加
算し、その加算結果で類似度を認識する。

【００３７】これにより、例えばテキストが文章のよう
な場合、２グラム要素では「から」、「より」、「で
は」のような２文字の助詞が一致したとき類似度が上が
ることになるが、３グラム要素ではこのような一致を防
止できるので、類似度を精度良く算出できる。以下の説
明は２グラム化と３グラム化した場合について述べる。

【００３８】（１）まずユーザは図示省略した端末装置
よりテキスト「ＷｉｎＮＴ４」と「Ｗｉｎｄｏｗｓ−Ｎ
Ｔ」を入力する。これらのテキストは入力インタフェー
ス手段１０１を介して前処理手段１０３に入力される。
前処理手段１０３はこれらのテキストを前処理して、こ
れらをＷＩＮＮＴ４、ＷＩＮＤＯＷＳＮＴとしてＮグラ
ム化手段１０４に送出する。

【００３９】（２）Ｎグラム化手段１０４では、これら
を先ず２グラム要素に断片して、図３（Ｂ）に示すもの
を類似度算出手段１０５に出力してその２グラム要素に
おける類似度の算出を行い、（この例では３／１０）次
いで３グラム要素に断片して、図３（Ｃ）に示すものを
類似度算出手段１０５に出力してその３グラム要素にお
ける類似度の算出を行う（この例では１／１０）。

【００４０】（３）そしてこれら２グラム要素における
類似度と、３グラム要素における類似度とを類似度加算
手段１０６に送出して、これらの和を求め、これを出力
インタフェース手段１０８を経由して、前記テキストを
入力した端末装置にこれを出力、表示する。

【００４１】類似度はＮの値により、また複数種類Ｎの
値により、変化するので、各ケースに応じて類似非類似
の基準が異なるものとなる。

【００４２】なお前記の場合、Ｎグラム化手段、類似度
算出手段をそれぞれＮの種類の数だけ設けてもよく、１
個ずつ設けてもよい。複数にすれば高速化をはかること
ができ、１個にすればコスト節約をはかることができ
る。

【００４３】Ｃ．本発明の第３の実施の形態本発明の第３の実施の形態を図４にもとづき説明する。

【００４４】図４において類似テキスト検索装置３は、
類似度を算出すべき対象である複数のテキストをあらか
じめテキスト・データベース１０９に格納しておく。こ
れにより、類似度を算出する場合に、図示省略した端末
装置から複数のテキストを入力する必要はなく、１テキ
ストのみ入力すればよいので、入力コストが大幅に削減
され、高速に類似度を算出することができる。テキスト
・データベース１０９には複数のテキストが格納されて
いるので、ソート手段１０７を介してその類似度の高い
ものから順次出力される。

【００４５】（１）まずテキスト・データベース１０９
に、あらかじめ類似度の算出対象となる複数のテキスト
Ｔ₁、Ｔ₂、Ｔ₃・・・を図示省略した、入力手段から
格納しておく。

【００４６】（２）ユーザは、図示省略した端末装置よ
りテキストＴ₀を入力する。このテキストＴ₀は入力イ
ンタフェース手段１０２を経由して前処理手段１０３に
送出されて、前記前処理が行われ、Ｎグラム化手段１０
４によりＮグラム化例えば２グラム要素に断片され、類
似度算出手段１０５に送出される。

【００４７】（３）テキスト・データベース１０９で
は、まずテキストＴ₁が読み出されて、前処理手段１０
３で前処理され、Ｎグラム化手段１０４により、前記テ
キストＴ₀と同じく２グラム要素に断片され、類似度算
出手段１０５により、テキストＴ₀とＴ₁との類似度Ｓ
₁が算出され、ソート手段１０７にこれが送出される。

【００４８】（４）次にテキスト・データベース１０９
からテキストＴ₂が読み出され、同様にして類似度算出
手段１０５によりテキストＴ₀とＴ₂との類似度Ｓ₂が
算出され、ソート手段１０７に送出される。このように
してテキスト・データベース１０９からテキストＴ₃、
Ｔ₄・・・が読み出され、テキストＴ₀との類似度
Ｓ ₃、Ｓ₄・・・が算出され、ソート手段１０７に送出
される。

【００４９】（５）このようにテキスト・データベース
１０９内のすべてのテキストに対して類似度が算出され
た後に、ソート手段１０７はそれらの類似度を高い順に
ソートして、これらを全部、あるいはあらかじめ定めら
れた数だけ出力し、出力インタフェース手段１０８を経
由して、前記テキストＴ₀を入力したユーザの端末装置
に対しこれらを出力する。

【００５０】なお前記説明では、ユーザから入力された
テキストＴ₀に対する前処理手段、Ｎグラム化手段を、
テキスト・データベース１０９から読み出したテキスト
Ｔ₁、Ｔ₂・・・に対する前処理手段、Ｎグラム化手段
とを別のものを使用する例について記載したが、勿論こ
れらは同一のものを使用してもよい。

【００５１】Ｄ．本発明の第４の実施の形態本発明の第４の実施の形態を図５に示す。図５において
類似テキスト検索装置４では、ユーザが入力したテキス
トＴ₀及びテキスト・データベース１０９に格納されて
いるテキストＴ₁、Ｔ₂・・・をそれぞれＮの値の異な
る複数種類のＮグラム要素を作成し、類似度を算出し、
類似度を加算して類似の程度を認識するものである。

【００５２】図５の動作について説明する。

【００５３】（１）まずテキスト・データベース１０９
に、あらかじめ類似度の算出対象となる複数のテキスト
Ｔ₁、Ｔ₂、Ｔ₃・・・を図示省略した入力手段から格
納しておく。

【００５４】（２）ユーザは、図示省略した端末装置よ
りテキストＴ₀を入力する。このテキストＴ₀は入力イ
ンタフェース手段１０２を経由して前処理手段１０３に
送出されて、前記前処理が行われ、Ｎグラム化手段１０
４、１０４によりＮの値の異なる複数種類のＮグラム要
素、例えば２グラム要素及び３グラム要素に断片され、
それぞれ類似度算出装置１０５、１０５に送出される。

【００５５】（３）テキスト・データベース１０９で
は、先ずテキストＴ₁が読み出されて、前処理手段１０
３で前処理され、Ｎグラム化手段１０４、１０４によ
り、前記テキストＴ₀と同じく２グラム要素及び３グラ
ム要素に断片され、類似度算出手段１０５、１０５に送
出され、類似度算出手段１０５、１０５で２グラム要素
及び３グラム要素にもとづきテキストＴ₀とＴ₁の類似
度Ｓ₁₂、Ｓ₁₃が算出され、これらが類似度加算手段１０
６に送出されてその和（Ｓ₁₂＋Ｓ₁₃）が求められ、ソー
ト手段１０７に送出される。

【００５６】（４）次にテキスト・データベース１０９
からテキストＴ₂が読み出され、同様にして類似度算出
手段１０５、１０５によりテキストＴ₀とＴ₂の２グラ
ム要素及び３グラム要素にもとづき類似度Ｓ₂₂、Ｓ₂₃が
算出され、これらが類似度加算手段１０６に送出されて
その和（Ｓ₂₂＋Ｓ₂₃）が求められ、ソート手段１０７に
送出される。

【００５７】（５）このようにしてテキスト・データベ
ース１０９からテキストＴ₃、Ｔ₄・・・が読み出さ
れ、テキストＴ₀との２グラム要素及び３グラム要素に
もとづく類似度（Ｓ₃₂、Ｓ₃₃）、（Ｓ₄₂、Ｓ₄₃）・・・
が算出され、これらが類似度加算手段１０６に送出され
てその和（Ｓ₃₂＋Ｓ₃₃）、（Ｓ₄₂＋Ｓ₄₃）・・・が得ら
れ、ソート手段１０７に送出される。

【００５８】（６）このようにテキスト・データベース
１０９内の全てのテキストに対して２グラム要素、３グ
ラム要素の類似度の和が算出された後に、ソート手段１
０７はこれらの類似度の和の値の高い順にソートしてこ
れらを全部、あるいはあらかじめ定められた数だけ出力
し、出力インタフェース手段１０８を経由して、前記テ
キストＴ₀を入力したユーザの端末装置に対しこれらを
出力する。

【００５９】なお前記説明では、ユーザから入力された
テキストＴ₀に対する前処理手段、Ｎグラム化手段を、
テキスト・データベース１０９から読み出したテキスト
Ｔ₁、Ｔ₂・・・に対する前処理手段、Ｎグラム化手段
とを別のものを使用する例について記載したが、これら
は同一のものを使用してもよい。またＮグラム化手段及
び類似度算出手段をこれまた同一のものを使用してもよ
い。

【００６０】Ｅ．本発明の第５の実施の形態本発明の第５の実施の形態を図６〜図９にもとづき説明
する。図６は本発明の第５の実施の形態を示し、図７は
そのインデクス・データベースの説明図、図８はインデ
クス・データベースにデータを登録するときの動作説明
図、図９は検索・類似度算出のときの動作説明図であ
る。

【００６１】図６において、類似テキスト検索装置５で
は、インデクス・データベース１１１には検索対象とな
るテキストＴ₁、Ｔ₂・・・のＮグラム要素と、テキス
トとの関係が例えば図７（Ｄ）に示す如く、テーブル化
されて格納されている。

【００６２】検索対象となるテキストＴ₁、Ｔ₂、Ｔ₃
が、図７（Ａ）に示す如く、ＷｉｎｄｏｗｓＮＴ、Ｗｉ
ｎｄｏｗｓ２０００、ＷｉｎＭＥのとき、図７（Ｂ）に
示す如く、例えば２グラム化され、同（Ｄ）に示す如
く、各２グラム要素ＷＩ、ＩＮ・・・と、その属するテ
キスト名Ｔ₁、Ｔ₂、Ｔ₃が格納されている。なおテキ
ストＴ₂では２グラム要素として００が２個作成される
が、同一要素については１個のみ残すので、図７（Ｄ）
の如きものとなる。そしてｔ₁はテキストＴ₁の２グラ
ム要素の数（この場合はｔ₁＝８）、ｔ₂はテキストＴ
₂の２グラム要素の数（この場合はｔ₂＝９）、ｔ₃は
テキストＴ₃の２グラム要素の数（この場合はｔ₃＝
４）を示す。

【００６３】そして図７（Ａ）に示すテキストＴ₀（Ｗ
ｉｎＮＴ４）との類似度を求めるとき、テキストＴ₀の
２グラム要素をインデクス・データベース１１１に格納
されているテキストＴ₁、Ｔ₂、Ｔ₃の２グラム要素と
照合し、その一致数を求める。このときテキストＴ₀の
みに存在する２グラム要素、ＮＮ、Ｔ４をインデクス・
データベース１１１に登録し、他のテキストとの照合に
備える。これによりテキストＴ₀とＴ₁は３／１０、Ｔ
₀とＴ₂は２／１２、Ｔ₀とＴ₃は２／７という類似度
を得ることができる。このように、テキストＴ₁、
Ｔ₂、Ｔ₃の２グラム要素及びその数（頻度ともいう）
ｔ₁、ｔ₂、ｔ₃が登録されているので類似度の演算を
高速に行うことができる。

【００６４】なおインデクス・データベース１１１に
は、図７（Ｃ）に示す如く、テキストＴ₁、Ｔ₂、Ｔ₃
・・・のＮグラム要素（この例では２グラム要素）を格
納してもよい。

【００６５】図６の動作を、図８に示すインデクス・デ
ータベース１１１にデータを登録する場合と、図９に示
す類似度算出の場合について説明する。

【００６６】（１）データ登録について、Ｓ１．まずテキスト・データベース１０９に、あらかじ
め類似度の算出対象となる図７（Ａ）に示す如き、複数
のテキストＴ₁、Ｔ₂、Ｔ₃・・・を図示省略した入力
手段から格納する。それからリストから得た最初のテキ
ストＴ₁を前処理手段１０３に送出し、小文字の大字化
や空白、ハイフォンの削除等の前処理を行ってキーワー
ドクリーニングする。

【００６７】Ｓ２．このように前処理されたテキストを
Ｎグラム化手段１０４に送り、例えば２グラム要素に断
片される。

【００６８】Ｓ３．同一テキストにおいて同じ２グラム
要素が存在したとき、重複した２グラム要素を削除して
１つにする。

【００６９】Ｓ４．このようにして得たテキストＴ₁の
２グラム要素を、データベース・アクセスインタフェー
ス手段１１０によりテキスト名Ｔ₁と２グラム要素数ｔ
₁とともにインデクス・データベース１１１に格納す
る。このようにして、テキスト・データベース１０９の
リストより得た他のテキストＴ₂、Ｔ₃についても同様
の処理を行い、図７（Ｄ）に示す如く、インデクス・デ
ータベース１１１が作成される。

【００７０】（２）類似度算出についてＳ１０．ユーザが、図示省略した端末装置より図７
（Ａ）に示すテキストＴ₀を入力する。この入力された
テキストＴ₀（入力キーワード）は、入力インタフェー
ス手段１０２を経由して前処理手段１０３に送出されて
前処理が行われ、入力キーワードがクリーニングされ
る。

【００７１】Ｓ１１．このように前処理されたテキスト
Ｔ₀は、Ｎグラム化手段１０４により、前記テキストＴ
₁、Ｔ₂、Ｔ₃と同様に、図７（Ｂ）に示す如く、２グ
ラム要素に断片される。

【００７２】Ｓ１２．この場合、２グラム要素に重複す
るものがあれば、これらを１個だけ残して他の重複２グ
ラム要素を削除する。

【００７３】Ｓ１３．このようにして得られた入力テキ
ストＴ₀の２グラム要素がＮグラム化手段１０４から類
似度算出手段１０５に入力されると、類似度算出手段１
０５は、データベース・アクセスインタフェース手段１
１０を介してインデクス・データベース１１１より、図
７（Ｄ）に示す、テキストＴ₁のレコードを取得する。

【００７４】Ｓ１４．そして類似度を計算する。これに
よりテキストＴ₀とＴ₁との類似度Ｓ₁＝３／１０が得
られる。

【００７５】Ｓ１５．このようにしてリストに記入され
た他の全テキストＴ₂、Ｔ₃とテキストＴ₀との類似度
Ｓ₂、Ｓ₃が算出され、Ｓ₂＝２／１２、Ｓ₃＝２／７
が得られる。

【００７６】Ｓ１６．これらの類似度Ｓ₁、Ｓ₂、Ｓ₃
はソート手段１０７に送出される。ソート手段１０７は
これらの類似度をその高い順にソートして、これらを出
力インタフェース手段１０８を経由して、前記テキスト
Ｔ₀を入力したユーザの端末装置に対しこれらを出力す
る。

【００７７】なお前記説明ではユーザから入力されたテ
キストＴ₀に対する前処理手段、Ｎグラム化手段を、テ
キスト・データベース１０９から読み出したテキストＴ
₁、Ｔ₂・・・に対する前処理手段、Ｎグラム化手段と
別のものを使用する例について記載したが、これらは同
一のものを使用してもよい。

【００７８】Ｆ．本発明の第６の実施の形態本発明の第６の実施の形態を図１０にもとづき説明す
る。図１０において、テキスト類似検索装置６におい
て、ユーザが入力したテキストＴ₀及びテキスト・デー
タベース１０９に格納されているテキストＴ₁、Ｔ₂・
・・を、それぞれＮの値の異なる複数種類のＮグラム要
素を作成し、類似度を算出し、類似度を加算して類似の
程度を認識するものである。またインデクス・データベ
ース１１１もＮの値の異なる複数種類のＮグラム要素用
に複数用意されている。

【００７９】（１）まずテキスト・データベース１０９
に、あらかじめ類似度の算出対象となる、図７（Ａ）に
示す如き、複数のテキストＴ₁、Ｔ₂、Ｔ₃を図示省略
した入力手段から格納する。それから最初のテキストＴ
₁を前処理手段１０３に送出し、前処理を行ったのち、
Ｎグラム化手段１０４、１０４によりＮの値の異なる複
数種類のＮグラム要素、例えば２グラム要素及び３グラ
ム要素に断片され、それぞれデータベース・アクセスイ
ンタフェース手段１１０を介してＮの値の異なる複数種
類のインデクス・データベース１１１、１１１に、格納
される。テキストＴ₂、Ｔ₃についても同様な処理が行
われ、図７（Ｄ）に示す如く、格納される。

【００８０】（２）ユーザは、図示省略した端末装置よ
りテキストＴ₀を入力する。このテキストＴ₀は入力イ
ンタフェース手段１０２を経由して前処理手段１０３に
送出されて、前記前処理が行われ、Ｎグラム化手段１０
４、１０４によりＮの値の異なる複数種類のＮグラム要
素、例えば２グラム要素及び３グラム要素に断片され、
それぞれ類似度算出装置１０５、１０５に送出される。

【００８１】（３）インデクス・データベース１１１、
１１１では先ずテキストＴ₁に対する２グラム要素及び
３グラム要素が読み出され、テキストＴ₀に対する２グ
ラム要素及び３グラム要素と、類似度算出手段１０５、
１０５において２グラム要素同士、３グラム要素同士で
類似度の算出を行い、テキストＴ₀とＴ₁の２グラム要
素の類似度Ｓ₁₂、３グラム要素の類似度Ｓ₁₃が算出さ
れ、これらが類似度加算手段１０６に送出されてその和
（Ｓ₁₂＋Ｓ₁₃）が求められ、ソート手段１０７に送出さ
れる。

【００８２】（４）次にインデクス・データベース１１
１、１１１よりテキストＴ₂に対する２グラム要素及び
３グラム要素が読み出されて同様にして類似度算出手段
１０５、１０５によりテキストＴ₀とＴ₂の２グラム要
素及び３グラム要素にもとづき類似度Ｓ₂₂、Ｓ₂₃が算出
され、これらが類似度加算手段１０６に送出されてその
和（Ｓ₂₂＋Ｓ₂₃）が求められ、ソート手段１０７に送出
される。このようにしてテキストＴ₀とＴ₃との２グラ
ム要素及び３グラム要素にもとづき類似度Ｓ₃₂、Ｓ₃₃が
算出されて類似度加算手段１０６においてその和（Ｓ₃₂
＋Ｓ₃₃）が求められソート手段１０７に送出される。

【００８３】（５）ソート手段１０７は類似度加算手段
１０６から送出された類似度の和（Ｓ₁₂＋Ｓ₁₃）、（Ｓ
₂₂＋Ｓ₂₃）、（Ｓ₃₂＋Ｓ₃₃）の値が高い順にソートし
て、これらをソート順に出力インタフェース手段１０８
を経由して、前記テキストＴ₀を入力したユーザの端末
装置に出力する。

【００８４】なお前記説明では、ユーザから入力された
テキストＴ₀に対する前処理手段、Ｎグラム化手段を、
テキスト・データベース１０９から読み出したテキスト
Ｔ₁、Ｔ₂・・・に対する前処理手段、Ｎグラム化手段
を別のものを使用する例について記載したが、これらは
同一のものを使用してもよい。またＮグラム化手段及び
類似度算出手段インデクス・データベースもこれまた同
一のものを使用してもよい。同一機能のものは同一のも
のを使用してもよい。

【００８５】なお前記説明ではテキストがプログラム名
等で記載された例について説明したが、本発明はこれに
限定されるものではない。日本語の文書でも同様に適用
することができる。例えば書籍検索システムの場合、本
の正しい書名を忘れた場合でも、その一部である有名な
文書を入力することにより書名候補を得ることができ
る。

【００８６】ある特定の検索対象に対してあいまい検索
を行うことにより、表記のゆれや入力ミスなどを吸収し
た検索を行うことができる。インデクス・データベース
に検索対象の前処理データを入れておくことにより、検
索者が入力してからの応答速度を高めることができる。

【００８７】また２テキストの長さが極端に異なる場合
は短い方のテキストのＮグラム要素の個数で共通のＮグ
ラム要素を商し、類似度を求めることができる。これに
より、従来行われていた最長部分列の長さによる類似度
計算に比べ、高速に類似度計算が可能である。

【００８８】本発明を検索エンジンに適用する際にさら
に高速化するために、予めデータとして保持されている
テキストに対し、前処理、Ｎグラム化、重複Ｎグラム要
素削除等の処理を行ったものを蓄えておくことで、高速
化を図ることができる。

【００８９】本発明の実施の形態を以下に付記する。

【００９０】（付記１）テキストが入力される入力イン
タフェース手段と、入力されたテキストに対する前処理
を行う前処理手段と、テキストに対するＮグラム要素を
作成するＮグラム化手段と、複数のテキストに関するＮ
グラム要素の一致度を演算する類似度演算手段と、この
類似度演算手段の演算結果を出力する出力インタフェー
ス手段を具備したことを特徴とする類似テキスト検索装
置。

【００９１】（付記２）テキストが入力される入力イン
タフェース手段と、入力されたテキストに対する前処理
を行う前処理手段と、テキストに対するＮの値が異なる
Ｎグラム要素を作成するＮグラム化手段と、複数のテキ
ストに関するＮグラム要素の一致度をＮグラムの頻度に
より演算する類似度演算手段と、この類似度演算手段の
演算結果を出力する出力インタフェース手段を具備した
ことを特徴とする類似テキスト検索装置。

【００９２】（付記３）テキストが入力される入力イン
タフェース手段と、類似度演算対象となるテキストが保
持されるテキスト・データベース手段と、テキストに対
する前処理を行う前処理手段と、テキストに対するＮグ
ラム要素を作成するＮグラム化手段と、複数のテキスト
に関するＮグラム要素の一致度を演算する類似度演算手
段と、前記一致度の高い順から演算結果を出力するソー
ト手段と、このソート手段のソート結果を出力する出力
インタフェース手段を具備したことを特徴とする類似テ
キスト検索装置。

【００９３】（付記４）テキストが入力される入力イン
タフェース手段と、類似度演算対象となるテキストが保
持されるテキスト・データベース手段と、テキストに対
する前処理を行う前処理手段と、テキストに対するＮの
値が異なる複数種類のＮグラム要素を作成する複数のＮ
グラム化手段と、前記異なる複数種類のＮグラム要素に
ついて、それぞれのＮグラム要素の頻度により類似度を
算出する類似度算出手段と、それぞれのＮグラム要素の
頻度により類似度を算出した値を加算する類似度加算手
段と、この類似度加算手段の出力を大きい順から出力す
るソート手段と、このソート手段のソート結果を出力す
る出力インタフェース手段を具備したことを特徴とする
類似テキスト検索装置。

【００９４】（付記５）テキストが入力される入力イン
タフェース手段と、類似度演算対象となるテキストが保
持されるテキスト・データベース手段と、テキストに対
する前処理を行う前処理手段と、テキストに対するＮグ
ラム要素を作成するＮグラム化手段と、テキスト・デー
タベース手段に保持されたテキストに対して作成された
Ｎグラム要素をインデクス保持するインデクス・データ
ベース手段と、このインデクス・データベース手段に対
するアクセス手段と、複数のテキストに関するＮグラム
要素の一致度を演算する類似度演算手段と、前記一致度
の高い順から演算結果を出力するソート手段と、このソ
ート手段のソート結果を出力する出力インタフェース手
段を具備したことを特徴とする類似テキスト検索装置。

【００９５】（付記６）テキストが入力される入力イン
タフェース手段と、類似度演算対象となるテキストが保
持されるテキスト・データベース手段と、テキストに対
する前処理を行う前処理手段と、テキストに対するＮの
値が異なる複数種類のＮグラム要素を作成する複数のＮ
グラム化手段と、テキスト・データベース手段に保持さ
れたテキストに対して作成された、異なる複数種類のＮ
グラム要素をインデクス保持するインデクス・データベ
ース手段と、このインデクス・データベース手段に対す
るアクセス手段と、前記異なる複数種類のＮグラム要素
について、それぞれのＮグラム要素の頻度により類似度
を算出する類似度算出手段と、それぞれのＮグラム要素
の頻度により類似度を算出した値を加算する類似度加算
手段と、この類似度加算手段の出力を大きい順から出力
するソート手段と、このソート手段のソート結果を出力
する出力インタフェース手段を具備したことを特徴とす
る類似テキスト検索装置。

【００９６】

【発明の効果】本発明により下記の効果を奏することが
できる。

【００９７】（１）テキストをそれぞれＮグラム要素を
作成してそのマッチングを行うので、表現のぶれを吸収
した形でテキストのマッチングを検索できるので、あい
まい検索を正確に実行することができる。

【００９８】（２）あらかじめ比較すべき一方のテキス
トをテキスト・データベースに保持しているので、検索
の度に比較すべき全テキストを入力する必要がなく、高
速に類似テキストを検索できる。

【００９９】（３）一方のテキストをデータベースに保
持するとともに、Ｎの値が異なる複数種類のＮグラム要
素を作成してその頻度によって類似度を演算するので、
例えばＮ＝２つまり２グラム要素の場合に助詞の部分の
一致により見かけ上の類似度の上がるようなテキストに
対しても３グラム要素の場合にはこれを抑制することが
でき、類似度の判定結果の速度及び精度を向上すること
ができる。

【０１００】（４）あらかじめテキスト・データベース
に保持していたテキストのＮグラム要素を作成し、これ
をインデクス・データベースに保持しているので、テキ
ストの比較に際し、このインデクス・データベースに保
管していたＮグラム要素を使用して入力されたテキスト
に対する類似度を算出することを高速に行うことができ
る。

【０１０１】（５）入力テキストをＮの値の異なる複数
種類のＮグラム要素を作成し、またテキスト・データベ
ースに保持していたテキストについてもこれまたＮの異
なる複数種類のＮグラム要素を作成してインデクス・デ
ータベースに保持しているので、Ｎグラム要素の頻度に
よる類似度を高速に行うことができ、しかもその類似度
の精度を向上したものとすることができる。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態である。

【図２】本発明の第２の実施の形態である。

【図３】本発明の第２の実施の形態の動作説明図であ
る。

【図４】本発明の第３の実施の形態である。

【図５】本発明の第４の実施の形態である。

【図６】本発明の第５の実施の形態である。

【図７】インデクス・データベースの説明図である。

【図８】インデクス・データベースにデータを登録する
ときの動作説明図である。

【図９】検索・類似度算出のときの動作説明図である。

【図１０】本発明の第６の実施の形態である。

【符号の説明】

１〜６類似テキスト検索装置１０１、１０２入力インタフェース手段１０３前処理手段１０４Ｎグラム化手段１０５類似度算出手段１０６類似度加算手段１０７ソート手段１０８出力インタフェース手段１０９テキスト・データベース１１０データベース・アクセスインタフェース手段１１１インデクス・データベース

Claims

【特許請求の範囲】

【請求項１】テキストが入力される入力インタフェース
手段と、入力されたテキストに対する前処理を行う前処理手段
と、テキストに対するＮグラム要素を作成するＮグラム化手
段と、複数のテキストに関するＮグラム要素の一致度を演算す
る類似度演算手段と、この類似度演算手段の演算結果を出力する出力インタフ
ェース手段を具備したことを特徴とする類似テキスト検
索装置。
【請求項２】テキストが入力される入力インタフェース
手段と、類似度演算対象となるテキストが保持されるテキスト・
データベース手段と、テキストに対する前処理を行う前処理手段と、テキストに対するＮグラム要素を作成するＮグラム化手
段と、複数のテキストに関するＮグラム要素の一致度を演算す
る類似度演算手段と、前記一致度の高い順から演算結果を出力するソート手段
と、このソート手段のソート結果を出力する出力インタ
フェース手段を具備したことを特徴とする類似テキスト
検索装置。
【請求項３】テキストが入力される入力インタフェース
手段と、類似度演算対象となるテキストが保持されるテキスト・
データベース手段と、テキストに対する前処理を行う前処理手段と、テキストに対するＮの値が異なる複数種類のＮグラム要
素を作成する複数のＮグラム化手段と、前記異なる複数種類のＮグラム要素について、それぞれ
のＮグラム要素の頻度により類似度を算出する類似度算
出手段と、それぞれのＮグラム要素の頻度により類似度を算出した
値を加算する類似度加算手段と、この類似度加算手段の出力を大きい順から出力するソー
ト手段と、このソート手段のソート結果を出力する出力インタフェ
ース手段を具備したことを特徴とする類似テキスト検索
装置。
【請求項４】テキストが入力される入力インタフェース
手段と、類似度演算対象となるテキストが保持されるテキスト・
データベース手段と、テキストに対する前処理を行う前処理手段と、テキストに対するＮグラム要素を作成するＮグラム化手
段と、テキスト・データベース手段に保持されたテキストに対
して作成されたＮグラム要素をインデクス保持するイン
デクス・データベース手段と、このインデクス・データベース手段に対するアクセス手
段と、複数のテキストに関するＮグラム要素の一致度を演算す
る類似度演算手段と、前記一致度の高い順から演算結果を出力するソート手段
と、このソート手段のソート結果を出力する出力インタフェ
ース手段を具備したことを特徴とする類似テキスト検索
装置。
【請求項５】テキストが入力される入力インタフェース
手段と、類似度演算対象となるテキストが保持されるテキスト・
データベース手段と、テキストに対する前処理を行う前処理手段と、テキストに対するＮの値が異なる複数種類のＮグラム要
素を作成する複数のＮグラム化手段と、テキスト・データベース手段に保持されたテキストに対
して作成された、異なる複数種類のＮグラム要素をイン
デクス保持するインデクス・データベース手段と、このインデクス・データベース手段に対するアクセス手
段と、前記異なる複数種類のＮグラム要素について、それぞれ
のＮグラム要素の頻度により類似度を算出する類似度算
出手段と、それぞれのＮグラム要素の頻度により類似度を算出した
値を加算する類似度加算手段と、この類似度加算手段の出力を大きい順から出力するソー
ト手段と、このソート手段のソート結果を出力する出力インタフェ
ース手段を具備したことを特徴とする類似テキスト検索
装置。