高效搜索排序文件

Question

我有一个大文件，每一行包含一个字符串。我希望能够快速确定文件中是否有字符串。理想情况下，这将使用二进制chop类型的算法来完成。

一些谷歌用户透露了带有look标志的-b命令，该标志承诺使用二进制搜索算法定位和输出以给定前缀开头的所有字符串。不幸的是，它似乎不能正常工作，并且返回我知道在文件中的字符串的空结果(它们由等价的grep搜索正确地返回)。

是否有人知道另一种有效搜索该文件的实用工具或策略？

Answer 1

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

除非另有明确说明，grep甚至会在行中的某个地方找到模式。对于look，命令页声明：

以给定字符串开头的显示行

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

Answer 2

也许是有点晚的回答：

斯格里普会帮你的。

Sgrep (已排序的grep)搜索排序后的输入文件中匹配搜索键并输出匹配行的行。在搜索大型文件时，sgrep比传统的Unix要快得多，但有很大的限制。

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

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

这里的文件是：http://sgrep.sourceforge.net/

另一种方式是：

我不知道您应该尝试并行的file.Maybe有多大：

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

我总是用大于100 do的文件来做grep，它工作得很好。

Answer 3

sgrep可能会为你工作：

sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt

项目页面http://sgrep.sourceforge.net/说：

Sgrep使用二进制搜索算法，该算法非常快速，但需要排序输入。

但是，对于插入，我认为没有比使用数据库更好的解决方案了：https://stackoverflow.com/questions/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/33859372#33859372