Заменить строку в огромном (70 ГБ), одной строке, текстовом файле

126

У меня есть огромный (70 ГБ), одна строка , текстовый файл, и я хочу заменить строку (токен) в нем. Я хочу заменить токен <unk>другим фиктивным токеном ( проблема с перчатками ).

Я пробовал sed:

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

но выходной файл corpus.txt.newимеет нулевые байты!

Я также пытался использовать Perl:

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

но я получил ошибку нехватки памяти.

Для файлов меньшего размера обе вышеуказанные команды работают.

Как мне заменить строку таким файлом? Это связанный вопрос, но ни один из ответов не сработал для меня.

Изменить : Как насчет разделения файла на куски по 10 ГБ (или что-то еще) каждый и применения sedк каждому из них, а затем объединить их с cat? Имеет ли это смысл? Есть ли более элегантное решение?

Христос Базиотис
источник
Как заметил @Gilles, вы можете обнаружить какой-нибудь повторяющийся символ, который мог бы послужить пользовательским разделителем в вашей большой строке?
РоманПерехрест
Я думаю, что инструмент, который может только выполнять поиск и замену, но не более сложное регулярное выражение, будет быстрее. Также было бы не выгодно делать строки за раз, поэтому не захлебнулся бы этим файлом. К сожалению, я не имею представления о существовании такого инструмента, хотя написать его было бы несложно. Если это один раз, то замена символов новой строки, как в одном из ответов, вероятно, будет проще всего.
Ctrl-Alt-Delor
Содержит ли ваш файл что-то кроме ASCII? Если это так, вся обработка Юникода может быть опущена, и необработанные байты могут быть обработаны.
Патрик Бухер
Я согласен с @PatrickButcher Посмотрите на картину в целом. Помимо срочной необходимости заменить этот текст, для чего еще этот файл должен использоваться? Если это какой-то журнал, никто не сможет эффективно с ним работать. Если это файл данных, который используется каким-либо приложением, то это приложение должно нести ответственность за сохранение данных в этом файле.
Томас Карлайл
2
Вы можете использовать splitс -bопцией, определяющей размеры файла чанка в байтах. Обработайте каждый по очереди, используя sedи собирая заново. Существует риск того, что <unk>его можно разделить на два файла и не найти ...
Владислав Довгальец

Ответы:

106

Обычные инструменты обработки текста не предназначены для обработки строк, которые не помещаются в ОЗУ. Они имеют тенденцию работать, читая одну запись (одну строку), манипулируя ею и выводя результат, затем переходя к следующей записи (строке).

Если есть символ ASCII, который часто появляется в файле и отсутствует в <unk>или <raw_unk>, то вы можете использовать его как разделитель записей. Поскольку большинство инструментов не допускают использование пользовательских разделителей записей, поменяйте местами этот символ и символы новой строки. trобрабатывает байты, а не строки, поэтому не имеет значения размер записи. Предположим, что ;работает:

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

Вы также можете привязать первый символ искомого текста, предполагая, что он не повторяется в тексте поиска и появляется достаточно часто. Если файл может начинаться с unk>, измените команду sed, sed '2,$ s/…чтобы избежать ложного совпадения.

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

В качестве альтернативы используйте последний символ.

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

Обратите внимание, что этот метод предполагает, что sed работает незаметно для файла, который не заканчивается новой строкой, то есть обрабатывает последнюю частичную строку, не обрезая ее и не добавляя заключительный символ новой строки. Работает с GNU sed. Если вы можете выбрать последний символ файла в качестве разделителя записей, вы избежите проблем переносимости.

