Take the 2-minute tour ×
Ask Ubuntu is a question and answer site for Ubuntu users and developers. It's 100% free, no registration required.

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

2 Answers 2

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
1  
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 at 23:34

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

Your Answer

 
discard

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.