Como consultar todas as linhas em um arquivo que NÃO são iguais ou sufixos de qualquer nome em outro arquivo

Question

Eu tenho dois arquivos file1 e file2 . Os dois arquivos contêm nomes. Um nome em cada linha. Desejo consultar todos os nomes em file2 que são not equal to ou suffix of nome em file1 . Observe que o prefixo é identificado por qualquer caractere seguido por um ponto ( . ) e depois pelo sufixo.

Por exemplo. Se file2 contiver f2name em uma linha e file1 contiver sub.f2name , então f2name será um sufixo para um nome em file1 e não queremos colocá-lo no resultado.

Outro exemplo é sub1.sub2.f2name . O names em file1 pode ser precedido por qualquer número de prefixos (caracteres separados por pontos). Os nomes de file2 podem aparecer como sufixo para qualquer número de prefixos ou podem ser iguais a nomes em file1 .

Eu preciso consultar nomes em file2 que não são iguais e não são sufixos de qualquer número de prefixos de nomes em file1 . Por exemplo: file2 contém:

bb.com
a.com
123.com

file1 contém:

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

Os nomes que eu quero são aqueles em file2 não iguais e não são sufixos de nomes em file1 . ou seja:

123.com

O motivo da saída: a.com in file2 é igual a um nome em file1 : aa.bb.com E bb.com de file2 é sufixo de aa.ff.bb.com e aa.bb.com in file1 (nota: os prefixos podem ser repetidos mais de um ou dois. O ponto é que ele termina com um nome em file2 ).

Eu tentei usar o MySQL para fazer uma consulta. Mas o arquivo2 contém 3 milhões de linhas e o arquivo1 contém 1 milhão. O MySQL não pôde executar bem. O Linux possui comandos que podem realizar essa consulta em um tempo razoável?

    

Answer 1

Eu não tenho ideia de quão eficiente isso será, para sua opinião, mas aqui está uma possível estratégia:

1. transforme as linhas de file2 em padrões de regex ancorados à linha

   sed -e 's/\./\./g' -e 's/$/\$/' file2
   

2. canaliza os padrões para o grep para gerar apenas as partes correspondentes de file1

   ... | grep -of - file1
   

3. (opcional) uniquifique os resultados

4. pesquisa de texto simples file2 para as entradas correspondentes

   ... | grep -vxFf - file2
   

Ex.

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

Se as entradas em file2 contiverem caracteres especiais de regex além de . , elas também precisarão ser ignoradas.

    

Answer 2

A primeira solução que tentei (existe uma alternativa mais rápida abaixo) é semelhante ao apresentado pelo @steeldriver. No entanto, os valores no arquivo2 precisam ter um ponto de partida para evitar que uma linha como a.bb.com corresponda em cc.aa.bb.com . As correspondências devem ter um ponto como um delimitador. Fazendo isso em quatro etapas:

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

Mas o tempo aumenta como o quadrado de n , é bastante rápido por menos que 1000 linhas (ambos os arquivos). Mas cresce para a ordem de 475 dias (mais de um ano) para 1 milhão de linhas. Claramente não é uma solução viável.

Opção b

Uma opção não tão intuitiva é expandir o arquivo1 para todos os seus constituintes.
Um processo semelhante ao expandir aa.ff.bb.com para:

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

Depois, depois de remover linhas repetidas neste arquivo, encontre todas as linhas que existem apenas no arquivo (classificado )2.

A etapa para classificar (e remover repetições) usa a maior parte do tempo, mas na ordem de 8 segundos para um arquivo de linhas de 1 milhão (único), é bastante razoável.

Todo o processo (incluindo a geração de arquivos fonte) é:

#!/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

Isso imprime os resultados:

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

Na ordem de 15 segundos.