жилль
источник
8
У меня нет такого файла для тестирования, но в Awk вы можете указать «Разделитель записей» и «Разделитель записей вывода». Итак, если в вашем файле есть приличное количество запятых, возможно, вам удастся решить эту проблему следующим образом: awk -v RS=, -v ORS=, '{gsub(/<unk>/, "<raw_unk>"); print}' Нет?
Wildcard
4
@Wildcard Да, это еще одно решение. Awk, как правило, медленнее, чем sed, поэтому я не предлагаю его в качестве предпочтительного решения для огромного файла.
Жиль
Вы можете установить разделитель записей в Perl с параметром командной строки -0и восьмеричным значением символа, или же внутри скрипта его можно установить с помощью специальной переменной$/
beasy
@ Жиль: Но с помощью awkизбегайте передачи потока дважды tr. Так будет ли это еще медленнее?
user285259
2
@ user285259 Обычно нет. trочень быстро и трубу можно даже распараллелить.
Жиль
110

Для такого большого файла одна возможность - Flex. Позвольте unk.lбыть:

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

Затем скомпилируйте и выполните:

$ flex -o unk.c  unk.l
$ cc -o unk -O2 unk.c -lfl
$ unk < corpus.txt > corpus.txt.new
JJoao
источник
5
makeдля этого есть правила по умолчанию, вместо flex / cc вы можете добавить в %option mainкачестве первой строки unk.l, а затем просто make unk. Я более-менее рефлексивно пользуюсь %option main 8bit fast, и имею export CFLAGS='-march=native -pipe -Os'по моему .bashrc.
до
1
@undercat: Если бы это не было не по теме, я мог бы показать вам ряд некомпонентных приложений, от решения проблемы уровня воды до специального анализа ввода. Удивительно, что вы можете с этим сделать, если немного подумать нестандартно :-)
jamesqf
@ jthill, спасибо: %option main+ make+ CFLAGSэто очень хороший трюк !! Является ли -march=nativeповедение по умолчанию?
JJoao
1
@jamesqf, как вы сказали - будет трудно сделать это по теме вопроса - но я бы тоже хотел это увидеть
Стивен Пенни
1
@jamesqf Мой профессор из универа использовал flex для создания инструмента, который распознавал бы типы тканей для фабрики! Как насчет того, чтобы спросить что-то вроде: «flex кажется очень мощным инструментом, но я вряд ли буду писать какие-либо компиляторы / парсеры - есть ли другие варианты использования для flex?»
Пол Эванс
40

Таким образом, у вас недостаточно физической памяти (ОЗУ) для одновременного хранения всего файла, но в 64-разрядной системе у вас достаточно виртуального адресного пространства для сопоставления всего файла. Виртуальные отображения могут быть полезны как простой взлом в таких случаях.

