Efficiently search sorted file

Question

I have a large file containing one string on each line. I would like to be able to quickly determine if a string is in the file. Ideally, this would be done using a binary chop type algorithm.

Some Googling revealed the look command with the -b flag which promises to locate and output all strings beginning with a given prefix using a binary search algorithm. Unfortunately, it doesn't seem to work correctly and returns null results for strings that I know are in the file (they are properly returned by the equivalent grep search).

Does anyone know of another utility or strategy to search this file efficiently?

Answer 1

There's an essential difference between grep and look:

Unless explicitly stated otherwise, grep will find patterns even somewhere within the lines. For look the manpage states:

look — display lines beginning with a given string

I'm not using look very often, but it did work fine on a trivial example I just tried.

Answer 2

Maybe a little late answer:

Sgrep will help you.

Sgrep (sorted grep) searches sorted input files for lines that match a search key and outputs the matching lines. When searching large files sgrep is much faster than traditional Unix grep, but with significant restrictions.

• All input files must be sorted regular files.
• The sort key must start at the beginning of the line.
• The search key matches only at the beginning of the line.
• No regular expression support.

You can download source here: https://sourceforge.net/projects/sgrep/?source=typ_redirect

and the documents here: http://sgrep.sourceforge.net/

Another Way:

I don't know how large is the file.Maybe you should try parallel:

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

I always do grep with files which size > 100GB, it works well.

Answer 3

You could hash the file into pieces and then grep just the piece you wanted:

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

then the lookup would look like:

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

This does two things:

1. read and write compressed files. It's generally faster to put the load on the cpu (very fast) instead of the disk (very slow)
2. hash things in order to get an approximately equal distribution, you can use a shorter or longer hash as you'd like in order to reduce the size of each piece (but I'd recommend using nested subdirs if you do)

Answer 4

sgrep might work for you:

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

The project page http://sgrep.sourceforge.net/ says:

Sgrep uses a binary search algorithm, which is very fast, but requires sorted input.

For insertion however, I think there is no better solution than using a database: https://stackoverflow.com/questions/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/33859372#33859372

Answer 5

If you want it really fast (O(1) fast) you can build a hash set to look into. I couldn't find an implementation that would let me store a pre-built hash set in a file and probe it without having to read the entire file into memory, so I rolled my own.

Build the hash set (-b/--build):

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

Probe the hash set (-p/--probe):

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

… or with string to look-up on standard input:

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

You can quiet the output of --probe with the -q/--quiet option if you're only interested in the exit status:

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

For more options see the usage description accessible through the -h/--help option or the accompanying README file.