6

我想存储大量（约数千个）字符串并能够使用通配符执行匹配。

例如，这是一个示例内容：

  • Folder1
  • Folder1/Folder2
  • Folder1/*
  • Folder1/Folder2/Folder3
  • Folder2/Folder*
  • */Folder4
  • */Fo*4

（每一行也有额外的数据，比如标签，但匹配只针对那个键）

这是我想与数据匹配的示例：

  • Folder1
  • Folder1/Folder2/Folder3
  • Folder3

（*这里是通配符，可以是不同的字符）

我天真地考虑将它存储在 MySQL 表中并%在运算符中使用通配符LIKE，但 MySQL 索引仅适用于通配符左侧的字符，在我的情况下它可以在任何地方（即%/Folder3）。

所以我正在寻找一个可以从PHP使用的快速解决方案。我是开放的：它可以是一个单独的服务器，一个使用正则表达式文件的 PHP 库，......

4

9 回答 9

1

您是否考虑过使用 MySQL 的正则表达式引擎？尝试这样的事情：

SELECT * FROM your_table WHERE your_query_string REGEXP pattern_column

这将返回带有您的查询字符串匹配的正则表达式键的行。我希望它比运行查询以提取所有数据并在 PHP 中进行匹配的性能更好。

更多信息在这里：http ://dev.mysql.com/doc/refman/5.1/en/regexp.html

于 2013-03-14T04:49:17.170 回答
0

如果您的字符串代表某种层次结构（就像在您的示例内容中一样），实际上不是“真实”文件，但您说您对替代解决方案持开放态度 - 为什么不考虑像基于文件的索引之类的东西？

  • 选择一个新目录，例如myindex
  • 使用字符串键作为位置和文件名为每个条目创建一个空文件myindex

现在您可以使用glob- 由于分层文件结构，glob 搜索应该比搜索所有数据库条目快得多。如果需要，您可以将结果与您的 MySQL 数据相匹配 - 由于您的 MySQL 索引在键上，此操作将非常快。

但是不要忘记更新MySQL 数据库中的结构myindex。INSERTUPDATEDELETE

这个解决方案只会在一个庞大的数据集（但不像@Kyle 提到的那样庞大）上竞争，它的层次结构相当深而不是宽。

编辑 对不起，只有当通配符在您的搜索词中而不是在存储的字符串本身中时，这才有效。

于 2013-02-27T15:38:30.977 回答
0

我建议将密钥及其相关的有效负载读入按字母数字顺序排列的二叉树表示。如果您的密钥不是非常“聚集”，那么您可以避免（稍微额外的）开销构建平衡树。您还可以避免任何树维护代码，因为如果我正确理解您的问题，数据将经常更改，重建树而不是添加/删除/更新节点是最简单的。读入树的开销类似于执行初始排序，并且遍历树以搜索您的值是直接的，并且比仅针对一堆字符串运行正则表达式更有效。您甚至可能会在处理它时发现，您在树中的通配符会导致一些快捷方式来修剪搜索空间。

于 2013-03-04T20:07:57.627 回答
0

数据库不是进行此类搜索的正确工具。您仍然可以使用数据库（任何数据库和任何结构）来存储字符串，但是您必须编写代码才能在内存中进行所有搜索。从数据库中加载所有字符串（几千个字符串真的没什么大不了的），缓存它们并在它们上运行你的搜索\匹配算法。

您可能必须自己编写算法代码，因为标准工具对于您想要实现的目标来说太过分了，并且无法保证它们能够准确地实现您所需要的。

我将构建基于通配符的字符串的正则表达式表示，并在您的输入上运行这些正则表达式。在正确使用正则表达式之前，您可能需要做一些工作，但这将是最快的方法。

于 2013-03-02T17:13:58.813 回答
0