Все необходимые операции включены в Python. Есть несколько раздражающих тонкостей, но при этом не нужно писать C-код. В частности, необходимо соблюдать осторожность, чтобы не копировать файл в память, что могло бы полностью устранить проблему. С другой стороны, вы получаете сообщения об ошибках бесплатно (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
источник
Если в моей системе около 4 ГБ свободной памяти из 8 ГБ, значит ли это, что mem = mmap.mmap (sys.stdin.fileno (), 0, access = mmap.ACCESS_READ) означает, что она помещает данные в это пространство? Или это будет намного ниже (1 ГБ?)>
Рахул
1
@Rahul "Так что у вас недостаточно оперативной памяти, но в 64-битной системе у вас достаточно виртуального адресного пространства для сопоставления всего файла." По требованию (или без таковой) он выгружается в физическую память и из нее. Эта программа должна работать, не требуя большого объема физической оперативной памяти. 64-разрядные системы имеют гораздо больше виртуального адресного пространства, чем максимальный физический объем памяти. Также каждый запущенный процесс имеет свое собственное виртуальное адресное пространство. Это означает, что система в целом исчерпывает виртуальное адресное пространство - это не вещь, это недопустимая концепция.
sourcejedi
4
@Rahul да! python mmap.mmap () - довольно тонкая оболочка для функции C mmap (). И mmap () - это тот же механизм, который используется для запуска исполняемых файлов и кода из общих библиотек.
sourcejedi
2
@jamesqf Я могу ошибаться, но я чувствую, что это просто личный выбор. Поскольку потери производительности были бы пренебрежимо малы (потому что, как он сказал, фактическая функция вызывает функцию c), непроизводительные потери очень малы, поскольку между ними не происходит никаких других вещей. C был бы лучше, но это решение не было направлено на оптимизацию, просто чтобы решить большую и сложную проблему 70 ГБ.
Рахул
1
В общем, написание на Python более компактно. В этом случае оказалось, что в Python-версии есть пара деталей, и C-версию лучше написать. (Хотя это не так просто, если searchможет содержать символ NUL. И я заметил, что другая версия C здесь не поддерживает символы NUL replace.). Вы можете получить версию C для сравнения. Однако помните, что моя версия включает базовые отчеты об ошибках для выполняемых операций. Версия C будет, по крайней мере, более раздражающей для чтения IMO, если в нее включены отчеты об ошибках.
Sourcejedi
16

В replaceпакете mariadb-server / mysql-server есть утилита. Он заменяет простые строки (не регулярных выражений) и в отличие от Grep / SED / AWK replaceне заботится о \nи \0. Потребление памяти постоянно с любым входным файлом (около 400 КБ на моей машине).

Конечно, вам не нужно запускать сервер mysql для его использования replace, он упакован таким образом только в Fedora. Другие дистрибутивы / операционные системы могут быть упакованы отдельно.

legolegs
источник
16

Я думаю, что версия C может работать намного лучше:

#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;
}

РЕДАКТИРОВАТЬ: Изменено в соответствии с предложениями из комментариев. Также исправлена ​​ошибка с рисунком <<unk>.

