(57)【特許請求の範囲】
【請求項１】
文字列又は音声認識により変換された文字列を検索文字列として入力するインタフェースを備え、複数の検索対象文書から前記検索文字列と類似する部分を含む検索対象文書を検索する検索装置において、
大量の文書における複数の音節又は音素（以下、「サブワード」という）から予め決められた所望数のサブワードを繋げた組み合わせで形成される音節列又は音素列（以下、「サブワード連鎖」という）を作成し、前記各サブワード連鎖間の距離に基づいてクラスタリングした複数のサブワード連鎖が属するグループを音節列クラスタ又は音素列クラスタ（以下、「サブワード連鎖クラスタ」という）として登録し、登録された複数のサブワード連鎖クラスタと前記検索対象文書との音素列同士を比較して類似度をそれぞれ算出し、前記各サブワード連鎖クラスタに対応させた類似度のテーブルを検索用INDEXとして予め作成する検索用INDEX作成手段と、
前記インタフェースに入力された検索文字列を構成する音節又は音素から前記所望数を繋げた複数の音節列又は音素列をサブワード連鎖として抽出するサブワード連鎖抽出手段と、
前記サブワード連鎖抽出手段により抽出した各サブワード連鎖について、各サブワード連鎖が属するサブワード連鎖クラスタに対応する各類似度を前記検索用INDEXから求め、前記各類似度の合計を前記各検索対象文書に対する類似度として演算する類似度演算手段と、
前記類似度に基づいた文書データの検索結果を出力する出力インタフェースと
を具備することを特徴とする類似文書検索装置。
【請求項２】
前記類似度演算手段は、検索用INDEXから求めた前記各サブワード連鎖が属するサブワード連鎖クラスタに対応する類似度の合計が高い順で上位複数個の検索対象文書候補の絞り込みを行う第１パスINDEX検索と、
前記上位複数個の検索対象文書候補を音素列に変換し、検索文字列の音素列との間で音素を単位としたＤＰマッチングを行って得られる類似度により出力順位を決める第２パスＤＰマッチング検索とを含む請求項１に記載の類似文書検索装置。
【請求項３】
前記INDEX作成手段における類似度は、各サブワード連鎖クラスタを代表する音節列または音素列と検索対象文書をそれぞれ音素列に変換し、二つの音素列において音素を単位とした端点フリーＤＰマッチングを行って得られた累積ＤＰマッチングコスト値に基づいて算出する請求項１に記載の類似文書検索装置。
【請求項４】
前記音素列間の端点フリーＤＰマッチングは、音素の置換コスト値、音素の挿入コスト値、音素の脱落コスト値を音声認識実験による音素混同行列に基づいて計算する請求項３に記載の類似文書検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ関連用語によるコンテンツの検索システムや、大量の文書データ（テキスト文書）を検索するテキストの検索システムにおいて使用される検索装置に関し、クエリと称する検索用の特定の文字列（以降、「検索文字列」と言う）が検索対象とする文書の原文と一致しない場合であっても、類似度を高速に判別して複数の検索対象文書から目的の文書を検索できるようにした類似文書検索装置に関する。
【背景技術】
【０００２】
例えば、非特許文献1のＦＡＳＴＡプログラムでは、N-Gram要素（連続したN個文字）を単位とする２種類の検索手順を実行（２パス検索）することで、指定したDNA配列に類似する配列の高速データベース検索を実現している。
すなわち、初めに、検索対象となる文字列（DNAデータベースに格納しているプレーンテキストフォーマットのタンパク質のアミノ酸配列）をN-Gram要素に分解し、上記N-Gram要素とそれの出現箇所を照合用のテーブルに登録する。
検索時では、第１パスで検索文字列（指定したタンパク質のアミノ酸配列）を同様にN-Gram要素に分解して照合用のテーブルを検索し、検索文字列のN-Gram要素が含まれる割合（一致度）の高い検索対象の部分（DNAデータベースのタンパク質のアミノ酸配列中の数箇所）を検索対象候補として出力する。
そして、第２パスでこれらの候補に限られた領域でスミス−ウォーターマン法に基づく動的計画法演算を行う。
【０００３】
また、特許文献１の「音声検索システム」では、検索対象となるニュースや講演などの音声データを音声認識により予め文字列に変換しておき、入力された検索文字列で検索するシステムにおいて、検索文字列に対応する音声部分が誤認識されていて、音声認識結果の文字列と検索文字列と一致しない場合にも検索可能で、かつ高速な検索を可能にする技術が開示されている。検索手法としては、上記音声認識に使われた認識辞書の単語において、検索文字列と音響的に類似度が高い単語列候補（認識辞書の単語の並び）を効率的に求め、上記単語列候補の中に上記認識結果に出現したものを検索結果として出力する。上記単語列候補を求める際に、入力された検索文字列を音素列に変換し、連続単語音声認識で用いられているフレーム同期ビームサーチ（入力特徴ベクトルを上記検索文字列の音素列に置き換えること）やレベルビルディングなどの手法を用い、検索文字列の音素列を認識辞書中の単語の様々な組み合わせの音素列と照合することによって、類似度の高い単語組合せを候補として選び出す。
【０００４】
また、本発明者らは、歌詞の一部分を入力して楽曲を検索する文書データ検索装置において、ユーザが聞き間違えて覚えてしまった歌詞で検索した場合にも、類似度を高速に判別して目的歌詞の検索ができる検索装置を特願２００８−２９７３８７号（特許文献２）で提案した。
この検索装置では、まず入力される検索文字列に出現しそうな単語を予測し、検索対象である文書（歌詞）との類似度を表す距離値を予め計算しておき、INDEXに登録する。上記距離値の計算方法は、各検索対象の文書において、予測される検索文字列について構成単語を抽出し、それぞれ音素列に変換してから、上記単語の音素列と逐次に音素ベースでのＤＰマッチングを行い、最も低いＤＰマッチングコスト値を当文書と予測した単語の距離値にするというものである。
検索時には、検索文字列から単語を抽出し、各検索対象文書に対して上記INDEXを検索し、検索文字列を構成する単語（出現順番を無視）に対する距離値を合計する。合計距離値が小さい検索対象文書が検索文字列との類似度が高いと判断され、検索結果として出力される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−３１２７８号公報
【特許文献２】特願２００８−２９７３８７号
【非特許文献】
【０００６】
【非特許文献１】プロシーディングス オブ ナショナル アカデミー オブ サイエンシズ ユーエスエー ８５巻，２４４４−２４４８頁(１９８８年)(Proc.Natl. Acad. Sci. U.S.A., vol.85, pp.2444−2448(1988)）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
歌詞検索や映画の台本検索などの文書検索を行うに際し、検索文字列に聞き間違いや記憶違い等に起因する部分的誤りが含まれることがしばしば生じる。例えば、歌詞の原文に存在する文字列が「ムスウノヒカリ」であるのに対して、検索文字列について、表記が異なるが音響的には類似する「マッスグナヒカリ」と誤って入力して検索するような場合である。
【０００８】
このような検索を行う場合、非特許文献１では２パス処理による検索高速化を実現しているが、第1パスでは、検索対象となる文書や文字列において、検索文字列のN-Gram要素が含まれる割合（一致度）の高い部分を検索対象候補とするため、含まれないN-Gram要素と検索対象との類似度を考慮しないという問題点がある。
すなわち、上述した検索例に対しては、検索対象となる「ムスウノヒカリ」において、検索文字列「マッスグナヒカリ」のN-Gram要素中に「ヒカリ」だけ含まれていて、N-Gram要素の一致度が低くなるため、正解の「ムスウノヒカリ」が第1パスにて検索候補から外されてしまい検索精度が低くなる。
【０００９】
特許文献１のシステムでは音響的な類似度を考慮しているが、検索するたびに、音声認識辞書の全ての単語において、検索文字列の類似単語列候補を求めるための類似度計算を行う必要がある。現状では、Web上の検索対象が多い（商用歌詞検索システムでは数万、数十万以上の歌詞を対象とする）場合に、類似度を計算する際の探索空間（単語組合せの種類数）が膨大になるため、オンラインでの検索が非常に遅くなるという問題点があった。
【００１０】
特許文献２の検索装置では、検索文字列に出現可能な単語を予測してINDEXに登録するため、実際に入力された検索文字列の単語が未登録（OUT-OF-VOCABULRY問題）である場合には、オンラインでその検索文字列を音素列に変換し、各検索対象文書の音素列とのＤＰマッチングを行い、その結果得られたＤＰマッチングコスト値に基づいて検索を行うので、検索時間が遅くなるという問題点があった。また、仮に存在する全ての単語をINDEXに登録するとすれば、INDEXのサイズが膨大になるため、実際のシステムへの実装にはコストが高くなるという問題点があった。
【００１１】
本発明は、上記実情に鑑みて提案されたもので、文書検索を行うに際して、検索文字列に聞き間違いや記憶違い等に起因する部分的誤りが含まれる場合であっても、複数の検索対象文書から目的の文書の検索を高速かつ高精度に実現できる類似文書検索装置を提供することを目的としている。
【課題を解決するための手段】
【００１２】
本発明は上記目的を達成するため、類似文書検索装置において、文書の構成要素となる、連続する一定数の音素または音節（サブワード連鎖）を単位として検索文字列と検索対象文書との類似度を考慮するものである。そして、検索文字列と検索対象文書との類似度を考慮する場合、予め構築した検索用INDEXを用いて第１段階の検索（第１パス）を行って検索対象文書の候補を絞り、続いて第２段階の検索（第２パス）を行う２（種類の）パス検索アルゴリズムを導入する。
【００１３】
先ず、上記検索用INDEXの構築では、未知の検索文字列に対応するため、Ｎ個の音節（又は音素）の組合せ若しくは大量の文書から所望数の音節（又は音素）から構成される音節列（音節N-Gram）又は音素列(音素N-Gram）をサブワード連鎖として集める。
音節列（音節N-Gram）又は音素列(音素N-Gram）は、その長さ（音節又は音素の数）によって種類が非常に多くなるため、音節N-Gram又は音素N-Gram同士間の距離に基づいてクラスタリングを行う。クラスタリングで得た音節列クラスタ又は音素列クラスタ（サブワード連鎖クラスタ）と検索対象文書（歌詞データ、台本など）との各類似度に基づいて予め検索用INDEXのテーブルを作成しておく。
【００１４】
検索文字列の検索時には、上述の第１パスで検索文字列を複数のサブワード連鎖に変換し、検索用INDEXを用いた高速な探索によりサブワード連鎖と類似度の高い検索対象候補の絞り込みを行い、上述の第２パスで絞り込んだ検索対象候補と検索文字列との音素列における音素ベースでの端点フリーＤＰマッチングによる高精度探索を行うものである。
【００１５】
すなわち、請求項１の類似文書検索装置は、文字列又は音声認識により変換された文字列を検索文字列として入力するインタフェースを備え、複数の検索対象文書から前記検索文字列と類似する部分を含む検索対象文書を検索する検索装置において、次の構成を含むことを特徴としている。
INDEX作成手段。INDEX作成手段は、大量の文書における複数の音節又は音素（以下、「サブワード」という）から予め決められた所望数のサブワードを繋げた組み合わせで形成される音節列又は音素列（以下、「サブワード連鎖」という）を作成し、前記各サブワード連鎖間の距離に基づいてクラスタリングした複数のサブワード連鎖が属するグループを音節列クラスタ又は音素列クラスタ（以下、「サブワード連鎖クラスタ」という）として登録し、登録されたサブワード連鎖クラスタと前記検索対象文書との音素列同士を比較して類似度をそれぞれ算出し、前記サブワード連鎖クラスタに対応させた類似度のテーブルを検索用INDEXとして予め作成する。
サブワード連鎖抽出手段。サブワード連鎖抽出手段は、前記インタフェースに入力された検索文字列を構成する音節又は音素から前記所望の数を繋げた複数の音節列又は音素列をサブワード連鎖として抽出する。
類似度演算手段。類似度演算手段は、前記サブワード連鎖抽出手段により抽出した各サブワード連鎖について、各サブワード連鎖が属するサブワード連鎖クラスタに対応する各類似度を前記検索用INDEXから求め、前記各類似度の合計を前記各検索対象文書に対する類似度として演算する。
出力インタフェース。出力インタフェースは、前記類似度に基づいた文書データの検索結果を出力するものである。
【００１６】
請求項２の類似文書検索装置は、請求項１において、前記類似度演算手段は、検索用INDEXから求めた前記各サブワード連鎖が属するサブワード連鎖クラスタに対応する類似度の合計が高い順で上位複数個の検索対象文書候補の絞り込みを行う第１パスINDEX検索と、
前記上位複数個の検索対象文書候補を音素列に変換し、検索文字列の音素列との間で音素を単位としたＤＰマッチングを行って得られる類似度により出力順位を決める第２パスＤＰマッチング検索とを含むことを特徴としている。
【００１７】
請求項３の類似文書検索装置は、請求項１において、前記INDEX作成手段における類似度は、各サブワード連鎖クラスタを代表する音節列または音素列と検索対象文書をそれぞれ音素列に変換し、二つの音素列において音素を単位とした端点フリーＤＰマッチングを行って得られた累積ＤＰマッチングコスト値に基づいて算出することを特徴としている。
【００１８】
請求項４の類似文書検索装置は、請求項３において、前記音素列間の端点フリーＤＰマッチングは、音素の置換コスト値、音素の挿入コスト値、音素の脱落コスト値を音声認識実験による音素混同行列に基づいて計算することを特徴としている。
【発明の効果】
【００１９】
本発明によれば、検索用INDEXの作成段階において、各サブワード連鎖クラスタと検索対象文書との類似度を事前に計算しておくため、類似検索文字列の検索時における第１パスINDEX検索での絞り込み処理には類似度の計算が不要となる。したがって、検索文字列と検索対象文書との音素間で行われる計算量の多いＤＰマッチングは、第２パスで少量の検索対象候補に限定して行われるため、全体の計算量を減少させることで高速検索を実現することができる。
【００２０】
また、検索用INDEXの作成時に、検索文字列の構成部分となる可能性があるサブワード連鎖が含まれる音節列クラスタと検索対象文書の類似度を考慮するため、第１パスINDEX検索において正解となる検索対象文書を候補から外してしまう確率を低下させることができる。この結果、全検索対象に対するＤＰマッチングによる検索と同程度の検索精度が実現できる。
【００２１】
また、検索用INDEX作成と検索文字列検索の際に、単語の代わりに、音節列または音素列（サブワード連鎖）を利用することによって、検索文字列と検索対象文書との間で対応する単語が存在しない（OUT-OF-VOCABULRY）という問題が生じることがなくなる。
さらに、クラスタリングによって検索用INDEXへのエントリ数が（音節列または音素列の数から音節列クラスタまたは音素列クラスタの数になったため）減るので、検索用INDEX作成のための音節列または音素列の種類が多い場合でも検索用INDEXサイズを削減することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の類似文書検索装置の実施形態の一例を示す機能ブロック図である。
【図２】本発明の類似文書検索装置における検索用INDEXファイル作成処理手順を示すフローチャートである。
【図３】検索用INDEX作成手段で得られた音節列クラスタと歌詞データの音節列との類似度を示したテーブル図である。
【図４】検索用音素列Ｓ１「ｔｏｇａｎａｉ」と、検索対象音素列Ｓ２「…ｋｏｔｏｗａｎａｎｉａ…」との端点フリーＤＰマッチングによるＤＰ距離の計算の手順を説明するための計算結果表である。
【図５】本発明の類似文書検索装置における検索処理の一例を示すフローチャートである。
【図６】図５のフローチャートの第１パスINDEX検索における処理の詳細を示す説明図である。
【発明を実施するための形態】
【００２３】
以下、本発明の類似文書検索装置の一実施形態について、図１のブロック図を参照しながら説明する。
類似文書検索装置の一例として、歌詞の一部のフレーズ等を検索文字列として入力し、歌詞データや楽曲情報を出力する歌詞検索装置を例に説明する。歌詞検索装置では、歌詞の構成要素となる「連続する一定数の音素または音節」であるサブワード連鎖を単位として検索文字列と登録されている歌詞データとの類似度を考慮する。音節列又は音素列（以下、「サブワード連鎖」という）は、音節又は音素（以下、「サブワード」という）から予め決められた所望数のサブワードを繋げた組み合わせで形成されるものである。
歌詞検索装置となる類似文書検索装置１は、楽曲の歌詞の一部のフレーズ等を検索文字列として入力する入力インタフェース２と、歌詞データ（文書データ）の検索結果を出力する出力インタフェース３と、検索対象となる複数の歌詞データ（検索対象文書）が格納された歌詞データベース４と、入力インタフェース２に入力された検索文字列から歌詞データベース４に格納されている歌詞データの検索処理を行う制御部１０を有して構成されている。入力インタフェース２に入力される検索文字列は、音声認識により変換された文字列であってもよい。
【００２４】
より具体的には、本発明の類似文書検索装置は、中央演算処理部（ＣＰＵ），ハードディスク等の記憶部，ドライバ等の読取部，キーボード等の入力部，ディスプレイ等の表示部等を備えた汎用のパーソナルコンピュータ（ＰＣ）や携帯情報機器に専用プログラムをインストールすることで構成される。したがってＰＣにおいて、入力インタフェース２は入力部に、出力インタフェース３は表示部に該当し、歌詞データベース４は記憶部内に構築され、音節列クラスタ作成手段１１、検索用INDEX作成手段１２、サブワード連鎖抽出手段１３、類似度演算手段１４における各種処理は中央演算処理部（ＣＰＵ）で実行される。また、入力インタフェース２を携帯端末とし、検索処理をＰＣで行うようにしてもよい。
【００２５】
制御部１０は、後述する音節N-Gram間の距離に基づいてクラスタリングしてサブワード連鎖クラスタ（音節列クラスタ）を登録する音節列クラスタ作成手段１１と、サブワード連鎖クラスタ（音節列クラスタ）と歌詞データベース４の各歌詞データ（検索対象文書）の音素列との類似度をテーブルとした検索用INDEXを予め作成する検索用INDEX作成手段１２と、検索文字列から複数のサブワード連鎖として抽出するサブワード連鎖抽出手段１３と、検索文字列に対する各歌詞データ（検索対象文書）の類似度を演算する類似度演算手段１４を備えている。
【００２６】
音節列クラスタ作成手段１１は、大量の文書における複数の音節から予め設定された個数（Ｎ個）の音節を組み合わせることでサブワード連鎖として複数の音節N-Gramを作成し、各音節N-Gram間の距離（類似度）に基づいてクラスタリングした複数の音節N-Gramが属するグループをサブワード連鎖クラスタ（音節列クラスタ）として登録する。
なお、音節の代わりに音素を使用してもよい。この場合、音節列クラスタ作成手段１１は、音素列クラスタ作成手段１１となり、予め設定された個数（Ｎ個）の音素を組み合わせることで複数の音素N-Gramを作成し、各音素N-Gram間の距離（類似度）に基づいてクラスタリングした複数の音素N-Gramが属するグループを音素列クラスタとして登録すればよい。
各音節N-Gram間（各音素N-Gram間）の距離（類似度）は、各音節N-Gramを構成するＮ個の音節を構成する音素同士（音素の数が異なる場合もある）の比較で行うＤＰマッチングで算出する。ＤＰマッチングについては後述する。
【００２７】
検索用INDEX作成手段１２は、登録された複数の音節列クラスタと歌詞データベース４の各歌詞データの音素列との類似度をテーブルとした検索用INDEXを予め作成する。各音節列クラスタは、それぞれ複数の音節N-Gramを代表する音節N-Gramである。検索用INDEXには、予め算出された各音節列クラスタに対する各歌詞データの類似度が記憶されている。検索用INDEXの作成手順については後述する。
【００２８】
サブワード連鎖抽出手段１３は、入力された検索文字列を、Ｎ個の音節毎に分けて複数のサブワード連鎖として抽出する。例えば、検索文字列が８個の音節で構成され、Ｎを３個とした場合、それぞれ先頭から１，２，３番目の音節、２，３，４番目の音節、３，４，５番目の音節、４，５，６番目の音節、５，６，７番目の音節、６，７，８番目の音節（音節3-Gram）がサブワード連鎖として抽出される。
前記音素列クラスタ作成手段１１に応じて、サブワード連鎖抽出手段１３では、音節の代わりに音素を使用し、検索文字列をＮ個の音節毎に分けて複数のサブワード連鎖（音素N-Gram）として抽出する。
【００２９】
類似度演算手段１４による検索文書は、検索用INDEXを参照して検索文字列に対する歌詞データ候補を絞り込む第１パスINDEX検索と、この歌詞データ候補と検索文字列との音素列同士のＤＰマッチングを行って最終的な歌詞データの検索を行う第２パスＤＰマッチング検索とにより行われる。
第１パスINDEX検索は、前記した検索用INDEXを参照して抽出した各サブワード連鎖（音節3-Gram）に対応するサブワード連鎖クラスタ（音節列クラスタ）の類似度の合計から各歌詞データの音素列との類似度を演算することで行われる。すなわち、各サブワード連鎖が属するクラスタに対応する各類似度を検索用INDEXから求め、各類似度の合計を各検索対象文書（各歌詞データの音素列）に対する類似度として演算する。
第２パスＤＰマッチング検索は、歌詞データ候補と検索文字列との音素列同士のＤＰマッチングにより類似度を演算して最終的な歌詞データの検索を行う。
【００３０】
出力インタフェース３は、類似度演算手段１４での演算結果に基づいて歌詞データ（検索対象文書）の検索結果を出力する。検索結果は、入力インタフェース２に入力される検索文字列との類似度の高い順で出力される。
【００３１】
次に、第１パスINDEX検索における検索文字列に対する歌詞データの検索時に使用する検索用INDEXの作成手順について、図２を参照しながら説明する。検索用INDEXは、音節列クラスタ作成手段１１及び検索用INDEX作成手段１２に対して予め入力される情報により作成される。
【００３２】
先ず、歌詞データや新聞コーパス等の大量の文書データをサブワード連鎖抽出手段１３に入力し、所望の数Ｎを指定して形態素解析を行って音節列に変換することで、文書データに含まれる音節Ｎ個から構成された全ての音節列を音節N-GramＡ（ｉ）として算出する。
例えば、図２に示すように、文書データに文字列「好きな事がない」が存在しサブワード連鎖抽出手段１３に入力された場合（ステップ２１）、音節変換処理を施すことで音節列「su-ki-na-ko-to-ga-na-i」を求め（ステップ２２）、所望の数Ｎを３とした場合、これを３音節で構成される複数の音節N-Gram（音節3-Gram）Ａ（ｍ）に変換する。音節N-GramＡ（1〜6）は、それぞれ「su-ki-na」「ki-na-ko」「na-ko-to」「ko-to-ga」「to-ga-na」「ga-na-i」に変換される（ステップ２３）。
【００３３】
次に、作成された全ての音節N-GramＡ（ｍ）について、音節N-Gram同士の距離行列を計算する（ステップ２４）。音節N-Gram同士間の距離の計算ついては、二つの音節N-Gramをそれぞれ音素列に変換し、二つの音素列間の音響距離を求めることになる。音素列間の音響距離の計算の仕方については、二つの音素列において、音素を単位とするＤＰマッチング（系列になっているデータ同士の類似度の計算）を行う。
【００３４】
ＤＰマッチングとは、既存の技術である動的計画法による文字列類似度計算であり、二つの音素列間の音響類似距離値を求めるに際し、音素間の差違や音素の挿入や脱落を考慮した計算手段により計算する。ＤＰマッチングの具体的な計算例については後述する。
【００３５】
図２のフローチャートに戻り、ＤＰマッチングにより各音節間の音響距離に基づいてクラスタリングした複数の音節N-Gramが属するグループを音節列クラスタＣ（ｎ）として登録する（ステップ２５）。
複数の音節N-GramＡ（ｍ）のクラスタリングは、次のような手順で行われる。
音節N-Gram同士の距離行列で構成される各音響距離値の計算（音節N-Gram同士間の距離の計算）については、上述したように、二つの音節N-Gramをそれぞれ音素列に変換し、二つの音素列間の音響距離を求める。
そして、各音節N-Gramを音響距離値空間上にプロットし、距離の近い音響距離値同士で空間をクラスタリングして、各クラスタの代表ベクトルとなる音節列クラスタＣ（ｎ）を算出する。音節列クラスタＣ（ｎ）は、複数（クラスタにより異なる一定でない数）の音節N-GramＡ（ｍ）を代表する。
【００３６】
クラスタリングの具体的な実現手段としては、公知技術であるk-meansを用いることができる。k-means によるクラスタリングは、以下の（１）〜（４）の手順により行われる。
（１）データを指定された任意の数であるk個のクラスタに分割する。例えば、音節列クラスタＣ（ｎ）の個数ｎを１０００個とする。
（２）各クラスタについて重心を計算する。
（３）全てのデータについて、重心との距離を最小にするクラスタを求め、各データを最小のクラスタに割り当てる。
（４）前回のクラスタから変化がなければ終了する。変化がある場合は、（２）に戻る。
【００３７】
上述した例では、文書データをサブワード連鎖抽出手段１３に入力して音節列に変換することで音節N-Gram（音節3-Gram）Ａ（ｍ）を作成したが、文書データを入力することなく得ることもできる。すなわち、音節列クラスタ作成手段１１において、５０音及び「しゃ」「じゃ」等の濁音や促音を含んだ複数の音素（最大で１２０〜１３０程度存在する）から所望（例えば３音）の数（Ｎ個）の音素を繋げた全ての音節N-Gram（音節3-Gram）Ａ（ｍ）を作成すればよい。この場合、例えば、"ア-イ-ウ"や"シャ-カ-イ"のような３音の音素の連結を単位として全ての音節N-GramＡ（ｍ）を作成する。音素として１００音を選択すれば、１００の３乗個の音節N-Gram（音節3-Gram）Ａ（ｍ）が存在することになる。
【００３８】
音節N-Gram同士間の距離に基づいたk-means法を用いてクラスタリングすることで、複数の音節N-Gramを代表する音節N-Gramが音節列クラスタＣ（ｎ）として自動的に分類され、この音節列クラスタＣ（ｎ）と歌詞データベース４に登録された検索対象文書である複数の歌詞データＬ（ｋ）の音素列との音響距離値である各類似度を算出し、図３に示すような検索用INDEXのテーブル３０を予め作成しておく。
【００３９】
音節列クラスタＣ（ｎ）と歌詞データＬ（ｋ）の音素列との音響距離値（類似度）は、ＤＰマッチングで算出する。この場合、音節列クラスタＣ（ｎ）の音素数に対して、歌詞データＬ（ｋ）の音素数が多くなるので、二つの音素列の長さが異なるため、端点フリーＤＰマッチングを利用する。端点フリーＤＰマッチングを使用することで、音節列クラスタＣ（ｎ）を構成する音素の連続と歌詞データの最も長い共通部分列を算出し、その共通部分の類似度を算出できる。
【００４０】
端点フリーＤＰマッチングによる具体的な計算方法について説明する。二つの音素列Ｓ１，Ｓ２が存在し、ＤＰマッチング計算における挿入、脱落、置換のコスト値をそれぞれＣins，Ｃdel,Ｃsubとした場合、ＤＰマッチング計算式の初期値は数１、計算値は数２、結果値は数３でそれぞれ表わされる。
【００４１】
【数１】
0005436307.tif 000002
【００４２】
【数２】
0005436307.tif 000003
【００４３】
【数３】
0005436307.tif 000004
【００４４】
検索用音素列Ｓ１が「ｔｏｇａｎａｉ」であり、検索対象音素列Ｓ２が「…ｋｏｔｏｗａｎａｎｉａ…」である場合を例に、ＤＰ距離の計算処理結果を図４に示す。この場合において、計算する際の単純化を図るため、Ｃins＝１，Ｃdel＝１,Ｃsub＝１とした。実際には、後述する音素混同行列によって各音素に対してＣins，Ｃdel,Ｃsubのコスト値が算出される。
【００４５】
先ず、数１の初期化計算式により検索対象音素列Ｓ２の各値の初期化を行う（STEP１）。次に、検索用音素列Ｓ１の「ｔ」に対する検索対象音素列Ｓ２の各要素の計算値を数２により計算する（STEP２）。数２では、４つの式のうちの最小値が選択される。
この計算を、検索用音素列Ｓ１の「ｏ」「ｇ」「ａ」「ｎ」「ａ」「ｉ」に対して順次行い（STEP３〜８）、全てのＤ（i.j）が算出される。
【００４６】
Ｄ（len(S1),j）の最小値を終点とし、終点からバックトレースすることで、Ｄ（i,j）を最小値（最短距離）となる最適経路を導き出す（STEP９）。
その結果、検索用音素列Ｓ１「ｔｏｇａｎａｉ」は、検索対象音素列Ｓ２「…ｋｏｔｏｗａｎａｎｉａ…」の「ｔｏｗａｎａ」と類似し、ＤＰ距離は「２」となる。
【００４７】
検索用INDEXのテーブル３０では、図３に示すように、算出された各音節列クラスタを縦に配置し、各歌詞データを横に配置し、予め計算されたクラスタ音節と歌詞データの音素列同士の類似度が対応箇所に記載された表で構成されている。
【００４８】
ＤＰマッチングの計算においては、音素の置換コスト値（異なる音素間の置換コスト値）、音素挿入コスト値、音素脱落コスト値をそれぞれ予め数値を与え、音素列間の類似度を表す累積ＤＰマッチングコストを求める。この累積ＤＰマッチングコストを音素列間の音響距離値とする。上述した音素の置換、挿入及び脱落コストの数値については、音声認識実験による音素混同行列（phonetic confusion matrix）に基づいて計算される。
【００４９】
音素混同行列とは、音声認識実験などにより求められるもので、行列の要素を確率で表したものである。音声認識実験は、音声データを学習データとして大量に集め、ＨＭＭ学習アリゴリズムによって学習データを利用して音声認識用の音素の音響モデルを作成する。
【００５０】
また、音素間混同行列を使用した各音素の挿入、脱落及び他の音素との置換コストの算出例について、表１を参照して説明する。この場合、テスト用音声データを音声認識器に入力し、認識結果となった音素列を出力し、テスト用音声データを書き起こした正解音素列と前記認識結果となった音素列を比較することで音素間混同行列が作成される。
表１は、ａ，ｂ…ｚの各音素についての置換、脱落、挿入の回数を示すもので、ｎ（ｐ,ｋ）は音声認識器によって音素ｐを音素ｋとして認識した回数、ｎ（φ,ｐ）は音声認識器によって音素ｐが音声認識結果に挿入された（正解音素列には存在しない）回数、ｎ（ｐ,φ）は音声認識器によって音素ｐが脱落した回数をそれぞれ示している。
【００５１】
【表１】
0005436307.tif 000005
【００５２】
ＤＰマッチング計算における挿入、脱落、置換のコスト値（Ｃins，Ｃdel,Ｃsub）は、Ｍを音素の集合とした場合、数４〜６により求められる。
【００５３】
【数４】
0005436307.tif 000006
【００５４】
【数５】
0005436307.tif 000007
【００５５】
【数６】
0005436307.tif 000008
【００５６】
次に、検索文字列を入力して類似する歌詞データを検索する場合について、図５のフローチャートを参照して説明する。
先ず、ユーザが歌詞の一部であるとして記憶しているフレーズ（聞き覚えのある単語の集合である文字列。例えば「好きな事がない」）を検索文字列として入力インタフェース２から入力する（ステップ４１）。前記したフレーズ「好きな事がない」は、実際の歌詞に含まれている音節と完全に一致していなくてもよい。
【００５７】
入力されたフレーズは、サブワード連鎖抽出手段１３により、フレーズを構成する文字から音節変換処理が行われる（ステップ４２）。具体的には、フレーズ「好きな事がない」を音節列である「su-ki-na-ko-to-ga-na-i」に変換する。
【００５８】
続いて、指定された数Ｎ（この例では「３」）の音節数から構成される複数の音節N-Gram（音節3-Gram）Ｑに変換する（ステップ４３）。
音節N-GramＱは、上記例の音節列「su-ki-na-ko-to-ga-na-i」に対して、Ｑ（１）「su-ki-na」，Ｑ（２）「ki-na-ko」，Ｑ（３）「na-ko-to」，Ｑ（４）「ko-to-ga」，Ｑ（５）「to-ga-na」，Ｑ（６）「ga-na-i」の６個に変換される。
【００５９】
次に、歌詞データＬ（ｋ）に対する近似音響距離Ｒ（ｋ）を検索用INDEXのテーブル３０を使用し、値が小さい上位複数個（Ｐ個）の歌詞データを候補として選択する第１パスINDEX検索が行われる（ステップ４４）。
この検索は、図６に示すように、検索文字列のフレーズに対応する各音節N-GramＱが含まれる音節列クラスタＣと、歌詞データの音節列との類似度の総和である近似音響距離Ｒ（ｋ）＝Ｄ（35,k）＋…＋Ｄ（n,k）＋…＋Ｄ（1000,k））をテーブルに記憶された値に基づいて計算することで求める。
【００６０】
具体的は、Ｑ（１）「su-ki-na」が含まれる音節列クラスタがＣ（35）であり、Ｑ（ｍ）「na-ko-to」が含まれる音節列クラスタがＣ（n）であり、Ｑ（６）「ga-na-i」が含まれる音節列クラスタがＣ（1000）である場合、これを加算した値が近似音響距離Ｒ（ｋ）となる。
そして、各歌詞データに対する近似音響距離Ｒの値の低い順で歌詞データをランキングし、その上位Ｐ個の歌詞データを検索対象候補として絞り込む。歌詞データの絞り込み個数であるＰは、可変にできるようになっている。
【００６１】
続いて、検索文字列の音素列と歌詞データの音素列との音響距離が最も小さい歌詞データを決めるため第２パスＤＰマッチング検索が行われる（ステップ４５）。この検索は、検索文字列の音素列と、第１パスINDEX検索によって検索対象候補となった歌詞データの音素列との音響距離値（類似度）Ｒ´をＤＰマッチングで算出する。この場合、検索文字列の音素の数と、歌詞データＬ（ｋ）の音素の数が異なるので、上述した検索用INDEXの作成時の音節列クラスタと歌詞データとの類似度の算出と同様に端点フリーＤＰマッチングを利用する。
例えば、入力した検索文字列が「好きな事がない」である場合に、歌詞データを構成する音素列との比較を行い、歌詞データに「好きな事が何」が含まれる場合、検索文字列の「好きな事がない」の音素列「sukinakotoganai」（１５音素）と、歌詞データ（１５音素以上）と端点フリーＤＰマッチングで比較し、歌詞データに含まれる最も類似する「好きな事は何」の音素列「sukinakotowanani」との音響距離値（類似度）Ｒ´が算出される。
【００６２】
算出された音響距離値（類似度）Ｒ´を低い順に歌詞データのランキングを行った後に、上位Ｘ（少なくともＸはＰより小さい値）位となる歌詞データ及びそれらの楽曲情報を検索結果として出力インタフェース３に出力する。
【００６３】
上述した類似文書検索装置によれば、検索用INDEX作成手段１２におけるテーブル３０の作成段階において、各音節列クラスタＣ（ｎ）と歌詞データ（検索対象文書）Ｌ（ｋ）との類似度を事前に計算しておくため、検索文字列の検索時における第１パスINDEX検索での歌詞データの絞り込み処理にはテーブル３０の類似度を加算するだけで類似度のＤＰマッチングによる計算が不要となる。したがって、検索文字列と検索対象文書との音素間同士で行われる計算量の多いＤＰマッチングは、少量の検索対象候補に限定して行う第２パスＤＰマッチング検索のみで行われるため、全体の計算量を減少させることで高速検索を実現することができる。
【００６４】
また、検索用INDEX作成手段１２におけるテーブル３０の作成時に、検索文字列のサブワード連鎖となる可能性がある音節N-Gramが含まれる音節列クラスタと歌詞データ（検索対象文書）の類似度を考慮するため、第１パスINDEX検索において正解となる歌詞データ（検索対象文書）を候補から外してしまう確率を低下させることができる。この結果、全検索対象に対するＤＰマッチングによる検索と同程度の検索精度が実現できる。
【００６５】
また、検索用INDEX作成手段１２におけるテーブル３０の作成時、及び、検索文字列を入力して類似文書検索を行い際に、単語の代わりに、サブワード連鎖である音節N-Gramを利用することによって、検索文字列と歌詞データ（検索対象文書）との間で対応する単語が存在しない（OUT-OF-VOCABULRY）という問題が生じることがなくなる。
さらに、検索用INDEX作成手段１２におけるテーブル３０の作成時に、クラスタリングによって検索用INDEXへのエントリ数が（音節N-Gramの数から音節列クラスタの数になったため）減るので、検索用INDEX作成のための音節N-Gramの種類が多い場合でも検索用INDEXサイズを削減することができる。
【００６６】
上述した類似文書検索装置では、類似度演算手段１４において類似度を考慮して検索文字列から歌詞データ（検索対象文書）を検索する場合、第１パスINDEX検索での歌詞データの絞り込み処理と、検索文字列と検索対象文書との音素間同士のＤＰマッチングによる第２パスＤＰマッチング検索処理を行っている。そして、第１パスINDEX検索での歌詞データの絞り込み個数Ｐは変数となっているので、検索精度を高める場合は個数Ｐを多くして第２パスＤＰマッチング検索処理を行い、検索処理時間を短縮する場合には個数Ｐを少なくして第２パスＤＰマッチング検索処理を行うように個数Ｐを設定すればよい。
検索処理時間の短縮化を最優先に考えた場合、第２パスＤＰマッチング検索処理を省略して第１パスINDEX検索のみで処理するようにしてもよい。この場合、必要とする歌詞データ（検索対象文書）の検索精度が低くなるが、検索文字列と検索対象文書との音素間同士のＤＰマッチングを完全に省略できるので高速度に検索結果を得ることができる。
【符号の説明】
【００６７】
１…類似文書検索装置、  ２…入力インタフェース、  ３…出力インタフェース、  ４…歌詞データベース、  １０…制御部、  １１…音節列クラスタ生成手段、  １２…検索用INDEX作成手段、  １３…サブワード連鎖抽出手段、  １４…類似度演算手段。
【図１】
0005436307.tif 000009
【図２】
0005436307.tif 000010
【図３】
0005436307.tif 000011
【図４】
0005436307.tif 000012
【図５】
0005436307.tif 000013
【図６】
0005436307.tif 000014