(57)【要約】データベースからデータを抽出する方法及び装置が開示される。複数のエンティティが第１メモリに格納され、格納されている各エンティティに関する情報が第２メモリに格納される。少なくとも１つの不明確な表現の形式による基準が、格納されているエンティティからいくつかのエンティティを選択するためユーザから受け取られる。受け取られた基準は、格納されている情報において用いられる用語に変換される。その後、変換された基準に基づくエンティティのシーケンスが選択される。
2006510986.tif 000002
【特許請求の範囲】
【請求項１】
複数のエンティティを格納する手段と、
格納されている各エンティティに関する情報を格納する手段と、
前記格納されているエンティティからいくつかのエンティティを選択するため、少なくとも１つの不明確な表現の形式による基準をユーザから受け取る手段と、
受け取った基準を前記格納されている情報において用いられる用語に変換する手段と、
前記変換された基準に基づきエンティティのシーケンスを選択する手段と、
を有することを特徴とするデータベース抽出システム。
【請求項２】
請求項１記載のデータベース抽出システムであって、
前記ユーザから基準を受け取る手段は、キーボード、マウス、マイクロフォンの少なくとも１つを有することを特徴とするシステム。
【請求項３】
請求項１記載のデータベース抽出システムであって、
エンティティは、音楽、映像コンテンツ、音声/.映像コンテンツ及び画像の少なくとも１つを有することを特徴とするシステム。
【請求項４】
請求項１記載のデータベース抽出システムであって、
前記少なくとも１つの不明確な表現は、不明確限定詞、単数/複数数量詞、疑問副詞及び疑問形容詞の少なくとも１つを有することを特徴とするシステム。
【請求項５】
請求項１記載のデータベース抽出システムであって、
前記受け取られた基準は、ハミング及びタッピングの１つを有することを特徴とするシステム。
【請求項６】
請求項１記載のデータベース抽出システムであって、
前記受け取られた基準は、アドホッククラスであることを特徴とするシステム。
【請求項７】
請求項１記載のデータベース抽出システムであって、
前記格納されている情報は、当該データベース抽出システムにダウンロードされることを特徴とするシステム。
【請求項８】
請求項１記載のデータベース抽出システムであって、
前記ユーザは、前記格納されている情報の少なくとも一部を当該データベース抽出システムに入力することを特徴とするシステム。
【請求項９】
請求項１記載のデータベース抽出システムであって、
前記エンティティに関する情報は、前記エンティティから読み出され、前記格納する手段に格納されることを特徴とするシステム。
【請求項１０】
複数のエンティティを格納するステップと、
格納されている各エンティティに関する情報を格納するステップと、
前記格納されているエンティティからいくつかのエンティティを選択するため、少なくとも１つの不明確な表現の形式による基準をユーザから受け取るステップと、
受け取った基準を前記格納されている情報において用いられる用語に変換するステップと、
前記変換された基準に基づきエンティティのシーケンスを選択するステップと、
を有することを特徴とするデータベース抽出方法。
【請求項１１】
請求項１０記載のデータベース抽出方法であって、
前記ユーザからの基準は、キーボード、マウス、マイクロフォンの少なくとも１つを用いて入力されることを特徴とする方法。
【請求項１２】
請求項１０記載のデータベース抽出方法であって、
エンティティは、音楽、映像コンテンツ、音声/.映像コンテンツ及び画像の少なくとも１つを有することを特徴とする方法。
【請求項１３】
請求項１０記載のデータベース抽出方法であって、
前記少なくとも１つの不明確な表現は、不明確限定詞、単数/複数数量詞、疑問副詞及び疑問形容詞の少なくとも１つを有することを特徴とする方法。
【請求項１４】
請求項１０記載のデータベース抽出方法であって、
前記受け取られた基準は、ハミング及びタッピングの１つを有することを特徴とする方法。
【請求項１５】
請求項１０記載のデータベース抽出方法であって、
前記受け取られた基準は、アドホッククラスであることを特徴とする方法。
【請求項１６】
請求項１０記載のデータベース抽出方法であって、
前記格納されている情報は、データベース抽出システムにダウンロードされることを特徴とする方法。
【請求項１７】
請求項１０記載のデータベース抽出方法であって、
前記ユーザは、前記格納されている情報の少なくとも一部をデータベース抽出システムに入力することを特徴とする方法。
【請求項１８】
請求項１０記載のデータベース抽出方法であって、
前記エンティティに関する情報は、前記エンティティから読み出され、前記格納するステップに格納されることを特徴とする方法。
【請求項１９】
複数のエンティティと各エンティティに関する情報が格納されるデータベースからデータを受け取る方法ステップを実行するようマシーンにより実行可能な命令のプログラムを有形に実現する前記マシーンにより読み出し可能なプログラム記憶装置であって、
前記方法ステップは、
前記格納されているエンティティからいくつかのエンティティを選択するため、少なくとも１つの不明確な表現の形式により基準をユーザから受け取るステップと、
受け取られた基準を前記格納されている情報で用いられる用語に変換するステップと、
前記変換された基準に基づきエンティティのシーケンスを選択するステップと、
を有することを特徴とするプログラム記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ情報に対する方法及び装置に関し、より詳細には、不明確な表現を用いてデータベースから情報を照会する方法及び装置に関する。
【背景技術】
【０００２】
コンピュータがより強力になり、より安価に購入及び使用することができるようになるに従い、コンピュータデータベースに格納されているデータ量は、驚くべきスピードで拡大している。例えば、コンピュータデータベースは、音楽コレクション、映像コンテンツ、音声/映像コンテンツ、画像などを有するかもしれない。これらデータベースに格納されているデータへのアクセス及び利用を行うため、様々なデータベース抽出技術が利用される。
【０００３】
既知のデータベース抽出技術は、主として、ミュージックイディオム、インスツルメンテーション、演奏者、作曲家などに関する検索及び照会、あるいはキーワード検索などのテキストベースメディアとして音楽情報を扱う音楽に対する従来の書誌的分類スキームに基づくものである。従来技術による方法では、指定された属性とそれらに関する値の論理表現としてクエリを定式化することが要求される。このとき、このクエリの実行は、音楽レコーディングなどの特定のエンティティ群を指定する。これら従来の方法は、音楽属性及びそれら各自の値に関するユーザ側のドメイン知識を要求する。典型的なクエリは、ミュージックイディオムと当該イディオムからの楽曲アーティストの選択である。テキストベース抽出は、曲の歌詞などの静的テキストをインデックス化し、これらのインデックスとユーザクエリとの間の類似性を検出することによって、キーワードから構成されたユーザクエリを解く統計的技術の適用に着目したものである。
【０００４】
ユーザがこれらの音楽の特徴に精通していないか、あるいは無知である場合、ユーザは場当たり的なナビゲーションに頼り、音楽コレクションを検索しなければならなくなる。さらに、多数の人々は視聴したいものは知ってはいるが、現在のデータベース抽出技術に必要とされる正確な方法または用語により自身の要求を表現または定式化することができない。従って、ユーザが曖昧だが自然な用語を用いてデータベースからの１以上のアイテムを要求することを可能にすることにより、よりユーザフレンドリーなデータベース抽出システムが必要とされる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の課題は、不明確な表現を用いてデータベースからアイテムを選択することにより、データベースに照会する方法及び装置を提供することにより上記問題点を解決することである。
【課題を解決するための手段】
【０００６】
本発明の一実施例によると、データベースからデータを抽出する方法及び装置が開示される。複数のエンティティが第１メモリに格納され、格納されている各エンティティに関する情報が第２メモリに格納されている。少なくとも１つの不明確な表現形式による基準が、格納されているエンティティからエンティティを選択するためユーザから受信される。受信した基準は、格納されている情報に用いられる用語に変換される。その後、変換された基準に基づくエンティティのシーケンスが選択される。
【０００７】
本発明の上記及び他の特徴は、以降において説明される実施例を参照することにより明らかとなるであろう。
【発明を実施するための最良の形態】
【０００８】
本発明は、データベースから情報を照会するための新規な方法を提供する。以下の説明は、楽曲抽出、楽曲選択、楽曲編集及び楽曲シーケンス処理のため、楽曲に関する情報の照会を説明するが、本発明は映像コンテンツ、音声/映像コンテンツ、画像などを有するデータベースにもまた利用可能であるということは当業者には理解されるであろう。
【０００９】
図１は、本発明の実施例を利用する用いることができる音声/映像ジュークボックスシステム１０を示す。ジュークボックスシステム１０は、市場で入手可能な各種標準的なデータプロセッサを備えるコンピュータ１１を有する。コンピュータ１１のサイズは、アクセスされるデータベースのサイズ、プロセッサ１２に必要とされる他の機能、及び各種処理を実行するのに要するスピードに応じて可変とされてもよい。以下の説明のため、同一のコンピュータ１１を用いてユーザから受信した用語を変換し、データベースを検索すると仮定するが、このことは本発明を限定するものではなく、後述される各種機能を実行するのに異なるプロセッサが利用されてもよい。さらに、コンピュータ１１は、ユーザにより提供された用語から楽曲などの格納されているデータシーケンスを検出するのに用いられる１以上の既知のアルゴリズムを有する。
【００１０】
コンピュータ１１は、検索対象のデータベースが格納されている少なくとも１つの大規模メモリを有する。メモリ１３は、各種大容量メモリの何れであってもよい。コンピュータ１１はまた、メモリ１３に格納されている情報のめたデータが構造化形式により格納されている少なくとも１つの追加的記憶装置１４を有するようにしてもよい。メインデータベースメモリ１３のサイズに応じて、メモリ１４はまたかなりのサイズを有するものとしてもよい。メモリ１３及び１４は、別々の記憶装置であってもよいし、あるいは同一の記憶装置の各セクションであってもよい。
【００１１】
本発明の一実施例では、メインデータベースメモリ１３は、音楽、映像コンテンツ、音声/映像コンテンツ、画像などのエンティティのコレクションを有するようにしてもよい。さらにジュークボックスシステムでは、メモリ１３は、音楽ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）のコレクションを有するＣＤ記憶装置２１に接続されてもよい。第２メモリ１４は、データベースメモリ１３の各エンティティを特徴付けするのに利用されるメタデータを有するようにしてもよい。メタデータは、各エンティティがユーザにより指定された基準を満たすか判断するため、検索アルゴリズムにより使用される。
【００１２】
メタデータは様々な方法により生成し、メモリ１４に格納することが可能であるが、本発明はこれに限定されるものではない。例えば、メタデータは、タイトルが購入または取得されるとき、各タイトルに付属するかもしれない。例えば、ＣＤの各楽曲を記述するメタデータが、メモリ１３に転送されたり、あるいはコンパクトな記憶装置２１に追加されると、メタデータはＣＤからメモリ１４に追加することが可能となる。さらに、ユーザはコンピュータ１１を用いて、データベースメモリ１３に追加された各タイトルのめたデータを生成することができる。メタデータはまた、インターネットなどを用いて外部のコンピュータからコンピュータ１１にダウンロードすることも可能である。
【００１３】
コンピュータ１１に情報を提供するため、いくつかの標準的な入力装置１６が利用可能であってもよい。これらは、以下に限定されるものではないが、キーボード装置、マウス、ローラボール入力、テキスト/画像スキャナ、モデム、対話型ディスプレイ、他のシステムからのネットワーク入力などを含むものであってもよい。当該システムに利用可能な１つのオプションは、システムにクエリを入力するのに利用可能なマイクロフォンを有する音声認識モジュール１７である。コンピュータ１１はまた、ディスプレイ、プリンタ、音声シンセサイザ、スピーカー１９などのいくつかの標準的な出力装置１８を有するようにしてもよい。
【００１４】
本発明の一実施例によると、クエリはマイクロフォンに入力された楽曲の一部のハミングやタッピングとして与えられてもよい。
【００１５】
本発明の一実施例によると、本発明は、音楽ドメインのクエリ結果を提供するため、複数のクエリ機構、クエリダイアログ及び対話的方法を統合したものを表す。プレイリストの生成は、制約充足問題とみなすことができる。簡単には、制約充足問題（ＣＳＰ）は以下のように述べられる。有限の離散的なドメインと制約集合から値をとりうる変数集合（または未知の）が与えられる。各制約は、解かれるべき問題に関する部分的情報を提供する変数の部分集合上で定義される線形表現または論理関係である。各制約は、部分集合の変数がとりうる値の組み合わせを制限する。問題の解法は、すべての制約が充足されるような変数に対する値の割当てを求めることである。また、すべての制約を満たすすべての可能な値の割当てを網羅的に検索することも可能である。
【００１６】
制約の重要な特徴はそれの宣言的性質であり、すなわち、制約はどの関係が成り立つ必要があるか、当該関係を実行するための計算手順を特定することなく指定する。言い換えると、システムタスクが問題を解こうとする間、ユーザは満たされるべき制約により当該問題を記述する。「私は、スローテンポでピアノとサックスフォンとの小さなアンサンブルにより演奏されるが、３人のみのピアノ演奏者からの１０タイトルのジャズソングを所望する」というフレーズは、音楽ドメインに対する制約を宣言することにより、ユーザが自身の音楽選考を表現する典型的な一例である。この例では、１つの制約が充足される必要があるだけでなく、必ずしも独立またはコンフリクトのない制約群が充足される必要があるということは明らかである。
【００１７】
制約は、すべての変数の部分集合上で定義される関係としてみなすことができる。すなわち、それは、これらの変数に対する許容される値の割当てを表す項の集合から構成される。それのすべての変数が値を有し、対応する値の項が当該制約に属する場合、制約は「充足」される。ＣＳＰの「解」は、すべての制約が充足されている間のすべての変数の完全なインスタント化である。任意の制約を満たさないＣＳＰの部分的または完全なインスタンス化は、「ｃｏｎｓｉｓｔｅｎｔ」と呼ばれる。解が存在しないＣＳＰは、「ｉｎｃｏｎｓｉｓｔｅｎｔ」（または、解決不能、制約オーバー）と呼ばれる。
【００１８】
「変数の濃度（ｃａｒｄｉｎａｌｉｔｙ）」とは、当該変数を参照する制約の個数である。「制約の項数（ａｒｉｔｙ）」とは、当該制約が定義される変数の個数である。一項制約は、１つの変数の値を制限する。二項制約は、２つの変数の値を制限する。ｎ項制約は、ｎ個の変数の値を制限する。一項及び二項制約は、主として基本制約と呼ばれる。これは、ｎ項制約から構成される任意のＣＰＳは、二項制約のみからなるＣＳＰに変換することができるためである。いわゆる二項ＣＳＰは、ノードが変数を表し、各エッジが当該エッジの終端により表される変数間の二項制約を表す制約付グラフにより示すことが可能である。一項制約は、同一ノードから始まり、そこで終わるループエッジにより表される。二項ＣＳＰへの変換は、与えられたｎ項ＣＳＰは、追加的な制約がより大きなドメインによる追加的な値に対して生成及び解かれる必要があるため、より容易に解くことができるということを必ずしも意味するものでない。しかしながら、多くのＣＳＰ解法技術は、二項ＣＳＰのみに適用可能である。
【００１９】
楽曲プレイリストは、連続的に再生することが可能な楽曲の有限シーケンスとして定義される。自動による楽曲リストの生成は、困難な組み合わせ問題である。
【００２０】
それを制約充足問題として定式化することは、図２に示されるような制約集合のプレイリストの所望のプロパティを指定することに帰着する。プレイリストのプロパティは、音楽リスナーにより表現されるような音楽選好を反映したものである。この点に関する変数は、所与の有限のサイズを有する音楽コレクションからの楽曲により占有されねばならないプレイリストシーケンスにおけるオープンポジションである。初期的には、各オープンプレイリストポジションのドメインは、音楽コレクション全体により決定される。これは、プレイリストの各ポジションが当該コレクションからの何れかの楽曲により充填される可能性があるためである。このとき、ｃｏｎｓｉｓｔｅｎｔなプレイリストは、プレイリストのすべてのプロパティが満足されながら、すべてのプレイリストポジションが音楽コレクションからの楽曲を有する解となる。
【００２１】
各楽曲は、書誌的データと音楽知覚プロパティを有する属性表現により表される。また、楽曲属性は、所与の有限の属性ドメインからの値のみをとりうるものであり、楽曲属性のドメインは、この所与の音楽コレクションに存在するすべての値の集合から構成される。与えられた楽曲の属性が固定された値を有し、問題を解いている間それらは操作不可とされるということが強調されるべきである。代わりに、プレイリストポジションに割当てられる楽曲自体が操作される。本実施例では、テーブル１に示される楽曲の属性表現が用いられるが、本発明はそれに限定されるものでない。
【００２２】
【表１】
2006510986.tif 000003
楽曲属性のドメインは、「ノミナル（ｎｏｍｉｎａｌ）」、「バイナリ（ｂｉｎａｒｙ）」、カテゴリカル（ｃａｔｅｇｏｒｉｃａｌ）」、「タクソノミカル（ｔａｘｏｎｏｍｉｃａｌ）」、「オーディナル（ｏｒｄｉｎａｌ）」、「ニューメリカル（ｎｕｍｅｒｉｃａｌ）」あるいは「コンポジット（ｃｏｍｐｏｓｉｔｅ）」が可能である。「ノミナル」属性の値は、値の集合の等価性、相違性及び所属性（ｍｅｍｂｅｒｓｈｉｐ）のみを反映している。同一のオブジェクトには同一の値が与えられるが、異なるオブジェクトには異なる値が与えられる。ノミナル属性の例として、タイトル、アルバムタイトル及び楽曲アーティストがあげられる。ドメインは、音楽コレクションで知られているすべてのタイトル及びアーティストから構成される。
【００２３】
「バイナリ」属性は、異なる２つの値のうち１つのみをとりうる属性である。本質的には、バイナリ属性はノミナルである。それの値は等価性または相違性に関するテストのみを可能にする。一例として、ある楽曲がライブの聴衆の前で記録されたかどうかを示す表示があげられる。
【００２４】
「カテゴリカル」属性は、与えられた楽曲がそれのミュージックイディオム（例えば、クラシック、ジャズ、ポップスなどの主要なジャンルなど）などに割当てることが可能なカテゴリを表す。ここでの属性表現にはない他の例として、クラシック作曲の主題的カタログ番号やクラシック作品のクラス（オーケストラ、チェインバ、キーボード、ボーカル）があげられる。それの値は、単に等価性、相違性及び集合所属性を反映している。ある特徴に関して同一であるオブジェクトには、それらが同一のカテゴリに属するとみなされるときには、同一の値が与えられる。
【００２５】
「タクソノミカル」属性は、概念的階層をそれの値に課す。これらタクソノミーは、音楽をカタログ化するための専門知識を実現する。ミュージックイディオムでは、このＩＳ−Ａ階層は、音楽スタイル、ジャンル及びサブジャンルから構成される。楽器のタクソノミーは、管楽器、弦楽器、打楽器、発声などの楽器の種類への分割である。厳密には、階層の利用は値の間の半順序関係の定式化を可能にするが、それの値は等価性、相違性及び集合所属性のみを反映している。この半順序は、値に課せられた類似度として利用することが可能である。
【００２６】
「オーディナル」属性の値は、等価性、相違性及び集合所属性に加えて、順序構造を反映している。この順序は、ある値と他の値との大小関係（その差はわからないが）を推論するのに利用可能である。一例として、「大変遅い（ラルギッシモ、約４０ｂｐｍ）」から「大変速い（プレスティッシモ、２０８ｂｐｍ以上）」までのそれのテンポマーキングにグループ化された楽曲のグローバルテンポがあげられる。
【００２７】
「ニューメリカル」属性の値は、標準単位と一意的なゼロの点により拡大された順序構造を反映している。これら２つは、１つの値が他の値と加法的及び乗法的な意味においてどれだけ異なっているか推論できることを可能にする。この属性は、整数ドメインから値をとり、音楽コレクションにより決定されるような極値（すなわち、最大値と最小値）を有する。例として、１分あたりのビート数で表される楽曲演奏のグローバルテンポ、秒単位での楽曲の時間、あるいは楽曲が記録またはリリースされた年があげられる。
【００２８】
「コンポジット」属性は、その他の属性ドメインからの値の列挙として最も良く表される楽曲の特徴に対し用意される。例として、参加ミュージシャンや使用されているインスツルメンテーションのリストがあげられる。
【００２９】
制約は、ある形式によるそれらの引数を受け取る必要がある。当然、それらは、プレイリストの楽曲間の関係を表している。それらの一部は、楽曲の属性に対する基本的制約として定義することが可能であり（例えば、ジャンル、メインアーティスト、テンポなど）、他のものは、プレイリストの構成に関するグローバルシーケンスの制約としてみなすことができる。後者の典型例は、プレイリストに含まれるべき所望のレベルの規制や音楽多様性を表す。多様性の制約は、（連続した）楽曲が異なる演奏者、ジャンルなどからのものであるべきという制限により表現することが可能である。規制の制約は、ある楽曲の属性値（例えば、所与のアーティストなど）がプレイリストに十分に与えられるべきであるということを述べることにより表現することができる。
【００３０】
プレイリストの自動生成をＣＳＰとして定式化するとき、所望のプレイリストは、連続するプレイリストポジションの有限のシーケンスＳ＝ｓ１，ｓ２，．．．，ｓＭとすることができる。各変数ｓｉは、当該シーケンスの第ｉポジションを表す。楽曲の有限ドメインＤｉは、各ｓｉと関連付けされている。ｓｉは、Ｎ個の楽曲から構成される音楽コレクションから任意の楽曲を取得することができる。
【００３１】
楽曲は任意の順序付け及び固定されたＫ個の値の属性Ａｋ＝Ｖｉｋ（ｋ＝１，．．．，Ｋ）により表される。ここで、Ａｋは、属性の名称を表す。楽曲は、ベクトルｓｉ＝（Ｖｉ１，Ｖｉ２，．．．，ＶｉＫ）により表される。プレイリストのプロパティは、変数ｓｉ（１≦ｉ≦Ｍ）と対応する楽曲属性Ｖｉｋ（ｋ＝１，．．．，Ｋ）上で定義される制約である。記号の便宜上、Ｖｉｋ＝（ｖｉｋ１，ｖｉｋ２，．．．，ｖｉｋＬｉｋ）の値は、長さＬｉｋのベクトルである。大部分の属性に対し、それらは値のリストを表すため、コンポジット属性を除いてＬｉｋ＝１となる。
【００３２】
自動プレイリスト生成に有用と考えられるすべての制約が説明されるが、本発明はそれに限定されるものでない。大部分の制約は文献からとられたものである。各制約は、以下のエンティティにより記述される。
【００３３】
「名称（ｎａｍｅ）」は、参照のための制約の象徴的名称を与える。
【００３４】
制約の「項（ａｒｉｔｙ）」は、制約に合成されるプレイリストポジションの個数を示す。
【００３５】
「署名（ｓｉｇｎａｔｕｒｅ）」は、引数、そのタイプ、任意のパラメータ値及び必要な制限のリストを提供する。
【００３６】
「意味（ｍｅａｎｉｎｇ）」は、制約の目的を説明する。
【００３７】
「例（ｅｘａｍｐｌｅ）」は、プレイリストの生成のための制約の可能な使用例を列挙する。
【００３８】
基本的制約は、一項及び二項制約である。「一項楽曲固定（ｕｎａｒｙ  ｓｏｎｇ  ｆｉｘｅｄ）」制約は、所与のプレイリストポジションに、楽曲集合からの１つの楽曲が現れるべきであるということを述べている。その署名と意味は、
【００３９】
【表２】
2006510986.tif 000004
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、Ｓは楽曲集合である。一例として、第１の楽曲が音楽リスナーにより固定され、与えられるプレイリストがあげられる。
【００４０】
「一項ｅｑｕａｌ」制約は、第ｋ属性Ｖｉｋが所与の属性値ｖを有する楽曲が、所与のプレイリストポジションに現れるべきであることを述べる。その署名と意味は、
【００４１】
【表３】
2006510986.tif 000005
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示す。属性のタイプは、定義されたもの（すなわち、ノミナル、バイナリ、カテゴリカル、ニューメリカル、コンポジット）の何れかとすることができる。一例として、プレイリストの第ｉ楽曲は「ジャズ」であるか、第ｉ楽曲は「Ｐｒｉｎｃｅ」により演奏されるか、あるいは第ｉ楽曲はピアノ、ダブルベース及びドラムからなる所与のインスツルメンテーションを有するべきであるということを述べている。
【００４２】
「一項ｉｎｅｑｕａｌ」制約は、一項等価制約の単なる否定形である。それは、第ｋ属性Ｖｉｋが所与の属性値ｖを持たない楽曲が、所与のプレイリストポジションに現れるべきであることを述べている。その署名と意味は、
【００４３】
【表４】
2006510986.tif 000006
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示す。属性のタイプは、定義されたもの（すなわち、ノミナル、バイナリ、カテゴリカル、ニューメリカル、コンポジット）の何れかとすることができる。一例として、プレイリストの第ｉ楽曲は「ジャズ」でないか、第ｉ楽曲は「Ｐｒｉｎｃｅ」と異なる人により演奏されるか、あるいは第ｉ楽曲はピアノ、ダブルベース及びドラムとは異なる所与のインスツルメンテーションを有するべきであるということを述べている。
【００４４】
「一項ｇｒｅａｔｅｒ」制約は、第ｋ属性Ｖｉｋが所与の属性値ｖより大きい楽曲が、所与のプレイリストポジションに現れるべきであることを述べる。その署名と意味は、
【００４５】
【表５】
2006510986.tif 000007
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示す。明らかに、属性ドメインの値の間には順序関係が存在しなければならない。このことは、制約が序数的かつ数量的属性上に定義することができるということを意味する。一例として、プレイリストの第ｉ楽曲は１００ｂｐｍより速くなるべきでないか、あるいは第ｉ楽曲が１９９０年より後にリリースされたものであるべきであると述べている。
【００４６】
「一項ｇｒｅａｔｅｒ−ｅｑｕａｌ」制約は、一項ｅｑｕａｌと一項ｇｒｅａｔｅｒ制約を合成したものである。それは、第ｋ属性Ｖｉｋが所与の属性値ｖ以上である楽曲が、所与のプレイリストポジションに現れるべきであることを述べる。その署名と意味は、
【００４７】
【表６】
2006510986.tif 000008
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示す。明らかに、属性ドメインの値の間には順序関係が存在しなければならない。このことは、制約が序数的かつ数量的属性上に定義することができるということを意味する。一例として、プレイリストの第ｉ楽曲が１００ｂｐｍ以上のグローバルテンポを有するか、あるいは第ｉ楽曲が１９９０年以後にリリースされたものであるべきであると述べている。
【００４８】
「一項ｓｍａｌｌｅｒ」制約は、第ｋ属性Ｖｉｋが所与の属性値ｖ未満である楽曲が、所与のプレイリストポジションに現れるべきであることを述べる。その署名と意味は、
【００４９】
【表７】
2006510986.tif 000009
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示す。明らかに、属性ドメインの値の間には順序関係が存在しなければならない。このことは、制約が序数的かつ数量的属性上に定義することができるということを意味する。一例として、プレイリストの第ｉ楽曲が１００ｂｐｍより遅いものであるべきか、あるいは第ｉ楽曲が１９９０年より前にリリースされたものであるべきであると述べている。
【００５０】
「一項ｓｍａｌｌｅｒ−ｅｑｕａｌ」制約は、一項ｅｑｕａｌと一項ｓｍａｌｌｅｒ制約を合成したものである。それは、第ｋ属性Ｖｉｋが所与の属性値ｖ以下である楽曲が、所与のプレイリストポジションに現れるべきであることを述べる。その署名と意味は、
【００５１】
【表８】
2006510986.tif 000010
であり、ここで、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示す。明らかに、属性ドメインの値の間には順序関係が存在しなければならない。このことは、制約が序数的かつ数量的属性上に定義することができるということを意味する。一例として、プレイリストの第ｉ楽曲が１００ｂｐｍ以下のグローバルテンポを有するか、あるいは第ｉ楽曲が１９９０年以前にリリースされたものであるべきであると述べている。
【００５２】
「一項ａｍｏｎｇ」制約は、第ｋ属性Ｖｉｋの値が値の集合ｖａｌｓ＝｛ｖ１，．．．，ｖｐ｝の要素である楽曲が、所与のプレイリストポジションに現れるべきであるということを述べている。その署名及び意味は、
【００５３】
【表９】
2006510986.tif 000011
であり、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示し、ｖａｌｓ＝｛ｖ１，．．．，ｖｐ｝は属性値の集合を示す。この制約は、任意のタイプの属性に対し指定することが可能である。一例として、プレイリストの第ｉ楽曲は「ジャズ」または「ポップス」であるべきであるか、あるいは第ｉ楽曲は「Ｐｒｉｎｃｅ」、「Ｊａｍｅｓ  Ｂｒｏｗｎ」または「Ｍｉｃｈａｅｌ  Ｊａｃｋｓｏｎ」により演奏されるべきであるということを述べている。
【００５４】
「一項ｒａｎｇｅ」制約は、第ｋ属性Ｖｉｋの値が整数値ｖからｗまでの範囲内にある楽曲が、所与のプレイリストポジションに現れるべきであることを述べている。その署名及び意味は、
【００５５】
【表１０】
2006510986.tif 000012
であり、ｉはプレイリストのポジションを参照する整数のインデックスであり、ｋは楽曲ｓｉの第ｋ属性を示し、ｖとｗはｗ＞ｖである２つの属性値を示す。この制約は、序数的かつ数量的属性にのみ指定することが可能である。一例として、プレイリストの第ｉ楽曲は１０８〜１２０ｂｐｍの範囲内のテンポを有するべきであり（すなわち、適度な「アンダンテ」のテンポカテゴリ）、あるいは第ｉ楽曲は１９７０年代（１９７０〜１９７９）にリリースされたものであるべきであるということを述べている。
【００５６】
「二項ｉｄｅｎｔｉｃａｌ」制約は、相異なる２つのプレイリストポジションｉとｊに割当てられた楽曲が同一のものであるべきであるということを述べている。その署名及び意味は、
【００５７】
【表１１】
2006510986.tif 000013
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表す。一例は、プレイリストの最初と最後の楽曲が同じものであるべきであるというものである。
【００５８】
「二項ｄｉｆｆｅｒｅｎｔ」制約は、二項ｉｄｅｎｔｉｃａｌ制約の否定形である。それは、相異なる２つのプレイリストポジションに現れる楽曲が異なるものであるべきであるということを述べている。その署名及び意味は、
【００５９】
【表１２】
2006510986.tif 000014
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表す。直接的な例として、プレイリストの最初の２つの楽曲が異なるものであるべきであるというものである。
【００６０】
「二項ｕｑｕａｌ」制約は、ポジションｉとｊにおける楽曲の第ｋ属性の値が等しいものであるべきであるということを述べている。その署名及び意味は、
【００６１】
【表１３】
2006510986.tif 000015
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表す。一例は、最初と最後の楽曲が同じジャンル（またはアルバム）のものであるべきか、あるいは同じアーティストにより演奏されたものであるべきかというものである。
【００６２】
「二項ｉｎｅｑｕａｌ」制約は、二項ｅｑｕａｌ制約の否定形である。それは、２つのプレイリストポジションに現れる楽曲の第ｋ属性の値がことなるものであるべきであるということを述べている。その署名及び意味は、
【００６３】
【表１４】
2006510986.tif 000016
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表し、ｋは楽曲ｓｉとｓｊの第ｋ属性を参照している。一例は、最初と最後の楽曲が異なるジャンルに属するべきか、あるいは異なるアーティストにより演奏されるべきであったかというものである。
【００６４】
「二項ｓｍａｌｌｅｒ」制約は、１つのプレイリストポジションに現れる楽曲の第ｋ属性の値が他のプレイリストポジションのものより小さいものであるべきであるということを述べている。その署名及び意味は、
【００６５】
【表１５】
2006510986.tif 000017
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表し、ｋは楽曲ｓｉとｓｊの第ｋ属性を参照している。一例は、第１楽曲のテンポが第２楽曲より遅いものであるべきであるというものである。
【００６６】
「二項ｅｑｕａｌ−ａｍｏｎｇ」制約は、２つのプレイリストポジションに現れる楽曲の第ｋ属性の値が等しく、値の集合の要素であるべきであるということを述べている。その署名及び意味は、
【００６７】
【表１６】
2006510986.tif 000018
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表し、ｋは楽曲ｓｉとｓｊの第ｋ属性を参照し、ｖａｌｓ＝｛ｖ１，．．．，ｖｐ｝は属性値の集合を示す。一例は、プレイリストは同じジャンル、「テクノ」、「ダンス」または「ハウス」の２つの楽曲から開始されるべきであるというものである。
【００６８】
「二項ｓａｍｅ−ｇｒｏｕｐ」制約は、２つのプレイリストポジションに現れる楽曲の第ｋ属性の値が同一の値の集合の要素であるべきであるということを述べている。その署名及び意味は、
【００６９】
【表１７】
2006510986.tif 000019
であり、ｉとｊはプレイリストのポジションを参照する整数インデックスを表し、ｋは楽曲ｓｉとｓｊの第ｋ属性を参照し、ｖａｌｓ＝｛ｖ１，．．．，ｖｐ｝は属性値の集合を示す。一例は、プレイリストは、「ダンス」、「テクノ」及び「ハウス」ジャンルから選択された２つの楽曲から開始されるべきであるというものである。
【００７０】
グローバル制約は、他の（基本）制約の集合を包含する制約を表す。言い換えると、いくつかのグローバル制約は、同一の基本制約のネットワークとしてモデル化することができる。「グローバルｓｕｍ」制約は、プレイリストポジションの集合に現れる楽曲の第ｋ属性の値の和が、所与の値ｖ１より小さくなく、かつ所与の値ｖ２を超えるべきでないということを述べている。その署名及び意味は、
【００７１】
【表１８】
2006510986.tif 000020
であり、
【００７２】
【数１】
2006510986.tif 000021
はプレイリストのポジションを参照する整数インデックスの集合を表し、ｖ１とｖ２はそれぞれ和の下限と上限を参照する整数値を表す。この制約は、数量的属性にのみ利用可能である。この制約の一例は、プレイリストの合計時間が聞くことを楽しむ時間全体より長いものであるべきでないという要件である。
【００７３】
グローバル「ａｌｌ  ｓｏｎｇ  ｄｉｆｆｅｒｅｎｔ」制約は、プレイリストポジションの集合に割当てられた楽曲が対ごとに異なるものであるべきであるということを述べている。この制約は、実質的には、すべての可能な対ごとのプレイリストポジションに対する二項ｄｉｆｆｅｒｅｎｔ制約を結合したものである。すべてのプレイリストポジションが関係する場合、それはＭ（Ｍ−１）/２個の制約となる。その署名及び意味は、
【００７４】
【表１９】
2006510986.tif 000022
であり、
【００７５】
【数２】
2006510986.tif 000023
はプレイリストのポジションを参照する整数インデックスの集合を表す。この制約の一例は、プレイリストのすべての楽曲が異なるものであるべきという要件であり、些細な要求であるかもしれない。
【００７６】
グローバル「ａｌｌ  ａｔｔｒｉｂｕｔｅ  ｄｉｆｆｅｒｅｎｔ」制約は、プレイリストポジションの所与の集合に現れる楽曲の第ｋ属性の値が対ごとに異なるべきであるということを述べている。その署名及び意味は、
【００７７】
【表２０】
2006510986.tif 000024
であり、
【００７８】
【数３】
2006510986.tif 000025
はプレイリストのポジションを参照する整数インデックスの集合を表し、ｋは楽曲ｓｉとｓｊの第ｋ属性を参照している。この制約の一例は、プレイリストの楽曲のすべての主演奏者またはすべての作曲家が異なるべきであるという要件である。
【００７９】
グローバル「ａｌｌ  ａｔｔｒｉｂｕｔｅ  ｅｑｕａｌ」制約は、プレイリストポジションの所与の集合に現れる楽曲の第ｋ属性の値がすべて等しいものであるべきであるということを述べている。その署名及び意味は、
【００８０】
【表２１】
2006510986.tif 000026
であり、
【００８１】
【数４】
2006510986.tif 000027
はプレイリストのポジションを参照する整数インデックスの集合を表し、ｋは楽曲ｓｉとｓｊの第ｋ属性を参照している。この制約の一例は、プレイリストのすべての楽曲が同じジャンルに属しているべきか、同じアーティストにより演奏されているべきか、あるいは同じアルバムからとられたものであるべきかという要件である。
【００８２】
「グローバルｍｉｎｉｍｕｍ」制約は、プレイリストポジションの所与の集合に現れる楽曲の第ｋ属性の値の最小値が所与の値と等しいものとなるべきであるということを述べている。その署名及び意味は、
【００８３】
【表２２】
2006510986.tif 000028
であり、
【００８４】
【数５】
2006510986.tif 000029
はプレイリストのポジションを参照する整数インデックスの集合を表し、ｋは楽曲の第ｋ属性を参照し、ｖは要求される最小値である。一例は、プレイリストの楽曲のグローバルテンポが９０ｂｐｍ以上であるべきであるというものである。
【００８５】
「グローバルｍａｘｉｍｕｍ」制約は、プレイリストポジションの所与の集合に現れる楽曲の第ｋ属性の値の最大値が所与の値と等しいものとなるべきであるということを述べている。その署名及び意味は、
【００８６】
【表２３】
2006510986.tif 000030
であり、
【００８７】
【数６】
2006510986.tif 000031
はプレイリストのポジションを参照する整数インデックスの集合を表し、ｋは楽曲の第ｋ属性を参照し、ｖは要求される最大値である。一例は、プレイリストの楽曲のグローバルテンポが１２０ｂｐｍ以下であるべきであるというものである。
【００８８】
グローバル「ａｌｌ  ａｔｔｒｉｂｕｔｅ  ｒａｎｇｅ」制約は、プレイリストポジションの所与の集合に現れる楽曲の第ｋ属性の値が指定された範囲内にあるべきであるということを述べている。その署名及び意味は、
【００８９】
【表２４】
2006510986.tif 000032
であり、Ｉはプレイリストポジションを参照する整数インデックスの集合
【００９０】
【数７】
2006510986.tif 000033
であり、ｋは第ｋ属性（１≦ｋ≦Ｋ）を示し、Ｔ１とＴ２はそれぞれ下位と上位の閾値を示す。一例は、プレイリストの楽曲が１９７０年代（１９７０〜１９７９）にすべてリリースされているべきであるというものである。
【００９１】
グローバル「ｓｕｃｃｅｓｓｉｖｅ  ａｔｔｒｉｂｕｔｅ  ｓｉｍｉｌａｒｉｔｙ」制約は、ｉからｊまでの範囲の任意の２つの連続するプレイリストポジションに割当てられた２つの楽曲の第ｋ属性の値がある点に関して「類似」（しかし、類似し過ぎてはいない）したものであるべきであるということを述べている。その署名及び意味は、
【００９２】
【表２５】
2006510986.tif 000034
であり、ｉとｊ（ｉ＜ｊ）はプレイリストのポジションを参照する整数インデックスを表し、Ｔ１とＴ２はそれぞれ下位と上位の類似性閾値を表し、ｆ（ｖ，ｗ）は属性値類似性関数を表す。この関数ｆ（ｖ，ｗ）はまた二項述語として表現することが可能である。
【００９３】
タイトル、人物の名前、音楽ジャンルなどのノミナル、バイナリ、カテゴリカル及びオーディナル属性に対し、属性値類似性ｆ（ｖ，ｗ）は、属性値が同一である場合には１、異なる場合には０となる。概念的階層の構造と当該階層の２つの値の相対位置を利用して、タクソノミカル属性の類似度を定義することが可能である。
【００９４】
１分あたりのビート数によるグローバルテンポ、リリース年、アンサンブルの強度などの数量的属性に対し、属性値類似性は、数量的属性ドメインのトータルスパンと絶対値との比を１から引いたものとすることができる。より正確には、
【００９５】
【数８】
2006510986.tif 000035
であり、Ｒは対応する属性がとりうる最小値（上界）と最大値（下界）の差を表す。しかしながら、他の属性値類似性関数もまた定義可能である。この制約の一例は、プレイリストの２つの連続する楽曲が、指定された範囲内のリリース年またはグローバルテンポを有するべきであるという要件である。
【００９６】
グローバル「ｓｕｃｃｅｓｓｉｖｅ  ｓｏｎｇ  ｓｉｍｉｌａｒｉｔｙ」制約は、ｉからｊまでの範囲の任意の連続する２つのプレイリストポジションに割当てられた２つの楽曲の第ｋ属性の値が、あるグローバルな点に関して「類似」（しかし、類似し過ぎてはいない）したものであるべきであるということを述べている。その署名及び意味は、
【００９７】
【表２６】
2006510986.tif 000036
であり、ｉとｊ（ｉ＜ｊ）はプレイリストのポジションを参照する整数インデックスを表し、Ｔ１とＴ２はそれぞれ下位と上位の類似性閾値を表し、Ｆ（ｓｉ，ｓｊ）は楽曲類似性関数を表す。
【００９８】
楽曲類似性関数は、すべての属性値類似度の加重和から構成することが可能である。プレイリストポジションｓｉとｓｊの間の楽曲類似性Ｆ（ｓｉ，ｓｊ）は、関係するすべての属性値類似度の正規化された加重和として定義することが可能である。その値は０から１までの範囲内にある。より正確には、
【００９９】
【数９】
2006510986.tif 000037
であり、Ｋは属性の個数であり、Ｌｉｋは属性Ａｋの値の個数であり、ｓ（，ｓｖｉｋｌ，ｖｊｋｌ）は楽曲（またはプレイリストポジション）ｓｉとｓｊとの間の属性Ａｋの属性値類似度を示し、ウェートｗｉｋｌは属性値の相対重要度を表す。
【０１００】
類似度は、数学的な距離の意味での距離ではない。なぜなら、それは３つの距離に関する公理の２つを満たしていないからである。しかしながら、すべての楽曲に対して、何れの楽曲とそれ自身との類似度は同じであり、可能なものの中の最大値となる（すなわち、
Ｆ（ｓｉ，ｓｊ）≦Ｆ（ｓｉ，ｓｉ）＝Ｆ（ｓｊ，ｓｊ）＝１
となる）。これは、楽曲が他の楽曲と間違われる可能性は少ないため、自明であろう。また、各楽曲は自らのウェート集合を有するため、類似度が非対称性を有する（すなわち、
Ｆ（ｓｉ，ｓｊ）≠Ｆ（ｓｊ，ｓｉ）
となる）ことに注意すべきである。類似度の非対称性は、ある文脈では楽曲ｓｉが楽曲ｓｊと類似度が高くなるが、他の文脈ではそうでもないという観察結果を表したものである。それは、楽曲が比較される順序と基準点として機能する楽曲とにより生成することが可能である。基準点の選択は、類似度計算にあまり関係しない他の楽曲の一部でない属性値を生成する。リスナーにより知られた音楽が、そのような基準点として機能するようにしてもよい。このとき例えば、比較的知られていないアーティストの音楽はよく知られているアーティストの音楽と極めて類似していると判断されるかもしれず、逆の判断は真でないかもしれない。最後に、三角不等式、すなわち、
Ｆ（ｓｉ，ｓｊ）＋Ｆ（ｓｊ，ｓｋ）≧Ｆ（ｓｉ，ｓｋ）
は、３つの楽曲の対ごとの類似度の比較において、属性の関連性の変化と多数の属性のノミナルな性質により、一般には成り立たない。
【０１０１】
他の数学的なものでない心理的類似度は、「コントラスト（ｃｏｎｔｒａｓｔ）」モデルと「プロダクトルール（ｐｒｏｄｕｃｔ  ｒｕｌｅ）」モデルに基づく。この制約の一例は、プレイリストにおいて互いに従うすべての楽曲が「コヒーレント（ｃｏｈｅｒｅｎｔ）」であるべきであるという要件である。
【０１０２】
「グローバルａｔｔｒｉｂｕｔｅ  ｃｏｕｎｔ」制約は、プレイリストポジションの選択された集合に対する第ｋ属性の異なる値の個数は、２つの整数値ａとｂの範囲内にあるべきであるということを述べている。その署名及び意味は、
【０１０３】
【表２７】
2006510986.tif 000038
であり、Ｉはプレイリストポジションを参照する整数インデックスの集合であり（すなわち、
【０１０４】
【数１０】
2006510986.tif 000039
である）、ｋは第ｋ属性（１≦ｋ≦Ｋ）を示し、ａとｂは許容される最小基数と最大基数である（０≦ａ≦ｂ≦Ｍ）。この制約は、任意の属性タイプに対して利用することが可能である。一例は、プレイリストが３つの異なるアルバムのみを用いて生成されるべきであるか、あるいはプレイリストが６人の主演奏者を含むべきであるかというものである。
【０１０５】
「グローバルｓｏｎｇ  ｃａｒｄｉｎａｌｉｔｙ」制約は、第ｋ属性の値ｖが所与の集合ｖａｌｓの要素となるプレイリストポジションの所与の集合における楽曲数が、２つの整数ａとｂの範囲内にあるべきであるということを述べる。その署名及び意味は、
【０１０６】
【表２８】
2006510986.tif 000040
であり、
【０１０７】
【数１１】
2006510986.tif 000041
はプレイリストポジションを参照する整数インデックスの集合であり、ｖａｌｓ＝｛ｖ１，．．．，ｖｐ｝は属性値の集合を示し、ａとｂはそれぞれ許容される最小基数と最大基数を示す（０≦ａ≦ｂ≦Ｍ）。この制約は、任意の属性タイプに利用することが可能である。
【０１０８】
値の範囲が値の集合の代わりに引数としてわたされる数量的属性に対して、この制約の特別な変形が存在する。より正確には、
【０１０９】
【表２９】
2006510986.tif 000042
であり、
【０１１０】
【数１２】
2006510986.tif 000043
はプレイリストポジションを参照する整数インデックスの集合であり、ｖ１とｖ２はそれぞれ下位と上位の閾値を示し、ａとｂはそれぞれ許容される最小基数と最大基数を示す（０≦ａ≦ｂ≦Ｍ）。
【０１１１】
他の変形は、第ｋ属性の値が所与の値を有するある関係を有するプレイリストポジションの所与の集合における楽曲数を述べる。その署名及び意味は、
【０１１２】
【表３０】
2006510986.tif 000044
であり、
【０１１３】
【数１３】
2006510986.tif 000045
はプレイリストポジションを参照する整数インデックスの集合であり、ｋは第ｋ属性を示し（１≦ｋ≦Ｋ）を示し、ｒｅｌは関係演算子であり（すなわち、
【０１１４】
【数１４】
2006510986.tif 000046
である）、ａとｂはそれぞれ許容される最小基数と最大基数を示す（０≦ａ≦ｂ≦Ｍ）。一例は、主演奏者である「Ｍｉｌｅｓ  Ｄａｖｉｓ」が少なくとも２回かつ多くても４回だけ１０曲の楽曲からなるプレイリストにおいて登場すべきであるか、あるいは少なくとも６曲の楽曲が１９７０年代（１９７０〜１９７９）にリリースされたものであるべきであるというものである。
【０１１５】
「グローバルｓｏｎｇ  ｂａｌａｎｃｅ」制約は、第ｋ属性に対する値として最も出現する曲数と最も出現しない曲数との差がある値に限定されるべきであるということを述べている。その署名及び意味は、
【０１１６】
【表３１】
2006510986.tif 000047
であり、
【０１１７】
【数１５】
2006510986.tif 000048
はプレイリストポジションを参照する整数インデックスの集合であり、ｋは第ｋ属性を示し（１≦ｋ≦Ｋ）を示し、ａはバランス閾値（０≦ａ≦Ｍ）を示す。この制約は、任意の属性タイプに利用することが可能である。一例は、いくつのスタイルまたは何人の演奏者がプレイリストに含まれるべきか言うことなく、音楽スタイルと主演奏者とのバランスをとることである。
【０１１８】
ＣＳＰを解くため、変数に対する可能な値の割当てのすべての組み合わせの完全な列挙を含む空間において検索が行われる必要がある。この検索空間のサイズは、関係するすべての変数のドメインの直積に等しい。この場合、これはすべての可能なプレイリストを含む空間における検索を意味する。例えば、５００曲の楽曲の音楽コレクションから１０曲を保持するプレイリストを生成することを所望する場合、考慮されねばならないプレイリストの個数は、５００１０となる。
【０１１９】
本セクションは、ＣＳＰを解くための検索及び制約伝搬方法を与える。ＣＳＰで用いられる用語が、音楽領域の用語に置き換えられた。変数、値、領域及び解の代わりに、それぞれプレイリストポジション、楽曲、音楽コレクション及びコンシスタントなプレイリストが用いられた。与えられる大多数の検索方法は、発見的解法に頼り、行き止まりから回復するため記録をとりながら、部分的にコンシスタントなプレイリストがポジション単位に拡張されるバックトラッキングに関する変形である。検索方法の説明では、一項及び二項制約に関するプレイリストの生成は単に仮定される（バイナリＣＳＰ）。制約伝搬（ｃｏｎｓｔｒａｉｎｔ  ｐｒｏｐａｇａｔｉｏｎ）は、制約を満足せず、このため、コンシスタントなプレイリストの一部とすることができないコレクションからの楽曲を削除する方法のクラスである。これらの方法は、開始時の検索空間を減少させ、パフォーマンスを向上させるため検索方法においてそれらを関係させるための前処理段階として利用することが可能である。
【０１２０】
制約伝搬は、問題をより管理し易い比率に還元することに関する。コンシスタントなプレイリストの一部とはなりえない楽曲は削除され、空いているプレイリストのポジションに対するドメインの縮小及び制約の強化をもたらす。解に実際には寄与しない楽曲を考慮する必要がなくなることにより、検索パフォーマンスを向上させることが可能である。これら楽曲の削除は興味のある何れのプレイリストを削除するものでないということは明らかである。
【０１２１】
制約伝搬量は、実現されるコンシスタンシーのレベルにより特徴付けされる。対象となる問題がもたらされうるコンシスタンシーには様々なレベルがあり、問題におけるコンシスタンシーのレベルを確立するアルゴリズムには様々なものがある。
【０１２２】
プレイリスト生成問題は、空のプレイリストポジションのすべての楽曲に対してすべての一項制約が成り立つ場合、ノードコンシスタント（ｎｏｄｅ−ｃｏｎｓｉｓｔｅｎｔ）となる。ある問題がノードコンシスタンシーを欠く場合、これは、少なくとも１つの楽曲が一項制約を満たしていないことを意味する。任意のポジションにおける当該楽曲の以降の利用は、常に即時の違反をもたらす。
【０１２３】
プレイリスト生成問題は、ノードコンシスタントであり、かつ任意のプレイリストポジションの任意の候補楽曲に対し、当該ポジションを参照する任意の二項制約が満足されうる場合、アークコンシスタント（ａｒｃ−ｃｏｎｓｉｓｔｅｎｔ）となる。アークコンシスタンシーが欠落し、二項制約がある楽曲が２つのポジションに現れるよう制限する場合、これらのポジションにおける当該楽曲の配置は、常に即時の違反を招くであろう。ある問題は、まずそれをノードコンシスタントとし、その後に各二項制約を経由し、制約に違反する両方のポジションに対しすべての楽曲を削除することにより、アークコンシスタントとすることができる。与えられたポジションの楽曲が削除された場合、当該ポジションを参照する他の制約が再検討される必要がある。
【０１２４】
二項制約では、楽曲の削除は、推論規則を利用することにより効率的に実現することが可能である。例えば、二項ｓｍａｌｌｅｒ制約Ｖｉｋ＜Ｖｊｋ（ただし、ＶｉｋとＶｊｋはそれぞれ、ポジションｓｉとｓｊの第ｋ整数（数量的）属性である）に対し、この削除は以下のように定式化することができる。
【０１２５】
【数１６】
2006510986.tif 000049
ただし、Ｚは整数の集合である。ここで、ポジションｓｊの楽曲は、ＶｊｋのドメインがＶｉｋのドメインの最小値に１を加えた値と等しい最小値を有するように削除される。ポジションｓｉの楽曲は、Ｖｉｋのドメインが１からＶｉｋのドメインの最大値を引いた値に等しい最大値を有するように削除される。
【０１２６】
アークコンシスタンシーのより弱い形式は、ディレクショナルアークコンシスタンシー（ｄｉｒｅｃｔｉｏｎａｌ  ａｒｃ  ｃｏｎｓｉｓｔｅｎｃｙ）として知られる。ある問題は、与えられた順序付けに従う任意のプレイリストポジションの任意の候補楽曲に対し、両方のポジションを参照する何れの二項制約に違反することなく、順序付けにおける先行する何れのポジションに対し候補楽曲が存在する場合、ディレクショナルアークコンシスタントとなる。
【０１２７】
コンシスタンシーのレベルは、与えられた部分的コンシスタントなプレイリストがどの程度まで拡張可能であるか示す。１つのポジションのみがアークコンシスタントプレイリストの楽曲を占有する場合、この部分的プレイリストは常に他のポジション上の追加的楽曲に拡張することが可能である。より多くのポジションが含まれる場合、ｋ−コンシスタンシーのコンセプトに到達する。
【０１２８】
プレイリスト生成問題は、ｋ−１個のポジションの楽曲を有する任意の部分的コンシスタントプレイリストが、残りの空のポジションの何れかに楽曲を割当てることにより拡張することが可能である。それは、１−コンシスタント、２−コンシスタント、ｋ−コンシスタントまでである場合、強いｋ−コンシスタントでさえある。ノードコンシスタンシーは強い１−コンシスタントを意味し、アークコンシスタントは強い２−コンシスタントを意味する。
【０１２９】
対象となる問題がｋ−コンシスタントとすることが可能である場合、これは必ずしも、コンシスタントなプレイリストが存在することを意味するものでない。それが強いｋ−コンシスタントである場合、ｋ個のポジションの何れかの集合には検索やバックトラッキングの必要なく任意の順序で楽曲を割当てることが可能である。プレイリストが充填されるべきＭ個のポジションを有し、かつ当該問題が強いＭ−コンシスタントとすることが可能である場合、検索することなくプレイリストを生成することが可能となる。しかしながら、大きなｋに対する（強い）ｋ−コンシスタンシーを用いる実際的効果は限界的なものとなる。なぜなら、所与の問題を当該コンシスタンシーレベルに帰着する努力は指数的なものとなるためである。
【０１３０】
基本制約と対照的に、グローバル制約は伝搬させることが困難である。しかしながら、アークコンシスタンシーの概念は、非二項制約（グローバル）制約に拡張することが可能である。プレイリスト生成問題は、ある制約の任意のプレイリストポジションの任意の候補楽曲に対し、当該制約に違反することなく、制約のその他のポジションに対し楽曲が存在する場合、一般化アークコンシスタントとなる。アークコンシスタンシーを実現する標準的なアルゴリズムは、それらに一般化された形式を実現させるよう適応可能である。この問題点は、制約の希少性が増すに従い、還元が減少することである。従って、特別な伝搬アルゴリズムが、特定タイプのグローバル制約上で機能するよう構成される必要がある。
【０１３１】
バックトラッキングに基づかない直接的手法は、「生成及び検証」パラダイムである。このパラダイムでは、プレイリストのすべてのポジションには、システマティックに音楽コレクションからの楽曲が割当てられる。その後、このプレイリストがすべての制約を満足するか確認するため検証が行われる。このとき、すべての制約を満たす楽曲の最初の割当ては、コンシスタントなプレイリストである。さらなるプレイリストを検索することは、システマティックナ方法により生成及び検証方法を継続することにより単に実行される（すなわち、同一の割当てを実行することを回避することにより、あるいは違反したポジションの１つのみを変更することにより）。検索空間全体がすべての可能なコンシスタントプレイリストを検出するのに考慮される必要があるということは明らかである。
【０１３２】
より効率的な手法は、時間順バックトラッキング（ｃｈｒｏｎｏｌｏｇｉｃａｌ  ｂａｃｋｔｒａｃｋｉｎｇ）に基づくものである。この方法では、各プレイリストポジションには、１つずつ楽曲が割当てられる。制約に関連するすべてのポジションが楽曲を有するとすぐに、この部分的インスタンス化を用いて、当該制約の有効性がチェックされる。制約の１つが満たされない場合、ポジションへの直近の楽曲割当が元に戻され、当該ポジションに対する他の楽曲が選択されるバックトラッキング処理が実行される。その後、この調整されたインスタンス化は、制約有効性チェックに入力される。当該ポジションに対する他の楽曲が利用可能でない行き止まり状態になる場合、バックトラッキングは前のポジションのレベルでさらに追跡される。すべての制約を満たしながら、すべてのポジションが楽曲を有する場合、コンシスタントプレイリストが生成されている。他のコンシスタントプレイリストを検索することは、単に直近の楽曲割当てを元に戻し、同じバックトラッキング処理を継続することにより行われる。バックトラッキングすべきポジションが残っていないが、依然として制約違反が存在する場合、すべての制約を満たすコンシスタントプレイリストは存在しない。
【０１３３】
バックトラッキング検索は、サーチツリー探索とみなすことが可能である。このとき、ツリーのルートは、空のプレイリストを参照する。ツリーの第１レベルにあるノードは、１つのポジションに割当てられた楽曲を有するすべてのプレイリストを含む。第２レベルのノードは、２つのポジションに割当てられた楽曲を有するプレイリストを含む。以下同様とされる。ツリーのリーフは、すべてのポジションが占有されるすべての可能なプレイリストを含む。
【０１３４】
生成及び検証方法に関する効率性は、制約が部分的コンシスタントプレイリストにより満たされないとき、当該部分的プレイリストはさらには追跡されないため、検索空間の一部が削除されるという事実により明らかにされる。言い換えると、サブツリーはさらには探索はされない。なぜなら、この検索はツリーの他のブランチをとるためである。
【０１３５】
実際には、時間順バックトラッキングのランタイムコンプレクシティは、問題のサイズに関して依然として指数的である。このことは、検索ツリーの多過ぎるノードが以下の観察結果により訪問されていることを意味する。
【０１３６】
１．繰り返し、プレイリストの次のポジションと候補楽曲が任意の方法により選択される。オーダ発見的アプローチにより、詳細な検索を回避するため、ポジションと楽曲が選択される。
【０１３７】
２．制約違反は、それが発生するときのみ遅れて検出される。このことは、コンシスタントプレイリストが存在しないことの検出には、徹底的な検索を要するということを意味している。同一の制約の違反による繰り返される失敗は、何れの手段をとることなく起こる。「ルックアヘッド（ｌｏｏｋ−ａｈｅａｄ）スキーム」は、検索中に発生しうる制約違反を回避するため提案される。簡単には、これらのスキームは、制約に違反するポジションの候補楽曲を削除する。
【０１３８】
３．失敗の原因は検索空間の探索中には記録されず、このため、検索空間における異なる部分において同じ失敗が発生し（トラッシング（ｔｒａｓｈｉｎｇ）と呼ばれる）、余計な作業が生じることとなる。余計な作業を回避するため、「ルックバック（ｌｏｏｋ−ｂａｃｋ）スキーム」が提案される。簡単には、これらのスキームは失敗の原因を特定及び記憶し、これをバックトラッキングプロセスにおいて利用しようとするものである。
【０１３９】
次のプレイリストポジションが選択される順序は、バックトラッキングが必要であると結論付ける前に、詳細な検索を行うことを回避すべきである。直感的には、最重要ポジションがまず選択されるべきである。異なる問題特性に対しこの重要性を判断するため、いくつかの発見的アプローチが提案されてきた。ある発見的アプローチは、ポジションの順序が予め設定されている場合、静的アプローチと呼ばれる。他方、動的な発見的アプローチは、検索の現在状態に応じて順序を再調整する。いくつかの発見的アプローチが以下に与えられる。
・失敗第１原理（ｆａｉｌ  ｆｉｒｓｔ  ｐｒｉｎｃｉｐｌｅ）は、最小数の楽曲が利用可能なポジションをまず選択する。
・最小幅オーダリング（ｍｉｎｉｍｕｍ  ｗｉｄｔｈ  ｏｒｄｅｒｉｎｇ）は、以前にインスタンス化された最小数のポジションが従属するポジションをまず選択する（すなわち、結合制約）。
・最大基数オーダリング（ｍａｘｉｍｕｍ  ｃａｒｄｉｎａｌｉｔｙ  ｏｒｄｅｒｉｎｇ）は、最小数の以降のポジションが従属するポジションをまず選択する（すなわち、結合制約）。
・最小帯域幅オーダリング（ｍｉｎｉｍｕｍ  ｂａｎｄｗｉｄｔｈ  ｏｒｄｅｒｉｎｇ）は、制約を結合する互いに近接したポジションに配置する。
【０１４０】
適切な方法により次のポジションを選択するのに加えて、当該ポジションに対し最初に試行する適切な楽曲を選択することにより多くのものを取得することができる。ここでの滴せつな楽曲は、コンシスタントプレイリストを生成するのに「最も有望な」ものとして解釈されるべきである。「最小コンフリクトファースト（ｍｉｎｉｍｕｍ  ｃｏｎｆｌｉｃｔ  ｆｉｒｓｔ）」発見的アプローチは、プレイリストの他の空のポジションに対し最も多くの楽曲を残す現在ポジションに対して、楽曲を選択する。
【０１４１】
フォワードチェッキング（ｆｏｒｗａｒｄ  ｃｈｅｋｉｎｇ）は、バックトラッキングと同様の検索処理を用いる。それは、楽曲をプレイリストポジションに１つずつ割当て、関係する制約をチェックする。しかしながら、すべての空のプレイリストポジションに対し、部分的コンシスタントプレイリストに関する制約を満たす少なくとも１つの楽曲が存在することを保証する。これを確実にするため、楽曲がポジションに割当てられるごとに、残りの空のプレイリストポジションに対する候補楽曲を削除する必要がある。特に、制約伝搬により直近の楽曲割当てに関する何れかの制約に違反する楽曲は、ドメインから削除される必要がある。これらのドメインの１つが空になる場合、直近の楽曲割当ては拒絶されるであろう。そうでない場合、プレイリストが完成されるまで、次のプレイリストポジションに楽曲が割当てられるであろう。すべての楽曲が現在のポジションに対し不成功となった場合、バックトラキングと同様に前のポジションに戻る。
【０１４２】
フォワードチェッキングの制約伝搬段階では、空のプレイリストポジションに現れうる楽曲のみが、すでにポジションに割当てられている楽曲に対しチェックされる。パーシャルルックアヘッド（ｐａｒｔｉａｌ  ｌｏｏｋａｈｅａｄ）はさらに、固定された順序ですべての空のポジションに関する制約をチェックし、違反しているすべての楽曲を削除することにより、検索空間を縮小させる。ここで、任意の空のプレイリストポジションに対し、部分的コンシスタントプレイリストによる何れの制約にも違反しない少なくとも１つの楽曲が存在するが、すべての２つの空のポジションに対し楽曲ペアが存在することが保証される。しかしながら、制約伝搬は固定された順序で行われるため、任意の２つのプレイリストポジション間のコンシスタンシーの弱いバージョンのみが、ディレクショナルアークコンシスタンシーと呼ばれる。計算的により負荷の高いバージョンは、この順序を緩和し、アークコンシスタンシーを維持し、フルルックアヘッドと呼ばれる。
【０１４３】
行き止まりから回復するため前のプレイリストポジションに戻る代わりに、バックジャンピング（ｂａｃｋｊｕｍｐｉｎｇ）により、（一緒になって）行き止まりを招いたポジションにバックトラッキングする。行き止まりの状況では、制約に違反することなく現在のポジションに利用可能な楽曲はない。バックジャンピングは、現在のポジションにより制約に違反した楽曲をこれまでのすべてのポジションをまず収集する。その後、最も直近にインスタンス化されたポジションをバックトラッキングすべきものとして採用する。現在のポジションがすでに楽曲を保持しているが、バックトラッキングするのに用いられる場合、部分的コンシスタントプレイリストによりすべての制約を満たす少なくとも１つの楽曲が存在する。この場合、バックジャンピングは、通常のバックトラッキング処理を採用し、前のプレイリストポジションに戻る。
【０１４４】
バックジャンピングは、バックトラッキングすべき位置を計算するのみであるが、検索中に取得すべきものはさらにある。バックジャンピングに対する改良として、コンフリクトディレクティッドバックジャンピング（ｃｏｎｆｌｉｃｔ−ｄｉｒｅｃｔｅｄ  ｂａｃｋｊｕｍｐｉｎｇ）、バックチェッキング（ｂａｃｋｃｈｅｋｉｎｇ）及びバックマーキング（ｂａｃｋｍａｒｋｉｎｇ）はすべて、各ポジションに対してコンフリクト集合のすべてのコンフリクトポジションを維持するやや異なるアルゴリズムである。行き止まりの状況では、最も直近にインスタンス化されたポジションがバックトラッキングすべきものとしてとられる。さらに、制約違反に関する情報が欠落しないように、コンフリクト集合が結合される。
【０１４５】
バックジャンピングはまた、スキップされるポジションから構成されるコンシスタントプレイリストの一部をバックトラッキングし、それを忘れる傾向がある。「ダイナミックバックトラッキング（ｄｙｎａｍｉｃ  ｂａｃｋｔｒａｃｋｉｎｇ）」は、ポジションを再順序付けすることにより、バックトラッキングされるポジションに割当てられる楽曲を保持する。特に、バックトラッキングすべきポジションは、そうでない場合にはスキップされるポジションの終わりに実際には配置される。
【０１４６】
検索スキームと発見的アプローチの多様性は、プレイリストの生成に寄与するアルゴリズムにおける多数の選択を当然に導く。幸運なことに、多くの検索スキームと他の発見的アプローチは、直交している必要はないが、合成することが可能である。
【０１４７】
ある機会に対し１つのプレイリストが生成される必要があるだけでなく、複数の機会に対して多数のプレイリストが必要とされる。いくつかの例では、すべての制約を満足することが不可能であると判明することも考えられる。この点において、すべての制約が必ずしも「等しい重要度」を有する、すなわち、同一の優先度を有する必要はないということに着目することは価値がある。いわゆるハードな制約は、ソフトな制約では可能であるかもしれないが、犠牲とされることができず、このことは対象となる問題を緩和する。同様の方法は、０から１までの充足値において与えられたプレイリストがどの程度充足されるか表現することによるものである。このとき、与えられた制約の充足度は、各制約に対する個々の充足値のある組み合わせに等しくなる。
【０１４８】
図３を参照して、ジュークボックスシステム１０の本発明によるデータベース抽出システムの動作の図解的な例が説明される。この例は、ステップ３０２と３０４に示され、上述されたように、音楽コレクションがデータベースメモリ１３に格納されており、この音楽コレクションの各楽曲に対するメタデータがメモリ１４に格納されていると仮定する。その後、ジュークボックスシステム１０は、ステップ３０６において、何れかの入力装置１６を介しユーザからクエリに対する基準を受け取る。この例では、ユーザは不明確な表現を用いて、「約１時間の音楽」、「ロマンチックな夜用」、「ピアノによる」、「スローテンポな」、「同様のメロディー」、「及びフランス人のボーカルによる」などを要求する。このとき、ジュークボックスシステム１０は、ステップ３０８において、上記列挙された不明確な表現を基準、制約及び述語に変換する。この変換された不明確な表現はメモリ１４に格納されているメタデータに比較可能な情報形式となる。例えば、「約１時間の音楽」という表現は、「合計時間〜６０分」に変換される。「ロマンチックな夜用」という表現は、「テーマ＝愛」に変換される。「ピアノによる」という表現は、「楽器＝ピアノ」に変換される。「スローテンポな」という表現は、「テンポ＜８０ｂｐｍ」に変換される。「同様のメロディー」という表現は、「すべてのメロディーに対し、その距離間隔＜Ｋ」に変換される。「及びフランス人のボーカルによる」という表現は、「言語＝フランス語」に変換される。
【０１４９】
不明確な各表現が変換されると、ステップ３１０において、プロセッサ１２は既知の検索アルゴリズムを用いて、ユーザのクエリに合致する音楽に対しメモリ１４のメタデータを検索する。その後ステップ３１２において、プロセッサはジュークボックスにより再生可能な音楽リストを生成する。
【０１５０】
不明確な表現からの変換は、以下の方法により実行することが可能である。この例は、ユーザが当該時点で１つの制約を現在の制約ベースに追加することを仮定する。これは、追加的サポート及びユーザガイダンスによるダイアログにおいて実現される。従って、各表現は単一の制約に対応する。さらに、音楽ドメインにおけるコンセプト、属性及びそれらの相互関係を定義するデータモデルが生成されている。
【０１５１】
この変換は、各表現に対する２つの特徴、すなわち、（１）適切な制約の選択と、（２）適切な引数による制約のインスタンス化、に関する。制約はプレイリストのポジションの部分集合に課せられる関係としてみなすことができる。すなわち、それはこれらのポジションへの許容された楽曲の割当てを表す項の集合から構成される。それは、楽曲自体または楽曲の特定の属性（例えば、アーティスト、テンポ、スタイルなど）上に定義することが可能である。異なるタイプの制約の個数は限定的であり、それらの一部はデフォルトとすることが可能である。例えば、「ａｌｌ−ｄｉｆｆｅｒｅｎｃｅ」制約は、プレイリストのすべての楽曲が異なるものであるべきということを述べ、デフォルト制約の明らかな候補である。「同様の（ｓｉｍｉｌａｒ）」制約は、連続する楽曲は同様の特徴（例えば、同じアーティストまたはスタイルなど）を有するべきであるということを述べている。「カウント（ｃｏｕｎｔ）」制約は、特定の特徴（例えば、特定のアーティスト、スタイルまたはテンポ範囲など）を有する楽曲が十分に（与えられた限度内で）提供されるべきであるということを述べている。
【０１５２】
この表現は、フレーズストラクチャ文法を用いて構文解析される必要がある。各制約タイプは、適切な制約の選択が当該表現で用いられるワード及び文法形式（文法におけるターミナル）に依存するということを意味する自らの文法を有する。曖昧さが制約の引数と大きく関連する。それは異なる方法によるものである。表現中の通常の名詞及び従属節は、すでにある意味での曖昧さを有しうる。同一のオブジェクト（コンセプトと属性）に対する同義語は、それらに対し異なる名称を利用しながら、ユーザがデータモデルのオブジェクトを参照することを可能にするルックアップテーブルに維持される。これらの名称は表現から構文解析され、対応するオブジェクトが抽出される。「ロマンチックな夜用」などの従属節は、規則構造により分解される。
【０１５３】
形容詞やそれらの修飾語句を用いるとき、曖昧さが生じうる。大部分の形容詞は、反対の意味を有するペアとなっている（例えば、ゆっくり−速い、大声の−ソフトな、良い−悪いなど）。反対の意味を識別するブレークポイント（例えば、速いからゆっくり）などは任意である。修飾語句は、これら形容詞の意味に強弱を付けるよう機能する（例えば、「大変」、「とても」、「ほとんど」、「やや」など）。曖昧さはまた基数に関して生じうる。「たくさん」、「わずかな」、「いくつか」及び「約半分」などの量的表現の意味は、適切には定義されていない。
【０１５４】
この曖昧さを処理する方法は、既知のファジー変数、集合及び論理を用いることによりものである。その中心概念は、ファジー集合への所属性がメンバーシップ関数により０．０から１．０までの実数範囲で示されるということである。この関数は凸であり、確定されねばならない。補集合、和集合及び共通集合などの集合論による演算が、これらのメンバーシップ関数に対し行われる。ファジー集合を利用して、要素は集合に「多かれ少なかれ」割当てることが可能となる。ファジー集合は、メンバーシップ関数の詳細が任意であっても、数学的に信頼できる方法を用いて表現から意味を導出することを可能にする。
【０１５５】
不正確さや曖昧さ扱うため、（実）数の代わりにワードにおいて表現される値の範囲を有する言語変数が用いられる。言語変数は、凸関数により実現される各々がファジー変数である言語値または項の集合、ファジー変数がとりうる範囲となるドメイン、ドメイン範囲、言語変数を参照する項の構文解析または生成を行うための文法規則、及び各言語値に対し項を計算する意味に対する規則により特徴付けされる。その意味は、ファジー集合のメンバーシップ関数上で機能する修飾語句と連結詞（「〜と」、「〜でない」）に対する演算子を定義することによりアルゴリズム的に計算することが可能である。
【０１５６】
一例は、５０〜２５０ｂｐｍの１分あたりのビート数のドメインにおける「ゆっくり」や「速い」という言語値と「大変ゆっくり」「ややゆっくり」などのいくつかの修飾値を有する「テンポ」である。「大変」、「極めて」、「やや」などの修飾語は、図４に示されるような「大変ゆっくり」や「やや速い」などの表現に対する意味をこれらの機能上で機能させる。同様の例としては、１９４０〜２００２年までの年代ドメイン上の「昔の」、「最近の」、「新しい」などの値による「レコーディング年」や、数のドメイン上の「ない」、「わずかな」、「いくつか」、「ほとんど」及び「すべて」による基数があげられる。
【０１５７】
制約に対する引数の値を取得するため、ファジー集合をクリスプ（ｃｒｉｓｐ）する必要がある。これは、閾値Ｔを適用することにより行われる。閾値Ｔを有するファジー集合に属するようそのクリスプ集合ＡＴは、
【０１５８】
【数１７】
2006510986.tif 000050
により与えられる。ここで、ｆ（ｘ）はＡのメンバーシップ関数である。ここでの例では、Ｔ＝０．８を用いるとき、「大変ゆっくり」には５０〜６５ｂｐｍの範囲を、「やや速い」には１５２〜２５０ｂｐｍの範囲を与えている。
【０１５９】
本発明の実施例は、上記ステップの正確な順序に限定されるものでなく、いくつかのステップのタイミングは本発明の動作全体に影響を与えることなく交換可能であるということは理解されるであろう。さらに、「有する」という用語は、他の要素またはステップを排除するものでなく、「ある」という用語は複数存在することを排除するものでなく、単一のプロセッサまたは他のユニットが、請求項に記載されるユニットや回路のいくつかの機能を実現するものであってもよい。
【０１６０】
本発明は、データベースからデータを抽出する方法及び装置として開示された。複数のエンティティが第１メモリに格納され、格納されている各エンティティに関する情報が第２メモリに格納されている。少なくとも１つの不明確な表現の形式による基準が、格納されているエンティティからいくつかのエンティティを選択するためユーザから受け取られる。受け取られた基準は、格納されている情報において用いられる項に変換される。その後、変換された基準に基づくエンティティのシーケンスが選択される。
【図面の簡単な説明】
【０１６１】
【図１】図１は、本発明の実施例の教示が利用される一例となるシステムのブロック図を示す。
【図２】図２は、本発明の一実施例による制約問題として自動プレイリスト生成をモデル化する図である。
【図３】図３は、本発明の一実施例によるデータベースをクエリするための方法を示すフローチャートである。
【図４】図４は、本発明の一実施例による関連する値を有する言語変数の一例である「テンポ」を示す図である。
【図１】
2006510986.tif 000051
【図２】
2006510986.tif 000052
【図３】
2006510986.tif 000053
【図４】
2006510986.tif 000054
【国際調査報告】
2006510986.tif 000055
2006510986.tif 000056
2006510986.tif 000057
2006510986.tif 000058
2006510986.tif 000059