python - 类似 '%term%' 搜索的算法

Question

假设我有一个数据库列 filepath 并且我想进行包含搜索，例如:

matches = []
for filepath in filepaths:
    if "mutan" in filepath.lower():
        matches.append(filepath)

有没有办法优化这个算法？我愿意存储辅助结构或其他方法，但可能有哪些实用方法可以做到这一点？

我唯一能想到的就是标记文件路径，这样我就有了类似的东西:

/my/new/File.jpg ==>
# 1 char
['e', 'g', 'f', 'i', 'j', 'm', 'l', '/', 'n', 'p', 'w', 'y', '.']
# 2 char
['/n', '/m', 'le', 'y/', 'w/', '/f', 'jp', 'ne', 'e.', 'il', 'fi', 'ew', 'my', '.j', 'pg']
# etc...

然后使用术语 I have 进行查找，看看它是否存在于那里，但是用每个字母标记一个词似乎需要很长时间才能完成，而且还会占用大量空间。还有其他方法吗？

Answer 1

一些常见的算法是 https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm 和 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm还有其他的。

根据您的搜索需要，您可能还想实现一个小型布隆过滤器，我们为每个可能要搜索的字符串使用 32 位掩码，设置位 1 表示 'a' 存在，位 2 表示 'b' 等. 这使我们能够快速消除完整的数据库行而不是搜索所有行。

为了更具体，我们需要知道您要针对什么进行优化，内存、CPU 等。如今，在高端 CPU 上，即使扫描几 Gb 也相当快。