有效地使用(和生成)大型文本文件

Question

作为我工作的一部分,我正在处理非常大的文本文件,并在一定程度上分析它们的单词和短语频率.我遇到了计算时间,内存限制和提取相关信息的困难.

对于这个程序,我正在处理一个已经清理过的大文本文件(比如50MB),变成小写.但除此之外它只是非结构化的文本.我试图生成'bigrams','trigrams,'quadgrams'和'fivegrams'的列表 - 分别是经常出现的两个,三个,四个和五个单词短语的组合(即"我是"是一个二重奏,"我是自由的"是一个三元组,"我自由总是"是一个四元组".

我现在在做什么？

这是我当前的代码,其中inputlower是一个全小写字符串(使用Mathematica抓取的Web数据).

inputlower=Import["/directory/allTextLowered.txt"];
bigrams = 
  Sort[Tally[Partition[inputlower, 2, 1]], #1[[2]] > #2[[2]] &];
Export["/directory/bigrams.txt", bigrams];    
Clear[bigrams];
trigrams = 
  Sort[Tally[Partition[inputlower, 3, 1]], #1[[2]] > #2[[2]] &];
Export["/directory/trigrams.txt", trigrams];
Clear[trigrams];    
quadgrams = 
  Sort[Tally[Partition[inputlower, 4, 1]], #1[[2]] > #2[[2]] &];
Export["/directory/quadrams.txt", quadgrams];
Clear[quadgrams];
fivegrams = 
  Sort[Tally[Partition[inputlower, 5, 1]], #1[[2]] > #2[[2]] &];
Export["/directory/fivegrams.txt", fivegrams];

在某种程度上,它运作良好:我确实得到了生成的信息,并且在较小的尺度上,我发现这个代码工作得足够快,我可以得到一些近似于可行Manipulate[]程序的东西.但是,当我们处理大量投入时......

使用大文件时有什么问题？

最重要的是,我的输出文件太大而无法使用.有没有办法在代码中指定一个断点:例如,我不想要任何只出现一次的'bigrams'？如果证明仍然留下太多信息,是否有办法指明我不希望文件中有任何"bigrams",除非它们出现的次数超过10次？即如果"我的奶酪"出现20次,我想知道它,但如果"我垫"只出现一次,也许失去它会使文件更易于管理？

其次,这些过程需要很长时间:单独生成二元输出需要两到三个小时.我是否以有效的方式解决这个问题？

第三,如果我确实有一个包含所有信息的大型bigram文件(~650MB +),Mathematica是否有办法访问信息而不将其全部加载到内存中 - 即获取名为bigrams.txt的文件,了解它包含{{"i","am"},55}没有阻塞系统？

编辑

[截至12月7日,我删除了我提出的示例文件 - 再次感谢所有人]

Answer 1

介绍

我将提出的建议与之前给出的大多数建议不同,并且基于索引,散列表,打包数组Compress,.mx文件和DumpSave其他一些内容的组合.基本思想是以智能方式预处理文件,并将预处理的定义保存在.mx文件中以便快速加载.我建议转移重音,并在内存中完成大部分工作,而是找到从磁盘加载数据,将其存储在RAM中,处理数据并保存数据的方法,而不是将大部分工作基于磁盘读取.在磁盘上的时间和内存 - 高效的方式.在尝试实现这一目标时,我将使用我所知道的大多数高效的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的文件,它在某些时候占用了近5Gb的RAM.但是,这是值得的,如果没有足够的RAM,也可以用较小的文件测试上面的内容.通常,大文件可以分成几个部分,以解决此问题.

以优化格式预处理和保存

我们现在开始.我的机器上的预处理大约需要一分钟:

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-gram.

压缩和保存需要另外半分钟:

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

生成的.mx文件大约为63MB,大小与原始文件大小相当.请注意,由于我们保存的部分是一个(自压缩)变量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>>-]}

这足以开始处理数据,但在下一节中,我将概述一些关于如何使这项工作更有效的提示.

使用未压缩数据高效工作

例如,如果我们试图找到频率为1的2克的所有位置,那么天真的方式是这样的:

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

但是,我们可以利用我们使用存储在打包数组中的整数索引(而不是单词)的事实.这是自定义位置函数的一个版本(由于Norbert Pozar):

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];

使用它,我们可以非常有效地获得许多东西.例如,删除频率为1的2克:

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

或者,频率小于100的2克(这是执行此操作的次优方式,但它仍然非常快):

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

结束语

这里实现的加速似乎很大.通过以细粒度块的形式加载数据,可以控制数据占用的RAM量.通过利用打包数组,内存使用本身已经得到了极大的优化.在磁盘上的存储器的节省是由于组合Compress和DumpSave.散列表,Dispatch-ed规则和自解压是用于使其更方便的技术.

这里有足够的空间供进一步改进.可以将数据拆分为较小的块并单独压缩/保存,以避免在中间步骤中使用高内存.还可以根据频率范围分割数据,并将数据保存为单独的文件,以加快加载/自解压阶段.对于许多文件,需要对此进行概括,因为这里使用了哈希的全局符号.这似乎是应用一些OOP技术的好地方.一般来说,这只是一个起点,但我的信息是,这种方法IMO具有很高的潜力,可以有效地处理这些文件.

Answer 2

这些幻灯片是目前处理导入和处理大量数据的最佳智慧:

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

它涵盖了这里提到的一些主题,并给出了一些图表,它们将向您展示从切换进入后可以获得多少加速.

Answer 3

这些是我的建议:

1. 我建议使用ReadList[file, Word].通常比它快得多Import.这也会将其分解为单词.

2. 您也可以考虑使用gzip压缩文件. Import/ Export无缝支持这些,但ReadList不支持.对于磁盘限制操作,这实际上比读取/写入未压缩数据更快.

3. 你的Sorts可能很慢(我没有用大文件测试你的操作,所以我不确定). 看看昨天关于如何快速做到这一点的问题.

你不能Tally在它完成之前突破,但你总是可以使用Select,Cases或DeleteCases在导出之前修剪二元组列表.

最后,作为对上一个问题的回答:我担心Mathematica只有在您将所有数据加载到内存中时才有效/方便.该系统似乎被认为仅适用于内存数据.这来自个人经验.

编辑 使用50 MB的文本文件很慢,但在我的(相当旧的和慢的)机器上仍然可以忍受.只要确保你使用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 = Tally@Partition[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那里.

Answer 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,或使用此处描述的功能.