0

I have two files file1 and file2. The two files contain names. One name in each line. I want to query all names in file2 that are not equal to or a suffix of name in file1. Note that the prefix is identified by any characters followed by a dot (.) then the suffix.

For example. If file2contains f2name in a line, and file1 contains sub.f2name then f2name is a suffix for a name in file1 and we do not want to put it in the result.

Another example is sub1.sub2.f2name. The names in file1 can be preceded by any number of prefixes (characters separated by dots). The names of file2 can appear as suffix for any number of prefixes or can be equal to names in file1.

I need to query names in file2 that are not equal to and are not suffix of any number of prefixes of names in file1. For example: file2 contains:

bb.com
a.com
123.com

file1 contains:

aa.bb.com
aa.ff.bb.com
aa.bb.cc.com
a.com

The names I want are those in file2 not equal to and are not suffix of names in file1. i.e.:

123.com

The reason for the output: a.com in file2 is equal to a name in file1: aa.bb.com And bb.comfrom file2 is suffix of aa.ff.bb.com and aa.bb.com in file1 (note: prefixes can be repeated more than one or two. The point is that it ends with a name in file2).

I have tried to use MySQL to make a query. But file2 contains 3 million line and file1 contains 1 million. MySQL could not perform well. Does Linux has commands that can perform such query in a reasonable time?

  • Why are you requesting 'aa.bb.cc.com' to be printed? It is not in the source file2 in your question. – Isaac Jul 29 '18 at 14:41
  • @Isaac thanks. Corrected now. If you have an answer can you please tell me if it can be performed in a reasonable time (not more than an hour)? file2 is 3 million line, file1 is 1 million. – user9371654 Jul 29 '18 at 14:44
  • Could it happen that one line in file1 (like hh.ii.jj.com) is longer than all the (matching) lines in file2 (like ii.jj.com) ? – Isaac Jul 29 '18 at 14:47
  • @Isaac sorry I don't get your question. What do you mean by longer? your example is like the examples I pointed. Yes ideally if the name in file2 exist as a suffix in file1, then that name in file1 will be longer. – user9371654 Jul 29 '18 at 14:50
  • The lines are unique in both files BTW. But names in file2 can occur as a suffix in more than line in file1. Hope this clarify. – user9371654 Jul 29 '18 at 14:51
0

I have no idea how efficient this will be, for your input, but here's a possible strategy:

  1. turn the lines of file2 into line-anchored regex patterns

    sed -e 's/\./\\./g' -e 's/$/\$/' file2
    
  2. pipe the patterns into grep to output only the matching portions of file1

    ... | grep -of - file1
    
  3. (optional) uniquify the results

  4. plain-text search file2 for the matching entries

    ... | grep -vxFf - file2
    

Ex.

$ sed -e 's/\./\\./g' -e 's/$/\$/' file2 | 
    grep -of - file1 | 
    sort -u | 
    grep -vxFf - file2
123.com

If the entries in file2 contain regex-special characters besides . these will also need to be escaped.

  • Having a quadratic time complexity, it is not a good solution. But also, the match is not on dot boundaries. – Isaac Jul 29 '18 at 18:27
0

The first solution I tried (there is a faster alternative below) is similar to what @steeldriver presented. However, the values in file2 need to have an starting point to avoid that a line like a.bb.com match in cc.aa.bb.com. The matches must have a dot as a delimiter. Doing it in four steps:

n=100
echo "step1  ==============="
time head -n $n file2 | sort | tee file222 | sed 's/\./\\./g;s/^/\\./;s/$/$/' >file22
echo "step2  ==============="
time sed 's/^/./' file1 | head -n $n > file11
echo "step3  ==============="
time grep -oEf file22 file11 | sort -u | sed 's/^\.//' >file33
echo "step4  ==============="
time comm -13 file33 file222 > fileout

But the time increase as the square of n, it is quite fast for less than a 1000 lines (both files). But it grows to the order of 475 days (more than a year) for 1 Million lines. Clearly not a viable solution.

Option b

A not so intuitive option is to expand file1 to all of its constituents.
A process similar to expanding aa.ff.bb.com to:

aa.ff.bb.com
ff.bb.com
bb.com
com

And then, after removing repeated lines in this file, find all lines that exist only on (a sorted) file2.

The step to sort (and remove repeats) use the most time, but being in the order of 8 seconds for a 1 million (unique) lines files, it is quite reasonable.

The whole process (including the generation of source files) is:

#!/bin/bash
TIMEFORMAT='%R %U %S'

echo $'bb.com\na.com\n123.com' >file2
printf '%s\n'        {a..z}{a..m}.{a..z}{a..m}.{com,net,dot} >>file2
echo $'aa.bb.com\naa.ff.bb.com\naa.bb.cc.com\na.com' >file1
printf '%s\n' {h..k}.{e..z}{a..m}.{e..z}{a..m}.{com,net,dot} >>file1

echo "file2 has $(wc -l <file2) lines"
echo "file1 has $(wc -l <file1) lines"

n=10000000
time sed -n 'p;:1;s/[^.]*\.//p;t1' file1 >file1b1
echo "file1b1 has $(wc -l <file1b1) lines"
time sort -u file1b1 | head -n $n >file1b2
echo "file1b2 has $(wc -l <file1b2) lines"
time sort -u file2   | head -n $n >file2b2
time comm -13   file1b2 file2b2   >fileout

That prints this results:

file2 has 342735 lines
file1 has 981556 lines
4.353 4.248 0.096
file1b1 has 3926221 lines
8.649 15.024 0.488
file1b2 has 1227809 lines
0.618 0.908 0.112
1.011 0.968 0.032

In the order of 15 seconds.

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.