Эффективная работа с (и генерированием) больших текстовых файлов

Ответ 1

Введение

То, что я предложу, отличается от большинства предложенных ранее предложений и основано на комбинации индексирования, хэш-таблиц, упакованных массивов, Compress,.mx файлов и DumpSave и нескольких других вещей. Основная идея заключается в предварительной обработке файла в интеллектуальном ключе и сохранении предварительно обработанных определений в файле .mx для быстрой загрузки. Вместо того, чтобы основывать большую часть работы на чтении с диска, я предлагаю сместить акценты и выполнять большую часть работы в памяти, но найти способы загрузки данных с диска, сохранения их в ОЗУ, работы с данными и сохранения его на диске как во времени, так и в памяти - эффективно. Стремясь достичь этой цели, я буду использовать большинство эффективных конструкций Mathematica, о которых я знаю, как для работы в памяти, так и для взаимодействия с файловой системой.

Код

Вот код:

Clear[words];
words[text_String] :=  ToLowerCase[StringCases[text, WordCharacter ..]];

(* Rules to replace words with integer indices, and back *)
Clear[makeWordIndexRules];
makeWordIndexRules[sym_Symbol, words : {__String}] :=
   With[{distinctWords = DeleteDuplicates[words]},
    sym["Direct"] = Dispatch[Thread[distinctWords -> Range[Length[distinctWords]]]];
    sym["Inverse"] = Dispatch[Thread[ Range[Length[distinctWords]] -> distinctWords]];
    sym["keys"] = distinctWords;
];

(* Make a symbol with DownValues / OwnValues self - uncompressing *)
ClearAll[defineCompressed];
SetAttributes[defineCompressed, HoldFirst];
defineCompressed[sym_Symbol, valueType_: DownValues] :=
  With[{newVals = 
     valueType[sym] /.
       Verbatim[RuleDelayed][
         hpt : Verbatim[HoldPattern][HoldPattern[pt_]], rhs_] :>
            With[{eval = [email protected]}, hpt :> (pt = [email protected] eval)]
        },
        ClearAll[sym];
        sym := (ClearAll[sym]; valueType[sym] = newVals; sym)
];


