1
$\begingroup$

The problem.

Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are huge. In particular, neither the entire file nor the list of all distinct strings fit into central memory. The global file may be parsed and/or sorted (in external memory) a few times, though.

The goal is to build the file in which line $i$, for $i=1..m$, is integer $k$ if the string on line $i$ in the original file is the $k+1$-th distinct string appearing in the original file.

Example.

For instance, if the original file is:

bbb
cccc
cccc
bbb
aaa
ee
aaa
fff
dddd
cccc
bbb
fff

then $n=6$, $m=12$, and we should obtain:

0
1
1
0
2
3
2
4
5
1
0
4  

My approach.

I take benefit of standard unix command-line tools, as follows.

I first build a numbered string occurence file:

zcat input.gz | awk '{print NR-1,$0;}' | gzip -c > occurrences.gz

I use it to build an index file for strings that respects occurence rank, and starts with character '-', lower than any occurence number:

zcat occurrences.gz |
  sort -T. -S1g --stable -k2,2 |
  awk 'BEGIN{old="none";}{if ($2!=old) print $0; old=$2;}' |
  sort -T. -S1g -nk1,1 | awk '{print "-",$2,NR-1;}' |
  gzip -c > index.gz

I merge the two files and sort the result to ensure that the line with a string index will be just before all other lines containing this string; I then replace each string, sort according to occurence rank, and I am done:

zcat occurrences.gz index.gz |
  sort -T. -S1g -k2,2 -k1,1 |
  awk '{if ($1=="-") i=$3; else print $1,i;}' |
  sort -T. -S1g -nk1,1 |
  cut -d" " -f2 |
  gzip -c > result.gz

Technical detail: to avoid encoding issues, first set environment variable LC_ALL to C.

Question.

Is it possible to do significantly better than my approach, or to achieve similar performances with a significantly different approach, in practice?

Notice that I am not interested in minor, technical improvements, like using mawk, sed, etc, instead of awk. I am not interested in a purely theoretical solution either, that would be better asymptotically but would turn out to be so complex than no implementation is reasonably feasible.

Instead, my concern is the relevance and overall effectiveness of my approach, or variants.

For instance, would any external memory data structure be faster, while using as little memory, with available implementation?

$\endgroup$
5
  • $\begingroup$ Should -k2,2 -k1,1 be -k2,2 -nk1,1? (Not sure if that works with sort.) $\endgroup$ – D.W. Jan 5 at 7:40
  • $\begingroup$ It works on my platform as written in the question, but does not with this change. This sort just has to put identical strings together, with the line starting with '-' first, so numericai sort is not needed, if I am correct. $\endgroup$ – Matthieu Latapy Jan 5 at 7:50
  • $\begingroup$ Warm thanks for the edition, that makes the question much easier to read :) $\endgroup$ – Matthieu Latapy Jan 5 at 7:52
  • $\begingroup$ OK, thank you. It's possible it might be slightly faster with that change (you might have to change - to 0 or -1), if sort is faster on partly sorted files, but maybe not. Anyway: I can see how to speed up the index step (possibly significantly, I don't know, it depends on how sort works) by splitting into temporary files based on a hash of the string, but I can't see how to speed up the merge. I'm guessing the merge is the dominant cost, and if so, speeding up constructing the index won't help much. Let me know if I've misunderstood somehow. $\endgroup$ – D.W. Jan 5 at 7:53
  • $\begingroup$ Good point, replacing '-' by '-1' and sorting numerically may indeed be faster. Right again regarding splitting, but I think this is what sort does, and what makes it so effective. Thanks! $\endgroup$ – Matthieu Latapy Jan 5 at 7:58
1
$\begingroup$

The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary.

There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some variant of B-trees, or a hash table (e.g. extensible hashing) would work. Consider Berkeley DB if you need something off the shelf.

If that is too slow, you could use a Bloom filter as an in-memory cache. Then, you need only consult the on-disk data structure if you get a hit in the Bloom filter.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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