Mah*_*hes 7 string algorithm search glob wildcard
我正在使用一个小型搜索引擎来显示具有完整路径的匹配文件名.而且重要的是我需要提供通配符(GLOB)搜索*.doc,*list*.xlx或者*timesheet*或者???.doc或类似的东西.
我找到一些相关的解决方案
在小于O(n)的范围内搜索与模式"abc:*:xyz"匹配的字符串
但我正在寻找有效的算法,可以在不到一秒的时间内找到百万个文件名中的匹配,因此比O(n)更好.
我正在考虑两阶段算法,子串数组(后缀数组+前缀数组)搜索第一阶段和正常RegEx搜索通过第一阶段第二阶段的结果.
任何帮助将不胜感激...
据我所知，对于广义全局搜索来说，没有比 O(n) 更好的方法了。
然而，对于前缀和后缀搜索的特殊情况，您可以自己创建排序索引来执行二分搜索，从而导致前缀和后缀搜索的 O(log n) 。前缀索引将根据第一个字符排序，然后是第二个字符，依此类推。后缀索引将根据最后一个字符排序，然后是倒数第二个字符，依此类推（反向字符串）。
我会按照您在帖子中建议的那样进行搜索，分两个阶段进行搜索，搜索前缀或后缀索引，然后使用由 glob 生成的正则表达式对第一阶段提供的简化列表进行强力搜索。
由于字符串长度比较比正则表达式更快，因此我还会预过滤 ???.doc 示例的最小匹配字符串长度或固定长度匹配字符串。
从原始帖子的声音来看，索引还需要引用每个条目的完整路径，以便您可以在找到最终结果后显示它。