(* Get a list of indices corresponding to a full list of words in a text *)
Clear[getWordsIndices];
getWordsIndices[sym_, words : {__String}] :=
    Developer`ToPackedArray[words /. sym["Direct"]];

(* Compute the combinations and their frequencies *)
Clear[getSortedNgramsAndFreqs];
getSortedNgramsAndFreqs[input_List, n_Integer] :=
   Reverse[#[[Ordering[#[[All, 2]]]]]] &@ Tally[Partition[input, n, 1]];


(* 
 ** Produce n-grams and store them in a hash-table. We split combinations from
 ** their frequencies, and assume indices for input, to utilize packed arrays 
 *)
Clear[produceIndexedNgrams];
produceIndexedNgrams[sym_Symbol, input_List, range : {__Integer}] :=
 Do[
   With[{ngramsAndFreqs = getSortedNgramsAndFreqs[input, i]},
     sym["NGrams", i] = Developer`ToPackedArray[ngramsAndFreqs[[All, 1]]];
     sym["Frequencies", i] =  Developer`ToPackedArray[ngramsAndFreqs[[All, 2]]]
   ],
   {i, range}];


(* Higher - level function to preprocess the text and populate the hash - tables *)
ClearAll[preprocess];
SetAttributes[preprocess, HoldRest];
preprocess[text_String, inputWordList_Symbol, wordIndexRuleSym_Symbol,
    ngramsSym_Symbol, nrange_] /; MatchQ[nrange, {__Integer}] :=
  Module[{},
    Clear[inputWordList, wordIndexRuleSym, ngramsSym];
    inputWordList = [email protected];
    makeWordIndexRules[wordIndexRuleSym, inputWordList];
    produceIndexedNgrams[ngramsSym,
    getWordsIndices[wordIndexRuleSym, inputWordList], nrange]
  ];

(* Higher - level function to make the definitions auto-uncompressing and save them*)
ClearAll[saveCompressed];
SetAttributes[saveCompressed, HoldRest];
saveCompressed[filename_String, inputWordList_Symbol, wordIndexRuleSym_Symbol, 
   ngramsSym_Symbol] :=
Module[{},
   defineCompressed /@ {wordIndexRuleSym, ngramsSym};
   defineCompressed[inputWordList, OwnValues];
   DumpSave[filename, {inputWordList, wordIndexRuleSym, ngramsSym}];
];

Вышеупомянутая функциональность очень голодна: для обработки файла @Ian в какой-то момент потребовалось почти 5 ГБ ОЗУ. Тем не менее, это того стоит, и можно также протестировать выше с меньшими файлами, если не хватает ОЗУ. Как правило, большие файлы можно разделить на несколько частей, чтобы обойти эту проблему.

Предварительная обработка и сохранение в оптимизированном формате

Теперь мы начнем. Предварительная обработка занимает около минуты на моей машине:

test = Import["C:\\Temp\\lowered-text-50.txt", "Text"];

In[64]:= preprocess[test,inputlower,wordIndexRules,ngrams,{2,3}];//Timing
Out[64]= {55.895,Null}

Символы inputlower, wordIndexRules, ngrams здесь представляют собой некоторые символы, которые я выбрал для использования в списке слов в файле и для хеш-таблиц. Вот несколько дополнительных входов, иллюстрирующих использование этих символов и что они означают:

In[65]:= ByteCount[inputlower]
Out[65]= 459617456

In[69]:= inputlower[[1000;;1010]]
Out[69]= {le,fort,edmonton,le,principal,entrepôt,de,la,compagnie,de,la}

In[67]:= toNumbers = inputlower[[1000;;1010]]/.wordIndexRules["Direct"]
Out[67]= {58,220,28,58,392,393,25,1,216,25,1}

In[68]:= toWords =toNumbers/. wordIndexRules["Inverse"]
Out[68]= {le,fort,edmonton,le,principal,entrepôt,de,la,compagnie,de,la}

In[70]:= {ngrams["NGrams",2],ngrams["Frequencies",2]}//Short
Out[70]//Short= {{{793,791},{25,1},{4704,791},<<2079937>>,{79,80},{77,78},{33,34}},{<<1>>}}

Основная идея здесь заключается в том, что мы используем целочисленные индексы вместо слов (строк), что позволяет нам использовать упакованные массивы для n-граммов.

Сжатие и сохранение занимает еще полминуты:

In[71]:= saveCompressed["C:\\Temp\\largeTextInfo.mx", inputlower, 
      wordIndexRules, ngrams] // Timing
Out[71]= {30.405, Null}

Результирующий файл .mx составляет около 63 МБ, что соответствует размеру исходного файла. Обратите внимание, что поскольку часть того, что мы сохраняем, является (самосжатой) переменной inputlower, которая содержит все входные слова в исходном порядке, мы не теряем никакой информации по сравнению с исходным файлом. В принципе, с этого момента можно начать работу только с новым .mx файлом.

Работа с оптимизированным файлом

Теперь мы начинаем новый сеанс, покидая ядро. Для загрузки файла почти нет времени (формат .mx чрезвычайно эффективен):

In[1]:= Get["C:\\Temp\\largeTextInfo.mx"] // Timing
Out[1]= {0.016, Null}

Загрузка списка слов занимает некоторое время (саморазжатие):

In[2]:= inputlower//Short//Timing
Out[2]= {6.52,{la,présente,collection,numérisée,<<8000557>>,quicktime,3,0}}

но мы ничего не используем - он хранится на всякий случай. Загрузка 2-граммов и их частот:

In[3]:= Timing[Short[ngrams2 = {ngrams["NGrams",2],ngrams["Frequencies",2]}]]
Out[3]= {0.639,{{{793,791},{25,1},{4704,791},<<2079937>>,{79,80},{77,78},{33,34}},{<<1>>}}}

Обратите внимание, что большую часть времени здесь проводилось на саморазгружающее, которое является выборочным (так, например, ngrams["NGrams",3] все еще сжато). Загрузка 3-граммов и их частот:

In[4]:= Timing[Short[ngrams3 = {ngrams["NGrams",3],ngrams["Frequencies",3]}]]
Out[4]= {1.357,{{{11333,793,11334},{793,11334,11356},<<4642628>>,{18,21,22},{20,18,21}},{<<1>>}}}

Тайминги достойны, учитывая размер списков. Обратите внимание, что ни DumpSave - Get, ни Compress - Uncompress распаковать упакованные массивы, поэтому наши данные хранятся в памяти Mathematica довольно эффективно:

In[5]:= Developer`PackedArrayQ/@ngrams3
Out[5]= {True,True}

Здесь мы разжимаем правила, связывающие индексы со словами:

