那么,屏蔽词系统到底该怎么做?

目录 算法

caoz 在最近一篇公众号文章《企业面试需要几轮》中提到一个面试问题:

大家都知道做互联网有很多屏蔽词要处理,那么需要对用户发布的内容,做屏蔽词过滤,先不考虑一些正则组合的情况,假设我有一个屏蔽词库,里面有几万条屏蔽词信息,然后我有个非常火爆的社区,每天用户产生海量内容,比如上百万篇文章或评论,现在我要求每篇文章都能快速通过屏蔽词库去检索,而且要求服务器可以支撑尽可能多的处理请求,毕竟这是成本啊。那么请设计一个屏蔽词过滤的算法逻辑。

碰巧我在面试中也喜欢问这个问题,可惜的是能答上来的的确不多。

单单从算法层面论,大概有 50% 的人能回答出来逐个进行 KMP 匹配(另外 50% 不知道什么是 KMP)。让他更进一步优化的话,20% 的人能想到一些粗糙的优化技巧,10% 的人能说出前缀树匹配。大部分能答出前缀树匹配的人会提到 AC 自动机,但只有一半能大概答出 AC 自动机的大概算法。到目前为止,还没有人回答过其它算法,比如 Rabin-Karp 或者 Commentz-Walter。

即使在算法层面上能回答出来 AC 自动机,在实现上候选人也只能形象地描述一下 Trie 树和失败指针,Trie 树的每一层使用一个 Set 或者哈希表数据结构。到目前为止,还没有人回答过用 Double Array 来实现 Trie,甚至连用前缀做 key 的一个大哈希表来模拟 Trie 树的优化也没有。虽然构造 Double Array Trie 的代价非常高,但内存占用非常小,检索效率也很高,特别适用于屏蔽词的场合。离线建好 Double Array Trie,推送到线上仅仅需要读入两个内存块就能完成更新,加载过程到了极简。

哪怕是回答出了高效的算法和实现,离一个真正有效的屏蔽词系统还相差很远。首先要清楚一件事,道高一尺,魔高一丈。你平时想过什么办法绕过屏蔽词系统,现在就得想办法对抗你曾经开过的脑洞。下面举几个最常见的例子:

  1. 简繁体混用,大小写混用,全半角混用。首先得做归一化,繁体转简体,大写转小写,全角转半角。
  2. 在屏蔽词中间加特殊字符。原串先过一遍,去掉特殊字符再过一遍。
  3. 字形相近,读音相似。积累相近字典,替换为常用字再过一遍,将所有的字转为拼音再过一遍。
  4. 同义词替换。加屏蔽词时考虑替换场景,或者挖掘替换词库用来替代。

上面这几种方法,说起来简单,做起来都是坑。一不小心,就把正常的内容当成包含屏蔽词干掉了。这就是为啥大家老吐槽在某些网站发帖,动不动就被屏蔽,关键就在于坏招太多,规则多了就有误伤啊!所以一个优秀的屏蔽词系统,还得尽量避免误伤情况,也有一些办法。

  • 先切词,如果命中屏蔽词的范围不在切词的边缘,应该是误伤。最简单的例子是:24口交换机。
  • 添加屏蔽词的例外规则,比如“成人牙刷”需要是“成人”的例外规则。

最近几年机器学习特别火,其实机器学习也特别适合这种场景,就是一个二分类问题嘛。只是超出了简单算法的范畴,这里就不展开了。

所以你看,就一个“屏蔽词过滤的算法逻辑”,就有那么多要探讨的东西。而且以目前国内大部分互联网产品的实现上来看,可能考虑的还没我这篇文章全面。这可真不是一个能轻松就回答完美的问题。

C++ 多线程调用 Lua 的正确姿势

目录 编程

上一篇文章《轻量级的 C++ Lua 传参方法 - Protobuf 反射》提到我正在 C++ 项目中使用简单的 Lua 脚本做一些灵活的程序逻辑,这样可以把多个 Lua 脚本放在数据库或者缓存里,根据不同的条件选择执行不同的脚本,而且可以在线更新这些脚本。

但在 C++ 项目中集成 Lua,遇到的第一个问题就是多线程问题。Lua 本身是不知晓宿主程序线程环境的,所以 lua_State 的多线程访问是不安全的。而多线程又是服务端程序的天然特性,我暂时还不想把所有逻辑都托管给 Lua,用它自己的多线程机制。所以看起来有下面几个选择:

一是把 Lua 脚本也看成是一个独立服务,通过 RPC 或者消息队列的方式去调用它,在 Lua 脚本内部处理性能问题。这样做相当于用 Lua 写了个服务,脚本复杂度比较高,偏离了我的本意。

