Ask Ubuntu is a question and answer site for Ubuntu users and developers. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer
The file I need to search has around 110,000,000 lines. If I do egrep "^TEST" sortedlist.txt | wc -l I get 41,289 results. However the equivalent look commands, look -b TEST sortedlist.txt | wc -l yields only 1995 results. I almost wonder if there is a bug in look. – Matt Feb 20 '14 at 23:34
@Matt Maybe look is using different collation settings than the program you used to sort the file. – kasperd Oct 14 '15 at 20:07

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)
    prefix=$(echo $line | md5sum - | cut -c 1-2)
    mkdir -p $prefix
    echo $line | gzip >> $prefix/subwords

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)
share|improve this answer

sgrep might work for you:

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

The project page

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:

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.