Substituir string em um arquivo de texto enorme (70 GB), uma linha

126

Eu tenho um arquivo de texto enorme (70 GB), uma linha e desejo substituir uma string (token) nele. Quero substituir o token <unk> por outro token falso ( problema de luvas ).

Eu tentei sed :

sed 's/<unk>/<raw_unk>/g' < corpus.txt > corpus.txt.new

mas o arquivo de saída corpus.txt.new tem zero bytes!

Eu também tentei usar o perl:

perl -pe 's/<unk>/<raw_unk>/g' < corpus.txt > corpus.txt.new

mas recebi um erro de falta de memória.

Para arquivos menores, os dois comandos acima funcionam.

Como posso substituir uma string por um arquivo desse tipo? Este é uma questão relacionada, mas nenhuma das respostas funcionou para mim.

Editar : Que tal dividir o arquivo em pedaços de 10GB (ou qualquer outro) e aplicar sed em cada um deles e depois mesclá-los com cat ? Isso faz sentido? Existe uma solução mais elegante?

    
por Christos Baziotis 29.12.2017 / 15:58

14 respostas

106

As ferramentas usuais de processamento de texto não são projetadas para lidar com linhas que não se encaixam na RAM. Eles tendem a trabalhar lendo um registro (uma linha), manipulando-o e exibindo o resultado, e então prosseguindo para o próximo registro (linha).

Se houver um caractere ASCII que apareça com frequência no arquivo e não apareça em <unk> ou <raw_unk> , você poderá usá-lo como separador de registro. Como a maioria das ferramentas não permite separadores de registros personalizados, troque entre esse caractere e novas linhas. tr processa bytes, não linhas, por isso não se importa com nenhum tamanho de registro. Supondo que ; funcione:

<corpus.txt tr '\n;' ';\n' |
sed 's/<unk>/<raw_unk>/g' |
tr '\n;' ';\n' >corpus.txt.new

Você também pode ancorar no primeiro caractere do texto que está pesquisando, supondo que ele não seja repetido no texto de pesquisa e seja exibido com frequência suficiente. Se o arquivo puder começar com unk> , altere o comando sed para sed '2,$ s/… para evitar uma correspondência espúria.

<corpus.txt tr '\n<' '<\n' |
sed 's/^unk>/raw_unk>/g' |
tr '\n<' '<\n' >corpus.txt.new

Como alternativa, use o último caractere.

<corpus.txt tr '\n>' '>\n' |
sed 's/<unk$/<raw_unk/g' |
tr '\n>' '>\n' >corpus.txt.new

Observe que essa técnica pressupõe que o sed funcione perfeitamente em um arquivo que não termina com uma nova linha, ou seja, processa a última linha parcial sem truncá-la e sem anexar uma nova linha final. Funciona com o GNU sed. Se você puder escolher o último caractere do arquivo como o separador de registro, você evitará qualquer problema de portabilidade.

    
por 29.12.2017 / 16:07
110

Para um arquivo tão grande, uma possibilidade é o Flex. Seja unk.l :

%%
\<unk\>     printf("<raw_unk>");  
%%

Em seguida, compile e execute:

$ flex -o unk.c  unk.l
$ cc -o unk -O2 unk.c -lfl
$ unk < corpus.txt > corpus.txt.new
    
por 29.12.2017 / 17:40
41

Então você não tem memória física suficiente para armazenar o arquivo inteiro de uma só vez, mas em um sistema de 64 bits você tem espaço de endereçamento virtual suficiente para mapear o arquivo inteiro. Os mapeamentos virtuais podem ser úteis como um hack simples em casos como este.

As operações necessárias estão todas incluídas no Python. Existem várias sutilezas irritantes, mas evita escrever código em C. Em particular, é necessário cuidado para evitar a cópia do arquivo na memória, o que derrotaria completamente o ponto. No lado positivo, você obtém relatórios de erros gratuitamente (python "exceptions"):).