二是在每个 C++ 线程里,都创建一个独立的 Lua VM。每个线程有自己的上下文,也自然就互不干扰了。这样做会浪费一些内存,但考虑到 Lua VM 几十 K 级别的大小,对服务端来说根本不算什么开销。但创建线程级的 Lua VM,内存管理上又有不同的方法。

__thread 修饰符只能约束 POD 变量,的确可以存 lua_State 指针,可是它不支持指针的销毁,必须自己额外管理 lua_State 对象,然后再把指针传给线程变量。thread_local 的确能支持复杂类型,可以在析构里销毁 lua_State,可又要求 C++11。思来想去,用pthread_key_create/delete + pthread_get/setspecific 是一个相对稳妥又较为简单的方法,即不用额外自动管理内存,又能实现在线程结束后自动析构线程自己的 Lua VM。

三是将 C++ 的线程与 Lua 的线程对应起来,使用同一个 Lua VM,但在每个 C++ 线程中都用lua_newthread 创建一个 Lua 线程 State 指针。不过在创建线程那一刻,仍然需要对主 lua_State 加锁。这其实相当于给每个 C++ 线程都创建了一个独立的 Lua 堆栈,这样在传参和执行脚本的时候就不担心有数据冲突。理论上来讲效果应该与二是类似的。

四是使用一个线程安全的对象池。将 lua_State 指针放到对象池里,需要的时候拿出来,用完再放回去,由对象池来管理创建和销毁。这就需要一个额外的内存管理容器,代码量大一些,只是对很多成熟的产品来说,可能本身就有这样的轮子。

考虑到代码量,复杂度等问题,我实际在项目中采取了二方案。不过我对 Lua 的了解还不深入,不知道是否还有更好的办法?

一种轻量级 C++ Lua 传参方法 - Protobuf 反射

目录 编程

虽然很多动态语言(例如 PHP)的性能在近些年有了大幅度的提升,也得到了更广泛的应用,但是在一些对性能要求比较严苛的场合,C/C++ 还是有着难以替代的优势。可 C/C++ 最大的缺点就是它的不够灵活,很小一点修改都必须得重新编译,部署,重启上线。为了增强 C/C++ 的灵活性,很多项目都选择嵌入 Lua 解析器来处理程序逻辑中的动态部分,我们也不例外。

目前我们对 Lua 的使用还是比较保守,主要是封装了一些基于特定条件的排序或者过滤规则。它的特点就是传入参数较多,但返回值特别少,基本上就是一个数字或者布尔值。最开始是使用的原始方法,手工去拼 Lua Table 作为传入参数,每加一个参数,就要手写几行添加元素的代码。最近我看到 brpc 里的 pb2json ,忽然想到完全可以用 Protobuf 的反射机制,自动拼 Lua Table。下面是基本类型的转换方法,当然,也可以用类似的方法对 Protobuf 的 map, message 等高级数据结构进行进一步封装。

void ProtoMessageToLuaTable(const google::protobuf::Message &message, lua_State *L) {
    lua_newtable(L);
    const Descriptor* descriptor = message.GetDescriptor();
    const Reflection* reflection = message.GetReflection();
    int field_count = descriptor->field_count();
    for (int i = 0; i < field_count; ++i) {
        const FieldDescriptor* field = descriptor->field(i);
        switch (field->type()) {
        case FieldDescriptor::TYPE_BOOL:
            lua_pushboolean(L, reflection->GetBool(message, field));
            break;
        case FieldDescriptor::TYPE_UINT32:
            lua_pushinteger(L, reflection->GetUInt32(message, field));
            break;
        case FieldDescriptor::TYPE_UINT64:
            lua_pushinteger(L, reflection->GetUInt64(message, field));
            break;
        case FieldDescriptor::TYPE_INT32:
        case FieldDescriptor::TYPE_SINT32:
            lua_pushinteger(L, reflection->GetInt32(message, field));
            break;
        case FieldDescriptor::TYPE_INT64:
        case FieldDescriptor::TYPE_SINT64:
            lua_pushinteger(L, reflection->GetInt64(message, field));
            break;
        case FieldDescriptor::TYPE_FLOAT:
            lua_pushnumber(L, static_cast<double>(reflection->GetFloat(message, field)));
            break;
        case FieldDescriptor::TYPE_DOUBLE:
            lua_pushnumber(L, reflection->GetDouble(message, field));
            break;
        case FieldDescriptor::TYPE_STRING:
            lua_pushstring(L, reflection->GetString(message, field).c_str());
            break;
        default:
            lua_pushnil(L);
            break;
        }
        lua_setfield(L, -2, field->name().c_str());
    }
}

其实调研了一下,发现还有一些其它的方法,比如 luabind, sol2一堆库。但这些工具更适合 C++ Lua 交互比较复杂的场合,而且也引入了额外的依赖和额外的要求(比如 C++11)。对于像我们这样的简单场景,在不引入更多依赖的情况下使用 Protobuf 反射机制,不失为一个好的选择。