Патрик Бухер
источник
2
вы можете напечатать (pattern [j]) вместо (buf [j]) (они равны на данный момент, поэтому вам не нужен буфер
RiaD
3
также код не будет работать для строки «<< unk
RiaD
10
30 МБ за 0,3 секунды? Это всего лишь 90 МБ / с. memcpyСкорость (то есть узкое место в памяти) составляет что-то вроде 12 ГБ / с на недавнем процессоре x86 (например, Skylake). Даже с учетом издержек системного вызова stdio + для файла объемом 30 МБ, горячего в дисковом кеше, можно ожидать 1 ГБ / с для эффективной реализации. Вы компилировали с отключенной оптимизацией, или ввод-вывод по одному символу за раз действительно такой медленный? getchar_unlocked/ putchar_unlockedможет помочь, но определенно лучше читать / записывать порциями, может быть, 128 кБ (половина размера кэша L2 на большинстве процессоров x86, так что вы, в основном, работаете с L2 во время цикла после чтения)
Peter Cordes
2
от верхней части моей головы, GetChar и putchar является медленным.
Руи Ф Рибейро
3
fixК программе по - "<<unk>"прежнему не работает , если patternначинается с повторяющейся последовательностью символов (т.е. она не будет работать , если вы пытаетесь заменить Aardvark с зеброй и вы внесли свой вклад в aaardvak, или вы пытаетесь заменить ababc и был введен abababc). Как правило, вы не можете двигаться вперед по количеству прочитанных вами символов, если только вы не знаете, что совпадение, начинающееся с прочитанных вами символов, невозможно.
Икар
14

GNU grepможет показывать смещение совпадений в «двоичных» файлах, не считывая целые строки в памяти. Затем вы можете использовать ddдля считывания до этого смещения, пропустить совпадение, а затем продолжить копирование из файла.

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"

Для скорости я разделил ddна большое чтение размера блока 1048576 и меньшее чтение на 1 байт за раз, но эта операция все еще будет немного медленной для такого большого файла. grepВыход, например, 13977:<unk>и это делится на толстой кишке путем чтения в переменных offsetи pattern. Мы должны отслеживать, posсколько байтов уже скопировано из файла.

meuh
источник
11

Вот еще одна командная строка UNIX, которая может работать лучше, чем другие опции, потому что вы можете «искать» «размер блока», который работает хорошо. Чтобы это было надежно, вам нужно знать, что у вас есть хотя бы один пробел в каждых символах X, где X - ваш произвольный «размер блока». В приведенном ниже примере я выбрал «размер блока» из 1024 символов.

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

Здесь, fold будет захватывать до 1024 байтов, но -s гарантирует, что он будет разбит на пробел, если есть хотя бы один с момента последнего разрыва.

Команда sed ваша и делает то, что вы ожидаете.

Затем команда tr "раскроет" файл, преобразуя новые строки, которые были вставлены обратно, в ничто.

Вы должны попробовать использовать блоки большего размера, чтобы увидеть, работает ли он быстрее. Вместо 1024 вы можете попробовать 10240 и 102400 и 1048576 для опции -w сгиба.

Вот пример с разбивкой по каждому шагу, который преобразует все N в нижний регистр:

[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

Вам нужно будет добавить новую строку в самый конец файла, если он есть, потому что команда tr удалит его.

alfreema
источник
1
Как убедиться, что вы не нарушаете шаблон в крайних случаях, когда недостаточно свободного места?
сторожевик
1
Как уже говорилось, для того, чтобы это было устойчивым, требуется, чтобы в каждом символе X было хотя бы один пробел. Вы можете сделать этот анализ достаточно легко, с любым размером блока, который вы выберете: fold -w X mailtest.txt | grep -v "" | wc -l Возвращаемое число - это количество сложенных строк с потенциальными краями. Если оно равно нулю, решение гарантированно сработает.
Alfreema
10

С помощью perl

Управление своими собственными буферами

Вы можете использовать IO::Handles setvbufдля управления буферами по умолчанию, или вы можете управлять своими собственными буферами с помощью sysreadи syswrite. Проверьте perldoc -f sysreadи perldoc -f syswriteдля получения дополнительной информации, по существу, они пропускают буферизованные io.

Здесь мы запускаем наш собственный буферный ввод-вывод, но мы делаем это вручную и произвольно на 1024 байтах. Мы также открываем файл для RW, поэтому делаем все это одновременно на одном и том же FH.

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++;
}

Если вы собираетесь идти по этому маршруту

  1. Убедитесь в том , <unk>и <raw_unk>имеют тот же размер байт.
  2. Возможно, вы захотите убедиться, что наш буферизованный метод не пересекает CHUNKSIZEграницу, если вы заменяете более 1 байта.
Эван Кэрролл
источник
2
Что делать, если <unk>падает на границу между кусками?
Лиори
8

Вы можете попробовать bbe ( редактор двоичных блоков ), « sedдля двоичных файлов».

Я имел хороший успех, используя его в текстовом файле размером 7 ГБ без EOLсимволов, заменив несколько вхождений строки одной длины. Без попыток какой-либо оптимизации средняя скорость обработки составила> 50 МБ / с.

ovirt
источник
5

С помощью perlвы можете работать с записями фиксированной длины, такими как:

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

И надеюсь, что <unk>эти две записи по 100 МБ не будут охватывать вас.

Стефан Шазелас
источник
Я также думал об этом методе, но использовал while read -N 1000 chunk;( 1000выбранный в качестве примера). Решение <unk>, разбитое между блоками, состоит в двух проходах по файлу: первый с блоками 100 МБ, а второй с блоками «100 МБ + 5 байт». Но это не оптимальное решение в случае файла 70 ГБ.
MiniMax
3
Вам даже не нужно два прохода. Прочитать блок A. Пока не EOF, прочитать блок B. Найти / заменить в A + B. A: = B. Петля. Сложность гарантирует, что вы не замените внутри замены.
roaima
@MiniMax, этот второй проход не обязательно помог бы, так как первый проход добавил бы 5 байтов для каждого вхождения <unk>.
Стефан
1
@roaima, да, это было бы гораздо более сложным решением. Вот это простой подход , который является лишь весьма вероятным (предполагая , что <unk>вхождения далеко аппарт, если нет, то используйте $/ = ">"и s/<unk>\z/<raw_unk>/g) быть правильным.
Стефан
5

Вот небольшая программа Go, которая выполняет задачу ( 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)
    }
}