In[6]:= Timing[Short[wordIndexRules["Inverse"]]]
Out[6]= {0.905,Dispatch[{1->la,2->présente,<<160350>>,160353->7631,160354->jomac},-<<14>>-]}

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

Эффективная работа с несжатыми данными

Если мы попытаемся найти, например, все позиции 2 грамма с частотой 1, наивный способ:

In[8]:= Position[ngrams["Frequencies",3],1,{1}]//Short//Timing
Out[8]= {1.404,{{870044},{870045},{870046},<<3772583>>,{4642630},{4642631},{4642632}}}

Однако мы можем использовать тот факт, что мы работаем с целыми индексами (вместо слов), хранящимися в упакованном массиве. Вот одна версия пользовательской функции позиции (из-за Норберта Позара):

extractPositionFromSparseArray[HoldPattern[SparseArray[u___]]] := {u}[[4, 2, 2]]; 
positionExtr[x_List, n_] := 
    extractPositionFromSparseArray[SparseArray[Unitize[x - n], Automatic, 1]]

Используя это, мы получаем его в 10 раз быстрее (можно использовать скомпилированную функцию C, которая еще в два раза быстрее):

In[9]:= positionExtr[ngrams["Frequencies",3],1]//Short//Timing
Out[9]= {0.156,{{870044},{870045},{870046},<<3772583>>,{4642630},{4642631},{4642632}}}

Вот еще несколько удобных функций:

Clear[getNGramsWithFrequency];
getNGramsWithFrequency[ngramSym_Symbol, n_Integer, freq_Integer] :=
  Extract[ngramSym["NGrams", n], positionExtr[ngramSym["Frequencies", n], freq]];

