Выполните много замен в текстовом файле, используя огромный список пар замены

Question

Дано:

• файл a.txt, содержащий много миллионов строк (скажем, одно предложение на строку) (2,6 ГБ!
• файл b.txt, содержащий 830 тыс. Строк с парами [word1] [word2]

Вопрос:

Как наиболее эффективно заменить каждое слово1 на слово2 для каждого из 830 тыс. Кортежей (w1, w2) в огромном текстовом файле?

Наивным методам, таким как sed, perl, python и т. Д., Потребуются недели для этого. Существуют ли (возможно, на основе распараллеливания) способы выполнения этой загрузки замен?

Answer 1

Я бы сделал это на python, но любой другой язык сработает, если вы правильно поймете алгоритм. Весь трюк состоит в том, чтобы сохранить пары слов (файл b.txt) в памяти и пройти через большой файл за один проход. Поскольку операция ввода-вывода выполняется намного медленнее, чем чтение из ОЗУ, производительность этого подхода будет O (file1) + O (file2)

В псевдокоде:

myMap = {}
for line in fileB:
  myMap[1st word of line] = 2nd word of line

for line in fileA
  for word in line
    if myMap contains word
      replace word with myMap[word]

Я полагаю, это самый быстрый способ, которым вы можете воспользоваться.

Answer 2

Я согласен с idrosid, ответившим о простой загрузке пар в память и последующей потоковой передаче по файлу. Если у вас действительно много данных (много гигабайт), и у вас нет машинных ресурсов, чтобы сделать это так быстро, как хотелось бы, новый сервис Amazon Elastic Hadoop будет хорошим решением. Если у вас есть простой исполняемый файл, работающий с небольшими файлами, было бы довольно просто масштабировать его до тонны данных с помощью инфраструктуры Hadoop Map Reduce.

Answer 3

Разделить файл на более мелкие куски. Скорее всего, вы израсходовали много места в памяти, ничего не делая, кроме сдвига битов в памяти или на диске.

Это похоже на то, как гораздо быстрее объединять / заменять массив строк, а не одну строку.

Единственная хитрость в том, чтобы убедиться, что место, где вы поместили разрыв в файл, не является хорошим совпадением, что относительно тривиально. На самом деле, если вы можете сделать это по линиям, это даже лучше, не нужно проверять совпадения.

Мне также кажется странным, что это займет недели PERL. Есть некоторые неподтвержденные данные, свидетельствующие о том, что он справится с этим менее чем за час:

• http://www.wellho.net/forum/Perl-Programming/replace-text-in-a-large-text-file.html
• http://muharem.wordpress.com/2008/04/30/text-filtering-with-erlang/

На самом деле, они говорят о файлах 1 Гб, занимающих 2 минуты во второй ссылке.

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

Answer 4

Сортировка списка поиска / замены пар по слову для поиска [word1]

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

Это должно быть достижимо.

Answer 5

Я бы сделал это в SQL.

Создать таблицу с двумя столбцами (dataline, sequence) и поместить в нее файл a.txt (одна строка на строку таблицы)

Затем создайте вторую таблицу, снова с двумя столбцами (word1 и word2) и прочитайте в нее b.txt (опять же, по одной строке на строку таблицы)

сгенерировать оператор обновления update table1 на основе table2

запустить оператор sql

когда она завершится, прочитайте первую таблицу обратно в файл