(57)【要約】【課題】誤りを含む系列信号から複数候補を効率よく処理できる系列信号検索装置および系列信号検索方法を提供する。【解決手段】音声データの音声認識結果の音節列と検索語の音節列から２次元配列を表し、前記２次元配列の要素として音節間の距離、すなわち類似度を用いることにより平面を構成し、前記平面上で直線を検出することにより、検索語による音声データの検索処理を実現する。距離を考慮した索引付けを用いることで高速な検出が可能となるとともに、音声認識の複数候補を考慮することで高精度な検出も可能になる。そして、距離を考慮した索引付けは、距離の近い、あるいは近似的に近い候補から探索を進めることができるため探索を打ち切る必要は無く、適切なしきい値が設定できる。さらに、しきい値で探索を打ち切らないので、ノイズが大きい場合でも、距離の近い、あるいは近似的に近い候補から順番に解を見つけることができるようになる。【選択図】図１
2011128903.tif 000002
【特許請求の範囲】
【請求項１】
検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出手段と、
前記信号特徴抽出手段により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出手段と、
前記類似距離算出手段により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成手段と、
前記系列信号情報、前記参照信号特徴、前記信号特徴の特徴量の類似度を示す距離、および、前記特徴ベクトルを記憶する記憶装置と、
検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出手段と、
前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成手段と、
前記信号特徴列生成手段により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定手段と、
前記検索結果を出力する出力手段と
を備えたことを特徴とする系列信号検索装置。
【請求項２】
前記判定手段は、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成手段により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定手段であることを特徴とする請求項１に記載の系列信号検索装置。
【請求項３】
前記系列信号情報が音声データであり、前記信号特徴および前記参考信号特徴が、音素、音節または音素もしくは音節のｎ−ｇｒａｍによって特徴付けられる信号特徴であることを特徴とする請求項１または２に記載の系列信号検索装置。
【請求項４】
記憶装置に蓄積された情報に接続される計算機を介して検索する方法において、前処理過程および実行時処理過程とで構成された系列信号検索方法であって、
前処理過程は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出過程と、
前記信号特徴抽出過程により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出過程と、
前記類似距離算出過程により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成過程とで構成され、
実行時処理過程は、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出過程と、
前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成過程と、
前記信号特徴列生成過程により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定過程と、
前記検索結果を出力する出力過程とで構成された
ことを特徴とする系列信号検索方法。
【請求項５】
前記判定過程は、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成過程により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定過程であることを特徴とする請求項４に記載の系列信号検索方法。
【請求項６】
前記信号特徴抽出過程は、音声データを音素、音節または音素もしくは音節のｎ−ｇｒａｍを単位として分割し、該単位ごとの信号特徴を抽出する信号特徴抽出過程であり、前記検索信号特徴抽出過程は、文字データを音素、音節または音素もしくは音節のｎ−ｇｒａｍを単位として分割し、該単位ごとの信号特徴を抽出する検索信号特徴抽出過程であることを特徴とする請求項４または５に記載の系列信号検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置および検索方法に関し、特に、音声データ中に使用された言葉の検索、またはＯＣＲ後の誤りを含むテキストデータからの検索などのように系列信号について検索するための検索装置および検索方法に関するものである。
【背景技術】
【０００２】
音声・画像・ビデオの記録・編集機器の拡大、およびインターネットをはじめとする情報通信網の発展により、誰でも気軽にコンテンツを作成・公開することが可能となり、マルチメディアコンテンツの情報爆発が進行しつつある。これらのコンテンツには、ファイル名やタイトル以外にはメタデータが付与されていないことが多く、従来のテキストベースの検索技術だけでは、目的のコンテンツにたどり着くことは困難である。一方、話し言葉を含むコンテンツの場合には、大語彙連続音声認識技術を利用することで、言語情報を利用した検索が可能である。このような音声言語情報を対象とした検索技術は「音声ドキュメント検索（Ｓｐｏｋｅｎ
Ｄｏｃｕｍｅｎｔ Ｒｅｔｒｉｅｖａｌ）」または、単に「音声検索」と呼ばれ、マルチメディアコンテンツの情報爆発時代に必要不可欠な技術である。
【０００３】
音声ドキュメント検索のうち、入力した検索語（クエリ、パターンなどと呼ぶ）が音声データ中で現れる位置を特定する問題は、音声中の検索語検出（Ｓｐｏｋｅｎ
Ｔｅｒｍ Ｄｅｔｅｃｔｉｏｎ；ＳＴＤ）、音声中の既知語検索（Ｋｎｏｗｎ Ｉｔｅｍ Ｒｅｔｒｉｅｖａｌ）、音声キーワード検索、あるいは単に音声検索、などと呼ばれ、音声情報処理の分野では活発に研究が行われている問題である。１９９７年には、米国ＮＩＳＴ主催の評価型ワークショップＴＲＥＣの音声ドキュメント検索トラック（ＳＤＲ
Ｔｒａｃｋ）において、Ｋｎｏｗｎ Ｉｔｅｍ Ｒｅｔｒｉｅｖａｌの評価が行われた［非特許文献１］。また、２００６年にＮＩＳＴは再びＳｐｏｋｅｎ
Ｔｅｒｍ Ｄｅｔｅｃｔｉｏｎを研究課題として設定し、それ以降未知語の検出を重視したＳＴＤの研究が盛んに行われるようになった［非特許文献２］。音声情報処理の代表的な国際会議であるＩＣＡＳＳＰ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃ，  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ）でも２００９年に音声ドキュメント検索のスペシャルセッションが組まれている。また、日本においても情報処理学会音声言語情報処理研究会のワーキンググループにおいて、ＳＴＤの評価用テストコレクションの整備が進行中である［非特許文献３］。
【０００４】
ＳＴＤに対する従来手法は、音声認識の認識誤りを、比較的研究が進んでいるテキストを対象とした検索手法の枠組みの中で扱う方法がほとんどである。前述ＴＲＥＣのＳＤＲ
Ｔｒａｃｋでは、音声認識結果の一位の候補に加えて二位以下の複数候補を利用することで性能改善できることが示されている。その後の手法は、認識結果の複数候補を効率よく表現する方法、たとえば代表的な方法として、Ｃｏｎｆｕｓｉｏｎ
Ｎｅｔｗｏｒｋ［非特許文献４］やＴＡＬＥ（Ｔｉｍｅ−Ａｎｃｈｏｒｅｄ Ｌａｔｔｉｃｅ
Ｅｘｐａｎｓｉｏｎ）［非特許文献５］、に焦点が当てられ、検索については誤りの無いテキスト検索方法と同様の手法で索引付けする方法を用いるものがほとんどであった。これらの手法は、完全一致の索引を用いるため索引付けに漏れがあると全く検出できなくなるという問題点がある。特に、音声認識の認識語彙外語（未知語ともいう）の扱いが問題である。これに対し、音素や音節認識の結果を併用する手法も提案されているが、認識率の低下が問題となっている。また、誤認識の対処のため利用する認識候補数を大きく取ると、索引の数が大きくなり検索効率が悪化するという問題点もある。
【０００５】
一方、手島らは、サフィックスアレイを用いた索引付け手法をＳＴＤに適用した検索法を提案している〔非特許文献６］。ＳＴＤに近似文字列照合を適用した方法と位置づけられるが、サフィックスアレイ（あるいは、サフィックスツリー）で認識の複数候補を扱うことは難しく、検索精度に問題がある。また、従来のいずれの方法もテキストベースの索引付け法をそのまま適用しているため、索引自体は一致／不一致の２値情報しか含んでいない。そのため、検索時や検索後にＤＰ（Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ）マッチングなどを用いて距離の計算を要するという問題点がある。
【０００６】
一方、テキストデータを対象としてパターンと類似した部分を見つける問題は、「近似文字列照合（Ａｐｐｒｏｘｉｍａｔｅ
Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ）」と呼ばれる。近似文字列照合は、テキストがその場で与えられることを仮定してテキストを前処理することなしに照合を行うオンライン手法と、あらかじめテキストが与えられていることを仮定してテキストを前処理して索引付け（Ｉｎｄｅｘｉｎｇ）を行うオフライン手法の２つに分類される。
【０００７】
また、オフライン近似文字列照合の索引付け手法としては、以下の３種類に分類される［非特許文献７］。
【０００８】
（１）サフィックスツリー（Ｓｕｆｆｉｘ Ｔｒｅｅ）またはサフィックスアレイ（Ｓｕｆｆｉｘ  Ａｒｒａｙ）に基づく手法
（２）ｎ−ｇｒａｍ索引を用いる手法
（３）距離空間上の索引を用いる手法［非特許文献８］
【０００９】
これらの手法をＳＴＤに用いる場合、上記（１）は音声認識の複数候補を扱えない、上記（２）は検出位置には検索語と一定割合以上の完全一致箇所が含まれている必要がある、といった問題点がある。また、上記従来法（１）（２）のいずれの手法も「ある一定のエラーの範囲内の全候補を探す」という問題設定に対する手法となっており、「最も距離の近い上位Ｎ個の候補を求める」といった問題に適応するには、しきい値を決め直して再検索するなど、追加コストがかかることも問題である。一方、上記（３）の距離空間上の索引を用いる手法は、これまでＳＴＤに適用されていない。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】John S.Garofolo and Cedric G. P. Auzanne and Ellen M. Voorhees, “The TREC SpokenDocument Retrieval Track: A Success Story”, In Proceedings of TREC-9, page107-129, 1999.
【非特許文献２】NIST, “TheSpoken Term Detection Evaluation”:http://www.itl.nist.gov/iad/mig/tests/std/2006/index.html
【非特許文献３】伊藤慶明, 西崎博光, 胡新輝, 南条浩輝, 秋葉友良, 相川清明, 河原達也, 中川聖一, 松井知子, 山下洋一,“音声中の検索語検出のためのテストコレクション構築−中間報告−”, 情報処理学会研究報告,Vol.2009-SLP-78 No.4, 2009.
【非特許文献４】L.Mangu, E.Brill andA.Stolcke: “Finding Consensus in Speech Recognition: Word Error Minimizationand Other Applications of Confusion Network” Computer Speech andLanguage,Vol.14, No.4, pp.373-400, 2000.
【非特許文献５】P. Yu, Y. Shi and F. Seide,“Approximate Word-Lattice Indexing with Text Indexers: Time-Anchored LatticeExpansion”, In Proceedings of International Conference on Acoustic, Speech andSignal Processing (ICASSP), pp.5248-5251, 2008.
【非特許文献６】手島 茂樹，桂田 浩一，新田 恒雄： “Suffix Array を用いた高速なキーワード音声検索システム”， 日本音響学会2009年秋季研究発表会講演論文集，1-R-26 (2009-9)．
【非特許文献７】G. Navarro, et al., “Indexingmethods for approximate string matching”, IEEE Data Eng. Bull., 24(4):12-27,2001.
【非特許文献８】G. Navarro, et al., “A Metric Indexfor Approximate String Matching”, Theoretical Computer Science (TCS) 352(1-3):266-279, 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
従来法は、曖昧性の無いテキストを対象とした索引付け手法をベースにしているため、音声認識結果のような、（１）複数の候補を扱う方法、（２）連続的な距離を扱う方法、に問題があり、そのため精度あるいは効率のいずれかを犠牲にすることに問題があった。前記（１）については、一致／不一致の二値の索引付けを適用するため、複数候補を全く扱えないか、複数候補を扱うと候補数が多くなり効率が悪化してしまう。また前記（２）について、音声などの曖昧な情報を扱う場合は、連続的な距離（尤度、信頼度、確率、など）の扱いが必要である。
【００１２】
従来法は離散的な距離（ｎ文字異なる、など）を扱うことを目指しており、索引自体には距離情報を利用していなかった。そのため、検索時や検索後にＤＰマッチングなどを用いて距離の計算を要するという問題点がある。また、従来法は探索にしきい値を必要とし、適切なしきい値の設定が難しいという問題がある。
【００１３】
そこで、本発明は、複数候補を効率よく行うとともに、検索処理を簡素化することのできる検索装置および検索方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明者らは、鋭意検討の結果本発明に至った。
【００１５】
すなわち、系列信号検索装置にかかる本発明は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出手段と、前記信号特徴抽出手段により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出手段と、前記類似距離算出手段により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成手段と、前記系列信号情報、前記参照信号特徴、前記信号特徴の特徴量の類似度を示す距離、および、前記特徴ベクトルを記憶する記憶装置と、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出手段と、前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成手段と、前記信号特徴列生成手段により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定手段と、前記検索結果を出力する出力手段とを備えたことを特徴とする系列信号検索装置を要旨とすることができる。
【００１６】
上記発明の判定手段については、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成手段により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定手段とすることができる。
【００１７】
また、上記発明において、前記系列信号情報を音声データとし、前記信号特徴および前記参考信号特徴が、音素、音節または音素もしくは音節のｎ−ｇｒａｍによって特徴付けられる信号特徴とすることができる。
【００１８】
他方、系列信号検索方法にかかる本発明は、記憶装置に蓄積された情報に接続される計算機を介して検索する方法において、前処理過程および実行時処理過程とで構成された系列信号検索方法であって、前処理過程は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出過程と、前記信号特徴抽出過程により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出過程と、前記類似距離算出過程により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成過程とで構成され、実行時処理過程は、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出過程と、前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成過程と、前記信号特徴列生成過程により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定過程と、前記検索結果を出力する出力過程とで構成されたことを特徴とする系列信号検索方法を要旨としている。
【００１９】
上記発明の判定過程としては、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成過程により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定過程とすることができる。
【００２０】
また、上記発明において、前記信号特徴抽出過程は、音声データを音素、音節または音素もしくは音節のｎ−ｇｒａｍを単位として分割し、該単位ごとの信号特徴を抽出する信号特徴抽出過程であり、前記検索信号特徴抽出過程は、文字データを音素、音節または音素もしくは音節のｎ−ｇｒａｍを単位として分割し、該単位ごとの信号特徴を抽出する検索信号特徴抽出過程である構成とすることができる。
【００２１】
なお、上記構成の検索方法は従来技術のうち、距離空間上の索引を用いる手法に分類されると考えられるが、従来技術における手法が文字列全体の距離空間上で直接索引付けするのに対し、本発明は距離空間を線形に再構成可能な部分距離空間に分割し、各部分空間で距離空間索引付けを行うものである。
【００２２】
また、本発明の検索方法は、大規模な音声データ中から、入力した検索語と類似した箇所を、類似度の高い順に高速に検索する、ＳＴＤ手法の一つである。音声データからのキーワード検索のほかに、検索語を分割した単位、たとえば音声検索の場合は音素、音節、音節や音素のｎ−ｇｒａｍなど、と検索対象データの各位置の間に距離、特に連続値による距離または類似度が定義されている系列からの類似箇所検索一般に適用可能である。たとえば、近似文字列照合、ＯＣＲ後の誤りを含むテキストからの検索などに適用可能である。特に、検索対象データについて、各位置に複数の候補がある場合にも適用可能であることから、誤りを含む系列からの類似列検索に適している。
【発明の効果】
【００２３】
本発明によれば、距離を考慮した索引付けを用いることで高速な検出が可能となるとともに、音声認識の複数候補を考慮することで高精度な検出も可能になる。
【００２４】
そして、距離を考慮した索引付けは、距離の近い、あるいは近似的に近い候補から探索を進めるという良い性質を持っている。また、従来技術は、索引は距離を考慮していないので可能性のある候補を等価に扱う必要があり、そのため探索を打ち切るしきい値を必要とし、適切なしきい値の設定が難しいという問題があったが、本発明の検索方法によれば、しきい値を設定する必要は無く、この問題を回避できる。
【００２５】
このように、本発明の検索装置は、その性質により、新たなＳＴＤシステムの運用方法が可能になる。また、本発明の検索方法によれば、しきい値で探索を打ち切ることを行わないので、どんなにノイズが大きい場合でも、距離の近い、あるいは近似的に近い候補から順番に解を見つけることができる、という良い性質を持つ。この性質により、これまでにないシステムの運用が可能である。例えば、最初のＮ個の解が見つかるまで検出を行うといった運用や、検出に時間がかかる場合は、距離の類似した対立候補が多くそもそも検索語が存在しないなど良い結果が得られないことが示唆されるので、一定時間だけで検索を打ち切るなど、システム構築の際にこの性質を活かした運用を行うことが可能である。
【図面の簡単な説明】
【００２６】
【図１】ｘｙ平面上の直線検出による検索語の検出の模式図である。
【図２】音節距離配列の模式図である。
【図３】距離順にソートされた位置ｉのベクトル（スタック）を示す模式図である。
【図４】前処理（索引付け）アルゴリズムのフローチャートである。
【図５】検索アルゴリズムのフローチャートである。
【図６】検索アルゴリズムのフローチャートである。
【図７】近傍生成の例を示す模式図である。
【図８】Ｃｏｎｆｕｓｉｏｎ  Ｎｅｔｗｏｒｋを考慮した音節間距離の模式図である。
【図９】挿入、削除、誤りを考慮した音節間距離を表す模式図である。
【図１０】本発明の実施形態における前処理のための索引データ作成装置の模式図である。
【図１１】本発明の実施形態における検索処理装置の模式図である。
【図１２】本発明の実施形態における連続ＤＰのＳＴＤ実験結果を示すグラフである。
【図１３】本発明の実施形態におけるＳＴＤ実験結果を示すグラフである。
【発明を実施するための形態】
【００２７】
以下、本発明の実施の形態を説明する。本発明の基本的な原理は、ＳＴＤ問題の性質を利用して効率よい索引付け（前処理）手段と直線検出手段を利用した検索方法（実行時処理）に特長がある。
【００２８】
系列信号情報としては、音声データ、テキストデータ、音楽データおよび画像データなどが挙げられるが、本実施形態では音声データを例示して説明する。また、音声データについて分割する単位には、音素、音節または音素もしくは音節のｎ−ｇｒａｍなどを挙げることができるが、説明の容易さから音節を単位として音声データを分割し、それぞれの音節について、個々の音節を信号特徴として認識する場合について説明する。なお、各音節における信号特徴およびその類似度は、発音された音声波形と参照音節波形との間の物理的な差異を尺度とするほか、発声方法の相違点に着目した解析方法によって特徴付けられる基準により尺度を決定する場合もあり得る。より具体的には、音節をＨｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌ（ＨＭＭ）でモデル化して、そのモデル間の距離を尺度とすることができる。そのため、以下の説明中に示した「音節」には、上述のように特徴付けられた「音節ごとの信号特徴」を含む場合があるものとし、また、参照信号特徴とは、正確な発音をした場合の音節ごとの信号特徴を意味する。
【００２９】
音声データの音声認識結果の音節列をｘ軸、検索語の音節列をｙ軸にとった平面を考える（図１）。ＳＴＤは、この平面から直線を検出する問題ととらえることができる。ｘｙ平面は、要素として音節間の距離（類似度）が代入された音声データ長ｎ×検索語長ｍの２次元配列Ｄ［ｉ］［ｊ］
（０≦ｉ＜ｎ，０≦ｊ＜ｍ）で表現することができる。
【００３０】
このとき、例えば（最も一般的なマッチングのケースである） 傾き１の直線 ｙ＝ｘ＋ｃ の検出には、数１を各ｉ（０≦ｉ＜ｎ）で計算し、Ｔ［ｉ］の小さい箇所を類似箇所として検出する、と言った問題に定式化できる。
【００３１】
【数１】
2011128903.tif 000003
【００３２】
これ以降、ｊ（０≦ｊ＜ｍ−１）に関する＜式＞の総和を Σ＿ｊ ＜式＞ と表す。
【００３３】
画像の直線検出の場合は、２次元配列Ｄ［ｉ］［ｊ］がその場で得られるので、すべてオンラインで計算する必要がある。
【００３４】
一方、ＳＴＤの場合は、音声データは検索前に既知であると仮定できるので、検索語のある分割単位（音素、音節、音節や音素のｎ−ｇｒａｍ、など。以下、音節と呼ぶ。）ａごとに音声データの各位置での距離の配列Ｄ（ａ）［ｉ］  （０≦ｉ＜ｎ）をオフラインで計算しておくことができる（図２）。検索時には検索語の音節系列ａ［０］，ａ［１］，・・，ａ［ｍ−１］によって距離の配列Ｄ（ａ［０］）［ｉ］，Ｄ（ａ［１］）［ｉ］，・・，Ｄ（ａ［ｍ−１］）［ｉ］をｙ軸方向に順番に並べるだけで２次元配列Ｄ［ｉ］［ｊ］を構成できる（すなわち、Ｄ［ｉ］［ｊ］＝Ｄ（ａ［ｊ］）［ｉ］となる）。
【００３５】
さらに、距離の配列Ｄ（ａ）［ｉ］は、オフラインで距離の昇順にソートしておくことができる。つまり、類似距離の最小値から信号特徴を順次配列させるのである。音節ａについて音声データ中の各位置ｉをＤ（ａ）［ｉ］に従って距離の昇順にソートしたスタックをＳ（ａ）、そのスタックトップをＳ（ａ）．ｔｏｐとする（図３）。
【００３６】
以上で述べた、Ｄ（ａ）［ｉ］およびＳ（ａ）を計算するアルゴリズムのフローチャートを（図４）に示す。以下、（図４）に従って手順を説明する。
【００３７】
まず、音声データを音声認識する等の手段で、音節Ｃｏｎｆｕｓｉｏｎ  Ｎｅｔｗｏｒｋ  ＣＮ［ｉ］を用意する（ステップＡ１）。音節集合Ａを初期化し、全音節を代入する（ステップＡ２）。Ａから音節ａを一つ取り出し、位置ｉを０に初期化する（ステップＡ３）。ａとＣＮ［ｉ］の距離を計算し、それを距離の配列Ｄ（ａ）［ｉ］に代入し、ｉをインクリメントする（ステップＡ４）。位置ｉが文書長ｎに達したら次のステップＡ６に、そうでなければステップＡ４に戻る（ステップＡ５）。求めたＤ（ａ）［ｉ］に従って、文書位置を昇順にソートし、ソートされた位置ベクトルＳ（ａ）を得る（ステップＡ６）。音節集合Ａにまだ音節が残っていたらステップＡ３に戻る（ステップＡ７）。求めた位置ベクトルＳ（ａ）と距離ベクトルＤ（ａ）［ｉ］（両ベクトルを合わせて特徴ベクトルという）を出力する（ステップＡ８）。
【００３８】
前処理で計算しておいたＳ（ａ）を検索の索引として用いると、見込みのある位置から順に検出をする効率的な検出方法が構成可能である。より具体的には、以下の手順に従い、高速な検索語検出が可能である。
【００３９】
検索処理のフローチャートを（図５）に示す。以下、（図５）に従って手順を説明する。
【００４０】
まず、検索語を入力し、その音節列ａ［０］，ａ［１］，・・，ａ［ｍ−１］に従って、予め前処理で計算されているスタックの列Ｓ（ａ［０］），Ｓ（ａ［１］），・・，Ｓ（ａ［ｊ］），・・，Ｓ（ａ［ｍ−１］）を用意する。また、Ｒ＝｛｝，ｃｏｕｎｔ［ｉ］＝０
（０≦ｉ＜ｎ）に初期化する（ステップＢ１）。各スタック列のスタックトップの要素からなる集合Ｕ＝｛Ｓ（ａ［０］）．ｔｏｐ，Ｓ（ａ［１］）．ｔｏｐ，・・，Ｓ（ａ［ｊ］）．ｔｏｐ，Ｓ（ａ［ｍ−１］）．ｔｏｐ｝から、ある基準でｊを選び、Ｓ（ａ［ｊ］）．ｔｏｐをスタックＳ（ａ［ｊ］）から取り出し（ポップし）、位置ｉ＝Ｓ（ａ［ｊ］）．ｔｏｐ−ｊについて、投票した回数を数えるカウンタｃｏｕｎｔ［ｉ］に１を加える（投票する）（ステップＢ２）。ある値ｋについて、ｃｏｕｎｔ［ｉ］≧ｋ
がまだ成り立っていないなら、ステップＢ２に戻る（ステップＢ３）。位置ｉを検索結果候補集合Ｒに加える（ステップＢ４）。
Ｒ中の各候補ｉについて、ある基準を満たしたものを、検索結果として出力する。出力した候補はＲから取り除く（ステップＢ５）。終了条件が満たされていない場合はステップＢ２に戻る（ステップＢ６）。
【００４１】
以上の手順において、基本的には各候補について距離の計算は全く行う必要はないことに注意されたい。また、以降で述べるように、ステップＢ５で用いる基準によっては各候補の距離
【００４２】
【数２】
2011128903.tif 000004
【００４３】
を計算する必要があるが、あらかじめ求められている各音節の距離Ｄ（ａ［ｊ］）［ｉ＋ｊ］を足し込んでいくだけで、高価な計算なしに求めることができる。
【００４４】
ステップＢ２のｊを選ぶ基準には、Ｕ中で最小の距離を持つ要素（ａｒｇｍｉｎ＿ｊ Ｄ（ａ［ｊ］）［Ｓ（ａ［ｊ］）．ｔｏｐ］）などが考えられる。ステップＢ６の終了条件には、「最初の検索結果が得られるまで」「最初のＮ個の検索結果が得られるまで」「検索結果の距離があるしきい値を越えるまで」「ある一定時間が経過するまで」などが考えられる。また、ステップＢ５は各繰り返しで必ず実行する必要は無く、例えば、ステップＢ４を一定回数実行したら１回実行する、といった実装も考えられる。
【００４５】
ステップＢ３のｋとステップＢ５の基準の選択は、精度と効率に関係する。ステップＢ３のｋを小さくすると効率は良くなるが、精度は落ちる。そのためステップＢ５である基準により結果の評価を行い、安全なものを出力する。
【００４６】
最も単純な実装方法は、ｋ＝ｍ（検索語長）として、ステップＢ５には何も基準を課さず、すぐに検索結果を出力することが考えられる。また、効率を改善するには、ステップＢ５の基準を課さないまま、ｋを小さく取れば良い。例えば、ある実数α（０＜α＜１）についてｋ＝αｍとすると、検索語長に対して割合αだけ投票されたときに出力することとなる。
【００４７】
これらの、ステップＢ５で基準を課さない単純な実装のフローチャートを（図６）に示す。
【００４８】
図６において、ステップＢ１、ステップＢ２、ステップＢ３、ステップＢ６は、図５の対応するステップと同じである。図６のステップＢ４５では、位置ｉを検索結果としてそのまま出力する。
【００４９】
図５において、特にｋ＝１とした場合、ステップＢ５に次の基準１を用いると、以降の繰り返しで出力する候補よりも悪い（距離の大きい）候補は出力しないことを保証する最適解アルゴリズムが得られる。
【００５０】
（基準１） Σ＿ｊ Ｄ（ａ［ｊ］）［ｉ＋ｊ］≦Σ＿ｊ Ｓ（ａ［ｊ］）．ｔｏｐが成り立つ。
【００５１】
さらに、ステップＢ５で距離の小さい候補から順番に出力すれば、距離の昇順に解を出力するアルゴリズムとなる。また、集合Ｒは２分探索木やＢ木など順序を保持するデータ構造を用いれば、効率よく実装できる。
【００５２】
基準１の妥当性は、以下の補題から明らかである。
【００５３】
（補題１）まだ一度も投票が行われていない位置ｉの、数２で定義される最終的な距離Ｔ［ｉ］は、スタックトップの距離の総和Σ＿ｊ  Ｓ（ａ［ｊ］）．ｔｏｐ
【００５４】
【数３】
2011128903.tif 000005
以上である。
【００５５】
（証明）スタックは昇順にソートされているので、まだ投票の無い位置ｉについては任意の音節位置ｊについて、
【００５６】
【数４】
2011128903.tif 000006
が成り立つ。よって、
【００５７】
【数５】
2011128903.tif 000007
が成り立つ。（証明終）
【００５８】
（補題２）Σ＿ｊ Ｓ（ａ［ｊ］）．ｔｏｐより距離の小さい候補位置ｉは、少なくとも１回ある音節位置ｊで投票が行われている。
【００５９】
（証明）補題１の対偶により明らか。
【００６０】
以上により、候補集合Ｒ以外にΣ＿ｊ
Ｓ（ａ［ｊ］）．ｔｏｐより距離の小さい候補は存在しないことが分かり、最適解が得られることが保証される。
【００６１】
以上が基本的なアルゴリズムであるが、種々のバリエーションが考えられる。ここまでの説明では、最も単純な傾き１の直線ｙ＝ｘ＋ｃの場合を想定したが、これは距離尺度としては、文字列間のハミング距離に相当する。近似文字列照合の分野で使われる手法である近傍生成を適用することにより、直線の近傍となる直線や折れ線についても投票先Ｔ［ｉ］を用意し同様な計算が可能であり、より一般的な文字列間の距離尺度である編集距離やその他の距離に適用できる（図７）。
【００６２】
また、距離配列Ｄ（ａ）［ｉ］には、音節ａと音声データ中の位置ｉから求まる任意の距離を用いることが可能である。複数音声認識結果のコンパクトな表現方法であるＣｏｎｆｕｓｉｏｎ
ＮｅｔｗｏｒｋやＴＡＬＥ（Ｔｉｍｅ−Ａｎｃｈｏｒｅｄ Ｌａｔｔｉｃｅ Ｅｘｐａｎｓｉｏｎ）などを用いた複数候補を考慮した距離（図８）、認識のもっともらしさを表現した距離、挿入誤りや削除誤りを考慮して直線からの逸脱を許容するために隣接する音節との距離も考慮した距離（図９）、などより複雑な距離を使用することができる。
【実施例】
【００６３】
〔前処理〕次の手順で索引データ（前記実施の形態に示したスタックＳ（ａ））を作成する。（図１０）
【００６４】
１．ハードディスク、ＣＤ−ＲＯＭなどの記憶装置１０２に記録された音声データ２０１を用意する。音声データ１０２を、計算機１０１上にインストールした音声認識デコーダを用いて認識し、その認識結果である複数認識候補を表現した音節Ｃｏｎｆｕｓｉｏｎ
Ｎｅｔｗｏｒｋ２０２を記憶装置１０２上に作成する。音節Ｃｏｎｆｕｓｉｏｎ Ｎｅｔｗｏｒｋ２０２の代わりに、よりシンプルな認識結果の音節列をそのまま用いても良い。また、音節の代わりに、音素や、音節・音素のｎ−ｇｒａｍなど、検索語を分割して得られる任意の単位を用いても良い（以下では、これらをまとめて音節と呼ぶ。）
【００６５】
２．音節ａについて、音節Ｃｏｎｆｕｓｉｏｎ Ｎｅｔｗｏｒｋ２０２の各位値ｉの複数音節候補それぞれとの距離を計算機１０１で計算し、音節間距離の最小値を求める。すべての位置について距離計算した結果を、音節距離配列２０３として記憶装置１０２上に作成する。以上の操作をすべての音節で繰り返し、音節毎の音節距離配列２０３を作成する。
【００６６】
３．各音節ａについて、音節距離配列２０３に従って位置ｉを計算機を用いて昇順にソートし、その出力である音節位置のベクトル２０４を記憶装置上に作成する。
【００６７】
〔検索処理〕前処理で作成した音節位置ベクトル（スタック）を用いて検索処理を行う。（図１１）
【００６８】
１．音声データ４０１と〔前処理〕で作成した音節毎の音節位置ベクトル４０３を、ハードディスクなどの記憶装置３０２に用意する。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、音節毎の音節距離配列４０２も記憶装置３０２に用意する。音声認識結果のテキストを検索結果とする場合には、音声データ４０１の代わりに音声認識結果のテキストを記憶装置上に用意しても良い。
【００６９】
２．システムユーザの与える検索語（音節列）をキーボードなどの入力装置３０３を使って計算機３０１へ入力する。入力された音節列に含まれる各音節すべてについて、対応する音節位置ベクトル４０３を記憶装置３０２から計算機３０１に読み込んで、計算機メモリ上にスタックを構成する。スタックは、検索語を構成する各音節ごとに１つ、検索語の音節数だけ用意する。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、対応する音節距離配列４０２も計算機３０１のメモリ上に読み込む。
【００７０】
このとき、入力装置３０３には、キーボードの他、音声認識や手書き文字認識など、音節列を入力可能な任意の入力装置が利用できる。また、音節距離配列４０２はメモリに読み込む代わりに、記憶装置３０２にそのまま配置し、必要なときにランダムアクセスで参照することも可能である。音節位置ベクトル４０３も、記憶装置から一度にメモリ上に読み込む必要はなく、ベクトルを先頭からある長さまでのブロックに分割し、必要に応じて１ブロックずつ読み込むことも可能である。また音節ベクトルのうち距離の大きなものが記録されている接尾部分は、使用される可能性が低いので、記憶装置３０２の記憶容量の節約のため、削除してしまうことも可能である。
【００７１】
３．計算機３０１のメモリ上の音節毎に用意されたスタックを参照・操作しながら、前記実施の形態で示した方法により検索語出現位置を求める。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、計算機メモリ上（または、記憶装置上）の音節距離配列４０２も参照して処理を行う。
【００７２】
４．検出された検索語出現位置にしたがって、記憶装置３０２上の音声データ４０１から検索語出現位置付近の音声を取り出し、検索結果とする。音声認識結果のテキストを用いる場合は、検索語出現位置のテキストを検索結果とする。検索結果として出力する範囲は、検索語そのものや、検索語を含むより広い範囲の文や文書など、用途に応じて任意に選択することができる。検索結果は、音声再生装置やディスプレイ装置などの出力装置３０４を用いてユーザにそのまま提示してもよいし、機械翻訳、音声合成器、Ｗｅｂサーバ、などの各種サービスを提供する任意の装置への入力として利用することもできる。
【００７３】
以上の〔前処理〕〔検索処理〕で説明した装置を構成する要素である、記憶装置３０２、入力装置３０３、出力装置３０４、および計算機３０１は、直接接続することもできるし、ネットワーク上に分散して配置し、通信により相互接続して装置を構成することもできる。
【００７４】
また、記憶装置３０２上のデータである、音声データ４０１、音節距離配列４０２、音節位置ベクトル４０３は、それぞれ別の記憶装置に配置することも出来る。例えば、記憶装置３０２上のデータのうち音声データ４０１をネットワーク越しのサーバ上の記憶装置に配置し、音節位置ベクトルだけ計算機３０１に直結した記憶装置に配置することもできる。
【００７５】
また、入出力装置３０３をＷｅｂ上のクライアントで、その他をＷｅｂサーバ上に構築することもできる。
【００７６】
実施例に示した装置の実装と評価実験を、以下の手順で行った。
【００７７】
日本語の学会講演と模擬講演を記録したコーパスである「日本語話し言葉コーパス（ＣＳＪ）」中の１７７講演（約４４時間）の音声データを対象としたＳＴＤシステムを構築した。前記ＣＳＪを検索対象とした音声ドキュメント検索用テストコレクションに含まれる前記ＣＳＪの１ｂｅｓｔの音声認識結果を音素列に展開し、音素を分割単位として索引付けを行った。
【００７８】
音素ａと検索対象位置ｉの間の距離尺度としては、音素弁別特徴間のハミング距離［非特許文献６］を用いた。
【００７９】
検索語として、前記ＣＳＪを対象とした検索語検出のためのテストコレクション［非特許文献３］の検索語を用いた。
【００８０】
上記実施例と同条件の距離しきい値による連続ＤＰマッチングと比較を行った。実験結果を（図１２）と（図１３）に示す。この結果から、検索性能を落とすこと無く、検索効率が大幅に改善されていることがわかる。
【符号の説明】
【００８１】
１０１…計算機
１０２…記憶装置
２０１…音声データ
２０２…Ｃｏｎｆｕｓｉｏｎ  Ｎｅｔｗｏｒｋ
２０３…音節距離配列
２０４…音節位置ベクトル
３０１…計算機
３０２…記憶装置
３０３…入力装置
３０４…出力装置
４０１…音声データ
４０２…音節距離配列
４０３…音節位置ベクトル
【図１】
2011128903.tif 000008
【図２】
2011128903.tif 000009
【図３】
2011128903.tif 000010
【図４】
2011128903.tif 000011
【図５】
2011128903.tif 000012
【図６】
2011128903.tif 000013
【図７】
2011128903.tif 000014
【図８】
2011128903.tif 000015
【図９】
2011128903.tif 000016
【図１０】
2011128903.tif 000017
【図１１】
2011128903.tif 000018
【図１２】
2011128903.tif 000019
【図１３】
2011128903.tif 000020