65.9K
CodeProject 正在变化。 阅读更多。
Home

使用局部敏感哈希在度量空间中搜索音乐开头

Ajcek84
starIconstarIconstarIconstarIconstarIcon

5.00/5 (7投票s)

2018年11月27日

BSD

6分钟阅读

viewsIcon

19088

使用局部敏感哈希算法提高音乐开头搜索的性能

源代码只能从 GIT 存储库下载，因为它超过 100MB，而 CodeProject 只允许 10MB。

前言

本文提出的思想已在我用于 RISM 目录的唱段搜索引擎中实现，该搜索引擎可在 此处找到。该项目使用了 ASP.NET Core、Entity Framework、Blazor、Knockout.js、Manufaktura Controls 和 MySQL 数据库。完整的源代码可以在 https://github.com/manufaktura-controls/rism 找到。您可以在我写的其他文章 此处 阅读有关该项目中使用的其他技术的介绍。

问题

许多乐谱目录，例如 Oskar Kolberg's Catalogue 或 Répertoire International des Sources Musicales (RISM) ，都包含唱段，即用乐谱写成的短乐句。这些乐句允许用户通过旋律和节奏等音乐标准搜索乐谱。

在本文中，我将讨论按旋律进行查询。此类搜索应满足的主要标准是

  • 搜索移调 - 同一旋律可以以不同的调编写，搜索引擎应查找结果而不考虑调，
  • 按相似度排序结果 - 所需旋律的变体必须出现在结果中，并按与查询的相似度排序。

在这一主题上已经尝试了各种方法，其中值得一提的是两种

这两种方法的主要缺点是每次查询都会遍历数据库中的所有记录。这会导致在大数据集上的性能不佳。Kolberg's Catalogue 不存在这个问题，因为数据集的大小相对较小。然而，Monochord Project 必须部署在多核系统上并使用并行处理。

解决这个问题的方法是在计算相似度之前预过滤数据。在本文中，我将解释我如何在 RISM 数据（http://musicalsources.org/）的搜索引擎中做到这一点。

在度量空间中搜索音乐唱段

在此方法中，我们仅考虑音程，即声音之间以半音表示的距离。每个唱段都可以表示为 n 维笛卡尔空间中的一个向量，其中 n 是音程的数量。例如，这段旋律

可以表示为数字序列：4, -2, -2, 7, 9, -5, -2, -2, 4, -2, -2。

两种旋律之间的相似度表示为代表这两种旋律的空间中点之间的距离。我们使用此公式计算

我们想计算与此旋律的相似度

该旋律表示为 4、2、2 的序列。我们只考虑查询中出现的音程的数量，因此两段旋律之间的距离是

为了将相似度表示为百分比（对用户来说更易读），我们必须假定一个特定的任意距离等于 0%，而距离为 0 等于 100%。我们根据以下公式计算相似度

如果我们假设最大距离为 12，则相似度得分为 52.8%。

这些计算必须在对结果进行排序之前对数据库中的每条记录都完成。现在我将展示如何在计算相似度和排序之前过滤数据集。

局部敏感哈希 (LSH)

LSH 算法将空间划分为比我们可以用来预过滤数据的小单元格，因为相似的旋律会落入同一个单元格。为了解释该算法的工作原理，我们首先需要介绍一些概念：空间、平面、平面组和 LSH 哈希。

空间是一个包含所有唱段的集合，这些唱段被描述为向量或点。空间的维度数等于旋律中音程的数量。在我的用途中，我使用 1、2、3、4、5 和 6 维空间。如果旋律有超过 6 个音程，我只考虑前 6 个。

平面（或超平面）是比其周围空间（环境空间）少一个维度的空间。它总是将较高维度的空间分成两部分。下表有助于阐明这一概念

空间维度数 平面维度数
1 (直线) 0 (点)
2 (平面) 1 (直线)
3 (空间) 2 (平面)
4 (四维超空间) 3 (空间)
5 (五维超空间) 4 (四维超空间)
6 (六维超空间) 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 [秒] 使用 LSH 哈希 [秒] 使用 LSH 哈希
在索引列上 [秒]
4 3 5 -1 4 10 5,44 4,84 5,48
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
-8 5 -7 5 -7 5 40 5,78 N/A 0,02
-8 5 -7 5 -7 2 6 40 5,93 N/A 0,17

可以看到，通过空间哈希预过滤数据在大多数情况下可以减少查询时间。在哈希列上应用索引可以大大减少大多数查询的查询时间，但有时会增加成本。当用户输入一个很少见的旋律时，会达到最佳效果。如果用户搜索常见的音程模式，如音阶或琶音，性能影响可能会更差，因为许多旋律共享相同的空间哈希。

© . All rights reserved.