☰

高效搜索已排序文件

tag-icon • tag-icon command-line text-processing grep
高效搜索已排序文件

我有一个大文件，每行包含一个字符串。我希望能够快速确定文件中是否存在字符串。理想情况下，可以使用二进制砍伐型算法来完成此操作。

谷歌搜索后，我们发现look带有标志的命令-b承诺使用二分搜索算法来定位并输出所有以给定前缀开头的字符串。不幸的是，它似乎无法正常工作，并且对于我知道文件中存在的字符串返回空结果（等效搜索会正确返回这些结果grep）。

是否有人知道其他可以有效搜索此文件的实用程序或策略？

答案1

grep和之间有着本质的区别look：

除非另有明确说明，grep否则即使在行内某处也会找到模式。look手册页指出：

look — 显示线开始使用给定的字符串

我并不look经常使用它，但它在我刚刚尝试的一个简单的例子中确实运行良好。

答案2

也许回答得有点晚了：

Sgrep 将帮助您。

Sgrep（排序的 grep）在排序的输入文件中搜索与搜索关键字匹配的行并输出匹配的行。在搜索大文件时，sgrep 比传统的 Unix grep 快得多，但有明显的限制。

  • 所有输入文件必须是排序的常规文件。
  • 排序键必须从行首开始。
  • 搜索键仅匹配行的开头。
  • 不支持正则表达式。

您可以在这里下载源代码： https://sourceforge.net/projects/sgrep/?source=typ_redirect

以及此处的文件： http://sgrep.sourceforge.net/

其他方式：

我不知道文件有多大。也许你应该尝试并行：

https://stackoverflow.com/questions/9066609/fastest-possible-grep

我总是对大小 > 100GB 的文件进行 grep，效果很好。

答案3

您可以将文件哈希化为碎片，然后只 grep 您想要的部分：

for line in $(cat /usr/share/dict/american-english | tr '[:upper:]' '[:lower:]' | sort | uniq)
do
    prefix=$(echo $line | md5sum - | cut -c 1-2)
    mkdir -p $prefix
    echo $line | gzip >> $prefix/subwords
done

那么查找将如下所示：

    prefix=$(echo $word | md5sum - | cut -c 1-2)
    zgrep -m 1 -w word $prefix/subwords

这做了两件事：

  1. 读取和写入压缩文件。通常将负载放在 CPU 上（非常快）比放在磁盘上（非常慢）更快
  2. 为了得到大致相等的分布，你可以使用更短或更长的哈希值来减少每个部分的大小（但如果这样做，我建议使用嵌套子目录）

答案4

如果你想要的话真的快速（O(1) 快速）您可以构建一个哈希集进行查看。我找不到允许我将预构建的哈希集存储在文件中并对其进行探测的实现没有必须将整个文件读入内存，因此我自己动手。

构建哈希集（-b/ --build）：

./hashset.py --build string-list.txt strings.pyhashset

探测哈希集（-p/ --probe）：

./hashset.py --probe strings.pyhashset \
    'Is this string in my string list?' 'What about this one?'

…或者使用字符串在标准输入中查找：

printf '%s\n' 'Is this string in my string list?' 'What about this one?' |
./hashset.py --probe strings.pyhashset

如果您只对退出状态感兴趣，可以--probe使用-q/选项使输出安静：--quiet

if ./hashset.py --quiet --probe strings.pyhashset ...; then
    echo 'Found'
else
    echo 'Not found'
fi

-h有关更多选项，请参阅通过/--help选项或附带文件访问的使用说明README。

相关内容