-1

我需要审查所有出现的带有 * 的单词列表。我的列表中有大约 400 个单词，它会受到大量流量的影响，所以我想让它变得非常高效。什么是有效的算法/数据结构来做到这一点？最好是已经在 Python 中的东西。

例子：

  1. “小便” => “**** 关闭”
  2. “你好” => “你好”
  3. “去地狱” => “去地狱”
4

5 回答 5

1

不区分大小写的trie支持的集合实现可能符合要求。对于每个单词，您只会处理最少的字符。例如，您只需处理单词“zoo”的第一个字母，就可以知道该单词不在您的列表中（假设您没有“z”脏话）。

然而，这是没有与 python 打包的东西。您可能会从简单的字典解决方案中观察到更好的性能，因为它是用 C 实现的。

于 2012-08-28T03:02:12.227 回答
0

就像chechen 提到的那样，aTrie可能是您需要的东西，实际上，您应该使用Aho–Corasick 字符串匹配算法。比尝试更多的东西。

对于每个字符串，假设S您需要处理，时间复杂度大约为O(len(S)). 我的意思是，线性

并且您最初需要构建自动机，它的时间复杂度是O(sigma(len(words)))，而空间复杂度大约是（不太总是）O(52*sigma(len(words)))这里52表示字母的大小（我认为它是['a'..'z', 'A'..'Z']）。您只需执行一次（或每次系统启动时）。

于 2012-08-28T13:25:16.250 回答
0

您可能希望针对其他人对基于正则表达式的解决方案进行计时。我之前使用过类似的基于正则表达式的文本替换一到三千个单词来将短语更改为链接，但我没有将这些页面提供给很多人。

我取出一组单词（可能是短语），并从中形成一个正则表达式，由于'\b'，它将匹配它们在文本中作为一个完整单词的出现。

如果您有字典将单词映射到其净化版本，那么您可以使用它。为了方便起见，我只是用“*”交换每个奇怪的字母。

sanitizer 函数只返回任何匹配的脏话的净化版本，并在文本的正则表达式替换调用中使用以返回净化版本。

import re
swearwords = set("Holy Cow".split())
swear = re.compile(r'\b(%s)\b' % '|'.join(sorted(swearwords, key=lambda w: (-len(w), w))))
sanitized = {sw:''.join((ch if not i % 2 else '*' for i,ch in enumerate(sw))) for sw in swearwords}

def sanitizer(matchobj):
    return sanitized.get(matchobj.group(1), '????')

txt = 'twat prick Holy Cow ... hell hello shitter bonk'
swear.sub(sanitizer, txt)
# Out[1]: 'twat prick H*l* C*w ... hell hello shitter bonk'

您可能希望使用 re.subn 和 count 参数来限制完成的替换次数，如果它有太多亵渎的话，就拒绝整个文本：

maxswear = 2
newtxt, scount = swear.subn(sanitizer, txt, count=maxswear)
if scount >= maxswear: newtxt = 'Ouch my ears hurt. Please tone it down' 
print(newtxt)
# 'Ouch my ears hurt. Please tone it down'
于 2012-08-28T07:04:32.827 回答
0

(1) 令 P 为要审查的短语集。

(2) 预计算 H = {h(w) | p in P, w 是 p} 中的一个词，其中 h 是一个明智的散列函数。

(3)对于输入的每个单词v，测试h(v)是否在H中。

(4) 如果 h(v) 不在 H 中，则发出 v。

(5) 如果 h(v) 在 H 中，则退回到任何简单的方法，该方法将检查 v 和后面的单词是否在 P 中形成一个短语。

步骤（5）不是问题，因为我们假设 P 与输入量相比（非常）小。步骤 (3) 是 O(1) 操作。

于 2012-08-28T03:44:12.243 回答
-1

如果性能是您想要的，我建议：

  • 获取输入样本
  • 计算每行被删词的平均数量
  • 定义每行过滤的最大单词数（例如 3 个）
  • 计算样本中哪些被删减的词命中率最高
  • 编写一个给定审查词的函数，将生成一个带有 IF 语句的 python 文件来检查每个词，将“最热门”的词放在第一位，因为你只想匹配整个词，这将相当简单
  • 一旦达到每行的最大数量，退出函数

我知道这不好，我只是建议这种方法，因为流量很大，对列表中的每个单词进行循环将对性能产生巨大的负面影响。

希望对您有所帮助或至少给您一些关于如何解决问题的开箱即用的想法。

于 2012-08-28T03:09:22.843 回答