1

目录 D 包含几千封 .eml 格式的电子邮件。有些电子邮件是纯文本，有些来自 Outlook，有些则有 ASCII 标题和 HTML/MIME 内容等等。存在一个字典文件 F，其中包含要在 D 目录下的文件中查找的有趣单词列表（即 red\nblue\ngreen\n...）。D目录有大量子文件夹，但除上述.eml文件外没有其他文件。应使用以下规范列出最常出现的单词：

  • 对于每个有趣的单词，都应该提供有关它出现的次数和出现位置的信息。如果它在一个文件中出现多次，则应为该文件多次报告。报告发生意味着报告一个整数元组 (L,P)，其中 L 是从电子邮件源顶部开始的行号，P 是该行中发生的开始位置。

这将建立一个索引来引用不同的出现和最频繁出现的有趣单词的摘要。

输出应该在单个输出文件上，并且格式没有严格定义，只要包括上述信息：有趣的词，每个有趣的词出现的次数以及它出现的位置 -> 文件/行/开始位置。

这不是一个家庭作业，而是我想对一个相当大的数据集进行实际的文本分析。我面临的挑战是选择合适的工具进行有效过滤。一种迭代方法，即单词/电子邮件/等的笛卡尔积，速度太慢，因此需要为每个文件的每一行组合多个单词过滤。

我已经尝试从有趣的单词列表 w1|w2|w3|... 中构建替代正则表达式，编译它并在每封电子邮件的每一行运行它，但它仍然很慢，尤其是当我需要检查多个在一行中出现。

例子：

电子邮件 E 有一行包含以下文本：

^ ... blah ... 红苹果 ... 蓝色蓝莓 ... 红白蓝旗。$\n

正则表达式正确报告红色（2）和蓝色（2），但在使用真正的、非常大的有趣单词词典时速度很慢。

我尝试过的另一种方法是：

使用 Sqlite 数据库在解析令牌时将令牌转储到其中，包括每个条目的（列、位置）信息，并在最后查询输出。使用适当的内存缓冲区，批量插入有很大帮助，但会增加复杂性。

我还没有尝试过数据并行化，因为我不确定令牌/解析首先是正确的做法。也许一棵字母树会更合适？

我对以下解决方案感兴趣，按优先顺序排列：

  • Bash/GNU CLI 工具（尤其是通过 GNU 'parallel'可并行化的东西，仅用于 CLI 执行）
  • Python（自然语言处理？）
  • C/C++

不幸的是，没有 Perl，因为我不明白。

4

3 回答 3

2

一些备注：

  • 我们不希望按照“对所有电子邮件执行正则表达式搜索和 do_something();”之类的方式做一些事情。我可以想象大多数电子邮件的长度比有趣的单词列表要短，所以我会尝试单独处理每封电子邮件并提取必要的信息。
  • 构建一个专门的字符串数据结构（例如字符串 trie或三元搜索树）来快速查找一个词是否有趣。我在构建单词的三元搜索树方面有很好的经验，因为它可以快速查找单词。
  • 该算法将如下所示：

（当然是伪代码）

result <- empty list
for each email e:
    for each word w:
        if is_interesting_word(w, string_data_structure):
            add (filename, line_number, start_position, word) to results
  • 该问题现在非常适合使用MapReduce（例如Hadoop）等技术进行并行化。每封电子邮件都可以独立于其他电子邮件进行处理，并且不需要共享任何信息：可以在处理电子邮件之前计算字符串数据结构。在 map 步骤中，您从电子邮件中提取必要的信息，在 reduce 步骤中，您将每封电子邮件中的计算值合并到单个输出文件中。

我会减少您需要的处理量：没有正则表达式，没有高级解析；只需遍历电子邮件中的每个字符/行并跟踪您的位置（行号、位置等）。作为最后一步，分析您的代码并优化它的伤害:)

于 2012-06-11T19:41:42.533 回答
2

我假设您可以创建/找到一个 eml 到文本的转换器。那么这与您想要的非常接近：

find -type f | parallel --tag 'eml-to-text {} | grep -o -n -b -f /tmp/list_of_interesting_words'

输出未按您希望的方式 100% 格式化：

文件名 \t 行号：字节号（从文件开头）：字

如果您有很多有趣的单词，则“-f”中grep的启动速度很慢，因此如果您可以创建 maildir 的解压缩版本，则可以减少并行启动grep的次数：

find . -type f | parallel 'eml-to-text {} >/tmp/unpacked/{#}'
find /tmp/unpacked -type f | parallel -X grep -H -o -n -b -f /tmp/list_of_interesting_words

由于时间复杂度grep -f比线性更差，您可能希望将 /tmp/list_of_interesting_words 分割成更小的块：

cat /tmp/list_of_interesting_words | parallel --pipe --block 10k --files > /tmp/blocks_of_words

然后并行处理块和文件：

find /tmp/unpacked -type f | parallel -j1 -I ,, parallel --arg-file-sep // -X grep -H -o -n -b -f ,, {} // - :::: /tmp/blocks_of_words

此输出的格式如下：

文件名：行号：字节号（从文件开头）：字

要word通过排序而不是文件名管道将结果分组：

... | sort -k4 -t: > index.by.word

计算频率：

... | sort -k4 -t: | tee index.by.word | awk 'FS=":" {print $4}' | uniq -c

好消息是这应该相当快，我怀疑你是否能够使用 Python 达到同样的速度。

编辑：

grep -F 在启动时要快得多，并且您将需要 -w 用于 grep（因此“gram”这个词与“diagrams”不匹配）；这也将避免临时文件，并且可能相当快：

find . -type f | parallel --tag 'eml-to-text {} | grep -F -w -o -n -b -f /tmp/list_of_interesting_words' | sort -k3 -t: | tee index.by.word | awk 'FS=":" {print $3}' | uniq -c
于 2012-06-11T23:15:04.650 回答
0

Python：

list = ['a', 'bunch', 'of', 'interesting', 'words']
linepos = 0

with open("file") as f:
    for line in f:
        linepos += 1
        wordpos = 0
        for word in line.split():
            wordpos += 1
            if word in list:
                print "%s found at line %s, word %s" % (word, linepos, wordpos)
于 2012-06-11T19:57:23.227 回答