(57)【特許請求の範囲】
【請求項１】
コンピュータが実行する情報処理方法であって、
検索対象として指定された第１の文字列に混合する第２の文字列を取得する取得処理と、
前記第１の文字列に含まれる複数の文字の順序関係と、前記第２の文字列に含まれる複数の文字の順序関係とを維持しつつ、前記第１の文字列に対して前記第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する処理と、
前記データ格納部に格納されている前記第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する処理と、
を含む情報処理方法。
【請求項２】
前記コンピュータが、前記検索コンピュータから、複数の第４の文字列からなる検索結果を受信し、前記複数の第４の文字列から、前記第１の文字列に対応する文字列を抽出する処理
をさらに含む請求項１記載の情報処理方法。
【請求項３】
前記取得処理は、
文字又は文字列毎に共起率が閾値以上の文字又は文字列が対応付けられて格納されている第２のデータ格納部から、前記第１の文字列に含まれる文字又は文字列について対応付けられている文字又は文字列であって前記第１の文字列に含まれない文字又は文字列を抽出する処理により抽出された前記文字又は文字列の少なくともいずれかを含む第２の文字列を取得する処理
である請求項１又は２記載の情報処理方法。
【請求項４】
前記取得処理が、
文字又は文字列毎に共起率が閾値以上の文字又は文字列が対応付けられて格納されている第２のデータ格納部から、前記第１の文字列に含まれる文字又は文字列について対応付けられている文字又は文字列であって前記第１の文字列に含まれない文字又は文字列を抽出する処理と、
抽出された前記文字又は文字列を用いて前記第２の文字列を選択する選択処理と、
を含み、
前記選択処理が、
抽出された前記文字又は文字列のうち、１つの第２の文字列に含まれる文字又は文字列の数又は割合が第１の所定値以上となるように、前記第２の文字列を選択する処理、
前記第２の文字列の選択総数が予め設定されている場合に、抽出された前記文字又は文字列の少なくともいずれかを含む第２の文字列の、前記選択総数に対する割合が第２の所定値以上であるように、前記選択総数分の第２の文字列を取得する処理、又は
抽出された前記文字又は文字列が複数種類であり、前記第２の文字列が複数である場合、抽出された前記文字又は文字列のうち当該複数の第２の文字列に含まれる文字又は文字列の種類の数又は割合が第３の所定値以上となるように、前記複数の第２の文字列を選択する処理
を含む請求項１又は２記載の情報処理方法。
【請求項５】
前記編集距離に対する閾値が、前記第３の文字列の文字数に基づき、または前記第３の文字列の文字数及び前記第１の文字列の文字数に基づき決定される
請求項１乃至４のいずれか１つ記載の情報処理方法。
【請求項６】
検索対象として指定された第１の文字列に混合する第２の文字列を取得する取得処理と、
前記第１の文字列に含まれる複数の文字の順序関係と、前記第２の文字列に含まれる複数の文字の順序関係とを維持しつつ、前記第１の文字列に対して前記第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する処理と、
前記データ格納部に格納されている前記第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する処理と、
を、コンピュータに実行させるためのプログラム。
【請求項７】
検索対象として指定された第１の文字列に混合する第２の文字列を取得し、前記第１の文字列に含まれる複数の文字の順序関係と、前記第２の文字列に含まれる複数の文字の順序関係とを維持しつつ、前記第１の文字列に対して前記第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する混合部と、
前記データ格納部に格納されている前記第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する出力部と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、検索の秘匿化技術に関する。
【背景技術】
【０００２】
近年、企業によるクラウドコンピューティングの利用が拡大してきている。その中でも、業界クラウドと呼ばれるクラウドが注目されている。業界クラウドは、同一の業界に属する異なる複数の組織が有する計算機資源を含み、それぞれの資源を互いに利用するクラウドである。例えば、医療クラウドの場合、複数の病院が有する計算機資源を組み合わせることにより得られ、それぞれが有する診療情報などを互いに交換して、高度な医療サービスを顧客に提供することが期待されている。このように、業界クラウドは、同一業界における異なる組織が各々有するデータを互いに有効活用することで、より品質が高いサービスを提供することを目指すものである。
【０００３】
例えば、業界クラウドの一形態として、与信クラウドが知られている。与信クラウドは、異なる組織が各々有する、個人の借金暦などの信用情報を蓄積している。より具体的には、いわゆるブラックリストを管理している。このため、銀行等の金融機関が顧客に融資を行う際に、顧客の信用度を調査するために与信クラウドを用いる。与信クラウドには、異なる組織からのブラックリストが蓄積されるため、与信クラウドにより非常に広い範囲の与信情報を提供することが出来る。反面、異なる組織からのデータを組み合わせているため、同一人物であっても異なるデータとして登録されることがある。例えば、Ｘ社の”ワタナベ”さんは、Ｙ社では”ワタベ”さんとして登録されていることがある。このようなデータの差異を吸収し、異なるデータが示す同一人物を区別するために、「名寄せ」と呼ばれる処理が行われる。
【０００４】
名寄せでは、２つの文字列の類似度を計算し、所定の閾値以上ならば同一人物であると判定する。類似度の計算方法には様々な手法が知られているが、編集距離と呼ばれる手法を用いるのが一般的である。
【０００５】
編集距離は、文字列間の類似度を、「何文字削除、挿入、置き換えたか？」で評価する手法である。例えば、「ワタベ」は「ワタナベ」から一文字削除した文字列なので、「ワタナベ」からみた「ワタベ」の編集距離は１Ｄである。ただし、Ｄは１文字削除による編集距離としての重みを表すパラメータである。逆に、「ワタナベ」は「ワタベ」に対して一文字挿入した文字列であるので、「ワタベ」から見た「ワタナベ」の編集距離は１Ｉである。ただし、Ｉは１文字挿入による編集距離としての重みを表すパラメータである。
【０００６】
例えば、与信クラウドは、Ｘ社のデータベース、Ｙ社のデータベースなど、複数の組織が管理するブラックリストデータベースを有するものとする。銀行などの金融機関Ａは、与信クラウドに対して、自社の顧客名をクエリとして送信することで、自社顧客がブラックリスト該当者であるかどうかの調査を行う。この調査のために、金融機関Ａは自社顧客名「ワタナベ  タカシ」をクエリとして、与信クラウドに送信する。与信クラウドにおいては、名寄せ処理を行うサーバが金融機関Ａの顧客名「ワタナベ  タカシ」を受信する。サーバは、受信した「ワタナベ  タカシ」と、複数組織のブラックリストデータベースそれぞれに含まれる名前に対して、横断的な名寄せ処理を行う。この結果、ブラックリストに列挙されている名前の中で、類似度が閾値を超える「ワタベ  タカシ」がクエリに一致する名前として選出され、金融機関Ａに対しクエリレスポンスとして返信される。以上により、金融機関Ａは自社顧客がブラックリスト該当者であるか否かという信用調査を行うことが出来る。
【０００７】
しかし、このような与信クラウドでは、プライバシ上の問題が懸念される。第１の問題は、自社顧客名をそのまま与信クラウドに通知するため、調査対象の自社顧客名が与信クラウド側に漏洩してしまう。また、自社顧客名がブラックリスト該当者であった場合、調査対象の自社顧客名がブラックリスト該当者であることが、与信クラウド側に漏洩してしまう。
【０００８】
その結果、与信クラウドに対してクエリを送信する会社や組織は、自社顧客名という重要なプライバシ情報を漏洩する危険性にさらされる。このような問題は、ＳＳＬ（Secure Socket Layer）やＶＰＮ（Virtual Private Network）等の通信データ暗号化技術を用いても、与信クラウド内部で名寄せ処理を実施するサーバでデータが復号されるため、回避できない。このような情報漏洩に対応するために、クエリを変換するような技術は存在していない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１１−１１８５４５号公報
【特許文献２】特開２００７−７２９５９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本技術の目的は、一側面によれば、クエリを秘匿化するための技術を提供することである。
【課題を解決するための手段】
【００１１】
本技術に係る情報処理方法は、（Ａ）検索対象として指定された第１の文字列に混合する第２の文字列を取得する取得処理と、（Ｂ）第１の文字列に含まれる複数の文字の順序関係と、第２の文字列に含まれる複数の文字の順序関係と維持しつつ第１の文字列に対して第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する処理と、（Ｃ）データ格納部に格納されている第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する処理とを含む。
【発明の効果】
【００１２】
クエリを秘匿化することができるようになる。
【図面の簡単な説明】
【００１３】
【図１】図１は、第１の実施の形態におけるシステムの構成例を示す図である。
【図２】図２は、クライアント装置の機能ブロック図である。
【図３】図３は、第１の実施の形態の概要を説明するための図である。
【図４】図４は、比較例を説明するための図である。
【図５】図５は、第１の実施の形態に係る秘匿性を説明するための図である。
【図６】図６は、第１の実施の形態に係る秘匿性を説明するための図である。
【図７】図７は、編集距離の性質を説明するための図である。
【図８】図８は、第１の実施の形態におけるメインの処理フローを示す図である。
【図９】図９は、秘匿化処理の処理フローを示す図である。
【図１０】図１０は、混合処理の処理フローを示す図である。
【図１１】図１１は、混合処理の処理フローを示す図である。
【図１２】図１２は、混合処理の処理フローを示す図である。
【図１３】図１３は、混合処理の処理フローを示す図である。
【図１４】図１４は、検索処理の処理フローを示す図である。
【図１５】図１５は、編集距離の算出処理の処理フローを示す図である。
【図１６】図１６は、編集距離の算出処理を説明するための図である。
【図１７】図１７は、編集距離の算出処理を説明するための図である。
【図１８】図１８は、編集距離の算出処理の処理フローを示す図である。
【図１９】図１９は、編集距離の算出処理を説明するための図である。
【図２０】図２０は、共起テーブルの一例を示す図である。
【図２１】図２１は、共起テーブルの一例を示す図である。
【図２２】図２２は、第２の実施の形態に係る秘匿化処理の処理フローを示す図である。
【図２３】図２３は、第２の実施の形態に係る抽出処理の処理フローを示す図である。
【図２４】図２４は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１４】
［実施の形態１］
本実施の形態のシステム概要を図１を用いて説明する。図１の例では、インターネットなどのネットワーク１には、名寄せ処理を実施する検索サーバ５と、１又は複数のクライアント装置３（図１では３ａ及び３ｂ）とが接続されている。検索サーバ５は、例えば与信クラウドに含まれるサーバであり、例えば第１の企業のブラックリスト等のデータを格納する第１ＤＢ５１と、第２の企業のブラックリスト等のデータを格納する第２ＤＢ５２などと接続されており、これらのデータベースに対して横断的に名寄せ処理を実施する。クライアント装置３は、クエリを検索サーバ５に送信すると、検索サーバ５は、クエリに含まれる文字列との編集距離が閾値以下の文字列を第１ＤＢ５１等から抽出して、クエリ送信元のクライアント装置３に検索結果として返信する。
【００１５】
クライアント装置３の機能ブロック図を図２に示す。クライアント装置３は、入力部３１と、第１データ格納部３２と、第２データ格納部３３と、第１抽出部３４と、第３データ格納部３５と、混合部３６と、第４データ格納部３７と、クエリ送信部３８と、検索結果受信部３９と、第５データ格納部４０と、第２抽出部４１と、第６データ格納部４２と、出力部４３とを有する。
【００１６】
入力部３１は、ユーザから、例えば信用調査の対象となる顧客の姓名などの文字列の入力を受け付け、第１データ格納部３２に格納する、
【００１７】
第２データ格納部３３は、混合部３６で混合する姓及び名の候補となるデータを格納している。第１抽出部３４は、第２データ格納部３３から所定の個数の姓及び名を抽出して、第３データ格納部３５に格納する。混合部３６は、第１データ格納部３２に格納されている文字列と、第３データ格納部３５に格納されている文字列とを、文字列に含まれる文字の出現順番を維持しつつ混合して、混合した結果を第４データ格納部３７に格納する。クエリ送信部３８は、第４データ格納部３７に格納されているデータを含むクエリを、検索サーバ５に送信する。
【００１８】
検索結果受信部３９は、検索サーバ５から検索結果を受信し、第５データ格納部４０に格納する。第２抽出部４１は、第５データ格納部４０に格納されている検索結果から、第１データ格納部３２に格納されている顧客の姓名などの文字列に類似する文字列を抽出し、第６データ格納部４２に格納する。出力部４３は、第６データ格納部４２に格納されているデータを、表示装置などの出力装置又はクライアント装置３に接続されている他のコンピュータに出力する。
【００１９】
次に、図１に示したシステムの処理内容を説明する。最初に、図３乃至図１９を用いて本実施の形態の概要について説明する。
【００２０】
本実施の形態では、クライアント端末３は、検索対象の文字列「ワタナベタカシ」の文字とダミー文字列「ヨシダダイキ」及び「ヒロイヨシコ」の文字とをそれらの文字列における出現順番を維持しつつ混合することでクエリ「ヒワロタヨシイナベダヨダタシカイキシコ」を生成して、検索サーバ５に送信する。このように、クエリ自体は秘匿化される。検索サーバ５は、クエリを受信すると、第１ＤＢ５１及び第２ＤＢ５２に対して横断的に編集距離が閾値以下の文字列を抽出する。ここでは、「ワタベタカシ」及び「ヒロタタカコ」が抽出されるものとする。すなわち、検索サーバ５側では、「ワタベタカシ」及び「ヒロタタカコ」のいずれかを抽出しようとしたのかが不明である。たとえ１つしか文字列が抽出されない場合であっても、「ワタベタカシ」と「ワタナベタカシ」のように異なる文字列である場合もある。また、「ヒロタタカコ」のみが抽出されることもある。すなわちクエリの結果からもクエリに含まれる文字列を特定できない。なお、クライアント装置３は、検索対象の文字列「ワタナベタカシ」を保持しているので、クエリの結果「ワタベタカシ」及び「ヒロタタカコ」のうち類似する文字列「ワタベタカシ」を抽出することができるようになる。
【００２１】
本実施の形態は、以下に述べるような比較例に対しても秘匿性の面で有利である。すなわち、図４に示すように、同じようにダミー文字列を用いても混合しないで、「ワタナベタカシ」「ヨシダダイキ」及び「ヒロイヨシコ」を含むクエリを検索サーバ５に出力する。この場合には、検索サーバ５は、第１ＤＢ５１及び第２ＤＢ５２に対して編集距離が閾値以下の文字列を横断的に抽出すると、「ワタベタカシ」のみが抽出される。このような場合、本来の検索対象文字列「ワタナベタカシ」は秘匿化されているが、クエリの結果が「ワタベタカシ」がブラックリスト該当者であることが分かってしまうので、クエリに含まれる「ワタナベタカシ」との関係から検索サーバ５側に、クエリに含まれる「ワタナベタカシ」がブラックリストに「ワタベタカシ」で登録されていることが漏洩してしまう。
【００２２】
これは以下のような問題があるためである。すなわち、使用するダミー文字列をｎ個と仮定すると、クエリにはｎ＋１個の文字列が含まれているので、検索サーバ５側から見ると、候補数はｎ＋１個となり、秘匿化がなされている。一方、ダミー文字列を含めたｎ＋１個の文字列に対して、第１ＤＢ５１及び第２ＤＢ５２（例えばブラックリスト）においてヒットする文字列数が（ｎ＋１）／Ｂであることが期待される。なお、ＢはＢ個のうち１つがブラックリストに含まれる、という割合を表す定数である。
【００２３】
仮に、Ｂ＝１００、すなわち人口の１％がブラックリスト該当者であるとするならば、ｎ＝９９に設定しなければ、クエリにダミー文字列を含ませてもダミー文字列がヒットすることはない。Ｂが小さいほど、ｎの値を大きくしなければダミー文字列がヒットしなくなるので、ダミー文字列をヒットさせようとするとクエリのデータ量が膨大となってしまう。これによって、システム処理効率も低下してしまう。検索サーバ５から見た候補数を、そのままＢで除した値がブラックリストにおいてヒットする数であることを考慮すると、ｎに対して検索サーバ５から見た候補数を効率よく増加させることが好ましい。すなわち、ダミー文字列の数ｎに対して、検索サーバ５から見た候補数をｎに対する線形比例より大きなオーダーの個数に見えるようにする。
【００２４】
これに対して図３で示したような検索対象文字列とダミー文字列との混合方式を採用すると、検索サーバ５から見た候補数をｎに対する線形比例より大きくすることができるようになる。
【００２５】
すなわち、図５に示すように、検索対象文字列「タナカコウキ」とダミー文字列「コジマキイチ」とを混合して「タコナカジマキコウイキチ」をクエリとする場合には、検索サーバ５から見ると「コジマキイチ」「タナカコウキ」「コジマコウキ」「タナカキイチ」の４種類の他、「ナカジマコウイチ」等のｋｍv種類の候補が存在する。すなわち、検索対象文字列とｎ種類のダミー文字列の合計ｍ＝ｎ＋１種類の文字列を混合すると、図４に示すような比較例の場合、候補数がｍに過ぎないが、本実施の形態では、候補数はｍ2＋ｋｍv（ｋは定数、ｖは８以上の定数）となる。
【００２６】
このように、本実施の形態では、候補数はｎの８乗以上の関数に比例して飛躍的に増加するため、候補数をｎに対する線形比例より大きなオーダーの個数に見えるようにすることができる。
【００２７】
なお、ｍ2の項は、ｍ種類の姓とｍ種類の名とを、姓と名の単位で混合無しで組み合わせた場合の候補数である。ｋｍvの項は、ｍ種類の姓同士を文字列単位で混合した場合と、ｍ種類の名同士を文字列単位で混合した場合の候補数である。ｍ種類の姓同士を文字列単位で混合した場合、ｕ≧４に対してｍuに比例した候補数の候補が発生する。ｍ種類の名同士を文字列単位で混合した場合、ｗ≧４に対してｍwに比例した候補数の候補が発生する。従って、姓と名の組み合わせでは、これらの積であるｍu+w，ｕ＋ｗ≧８に比例した候補数となる。
【００２８】
次に、ｍ種類の姓又は名同士を文字列単位で混合した場合の候補数がｍの４乗以上に比例する理由を、図６を用いて説明する。
【００２９】
図６は、３文字の名前（姓もしくは名）２種を文字単位で混合した例における候補数を示している。３文字の名前２種を混合した場合、合計で６文字となる。この６文字が、他の名前に一致するパターンは、名前が２乃至４文字で表現できると仮定すると、６文字中２文字が他の名前に一致するパターンと、６文字中３文字が他の名前に一致するパターンと、６文字中４文字が他の名前に一致するパターンの３種に分類される。
【００３０】
これらのうち、６文字中２文字が他の名前に一致するパターンは、６文字中２文字を選別してできるランダムな文字列の組み合わせ総数である6Ｃ2に対して、ランダムな２文字の文字列が他の名前に一致する確率定数αを乗じたα6Ｃ2となる。但し、aＣbはａ個の中からｂ個を選ぶ場合の組み合わせの総数を表す記号であり、aＣb＝ａ×（ａ−１）×・・・×（ａ−ｂ＋１）／（１×２×・・・×ｂ）であり、例えば6Ｃ2＝６×５／（１×２）＝１５、6Ｃ3＝６×５×４／（１×２×３）＝２０である。
【００３１】
ランダムな３文字の文字列が他の名前に一致するパターン数は、同様にβ6Ｃ3と表される。但し、βはランダムな３文字の文字列が他の名前に一致する確率を表す定数である。さらに、ランダムな４文字の文字列が他の名前に一致するパターン数は、γ6Ｃ4と表される。但し、γはランダムな４文字の文字列が他の名前に一致する確率を表す定数である。以上から、候補数は、以下のように表される。
α6Ｃ2＋β6Ｃ3＋γ6Ｃ4  （１）
【００３２】
（１）式は、３文字の名前２種を混合し、合計６文字を用いた場合の候補数であるが、これを２乃至４文字の名前ｍ種類を混合した場合に一般化する。この場合、混合後の文字数の合計はｍＨと表される。但し、Ｈは名前の平均文字数であり、２乃至４の間の定数となる。よって、（１）式の「６」を「ｍＨ」に置換することで、一般化した場合の候補数が得られる。
αmHＣ2＋βmHＣ3＋γmHＣ4  （２）
【００３３】
aＣbの定義から、mHＣ2はｍに関する２次式、mHＣ3はｍに関する３次式、mHＣ4はｍに関する４次式となるので、（２）式はｍに関する４次式となる。すなわち、候補数がｍの４乗以上に比例する。
【００３４】
なお、文字列を混合する際には、混合前のそれぞれのｎ＋１個のそれぞれの文字列間の順序関係（すなわち出現順番）を変えないようにする。例えば正しい顧客名「ワタナベ」に対し、ダミー名「ヒロタ」を混合する場合は、以下の２点を守る。
・「ワ」の後に「タ」、「タ」の後に「ナ」、「ナ」の後に「ベ」
・「ヒ」の後に「ロ」、「ロ」の後に「タ」
【００３５】
すなわち、「ワタヒロナベタ」や「ワタヒナロベタ」は上記のルールに従うため、正しい混合であるが、「ワタヒロベナタ」「ワタヒナタベロ」では、前者は「ベ」が「ナ」の前、後者は「タ」が「ロ」の前であるため、上記要件を満たした正しい混合ではない。
【００３６】
この要件を満たすことで、検索サーバ５において算出される編集距離に、図７に示すような性質が生まれる。
【００３７】
すなわち、検索対象の文字列「タナカコウキ」及び「コジマキイチ」と、ブラックリストに含まれる文字列「タナカコウ」及び「コジマキイチロウ」と、検索対象の文字列を混合した結果の文字列「タコナカジマキコウイキチ」との編集距離を算出する。そうすると、「タナカコウキ」と「タナカコウ」との編集距離は「１」であり、「コジマキイチ」と「コジマキチイロウ」との編集距離は「２」であるとすると、「タコナカジマキコウイキチ」と「タナカコウ」との編集距離は６文字増加した分編集距離も＋６となって「７」になる。同様に、「タコナカジマキコウイキチ」と「コジマキチイロウ」との編集距離は６文字増加した分編集距離も＋６となって「８」が得られる。すなわち、文字列混合後も相対的な類似度（＝編集距離）の大小は基本的に維持されるので、名寄せ処理を行う際に用いる閾値を下げる、すなわち編集距離の閾値を上げることで、編集距離自体の計算には影響を与えずに適切な文字列を抽出できるようになる。
【００３８】
なお、別の文字列の方が編集距離が短くなる場合もある。例えば、「ナカジマコウイチ」という文字列がブラックリストに載っているとすると、こちらの編集距離は「４」となって、「タナカコウ」や「コジマキチイロウ」よりも短くなっている。これは、検索サーバ５においてはフィルタできないので、クライアント装置３側でフィルタリングする。
【００３９】
次に、図８乃至図１９を用いて図１に示したシステムの具体的な処理内容を説明する。
【００４０】
まず、クライアント装置３の入力部３１は、検索者からの検索対象文字列の入力を受け付け（ステップＳ１）、第１データ格納部３２に格納する。なお、本実施の形態では、一人分の姓及び名の指定がなされるものとする。すなわち、ここではクエリ姓及びクエリ名とが入力されるものとする。そして、第１抽出部３４及び混合部３６は、秘匿化処理を実施する（ステップＳ３）。この秘匿化処理については、図９乃至図１３を用いて説明する。
【００４１】
第１抽出部３４は、第２データ格納部３３から、ｋ個のダミー姓とｋ個のダミー名とをランダムに抽出し、第３データ格納部３５に格納する（ステップＳ２１）。例えば、第２データ格納部３３に登録されているダミー姓リストから、ランダムにｋ個のダミー姓を抽出する。ダミー姓リストには、複数の姓が登録されている。同様に、第２データ格納部３３に登録されているダミー名リストから、ランダムにｋ個のダミー名を抽出する。ダミー名リストには、複数の名が登録されている。
【００４２】
そして、混合部３６は、出現順番を維持しつつ、ダミー姓の文字をランダムにクエリ姓Ｓに挿入する処理を実施し、処理結果を第４データ格納部３７に格納する（ステップＳ２３）。また、混合部３６は、出現順番を維持しつつ、ダミー名の文字をランダムにクエリ名Ｇに挿入する処理を実施し、処理結果を第４データ格納部３７に格納する（ステップＳ２５）。そして呼出元の処理に戻る。
【００４３】
ステップＳ２３では、クエリ姓に含まれる文字の出現順番を維持するように、ダミー姓についてもそのダミー姓に含まれる文字をその出現順番に従って挿入する。すなわち、ｋ個のダミー姓については、１つのダミー姓についての処理が完了しないと他のダミー姓の処理には移行しない。ステップＳ２５では、クエリ名に含まれる文字の出現順番を維持するように、ダミー名についてもそのダミー名に含まれる文字をその出現順番に従って挿入する。ｋ個のダミー名は、任意の順番（例えば抽出順番）に１つずつ処理される。
【００４４】
ステップＳ２３は、例えば図１０及び図１１に示すような処理フローで処理される。
【００４５】
まず、混合部３６は、変数ｓ＿ｌｅｎにクエリ姓Ｓの文字数を代入する（ステップＳ３１）。また、混合部３６は、カウンタｉを０に初期化する（ステップＳ３３）。また、混合部３６は、変数ｓｄ＿ｌｅｎに、ｉ番目のダミー姓Ｓａｉの文字数を代入し、混合後の文字列の配列ＴにＮＵＬＬ文字を入力し、カウンタｊｘ及びｊｙを０に初期化する（ステップＳ３５）。さらに、混合部３６は、ｊを０に初期化する（ステップＳ３７）。
【００４６】
その後、混合部３６は、０以上１以下の乱数ｂを生成し（ステップＳ３９）、ｂがｓ＿ｌｅｎ／（ｓ＿ｌｅｎ＋ｓｄ＿ｌｅｎ）以上であるか否かを判断する（ステップＳ４１）。すなわち、Ｓの文字数とダミー姓Ｓａｉの文字数との和に対するＳの文字数の比がｂ以上であるか否かを判断する。
【００４７】
この条件を満たす場合には、混合部３６は、Ｔ［ｊ］にＳのｊｘ番目の文字を設定し、ｊを１インクリメントすると共にｊｘについても１インクリメントする（ステップＳ４３）。そして処理は端子Ａを介して図１１の処理に移行する。一方、ステップＳ４１の条件を満たさない場合には、混合部３６は、Ｔ［ｊ］にダミー姓Ｓａｉのｊｙ番目の文字を設定し、ｊを１インクリメントすると共にｊｙについても１インクリメントする（ステップＳ４５）。そして処理は端子Ａを介して図１１の処理に移行する。
【００４８】
図１１の処理の説明に移行して、混合部３６は、ｊｘがｓ＿ｌｅｎとなったか判断する（ステップＳ４７）。すなわち、Ｓの最後の文字まで処理したか判断する。ｊｘがｓ＿ｌｅｎとなった場合には、混合部３６は、Ｔ［ｊ＋１］＝Ｓａｉ［ｊｙ＋１］，．．，Ｔ［ｓ＿ｌｅｎ＋ｓｄ＿ｌｅｎ−１］＝Ｓａｉ［ｓｄ＿ｌｅｎ−１］と設定する（ステップＳ４９）。すなわち、ダミー姓Ｓａｉにおける未処理の文字をその順番で配列Ｔに設定する。そして処理はステップＳ５７に移行する。
【００４９】
一方、ｊｘ＝ｓ＿ｌｅｎではない場合、混合部３６は、ｊｙ＝ｓｄ＿ｌｅｎとなったか判断する（ステップＳ５１）。すなわち、ダミー姓Ｓａｉの最後の文字まで処理したか判断する。ｊｙ＝ｓｄ＿ｌｅｎとなった場合には、混合部３６は、Ｔ［ｊ＋１］＝Ｓ［ｊｘ＋１］，．．，Ｔ［ｓ＿ｌｅｎ＋ｓｄ＿ｌｅｎ−１］＝Ｓ［ｓ＿ｌｅｎ−１］と設定する（ステップＳ５３）。すなわち、Ｓにおける未処理の文字をその順番で配列Ｔに設定する。そして処理はステップＳ５７に移行する。
【００５０】
一方、ｊｙ＝ｓｄ＿ｌｅｎでもない場合には、混合部３６は、ｊがｓ＿ｌｅｎ＋ｓｄ＿ｌｅｎ−１より大きくなっているか判断する（ステップＳ５５）。この条件を満たさない場合には、端子Ｂを介して図１０のステップＳ３９に戻る。一方、この条件を満たす場合には、ステップＳ５７に移行する。
【００５１】
ステップＳ５７に移行すると、混合部３６は、ＳにＴを代入し、ｓ＿ｌｅｎにｓ＿ｌｅｎ＋ｓｄ＿ｌｅｎを代入する（ステップＳ５７）。すなわち、ダミー名Ｓａｉとの混合結果をＳと設定して、次のダミー名Ｓａ(i+1)との混合処理を実施する。また、混合部３６は、ｉを１インクリメントする（ステップＳ５９）。その後、混合部３６は、ｉがｋ−１より大きくなったか判断する（ステップＳ６１）。ｉがｋ−１より大きくない場合には、端子Ｃを介して残りのダミー姓Ｓａｉについての処理を行うため、図１０のステップＳ３５に戻る。一方、ｉがｋ−１より大きくなった、すなわち全てのダミー姓Ｓａｉについての混合処理が完了した場合には、呼出元の処理に戻る。
【００５２】
このようにすれば、クエリ姓Ｓ及びダミー姓Ｓａｉ共に包含される各文字の出現順番を維持しつつ混合することができるようになる。
【００５３】
次に、ステップＳ２５は、例えば図１２及び図１３に示すような処理フローで処理される。
【００５４】
まず、混合部３６は、変数ｇ＿ｌｅｎにクエリ名Ｇの文字数を代入する（ステップＳ７１）。また、混合部３６は、カウンタｉを０に初期化する（ステップＳ７３）。また、混合部３６は、変数ｇｄ＿ｌｅｎに、ｉ番目のダミー名Ｇａｉの文字数を代入し、混合後の文字列の配列ＴにＮＵＬＬ文字を入力し、カウンタｊｘ及びｊｙを０に初期化する（ステップＳ７５）。さらに、混合部３６は、ｊを０に初期化する（ステップＳ７７）。
【００５５】
その後、混合部３６は、０以上１以下の乱数ｂを生成し（ステップＳ７９）、ｂがｇ＿ｌｅｎ／（ｇ＿ｌｅｎ＋ｇｄ＿ｌｅｎ）以上であるか否かを判断する（ステップＳ８１）。すなわち、クエリ名Ｇの文字数とダミー名Ｇａｉの文字数との和に対するクエリ名Ｇの文字数の比がｂ以上であるか否かを判断する。
【００５６】
この条件を満たす場合には、混合部３６は、Ｔ［ｊ］にクエリ名Ｇのｊｘ番目の文字を設定し、ｊを１インクリメントすると共にｊｘについても１インクリメントする（ステップＳ８３）。そして処理は端子Ｄを介して図１３の処理に移行する。一方、ステップＳ８１の条件を満たさない場合には、混合部３６は、Ｔ［ｊ］にダミー名Ｇａｉのｊｙ番目の文字を設定し、ｊを１インクリメントすると共にｊｙについても１インクリメントする（ステップＳ８５）。そして処理は端子Ｄを介して図１３の処理に移行する。
【００５７】
図１３の処理の説明に移行して、混合部３６は、ｊｘがｇ＿ｌｅｎとなったか判断する（ステップＳ８７）。すなわち、Ｇの最後の文字まで処理したか判断する。ｊｘがｇ＿ｌｅｎとなった場合には、混合部３６は、Ｔ［ｊ＋１］＝Ｇａｉ［ｊｙ＋１］，．．，Ｔ［ｇ＿ｌｅｎ＋ｇｄ＿ｌｅｎ−１］＝Ｇａｉ［ｇｄ＿ｌｅｎ−１］と設定する（ステップＳ８９）。すなわち、ダミー名Ｇａｉにおける未処理の文字をその順番で配列Ｔに設定する。そして処理はステップＳ９７に移行する。
【００５８】
一方、ｊｘ＝ｇ＿ｌｅｎではない場合、混合部３６は、ｊｙ＝ｇｄ＿ｌｅｎとなったか判断する（ステップＳ９１）。すなわち、ダミー名Ｇａｉの最後の文字まで処理したか判断する。ｊｙ＝ｇｄ＿ｌｅｎとなった場合には、混合部３６は、Ｔ［ｊ＋１］＝Ｇ［ｊｘ＋１］，．．，Ｔ［ｇ＿ｌｅｎ＋ｇｄ＿ｌｅｎ−１］＝Ｇ［ｇ＿ｌｅｎ−１］と設定する（ステップＳ９３）。すなわち、Ｇにおける未処理の文字をその順番で配列Ｔに設定する。そして処理はステップＳ９７に移行する。
【００５９】
一方、ｊｙ＝ｇｄ＿ｌｅｎでもない場合には、混合部３６は、ｊがｇ＿ｌｅｎ＋ｇｄ＿ｌｅｎ−１より大きくなっているか判断する（ステップＳ９５）。この条件を満たさない場合には、端子Ｅを介して図１２のステップＳ７９に戻る。一方、この条件を満たす場合には、ステップＳ９７に移行する。
【００６０】
ステップＳ９７に移行すると、混合部３６は、ＧにＴを代入し、ｇ＿ｌｅｎにｇ＿ｌｅｎ＋ｇｄ＿ｌｅｎを代入する（ステップＳ９７）。すなわち、ダミー名Ｇａｉとの混合結果をＧと設定して、次のダミー名Ｇａ(i+1)との混合処理を実施する。また、混合部３６は、ｉを１インクリメントする（ステップＳ９９）。その後、混合部３６は、ｉがｋ−１より大きくなったか判断する（ステップＳ１０１）。ｉがｋ−１より大きくない場合には、端子Ｆを介して残りのダミー名Ｇａｉについての処理を行うため、図１２のステップＳ７５に戻る。一方、ｉがｋ−１より大きくなった、すなわち全てのダミー名Ｇａｉについての混合処理が完了した場合には、呼出元の処理に戻る。
【００６１】
このようにすれば、クエリ名Ｇ及びダミー名Ｇａｉ共に包含される各文字の出現順番を維持しつつ混合することができるようになる。
【００６２】
図８の処理の説明に戻って、クエリ送信部３８は、第４データ格納部３７に格納されている、混合処理後のクエリ姓及びクエリ名を連結して、当該クエリ姓及びクエリ名を含むクエリを、検索サーバ５に送信する（ステップＳ５）。
【００６３】
これに対して、検索サーバ５は、クライアント装置３からクエリを受信し（ステップＳ７）、検索処理を実施する（ステップＳ９）。検索処理は、例えば図１４に示すような処理である。
【００６４】
検索サーバ５は、第１ＤＢ５１及び第２ＤＢ５２等における未処理の被検索文字列を１つ読み出す（ステップＳ１１１）。そして、検索サーバ５は、クエリと被検索文字列との編集距離を算出する（ステップＳ１１３）。
【００６５】
編集距離の算出には、Levenshtein distanceと呼ばれる手法が一般的に用いられる。この手法の処理フローを図１５乃至図１９を用いて説明する。
【００６６】
検索サーバ５は、文字列ｓｔｒ＿１［１，．．，Ｘｍａｘ］及びｓｔｒ＿２［１，．．．，Ｙｍａｘ］に、クエリの文字列と被検索文字列とを設定する（ステップＳ１２１）。また、検索サーバ５は、初期設定として、ｄ［ｘ，０］＝Ｄのｘ倍、ｄ［０，ｙ］＝Ｉのｙ倍を、０≦ｘ≦Ｘｍａｘ及び０≦ｙ≦Ｙｍａｘについて設定する（ステップＳ１２３）。Ｄは、削除コストの重みであり、Ｉは挿入コストの重みである。
【００６７】
例えば、「ワタナベ」と「ワタベ」との間についての編集距離を算出する場合を一例として説明する。ｄ［ｘ，ｙ］という配列は、図１６に示すような配列である。すなわち、各文字列の先頭に空白を挿入した状態で、両文字列を一致させるためにどのように修正するのか、すなわち「修正文字数×修正操作の重み」について文字毎に登録するものである。例えば、「  ワタベ」の先頭空白と「  ワタナベ」の先頭空白とは、一致しているのでｄ［０，０］＝０であり、「  ワタベ」の先頭空白と「  ワタナベ」の「  ワ」とでは後者を１文字削除すれば一致するので、ｄ［１，０］＝１Ｄとなる。「  ワタベ」の先頭空白と「  ワタナベ」の「  ワタ」とでは後者を２文字削除すれば一致するので、ｄ（２，０）＝２Ｄとなる。以下同様である。一方、「  ワタベ」の「  ワ」と「  ワタナベ」の先頭空白とでは後者に「ワ」を挿入すると一致するので、ｄ［０，１］＝１Ｉとなる。「  ワタベ」の「  ワタ」と「  ワタナベ」の先頭空白とでは後者に「ワタ」を挿入すると一致するので、ｄ［０，２］＝２Ｉとなる。以下同様である。
【００６８】
また、検索サーバ５は、ｙ＝１に設定し（ステップＳ１２５）、さらにｘ＝１を設定する（ステップＳ１２７）。
【００６９】
その後、検索サーバ５は、ｓｔｒ＿１［ｘ］＝ｓｔｒ＿２［ｙ］であるか否かを判断する（ステップＳ１２９）。ｓｔｒ＿１［ｘ］＝ｓｔｒ＿２［ｙ］であれば、検索サーバ５は、ｄ［ｘ，ｙ］＝ｍｉｎ（ｄ［ｘ，ｙ−１］＋Ｉ，ｄ［ｘ−１，ｙ−１］，ｄ［ｘ−１，ｙ］＋Ｄ）と設定する（ステップＳ１３１）。そしてステップＳ１３５に移行する。一方、ｓｔｒ＿１［ｘ］＝ｓｔｒ＿２［ｙ］でなければ、検索サーバ５は、ｄ［ｘ，ｙ］＝ｍｉｎ（ｄ［ｘ，ｙ−１］＋Ｉ，ｄ［ｘ−１，ｙ−１］＋Ｓ，ｄ［ｘ−１，ｙ］＋Ｄ）と設定する（ステップＳ１３３）。そしてステップＳ１３５に移行する。
【００７０】
このアルゴリズムでは、図１７に示すように、右下のマスＭのコストを算出する場合には、Ｍの上のマスの文字列から１文字挿入することで一致させる場合のコスト（Ｍの上のマスのコスト＋１文字挿入コストＩ）と、Ｍの左斜め上のマスの文字列の最後の文字を１文字置換することで一致させる場合のコスト（Ｍの左斜め上のマスのコスト＋１文字置換コストＳ）と、Ｍの左のマスの最後の文字を１文字削除することで一致させる場合のコスト（Ｍの左のマスのコスト＋１文字削除コストＤ）とのうち最小のコストを採用する。但し、処理に係る文字が両文字列で一致する場合には、Ｍの左斜め上のマスのコストに加えるべき置き換えコストＳは０となるので、ステップＳ１３１とＳ１３３との差が生じている。
【００７１】
そして、検索サーバ５は、ｘを１インクリメントして（ステップＳ１３５）、ｘがＸｍａｘを超えたか判断する（ステップＳ１３７）。ｘがＸｍａｘ以下であれば、処理はステップＳ１２９に戻る。一方、ｘがＸｍａｘを超えていると、端子Ｇを介して図１８の処理に移行する。
【００７２】
図１８の処理の説明に移行して、検索サーバ５は、ｙを１インクリメントして（ステップＳ１３９）、ｙがＹｍａｘを超えているか判断する（ステップＳ１４１）。ｙがＹｍａｘ以下であれば、端子Ｈを介して処理は図１５のステップＳ１２７に戻る。一方、ｙがＹｍａｘを超えていれば、検索サーバ５は、ｄ［Ｘｍａｘ，Ｙｍａｘ］を、編集距離として出力する（ステップＳ１４３）。そして処理は呼出元の処理に戻る。
【００７３】
このようにすれば、例えば図１９に示すように、矢印の順番で処理を行って、図１７で示したように３つのマスのコストから各マスのコストを算出して、最後にｄ［４，３］のコストが最終的な編集距離となる。なお、ハッチング付きのマスについてはステップＳ１３１で編集距離が決定されたマスである。
【００７４】
図１４の処理の説明に戻って、検索サーバ５は、算出された編集距離が閾値以下であるか否かを判断する（ステップＳ１１５）。本実施の形態では、クエリの文字列に含まれる文字数Ｑと、被検索文字列に含まれる文字の文字数Ｌと、本来の閾値Ｅとから、Ｑ−Ｌ＋Ｅを閾値として採用する。Ｑ−Ｌは、混合処理による閾値のオフセットを示している。但し、例えば本来の検索対象文字列に含まれる文字の文字数をＬとして、クライアント装置３からクエリにより検索サーバ５に送信することにして、閾値決定に用いるようにしても良い。
【００７５】
編集距離が閾値を超えていれば処理はステップＳ１１９に移行する。一方、編集距離が閾値以下であれば、検索サーバ５は、検索結果に、被検索文字列を追加する（ステップＳ１１７）。そして、検索サーバ５は、第１ＤＢ５１及び第２ＤＢ５２等において未処理の被検索文字列が存在するか判断し（ステップＳ１１９）、未処理の被検索文字列が存在すれば処理はステップＳ１１１に戻る。一方、未処理の被検索文字列が存在しない場合には、処理は呼出元の処理に戻る。
【００７６】
このような処理を実施すれば、混合処理の影響で伸びた編集距離を勘案した閾値をベースに、編集距離が閾値以下の文字列を抽出することができるようになる。
【００７７】
図８の処理の説明に戻って、検索サーバ５は、検索結果を、クエリの送信元のクライアント装置３に返信する（ステップＳ１１）。クライアント装置３の検索結果受信部３９は、検索結果を受信すると、第５データ格納部４０に格納する（ステップＳ１３）。第２抽出部４１は、第１データ格納部３２に格納されている検索対象文字列から、クエリに対応する検索結果を、第５データ格納部４０に格納されている検索結果を抽出し、第６データ格納部４２に格納する（ステップＳ１５）。そして、出力部４３は、第６データ格納部４２に格納されているデータを、出力装置その他の装置に出力する。
【００７８】
ステップＳ１５の処理は、どのような処理であっても良いが、例えば再度検索対象文字列と検索結果に含まれる文字列との編集距離で判断するようにしても良い。
【００７９】
このようにすれば、クエリを秘匿化して、さらに検索結果についても秘匿化することができるようになる。
【００８０】
［実施の形態２］
第１の実施の形態では、ダミー文字列をランダムに選んでいた。これでも十分な秘匿化が可能であるが、本実施の形態では、文字間の共起を考慮したダミー文字列の選択を行うことで、検索サーバ５側から見た候補数を増加させ、秘匿化の効果を高める。
【００８１】
本実施の形態の内容を詳細に説明する前に、文字間の共起を利用したプライバシ保護効果の向上の考え方について述べる。「共起」とは、文字間の発生頻度の相関の強さを表す。例えば、「タナカ」「タジマ」などの姓が頻出する場合、「タ」に対して「ナカ」は接尾語として相関の高い文字であり、「タ」に対して「ジマ」も接尾語として相関の高い文字である。また、「サトウ」「カトウ」「サイトウ」「イトウ」などの姓が頻出する場合、「トウ」に対して「サ」「カ」「サイ」「イ」が接頭語として相関の高い文字である。この相関の強さを「共起率」と呼ぶ。相関が高い場合は「共起率が高い」と呼び、相関が低い場合は「共起率が低い」と呼ぶ。この共起率を考慮したダミー文字列の選択を行うことで、検索サーバ５側から見た候補数がさらに増加するため、秘匿化をさらに向上させることが出来る。
【００８２】
上でも述べたが、「トウ」に対して「サ」「カ」「イ」の共起率が高い。すなわち、「サトウ」を秘匿化した結果が「イトウ」や「カトウ」にも見えることが、秘匿化としては望ましい。すなわち、「サトウ」を秘匿化する場合は、共起率が高い「イ」「カ」の文字をなるべく多く含むダミー文字列が望ましい。但し、「サ」は共起率が高いが、除外する。
【００８３】
共起率を考慮しない場合として、これらの文字を含まない「マチダ」がダミー文字列として選ばれる場合がある。この秘匿化結果は「マサチトウダ」となるが、この秘匿化結果を検索サーバ５から見ると、「マチダ」もしくは「サトウ」の２種類が候補名となる。
【００８４】
共起率を考慮した場合、「イ」「カ」を多く含む「カイヤ」がダミー文字列として選ばれる。この秘匿化結果は「カサイヤトウ」となるが、検索サーバ５側から見た場合、「カトウ」「サトウ」「イトウ」「サイトウ」「カイヤ」「カサイ」の６種類が候補名となる。このように、検索結果に多くの文字列が含まれるようになれば、それだけ検索結果から検索対象文字列の漏洩を防止できるようになる。
【００８５】
本実施の形態のように共起率を用いる場合には、図２０及び図２１のような姓についての共起テーブル及び名についての共起テーブルを、第２データ格納部３３に追加で格納しておく。そして、第１抽出部３４が、第１データ格納部３２に格納されている検索対象文字列に基づき、共起率が高い文字又は文字列を抽出して、当該抽出された文字又は文字列を含む姓及び名をさらに抽出する。
【００８６】
図２０は、姓についての共起テーブルの一例を示す。図２０の例では、姓に「トウ」などの文字又は文字列が出現した場合に共起率が閾値以上となる文字又は文字列「サ」などが登録されている。同様に、図２１は、名についての共起テーブルの一例を示す。図２１の例では、名に「ロウ」などの文字又は文字列が出現した場合に共起率が閾値以上となる文字又は文字列「イチ」などが登録されている。
【００８７】
また、図９の秘匿化処理は、図２２に示すような処理に変更される。
【００８８】
第１抽出部３４は、第１データ格納部３２に格納されている検索対象文字列の姓Ｓと名Ｇについて、共起テーブルから共起率が閾値以上の文字又は文字列（共起文字と呼ぶ）Ｓｃｐ（０≦ｐ≦Ｐ−１）及びＧｃｑ（０≦ｑ≦Ｑ−１）を抽出する（ステップＳ２０１）。但し、姓Ｓにおいて共起文字が出現している場合にはその共起文字は採用しない。また、名Ｇについても同様である。例えば、検索対象文字列の姓Ｓが「イトウ」の場合には、「トウ」の接頭語「イ」については、共起文字として抽出しない。
【００８９】
そして、第１抽出部３４は、ダミー姓の抽出処理を実施する（ステップＳ２０３）。このダミー姓の抽出処理については、図２３を用いて説明する。
【００９０】
まず、第１抽出部３４は、ｉを１に初期化し（ステップＳ２１１）、ダミー文字列（ダミー姓の抽出処理であれば姓）をランダムに１つ選択する（ステップＳ２１３）。そして、第１抽出部３４は、選択したダミー文字列に含まれる共起文字（Ｓｃｐ又はＳｃｑ）の文字数を計数する（ステップＳ２１５）。「サトウ」の「トウ」について共起率が閾値以上の共起文字として「イ」「カ」が特定されたものとする。この場合、「カイヤ」というダミー文字列については共起文字の個数は「２」となる。また、「ヒロイ」というダミー文字列については共起文字の個数は「１」となる。
【００９１】
そして、第１抽出部３４は、計数された文字数が閾値以上であるか判断する（ステップＳ２１７）。ダミー文字列に含まれる文字数に対する計数文字数の割合で判断しても良い。
【００９２】
文字数が閾値未満であれば、このダミー文字列を不採用として処理はステップＳ２２３に移行する。一方、文字数が閾値以上であれば、第１抽出部３４は、ダミー文字列をＳａｉ又はＧａｉに設定する（ステップＳ２１９）。ダミー姓の抽出処理であればＳａｉに設定し、ダミー名の抽出処理であればＧａｉに設定する。そして、第１抽出部３４は、ｉを１インクリメントする（ステップＳ２２１）。さらに、第１抽出部３４は、ｉがＮを超えているか判断し（ステップＳ２２３）、ｉがＮ以下であれば処理はステップＳ２１３に戻る。一方、ｉがＮを超えていれば、呼出元の処理に戻る。
【００９３】
このように図２３の処理フローでは、どのような共起文字でも各ダミー文字列において閾値個数以上の文字が含まれていることを担保しているが、本処理はこれに限定されるものではない。例えば、ｎ個のダミー文字列を抽出するのであれば、ｎ個のうち８０％といった所定の閾値を超える割合で共起文字が含まれているダミー文字列が抽出できればよいという場合もある。さらに、できるだけ共起文字の全ての種類がダミー文字列に含まれる方が好ましいので、共起文字のカバー率が所定の閾値以上になるようにダミー文字列を抽出するようにしても良い。
【００９４】
図２２の処理の説明に戻って、第１抽出部３４は、ダミー名の抽出処理を実施する（ステップＳ２０５）。この処理は、図２３に示した処理をダミー名について実施する。
【００９５】
そして、混合部３６は、出現順番を維持しつつ、ダミー姓の文字をランダムにクエリ姓Ｓに挿入する処理を実施し、処理結果を第４データ格納部３７に格納する（ステップＳ２０７）。また、混合部３６は、出現順番を維持しつつ、ダミー名の文字をランダムにクエリ名Ｇに挿入する処理を実施し、処理結果を第４データ格納部３７に格納する（ステップＳ２０９）。そして呼出元の処理に戻る。ステップＳ２０７及びＳ２０９については、図１０及び図１３の処理フローで処理される。
【００９６】
このようにすれば、検索サーバ５の処理結果である検索結果に、ダミー文字列由来の検索結果が含まれる可能性が高まり、結果として検索結果についての秘匿化も向上する。
【００９７】
以上本技術の実施の形態を説明したが、本技術はこれらに限定されるものではない。
【００９８】
例えば図２の機能ブロック図は一例であって必ずしも実際のプログラムモジュール構成と一致しない場合もある。また、処理フローについても処理結果が変わらない限り、ステップを並列に実行したり、実行順序を入れ替えたりすることができる。
【００９９】
また、クライアント装置３及び検索サーバ５の機能は、１台のコンピュータで実施される場合もあれば、複数台のコンピュータで実施される場合もある。
【０１００】
なお、上で述べたクライアント装置３及び検索サーバ５は、コンピュータ装置であって、図２４に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１０１】
以上述べた本実施の形態をまとめると、以下のようになる。
【０１０２】
本実施の形態に係る情報処理方法は、（Ａ）検索対象として指定された第１の文字列に対して混合すべき１又は複数の第２の文字列を取得する取得処理と、（Ｂ）第１の文字列に含まれる複数の文字の出現順番又は順序関係及び１又は複数の第２の文字列に含まれる複数の文字の出現順番又は順序関係を維持しつつ第１の文字列に対して１又は複数の第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する処理と、（Ｃ）データ格納部に格納されている第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する処理とを含む。
【０１０３】
このようにすればクエリ自体が秘匿化され、検索コンピュータにおいて検出される検索結果についても真の検索結果を特定できないため、クエリの秘匿化がなされる。
【０１０４】
また、本実施の形態に係る情報処理方法は、（Ｄ）検索コンピュータから、複数の第４の文字列を含む検索結果を受信した場合、複数の第４の文字列から、第１の文字列に対応する文字列を抽出する処理をさらに含むようにしても良い。単に、複数の第４の文字列を検索者に提示しても、第１の文字列が分かっているので抽出できるが、このように自動的に抽出するようにしても良い。
【０１０５】
また、上で述べた取得処理が、（ａ１）文字又は文字列毎に共起率が閾値以上の文字又は文字列が対応付けられて格納されている第２のデータ格納部から、第１の文字列に含まれる文字又は文字列について対応付けられている文字又は文字列であって第１の文字列に含まれない文字又は文字列を抽出する処理と、（ａ２）抽出された文字又は文字列の少なくともいずれかを含む１又は複数の第２の文字列を取得する第２の取得処理とを含むようにしても良い。このようにすることで、検索結果に第１の文字列との関係が薄い文字列が検索結果に入りやすくなるため、検索結果の秘匿化も向上する。
【０１０６】
また、上で述べた取得処理が、（ａ１１）文字又は文字列毎に共起率が閾値以上の文字又は文字列が対応付けられて格納されている第２のデータ格納部から、第１の文字列に含まれる文字又は文字列について対応付けられている文字又は文字列であって第１の文字列に含まれない文字又は文字列を抽出する処理と、（ａ１２）抽出された文字又は文字列を用いて第２の文字列を選択する選択処理とを含むようにしても良い。この場合、上で述べた選択処理が、（ａ１２−１）抽出された文字又は文字列のうち、１つの第２の文字列に含まれる文字又は文字列の数又は割合が第１の所定値以上となるように、第２の文字列を選択する処理、（ａ１２−２）第２の文字列の選択総数が予め設定されている場合に、抽出された文字又は文字列の少なくともいずれかを含む第２の文字列の、選択総数に対する割合が第２の所定値以上であるように、選択総数分の第２の文字列を取得する処理、又は（ａ１２−３）抽出された文字又は文字列が複数種類であり、第２の文字列が複数である場合、抽出された文字又は文字列のうち当該複数の第２の文字列に含まれる文字又は文字列の種類の数又は割合が第３の所定値以上となるように、複数の第２の文字列を選択する処理を含むようにしても良い。第２の文字列については様々な選択方法がある。
【０１０７】
また、編集距離に対する閾値が第３の文字列の文字数に基づき決定されるか、編集距離に対する閾値が第３の文字列の文字数及び第１の文字列の文字数に基づき決定されるようにしても良い。編集距離の性質に基づくものである。
【０１０８】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。
【０１０９】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１１０】
（付記１）
コンピュータが実行する情報処理方法であって、
検索対象として指定された第１の文字列に混合する第２の文字列を取得する取得処理と、
前記第１の文字列に含まれる複数の文字の順序関係と、前記第２の文字列に含まれる複数の文字の順序関係とを維持しつつ、前記第１の文字列に対して前記第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する処理と、
前記データ格納部に格納されている前記第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する処理と、
を含む情報処理方法。
【０１１１】
（付記２）
前記コンピュータが、前記検索コンピュータから、複数の第４の文字列からなる検索結果を受信し、前記複数の第４の文字列から、前記第１の文字列に対応する文字列を抽出する処理
をさらに含む付記１記載の情報処理方法。
【０１１２】
（付記３）
前記取得処理は、
文字又は文字列毎に共起率が閾値以上の文字又は文字列が対応付けられて格納されている第２のデータ格納部から、前記第１の文字列に含まれる文字又は文字列について対応付けられている文字又は文字列であって前記第１の文字列に含まれない文字又は文字列を抽出する処理により抽出された前記文字又は文字列の少なくともいずれかを含む第２の文字列を取得する処理
である請求項１又は２記載の情報処理方法。
【０１１３】
（付記４）
前記取得処理が、
文字又は文字列毎に共起率が閾値以上の文字又は文字列が対応付けられて格納されている第２のデータ格納部から、前記第１の文字列に含まれる文字又は文字列について対応付けられている文字又は文字列であって前記第１の文字列に含まれない文字又は文字列を抽出する処理と、
抽出された前記文字又は文字列を用いて前記第２の文字列を選択する選択処理と、
を含み、
前記選択処理が、
抽出された前記文字又は文字列のうち、１つの第２の文字列に含まれる文字又は文字列の数又は割合が第１の所定値以上となるように、前記第２の文字列を選択する処理、
前記第２の文字列の選択総数が予め設定されている場合に、抽出された前記文字又は文字列の少なくともいずれかを含む第２の文字列の、前記選択総数に対する割合が第２の所定値以上であるように、前記選択総数分の第２の文字列を取得する処理、又は
抽出された前記文字又は文字列が複数種類であり、前記第２の文字列が複数である場合、抽出された前記文字又は文字列のうち当該複数の第２の文字列に含まれる文字又は文字列の種類の数又は割合が第３の所定値以上となるように、前記複数の第２の文字列を選択する処理
を含む請求項１又は２記載の情報処理方法。
【０１１４】
（付記５）
前記編集距離に対する閾値が、前記第３の文字列の文字数に基づき、または前記第３の文字列の文字数及び前記第１の文字列の文字数に基づき決定される
付記１乃至４のいずれか１つ記載の情報処理方法。
【０１１５】
（付記６）
検索対象として指定された第１の文字列に混合する第２の文字列を取得する取得処理と、
前記第１の文字列に含まれる複数の文字の順序関係と、前記第２の文字列に含まれる複数の文字の順序関係とを維持しつつ、前記第１の文字列に対して前記第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する処理と、
前記データ格納部に格納されている前記第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する処理と、
を、コンピュータに実行させるためのプログラム。
【０１１６】
（付記７）
検索対象として指定された第１の文字列に混合する第２の文字列を取得し、前記第１の文字列に含まれる複数の文字の順序関係と、前記第２の文字列に含まれる複数の文字の順序関係とを維持しつつ、前記第１の文字列に対して前記第２の文字列を混合することで第３の文字列を生成し、データ格納部に格納する混合部と、
前記データ格納部に格納されている前記第３の文字列を含むクエリを、編集距離を用いて文字列検索を行う検索コンピュータに対して出力する出力部と、
を有する情報処理装置。
【符号の説明】
【０１１７】
１  ネットワーク
３  クライアント装置
５  検索サーバ
５１  第１ＤＢ
５２  第２ＤＢ
３１  入力部
３２  第１データ格納部
３３  第２データ格納部
３４  第１抽出部
３５  第３データ格納部
３６  混合部
３７  第４データ格納部
３８  クエリ送信部
３９  検索結果受信部
４０  第５データ格納部
４１  第２抽出部
４２  第６データ格納部
４３  出力部
【図１】
0005910337.tif 000002
【図２】
0005910337.tif 000003
【図３】
0005910337.tif 000004
【図４】
0005910337.tif 000005
【図５】
0005910337.tif 000006
【図６】
0005910337.tif 000007
【図７】
0005910337.tif 000008
【図８】
0005910337.tif 000009
【図９】
0005910337.tif 000010
【図１０】
0005910337.tif 000011
【図１１】
0005910337.tif 000012
【図１２】
0005910337.tif 000013
【図１３】
0005910337.tif 000014
【図１４】
0005910337.tif 000015
【図１５】
0005910337.tif 000016
【図１６】
0005910337.tif 000017
【図１７】
0005910337.tif 000018
【図１８】
0005910337.tif 000019
【図１９】
0005910337.tif 000020
【図２０】
0005910337.tif 000021
【図２１】
0005910337.tif 000022
【図２２】
0005910337.tif 000023
【図２３】
0005910337.tif 000024
【図２４】
0005910337.tif 000025