Просто создайте его go build unk.goи запустите как ./unk <input >output.

РЕДАКТИРОВАТЬ:

Извините, я не читал, что все в одной строке, поэтому я пытался читать файл символ за символом.

РЕДАКТИРОВАТЬ II:

Применяется то же исправление, что и к программе на Си.

Патрик Бухер
источник
1
это позволяет избежать чтения всего файла в память?
кошка
1
Он читает файл символ за символом и никогда не хранит весь файл в памяти, только отдельные символы.
Патрик Бухер,
1
scanner.Split(bufio.ScanRunes)делает волшебство.
Патрик Бухер
Также проверьте go doc bufio.MaxScanTokenSizeразмер буфера по умолчанию.
Патрик Бухер
Как и ваша Cпрограмма, это не работает для замены aardvark на zebra с вводом aaardvark.
Икар
1

Это может быть излишним для файла объемом 70 ГБ и простым поиском и заменой, но среда Hadoop MapReduce решит вашу проблему прямо сейчас без каких-либо затрат (выберите опцию «Единый узел» при настройке для ее локального запуска) - и это может быть масштабируется до бесконечной емкости в будущем без необходимости изменять ваш код.

Официальное руководство по адресу https://hadoop.apache.org/docs/stable/hadoop-mapreduce-client/hadoop-mapreduce-client-core/MapReduceTutorial.html использует (чрезвычайно простую) Java, но вы можете найти клиентские библиотеки для Perl или какой бы язык вы не хотели использовать.

Таким образом, если позже вы обнаружите, что выполняете более сложные операции с текстовыми файлами объемом 7000 ГБ - и должны делать это 100 раз в день - вы можете распределить рабочую нагрузку по нескольким узлам, которые вы предоставляете или которые автоматически предоставляются вам облачным на основе кластера Hadoop.

Сэм Рахими
источник
1
да да это. «Не используйте Hadoop - ваши данные не такие большие» . Это очень простая проблема потокового ввода-вывода.
sourcejedi
0

Все предыдущие предложения требуют чтения всего файла и записи всего файла. Это не только занимает много времени, но и требует 70 ГБ свободного места.

1) Если я вас понимаю конкретный случай, правильно было бы приемлемо заменить <УНК> с какой-либо другой строки той же длины?

2а) Есть ли несколько случаев? 2b) Если да, то знаете, сколько?

Я уверен, что вы уже решили эту проблему года плюс, и я хотел бы знать, какое решение вы использовали.

Я бы предложил решение (скорее всего, на С), которое бы считывало БЛОКИ файла, ища по каждой строке, с учетом возможного пересечения блоков. Как только найден, замените строку с той же длины чередуется и записать только этот блок. Продолжая в течение известного числа случаев или до конца файла. Это потребует всего лишь записи числа событий и не более чем вдвое (если каждое вхождение было разделено между 2 блоками). Это не потребует никакого дополнительного места!

DGerman
источник
-1

Если у нас есть минимальное количество <unk>(как ожидается, согласно закону Ципфа),

awk -v RS="<unk>" -v ORS="<raw_unk>" 1
JJoao
источник
1
Нет, sedчитает строку за раз в памяти независимо. Он не сможет соответствовать этой линии.
Кусалананда
1
Я не могу найти документацию, которая говорит что-либо кроме того, что GNU sedне будет делать буферизацию ввода / вывода при использовании этого флага. Я не вижу, что он будет читать частичные строки.
Кусалананда