在音乐领域，音乐片段（incipits）是音乐作品的短小片段，常用于音乐数据库的检索。例如，Oskar Kolberg的音乐目录或国际音乐资料目录（RISM）就包含了大量的音乐片段。这些片段允许用户根据旋律和节奏等音乐标准来搜索音乐资料。本文将讨论如何通过旋律进行查询，以及如何优化这一过程。
音乐片段搜索面临的主要挑战是，相同的旋律可能以不同的调性书写，搜索引擎需要能够忽略调性差异，找到所有相关的结果。此外，搜索结果需要根据与查询旋律的相似度进行排序。目前，已有多种方法尝试解决这一问题，包括对音高序列进行对齐并计算相似度分数，以及在度量空间中计算距离。然而，这些方法的主要缺点是每次查询都需要遍历数据库中的所有记录，这在大量数据集上会导致性能不佳。
为了解决性能问题，可以在计算相似度之前先对数据进行预过滤。本文将介绍如何在RISM数据的搜索引擎中实现这一点。
在这种方法中，只考虑音程，即声音之间的距离，用半音表示。每个片段可以表示为n维笛卡尔空间中的一个向量，其中n是音程的数量。例如，某个旋律可以表示为一系列数字：4, -2, -2, 7, 9, -5, -2, -2, 4, -2, -2。两个旋律之间的相似度可以表示为代表这两个旋律的空间中点之间的距离。使用以下公式计算这个距离：
double distance = Math.sqrt(Math.pow(interval1 - queryInterval1, 2) + Math.pow(interval2 - queryInterval2, 2) + ...);
为了将相似度以百分比的形式表示（这对用户来说更易于理解），需要假设一个特定的任意距离等于0%，而距离为0等于100%。使用以下公式计算相似度：
double similarity = (100 / maxDistance) * (1 - distance / maxDistance);
在数据库中的每条记录上都需要进行这些计算，然后才能对结果进行排序。接下来，将展示如何在计算相似度和排序之前过滤数据集。
LSH算法将空间划分为更小的单元，这些单元可以用来预过滤数据，因为相似的旋律会落在同一个单元中。为了解释算法的工作原理，首先需要引入一些概念：空间、平面、平面组和LSH哈希。
空间是包含所有被描述为向量或点的片段的集合。空间的维数等于旋律中的音程数量。对于目的，使用1、2、3、4、5和6维空间。如果旋律有超过6个音程，只考虑前6个。
平面（或超平面）是一个比包围它的空间（环境空间）少一个维度的空间。它总是将高维空间分成两部分。下表应该可以澄清这个概念：
| 空间的维度数 | 平面的维度数 |
|---|---|
| 1（线） | 0（点） |
| 2（平面） | 1（线） |
| 3（空间） | 2（平面） |
| 4（4维超空间） | 3（空间） |
| 5（5维超空间） | 4（4维超空间） |
| 6（6维超空间） | 5（5维超空间） |
如果想要一个平面通过坐标系的中心，可以将其描述为一个单一的向量。然而，这种方法将有利于较小的音程——较大的音程会落入较大的“单元”中。为了使哈希分布相等，可以将平面描述为两个向量：第一个定义平面的“对齐”，第二个定义平移。
对于空间中的每个点，可以确定它位于平面的哪一侧。使用点积来计算它：
public static double DotProduct(Vector vector1, Vector vector2)
{
if (vector1.Length != vector2.Length)
throw new ArgumentException("Lengths do not match.");
var sum = 0d;
for (var i = 0; i < vector1.Length; i++)
{
sum += vector1[i] * vector2[i];
}
return sum;
}
算法的目标是生成固定数量的随机平面。然后，对于每个点（一个旋律），确定它与每个平面的关系。如果该点位于平面的一侧，写0，或者如果该点位于平面的另一侧，写1：
public long ComputeHash(Vector point)
{
long hash = 0;
long orderOfMagnitude = 1;
foreach (var plane in Planes)
{
var pointCopy = point.Clone();
if (plane is TranslatedVector translatedPlane) pointCopy = pointCopy.Translate(new Vector(translatedPlane.Translation).Invert());
hash += (GetSideOfAPlane(pointCopy, plane) ? 1 : 0) * orderOfMagnitude;
orderOfMagnitude *= 2;
}
return hash;
}
private bool GetSideOfAPlane(Vector point, Vector plane)
{
return Vector.DotProduct(point, plane) > 0;
}
可以将结果写成二进制数，如10010，或十进制数，如18。这是一个LSH哈希。注意，必须为每个维度数存储单独的哈希。不能只取一个高维空间，并将剩余的维度用零填充，因为零被视为完美的一致。
平面组是一个可以用来避免相似旋律意外落入错误单元的概念。创建几个平面组，并分别为每个组计算哈希，以便每个旋律有多个哈希。这是可选的，因为它可以提高搜索精度，但会降低性能。
在MySQL数据库上进行了实验。这是没有LSH优化的查询的执行计划。如所见，整个表被扫描，然后行被排序：
SELECT i.Id, i.MusicalNotation, i.Clef, i.KeySignature, i.TimeSignature, i.CaptionOrHeading, ms.ComposerName, ms.Id, i.TextIncipit, ms.Title, i.VoiceOrInstrument,
100 - (SQRT(POW(i.Interval1 - -8, 2) + POW(i.Interval2 - 5, 2) + POW(i.Interval3 - -7, 2) + POW(i.Interval4 - 5, 2) + POW(i.Interval5 - -7, 2) + POW(i.Interval6 - 2, 2))) * (100 / 12) as Relevance
from incipits i
inner join musicalsources ms on ms.id = i.MusicalSourceId
order by Relevance desc
LIMIT 100 OFFSET 0
现在添加了空间哈希过滤：
SELECT i.Id, i.MusicalNotation, i.Clef, i.KeySignature, i.TimeSignature, i.CaptionOrHeading, ms.ComposerName, ms.Id, i.TextIncipit, ms.Title, i.VoiceOrInstrument,
100 - (SQRT(POW(i.Interval1 - -8, 2) + POW(i.Interval2 - 5, 2) + POW(i.Interval3 - -7, 2) + POW(i.Interval4 - 5, 2) + POW(i.Interval5 - -7, 2) + POW(i.Interval6 - 2, 2))) * (100 / 12) as Relevance
from incipits i
inner join musicalsources ms on ms.id = i.MusicalSourceId
WHERE i.Hash6d = 78126898370
order by Relevance desc
LIMIT 100 OFFSET 0
执行计划如下：
注意LIMIT 100 OFFSET 0在任何查询中都没有提高性能，因为排序迫使所有行都被扫描。第二个查询中的排序更快，因为它操作的是预过滤的记录子集。
| 查询 | 音程数 | 维度数 | 平面数 | 无LSH [s] | 有LSH哈希 [s] | 有LSH哈希（索引列） [s] |
|---|---|---|---|---|---|---|
| 4 3 5 -1 | 4 | 3 | 5 | -1 | 5.44 | 4.84 |
| 4 3 5 -1 -4 | 5 | 10 | 5.44 | 5.14 | 7.20 | |
| 4 3 5 -1 | 4 | 20 | 5.46 | 4.31 | 3.48 | |
| 4 3 5 -1 -4 | 5 | 20 | 5.66 | 4.39 | 2.64 | |
| 4 3 5 -1 | 4 | 40 | 5.60 | 4.61 | 3.90 | |
| 4 3 5 -1 -4 | 5 | 40 | 5.87 | 4.75 | 2.20 |