(57)【要約】本発明は、入力文書の非プレフィックスフリー（ＮＰＦ）符号化がプライバシーを提供するために変換手段として使用される、文書類似性検出方法に関する。本方法は、文書のシンボルを非プレフィックスフリー符号化方式で符号化するステップと、変換された文書を取得するステップと、符号化された文書の正規化圧縮距離を計算して文書の類似性スコアを計算するステップと、を含む。【選択図】図３
2019536152.tif 000002
【特許請求の範囲】
【請求項１】
プライバシーを保護した文書類似性検出方法であって、
非プレフィックスフリー符号化方式によって文書のシンボルを符号化するステップと、
変換された前記文書を取得するステップと、
符号化された前記文書の正規化圧縮距離を計算して、前記文書の類似性スコアを計算するステップと、を含み、
前記文書の前記シンボルは、可変ビット長コードワードに置き換えられ、前記コードワードは他の少なくとも何れかのプレフィックスであることを特徴とする、方法。
【請求項２】
請求項１に記載の方法であって、
同一のアルファベットで書かれた前記文書の中の前記シンボルの数を判定するステップと、
前記アルファベットの中の前記シンボルの数と等しいシーケンス番号のセットをランダムに準備するステップと、
シーケンスリストの前記セットの中の全ての数に１以上の整数を加えるステップと、
シーケンスリストの前記セットの中の全ての数のバイナリ表現ビットシーケンスを計算するステップと、
全ての前記コードワードから、１に設定された左端ビットを削除するステップと、
前記コードワードのセットを取得するステップと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プライバシーを保護した文書類似性検出方法に関する。
【０００２】
本発明は、特に、入力文書の非プレフィックスフリー（ＮＰＦ、non-prefix-free）符号化がプライバシーを提供するために変換手段として使用される、文書類似性検出方法に関する。
【背景技術】
【０００３】
文書間の類似性計算には、多くの用途があり、その一部を列挙すると、盗用の検出、著作権管理、重複報告の検出、文書の分類／クラスタリング、検索エンジンなどがある。多くの解決手法は、文書の内容が公開されていると仮定したものである。ここで、一般的な傾向として、初めに、主に文書内の単語の出現数、又はｎグラム頻度に基づく、特徴ベクトルを計算する。次に、それらの特徴、又はそれらから抽出されたフィンガープリント値を比較して、類似性スコアを計算する。自然言語処理ベースのアプローチにもかかわらず、情報距離ベースの類似性指標は、ソフトウェア盗作検出などのいくつかの実用的な事例にも適用されてきた。
【０００４】
プライバシーを保護した類似性検出は、文書の所有者が、文書の内容を秘密にしておきたいが、それらの文書間の類似性を測定する際に必要とされる。必要とされるシナリオの例には、学界の関連する会議及び雑誌の間での二重投稿管理、並びに保険会社又は情報機関の間での情報共有などが含まれるが、これに限られない。
【０００５】
同時投稿検出問題では、それぞれの投稿物の内容は非公開であるため、提出された主催者が、他の主催者においても同時にレビュー中の同一の論文の非常に類似したコピーが存在しているか否かを確認するために、投稿物を公に共有することはできない。しかしながら、実用的なプライバシーを保護した文書類似性検出ツールが利用可能である場合には、類似するトピックについて同時に複数の論文を受理する会議又は雑誌などの関連する主催者は、二重投稿を制御するためにこの手順を使用することができる。
【０００６】
他の例として、詐欺申請を検出するための保険会社間の文書比較がある。ある会社から損害又は損失が請求された場合、他の会社から提出された同様の請求を確認する必要がある。しかしながら、これらの請求は機密であるため、公開して比較することはできず、企業がプライバシーを侵害することなく、ファイルを比較するプライバシーを保護した類似性検出方法が必要とされる。政府諜報機関の間の協働における情報共有でも、同様のシナリオが考えられる。
【０００７】
プライバシーを保護した文書類似性検出問題を解決するために提案された既知の方法は、一般に、準同型（homomorphic）方式を用いて、文書から抽出された特徴を暗号化することから始まり、これにより、情報を確実にセキュアに保ちながら暗号化されたデータに対して処理される、いくつかの限られた処理を可能にする。準同型暗号化を介して実行可能なこれらの処理に基づいて、暗号化された特徴ベクトルの比較は、いくつかのマルチパーティ秘密計算（multi-party secure computation）プロトコルを介して達成される。しかしながら、準同型方式に固有の実用上の難しさが、プライバシーを保護した文書類似性検出のために、上述した解決手法を使用することを妨げる。
【０００８】
中国特許文献番号ＣＮ１４４７６０３は、情報技術分野におけるデータの可逆圧縮及び解凍の技術に関するものであるが、情報源エントロピー符号化を使用する可逆圧縮及び解凍は、全て、非プレフィックス符号化のエントロピー符号化方法に基づいており、メッセージソースの出現頻度に基づいてバイナリツリーを構築するとともに、ルートからリーフまでの検索を通じて、メッセージソースのコードを構築する。ただし、この方法は、プライバシーを保護した文書類似性検出のための方法を提供することを目的としておらず、かつ非プレフィックス符号化が全く異なる。
【０００９】
「制約付きシーケンスのための非プレフィックスフリー符号（Non prefix-free codes for constrained sequences）」というタイトルの論文（マルコ・ダライ及びリカード・レオナルディ、ブレシア大学  自動化電子工学科、イタリア）では、シンボルの制約付きシーケンスを符号化するための可変長非プレフィックスフリー符号の使用が言及されている。ただし、この方法は、プライバシーを保護した文書類似性検出のための方法を提供することを目的としておらず、かつ非プレフィックス符号化が全く異なる。
【発明の概要】
【００１０】
本発明の目的は、入力文書の非プレフィックスフリー（ＮＰＦ）符号化がプライバシーを提供するために変換手段として使用される方法を提供することである。
【００１１】
本発明の他の目的は、非プレフィックスフリー符号中の可変長符号がセキュリティの用途で使用される方法を提供することである。
【００１２】
本方法では、新たなプライバシーを保護した文書類似性検出が提示される。本方法におけるプライバシーは、非プレフィックスフリー符号における一意の復号化可能性（decodability）の欠如に基づいており、これは、従来提案されてきた、主に準同型方式及びマルチパーティ秘密計算方法に依存する解決手法とは異なる。プライバシーを保護しながら、ＮＰＦ符号化は、単にファイルのシンボルを可変ビット長のコードワードで置き換えるので、ソースファイル内のパターンを変更しない。したがって、文書間の規則性は、変換されたバージョンでも維持される。この特性のおかげで、正規化圧縮距離（ＮＣＤ、normalized compression distance）は、非常に適切なツールとして、類似性検出に使用される。２つのシーケンスにおけるＮＣＤ類似性は、０から１の間の値である。１００ファイルのコーパスに対して行われた実験では、ＮＰＦ変換による比較と通常の変換なしの比較との間の偏差が約０．０２ポイントであり、実際の使用に許容可能な程度であることが明らかになった。ＮＣＤ類似性指標に関わらず、ＮＰＦ符号化変換と同一の考えを、ｎグラムシンボルカウントに基づくものなどの、他の提案された類似性評価に統合することが可能である。
【図面の簡単な説明】
【００１３】
【図１】図１は、ＮＰＦ符号化された文書と符号化なしの文書との間で得られた類似性スコア間の線形相関を表す。
【図２】図２は、αとα’の違いを示す。
【図３】図３は、あるサンプル文書とその他のコーパスとの間で得られた類似性スコアスコアの、符号化なし（パブリック）形式とＮＰＦ符号化（プライベート）形式の比較を示す。
【００１４】
（発明の詳細な説明）
Ａ＝ａ１ａ２・・・ａｐ及びＢ＝ｂ１ｂ２・・・ｂｑが、それぞれｐ及びｑのシンボル長の２つの文書を表すものとする。ここで、それぞれの文字ａｉ及びｂｊは、アルファベットΣ＝｛ε１，ε２，・・・εσ｝によって描かれ、１≦ｉ≦ｐかつ１≦ｊ≦ｑである。方法Ｓ（）で計算された類似性スコアはＳ（Ａ，Ｂ）で表される。
【００１５】
この方法で使用される正規化圧縮距離の類似性指標は、２つの文書が類似している場合、それぞれの文書は他方から抽出されたモデルでうまく圧縮できるはずであるという事実に基づくものである。言い換えれば、それらのうちの１つが他の文書の終わりに連結され、そしてコンプレッサに送られた場合、類似する文書を組み合わせると、関連のないペアよりも圧縮率が高くなるため、得られる圧縮率は、それらの類似性を反映しているはずである。文書の長さの違いを考慮して圧縮率を正規化すると、ＮＣＤ類似性スコアは次の式で表される。
【数１】
2019536152.tif 000003
ここで、Ｃ（）は任意のコンプレッサであって、ＡＢは、文書Ａ及びＢの連結である。スコアは０から１の間である。類似性は０に向かって増加し、１に向かって減少する。
【００１６】
この方法では、文書は非プレフィックスフリー符号化方式で符号化される。Ｗ＝｛ｗ１，ｗ２，・・・ｗσ｝は、アルファベットΣ＝｛ε１，ε２，・・・εσ｝用に生成されたコードセットであると仮定する。各々のｗｉは、任意の長さのビットシーケンスであり、Ｗにおける別のコードワードｗｊのプレフィックスであり得る。シーケンスＴ＝ｔ１ｔ２・・・ｔｎであって、ｔｉ∈Σであるとすると、ＮＰＦ：Σ→Ｗの符号化は、Ｔにおいて出現する全てのεｉを対応するｗｉに置き換える。
Ｔ＝ＮＯＮＰＲＥＦＩＸＦＲＥＥ
Σ＝｛Ｅ，Ｒ，Ｆ，Ｎ，Ｉ，Ｏ，Ｐ，Ｘ｝
Ｗ＝｛01，0，111，001，010，1111，00，1｝
ＮＰＦ（Ｔ）＝001 1111 001 00 0 111 010 1 111 0 01 01
例１：シーケンスＴ＝ＮＯＮＰＲＥＦＩＸＦＲＥＥの非プレフィックスフリー符号化の例
【００１７】
例１は、Ｔ＝ＮＯＮＰＲＥＦＩＸＦＲＥＥにおけるＮＰＦ符号化の例を示している。Ｗにおけるコードワードは、プレフィックスフリーではない。例えば、シンボルＸに割り当てられたコードワード１は、それぞれＦ及びＯに割り当てられたコードワード１１１、１１１１のプレフィックスである。非プレフィックスフリー特性の他の例は、Ｗに現れている。サンプルＴの符号化されたビットストリームが示されている。非プレフィックスフリー特性のため、符号化されたストリームにおいて、コードワードの境界が判定できないことに注意されたい。同一のストリームは、コードワードセットＷに従った、他の多くの解析を有することができ、例えば、先頭のビット００１１１１１１は、シーケンスＰＦＸＸ等をも表すことができる。一意の復号化可能性が欠如しているため、非プレフィックスフリー符号は、データ圧縮の観点からそれほど興味深いものではない。
【００１８】
セキュリティの目的から、可変長符号を使用することもできる。前述のとおり、ハフマン符号のようなプレフィックスフリー符号は暗号解読が困難であり、プレフィックスフリー符号化したバージョンから元のシーケンスを抽出することは困難である。非プレフィックスフリー符号の場合では、暗号文単独攻撃（ciphertext-only attack）で使用されるという制限がはるかに少ないため、状況は更に困難である。
【００１９】
元のシーケンスを抽出するのは困難であるが、ＮＰＦ符号化方式は実際には文書の構文構造を保持する。異なる文書において互いに等しい部分は、同一のビットストリームにマッピングされる。したがって、共有の情報コンテンツは、ＮＰＦ変換後も保持される。このため、文書間のＮＣＤ距離は、それらのＮＰＦ変換したバージョンでも維持される。より正式には、｜Ｓ（Ａ，Ｂ）−Ｓ（ＮＰＦ（Ａ），ＮＰＦ（Ｂ））｜が小さいと予想される。
【００２０】
（方法）
例えば、アリスとボブがそれぞれ文書Ａと文書Ｂを所有しているとする。両方の文書は同一のアルファベットΣを有すると仮定する。彼らは、内容を互いに明らかにせずに、文書がどの程度類似しているかを知りたいとする。この目的を達成するために、彼らは、彼らが事前に同意した、同一のＮＰＦコードワードセットＷで彼らの文書を符号化する。
【００２１】
ここでの目的はデータ表現における効率ではなく、プライベートなデータの比較であるため、ＮＰＦ符号化のためのコードワードセットＷは任意に選ぶことができる。重要なことは、コードワードを他のコードワードのプレフィックスにすることである。この点を考慮して、所与のアルファベットΣのコードワードセットＷは、以下のように用意することができる。
【００２２】
シーケンスＸ＝＜１，２，・・・σ＞は、１からσまでの数のランダム順列（random permutation）を得るために、擬似乱数発生器ＰＲＮＧ（pseudo-random number generator）を用いてシャッフルされる。ＰＲＮＧは、初めに任意に選択されたシードで初期化される。ｉ＝１からσまでそれぞれ順番に、ＸｉとＸｒの値が交換される。ここで、ｒは、１からσの間の、ＰＲＮＧによって生成される乱数である。この手順は、Ｋ回（Ｋは大きな数）繰り返され、例えば、実施された実験では１０００回繰り返される。最後に、ランダム順列Ｘ’＝＜ｘ１，ｘ２，・・・ｘσ＞が準備される。ここでｘｉ∈｛１，２，３，・・・σ｝で、ｉ＝ｊでない限りｘｉ≠ｘｊである。
【００２３】
Ｗのコードワードは、各ｗｉを（ｘｉ＋１）の最小二進表現（minimal binary representation）に設定することによって生成される。整数ｉの最小二進表現ビットシーケンスは、左端ビットが１に設定されていない、長さ┗ｌｏｇ２ｉ┛のバイナリ文字列である。例えば、５＝（１０１）２の最小二進表現は０１であって、長さ２＝┗ｌｏｇ２５┛である。例えば、アルファベットサイズσ＝８と仮定し、ランダム順列ベクトルＸ＝＜２，５，３，６，７，１，４，８＞と仮定すると、上述した手順によって、コードワードセットＷは、Ｗ＝｛１，１０，００，１１，０００，０，０１，００１｝と生成される。
【００２４】
ＰＲＮＧの初期化に同一のシードを使用し、同一のＫ回のシャッフル操作を繰り返すことで、両当事者が同一の順列を有し、これによって、同一のＷを有することに注意されたい。
【００２５】
アリス及びボブが彼らの文書を同一の非プレフィックスフリーコードワードセットＷで符号化すると、変換された文書の類似性スコアを計算することができる。彼らのＮＰＦ符号化した変換物から元の文書を抽出することは、変換されたビットシーケンスにおけるコードワード境界の欠如のために難しいので、彼らは文書を交換して、上述したＮＣＤ指標を用いて類似性を計算することができる。類似性スコアが特定の閾値を下回る場合、変換された文書間の類似性は元の文書の類似性を反映するので、元の文書が関連していることを意味する。
【００２６】
しかしながら、このシナリオでは、アリスとボブが、彼らの文書がＮＰＦで符号化されていても、文書を交換することを望まない場合がある。それは、実質的に文書のプライバシーが確立されていると考えられるものの、当事者はシステムの証明可能なセキュリティについて懐疑的となり得るためである。そのような事例は、例えばアリス及びボブが情報機関の職員であり、双方がある問題について同様の知識を持っているか否かを確認したい場合に、起こり得る。一方で、そのような事例は、アリス及びボブが関連する会議のプログラム委員であり、同時投稿があるか否かを検査したい場合には、起こる可能性は低い。
【００２７】
いずれにせよ、そのような種類の懸念がある場合には、両当事者が信頼できる第三者にＮＰＦ符号化された文書へのアクセスを許可し、その第三者がＮＣＤ計算を実行する。その信頼された第三者がＮＰＦコードワードセット及び文書についての知識を全く持っていないため、その第三者が暗号文単独攻撃を試みることは更に難しいことに注意されたい。
【００２８】
（実験結果）
我々は、５人の異なるトルコ人ジャーナリストの日々のコラムである、１００個の文書のコーパスを集めた。それぞれの著者は２０個のファイルで表され、合計１００個の文書が作成される。それぞれの文書のサイズは約５ＫＢである。
【００２９】
実験における我々の主な興味は、α’←ＮＣＤ（ＮＰＦ（Ａ），ＮＰＦ（Ｂ））で示されるプライベートドメインの類似性が、α←ＮＣＤ（Ａ，Ｂ）で示されるパブリックドメインの類似性にどの程度近いかを観察することである。
【００３０】
そのために、我々は、http://complearn.orgから取得したＮＣＤソフトウェアを使用して、取り得る文書のペア間のそれぞれの類似性スコアを計算した。その後、我々は、ランダムシードを選択し、Ｃプログラミング言語のＰＲＮＧ（ｒａｎｄ（）コマンド）を使用して必要な乱数を生成することにより、提案されたＮＰＦ符号化方式で各文書を符号化した。我々は、２５６文字のＡＳＣＩＩコードを文書のソースアルファベットと見なした。このようにして、ＮＰＦ符号化された文書コーパスが作成された。
【００３１】
ここで、実際の使用に関して軽微な差異がある。符号化された文書を保存する際に、我々は、各ビットをバイトで表した。その理由は、バイト指向の、一般的なコンプレッサの動作メカニズムによるものである。ＮＣＤソフトウェアでも使用されているコンプレッサは、入力シーケンスをビットストリームではなくバイトストリームとみなす。このため、ＮＣＤを用いた類似性計算の圧縮段階において、いかなる精度も損なわないように、我々は、ＮＰＦ符号化シーケンスにおいてビット当たり１バイトを費やすこととした。
【００３２】
図１は、ＮＰＦ符号化された文書と符号化なしの文書との間で得られた類似性スコア間の線形相関を表す。類似性スコアは、０（高い類似性）と１（低い類似性）との間である。グラフには単に（α’、α）の組が示されるが、ここで、α’←ＮＣＤ（ＮＰＦ（Ａ），ＮＰＦ（Ｂ））、α←ＮＣＤ（Ａ，Ｂ）であり、その数は、
【数２】
2019536152.tif 000004
である。
【００３３】
図２は、αとα’の違いを示す。この差は平均で約０．０２であり、もっとも悪い事例は約０．０４であることがわかる。
【００３４】
図３は、あるサンプル文書とその他のコーパス３との間で得られた類似性スコアの、符号化なし（パブリック）形式とＮＰＦ符号化（プライベート）形式との、比較を示す。ＮＰＦ符号化された文書間の類似性スコアは、符号化なし形式よりも約０．０２ポイント良好であることが観察された。これは、保存されている実際のシンタックスの類似性に加えて、ＮＰＦ符号化では、可変長符号からも発生する疑似類似性が加えられ得るためである。例えば、符号化された文書の両方に現れるビットシーケンスは、文書がその部分で共通のフレーズを共有していることを意味するものではない。しかしながら、逆のことも言え、もし文書がフレーズを共有している場合、それらのＮＰＦ符号化された変換物もその部分に同一のビットシーケンスを生成する。この理由から、ＮＰＦ符号化された文書は、通常わずかに良い類似性スコアを報告し、これはαとα’との間の０．０２ポイントの偏差の主な原因である。
【００３５】
プライバシーを保護した文書類似性検出方法を提案した。提案された方法におけるプライバシーは、非プレフィックスフリー符号における一意の復号化可能性の欠如に基づいており、これは、従来提案されてきた、主に準同型方式及びマルチパーティ秘密計算方法に依存する解決手法とは異なる。プライバシーを保護しながら、ＮＰＦ符号化は、単にファイルのシンボルを可変ビット長のコードワードで置き換えるので、ソースファイル内のパターンを変更しない。したがって、文書間の規則性は変換されたバージョンでも維持される。この特性のために、正規化圧縮距離（ＮＣＤ）は、非常に適切なツールとして、類似性検出に使用される。２つのシーケンスにおけるＮＣＤ類似性は、０から１の間の値である。１００ファイルのコーパスに対して行われた実験では、ＮＰＦ変換による比較と通常の変換なしの比較との間の偏差が約０．０２ポイントであることが明らかになり、実際の使用に許容可能な程度であることが明らかになった。ＮＣＤ類似性指標に関わらず、ＮＰＦ符号化変換と同一の考えを、ｎグラムシンボルカウントに基づくものなどの、他の提案された類似性評価に統合することが可能である。
【図１】
2019536152.tif 000005
【図２】
2019536152.tif 000006
【図３】
2019536152.tif 000007
【国際調査報告】
2019536152.tif 000008
2019536152.tif 000009