類似レコードの探索
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/02 09:30 UTC 版)
ハッシュ関数は、キーが似ているが全く同一ではない場合のレコード検索にも使える。この場合の入力は1つのキーか、似たようなキーを持つ巨大ファイル内の2つのレコードである。このためには、似たようなキーを与えられたとき、最大でも m しか違わないハッシュ値(m は小さい整数で例えば1か2)を生成するハッシュ関数を必要とする。このようなハッシュ関数を使って全レコードに関するハッシュテーブル T を構築すると、似たようなレコードは同じバケットか近いバケットに格納されることになる。すると各バケット T[i] について、-m から m の範囲の k で表されるバケット T[i+k] に格納されているレコード群を相互に比較すればよい。 この応用として声紋アルゴリズムと呼ばれる技法がある。これを使うと音声ファイルの巨大なコレクションから似たようなエントリを探すことができる(MusicBrainzの楽曲ラベリングサービスで使われている)。この場合のハッシュ関数は、ノイズやタイミングの違いや音量の違いといった差異をなるべく無視できるようなものであることが望ましい。
※この「類似レコードの探索」の解説は、「ハッシュ関数」の解説の一部です。
「類似レコードの探索」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。
- 類似レコードの探索のページへのリンク