#!/usr/bin/python3
# This script takes input from stdin
# (but it must be a regular file, to support mapping it),
# and writes the result to stdout.

search = b'<unk>'
replace = b'<raw_unk>'


import sys
import os
import mmap

# sys.stdout requires str, but we want to write bytes
out_bytes = sys.stdout.buffer

mem = mmap.mmap(sys.stdin.fileno(), 0, access=mmap.ACCESS_READ)
i = mem.find(search)
if i < 0:
    sys.exit("Search string not found")

# mmap object subscripts to bytes (making a copy)
# memoryview object subscripts to a memoryview object
# (it implements the buffer protocol).
view = memoryview(mem)

out_bytes.write(view[:i])
out_bytes.write(replace)
out_bytes.write(view[i+len(search):])
    
por 29.12.2017 / 22:44
17

Acho que a versão C pode ter um desempenho muito melhor:

#include <stdio.h>
#include <string.h>

#define PAT_LEN 5

int main()
{
    /* note this is not a general solution. In particular the pattern
     * must not have a repeated sequence at the start, so <unk> is fine
     * but aardvark is not, because it starts with "a" repeated, and ababc
     * is not because it starts with "ab" repeated. */
    char pattern[] = "<unk>";          /* set PAT_LEN to length of this */
    char replacement[] = "<raw_unk>"; 
    int c;
    int i, j;

    for (i = 0; (c = getchar()) != EOF;) {
        if (c == pattern[i]) {
            i++;
            if (i == PAT_LEN) {
                printf("%s", replacement);
                i = 0;
            }
        } else {
            if (i > 0) {
                for (j = 0; j < i; j++) {
                    putchar(pattern[j]);
                }
                i = 0;
            }
            if (c == pattern[0]) {
                i = 1;
            } else {
                putchar(c);
            }
        }
    }
    /* TODO: fix up end of file if it ends with a part of pattern */
    return 0;
}

EDIT: Modificado de acordo com sugestões dos comentários. Também correu bug com o padrão <<unk> .

    
por 29.12.2017 / 21:14
16

Existe um utilitário replace no pacote mariadb-server / mysql-server. Ele substitui strings simples (não expressões regulares) e, ao contrário de grep / sed / awk replace , não se preocupa com \n e replace . O consumo de memória é constante com qualquer arquivo de entrada (cerca de 400kb na minha máquina).

Claro que você não precisa rodar um servidor mysql para usar o %code% , ele é apenas empacotado dessa maneira no Fedora. Outras distros / sistemas operacionais podem ter pacotes separadamente.

    
por 29.12.2017 / 22:11
14

O GNU grep pode mostrar o deslocamento de correspondências em arquivos "binários", sem ter que ler linhas inteiras na memória. Você pode então usar dd para ler até esse deslocamento, pular a correspondência e continuar copiando do arquivo.

file=...
newfile=...
replace='<raw_unk>'
grep -o -b -a -F '<unk>' <"$file" |
(   pos=0
    while IFS=$IFS: read offset pattern
    do size=${#pattern}
       let skip=offset-pos
       let big=skip/1048576
       let skip=skip-big*1048576
       dd bs=1048576 count=$big <&3
       dd bs=1 count=$skip <&3
       dd bs=1 count=$size of=/dev/null <&3
       printf "%s" "$replace"
       let pos=offset+size
    done
    cat <&3
) 3<"$file" >"$newfile"

Para velocidade, dividi o dd em uma grande leitura de blocos de 1048576 e uma leitura menor de 1 byte de cada vez, mas essa operação ainda será um pouco lenta em um arquivo tão grande. A saída grep é, por exemplo, 13977:<unk> , e isso é dividido nos dois pontos pela leitura nas variáveis offset e pattern . Temos que acompanhar em pos de quantos bytes já foram copiados do arquivo.

    
por 29.12.2017 / 17:37
11

Aqui está outra única linha de comando do UNIX que pode funcionar melhor do que outras opções, porque você pode "procurar" por um "tamanho de bloco" que tenha um bom desempenho. Para que isso seja robusto, você precisa saber que tem pelo menos um espaço em cada caractere X, em que X é seu "tamanho de bloco" arbitrário. No exemplo abaixo, escolhi um "tamanho de bloco" de 1024 caracteres.

fold -w 1024 -s corpus.txt | sed 's/<unk>/<raw_unk>/g' | tr '/n' '/0'

Aqui, o fold irá pegar até 1024 bytes, mas o -s garante que ele seja quebrado em um espaço se houver pelo menos um desde o último intervalo.

O comando sed é seu e faz o que você espera.

Em seguida, o comando tr irá "desdobrar" o arquivo convertendo as novas linhas que foram inseridas de volta em nada.

Você deve considerar tentar tamanhos de bloco maiores para ver se ele tem um desempenho mais rápido. Em vez de 1024, você pode tentar 10240 e 102400 e 1048576 para a opção -w da dobra.

Aqui está um exemplo detalhado por cada etapa que converte todos os N's em minúsculas:

[root@alpha ~]# cat mailtest.txt
test XJS C4JD QADN1 NSBN3 2IDNEN GTUBE STANDARD ANTI UBE-TEST EMAIL*C.34X test

[root@alpha ~]# fold -w 20 -s mailtest.txt
test XJS C4JD QADN1
NSBN3 2IDNEN GTUBE
STANDARD ANTI
UBE-TEST
EMAIL*C.34X test

[root@alpha ~]# fold -w 20 -s mailtest.txt | sed 's/N/n/g'
test XJS C4JD QADn1
nSBn3 2IDnEn GTUBE
STAnDARD AnTI
UBE-TEST
EMAIL*C.34X test

[root@alpha ~]# fold -w 20 -s mailtest.txt | sed 's/N/n/g' | tr '\n' '
fold -w 1024 -s corpus.txt | sed 's/<unk>/<raw_unk>/g' | tr '/n' '/0'
' test XJS C4JD QADn1 nSBn3 2IDnEn GTUBE STAnDARD AnTI UBE-TEST EMAIL*C.34X test

Você precisará adicionar uma nova linha ao final do arquivo se ele tiver um, porque o comando tr irá removê-lo.

    
por 30.12.2017 / 17:30
10

Usando perl

Gerenciando seus próprios buffers

Você pode usar IO::Handle de setvbuf para gerenciar os buffers padrão ou pode gerenciar seus próprios buffers com sysread e syswrite . Verifique perldoc -f sysread e perldoc -f syswrite para mais informações, essencialmente eles ignoram o buffer de dados.

Aqui nós rolamos nosso próprio buffer IO, mas o fazemos manualmente e arbitrariamente em 1024 bytes. Nós também abrimos o arquivo para o RW, então fazemos tudo do mesmo FH de uma só vez.

use strict;
use warnings;
use Fcntl qw(:flock O_RDWR);
use autodie;
use bytes;

use constant CHUNK_SIZE => 1024 * 32;

sysopen my $fh, 'file', O_RDWR;
flock($fh, LOCK_EX);

my $chunk = 1;
while ( sysread $fh, my $bytes, CHUNK_SIZE * $chunk ) {
  if ( $bytes =~ s/<unk>/<raw_unk>/g ) {
    seek( $fh, ($chunk-1)* CHUNK_SIZE, 0 );
    syswrite( $fh, $bytes, 1024);
    seek( $fh, $chunk * CHUNK_SIZE, 0 );
  }
  $chunk++;
}

Se você for seguir esse caminho

  1. Certifique-se de que <unk> e <raw_unk> tenham o mesmo tamanho de bytes.
  2. Você pode querer garantir que nosso método em buffer não cruze o limite CHUNKSIZE , se você estiver substituindo mais de 1 byte.
por 29.12.2017 / 21:47
8

Você pode tentar bbe ( editor de bloco binário ) , " sed para arquivos binários".

Eu tive sucesso usando-o em um arquivo de texto de 7GB sem EOL chars, substituindo várias ocorrências de uma string por uma de comprimento diferente. Sem tentar qualquer otimização, ele gerou uma taxa de processamento média de > 50MB / s.

    
por 31.12.2017 / 03:52
5

Com perl , você pode trabalhar com registros de tamanho fixo como:

perl -pe 'BEGIN{$/=e8}
          s/<unk>/<raw_unk>/g' < corpus.txt > corpus.txt.new

E espero que não haja <unk> s abrangendo dois desses 100MB de registros.

    
por 29.12.2017 / 22:07
5

Aqui está um pequeno programa Go que executa a tarefa ( unk.go ):

package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
)

func main() {
    const (
        pattern     = "<unk>"
        replacement = "<raw_unk>"
    )
    var match int
    var char rune
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanRunes)
    for scanner.Scan() {
        char = rune(scanner.Text()[0])
        if char == []rune(pattern)[match] {
            match++
            if match == len(pattern) {
                fmt.Print(replacement)
                match = 0
            }
        } else {
            if match > 0 {
                fmt.Print(string(pattern[:match]))
                match = 0
            }
            if char == rune(pattern[0]) {
                match = 1
            } else {
                fmt.Print(string(char))
            }
        }
    }
    if err := scanner.Err(); err != nil {
        log.Fatal(err)
    }
}

Basta criá-lo com go build unk.go e executá-lo como ./unk <input >output .

EDITAR:

Desculpe, eu não li que tudo está em uma linha, então tentei ler o caractere de arquivo por caractere agora.

EDIT II:

Aplique a mesma correção ao programa em C.

    
por 29.12.2017 / 16:58
1

Isso pode ser um exagero para um arquivo de 70 GB e uma pesquisa simples & substituir, mas a estrutura do Hadoop MapReduce resolveria seu problema agora sem nenhum custo (escolha a opção 'Nó Único' ao configurá-lo para executá-lo localmente) - e ele poderá ser dimensionado para capacidade infinita no futuro sem a necessidade de modificar seu código.

O tutorial oficial no link usa Java (extremamente simples), mas você pode encontrar bibliotecas de clientes para Perl ou qualquer idioma que você queira usar.

Portanto, se mais tarde você descobrir que está realizando operações mais complexas em arquivos de texto de 7000 GB e precisar fazer isso 100 vezes por dia, poderá distribuir a carga de trabalho entre vários nós provisionados ou provisionados automaticamente para você um cluster do Hadoop baseado em nuvem.

    
por 04.01.2018 / 18:25
0

Todas as sugestões anteriores exigem a leitura do arquivo inteiro e a gravação do arquivo inteiro. Isso não só leva muito tempo, mas também requer 70 GB de espaço livre.

1) Se eu entendi seu caso específico corretamente, seria aceitável substituir < unk > com alguma outra string do mesmo comprimento?

2a) Existem várias ocorrências? 2b) Se sim, você sabe quantos?

Tenho certeza de que você já resolveu este problema com mais de um ano e gostaria de saber qual solução você usou.

Eu proporia uma solução (provavelmente em C) que leria os BLOCKS do arquivo pesquisando cada um pela string, levando em consideração o possível cruzamento de blocos. Uma vez encontrada, substitua a string pelo SAME length alternate e escreva somente aquele BLOCK. Continuando pelo número conhecido de ocorrências ou até o final do arquivo. Isso exigiria apenas algumas gravações de número de ocorrências e no máximo duas vezes (se cada ocorrência fosse dividida entre dois blocos). Isso não exigiria mais espaço!

    
por 16.05.2019 / 02:52
-1

Se tivermos uma quantidade mínima de <unk> (como esperado pela lei de Zipf),

awk -v RS="<unk>" -v ORS="<raw_unk>" 1
    
por 16.03.2018 / 10:30