0

例如我们有以下字符串。“披头士乐队 - 想象一下” 另外，我们在 PostgreSQL 中有一个庞大的艺术家姓名列表。

鉴于该字符串，我想使用我的数据库识别艺术家。

我正在寻找最优化、最快速的算法/技术来做到这一点。因此遍历数据库中的所有记录并查找子字符串是不适用的。

字符串可以是“想象 - 披头士”、“想象，披头士”。就像 Youtube 视频中的歌曲名称一样。

Solr、ElasticSearch 或其他技术在这里会有所帮助吗？会喜欢一些极客的建议。

4

2 回答 2

2

这个问题有两个部分。困难的部分是识别艺术家和标题。你有各种各样的变化：

  • 披头士乐队——想象一下
  • 披头士乐队——想象一下
  • 想象 - 披头士乐队
  • 披头士乐队，想象一下
  • 想象一下，披头士
  • 想象一下——披头士乐队

其他人也将包括专辑：

  • 想象 - 想象 - 披头士

如果您将这些作为随机的错误混杂，那么您将很难处理 - 将这些数据规范化为字段将需要一个“曲目名称”和“艺术家姓名”的数据库来尝试匹配，并且很多猜测。

我要做的是忽略整个混乱并将其扔给全文搜索引擎。

test=> select to_tsvector('simple', 'Beatles, The - Imagine');
           to_tsvector           
---------------------------------
 'beatles':1 'imagine':3 'the':2
(1 row)

test=> select to_tsvector('simple', 'Beatles, The - Imagine') @@ to_tsquery('simple', 'Beatles');
 ?column? 
----------
 t
(1 row)

如果您能够将其转换为字段分隔的规范化数据，您的搜索将变得更加强大，因为您可以使用setweight, ts_rank,tsvector连接||等对字段进行加权匹配。

于 2014-01-18T04:22:55.853 回答
0

原则上，如果数据库中的任何记录可能包含您的搜索字符串，那么您将不得不搜索数据库中的每条记录。

您可以做的是使用类似Rabin-Karp 算法的方法同时搜索许多相同长度的搜索字符串版本：“Beatles The”、“The Beatles”。如果您忽略空格和/或标点符号，那么您可能可以进一步减少传递次数：“The Beatles”、“Beatles, The”、“Beatles The”。如果只计算字母，克雷格·林格的答案中的所有例子都是相同的长度；您可以使用 Rabin-Karp 一次通过数据库找到所有这些匹配项

于 2014-01-18T11:07:46.537 回答