Введение
То, что я буду предлагать, отличается от большинства предложений, приведенных ранее, и основано на комбинации индексации, хеш-таблиц, упакованных массивов, 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 = Compress@rhs}, hpt :> (pt = Uncompress@ 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 = words@text;
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 и самоудаление - это методы, используемые для того, чтобы сделать его более удобным.
Здесь достаточно места для дальнейших улучшений.Можно разделить данные на более мелкие порции и сжать / сохранить их отдельно, чтобы избежать высокого использования памяти на промежуточных этапах.Можно также разделить данные в соответствии с частотными диапазонами и сохранить данные, разделенные таким образом, в отдельные файлы, чтобы ускорить этап загрузки / самораспаковывания.Для многих файлов нужно было бы обобщить это, так как здесь использовались глобальные символы для хэшей.Это хорошее место для применения некоторых методов ООП.Как правило, это только отправная точка, но я считаю, что этот подход IMO имеет хороший потенциал для эффективной работы с такими файлами.