2

对于单个大文本（约 4GB），我需要搜索约 100 万个短语并将它们替换为补充短语。原始文本和替换文本都可以轻松放入内存中。天真的解决方案实际上需要数年才能完成，因为单个替换大约需要一分钟。

天真的解决方案：

for search, replace in replacements.iteritems():
    text = text.replace(search, replace)

使用的正则表达式方法re.sub要慢 x10：

for search, replace in replacements.iteritems():
    text = re.sub(search, replace, text)

无论如何，这似乎是一个使用 Boyer-Moore 弦或 Aho-Corasick 的好地方；但是这些方法因为它们通常被实现仅适用于搜索字符串而不是替换它。

或者，任何可以快速执行此操作的工具（Python 之外）也将受到赞赏。

谢谢！

4

4 回答 4

1

在python之外，sed通常用于这种事情。

例如（取自此处），将文件 sue.txt 中的“丑陋”一词替换为“美丽”：

sed -i 's/ugly/beautiful/g' /home/bruno/old-friends/sue.txt

您还没有发布任何代码分析，您应该在进行任何过早优化之前尝试一些时间。搜索和替换 4GB 文件中的文本是一项计算密集型操作。

替代方案 问：我应该这样做吗？-

您将在下面讨论在 10 毫秒内完成整个 Wikipedia 语料库的搜索和替换。这敲响了一些警钟，因为它听起来不像是伟大的设计。除非有明显的理由不让您修改用于呈现和/或加载的任何代码，以进行搜索和替换，因为正在加载/查看数据的子集。您不太可能对整个 4GB 数据执行许多操作，因此将您的搜索和替换操作限制在您实际处理的范围内。此外，您的时间仍然非常不精确，因为您不知道您正在处理的文件有多大。

最后一点，您注意到：

加速必须是算法而不是链接数百万个 sed 调用

但是您表示您正在使用的数据是“单个大文本（〜4GB）”，因此如果我正确理解您的意思，则不应涉及任何更改。

更新： 您在下面指出对 ~4KB 文件（我假设）执行操作需要 90 秒，这对我来说似乎很奇怪 - sed 操作通常不会花费任何时间。如果文件实际上是 4MB（我希望），那么评估应该需要 24 小时（不理想但可能可以接受？）

于 2013-09-05T20:49:31.043 回答
1

可能有比这更好的方法：

re.sub('|'.join(replacements), lambda match: replacements[match.group()], text)

这会进行一次搜索，但它不是一个非常有效的搜索。re2模块可能会大大加快速度。

于 2013-09-05T20:58:43.537 回答
1

我也有这个用例，我需要对 Wikipedia 的全文进行大约 100,000 次搜索和替换操作。使用sed,awk或perl将需要数年时间。我找不到任何搜索和替换的 Aho-Corasick 实现，所以我写了自己的：fsed。该工具恰好是用 Python 编写的（因此您可以根据需要破解代码），但它被打包为一个命令行实用程序，运行方式类似于sed.

您可以通过以下方式获得它：

pip install fsed
于 2015-12-18T13:20:59.103 回答
0

它们通常仅用于搜索字符串而不是替换它

完美，这正是你需要的。在 4G 文本中使用无效算法进行搜索已经够糟糕了，但进行多次替换可能更糟糕……您可能需要移动数千兆字节的文本，以便为源文本和目标文本的大小差异导致的扩展/收缩腾出空间.

只需找到位置，然后将零件与替换零件连接起来。

所以一个愚蠢的类比是"_".join( "a b c".split(" ") )，但你当然不想像这样创建副本split。

注意：有什么理由在 python 中这样做？

于 2013-09-05T20:52:30.570 回答