Clear[deleteNGramsWithFrequency];
deleteNGramsWithFrequency[{ngrams_List, freqs_List}, freq_Integer] :=  
    Delete[#, positionExtr[freqs, freq]] & /@ {ngrams, freqs};

deleteNGramsWithFrequency[ngramSym_Symbol, n_Integer, freq_Integer] :=  
   deleteNGramsWithFrequency[{ngramSym["NGrams", n], ngramSym["Frequencies", n]}, freq];

Используя это, мы можем получить много вещей довольно эффективно. Например, удалите 2 грамма с частотой 1:

In[15]:= deleteNGramsWithFrequency[ngrams,2,1]//Short//Timing
Out[15]= {0.218,{{{793,791},{25,1},{4704,791},<<696333>>,{29,66},{36,37},{18,21}},{<<1>>}}}

Или, 2 грамма с частотами менее 100 (это неоптимальный способ сделать это, но все равно довольно быстро):

In[17]:= (twogramsLarger100 = 
  Fold[deleteNGramsWithFrequency,deleteNGramsWithFrequency[ngrams,2,1],Range[2,100]])
  //Short//Timing
Out[17]= {0.344,{{{793,791},{25,1},{4704,791},{25,10},<<6909>>,
  {31,623},{402,13},{234,25}},{<<1>>}}}

Основная идея состоит в том, что целочисленные индексы играют роль "указателей" для слов, и большинство вещей можно сделать с ними. При необходимости мы можем вернуться к нормальным словам:

In[18]:= twogramsLarger100/.wordIndexRules["Inverse"]//Short//Timing
Out[18]= {0.063,{{{of,the},{de,la},<<6912>>,{société,du},{processus,de}},{<<1>>}}}

Заключительные замечания

Ускорение, достигнутое здесь, кажется существенным. Можно контролировать, сколько ОЗУ занято данными, загружая данные в мелкозернистые куски. Само использование памяти было чрезвычайно оптимизировано за счет использования упакованных массивов. Экономия памяти на диске обусловлена ​​комбинацией Compress и DumpSave. Хэш-таблицы, Dispatch -ed правила и саморазжатие являются методами, используемыми, чтобы сделать его более удобным.

Здесь много места для дальнейших уточнений. Можно разделить данные на более мелкие куски и сжать/сохранить их отдельно, чтобы избежать использования высокой памяти на промежуточных этапах. Можно также разделить данные в соответствии с частотными диапазонами и сохранить данные так, чтобы они были разделены на отдельные файлы, чтобы ускорить этап загрузки/самораспаковывания. Для многих файлов нужно было бы обобщить это, поскольку здесь использовались глобальные символы для хэшей. Это кажется хорошим местом для применения некоторых методов ООП. Как правило, это всего лишь отправная точка, но мое сообщение заключается в том, что такой подход ИМО имеет хороший потенциал для эффективной работы с такими файлами.

Ответ 2

Эти слайды - это лучшая мудрость в отношении того, как справляться с импортом и работой с большими наборами данных:

http://library.wolfram.com/infocenter/Conferences/8025/

Он охватывает некоторые темы, упомянутые здесь, и дает некоторые графики, которые покажут вам, какую скорость вы можете ожидать от перехода от импорта.

Ответ 3

Это мои предложения:

• Я предлагаю использовать ReadList[file, Word]. Обычно это намного быстрее, чем Import. Это также сломает его на слова.

• Вы также можете работать с файлами, сжатыми gzip. Import/Export поддерживают их легко, но ReadList нет. Для операций с ограничением на диске это будет фактически быстрее, чем чтение/запись несжатых данных.

• Ваш Sort может быть медленным (я не тестировал ваши операции с большими файлами, поэтому я не уверен). Смотрите вчера вопрос о том, как это сделать быстро.

Вы не можете выйти из Tally до его завершения, но вы всегда можете использовать Select, Cases или DeleteCases, чтобы обрезать список bigram перед экспортом.

Наконец, в качестве ответа на ваш последний вопрос: я боюсь, что Mathematica эффективна/удобна в работе, когда вы загружаете все данные в память. Система, похоже, задумана, чтобы хорошо работать с данными в памяти. Это из личного опыта.

РЕДАКТИРОВАТЬ Работа с вашим 50 МБ текстовым файлом медленная, но все же переносимая на моей (довольно старой и медленной) машине. Просто убедитесь, что вы используете SortBy:

In[1]:= $HistoryLength = 0; (* save memory *)

In[2]:= Timing[
 data = ReadList["~/Downloads/lowered-text-50.txt", Word, 
    WordSeparators -> {" ", "\t", ".", ","}];]

Out[2]= {6.10038, Null}

In[3]:= Timing[counts = [email protected][data, 2, 1];]

Out[3]= {87.3695, Null}

In[4]:= Timing[counts = SortBy[counts, Last];]

Out[4]= {28.7538, Null}

In[5]:= Timing[counts = DeleteCases[counts, {_, 1}];]

Out[5]= {3.11619, Null}

Я не мог получить ReadList для правильной обработки UTF-8, поэтому вам может потребоваться придерживаться Import.

Ответ 4

Чтобы расширить комментарий, сделанный мной, Read является полезной альтернативой ReadList или Import. Как и ReadList, вы указываете тип, и если вы укажете String, он будет читаться во всей строке. Таким образом, вы можете обрабатывать весь файл, по одной (или более) строкам за раз. Единственная трудность состоит в том, что вам нужно следить за EndOfFile вручную. Например,

strm = OpenRead[file];
While[ (line = Read[ str, String ]) =!= EndOfFile,
 (* Do something with the line *)
];
Close[ strm ];

Чтобы распространить это на несколько строк сразу, замените String выше на список длиной количества строк, которые вы хотите обработать, одновременно с String. Это лучше всего выполнить с помощью ConstantArray[String, n] для нескольких строк. Конечно, вместо этого можно использовать Word, чтобы обрабатывать файл на основе слова.

Обработка файлов по очереди имеет нижнюю сторону, если вам нужно Abort процесс, strm останется открытым. Итак, я предлагаю обернуть код в CheckAbort или используя описанную функциональность здесь.

Ответ 5

Вы можете посмотреть на String Patterns", которые являются версиями регулярных выражений Mathematica. Возможно, что-то вроде StringCases[data, RegularExpression["\\w+?\\W+?\\w+?"]], которое должно возвращать все соответствующие последовательности слова-пробельного слова. Я не могу сказать, будет ли это быстрее, чем ваш код раздела или нет.

В нижней части этой страницы есть "Советы по эффективному сопоставлению".

Вы можете применить "DeleteDuplicates" , чтобы обрезать список перед сортировкой.

Если бы я делал это на другом языке, я бы сохранил n-граммы в Hash Table с текстом как ключом, и экземпляр считается значением. Это будет хорошо работать с синтаксическим анализатором строк. Однако, кажется, использование Hash Table в Mathematica не является простым.

И одно замечание: вместо 4 проходов вы можете просто сгенерировать все 5 граммов в один файл и использовать простую текстовую обработку строки в командной строке, чтобы генерировать 2-, 3- и 4-граммы из этого файла. Конечно, это полезно только после того, как вы получите 5-граммовый экстрактор для запуска в разумные сроки.