13

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?

2
  • The top answer states the wrong sorting: the fact is you have to sort with: LC_COLLATE=C sort -d for the look command to function correctly, because look seems to ignore the locale and just uses C like sorting hardcoded, I also opened a bug because of this confusing behaviour: bugzilla.kernel.org/show_bug.cgi?id=198011
    – Sur3
    Nov 30, 2017 at 8:52
  • 1
    look -b failed for me with an error File too large. I think it's trying to read the whole thing into memory. Apr 5, 2018 at 15:52

5 Answers 5

12

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.

2
  • 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, 2014 at 23:34
  • 1
    @Matt Maybe look is using different collation settings than the program you used to sort the file.
    – kasperd
    Oct 14, 2015 at 20:07
5

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.

4
  • 2
    Isn't that already in askubuntu.com/a/701237/158442?
    – muru
    Jul 2, 2018 at 3:57
  • yes, i fill in the download link...
    – memorybox
    Jul 4, 2018 at 1:03
  • If that's all, you should edit that post instead of posting a new answer.
    – muru
    Jul 4, 2018 at 1:06
  • 1
    that post recommended: sudo apt-get install sgrep to get sgrep, The sgrep in the buntu repositories is not actually this sgrep, i'm not sure it's the same thing.
    – memorybox
    Jul 4, 2018 at 1:11
0

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)
0

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

1
  • 5
    The sgrep in the Ubuntu repositories is actually this sgrep, which is designed to "search a file for a structured pattern" and has nothing to do with binary search. Jul 6, 2017 at 9:10
0

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .