Substitua a sequência em um arquivo de texto enorme (70 GB), uma linha

126

Eu tenho um arquivo de texto enorme (70 GB), uma linha , e quero substituir uma string (token) nele. Quero substituir o token <unk>por outro fictício ( problema de luva ).

Eu tentei sed:

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

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

Eu também tentei usar 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 é um arquivo? Esta é uma pergunta relacionada, mas nenhuma das respostas funcionou para mim.

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

Christos Baziotis
fonte
como observou @Gilles, você consegue detectar algum caractere repetido que possa servir como um delimitador personalizado em sua única linha grande?
RomanPerekhrest
Penso que uma ferramenta que só pode pesquisar e substituir, mas não uma regex mais complexa, seria mais rápida. Também não se beneficiaria de fazer uma linha de cada vez, por isso não se afogaria nesse arquivo. Infelizmente, não tenho idéia da existência de tal ferramenta, embora não seja difícil escrever. Se for um caso único, a substituição de caracteres de nova linha como em uma das respostas provavelmente seria mais fácil.
Ctrl-alt-delor
Seu arquivo contém algo diferente de ASCII? Nesse caso, todo o manuseio unicode pode ser omitido e os bytes brutos podem ser processados.
Patrick Bucher
Concordo com @PatrickButcher Veja uma imagem maior. Além da necessidade imediata de substituir esse texto, para que mais esse arquivo deve ser usado? Se for algum tipo de log, ninguém conseguirá trabalhar com ele efetivamente. Se for um arquivo de dados usado por algum aplicativo, ele deverá ser responsável por manter os dados nesse arquivo.
Thomas Carlisle
2
Você pode usar splitcom a -bopção de definir tamanhos de arquivo de bloco em bytes. Processe cada um por sua vez, usando sede remontando. Existe o risco é que <unk>pode ser dividido em dois arquivos e não será encontrado ...
Vladislavs Dovgalecs

Respostas:

106

As ferramentas usuais de processamento de texto não foram projetadas para lidar com linhas que não cabem na RAM. Eles tendem a trabalhar lendo um registro (uma linha), manipulando-o e produzindo o resultado, depois 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 registros. Como a maioria das ferramentas não permite separadores de registros personalizados, troque entre esse caractere e as novas linhas. trprocessa 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á procurando, supondo que ele não seja repetido no texto de pesquisa e apareça com frequência suficiente. Se o arquivo começar unk>, altere o comando sed sed '2,$ s/…para evitar uma correspondência falsa.

<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 sed opera perfeitamente em um arquivo que não termina com uma nova linha, ou seja, que 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 separador de registros, evitará qualquer problema de portabilidade.

Gilles
fonte
8
Não tenho esse arquivo para testar, mas no Awk você pode especificar o "Separador de registros" e o "Separador de registros de saída". Então, supondo que você tenha um número razoável de vírgulas em seu arquivo, é possível resolver isso com: awk -v RS=, -v ORS=, '{gsub(/<unk>/, "<raw_unk>"); print}' Não?
Curinga
4
@ Wildcard Sim, essa é outra solução. O Awk tende a ser mais lento que o sed, por isso não o ofereço como a solução preferida para um arquivo grande.
Gilles
Você pode definir o separador de registro em Perl opção de linha de comando com -0eo valor octal de um char, ou dentro do script que pode ser definido com a variável especial$/
beasy
@ Gilles: Mas usando awkevitar passar o fluxo duas vezes para tr. Então, seria ainda mais lento?
precisa saber é o seguinte
2
@ user285259 Normalmente não. tré muito rápido e o tubo pode até ser paralelo.
Gilles
110

Para um arquivo tão grande, uma possibilidade é o Flex. Let unk.lbe:

%%
\<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
JJoao
fonte
5
makepossui regras padrão para isso, em vez do flex / cc, você pode adicionar um %option maincomo a primeira linha de unk.l e depois apenas make unk. Eu uso mais ou menos reflexivamente %option main 8bit faste tenho export CFLAGS='-march=native -pipe -Os'no meu .bashrc.
jthill
11
@undercat: Se não estivesse fora do tópico, eu poderia mostrar uma série de aplicativos front-end não-compiladores, desde a solução do problema no nível da água até a análise de entradas para fins especiais. É incrível o que você pode fazer com ele, se você pensar fora da caixa um pouco :-)
jamesqf
@jthill, obrigado: %option main+ make+ opcionalmente CFLAGSsão um truque muito bom !! O -march=nativecomportamento padrão é?
JJoao
11
@ jamesqf como você disse - será difícil fazer disso uma questão de tópico - mas eu gostaria de vê-lo também #
Steven Penny
11
@jamesqf Um professor meu da uni usou o flex para criar uma ferramenta que reconheceu os tipos de tecido para uma fábrica! Que tal perguntar algo como: "flex parece ser uma ferramenta muito poderosa, mas é improvável que eu esteja escrevendo compiladores / analisadores - existem outros casos de uso para flex?"
Paul Evans
40

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

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

#!/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):])
sourcejedi
fonte
Se Meu sistema tiver cerca de 4 GB de memória livre conseqüente dos 8 GB, mem = mmap.mmap (sys.stdin.fileno (), 0, acesso = mmap.ACCESS_READ) significa que ele coloca os dados nesse espaço? Ou seria muito inferior (1gb?)>
Rahul
11
@Rahul "Então você não tem RAM suficiente, mas em um sistema de 64 bits, você tem espaço de endereço virtual suficiente para mapear o arquivo inteiro." É paginado dentro e fora da memória RAM sob demanda (ou falta dela). Este programa deve funcionar sem exigir grande quantidade de RAM física. Os sistemas de 64 bits possuem muito mais espaço de endereço virtual do que o máximo de RAM física. Além disso, cada processo em execução possui seu próprio espaço de endereço virtual. Isso significa que o sistema como um todo ficar sem espaço de endereço virtual não é uma coisa, não é um conceito válido.
sourcejedi
4
@Rahul yep! python mmap.mmap () é um invólucro bastante fino em torno da função C mmap (). E mmap () é o mesmo mecanismo usado para executar executáveis ​​e código de bibliotecas compartilhadas.
sourcejedi
2
@jamesqf Eu posso estar errado, mas acho que é apenas uma escolha pessoal. Como as perdas de desempenho seriam insignificantes (porque, como ele disse, a função real chama a função c), o desperdício de sobrecarga é muito baixo, uma vez que nenhuma outra coisa está acontecendo no meio. C teria sido melhor, mas esta solução não estava buscando otimização, apenas para resolver o problema maior e difícil de 70 GB.
Rahul
11
Em geral, escrever em python é mais compacto. Nesse caso, verificou-se que existem alguns detalhes na versão python, e a versão C pode ter sido melhor para escrever. (Embora não seja tão simples se searchpode conter um caractere NUL. E notei que a outra versão C aqui não suporta caracteres NUL replace.). Você pode obter a versão C para fins de comparação. No entanto, lembre-se de que minha versão inclui um relatório básico de erros para as operações que realiza. A versão C seria pelo menos mais chata de ler IMO, quando o relatório de erros estiver incluído.
precisa saber é o seguinte
16

Há um replaceutilitário no pacote mariadb-server / mysql-server. Ele substitui cadeias simples (não expressões regulares) e, diferentemente do grep / sed / awk, replacenão se importa com \ne \0. O consumo de memória é constante em qualquer arquivo de entrada (cerca de 400kb na minha máquina).

Claro que você não precisa rodar um servidor mysql para usá- replacelo, ele é empacotado dessa maneira no Fedora. Outras distribuições / sistemas operacionais podem ser embalados separadamente.

legolegs
fonte
16

Eu 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 as sugestões dos comentários. Também foi corrigido o erro com o padrão <<unk>.

Patrick Bucher
fonte
2
você pode imprimir (padrão [j]) em vez de (buf [j]) (eles são iguais neste momento, portanto você não precisa de buffer)
RiaD
3
o código também não funcionará para a string "<" ideone.com/ncM2yy
RiaD
10
30 MB em 0,3 segundos? Isso é apenas 90 MB / segundo. memcpyvelocidade (ou seja, o gargalo de memória) é algo como 12 GB / segundo em uma CPU x86 recente (por exemplo, Skylake). Mesmo com a sobrecarga de chamada do sistema stdio +, para um arquivo de 30 MB quente no cache do disco, eu esperaria talvez 1 GB / segundo para uma implementação eficiente. Você compilou com a otimização desativada ou a E / S de um caracter por vez é realmente lenta? getchar_unlocked/ putchar_unlockedPode ajudar, mas definitivamente melhor para leitura / gravação em blocos de talvez 128kiB (metade do tamanho do cache L2 na maioria das CPUs x86, para que principalmente atingido na L2 ao loop depois de ler)
Peter Cordes
2
do alto da minha cabeça, getchar e putchar são lentos.
Rui F Ribeiro
3
O fixprograma para "<<unk>"ainda não funcionará se o patterninício for uma sequência repetida de caracteres (ou seja, não funcionaria se você estivesse tentando substituir o aardvark por zebra e tivesse entrada de aaardvak ou se estivesse tentando substituir ababc e teve entrada de abababc). Em geral, você não pode avançar pelo número de caracteres que leu, a menos que saiba que não há possibilidade de uma correspondência começar nos caracteres que você leu.
icarus
14

O GNU greppode mostrar o deslocamento de correspondências em arquivos "binários", sem a necessidade de ler linhas inteiras na memória. Você pode usar ddpara ler esse deslocamento, pular a partida 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 ddaumentar a velocidade, dividi a leitura em um tamanho grande de bloco 1048576 e uma leitura menor de 1 byte por vez, mas essa operação ainda será um pouco lenta em um arquivo tão grande. A grepsaída é, por exemplo,, 13977:<unk>e isso é dividido em dois pontos pela leitura em variáveis offsete pattern. Temos que acompanhar posquantos bytes já foram copiados do arquivo.

meuh
fonte
11

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

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

Aqui, o fold pega até 1024 bytes, mas o -s garante que ele se quebre em um espaço se houver pelo menos um desde a última interrupção.

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

Em seguida, o comando tr "desdobra" o arquivo, convertendo as novas linhas que foram inseridas novamente em nada.

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

Aqui está um exemplo dividido por cada etapa que converte todos os Ns 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' '\0'
test XJS C4JD QADn1 nSBn3 2IDnEn GTUBE STAnDARD AnTI UBE-TEST EMAIL*C.34X test

Você precisará adicionar uma nova linha no final do arquivo, se houver uma, porque o comando tr a removerá.

alfreema
fonte
11
Como você garante que não está quebrando o padrão em casos extremos onde não há espaço em branco suficiente disponível?
rackandboneman
11
Como afirmado, para que isso seja robusto, é necessário que exista pelo menos um espaço a cada X caracteres. Você pode fazer essa análise com bastante facilidade, com qualquer tamanho de bloco que desejar: fold -w X mailtest.txt | grep -v "" | wc -l O número retornado é o número de linhas dobradas com possíveis arestas. Se for zero, é garantido que a solução funcione.
Alfreema
10

Usando perl

Gerenciando seus próprios buffers

Você pode usar IO::Handle's setvbufpara gerenciar os buffers padrão ou gerenciar seus próprios buffers com sysreade syswrite. Verifique perldoc -f sysreade, perldoc -f syswritepara obter mais informações, essencialmente eles ignoram o buffer io.

Aqui rolamos nossa própria E / S de buffer, mas fazemos isso manualmente e arbitrariamente em 1024 bytes. Também abrimos o arquivo para o RW, então fazemos tudo no 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ê estiver indo por esta rota

  1. Certifique-se <unk>e <raw_unk>são do mesmo tamanho byte.
  2. Convém garantir que nosso método em buffer não ultrapasse os CHUNKSIZElimites, se você estiver substituindo mais de 1 byte.
Evan Carroll
fonte
2
E se <unk>cair em um limite entre pedaços?
liori 02/01
8

Você pode tentar o bbe ( editor de bloco binário ), um " sedpara arquivos binários".

Tive um bom sucesso usando-o em um arquivo de texto de 7 GB sem EOLcaracteres, substituindo várias ocorrências de uma string por uma de comprimento diferente. Sem tentar qualquer otimização, obteve uma taxa de transferência média de processamento de> 50MB / s.

ovirt
fonte
5

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

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

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

Stéphane Chazelas
fonte
Eu também estava pensando sobre esse método, mas usando o while read -N 1000 chunk;(o 1000escolhido como exemplo). A solução para <unk>, dividida entre os pedaços, é duas passagens pelo arquivo: a primeira com os pedaços de 100 MB e a segunda com os pedaços de '100 MB + 5 bytes'. Mas não é a solução ideal no caso do arquivo de 70GB.
MiniMax
3
Você nem precisa de dois passes. Leia o bloco A. Embora não seja EOF, leia o bloco B. Pesquisar / Substituir em A + B. A: = B. Loop. A complexidade é garantir que você não substitua dentro da substituição.
roaima
@MiniMax, essa segunda passagem não ajudaria necessariamente, pois a primeira passagem teria adicionado 5 bytes para cada ocorrência de <unk>.
Stéphane Chazelas
11
@roaima, sim, isso seria uma solução muito mais envolvida. Aqui está uma abordagem simples que é altamente provável (supondo que as <unk>ocorrências sejam muito diferentes, se não, use $/ = ">"e s/<unk>\z/<raw_unk>/g) de estar correta.
Stéphane Chazelas
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)
    }
}

Apenas construa go build unk.goe execute como ./unk <input >output.

EDITAR:

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

EDIÇÃO II:

Aplicou a mesma correção do programa C.

Patrick Bucher
fonte
11
isso evita a leitura de todo o arquivo na memória?
cat
11
Ele lê o arquivo caractere por caractere e nunca retém o arquivo inteiro na memória, apenas caracteres individuais.
Patrick Bucher
11
scanner.Split(bufio.ScanRunes)faz a mágica.
Patrick Bucher
Verifique também go doc bufio.MaxScanTokenSizeo tamanho padrão do buffer.
Patrick Bucher
Como seu Cprograma, isso não funciona para substituir o aardvark por zebra por uma entrada de aaardvark.
icarus
1

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

O tutorial oficial em https://hadoop.apache.org/docs/stable/hadoop-mapreduce-client/hadoop-mapreduce-client-core/MapReduceTutorial.html usa Java (extremamente simples), mas você pode encontrar bibliotecas clientes para Perl ou qualquer idioma que você queira usar.

Portanto, se, posteriormente, você descobrir que está executando operações mais complexas em arquivos de texto de 7000 GB - e precisando fazer isso 100 vezes por dia -, poderá distribuir a carga de trabalho entre vários nós que você provisiona ou que são provisionados automaticamente por uma nuvem - cluster Hadoop baseado em

Sam Rahimi
fonte
11
sim Sim é isso. "Não use o Hadoop - seus dados não são tão grandes" . Este é um problema muito simples de streaming IO.
precisa saber é o seguinte
0

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

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

2a) Existem múltiplas ocorrências? 2b) Se sim, você sabe quantos?

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

Eu proporia uma solução (provavelmente em C) que leria os BLOCOS do arquivo pesquisando cada uma pela string, levando em consideração o possível cruzamento de blocos. Uma vez encontrada, substitua a string pelo mesmo comprimento alternativo e escreva apenas esse BLOCK. Continuando pelo número conhecido de ocorrências ou até o final do arquivo. Isso exigiria apenas o número de gravações de ocorrências e no máximo duas vezes isso (se todas as ocorrências fossem divididas em 2 blocos). Isso não exigiria espaço adicional!

DGerman
fonte
-1

Se tivermos um valor mínimo de <unk>(como esperado pela lei de Zipf),

awk -v RS="<unk>" -v ORS="<raw_unk>" 1
JJoao
fonte
11
Não. sedLê uma linha de cada vez na memória, independentemente. Não poderá caber nesta linha.
Kusalananda
11
Não consigo encontrar documentação que diga algo diferente de que o GNU sednão fará buffer de entrada / saída ao usar esse sinalizador. Não vejo que ele leia linhas parciais.
Kusalananda