作为项目的一部分，我和其他一些人目前正在研究 URL 分类器。我们试图实现的实际上非常简单:我们只需查看 URL 并找到其中出现的相关关键字并相应地对页面进行分类。
例如:如果 url 是:http://cnnworld/sports/abcd ，我们会将其归类到“体育”类别下
为实现这一点，我们有一个映射格式为:关键字 -> 类别的数据库
现在我们正在做的是，对于每个 URL，我们不断读取数据库中的所有数据项，并使用 String.find() 方法查看关键字是否出现在 URL 中。一旦找到，我们就会停止。
但是这种方法有一些问题，主要问题是:
(i) 我们的数据库非常大，这样的重复查询速度非常慢
(ii) 一个页面可能属于多个类别，我们的方法不处理这种情况。当然，确保这一点的一种简单方法是即使找到类别匹配项也继续查询数据库，但这只会让事情变得更慢。
我在考虑替代方案，想知道是否可以进行反向操作 - 解析 url，查找其中出现的单词，然后仅查询数据库中的这些单词。
一个朴素的算法将在 O( n^2 ) 中运行 - 查询数据库中出现在 url 中的所有子字符串。
我想知道是否有更好的方法来实现这一点。有任何想法吗 ？？提前谢谢你:)
最佳答案
在我们的商业分类器中，我们有一个包含 400 万个关键字的数据库 :) 我们还搜索 HTML 的正文，有多种方法可以解决这个问题:
- 使用 Aho-Corasick，我们使用了一种专门用于处理网页内容的改进算法，例如将:制表符、空格、\r、\n 视为空格，只有一个，因此两个空格将被视为一个空格, 并忽略小写/大写。
- 另一种选择是将所有关键字放在树中(例如 std::map)，以便搜索变得非常快，缺点是这会占用大量内存，但如果它在服务器上，你就不会感受一下。
关于string - URL 分类的模式匹配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10046178/