(57)【要約】  楽曲検索方法においては、ユーザからの入力音声における音高の時間変化を記号化し、データベースに記録された複数の楽曲に対して前記記号化された入力音声を含む記号列をクエリとして行われた、編集距離に基づく部分シーケンスマッチングの結果を取得する。
2017056982.tif 000002
【特許請求の範囲】
【請求項１】
ユーザからの入力音声における音高の時間変化を記号化し、
データベースに記録された複数の楽曲に対して前記記号化された入力音声を含む記号列をクエリとして行われた、編集距離に基づく部分シーケンスマッチングの結果を取得する
楽曲検索方法。
【請求項２】
前記記号化は、前記入力音声における音高の時間変化を、相対音高の差として記号化する
ことを特徴とする請求項１に記載の楽曲検索方法。
【請求項３】
前記記号化は、前記入力音声における音の時間長の情報は無視して記号化する
ことを特徴とする請求項１または２に記載の楽曲検索方法。
【請求項４】
前記入力音声の受け付けと並行して当該入力音声における音高の時間変化の記号化を繰り返し行い、
前記入力音声の受け付けと並行して前記部分シーケンスマッチングの結果の前記取得を繰り返し行い、
当該楽曲検索方法は、さらに、
前記入力音声の受け付けと並行して前記結果の出力を繰り返し行う
ことを特徴とする請求項１ないし３のいずれか一項に記載の楽曲検索方法。
【請求項５】
前記部分シーケンスマッチングにおいて、前記クエリの音高と前記データベースに記録されている楽曲における音高との差の大小に応じて、前記編集距離を算出する際の編集コストに重み付けがされている
ことを特徴とする請求項１ないし４のいずれか一項に記載の楽曲検索方法。
【請求項６】
前記部分シーケンスマッチングの結果は、前記複数の楽曲の各々について前記クエリとの類似度の高低を示す指標値を含み、
当該楽曲検索方法は、
前記部分シーケンスマッチングの結果のうち、前記指標値が示す類似度が高いものから順に上位の所定数の楽曲に対して、前記クエリに含まれる音の時間長と当該楽曲において当該クエリに対応する音の時間長との差に基づいて、当該結果を修正する
ことを特徴とする請求項１ないし５のいずれか一項に記載の楽曲検索方法。
【請求項７】
ユーザからの入力音声における音高の時間変化を示す記号化する記号化部と、
データベースに記録された複数の楽曲に対して前記記号化された入力音声を含む記号列をクエリとして行われた、編集距離に基づく部分シーケンスマッチングの結果を取得する取得部と、
を有する楽曲検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楽曲を検索する技術に関する。
【背景技術】
【０００２】
データベースに記録された多くの楽曲の中からユーザが所望する楽曲を検索する技術が知られている。例えば特許文献１には、ユーザが指定した音符列に対応する音符列を含む楽曲を、音符の指定毎に順次に検索するインクリメンタルな楽曲検索装置が開示されている。特許文献２および非特許文献１は楽曲の検索に関するものではないが、これらの文献には、検索クエリと部分的に類似するシーケンスデータを検索する技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１２−４８６１９号公報
【特許文献２】特開２００８−１３４７０６号公報
【非特許文献】
【０００４】
【非特許文献１】櫻井保志、外２名、「ダイナミックタイムワーピング距離に基づくストリーム処理」、一般社団法人電子情報通信学会、電子情報通信学会論文誌Ｄ、J92-D(3)、338-350、2009年3月1日
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の技術は、入力された音符列と合致する音符列を有する楽曲を検索結果として得るものであった。そのため、必ずしも所望の楽曲を正確に表していない歌唱音声を入力とした場合に適切な検索結果が得られないという問題があった。また、特許文献２および非特許文献１は楽曲検索を対象としたものではなかった。【０００６】
これに対し本発明は、音声入力に基づいて所望の楽曲を迅速に検索する技術を提供する。
【課題を解決するための手段】
【０００７】
本発明は、ユーザからの入力音声における音高の時間変化を記号化し、データベースに記録された複数の楽曲に対して前記記号化された入力音声を含む記号列をクエリとして行われた、編集距離に基づく部分シーケンスマッチングの結果を取得する楽曲検索方法を提供する。また、本発明は、ユーザからの入力音声における音高の時間変化を記号化する記号化部と、データベースに記録された複数の楽曲に対して前記記号化された入力音声を含む記号列をクエリとして行われた、編集距離に基づく部分シーケンスマッチングの結果を取得する取得部とを有する楽曲検索装置としても把握される。
【図面の簡単な説明】
【０００８】
【図１】一実施形態に係る楽曲検索システム１の概要を例示する図
【図２】楽曲検索システム１の機能構成を例示する図
【図３】端末装置１０のハードウェア構成を例示する図
【図４】サーバ装置２０のハードウェア構成を例示する図
【図５】楽曲検索システム１の動作の概要を示すシーケンスチャート
【図６】ステップＳ１の処理の詳細を示すフローチャート
【図７】入力音声における音高の差を例示する図
【図８】レーベンシュタイン距離を算出するための行列を例示する図
【図９】本実施形態に係るマッチング行列を例示する図
【図１０】ステップＳ３の処理の詳細を示す図
【図１１】ステップＳ５において表示される検索結果を例示する図
【図１２】ステップＳ７の処理の詳細を示す図
【図１３】類似度を算出する処理を例示する図
【図１４】一実施形態に係るカラオケシステム５の構成を例示する図
【図１５】カラオケシステム５の動作の概要を示すシーケンスチャート
【発明を実施するための形態】
【０００９】
１．構成  
図１は、一実施形態に係る楽曲検索システム１の概要を例示する図である。楽曲検索システム１は、ユーザの歌唱音声を入力として、データベースに記録されている複数の楽曲の中から、その歌唱音声と類似した部分を持つ楽曲を検索するサービス（以下「楽曲検索サービス」という）を提供するシステムである。楽曲検索システム１は、端末装置１０およびサーバ装置２０を有する。端末装置１０は、楽曲検索サービスにおけるクライアントとして機能する装置であり、楽曲検索装置の一例である。サーバ装置２０は、楽曲検索サービスにおけるサーバとして機能する装置である。端末装置１０およびサーバ装置２０は、ネットワーク３０を介して接続される。ネットワーク３０は、例えば、インターネット、ＬＡＮ（Local Area Network）、および移動通信網の少なくとも１つを含む。
【００１０】
図２は、楽曲検索システム１の機能構成を例示する図である。楽曲検索システム１は、音声入力部１１、記号化部１２、クエリ生成部１３、記憶部１４、検索部１５、出力部１６、修正部１７、および取得部１８を有する。この例では、音声入力部１１、記号化部１２、クエリ生成部１３、出力部１６、および取得部１８が端末装置１０に、検索部１５および修正部１７がサーバ装置２０に、それぞれ実装されている。
【００１１】
音声入力部１１は、ユーザが発した音声の入力を受け付ける。記号化部１２は、音声入力部１１が受け付けた音声における音高の時間変化を記号化する。クエリ生成部１３は、記号化部１２により記号化された入力音声を含む検索クエリを生成する。
【００１２】
記憶部１４は、複数の楽曲に関する情報が記録されたデータベースを記憶している。検索部１５は、記憶部１４に記憶されているデータベースの中から、クエリ生成部１３により生成された検索クエリと類似する部分を有する楽曲を検索する。検索部１５は、編集距離に基づく部分シーケンスマッチングによる検索アルゴリズムを採用している。部分シーケンスマッチングとは、マッチング対象（この例では楽曲）のうち検索クエリと類似した部分を特定することをいう。この類似した部分を「類似区間」という。修正部１７は、検索部１５による検索結果において、類似度の高いものから順に上位の所定数の楽曲に対して、編集距離に基づく部分シーケンスマッチングとは異なる手法により、検索結果を修正する。修正部１７は、オンセット時間差に基づいて検索結果を修正する。
【００１３】
出力部１６は、検索部１５による検索の結果および修正部１７による検索の結果を出力する。
【００１４】
図３は、端末装置１０のハードウェア構成を例示する図である。端末装置１０は、例えば、タブレット端末、スマートフォン、携帯電話機、またはパーソナルコンピュータである。端末装置１０は、ＣＰＵ（Central Processing Unit）１００、メモリ１０１、ストレージ１０２、入力装置１０３、表示装置１０４、音声出力装置１０５、および通信ＩＦ１０６を有するコンピュータ装置である。ＣＰＵ１００は、各種演算を行い、また他のハードウェア要素を制御する装置である。メモリ１０１は、ＣＰＵ１００が処理を実行する際に用いられるコードおよびデータを記憶する記憶装置であり、例えばＲＯＭ（Read Only Memory）およびＲＡＭ（Random Access Memory）を含む。ストレージ１０２は、各種のデータおよびプログラムを記憶する不揮発性の記憶装置であり、例えばＨＤＤ（Hard Disk Drive）またはフラッシュメモリを含む。入力装置１０３は、ＣＰＵ１００に情報を入力するための装置であり、この例では少なくともマイクロフォンを含む。入力装置１０３は、さらに、例えばキーボード、タッチスクリーン、およびリモートコントローラの少なくとも１つを含んでもよい。表示装置１０４は、映像を出力する装置であり、例えば液晶ディスプレイまたは有機ＥＬディスプレイを含む。音声出力装置１０５は、音声を出力する装置であり、例えばＤＡコンバーター、増幅器、およびスピーカを含む。通信ＩＦ１０６は、ネットワーク３０を介して他の装置と通信を行うインターフェースである。
メモリ１０１およびストレージ１０２は、非一過性（non-transitory）の記録媒体であるとして観念される。ただし本明細書中において、「非一過性」の記録媒体とは、一過性の伝搬信号（transitory, propagating signal）を除く全てのコンピュータ読み取り可能な記録媒体を含み、揮発性の記録媒体を除外するものではない。
【００１５】
ストレージ１０２は、コンピュータ装置を楽曲検索サービスにおけるクライアント装置として機能させるためのアプリケーションプログラム（以下「クライアントプログラム」という）を記憶している。ＣＰＵ１００がクライアントプログラムを実行することにより、図２の機能が実装される。入力装置１０３（特にマイクロフォン）は、音声入力部１１の一例である。クライアントプログラムを実行しているＣＰＵ１００は、記号化部１２、クエリ生成部１３、および取得部１８の一例である。表示装置１０４は、出力部１６の一例である。
【００１６】
図４は、サーバ装置２０のハードウェア構成を例示する図である。サーバ装置２０は、ＣＰＵ２００、メモリ２０１、ストレージ２０２、および通信ＩＦ２０６を有するコンピュータ装置である。ＣＰＵ２００は、各種演算を行い、また他のハードウェア要素を制御する装置である。メモリ２０１は、ＣＰＵ２００が処理を実行する際に用いられるコードおよびデータを記憶する記憶装置であり、例えばＲＯＭおよびＲＡＭを含む。ストレージ２０２は、各種のデータおよびプログラムを記憶する不揮発性の記憶装置であり、例えばＨＤＤ（Hard Disk Drive）またはフラッシュメモリを含む。通信ＩＦ２０６は、ネットワーク３０を介して他の装置と通信を行うインターフェースである。
メモリ２０１およびストレージ２０２は、非一過性の記録媒体であるとして観念される。
【００１７】
ストレージ２０２は、コンピュータ装置を楽曲検索サービスにおけるサーバ装置として機能させるためのプログラム（以下「サーバプログラム」という）を記憶している。ＣＰＵ２００がサーバプログラムを実行することにより、図２の機能が実装される。ストレージ２０２は、記憶部１４の一例である。サーバプログラムを実行しているＣＰＵ２００は、検索部１５および修正部１７の一例である。
【００１８】
２．動作
２−１．概要  
図５は、楽曲検索システム１の動作の概要を示すシーケンスチャートである。ステップＳ１において、端末装置１０は、ユーザによる音声入力を受け付ける。ステップＳ２において、端末装置１０は、入力された検索指示に基づいて生成された検索クエリを、サーバ装置２０に送信する。検索クエリとは、検索エンジンに対する情報要求であり、検索キーを含む。ここで、検索キーは、記号化された入力音声を含む。ステップＳ３において、サーバ装置２０は、与えられた検索クエリに従って楽曲を検索する。ここでは、編集距離に基づく部分シーケンスマッチング用検索アルゴリズムを用いた検索が行われる。ステップＳ４において、サーバ装置２０は、検索結果を端末装置１０に送信する。ステップＳ５において、端末装置１０は、検索結果を表示する。この例で、検索はインクリメンタルに行われる。すなわち、所定のイベントを契機としてステップＳ１〜Ｓ５の処理は繰り返し実行される。すなわち、検索クエリの生成、楽曲の検索、および結果の出力は、音声入力と並行して繰り返し行われる。
【００１９】
ステップＳ６において、端末装置１０は、サーバ装置２０に対し、より詳細なマッチング（検索）を要求する。ステップＳ７において、サーバ装置２０は、編集距離に基づく部分シーケンスマッチングによる検索により、類似度の高いものから順に上位の所定数の楽曲に対し、オンセット時間差に基づいて検索結果を修正する。ステップＳ８において、サーバ装置２０は、修正された検索結果を送信する。ステップＳ９において、端末装置１０は、検索結果を表示する。
【００２０】
２−２．音声入力の受け付け
図６は、ステップＳ１の処理の詳細を示すフローチャートである。図６のフローは、例えば、ユーザにより音声入力の開始が指示されたことを契機として開始される。音声入力の開始の指示は、例えば、入力装置１０３であるタッチスクリーンを介して入力される。なお以下の説明においてクライアントプログラム等のソフトウェアを処理の主体として記載することがあるが、これは、そのソフトウェアを実行しているＣＰＵ１００等のプロセッサが他のハードウェア要素と協働して処理を実行することを意味する。
【００２１】
ステップＳ１１において、クライアントプログラムは、入力音声の音高が安定したか判断する。入力音声とは、入力装置１０３であるマイクロフォンを介して入力されたユーザの歌唱音声をいう。入力音声がユーザ（人間）の歌唱音声であるため、その音高は種々の要因によって揺らぎ不安定となる。入力音声の音高が所定の安定条件を満たした場合、クライアントプログラムは、入力音声の音高が安定したと判断する。安定条件としては、例えば、音高の揺らぎの指標がしきい値より小さくなったという条件が用いられる。音高の揺らぎの指標としては、例えば、直近の所定期間における音高の分散または最大値と最小値との差が用いられる。入力音声の音高が安定したと判断された場合（Ｓ１１：ＹＥＳ）、クライアントプログラムは、処理をステップＳ１２に移行する。入力音声の音高が安定していないと判断された場合（Ｓ１１：ＮＯ）、クライアントプログラムは、音高が安定するまで待機する。ステップＳ１１の処理は、音声入力部１１を用いて行われる。
【００２２】
ステップＳ１２において、クライアントプログラムは、音高を数値化する。ここで数値化されるのは、ステップＳ１１において安定したと判断された範囲の音、すなわち音高が同一と考えられる範囲において単一の音である。クライアントプログラムは、数値化された音高をメモリ１０１に記憶する。
【００２３】
ステップＳ１３において、クライアントプログラムは、新たに数値化された音と、その１つ前に数値化された音との相対的な音高の差を計算する。音高の差ΔＰは、新たに数値化された音（入力音声におけるｉ個目の音）の音高をＰ［ｉ］と表すと、
ΔＰ＝Ｐ［ｉ］−Ｐ［ｉ−１］      …（１）
である。
【００２４】
ステップＳ１４において、クライアントプログラムは、音高の差ΔＰを記号化する。例えば、音高の差は、十二平均律における音程（相対音高）を基準とした数値に、変化の方向を表す符号（＋または−）を付加して表される。記号化された音高の差ΔＰ［ｉ］をＳ［ｉ］と表す。例えば、Ｐ［ｉ］とＰ［ｉ−１］とが同じ音高（一度）である場合、Ｓ［ｉ］＝±０である。Ｐ［ｉ］がＰ［ｉ−１］よりも短三度高い場合、Ｓ［ｉ］＝＋３である。Ｐ［ｉ］がＰ［ｉ−１］よりも完全五度低い場合、Ｓ［ｉ］＝−７である。ステップＳ１２〜Ｓ１４の処理は、記号化部１２により行われる。
【００２５】
ステップＳ１５において、クライアントプログラムは、検索クエリを生成する。検索クエリは、音声入力が開始されてからこの時点までに検知された音高の差を、時系列に含んでいる。例えば、入力音声においてｉ個目の音が検知されたときは、検索クエリは、Ｓ［２］〜Ｓ［ｉ］までの（ｉ−１）個の音高差を示す記号を含む。ステップＳ１５の処理は、クエリ生成部１３により行われる。
【００２６】
図７は、入力音声における音高の差を例示する図である。この図において、縦軸は音高を、横軸は時間を表している。期間Ｄ１〜Ｄ７は、音高が安定していると判断された期間を示している。時刻ｔ１〜ｔ７は、期間Ｄ１〜Ｄ７のそれぞれにおいて、音高が安定したと判断された時刻（すなわち、新たな音が検知された時刻）を示している。例えば時刻ｔ２において新たな音が検知されているが、このとき１つ前の音（期間Ｄ１の音）との、記号化された音高の差は、Ｓ［ｔ２］＝＋２である。
【００２７】
図６のフローでは、クライアントプログラムは、新たな音が検知されたことを契機として検索クエリを生成する。したがってこの例では、クライアントプログラムは、時刻ｔ２〜ｔ７においてそれぞれ検索クエリを生成する。各時刻において生成される検索クエリは、音声入力が開始されてからその時点までに検知された全ての音について、１つ前の音との音高の差を記号化した情報（すなわち音高の差の順列）を含んでいる。例えば時刻ｔ３において生成される検索クエリＱ（ｔ３）は、記号化された音高の順列として、
Ｑ（ｔ３）＝（＋２，＋１）      …（２）
を含んでいる。また、時刻ｔ７において生成される検索クエリＱ（ｔ７）は、記号化された音高の差の順列として、
Ｑ（ｔ７）＝（＋２，＋１，±０，−１，＋１，−２）      …（３）
を含んでいる。
【００２８】
ここで、記号化された音高の差の順列は、音長すなわち各音の時間長に関する情報を含んでいない（時間長の情報が無視されている）。新たに検知された音の音長が十六分音符に相当しようが二分音符に相当しようが、それは音高の差の順列には影響しない。ただ１つ前の音との音高の差だけが情報として記録される。また、休符も音高の差の順列には影響しない。ある音とその次の音とが連続していようが休符を挟んでいようが、記号化されれば同じである。
【００２９】
再び図６を参照する。ステップＳ１６において、クライアントプログラムは、音高が不安定になったか判断する。音高が不安定かどうかの判断基準は、例えばステップＳ１１で用いられた基準と同じものが用いられる。音高が安定していると判断された場合（Ｓ１６：ＮＯ）、クライアントプログラムは、音高が不安定化するまで待機する。音高が不安定になったと判断された場合（Ｓ１６：ＹＥＳ）、クライアントプログラムは、処理をステップＳ１１に移行する。こうして、音声入力が継続されている限り、検索クエリの生成は継続的に繰り返し行われる。クライアントプログラムは、例えば、ユーザがタッチスクリーンを介して音声入力終了の指示を入力したことを契機として音声入力の受け付けを終了する。あるいは、クライアントプログラムは、無音の期間がしきい値時間以上継続したことを契機として音声入力の受け付けを終了してもよい。
【００３０】
クライアントプログラムは、新たな検索クエリを生成する度に、生成された検索クエリをサーバ装置２０に送信する（ステップＳ２）。検索クエリが生成されてから送信されるまでに要する時間を無視すると、図７の例では、時刻ｔ１〜ｔ７にそれぞれ検索クエリが送信される。
【００３１】
２−３．楽曲の検索  
具体的な動作説明に先立ち、ここではまず検索アルゴリズムの概要を説明する。検索には、編集距離に基づく部分シーケンスマッチングが用いられる。本実施形態の検索アルゴリズムの説明に先立ち、編集距離に基づく部分シーケンスマッチングについて説明する。編集距離としては、一般に知られているレーベンシュタイン（Levenshtein）距離が用いられる。レーベンシュタイン距離とは、２つの記号列がどの程度異なっているかを示す距離であり、文字の挿入、削除、および置換によって、ある記号列を別の記号列に編集するのに必要な最小手順によって表される。レーベンシュタイン距離に基づく曖昧検索は、正規表現やN-gram類似度に基づく手法等の他の手法と比較して、部分的な間違い（歌い間違い）が起こりやすい音声入力による楽曲検索に適している。
【００３２】
図８は、レーベンシュタイン距離を算出するための行列を例示する図である。ここでは、マッチング対象（楽曲）の記号列が「ＧＡＨＣＤＢＣ」であり、検索クエリの記号列が「ＡＢＣ」である例を用いる。なお式（２）および（３）では数値に正負符号を付加した記号を用いる例を用いたが、図面等を簡単にするため、以下では、音高差がアルファベット１文字に記号化される例を用いる。また、この例では、編集距離（編集コスト）は、挿入、削除、および置換についていずれも等価であり「１」である。
【００３３】
まず、この行列のうち第ｉ行第ｊ列のセル（以下、セル（ｊ，ｉ）という）において、マッチング対象の第ｊ番目までの記号列の後に検索クエリの第ｉ番目以降の記号列を付加した記号列を考える。以下、この記号列を、各セルにおける「対象記号列」という。例えばセル（１，１）においては、マッチング対象の第１番目までの記号列「Ｇ」の後に検索クエリの第１番目以降の記号列「ＡＢＣ」を付加した記号列「ＧＡＢＣ」が対象記号列である。あるいは、セル（６，２）においては、マッチング対象の第６番目までの記号列「ＧＡＨＣＤＢ」に検索クエリの第２番目以降の記号列「ＢＣ」を付加した記号列「ＧＡＨＣＤＢＢＣ」が対象記号列である。図８においては、各セルにおける上段に対象記号列が記載されている。
【００３４】
次に、各セルの対象記号列につき、検索クエリとのレーベンシュタイン距離を算出する。例えば、セル（１，１）においては、検索クエリの先頭に「Ｇ」を挿入することにより対象記号列が得られるので、編集距離は「１」である。また、セル（６，２）においては、検索クエリの先頭に「Ｇ」を挿入し、検索クエリの１文字目「Ａ」と２文字目「Ｂ」との間に「ＨＣＤＢ」を挿入することにより対象記号列が得られるので、編集距離は「５」である。図８においては、このようにして算出された編集距離が各セルにおける下段に記載されている。
【００３５】
一般にレーベンシュタイン距離を考える場合には、記号列が一致しているときは行列において右斜め下のセルに、記号列を追加するときは右のセルに、記号列を削除するときは下のセルに、それぞれ進んでいく。行列上をこのように進んでいくことにより、編集のための最適経路が得られる（図８に矢印で示した経路）。最適経路の終着点（図８の例ではセル（７，４））に記載されている編集距離が、検索クエリの記号列とマッチング対象の記号列とのレーベンシュタイン距離である（図８の例では「４」）。しかし、この手法には主に２つの問題点がある。第１には、２つの記号列の文字数の差に依存して編集距離が大きくなる点である。例えば検索クエリと完全に一致する部分を含む２つの楽曲があったとしても、これらの楽曲の長さが異なっていれば、楽曲が長い方がレーベンシュタイン距離は大きくなる。第２には、マッチング対象の楽曲うち検索クエリと類似した部分（類似区間）の検出には不向きである点である。すなわち、行列において最適経路すなわち最小の距離を与える経路をたどっていっても、当該経路が必ずしも類似区間とは対応していない。
【００３６】
そこで、本実施形態においては、特許文献２および非特許文献１に関連するＳＰＲＩＮＧという手法が用いられる。この手法においては、検索クエリの先頭および末尾の行においてレーベンシュタイン距離ｄがゼロに設定される。
【００３７】
図９は本実施形態に係るマッチング行列を例示する図である。マッチング行列は、図８で示した編集距離を算出するための行列に対応するものであり、類似区間を特定するためのものである。まず対象記号列の考え方は、図８で説明したものと同様である。ここで、図９に示すように検索クエリの先頭にマッチング対象の第ｊ列までの記号列（検索クエリにおいて星印で表している）が付加されているので、第１行の全てのセルにおいて、検索クエリは対象記号列と等しくなり、編集距離はゼロとなる。
【００３８】
第２行目以降のセル（ｊ，ｉ）において、編集距離Ｄ（ｊ，ｉ）は以下のとおり算出される。
D(j,i) = d(j,i) + min[D(j-1,i-1), D(j-1,i), D(j,i-1)]      
…（４）
ここで、ｄ（ｊ，ｉ）は、セル（ｊ，ｉ）における対象記号列と、検索クエリの第（ｉ−１）番目以降の記号列の先頭にマッチング対象の第（ｊ−１）番目までの記号列を付加した記号列とのレーベンシュタイン距離である。例えば、セル（５，３）においては、対象記号列が「ＧＡＨＣＤＣ」であり、検索クエリの第２番目以降の記号列「ＢＣ」の先頭にマッチング対象の第４番目までの記号列「ＧＡＨＣ」を付加した記号列が「ＧＡＨＣＢＣ」であるので、両者を対比してｄ（５，３）＝１である。関数ｍｉｎは、引数のうち最小のものを表す。すなわち、上式の右辺第２項は、対象となっているセルの左斜め上、左隣、および上隣のセルの編集距離Ｄのうち最小値を示している。例えば、
D(5,3) = d(5,3) + min[D(4,2), D(4,3), D(5,2)]
= 1 + min[ 1, 2, 1 ]
= 1 + 1         = 2                                    
…（５）
である。
【００３９】
マッチング行列のうち最下行（図９の例では第５行）は、そのセルの左斜め上、左隣、および上隣のセルの編集距離のうち最小値を示している。このことから、マッチング行列の右下端のセルに記録されている編集距離は、そのマッチング対象のうち検索クエリと最も類似している部分の編集距離、すなわち検索クエリとの最小距離を示している。マッチング対象が検索クエリと完全に一致する部分を含んでいる場合、検索クエリとの最小距離はゼロである。この手法によれば、マッチング行列は、マッチング対象の記号列の長さに依らず検索クエリとの最小距離を出力することが保証されている。以下、楽曲において検索クエリとの最小距離を「スコア」という。スコアは、楽曲が検索クエリと類似している程度（類似度）の高低を示す指標値である。この例ではスコアがゼロに近いほど、検索クエリと類似した部分を含んでいることが示される（類似度が高い）。単に検索クエリと類似した部分を含む楽曲を検索するだけであれば、計算したマッチング行列の編集距離を全て記憶している必要はなく、楽曲毎にスコアだけを記憶しておけばよい。またこの手法によれば、最適経路（ここでは、右隣、右下、および下隣のセルのうち最小距離のセルをたどる経路。同一距離のセルが複数ある場合は「より右」かつ「より下」のセルが優先。図９に矢印で示した経路）により１つの類似区間（図９の例では類似区間ｒ２）を特定することができる。なお、ここでは最適経路を特定するため、「より右」かつ「より下」のセルが優先である例を説明したが、これらが等価なものとして扱われてもよい。この場合、編集距離が相互に等しい複数の類似区間（図９の例では類似区間ｒ１およびｒ２）が特定される可能性がある。
【００４０】
図１０は、ステップＳ３の処理の詳細を示す図である。ステップＳ３の処理は、検索部１５により行われる。ステップＳ３１において、サーバプログラムは、端末装置１０から検索クエリを受信したか判断する。新たな検索クエリを受信したと判断された場合（Ｓ３１：ＹＥＳ）、サーバプログラムは、処理をステップＳ３２に移行する。新たな検索クエリを受信していないと判断された場合（Ｓ３１：ＮＯ）、サーバプログラムは、検索クエリを受信するまで待機する。
【００４１】
ステップＳ３２において、サーバプログラムは、記憶部１４に記憶されているデータベースに記憶されている楽曲の中から、マッチング対象となる一の楽曲を所定の順序に従って特定する。データベースには、各楽曲に関する情報、具体的には、その楽曲の識別子等の属性情報、およびその楽曲を再生するための楽曲データ（例えばＭＩＤＩ（Musical Instrument Digital Interface）データ、リニアＰＣＭ（Pulse Code Modulation）データ等の非圧縮音声データ、またはいわゆるＭＰ３データ等の圧縮音声データ）が含まれる。さらに、このデータベースは、楽曲のうち主旋律（例えば歌唱楽曲であればメインボーカルの旋律）を記号化したデータを含んでいる。
【００４２】
ステップＳ３３において、サーバプログラムは、マッチング対象の楽曲について、マッチング行列（具体的には、各セルにおける編集距離、および当該楽曲に対する検索クエリとの最小距離（すなわちスコア））を計算する。マッチング行列の計算方法は既に説明したとおりである。マッチング行列の計算に際し、サーバプログラムは、データベースからマッチング対象の楽曲が記号化されたデータを読み出して使用する。
【００４３】
ステップＳ３４において、サーバプログラムは、マッチング対象の楽曲のスコアがしきい値よりも小さいか判断する。このしきい値は例えばあらかじめ設定されている。スコアがしきい値以上であると判断された場合（Ｓ３４：ＮＯ）、サーバプログラムは、計算したマッチング行列をメモリ２０１から消去する（ステップＳ３５）。スコアがしきい値よりも小さいと判断された場合（Ｓ３４：ＹＥＳ）、サーバプログラムは、処理をステップＳ３６に移行する。
【００４４】
ステップＳ３６において、サーバプログラムは、マッチング対象の楽曲の識別子およびスコアを結果テーブルに記録する。結果テーブルは、類似度が高い（スコアがしきい値より小さい）楽曲に関する情報が記録されたテーブルである。結果テーブルはさらに、各楽曲において類似区間を特定する情報を含んでいる。
【００４５】
ステップＳ３７において、サーバプログラムは、データベースに記録されている全ての楽曲についてマッチング行列の計算が完了したか判断する。まだマッチング行列を計算していない楽曲があると判断された場合（Ｓ３７：ＮＯ）、サーバプログラムは、処理をステップＳ３２に移行する。ステップＳ３２では次の楽曲が新たなマッチング対象となり、新たなマッチング対象の楽曲についてステップＳ３３〜Ｓ３６の処理が行われる。全ての楽曲についてマッチング行列の計算が完了したと判断された場合（Ｓ３７：ＹＥＳ）、サーバプログラムは、処理をステップＳ４に移行する。ステップＳ４において、サーバプログラムは、検索クエリの送信元の端末装置１０に検索結果として結果テーブルを送信する。
【００４６】
２−４．検索結果の表示
図１１は、ステップＳ５において表示される検索結果を例示する図である。端末装置１０のクライアントプログラムは、サーバ装置２０から受信した結果テーブルを用いて検索結果を表示する。表示される検索結果は、複数の楽曲について、楽曲の識別子（この例では曲名）およびスコアを含んでいる。複数の楽曲は、類似度が高い順（スコアの値が小さい順）に並べられている。
【００４７】
なお検索結果の表示方法は図１１の例に限定されない。例えば、楽曲の識別子およびスコアに加えて、または代えて、類似区間を特定する情報（例えば類似区間の楽譜や歌詞）が表示されてもよい。また、複数の楽曲に関する情報ではなく、スコアが最高の単一の楽曲に関する情報のみが表示されてもよい。
【００４８】
なお既に説明したようにステップＳ１〜Ｓ５の処理は繰り返し行われるので、音声入力が継続している限り、検索結果は継続的に更新されていく。音声入力が開始して間もないうちは検索クエリが短いので検索結果にノイズが含まれる可能性が高いが、音声入力を継続して検索クエリが長くなるにつれ楽曲は絞り込まれノイズが落とされていくことが期待される。
【００４９】
２−５．検索結果の修正
詳細なマッチングを開始するための条件が満たされると、端末装置１０は、サーバ装置２０に対し、より詳細なマッチング、すなわち検索結果の高精度化を要求する（ステップＳ６）。詳細なマッチングを開始するための条件は、例えば、音声入力が終了した、または、ユーザから詳細なマッチングの明示的な指示が入力された、という条件である。この条件が満たされると、端末装置１０は、詳細なマッチングの要求（以下「高精度化要求」という）を送信する。この高精度化要求は、詳細なマッチングの要求である旨の情報、検索クエリ、対象楽曲を特定する情報、および各楽曲において類似区間を特定する情報を含んでいる。対象楽曲を特定する情報は、ステップＳ４で受信した結果テーブルに含まれる楽曲の少なくとも一部の楽曲の識別子を含む。少なくとも一部の楽曲とは、例えば、結果テーブルにおいて類似度の最上位から所定順位まで（具体例としては１〜１０位）の楽曲である。
【００５０】
この高精度化要求に含まれる検索クエリは、ステップＳ１４およびＳ１５で生成された検索クエリとは別の情報であり、各音の音長に関する情報を含んでいる。音長に関する情報には、例えばオンセット時間差を示す情報が含まれる。オンセット時間差とは、ある音の発音が開始されてからその次の音の発音が開始されるまでの時間長をいう。以下、ステップＳ６において送信される検索クエリをステップＳ１４およびＳ１５で生成された検索クエリと区別するときは、前者を「第１検索クエリ」といい、後者を「第２検索クエリ」という。第２検索クエリは、入力音声の波形を示す非圧縮音声データまたは圧縮音声データであってもよいし、入力音声をオンセット時間差も含めて記号化したデータであってもよい。クライアントプログラムは、入力音声をデータ化して記憶しておき、記憶しているデータを用いて第２検索クエリを生成する。第１検索クエリによる検索では発音の時間長が無視されるのに対し、第２検索クエリによる検索では、発音の時間長も加味して楽曲が絞り込まれる。
【００５１】
図１２は、ステップＳ７の処理の詳細を示す図である。ステップＳ７の処理は、修正部１７により行われる。ステップＳ７１において、サーバプログラムは、高精度化要求に含まれる対象楽曲の中から、マッチング対象となる一の楽曲を所定の順序に従って特定する。
【００５２】
ステップＳ７２において、サーバプログラムは、マッチング対象の楽曲のうち第１検索クエリとの類似区間と第２検索クエリとを比較し、両者の類似度を数値化する。類似度を数値化する際には、オンセット時間差が考慮される。なお、オンセット時間差に代えて、入力音声のうち有声音の区間の時間長（すなわち音高が検出された区間の時間長）を、第２検索クエリにおいて記号化することも可能である。
【００５３】
図１３は、類似度を算出する処理を例示する図である。ここでは、マッチング対象として２つの楽曲（楽曲１および楽曲２）を考える。図１３には、楽曲１および楽曲２のうち、第１検索クエリとの類似区間の譜面のみを示している。譜面から明らかなように両者は異なる楽曲であるが、ステップＳ１４およびＳ１５において記号化され音長の情報が削除されると、両者は同じ記号となる。ここでは例として「ＡＢＣＡＢＣ」という記号を考える。記号が同じであるので、第１段階における検索では楽曲１のスコアと楽曲２のスコアとは同点である。
【００５４】
図１３には第２検索クエリも併せて記載している。第１検索クエリは「ＡＢＣＡＢＣ」である。オンセット時間差も含めて記号化すると、第２検索クエリは例えば「Ａ（１）Ｂ（１）Ｃ（１）Ａ（２）Ｂ（１）Ｃ（１）」と表せる。括弧内の数字は、その前の記号の音とその１つ前の音とのオンセット時間差を表している（この例では八分音符相当の時間長が「１」）。同様に楽曲１をオンセット時間差も含めて記号化すると「Ａ（１）Ｂ（２）Ｃ（２／３）Ａ（２／３）Ｂ（２／３）Ｃ（２）」と表せる。楽曲２をオンセット時間差も含めて記号化すると「Ａ（１）Ｂ（１）Ｃ（１）Ａ（２）Ｂ（１）Ｃ（１）」と表せる。なおここでは便宜的に第１音のオンセット時間差を１とした。
【００５５】
サーバプログラムは、まず楽曲１と検索クエリとのオンセット時間差を計算する。ここでは、音毎にオンセット時間差の二乗を求め、これを類似区間の全ての音について積算する。例えば、楽曲１と検索クエリとのオンセット時間差ΔＬ（１）は、
【数１】
2017056982.tif 000003
同様に、例えば楽曲２と検索クエリとのオンセット時間差ΔＬ（２）は、  
ΔL(2) = 0.0      ・・・（７）
である。オンセット時間差ΔＬは、その値が小さいほど検索クエリと類似していることを示している。すなわちこの例では、楽曲２の方が楽曲１より検索クエリと類似していることが分かる（すなわち楽曲２との類似度が楽曲１との類似度よりも高い）。このように、オンセット時間差ΔＬは、マッチング対象の楽曲と第２検索クエリとの類似度の高低を示す第２の指標値であるといえる（これに対し、スコアは、マッチング対象の楽曲と第１検索クエリとの類似度の高低を示す第１の指標値であるといえる）。
【００５６】
再び図１２を参照する。ステップＳ７３において、サーバプログラムは、マッチング対象の楽曲のスコアを、ステップＳ７２において計算されたオンセット時間差を用いて修正する。例えば、サーバプログラムは、マッチング対象の楽曲のスコアに、計算されたオンセット時間差を加算または乗算する。
【００５７】
ステップＳ７４において、サーバプログラムは、高精度化要求において指定された全てのマッチング対象楽曲についてスコアの修正が完了したか判断する。まだスコアの修正が終了していない楽曲があると判断された場合（Ｓ７４：ＮＯ）、サーバプログラムは、処理をステップＳ７１に移行する。ステップＳ７１においてサーバプログラムは新たなマッチング対象の楽曲を特定し、以下ステップＳ７２〜Ｓ７３の処理を行う。全てのマッチング対象楽曲についてスコアの修正が完了したと判断された場合（Ｓ７４：ＹＥＳ）、サーバプログラムは、修正されたスコアの一覧を高精度化要求の送信元の端末装置１０に送信する（ステップＳ８）。端末装置１０は、検索結果を表示する（ステップＳ９）。ここでの結果表示は、例えばステップＳ５における結果表示と同様に行われる。あるいは、この結果は、この結果が最終結果である（これ以上インクリメント検索が実行されない）ことを示す情報と共に表示されてもよい。
【００５８】
３．適用例  
次に、楽曲検索システム１をカラオケ装置に適用した例を説明する。この例では、データベースに記録されているカラオケ楽曲の中から、ユーザの歌唱音声の入力を検索クエリとして楽曲が検索される。さらに、検索により特定された楽曲は、ユーザの歌唱音声に追従するように再生される。すなわちこのカラオケ装置によれば、ユーザがある楽曲をアカペラで歌い出すと、そのメロディに適合する楽曲が検索され、ユーザの歌に追従する形でカラオケ（伴奏）が演奏される。
【００５９】
図１４は、一実施形態に係るカラオケシステム５の構成を例示する図である。カラオケシステム５は、カラオケ装置５０およびサーバ装置６０を有する。カラオケ装置５０は、ユーザにより選択された楽曲を演奏（再生）する装置である。サーバ装置６０は、カラオケ楽曲のデータを記憶しており、また、楽曲検索サービスを提供する。カラオケ装置５０およびサーバ装置６０は、インターネットまたは専用線を介して通信する。
【００６０】
カラオケ装置５０は、音声入力部１１、記号化部１２、クエリ生成部１３、出力部１６、特定部５１、通信部５２、および再生部５３を有する。カラオケ装置５０は、楽曲検索システム１における端末装置１０に相当（すなわち楽曲検索装置に相当）する。音声入力部１１、記号化部１２、クエリ生成部１３、および出力部１６については既に説明したとおりである。特定部５１は、ユーザの歌唱による入力音声から、その歌唱におけるテンポおよびキーを取得する。通信部５２は、サーバ装置６０と通信する。この例で、通信部５２は、クエリ生成部１３により生成された検索クエリ、および一の楽曲の要求をサーバ装置６０に送信し、楽曲データをサーバ装置６０から受信する。再生部５３は、サーバ装置６０から受信した楽曲データに従って楽曲を再生する。再生部５３は、例えばスピーカおよび増幅器を含む。
【００６１】
サーバ装置６０は、記憶部１４、検索部１５、修正部１７、および通信部６１を有する。サーバ装置６０は、楽曲検索システム１におけるサーバ装置２０に相当する。記憶部１４、検索部１５、および修正部１７については既に説明したとおりである。記憶部１４に記憶されているデータベースは、カラオケ楽曲のデータベースである。通信部６１は、カラオケ装置５０と通信する。この例で、通信部６１は、検索結果および楽曲データをカラオケ装置５０に送信する。
【００６２】
図１５は、カラオケシステム５の動作の概要を示すシーケンスチャートである。ステップＳ１００において、カラオケ装置５０は、音声入力を受け付ける。ステップＳ２００において、カラオケ装置５０は、検索クエリをサーバ装置６０に送信する。ステップＳ３００において、サーバ装置６０は、検索クエリと類似する部分を有する楽曲を検索する。ステップＳ５００において、カラオケ装置５０は、検索結果を表示する。なお、ステップＳ１００〜Ｓ５００の処理の詳細は、楽曲検索システム１におけるステップＳ１〜Ｓ９の処理と同様である。
【００６３】
ステップＳ６００において、カラオケ装置５０は、検索結果として得られた複数の楽曲の中から一の楽曲を選択する。楽曲はユーザの指示入力により選択されてもよいし、ユーザの明示的な指示によらずカラオケ装置５０により自動的に選択（例えば類似度が最高（スコアが最小）の楽曲を自動的に選択）されてもよい。
【００６４】
ステップＳ７００において、カラオケ装置５０は、選択された楽曲の要求をサーバ装置６０に送信する。この要求は、選択された楽曲を特定する識別子を含んでいる。サーバ装置６０は、要求された楽曲の楽曲データをカラオケ装置５０に送信する。ステップＳ８００において、カラオケ装置５０は、サーバ装置６０から楽曲データを受信する。
【００６５】
ステップＳ９００において、カラオケ装置５０は、受信した楽曲データに従って、カラオケ楽曲を再生する。このとき、カラオケ装置５０は、ユーザの入力音声から抽出されたテンポおよびキーでカラオケ楽曲を再生する。カラオケ装置５０は、ステップＳ１００〜Ｓ８００までのいずれかのタイミングで、歌唱の入力音声から、その歌唱のテンポおよびキーを抽出する。カラオケ装置５０は、カラオケ楽曲を、入力音声から抽出されたテンポおよびキーに合わせて再生する。また、カラオケ装置５０は、ユーザの歌唱に追従する再生位置（再生時刻）からカラオケ楽曲を再生する。ユーザの歌唱に追従する再生位置とは、選択されたカラオケ楽曲において検索クエリとの類似区間に応じて特定される再生位置をいう。例えば、カラオケ装置５０がサーバ装置６０に対して検索クエリを送信してから楽曲データの送信を要求し、さらにその楽曲データの受信が完了するまでの時間差がほぼゼロであるような理想的なシステムにおいては、カラオケ装置５０は、類似区間の終了時点からそのカラオケ楽曲を再生する。この時間差が無視できない程度ある場合、カラオケ装置５０は、類似区間の終了時点に、この時間差の予測値を付加した時刻からそのカラオケ楽曲を再生する。
【００６６】
カラオケシステム５によれば、ユーザは膨大な一覧の中から所望の楽曲を検索する手間を省くことができる。さらに、カラオケシステム５によれば、ユーザのアカペラ歌唱に追従する形でカラオケ楽曲（伴奏）が再生され、新たな楽しみ方を提供することができる。
【００６７】
なお、例えば検索結果として得られた複数の楽曲の何れかをユーザが選択した時点で検索を終了することも可能である。例えば、検索された複数の楽曲のリストが出力部１６により表示される。具体的には、複数の楽曲の楽曲名をスコアの降順で配列したリストが表示される。スコアに応じて各楽曲の表示態様（例えば表示の色またはサイズ）を相違させることも可能である。
【００６８】
ユーザは、自身が意図した楽曲をリストから選択可能である。出力部１６は、ユーザが選択した楽曲を強調表示する。例えば、ユーザが選択した楽曲がリストの最上位に移行され、他の楽曲とは異なる表示態様で（例えば異なる色で）で表示される。以上のように楽曲が選択されると、楽曲の検索が終了し、その時点の検索結果が最終的な結果として確定する。具体的には、ユーザによる楽曲の選択を契機として検索クエリの生成および送信が終了し、以降は楽曲の検索は実行されない。
【００６９】
４．変形例  
本発明は上述の実施形態に限定されるものではなく、種々の変形実施が可能である。以下、変形例をいくつか説明する。以下の変形例のうち２つ以上のものが組み合わせて用いられてもよい。
【００７０】
４−１．変形例１  
編集距離の算出方法は実施形態で例示したものに限定されない。例えば、挿入、削除、および置換の編集コストは等価ではなく、重みが付けられていてもよい。具体的には、置換の編集コストは、置換前後の音高の差に応じて編集コストが異なっていてもよい。例えば、置換前後の音高の差が小さいほど編集コストが小さくなるように設定されていてもよい。単純なレーベンシュタイン距離のみによれば音高の差は考慮されず、検索クエリと半音ずれているときでも５音ずれているときでも編集コストすなわちスコアは同じである。しかし、この例では音高差が小さいほど編集コストが小さいので、検索クエリとの音高差が小さいほどスコアの値が小さく（類似度が高く）なり、より詳細に類似度を判定できる。あるいは、挿入よりも削除の方が編集コストの方が大きいといったように、編集の種類毎に編集コストが異なっていてもよい。
【００７１】
４−２．変形例２  
音高差または編集の種類に応じて編集コストを異ならせる場合、過去の検索クエリの履歴に応じて編集コストが決定されてもよい。例えば、ある楽曲の特定の部分について、過去の検索クエリにおいては特定の部分の音高が実際の楽曲よりも低くなる傾向が統計的に見られる場合がある。この場合、楽曲内の特定の部分の音高と比べて検索クエリ内の当該特定の部分の音高が低い場合の方が、音高が高い場合よりも編集コストが小さくなるように設定される。あるいは検索クエリにおいて音高差が特定の条件を満たすとき（例えば、前の音と次の音で１オクターブ以上音程が上がるとき）に特定の音高のずれが発生しやすい傾向が統計的に見られる場合、この傾向に応じて編集コストが設定される。
【００７２】
４−３．他の変形例  
検索クエリを生成する契機となるイベントは、入力音声において新たな音が検出されたことに限定されない。音声入力中に検索クエリを直近に生成してから所定の時間が経過したことを契機として、検索クエリが生成されてもよい。また、特に音声入力が開始した直後においては、記号化された入力音声のデータ量がしきい値を超えたことを契機として、検索クエリが生成されてもよい。あるいは、入力音声において新たな音高差が所定数、検出されたことを契機として検索クエリが生成されてもよい。さらに別の例で、音声入力が終了したことを契機として検索クエリが生成されてもよい。この場合、インクリメンタルな検索は行われない。
【００７３】
編集距離に基づく部分シーケンスマッチングを行うための検索クエリは、オンセット時間差の情報を含んでいてもよい。すなわち、記号化部１２は、オンセット時間差の情報を含めて音声を記号化してもよい。また、記号化部１２は、音高の差ではなく、音高そのものを記号化してもよい。この場合、検索部１５が、検索クエリに含まれる音高の推移を、音高の変化の推移に変換する。
【００７４】
音高差を記号化する手法は実施形態で例示したものに限定されない。十二平均律などの音階における音程によらない基準により記号化されてもよい。
【００７５】
検索結果を高精度化する手法は実施形態で例示したものに限定されない。編集距離に基づく部分シーケンスマッチングで用いられていない情報を用いるものであれば、どのような手法が採用されてもよい。
【００７６】
図２に例示した楽曲検索システム１の機能の一部は省略されてもよい。例えば、修正部１７の機能、すなわちオンセット時間差に基づく検索結果の修正は省略されてもよい。
【００７７】
修正部１７が検索結果の修正を行うタイミングは実施形態で例示したものに限定されない。例えば、図５のフローにおいて、ステップＳ５の結果表示およびステップＳ６の詳細な検索要求は省略されてもよい。サーバ装置２０は、楽曲の検索（ステップＳ３）を行うと自動的に検索結果の修正（ステップＳ７）を行う。すなわち、サーバ装置２０は、楽曲の検索および検索結果の修正を逐次的に行う。この場合、端末装置１０は、ステップＳ２においてオンセット時間差に関する情報をサーバ装置２０に送信する。サーバ装置２０は、修正された検索結果を端末装置１０に送信する。
【００７８】
楽曲検索システム１のハードウェア構成は図３および図４に例示したものに限定されない。要求される機能を実現できるものであれば、楽曲検索システム１はどのようなハードウェア構成を有していてもよい。また、機能とハードウェア要素との対応関係は実施形態で例示したものに限定されない。例えば、端末装置１０が、検索部１５および修正部１７に相当する機能を有していてもよい。すなわち、サーバ装置２０が検索を行うのではなく、端末装置１０自身が検索を行ってもよい。この場合には、取得部１８は自身の検索部１５が行った部分シーケンスマッチングの結果を取得する。さらに端末装置１０が、記憶部１４に相当する機能を有していてもよい。すなわち、端末装置１０自身がデータベースを記憶していてもよい。別の例で、端末装置１０ではなくサーバ装置２０が、記号化部１２、クエリ生成部１３、および取得部１８を有していてもよい。すなわち、サーバ装置２０も本発明の楽曲検索装置の一例であり、サーバ装置２０の取得部１８は自身の検索部１５が行った部分シーケンスマッチングの結果を取得する。
【００７９】
ステップＳ７２における類似度の算出方法は実施形態で例示したものに限定されない。入力音声におけるオンセット時間差を記号化する際、端末装置１０は、入力音声を、その長さがマッチング対象の楽曲のうち入力音声に対応する部分の長さと等しくなるように伸張（すなわち入力音声の時間長を規格化）してから記号化してもよい。この方法によれば、テンポが違う曲でも、譜割りの違いによって類似度を見分けることができる。また、類似度の指標として、検索クエリにおける音とマッチング対象の楽曲における対応する音とのオンセット時間差の二乗和（式（６））に代わり、オンセット時間差の絶対値を音の数で平均した値が用いられてもよい。音数で平均することで、音の多さに依存しないオンセット時間差を評価することができる。なお検索クエリにおける音とマッチング対象の楽曲における対応する音とのオンセット時間差に代えて、または加えて、両者における相互に対応する音の音長の差が用いられてもよい。なお音長を用いるのであれば、休符も考慮する必要がある。
【００８０】
入力音声のうち音高が検出されない区間を検索クエリＱに反映させることも可能である。音高が検出されない区間としては、音量の不足等の理由により音高を正確に検出できない区間（無音区間）と、調波構造を持たない子音が発音されている区間（子音区間）とが想定される。
例えば、無音区間または子音区間の直前の区間ａと直後の区間ｂとで音高が同一である場合には、区間ａとその直前の区間との音高差を表す記号と、区間ｂとその直前に音高が検出された区間ａとの音高差（すなわちゼロ）を表す記号とが、検索クエリＱに個別に含められる。無音区間または子音区間を、音高がない区間として記号化することも可能である。また、高精度化要求に含まれる検索クエリでは、子音区間を、当該子音に対応する直後の母音の区間に含めて、時間長（オンセット時間差）を決定することも可能である。
【００８１】
楽曲検索サービスを提供するためのソフトウェア構成は実施形態で例示したものに限定されない。単一のプログラムではなく、複数のソフトウェアコンポーネントの集合体が実施形態で説明した機能を提供してもよい。
【００８２】
楽曲検索サービスを提供するためのプログラム（例えばクライアントプログラムおよびサーバプログラム）は、光ディスク、磁気ディスク、半導体メモリなどの記憶媒体により提供されてもよいし、インターネット等の通信回線を介してダウンロードされてもよい。
【００８３】
楽曲検索システム１の適用例は、カラオケシステムに限定されない。例えば、ネットワークを介した楽曲配信サービスにおける楽曲検索、または音楽プレイヤーにおける楽曲検索に楽曲検索システムが適用されてもよい。
【００８４】
以上の説明から、以下に述べる各態様の発明が把握される。
すなわち、本発明の一態様にかかる楽曲検索方法は、ユーザからの入力音声における音高の時間変化を記号化し、データベースに記録された複数の楽曲に対して前記記号化された入力音声を含む記号列をクエリとして行われた、編集距離に基づく部分シーケンスマッチングの結果を取得する。この態様によれば、音声入力に基づいて所望の楽曲を迅速に検索することができる。
【００８５】
好適な態様において、前記記号化は、前記入力音声における音高の時間変化を、相対音高の差として記号化してもよい。この態様においては、相対音高（例えば十二平均律における音程）の差として入力音声が記号化されるから、入力音声における音の音高が楽曲における音の音高と相違していても、入力音声における時系列の音の音高の推移（すなわちメロディ）に適合する楽曲を検索可能となる。
【００８６】
好ましくは、前記記号化は、前記入力音声における音の時間長の情報は無視して記号化してもよい。この態様によれば、ユーザから入力音声における音の時間長が楽曲における対応する音の時間長と相違している場合であっても、音高が一致する楽曲を検索可能となる。
【００８７】
好適な態様において、上記楽曲検索方法においては、前記入力音声の受け付けと並行して当該入力音声における音高の時間変化の前記記号化を繰り返し行い、入力音声の受け付けと並行して前記部分シーケンスマッチングの結果の前記取得を繰り返し行い、さらに、前記入力音声の受け付けと並行して前記結果の出力を繰り返し行ってもよい。この態様においては、入力音声の受付と並行して入力音声の記号化および部分シーケンスマッチングの結果の取得が実行されて結果が出力されるので、入力音声の受付に追従して検索結果が更新され得る。よって、ユーザは、歌唱音声の入力途中であっても、適合する楽曲の検索結果を知ることが可能となる。
【００８８】
好適な態様において、前記部分シーケンスマッチングにおいて、前記クエリの音高と前記データベースに記録されている楽曲における音高との差の大小に応じて、前記編集距離を算出する際の編集コストに重み付けがされていてもよい。この態様によれば、音高の差が小さいほど編集コストが小さいので、クエリとの音高の差が小さい楽曲ほどスコアの値が小さく（類似度が高く）なり、より詳細に類似度を判定できる。
【００８９】
好適な態様において、前記部分シーケンスマッチングの結果は、前記複数の楽曲の各々について前記クエリとの類似度の高低を示す指標値を含み、当該楽曲検索方法は、前記部分シーケンスマッチングの結果のうち、前記指標値が示す類似度の高いものから順に上位の所定数の楽曲に対して、前記クエリに含まれる音の時間長と当該楽曲において当該検索クエリに対応する音の時間長との差に基づいて、当該結果を修正するようにしてもよい。この態様によれば、音高の時間変化に加えて音の時間長を加味するから、検索結果の精度を高めることが可能となる。
【００９０】
また、本発明は、以上の各態様にかかる楽曲検索方法を実行する楽曲検索装置、当該各楽曲検索方法をコンピュータに実行させるプログラム、または、当該プログラムを記録した記録媒体としても把握される。これら楽曲検索装置、プログラム、または記録媒体によれば、前述と同様の効果が奏される。楽曲検索装置は端末装置１０またはサーバ装置２０によって実現されてもよく、これらの装置が協働することにより実現されてもよいことは前述のとおりである。
【符号の説明】
【００９１】
１…楽曲検索システム、１０…端末装置、１１…音声入力部、１２…記号化部、１３…クエリ生成部、１４…記憶部、１５…検索部、１６…出力部、１７…修正部、２０…サーバ装置、３０…ネットワーク、１００…ＣＰＵ、１０１…メモリ、１０２…ストレージ、１０３…入力装置、１０４…表示装置、１０５…音声出力装置、１０６…通信ＩＦ、２００…ＣＰＵ、２０１…メモリ、２０２…ストレージ、２０６…通信ＩＦ
【図１】
2017056982.tif 000004
【図２】
2017056982.tif 000005
【図３】
2017056982.tif 000006
【図４】
2017056982.tif 000007
【図５】
2017056982.tif 000008
【図６】
2017056982.tif 000009
【図７】
2017056982.tif 000010
【図８】
2017056982.tif 000011
【図９】
2017056982.tif 000012
【図１０】
2017056982.tif 000013
【図１１】
2017056982.tif 000014
【図１２】
2017056982.tif 000015
【図１３】
2017056982.tif 000016
【図１４】
2017056982.tif 000017
【図１５】
2017056982.tif 000018
【国際調査報告】
2017056982.tif 000019
2017056982.tif 000020
2017056982.tif 000021
2017056982.tif 000022