PHP数组搜索优化

Question

这里是任务。我需要识别一个字符串是否包含某个城镇的名称。 换句话说 - 从一些文本中识别一个城镇。

我有一个需要搜索的文本输入和地理编码。 根据地理编码，从数据库中加载城镇列表。

现在，当前实现方式是我循环遍历这些城镇的列表，并尝试使用短路评估进行匹配。 就像这样：

if (stripos($text, $currentTown) !== false && 
    preg_match("#\b$currentTown\b#i", $text)) {
    // add town to recognized list
}

问题是我有一个英国城镇列表（约40,000个），循环需要花费相当长的时间。

所以我的问题是如何优化识别时间。也许数组中有一些高级搜索方法？

欢迎任何想法。

谢谢。

- Sergey Poskachey

---

这类似于DNA序列搜索问题。 - user703016

而解决方案是什么？ - Sergey Poskachey

SQL LIKE 操作比你的 PHP 代码片段更快吗？ - yent

正如你所想，一个有40,000个元素的数组可能不是最好的选择。我赞同使用数据库或服务解决方案的建议。 - Makita

说实话，我还没有考虑过这个解决方案。我需要彻底研究一下。为了匹配单词边界之间的城镇名称，需要使用RLIKE而不是LIKE。 - Sergey Poskachey

阅读MySQL FULLTEXT算法的相关资料。基本上，您需要维护一个包含城镇名称中所有单词哈希的列表，将字符串拆分为单词并将每个单词与该哈希列表进行查找。您需要进行第二次处理，以缩小可能匹配到的城镇列表（例如，包含_East_的字符串会生成相当多的命中）。 - TerryE

Answer 1

虽然我最初的选择是使用'MySQL全文搜索'，但我会尝试解决您的问题。我将从“最佳结果”开始尝试。

将所有城镇数据都保留为小写（或者至少在搜索时保持小写），并在搜索之前使用$text = strtolower($text);：这样您就可以使用strpos区分大小写搜索>不区分大小写搜索。为什么要烦恼preg_match();，因为你用stripos做的事情有99%是相同的。你可以跳过它。也许添加一些小检查，比如如果strlen($text) < 4就不要尝试搜索，因为它会产生可怕的结果。按长度排序数据（这很昂贵，所以只需执行一次并存储它），并跳过比输入短的当前城镇。按字母顺序排序数据，仅遍历与第一个字母匹配的部分（甚至是前两个字母）。可能，缓存结果/搜索。然后，您只需要在缓存中搜索，如果它能找到某一行（但缓存未命中会影响性能）。如果您有大型数据集，则PHP迭代器类可能会有所帮助。它可以加快遍历每个记录的过程。

- Tessmore