"検索質問としてコンテンツデータ片を入力し、当該コンテンツデータ片の特徴を示す複数の検索質問サブ特徴量から構成される互いに類似する複数の検索質問サブ特徴量短系列を作成する手段と、最終的な検索対象のコンテンツデータの特徴を示す直接的な検索対象となる複数の検索対象サブ特徴量を連結した検索対象サブ特徴量配列に基づき、当該検索対象サブ特徴量配列に含まれる各検索対象サブ特徴量から開始する前記検索質問サブ特徴量短系列の長さのブロックを2進数としての大小関係に基づいてソートした場合の先頭の検索対象サブ特徴量の識別情報をソートされた順に保持したインデックス配列に対し、前記検索質問サブ特徴量短系列により2分探索を行って検索候補位置を決定する手段と、決定された複数の検索候補位置からそれぞれ開始する検索対象サブ特徴量と前記検索質問サブ特徴量短系列とのハミング距離をそれぞれ計算する手段と、計算されたハミング距離が小さい順に検索候補位置に相当する検索結果をソートする手段と、ソートされた検索結果の上位所定数の検索結果を最終的な検索結果として出力する手段とを備えたことを特徴とするハミング空間検索装置。検索質問としてコンテンツデータ片を入力し、当該コンテンツデータ片の特徴を示す複数の検索質問サブ特徴量から構成される互いに類似する複数の検索質問サブ特徴量短系列を作成する工程と、最終的な検索対象のコンテンツデータの特徴を示す直接的な検索対象となる複数の検索対象サブ特徴量を連結した検索対象サブ特徴量配列に基づき、当該検索対象サブ特徴量配列に含まれる各検索対象サブ特徴量から開始する前記検索質問サブ特徴量短系列の長さのブロックを2進数としての大小関係に基づいてソートした場合の先頭の検索対象サブ特徴量の識別情報をソートされた順に保持したインデックス配列に対し、前記検索質問サブ特徴量短系列により2分探索を行って検索候補位置を決定する工程と、決定された複数の検索候補位置からそれぞれ開始する検索対象サブ特徴量と前記検索質問サブ特徴量短系列とのハミング距離をそれぞれ計算する工程と、計算されたハミング距離が小さい順に検索候補位置に相当する検索結果をソートする工程と、ソートされた検索結果の上位所定数の検索結果を最終的な検索結果として出力する工程とを備えたことを特徴とするハミング空間検索方法。ハミング空間検索装置を構成するコンピュータを、検索質問としてコンテンツデータ片を入力し、当該コンテンツデータ片の特徴を示す複数の検索質問サブ特徴量から構成される互いに類似する複数の検索質問サブ特徴量短系列を作成する手段、最終的な検索対象のコンテンツデータの特徴を示す直接的な検索対象となる複数の検索対象サブ特徴量を連結した検索対象サブ特徴量配列に基づき、当該検索対象サブ特徴量配列に含まれる各検索対象サブ特徴量から開始する前記検索質問サブ特徴量短系列の長さのブロックを2進数としての大小関係に基づいてソートした場合の先頭の検索対象サブ特徴量の識別情報をソートされた順に保持したインデックス配列に対し、前記検索質問サブ特徴量短系列により2分探索を行って検索候補位置を決定する手段、決定された複数の検索候補位置からそれぞれ開始する検索対象サブ特徴量と前記検索質問サブ特徴量短系列とのハミング距離をそれぞれ計算する手段、計算されたハミング距離が小さい順に検索候補位置に相当する検索結果をソートする手段、ソートされた検索結果の上位所定数の検索結果を最終的な検索結果として出力する手段として機能させるハミング空間検索プログラム。請求項3に記載のハミング空間検索プログラムを記録したコンピュータ読取可能な記録媒体。ランダム置換に基づく検索の最大の欠点は、膨大なデータ容量を必要とすることである。効率的な検索を行うためには、元の検索対象データ集合にあらかじめランダム置換を施したデータ集合を作成しておく必要がある図1参照。また、複数のランダム置換を考える必要があるため、元データ集合の数倍~数十倍程度の容量が必要となる。本発明は上記の従来の問題点に鑑み提案されたものであり、その目的とするところは、膨大なデータ容量を必要とすることなく、高速に検索を行えるようにすることにある。上記の課題を解決するため、本発明にあっては、検索質問としてコンテンツデータ片を入力し、当該コンテンツデータ片の特徴を示す複数の検索質問サブ特徴量から構成される互いに類似する複数の検索質問サブ特徴量短系列を作成する手段と、最終的な検索対象のコンテンツデータの特徴を示す直接的な検索対象となる複数の検索対象サブ特徴量を連結した検索対象サブ特徴量配列に基づき、当該検索対象サブ特徴量配列に含まれる各検索対象サブ特徴量から開始する前記検索質問サブ特徴量短系列の長さのブロックを2進数としての大小関係に基づいてソートした場合の先頭の検索対象サブ特徴量の識別情報をソートされた順に保持したインデックス配列に対し、前記検索質問サブ特徴量短系列により2分探索を行って検索候補位置を決定する手段と、決定された複数の検索候補位置からそれぞれ開始する検索対象サブ特徴量と前記検索質問サブ特徴量短系列とのハミング距離をそれぞれ計算する手段と、計算されたハミング距離が小さい順に検索候補位置に相当する検索結果をソートする手段と、ソートされた検索結果の上位所定数の検索結果を最終的な検索結果として出力する手段とを備える。本発明にあっては、膨大なデータ容量を必要とすることなく、高速に検索を行うことができる。以下、本発明の好適な実施形態につき説明する。<原理>ランダム置換に基づく検索では、元のデータ集合を複数のランダム置換により多重化することにより、ビット列データに対する近傍検索を実現しているということができる。もし仮に、検索質問のみを多重化することができれば、元のデータ集合に対する多重化は不要となり、少ない記憶容量でハミング空間の検索が可能になる。上記を実現するための考え方は単純であり、検索質問と類似したビット列データを複数作成することにより、検索質問の多重化を行う。図2に、検索質問多重化による検索手法の模式図を示す。図1と同様に、検索対象となるデータ集合を一番上に、検索質問を一番下に示している。図中、φiφ1、φ2、φ3は検索質問のビット列と類似したデータを作成する関数である。関数φiは、元になるビット列に数値計算等を施す場合だけではなく、元になるビット列から値を取得する位置等を変える等の情報操作一般を含む。<構成>図3は検索装置1の構成例を示す図である。なお、主として楽曲の検索を想定したものとなっているが、楽曲以外の検索にも適用できることは言うまでもない。図3において、検索装置1は、オーディオ指紋抽出部特徴量抽出部101と、インデックス配列作成部102と、検索質問曲片入力部検索質問コンテンツデータ片入力部103と、サブ指紋短系列抽出部サブ特徴量短系列生成部104と、検索候補位置決定部105と、ハミング距離計算部106と、検索結果ソート部107と、検索結果出力部108とを備えている。これらの機能部は、検索装置1を構成するコンピュータのCPUCentralProcessingUnit、ROMReadOnlyMemory、RAMRandomAccessMemory等のハードウェア資源上で実行されるコンピュータプログラムによって実現されるものである。これらの機能部は、単一のコンピュータ上に配置される必要はなく、必要に応じて分散される形態であってもよい。また、検索装置1が利用するデータベースとして、楽曲データベースコンテンツデータベース111と、オーディオ指紋データベース特徴量データベース112とが設けられている。これらのデータベースは、検索装置1を構成するコンピュータ内のHDDHardDiskDrive等の記憶媒体上に所定のデータを体系的に保持するものである。なお、楽曲データベース111とオーディオ指紋データベース112は検索装置1内に配置される必要はなく、他の装置データベースサーバ等上に配置し、ネットワークを介して検索装置1からアクセスする形態としてもよい。図4は楽曲データベース111の構造例を示す図である。楽曲データベース111は、楽曲コンテンツを識別する楽曲IDコンテンツIDと、曲名、アーティスト名、アルバム名等の書誌情報と、楽曲本体データコンテンツ本体データ等が対応付けられて保持されている。図5はオーディオ指紋データベース112の構造例を示す図である。オーディオ指紋データベース112は、楽曲IDコンテンツIDと、オーディオ指紋特徴量等が対応付けられて保持されている。オーディオ指紋は、メッセージダイジェスト一方向ハッシュ関数によるダイジェスト値の一種であり、楽曲の音響的知覚的特性に基づき、元の楽曲データを比較的コンパクトなビット列表現に変換するための技術である。認証やデジタル署名等で用いられるMD5等のメッセージダイジェストでは、元のデータが少しでも異なると、まったく異なったハッシュ値が得られるが、オーディオ指紋の場合には、楽曲にノイズが混入したり、楽曲が劣化したりといった場合にも、類似したハッシュ値が得られるように設計されている。また、オーディオ指紋データベース112には、楽曲毎にオーディオ指紋を連結したサブ指紋配列サブ特徴量配列FPが保持される。図示は省略してあるが、楽曲IDからサブ指紋配列FPに含まれるサブ指紋サブ特徴量を参照できるとともに、サブ指紋配列FPのサブ指紋から楽曲IDを参照できる。また、オーディオ指紋データベース112には、サブ指紋配列FPのサブ指紋を対象にして検索質問短系列の長さを単位に2進数としての大小関係に基づいてソートした順番で先頭のサブ指紋の位置を示すインデックス配列Sが保持される。図6は検索装置1のハードウェア構成例を示す図である。検索装置1は、システムバス11に接続されたCPU12、ROM13、RAM14、NVRAMNonVolatileRandomAccessMemory15、I/FInterface16と、I/F16に接続された、キーボード、マウス、モニタ、CD/DVDCompactDiskDigitalVersatileDiskドライブ等のI/OInputOutputDevice17、HDD18、NICNetworkInterfaceCard19等を備えている。Mはプログラムもしくはデータが格納されたCD/DVD等のメディア記録媒体である。<動作>図7は検索前の事前準備の処理例を示すフローチャートである。図7において、処理を開始すると、検索装置1のオーディオ指紋抽出部101は、楽曲データベース111から楽曲本体データを参照し、オーディオ指紋を抽出するステップS11。オーディオ指紋は、楽曲毎にサブ指紋を時系列に配置したものである。オーディオ指紋抽出アルゴリズムには、さまざまなものが提案されており、フーリエ係数特徴に基づく手法非特許文献13、メルケプストラム係数特徴に基づく手法非特許文献14、スペクトル扁平特徴に基づく手法非特許文献15などが研究されている。以下では、HaitsmaおよびKalker非特許文献1による周波数帯域間のエネルギー差の特徴を用いたオーディオ指紋抽出アルゴリズムの概要を示す。HaitsmaKalkerアルゴリズムでは、入力された楽曲データをフレームに分割後、オーバーラップした各フレームからサブ指紋subfingerprintと呼ばれる32ビットの特徴量を抽出する。サブ指紋は、実際には周波数領域において計算する。各フレームをFFTFastFourierTransformにより周波数領域に変換後、重なりのない33個の周波数帯域に分割し、帯域間のエネルギー差の符号プラスあるいはマイナスからサブ指紋を求める。HaitsmaおよびKalkerでは、フレーム長037秒フレームの重なり度は3132であり、ハニングウィンドウにより重み付けした後に、周波数領域に変換している。したがって、116ミリ秒ごとに1つのサブ指紋が抽出されることになる。なお、本実施形態においては、ハニングウィンドウに代えてハミングウインドウを用いている。具体的なサブ指紋の計算は、フレームnの周波数帯域mにおけるエネルギーをEn,mとするとき、フレームnの第mビットFn,mを以下の式により求める。HaitsmaおよびKalkerは、周波数領域におけるエネルギー差の符号から得られる特徴が、楽曲の識別同定において有効であり、しかも圧縮や伸長等の多くの処理に対し頑健であることを実験的に示している。HaitsmaKalkerアルゴリズムは、オーディオ指紋抽出の各ステップが単純な算術演算で実装でき、生成されるオーディオ指紋がコンパクトであるという特徴を持っている。次いで、オーディオ指紋抽出部101は、サブ指紋配列FPを作成するステップS12。サブ指紋配列FPは、オーディオ指紋楽曲毎にサブ指紋を時系列に配置を検索対象となる複数の楽曲について連結したものである。次いで、オーディオ指紋抽出部101は、楽曲毎に抽出したオーディオ指紋を楽曲ID等と対応付けてオーディオ指紋データベース112に格納するとともに、作成したサブ指紋配列FPをオーディオ指紋データベース112に格納するステップS13。次いで、検索装置1のインデックス配列作成部102は、サブ指紋配列FPに含まれる各サブ指紋から開始する検索質問短系列の長さのブロックを2進数としての大小関係に基づいてソートした場合の先頭のサブ指紋の識別情報位置をソートされた順に保持したインデックス配列Sを作成するステップS14。インデックス配列Sの作成は、例えば、次のように行う。検索質問短系列の長さをm、楽曲データベース中の全曲から得られたサブ指紋配列FP=FP1,FP2,,FPnとするとき、サブ指紋配列FP中の長さmの全系列のソート位置を表す1次元のインデックス配列S=S1,S2,,Snを考える。インデックス配列Sは、接尾辞配列suffixarray非特許文献16と同様に、サブ指紋配列FPへのインデックスを格納した配列であり、次式を満たすようにする。なお、iffはifandonlyifの略である。Sj=iiffFPi,FPi1,,FPim1がソート順でj番目の短系列検索処理では、検索質問曲から得られたサブ指紋の短系列に対し、インデックス配列S上を2分探索すればよい。また、2分探索された位置の前後を調べることで、サブ指紋短系列の近傍検索を行うことができる。インデックス配列Sの大きさは、楽曲データベース中のサブ指紋配列FPの長さに比例した大きさであり、ランダム置換を用いる手法に比べ、はるかに少ない容量である。次いで、インデックス配列作成部102は、ソート済サブ指紋配列もしくはインデックス配列Sをオーディオ指紋データベース112に格納しステップS15、処理を終了する。図8は検索の処理例を示すフローチャートである。図8において、処理を開始すると、検索装置1の検索質問曲片入力部103は、検索質問曲片を入力するステップS21。検索質問曲片はマイク等により取得された後、デジタルデータに変換されて入力される。次いで、検索装置1のサブ指紋短系列抽出部104は、検索質問曲片から類似する複数のサブ指紋短系列を抽出するステップS22。サブ指紋短系列はサブ指紋のブロックである。オーディオ指紋の抽出図7のステップS11では、検索対象である楽曲データベース111中の各楽曲から複数のサブ指紋ブロックを抽出している。すなわち、1つの楽曲データに対し、開始フレーム1から得られるサブ指紋ブロック、開始フレーム2から得られるサブ指紋ブロック、開始フレーム3から得られるサブ指紋ブロックというように、非常に多数のサブ指紋ブロックが得られる。これと同様に、検索質問として楽曲片が与えられると、この楽曲片からも開始フレームが少しずつ異ならせることで、複数のサブ指紋ブロックが得られる。サブ指紋の時系列において、隣り合ったサブ指紋の間には大きな類似性があり、時間が進むにつれ、少しずつ異なったサブ指紋が得られるという特徴がある。このような開始時間の異なる複数のサブ指紋を用いて検索質問の多重化を行うことができる。なお、オーディオ指紋の場合はサブ指紋ブロックを取得する開始フレームを少しずつ変化させることで多重化された類似する複数のサブ指紋短系列を抽出することができるが、ビデオ等を含む一般的なコンテンツデータ片の場合は、例えば、元のビット列を機械的に操作してビット反転を行うことや、あるいは元のビット列にノイズをのせる等により多重化を行うことができる。次いで、検索装置1の検索候補位置決定部105は、抽出したすべてのサブ指紋短系列に対して、インデックス配列S上を2分探索し、検索候補位置を求めるステップS23。2分探索は、インデックス配列S上の全体の中央に存在するサブ指紋ブロックの値と質問から抽出したサブ指紋短系列の値を2進数として比較し、抽出したサブ指紋短系列の値が大きければ、全体の中央よりも値が低い側の半分に範囲を限定してその中央に着目点を移して比較を続行し、抽出したサブ指紋短系列の値が小さければ、全体の中央よりも値が高い側の半分に範囲を限定してその中央に着目点を移して比較を続行するという処理を繰り返すものである。図9はサブ指紋短系列によりインデックス配列Sを2分探索する様子を示している。インデックス配列Sの2分探索にあたり、インデックス配列Sのインデックスからサブ指紋を参照し、サブ指紋の値を取得して比較を行う。次いで、図8に戻り、検索装置1のハミング距離計算部106は、抽出したすべてのサブ指紋短系列と、検索候補位置を開始位置とするサブ指紋ブロックとのハミング距離ビットエラー率BERbiterrorrateを計算するステップS24。2つのサブ指紋ブロックの同一性を判定するための尺度としてハミング距離を用いている。いま、2つの楽曲片A、Bから抽出されたサブ指紋をそれぞれFAn,m、FBn,mとするとき、長さNのサブ指紋ブロックに対するビットエラー率BERA,Bは、以下のようにして計算することができる。なお、演算子^は、ビット演算XORexclusiveorを表している。上式の分子は、2つのサブ指紋ブロック間のハミング距離を計算しており、サブ指紋ブロックのビット長32Nで除算することにより、1ビット当たりのエラー率を計算している。次いで、検索装置1の検索結果ソート部107は、計算したハミング距離に基づき、検索結果をハミング距離が小さい順にソートするステップS25。ここで、検索結果は、楽曲IDにより識別されるものとすることができる。次いで、検索装置1の検索結果出力部108は、ソートした上位のもの上位所定数を検索結果として出力するステップS26。検索結果に含まれる楽曲IDから楽曲データベース111を参照することで、曲名、アーティスト名、アルバム名等の書誌情報を出力することができる。<評価実験>本実施形態の楽曲検索アルゴリズムの有効性を検証するために、実際の楽曲データを用いた評価実験を行った。評価実験で用いたオーディオ指紋抽出は、基本的にはHaitsmaKalkerアルゴリズムと同様の手法を用いたが、音楽分析条件等は異なっている。検索対象となる楽曲は、8740曲のMP3データである。これらの曲は、CDやインターネットなどから個人的に収集した曲であり、曲によってMP3の圧縮率は異なっている。楽曲のジャンルも、和洋ポップス、クラシック、民族音楽など、多岐に渡っている。検索質問となる楽曲は、YouTubeにアップロードされたものを用いた。PVやライブ映像など、多様な形態の動画から音声部分のみを抽出した。前後に数十秒程度の無音があるもの、拍手、歓声、セリフなどを含んでいるもの、ノイズを含んでいるものなど、低品質な楽曲データも数多く存在する。評価用のデータは全268曲であり、これらのデータは、データ収集者による分類がなされ、楽曲の状態に関するコメントが付与されている図10参照。楽曲データは、4000Hzにダウンサンプリングを行った後、フレーム長1024秒、フレームシフト0032秒で分析を行い、ハミング窓Hammingwindowによる重み付け、FFTによる周波数領域への変換を行っている。周波数領域では、33個の周波数帯域に分割して、32ビットのサブ指紋特徴量を抽出した。また、サブ指紋ブロックの長さは128とした。上記の分析条件は、HaitsmaおよびKalker非特許文献1に比べると荒いものとなっているが、これらの条件は、いくつかの予備実験を行い決定した。提案アルゴリズムでは、上記程度の分析条件でも十分な検索精度が得られることがわかった。なお、この条件で分析を行った際に得られるサブ指紋の総数は、検索対象8740曲に対して、約7千万である。本稿での提案手法は、オーディオ指紋に基づく楽曲の高速検索アルゴリズムであるので、まず検索速度面について説明する。評価実験を行った計算機はDELLPrecisionM6500ノートパソコン、CPUはIntelCorei7173GHz全8コア、搭載メモリは4GBである。曲によって検索時間は異なるが、1曲あたり概ね04~06秒程度で検索可能である。検索質問1曲あたりのサブ指紋の系列長は、6000~8000程度のものが大多数を占める。提案アルゴリズムでは、検索質問曲から得られるすべてのサブ指紋短系列長さ3に対して、2分探索による検索候補位置の計算を行った後、サブ指紋ブロックに対するビットエラー率の計算を行っている。したがって、サブ指紋ブロック1つあたりの検索時間は00001秒以下で行われていることになり、十分、高速であるということができる。検索精度であるが、図10の右欄に、第1位での正解率を示している。原曲に対する第1位での検索率は968、ライブに対する第1位での正解率は831である。原曲に対しては、ノイズの有無によって評価データを2つに分類しているが、結果的には、ノイズによる検索精度への影響はみられなかった。原曲とライブとの間で検索精度の違いがみられるが、この理由は、ライブでは元の曲をアレンジしていたり、元の曲調とは異なっていたりする場合があるためであると考えられる。<総括>LSHでは、検索精度を保つために、一般に複数のハッシュ関数を用いており、このため検索用データであるハッシュ表に相当の容量が必要となる。ハミング距離に対する従来のLSHの場合、ランダム置換が一種のハッシュ関数に相当するが、ランダム置換により複数の検索対象データをあらかじめ用意しておく必要がある。我々の提案手法では、開始時間の異なる複数のサブ指紋の短い系列を用いて検索質問の多重化を行うことにより、検索対象データの多重化を必要としない。従来手法に比べ、検索インデックスの大きさをはるかに少なくすることが可能である。評価実験において、検索速度あるいは検索精度の面から評価を行い、提案手法の有効性を示した。以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。"