Introdução
Em tratamento de texto é comum juntar dois ou mais arquivos com campos semelhantes com a finalidade de extrair alguma informação. Exemplo comum é um campo identificador em um arquivo casar com uma linha de outro arquivo e essa linha ser útil para extrações. Essa situação se assemelha as operações Join’s de um banco de dados e veremos com executá-las em arquivos textos.
Produto cartesiano
Imagine que você tenha dois conjuntos A e B, sendo A={“a1”, “a2”} e B={“b1”, “b2”}. O produto cartesiano, AxB resultará no conjunto: AxB={“a1b1”, “a2b2”, “a2b1”, “a2b2”}. Essa operação faz justamente associar cada elemento de A a todos os elementos de B. Se |A| é o tamanho do conjunto A, e |B| o tamanho do conjunto B, o produto cartesiano resultará em |AxB|=|A|x|B| elementos.
Essa operação será bastante útil pois nos permite obter todas as relações entre as linhas de dois ou mais arquivos. Para implementar isso em bash veja o código abaixo (referência [1] + algumas modificações próprias)
#!/bin/bash
# Qua Dez 7 21:17:24 BRST 2016
# [cartesian.sh]
foreachline() {
_foreachline() {
DELIM=' '
if [ $# -lt 2 ]; then
printf "$1\n"
return
fi
local prefix=$1
local file=$2
shift 2
while read line; do
_foreachline "$prefix$line$DELIM" $*
done <$file
}
_foreachline "" $*
}
foreachline $*
Salve como cartesian.sh e digite:
$ chmod +x cartesian.sh
Para testá-lo, vamos considerar dois arquivos simples: ids.txt e acessos.txt. Os dois arquivos simulam um log de acesso onde o primeiro associa um id numérico a um site e o segundo arquivo contém o número de acessos daquele site em um dia da semana.
$ cat ids.txt 1 www.google.com 2 www.facebook.com 3 www.youtube.com 4 www.slashdot.com 5 www.reddit.com $ cat acessos.txt 1 122 119 88 80 111 199 67 2 13 14 18 80 66 77 11 3 4 6 11 18 6 8 19 4 20 11 17 80 18 10 21 5 40 41 30 20 22 21 11
O produto cartesiano é dado por:
$ ./cartesian.sh ids.txt acessos.txt 1 www.google.com 1 122 119 88 80 111 199 67 1 www.google.com 2 13 14 18 80 66 77 11 1 www.google.com 3 4 6 11 18 6 8 19 1 www.google.com 4 20 11 17 80 18 10 21 1 www.google.com 5 40 41 30 20 22 21 11 2 www.facebook.com 1 122 119 88 80 111 199 67 2 www.facebook.com 2 13 14 18 80 66 77 11 2 www.facebook.com 3 4 6 11 18 6 8 19 2 www.facebook.com 4 20 11 17 80 18 10 21 2 www.facebook.com 5 40 41 30 20 22 21 11 3 www.youtube.com 1 122 119 88 80 111 199 67 3 www.youtube.com 2 13 14 18 80 66 77 11 3 www.youtube.com 3 4 6 11 18 6 8 19 3 www.youtube.com 4 20 11 17 80 18 10 21 3 www.youtube.com 5 40 41 30 20 22 21 11 4 www.slashdot.com 1 122 119 88 80 111 199 67 4 www.slashdot.com 2 13 14 18 80 66 77 11 4 www.slashdot.com 3 4 6 11 18 6 8 19 4 www.slashdot.com 4 20 11 17 80 18 10 21 4 www.slashdot.com 5 40 41 30 20 22 21 11 5 www.reddit.com 1 122 119 88 80 111 199 67 5 www.reddit.com 2 13 14 18 80 66 77 11 5 www.reddit.com 3 4 6 11 18 6 8 19 5 www.reddit.com 4 20 11 17 80 18 10 21 5 www.reddit.com 5 40 41 30 20 22 21 11
Semanticamente temos linhas inválidas, pois o acesso de determinado site está associado a outro, isso é, algumas linhas possuem identificadores que não se casam. Podemos retirar essas linhas inválidas realizando uma operação JOIN, que nada mais é que um produto cartesiano com condição de junção.
Vamos mostrar o endereço do site seguido de seus acessos:
$ ./cartesian.sh ids.txt acessos.txt | awk '$1 == $3 {$3=""; print}'
1 www.google.com 122 119 88 80 111 199 67
2 www.facebook.com 13 14 18 80 66 77 11
3 www.youtube.com 4 6 11 18 6 8 19
4 www.slashdot.com 20 11 17 80 18 10 21
5 www.reddit.com 40 41 30 20 22 21 11
Se os identificadores são iguais ($1 igual a $3) então imprima toda a linha ignorando o terceiro campo (para não mostrar o id duas vezes).
O exemplo acima pode ser reescrito usando o comando join:
$ join ids.txt acessos.txt 1 www.google.com 122 119 88 80 111 199 67 2 www.facebook.com 13 14 18 80 66 77 11 3 www.youtube.com 4 6 11 18 6 8 19 4 www.slashdot.com 20 11 17 80 18 10 21 5 www.reddit.com 40 41 30 20 22 21 11
Por padrão ele iguala o primeiro campo de cada arquivo, mas esse comportamento pode ser mudado através das opções -1 e -2. O comando join só funciona para dois arquivos de entrada e eles devem estar ordenados.
Além da condição de junção, podemos realizar filtros nas linhas (simular um where) e também selecionar (ou projetar) colunas. O seguinte exemplo mostra os endereços que possuem acessos no primeiro dia da semana menor que o segundo (condição: $4 < $5).
$ ./cartesian.sh ids.txt acessos.txt | awk '($1 == $3) && ($4 < $5) {print $2}'
www.facebook.com
www.youtube.com
www.reddit.com
Quais pares de sites possuem o mesmo número de acesso no quarto dia da semana?
$ ./cartesian.sh ids.txt ids.txt acessos.txt acessos.txt | awk '($1 == $5) && ($3 == $13) && ($1 > $3) && ($9 == $17) { print $2, $4 }'
www.facebook.com www.google.com
www.slashdot.com www.google.com
www.slashdot.com www.facebook.com
É preciso repetir os arquivos de entrada para se obter os nomes em cada par. As duas primeiras condições do awk associam as linhas dos arquivos de acessos aos respectivos identificadores. A terceira condição impede que o mesmo site apareça duas vezes no par e a última condição iguala o quarto dia da semana. A ideia geral é fazer o produto cartesiano e igualar as colunas correspondentes e depois usar alguma condição mais específica.
Sabendo usar a linguagem do awk podemos criar scripts mais interessantes. O exemplo abaixo mostra o endereço do site seguido da soma total de seus acessos:
$ ./cartesian.sh ids.txt acessos.txt | awk '(sum=$4+$5+$6+$7+$8+$9+$10) && $1 == $3 {print $2, sum}'
www.google.com 786
www.facebook.com 279
www.youtube.com 72
www.slashdot.com 177
www.reddit.com 185
LEFT/RIGHT/FULL OUTER JOIN
Imagine que um identificador em ids.txt não case com alguma linha em acessos.txt — para os exemplos mostrados, essa linha seria suprimida. Existem casos em que recuperar essas linhas não casadas (ou órfãs) é interessante porque elas contêm informações do tipo “não está associado a”. Um LEFT OUTER JOIN, em banco de dados, é um JOIN que também mostra as linhas que não casaram do arquivo à esquerda. Similarmente, o RIGHT OUTER JOIN mostra linhas que não casaram do arquivo à direita. O FULL OUTER JOIN mostra todas as linhas casadas e todas as órfãs.
Vamos inserir linhas em nossos arquivos.
$ echo “6 daemoniolabs.wordpress.com” >> ids.txt $ echo “10 20 21 22 23 24 25 26” >> acessos.txt
De cara vemos que há dados inconsistentes, pois não existe id 6 no arquivo acessos.txt e também não existe id 10 no arquivo ids.txt.
O uso do join torna o tratamento mais conveniente:
# join (natural) $ join ids.txt acessos.txt 1 www.google.com 122 119 88 80 111 199 67 2 www.facebook.com 13 14 18 80 66 77 11 3 www.youtube.com 4 6 11 18 6 8 19 4 www.slashdot.com 20 11 17 80 18 10 21 5 www.reddit.com 40 41 30 20 22 21 11 # left outer join $ join -a 1 ids.txt acessos.txt 1 www.google.com 122 119 88 80 111 199 67 2 www.facebook.com 13 14 18 80 66 77 11 3 www.youtube.com 4 6 11 18 6 8 19 4 www.slashdot.com 20 11 17 80 18 10 21 5 www.reddit.com 40 41 30 20 22 21 11 6 daemoniolabs.wordpress.com # right outer join $ join -a 2 ids.txt acessos.txt 1 www.google.com 122 119 88 80 111 199 67 2 www.facebook.com 13 14 18 80 66 77 11 3 www.youtube.com 4 6 11 18 6 8 19 4 www.slashdot.com 20 11 17 80 18 10 21 5 www.reddit.com 40 41 30 20 22 21 11 10 20 21 22 23 24 25 26 # full outer join $ join -a 1 -a 2 ids.txt acessos.txt 1 www.google.com 122 119 88 80 111 199 67 2 www.facebook.com 13 14 18 80 66 77 11 3 www.youtube.com 4 6 11 18 6 8 19 4 www.slashdot.com 20 11 17 80 18 10 21 5 www.reddit.com 40 41 30 20 22 21 11 10 20 21 22 23 24 25 26 6 daemoniolabs.wordpress.com
Destaquei em negrito as linhas órfãs. A opção -a do join mostra linhas órfãs, sendo que o argumento 1 se refere às linhas do primeiro arquivo e o 2 linhas do segundo. Vale lembrar que o join só trabalha com arquivos ordenados, dois arquivos de entradas e com a união de uma só coluna.
Se for útil, podemos projetar colunas com a opção -o e usar a palavra “NULL” na coluna omitida pela linha órfã:
$ join -a 1 ids.txt acessos.txt -o 1.2,2.3 -e NULL www.google.com 119 www.facebook.com 14 www.youtube.com 6 www.slashdot.com 11 www.reddit.com 41 daemoniolabs.wordpress.com NULL
A opção -o indica o formato de saída, sendo que 1.2 se refere a segunda coluna do arquivo 1 e 2.3 a terceira coluna do arquivo 2. A opção -e coloca a palavra NULL nas colunas vazias.
O seguinte comando mostra a linha do site que ninguém acessa:
$ join -v 1 ids.txt acessos.txt 6 daemoniolabs.wordpress.com
A opção -v é semelhante a -a porém filtra as linhas casadas, mostrando somente as linhas não pareadas (ou órfãs).
Ou, através do awk, selecionando linhas que possuem colunas vazias:
$ join -a 1 ids.txt acessos.txt | awk '$3=="" { print $2 }'
daemoniolabs.wordpress.com
No exemplo acima projetamos somente o endereço do site. Por fim, o exemplo abaixo mostra o ID que não está cadastrado:
$ join -v 2 ids.txt acessos.txt -o 2.1 10
Quando usar?
Se comandos do bash simulam algumas consultas em banco de dados, então quando devemos usar um ou outro? Se a consulta for simples e o tamanho do produto cartesiano for pequeno então vale a pena executar via bash, pois assim pouparemos tempo por não precisar de criar um banco de dados do zero. Arquivos relativamente maiores poderão ainda ser usados se a consulta for feita usando o comando join.
Por outro lado, problemas complexos, grandes e com várias consultas são melhores tratados em um SGDB já que ele fornece todo um arcabouço otimizado para tratar os dados e as consultas.
Conclusão
Através do produto cartesiano e do comando join, podemos simular consultas específicas de banco de dados no terminal. Tal recurso pode ser utilizado no lugar de um SGDB quando o problema for tratável — não muito grande ou complexo — pois poupa-se tempo para se criar um banco de dados desde o zero.
Referências
Cartesian product of two files as sets of lines in GNU Linux by stackoverflow (http://archive.is/nhpVI) (Acessado em: Dezembro/2016)
http://stackoverflow.com/questions/1620946/cartesian-product-of-two-files-as-sets-of-lines-in-gnu-linux
Unix-Join by shapeshed (http://archive.is/ZJpxK) (Acessado em: Dezembro/2016)
https://shapeshed.com/unix-join/
O comando join by vivaolinux (http://archive.is/Cbo9M) (Acessado em: Dezembro/2016)
https://www.vivaolinux.com.br/dica/O-comando-join
Dæmonio Labs 