您可能想在很短的时间内使用多核方法来解决该搜索，我建议使用 FPGA 进行搜索和匹配，但这可能是最难的方法，考虑使用 CUDA 的这篇文章，您可以进行搜索在 16 倍平时，在多核 CPU 系统中，您可以使用 posix 或计算机集群来完成这项工作（例如 MPI），您可以调用Gearman服务以使用高级算法运行搜索。

于 2013-02-26T01:20:03.903 回答
0

如果是我，我会两次存储关键字段......一次向前和一次反转（参见mysql的反向功能）。然后，您可以使用 left(main_field) 和 left(reversed_field) 搜索索引。如果字符串中间和开头有通配符（例如“*Folder1*Folder2”），它对您没有帮助，但是当您在开头或结尾有通配符时，它会帮助您。

例如，如果你想搜索 */Folder1 然后搜索 where left(reverse_field, 8) = '1redloF/'; 对于 Folder1/*/FolderX 搜索其中 left(reverse_field, 8) = 'XredloF/' 和 left(main_field, 8) = 'Folder1/'

于 2013-02-26T01:26:59.727 回答
0

由于通配符 (*) 在您的数据中而不是在您的查询中，我认为您应该从将数据分解为多个部分开始。您应该创建一个具有以下列的索引表：

dataGroup INT(11),
exactString varchar(100),
wildcardEnd varchar(100),
wildcardStart varchar(100),

如果你有像“Folder1/Folder2”这样的值，将其存储在“exactString”中，并将主数据表中的值的ID分配给上述索引表中的“dataGroup”。

如果您有像“Folder1/*”这样的值，请将“Folder1/”的值存储到“wildcardEnd”，然后再次将主表中值的 id 分配给上表中的“dataGroup”字段。

然后，您可以使用以下方法在查询中进行匹配：

indexTable.wildcardEnd = LEFT('Folder1/WhatAmILookingFor/Data', LENGTH(indexTable.wildcardEnd))

这会将搜索字符串 ('Folder1/WhatAmILookingFor/Data') 截断为“Folder1/”，然后将其与 wildcardEnd 字段匹配。我认为 mysql 足够聪明，不会对每一行进行截断，而是从第一个字符开始并将其与每一行匹配（使用 B-Tree 索引）。

像“*/Folder4”这样的值将进入“wildcardStart”字段但相反。引用 Missy Elliot 的话：“值得吗，让我来做吧，我放下我的东西，翻转它，然后翻转它”（http://www.youtube.com/watch?v=Ke1MoSkanS4）。所以在“wildcardStart”中存储一个“4redloF/”的值。然后像下面这样的 WHERE 将匹配行：

indexTable.wildcardStart = LEFT(REVERSE('Folder1/WhatAmILookingFor/Folder4'), LENGTH(indexTable.wildcardStart))

当然，您可以在应用程序逻辑中执行“REVERSE”。

现在关于棘手的部分。像“*/Fo*4”这样的东西应该分成两条记录：

# Record 1
dataGroup ==> id of "*/Fo*4" in data table
wildcardStart ==> oF/
wildcardEnd ==> /Fo

# Record 2
dataGroup ==> id of "*/Fo*4" in data table
wildcardStart ==> 4

现在，如果您匹配某些内容，则必须注意数据组的每个索引记录都会返回完整匹配，并且不会发生重叠。这也可以在 SQL 中解决，但超出了这个问题。

于 2013-02-28T10:40:27.477 回答
-1

我不建议对 MySQL 中的大量数据进行文本搜索。您需要一个数据库来存储数据，但就是这样。对于搜索，请使用以下搜索引擎：

这些服务将允许您在眨眼之间进行各种时髦的文本搜索（包括通配符）；-)

于 2013-02-27T18:03:23.187 回答
-1

如果你运行SELECT folder_col, count(*) FROM your_sample_table group by folder_col，你会得到重复的 folder_col 值（即 count(*) 大于 1）吗？

如果没有，这意味着您可以生成一个可以生成有效 sphinx 索引的 SQL（请参阅http://sphinxsearch.com/）。

于 2013-02-22T15:03:45.680 回答