(57)【特許請求の範囲】
【請求項１】
複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成する生成部と、
前記リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、前記リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割する分割部と、
前記複数のブロックの各々についてハッシュ値を求める算出部と、
前記算出部が求めたハッシュ値を、文字列間で比較する比較部と、
を有し、
前記複数の特徴要素の一部は、前記文字列内での出現順序に従って抽出された複数の特徴要素、または、連続する複数の特徴要素である
文書検査装置。
【請求項２】
前記分割部は、
前記複数の特徴要素の一部から算出したハッシュ値に対して実行した演算処理の結果が所定条件を満たす場合に前記リスト内に区切りを設定することにより、前記リストを前記複数のブロックに分割する、
請求項１記載の文書検査装置。
【請求項３】
前記演算処理は、ハッシュ値を所定の値で除して剰余を求める演算処理であり、
前記所定条件は、前記剰余が所定の範囲に含まれるという条件を含む
請求項２記載の文書検査装置。
【請求項４】
前記分割部は、
前記連続する複数の特徴要素のうち最初の特徴要素の前、又は、前記連続する複数の特徴要素のうち最後の特徴要素の後に前記区切りを設定する
請求項１記載の文書検査装置。
【請求項５】
前記算出部は、
前記ブロックに含まれる特徴要素の数が閾値未満である場合、当該ブロックのハッシュ値を前記比較部による比較の対象から除外する、
請求項１乃至４のいずれか１つ記載の文書検査装置。
【請求項６】
コンピュータが、
複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成し、
前記リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、前記リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割し、
前記複数のブロックの各々についてハッシュ値を求め、
求められた前記ハッシュ値を、文字列間で比較する、
処理を実行し、
前記複数の特徴要素の一部は、前記文字列内での出現順序に従って抽出された複数の特徴要素、または、連続する複数の特徴要素である
文書検査方法。
【請求項７】
コンピュータに、
複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成し、
前記リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、前記リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割し、
前記複数のブロックの各々についてハッシュ値を求め、
求められた前記ハッシュ値を、文字列間で比較する、
処理を実行させ、
前記複数の特徴要素の一部は、前記文字列内での出現順序に従って抽出された複数の特徴要素、または、連続する複数の特徴要素である
文書検査プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書の類似性を検証する技術に関する。
【背景技術】
【０００２】
或るテキストデータが別のテキストデータから流用されたか否かは、テキストデータの特徴量を比較することで検知することができる。特徴量とは、テキストデータの特徴に相当するデータのことであり、そのテキストデータから抽出される。
【０００３】
特徴量を使用すれば、例えば、機密データの持ち出しを効率的に検知することができる。具体的には、機密データの特徴量を予め登録しておき、機密データの特徴量と、持ち出したことが疑われるデータの特徴量とを比較することで、持ち出しが行われたことを効率的に検知できる。
【０００４】
特徴量を使用したデータの比較に関しては、以下のような技術が知られている。具体的には、或る文献は、通信データに含まれるキー文から算出したハッシュコードと、秘密文書に含まれる文から算出したハッシュコードとに基づき、通信データに秘密情報が含まれるか判定する技術を開示する。この技術によれば、ハッシュコードの一致を判定することによって流用を検知できるため、処理が高速化される。一方で、文単位での比較を行うため、文章の形式の相違（例えば、句読点或いは空白の有無など）から影響を受けやすく、検知漏れが発生しやすい。
【０００５】
また、或る文献は、テキストデータにおけるキーワードから算出したハッシュ値を比較することによって文書の類似性を判定する技術を開示する。この技術においては、キーワード単位での比較を行うため、文章の形式の相違から影響を受けにくく、検知漏れが発生しにくい。また、使用するキーワードの数を変更することで、文書毎に算出される特徴量のサイズ（ここでは、ハッシュ値の合計サイズ）を容易に変更することができる。一方で、キーワード単位の比較だけでは本当に流用が行われたか判定できず、他に類似度を計算する処理等を行うことになるため、処理に時間がかかる。
【０００６】
その他の文献に記載の技術も、上記文献に記載の技術と同様、総合的に優れた検知技術であるとは言えない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−０６５８３７号公報
【特許文献２】特開２０１０−１８２２３８号公報
【特許文献３】特開２０１０−２３１７６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従って、本発明の目的は、１つの側面では、高精度で高速に文書の類似性を検証するための技術を提供することである。
【課題を解決するための手段】
【０００９】
本発明に係る文書検査装置は、複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成する生成部と、リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割する分割部と、複数のブロックの各々についてハッシュ値を求める算出部と、算出部が求めたハッシュ値を、文字列間で比較する比較部とを有する。
【発明の効果】
【００１０】
１つの側面では、高精度で高速に文書の類似性を検証できるようになる。
【図面の簡単な説明】
【００１１】
【図１】図１は、第１の実施の形態における情報処理装置の機能ブロック図である。
【図２】図２は、文書データ格納部に格納されるデータの一例を示す図である。
【図３】図３は、第１の実施の形態におけるメインの処理フローを示す図である。
【図４】図４は、リスト格納部に格納されるリストの一例を示す図である。
【図５】図５は、サブリスト格納部に格納されるリストの一例を示す図である。
【図６】図６は、特徴データ格納部に格納されるデータの一例を示す図である。
【図７】図７は、文書のデータ及び文書ＩＤの一例を示す図である。
【図８】図８は、特徴データ格納部に格納されるデータ一例を示す図である。
【図９】図９は、文書のデータ及び文書ＩＤの一例を示す図である。
【図１０】図１０は、抽出部が実行する処理の処理フローを示す図である。
【図１１】図１１は、抽出結果格納部に格納されるデータの一例を示す図である。
【図１２】図１２は、第２の実施の形態における文書検査装置の機能ブロック図である。
【図１３】図１３は、第２の実施の形態におけるメインの処理フローを示す図である。
【図１４】図１４は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１２】
特徴量は、精度面および効率面の両方から評価される。
【００１３】
精度面においては、特徴量のロバスト性が評価される。ロバスト性とは、たとえ生データが完全に一致しなくても流用が行われたことを検知できる性質のことであり、現実的には、特徴量がある程度のロバスト性を備えることが好ましい。例えばビジネス文書の場合、論文形式においては文の区切りに句点が使われることが多いが、スライド形式においては文単位で箇条書きにされることが多い。従って、文の区切りの方法によらず流用を検知できる程度のロバスト性を備えた特徴量であることが好ましい。また、機械的なファイルフォーマット変換（例えば、ＰＤＦ（Portable Document Format）化など）をすると、文の出現順序が変わったり、空白文字が増えたりする場合があるが、そういった場合においても流用を検知できる程度のロバスト性を備えることが好ましい。
【００１４】
効率面においては、比較効率及びサイズ調整のし易さが評価される。比較効率とは、或るテキストデータが別のどのテキストデータから流用されたものであるか決定する際の効率のことであり、比較効率が良いほど決定までに要する時間が短い。サイズ調整のし易さとは、特徴量のサイズの変更のし易さのことである。たとえば、特徴量のサイズを元のテキストデータのサイズの約１割にしたい場合、容易に実現できることが好ましい。
【００１５】
以下に示す実施の形態においては、ロバスト性、比較効率、及びサイズ調整という３つの評価観点において総合的に優れた特徴量をテキストデータから抽出する方法及び特徴量の比較方法について説明する。
【００１６】
［実施の形態１］
図１に、第１の実施の形態における情報処理装置１の機能ブロック図を示す。情報処理装置１は、文書データ格納部１０１と、リスト生成部１０３と、リスト格納部１０５と、サブリスト生成部１０７と、サブリスト格納部１０９と、登録部１１１と、特徴データ格納部１１３と、抽出部１１５と、抽出結果格納部１１７とを含む。
【００１７】
リスト生成部１０３は、文書データ格納部１０１に格納されたデータに基づき処理を実行し、処理結果をリスト格納部１０５に格納する。サブリスト生成部１０７は、リスト格納部１０５に格納されたデータに基づき処理を実行し、処理結果をサブリスト格納部１０９に格納する。登録部１１１は、サブリスト格納部１０９に格納されたデータに基づき処理を実行し、処理結果を特徴データ格納部１１３に格納する。抽出部１１５は、特徴データ格納部１１３に格納されたデータに基づき処理を実行し、処理結果を抽出結果格納部１１７に格納する。
【００１８】
図２に、文書データ格納部１０１に格納されるデータの一例を示す。図２の例では、或る文書のデータ及び文書ＩＤ（IDentifier）が格納される。図２の例では１つの文書についてデータが格納されているが、文書データ格納部１０１には複数の文書についてデータが格納されてもよい。文書のデータは、文書ＩＤによって識別される。文書のデータは、テキストデータ及びその他のメタデータ等を含む。
【００１９】
次に、図３乃至図１１を用いて、情報処理装置１が実行する処理について説明する。処理が開始される前に、リスト格納部１０５に格納されたデータ及びサブリスト格納部１０９に格納されたデータは削除されるものとする。
【００２０】
まず、リスト生成部１０３は、情報処理装置１のユーザから文書のデータ及び文書ＩＤの入力を受け付け、文書データ格納部１０１に格納する（図３：ステップＳ１）。文書ＩＤは、文書を特定できるデータであればよく、例えば、ファイルパス、日時、ユーザ名、及びファイル名といったデータを組み合わせたデータである。
【００２１】
リスト生成部１０３は、ステップＳ１において文書データ格納部１０１に格納された文書のデータからテキストデータを抽出する（ステップＳ３）。図２の例であれば、枠内における「照明から照射する・・・実現します。」という文章のデータがテキストデータに該当する。テキストデータの抽出には、例えばソフトウエア「Apache Tika」を利用することができる。なお、テキストデータを抽出する技術はよく知られているので、ここでは詳細な説明を省略する。
【００２２】
リスト生成部１０３は、ステップＳ３において抽出されたテキストデータに対して形態素解析を行い、特徴要素を抽出する（ステップＳ５）。本実施の形態においては、特徴要素は単語であり、好ましくは名詞である。
【００２３】
リスト生成部１０３は、ステップＳ５において抽出された特徴要素を含むリストを生成し、リスト格納部１０５に格納する（ステップＳ７）。図４に、リスト格納部１０５に格納されるリストの一例を示す。図４の例では、テキストデータに含まれる名詞が、出現する順序どおりに格納されている。
【００２４】
リスト格納部１０５にリストが格納されると、サブリスト生成部１０７は、区切りの前におけるｎ個の特徴要素について算出したハッシュ値の法（除数とも呼ばれる）ｍに関する剰余がｒ未満となるように、リスト内の区切りの位置を決定する（ステップＳ９）。これにより、リストから１又は複数のサブリストが生成される。サブリスト生成部１０７は、生成されたサブリストをサブリスト格納部１０９に格納する。
【００２５】
ここで、ｍ及びｎは２以上の自然数であり、ｒは０＜ｒ＜ｍを満たす自然数である。例として、ｎ＝４、ｍ＝１６、ｒ＝１である場合に区切りの位置を決定することを考える。ハッシュ関数ｈ０（ｅ１，ｅ２，．．．）は、全引数を空白文字（すなわちスペース）を使用して連結した文字列をＵＴＦ−８でエンコードしたバイト列に対してＳＨＡ−１（Secure Hash Algorithm-1）を適用し、適用結果を１０進数で表現するハッシュ関数であるとする。そして、ｈ１（ｅ１，ｅ２，．．．）：＝ｈ０（ｅ１，ｅ２，．．．） ｍｏｄ ｍとする。「：＝」は代入演算子を表す。
【００２６】
まず、ｈ１（"照明"，"照射"，"光"，"目"）＝０＜ｒであるので、特徴要素"目"の次を区切りの位置に決定する。ｈ１（"照射"，"光"，"目"，"通信"）＝０＜ｒであるので、特徴要素"通信"の次を区切りの位置に決定する。ｈ１（"光"，"目"，"通信"，"情報"）＝０＜ｒであるので、特徴要素"情報"の次を区切りの位置に決定する。ｈ１（"目"，"通信"，"情報"，"こと"）＝４≧ｒであるので、特徴要素"こと"の次は区切りの位置には該当しない。同様に処理を行うと、生成されるサブリストは、［"照明"，"照射"，"光"，"目"］、［"通信"］、［"情報"］、［"こと"，"照明"，"モノ"，"スマート"，"デバイス"，"カメラ"，"情報"，"配布"，"実現"］である。
【００２７】
本実施の形態においては、区切りの前におけるｎ個の特徴要素についてハッシュ値を算出するが、その他の方法によってハッシュ値を算出してもよい。例えば、区切りの後におけるｎ個の特徴要素についてハッシュ値を算出してもよい。なお、連続するｎ個の特徴要素であることが好ましいが、必ずしも連続するｎ個の特徴要素でなくてもよい。
【００２８】
図５に、サブリスト格納部１０９に格納されるサブリストの一例を示す。図５の例では、ステップＳ９において決定された位置でリストを区切ることによって生成されるサブリストが格納されている。
【００２９】
図３の説明に戻り、サブリスト生成部１０７は、サブリスト格納部１０９に格納されたサブリストのうち、特徴要素の数がｔ（ｔは自然数）未満であるサブリストをサブリスト格納部１０９から取り除く（ステップＳ１１）。パラメータｔを利用することで、過剰検出（すなわち、実際は流用が行われていないにもかかわらず流量が行われたと検知されてしまうこと）を抑制することができる場合がある。たとえ流用が行われていないとしても、特徴要素の数が少ない場合には同じ特徴要素列が出現する可能性が高くなるので、パラメータｔを利用することで過剰検出を抑制できるようになる。
【００３０】
例えば、図５の例においてｔ＝４とすると、サブリスト格納部１０９に残るサブリストは［"照明"，"照射"，"光"，"目"］及び［"こと"，"照明"，"モノ"，"スマート"，"デバイス"，"カメラ"，"情報"，"配布"，"実現"］である。
【００３１】
サブリスト生成部１０７の処理が終了すると、登録部１１１は、サブリスト格納部１０９に格納されたサブリストの各々についてハッシュ値を算出し、算出されたハッシュ値とステップＳ１において入力を受け付けた文書ＩＤとを対応付けて特徴データ格納部１１３に登録する（ステップＳ１３）そして処理を終了する。
【００３２】
ステップＳ１３におけるハッシュ関数は、ｈ２（ｅ１，ｅ２，．．．）：＝ｈ０（ｅ１，ｅ２，．．．） ｍｏｄ ２64であるとする。このようにすると、ｈ２（"照明"，"照射"，"光"，"目"）＝10002075992710416752であり、ｈ２（"こと"，"照明"，"モノ"，"スマート"，"デバイス"，"カメラ"，"情報"，"配布"，"実現"）＝15974053995356465065である。これらの数値を特徴データ格納部１１３に索引データとして登録すると、例えば図６のようになる。図６の例では、ハッシュ値と、文書ＩＤとが格納される。なお、索引データは、他の形式（例えばＲＤＭＳ（Relational Database Management System）の形式）であってもよい。
【００３３】
以上のような処理を実行すれば、局所的な複数の特徴要素を含むサブリストから算出されたハッシュ値を要素とする集合を、文書の特徴を現す特徴量とすることができるようになる。これにより、共通の要素が有るか判定することによってテキストデータの流用が行われたことを検知することができるようになる。
【００３４】
ここで、図３乃至図６を用いて説明した処理を、図７に示した文書「ｄ２」にも適用したとする。この場合、生成されるサブリストは、［"IoT"，"プラットフォーム"，"アプリケーション"，"開発"，"環境"］、［"クラウド"，"上"，"容易"，"利用"，"実現"，"性"，"検証"，"IoT"，"モデル"，"もと"，"センサー"，"デバイス"，"ネットワーク"，"ミドルウェア"，"アプリケーション"，"こと"］、及び［"可能"，"トータル"，"システム"，"環境"］である。算出されるハッシュ値は順に、16379724388191380887、13295147089011045793、及び10384776358887264315である。算出されたハッシュ値は特徴データ格納部１１３に追加されるので、特徴データ格納部１１３に格納される索引データは、図８に示すようになる。図８に示すように、索引データは、文書「ｄ１」についてのハッシュ値と、文書「ｄ２」についてのハッシュ値とが登録される。
【００３５】
次に、図９乃至図１１を用いて、或る文書が、既存の文書から流用された文章を含む文書であるか判定する処理について説明する。ここでは、図９に示すような文書「ｄ３」が、既存の文書から流用された文章を含む文書であるか判定する処理について説明する。
【００３６】
図９に示した文書「ｄ３」に対して、図３乃至図６を用いて説明した処理を適用しとする。この場合、生成されるサブリストは、［"照明"，"照射"，"光"，"目"］及び［"照明"，"モノ"，"デバイス"，"情報"，"配布"，"実現"］である。算出されるハッシュ値は順に、10002075992710416752及び426719386417036332である。但し、ハッシュ値は特徴データ格納部１１３には格納されず、抽出部１１５に渡されるものとする。
【００３７】
図１０を用いて、抽出部１１５が実行する処理について説明する。まず、抽出部１１５は、対象の文書（ここでは、文書「ｄ３」）から算出されたハッシュ値と一致するハッシュ値が特徴データ格納部１１３に登録されているか判断する（図１０：ステップＳ２１）。
【００３８】
対象の文書から算出されたハッシュ値と一致するハッシュ値が登録されていない場合（ステップＳ２３：Ｎｏルート）、処理を終了する。一方、対象の文書から算出されたハッシュ値と一致するハッシュ値が登録されている場合（ステップＳ２３：Ｙｅｓルート）、抽出部１１５は、対象の文書から算出されたハッシュ値と一致するハッシュ値に対応付けられている文書ＩＤを特徴データ格納部１１３から特定する。そして、抽出部１１５は、ハッシュ値を、特定された文書ＩＤと対象の文書の文書ＩＤとの組合せに対応付けて抽出結果格納部１１７に格納する（ステップＳ２５）。情報処理装置１は、抽出結果格納部１１７に格納されたデータを表示装置等に表示する。そして処理を終了する。
【００３９】
図１１に、抽出結果格納部１１７に格納されるデータの一例を示す。図１１の例では、文書ＩＤの組合せと、ハッシュ値とが格納される。図１１の例では、文書「ｄ１」から生成されたサブリスト［"照明"，"照射"，"光"，"目"］に対応するハッシュ値と、文書「ｄ３」から生成されたサブリスト［"照明"，"照射"，"光"，"目"］に対応するハッシュ値とが一致したので、文書「ｄ１」の文書ＩＤと文書「ｄ３」の文書ＩＤとの組合せとハッシュ値とが格納されている。
【００４０】
なお、文書「ｄ１」と文書「ｄ３」とを比較すると、特に後半部分に相違が多く有るものの、前半部分はほぼ同じである。このように、形式などが多少異なっていたとしても、文書「ｄ３」は文書「ｄ１」から流用されたデータを含む文章を含むことを検知することができたので、本実施の形態の方法はロバスト性が高い方法であると言える。ロバスト性が高い理由として、特徴要素を使うこと及び局所的に計算される値を使うことが挙げられる。特徴要素として単語等を使えば、空白及び句読点等の影響を受けなくなるので、種々の書式及び言語に対応可能になる。また、局所的に計算される値を使うことで、或る部分について流用の検出を行う際にその部分とは離れた部分に有る差異の影響を受けなくなるので、部分的に流用の検出を行うことが可能になる。
【００４１】
また、本実施の形態においてはハッシュ値の比較をしており、流用関係にはない文書のデータにアクセスして類似度を計算することがない。従って、比較効率が良い検知をすることができる。
【００４２】
また、パラメータｍ及びｒを変更することで、特徴量のサイズを柔軟に変更することができる。サブリストのサイズ（或いは、サブリストに含まれる特徴要素の数）は平均でｍ／ｒになり、特徴量のサイズは概ねｒ／ｍに比例することが期待されるため、Ｍ＝ａｍ及びＲ＝ｂｒを使用すれば、ｍ及びｒを使用する場合と比較して特徴量のサイズが約ｂ／ａ倍になる。
【００４３】
なお、パラメータｎの値が大きいほどサブリストのサイズの分散を小さくすることができ、また、ｍ及びｒによって特徴量のサイズを精度良く調整することができるようになる。例えば、ｎ＝１の場合には特徴要素"こと"のように頻繁に出現する特徴要素の後で区切られるかどうかでサブリストのサイズが大きく異なる。区切られる場合は、"こと"の後で常に区切られることになるため、サブリストの数が多く且つ特徴量のサイズが大きくなりがちである。逆に、区切られない場合は特徴量のサイズが小さくなりがちである。区切られるかどうかはｍ及びｒに依存するため、ｍ及びｒによる特徴量のサイズを精度良く調整することが難しい。一方、例えば、ｎ＝２の場合には、たとえ特徴要素リスト［"情報"，"こと"］の後で区切られたとしても、［"アプリケーション"，"こと"］の後で区切られる確率は、ｎ＝１の場合と違って１ではない（平均でｒ／ｍである）ため、頻繁に出現する特徴要素が特徴量のサイズに与える影響は小さくなる。つまり、ｎの値が大きいほどｍ及びｒによって特徴量のサイズを精度良く調整できる。このため、本実施の形態においては、複数の特徴要素から（すなわち、ｎを２以上の自然数として）ハッシュ値を算出している。
【００４４】
なお、同じ入力に対して同じハッシュ値が算出されるようにするため、システムを使用中に上記のパラメータやハッシュ関数を変更することはできない。
【００４５】
［実施の形態２］
図１２に、第２の実施の形態における文書検査装置１０００の機能ブロック図を示す。文書検査装置１０００は、生成部１００１と、分割部１００３と、算出部１００５と、比較部１００７とを有する。
【００４６】
生成部１００１は処理を実行し、処理結果を分割部１００３に出力する。分割部１００３は、生成部１００１から受け取った処理結果に基づき処理を実行し、処理結果を算出部１００５に出力する。算出部１００５は、分割部１００３から受け取った処理結果に基づき処理を実行し、処理結果を比較部１００９に出力する。比較部１００９は、算出部１００７から受け取った処理結果に基づき処理を実行する。
【００４７】
次に、図１３を用いて、文書検査装置１０００が実行する処理について説明する。
【００４８】
まず、生成部１００１は、複数の文字列の各々について、文字列における複数の特徴要素を含むリストを生成する（図１３：ステップＳ１０１）。
【００４９】
分割部１００５は、リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割する（ステップＳ１０３）。
【００５０】
算出部１００７は、複数のブロックの各々についてハッシュ値を求める（ステップＳ１０５）。
【００５１】
比較部１００９は、求められたハッシュ値を、文字列間で比較する（ステップＳ１０７）。そして処理を終了する。
【００５２】
以上のようにすれば、高精度で高速に文字列の類似性を検証できるようになる。
【００５３】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明した情報処理装置１の機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【００５４】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００５５】
また、本実施の形態においてはハッシュ値を特徴量として使用しているが、特徴量はハッシュ値には限られない。
【００５６】
また、上では日本語の文章を例として説明したが、名詞等の特徴要素を抽出できる言語であれば本実施の形態を適用することが可能である。また、自然言語には限られない。
【００５７】
また、本実施の形態において、リスト生成部１０３が生成するリスト内の要素は、文書内での出現順序どおりに並べられているが、このような順序には限られない。たとえば、辞書順に従って並べたり、重複する要素を削除しても良い。このようにすれば、文書内の多くの箇所において単語の語順が入れ替えられた場合にも類似文書として取り扱うことができるようになる。また、出現順よりも辞書順の方が同じハッシュ値が算出されやすく、それによってロバスト性が高くなるという効果がある。
【００５８】
また、ハッシュ関数は上で述べたようなものには限られない。なお、ステップＳ１３においてはＳＨＡ−１の出力を６４ビット空間に圧縮しているため、過剰検出が稀に起きることがある。出力空間の圧縮率を下げれば過剰検出の率を下げることができる一方、特徴量のサイズが大きくなるというトレードオフがある。
【００５９】
なお、上で述べた情報処理装置１及び文書検査装置１０００は、コンピュータ装置であって、図１４に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００６０】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【００６１】
本実施の形態の第１の態様に係る文書検査装置は、（Ａ）複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成する生成部と、（Ｂ）リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割する分割部と、（Ｃ）複数のブロックの各々についてハッシュ値を求める算出部と、（Ｄ）算出部が求めたハッシュ値を、文字列間で比較する比較部とを有する。
【００６２】
このようにすれば、リストに含まれる複数の特徴要素の一部から算出したハッシュ値を利用することで、高精度で高速に文字列の類似性を検証できるようになる。
【００６３】
また、上で述べた分割部は、（ｂ１）複数の特徴要素の一部から算出したハッシュ値に対して実行した演算処理の結果が所定条件を満たす場合にリスト内に区切りを設定することにより、リストを複数のブロックに分割してもよい。このようにすれば、区切りを適切な位置に設定できるようになる。
【００６４】
また、複数の特徴要素の一部は、文字列内での出現順序に従って抽出された複数の特徴要素であってもよい。このようにすれば、文字列の特徴がハッシュ値により反映されやすくなる。
【００６５】
また、複数の特徴要素の一部は、連続する複数の特徴要素であってもよい。このようにすれば、文字列の特徴がハッシュ値により反映されやすくなる。
【００６６】
また、演算処理は、ハッシュ値を所定の値で除して剰余を求める演算処理であってもよく、所定条件は、剰余が所定の範囲に含まれるという条件を含んでもよい。このようにすれば、ブロックの大きさが不均一になりにくくなる。
【００６７】
また、上で述べた分割部は、（ｂ２）連続する１又は複数の特徴要素のうち最初の特徴要素の前、又は、連続する１又は複数の特徴要素のうち最後の特徴要素の後に区切りを設定してもよい。
【００６８】
また、上で述べた算出部は、（ｃ１）ブロックに含まれる特徴要素の数が閾値未満である場合、当該ブロックのハッシュ値を前記比較部による比較の対象から除外してもよい。このようにすれば、過剰検出を抑制できるようになる。
【００６９】
また、特徴要素は名詞であってもよい。
【００７０】
本実施の形態の第２の態様に係る文書検査方法は、（Ｅ）複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成し、（Ｆ）リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割し、（Ｇ）複数のブロックの各々についてハッシュ値を求め、（Ｈ）求められたハッシュ値を、文字列間で比較する処理を含む。
【００７１】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００７２】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７３】
（付記１）
複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成する生成部と、
前記リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、前記リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割する分割部と、
前記複数のブロックの各々についてハッシュ値を求める算出部と、
前記算出部が求めたハッシュ値を、文字列間で比較する比較部と、
を有する文書検査装置。
【００７４】
（付記２）
前記分割部は、
前記複数の特徴要素の一部から算出したハッシュ値に対して実行した演算処理の結果が所定条件を満たす場合に前記リスト内に区切りを設定することにより、前記リストを前記複数のブロックに分割する、
付記１記載の文書検査装置。
【００７５】
（付記３）
前記複数の特徴要素の一部は、前記文字列内での出現順序に従って抽出された複数の特徴要素である、
付記１又は２記載の文書検査装置。
【００７６】
（付記４）
前記複数の特徴要素の一部は、連続する複数の特徴要素である
付記１又は２記載の文書検査装置。
【００７７】
（付記５）
前記演算処理は、ハッシュ値を所定の値で除して剰余を求める演算処理であり、
前記所定条件は、前記剰余が所定の範囲に含まれるという条件を含む
付記２記載の文書検査装置。
【００７８】
（付記６）
前記分割部は、
前記連続する１又は複数の特徴要素のうち最初の特徴要素の前、又は、前記連続する１又は複数の特徴要素のうち最後の特徴要素の後に前記区切りを設定する
付記４記載の文書検査装置。
【００７９】
（付記７）
前記算出部は、
前記ブロックに含まれる特徴要素の数が閾値未満である場合、当該ブロックのハッシュ値を前記比較部による比較の対象から除外する、
付記１乃至６のいずれか１つ記載の文書検査装置。
【００８０】
（付記８）
前記特徴要素は名詞である
付記１乃至７のいずれか１つ記載の文書検査装置。
【００８１】
（付記９）
コンピュータが、
複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成し、
前記リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、前記リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割し、
前記複数のブロックの各々についてハッシュ値を求め、
求められた前記ハッシュ値を、文字列間で比較する、
処理を実行する文書検査方法。
【００８２】
（付記１０）
コンピュータに、
複数の文字列の各々について、当該文字列における複数の特徴要素を含むリストを生成し、
前記リストに含まれる複数の特徴要素の一部から算出したハッシュ値に基づき、前記リストを、各々が１又は複数の特徴要素を含む複数のブロックに分割し、
前記複数のブロックの各々についてハッシュ値を求め、
求められた前記ハッシュ値を、文字列間で比較する、
処理を実行させる文書検査プログラム。
【符号の説明】
【００８３】
１  情報処理装置    １０１  文書データ格納部
１０３  リスト生成部    １０５  リスト格納部
１０７  サブリスト生成部    １０９  サブリスト格納部
１１１  登録部    １１３  特徴データ格納部
１１５  抽出部    １１７  抽出結果格納部
１０００  文書検査装置    １００１  生成部
１００３  分割部    １００５  算出部
１００７  比較部
【図１】
0006561529.tif 000002
【図２】
0006561529.tif 000003
【図３】
0006561529.tif 000004
【図４】
0006561529.tif 000005
【図５】
0006561529.tif 000006
【図６】
0006561529.tif 000007
【図７】
0006561529.tif 000008
【図８】
0006561529.tif 000009
【図９】
0006561529.tif 000010
【図１０】
0006561529.tif 000011
【図１１】
0006561529.tif 000012
【図１２】
0006561529.tif 000013
【図１３】
0006561529.tif 000014
【図１４】
0006561529.tif 000015