Sucha's Blog ~ Archive for June, 2020

20年6月21日 周日 11:39

Text Rank 算法

TextRank 是一种抽取式自动文摘算法,随便在网上搜一下相关,或者在 github 上面搜一下,介绍都一大把的。可是绝大部分的文章都只是堆 python 然后说要怎么做,也许是我的理解能力问题,在有限的几步里面,不晓得这么做的原因,会感觉很头疼。

这里尝试从大的方面还原这个算法,然后给出自己的实现,不过感觉自己的实现有些问题,效果没有想象中那么好,不过也总比没有强吧。

先开始吧。

TextRank 是一种抽取式的文章摘要算法,其最后的输出内容,都来源于文档本身的句子。这些句子会被算法打分排序,依靠的其实是 PageRank 算法。

PageRank

PageRank 算法原来只是为了描述网页间的重要程度,重要程度的计算,来源于他们间的超链接关系。简单的说,被链接得越多的页面,越重要,跟重要页面有链接的页面,比其他的页面更重要。准确分值的计算,是根据下面的公式来的:

img

其中,PR(Vi) 表示网页 Vi 的分值,In(Vi) 表示 PR(Vi) 包含的网页集合,Out(Vj) 表示 PR(Vi) 链接出去的网页集合,d 是链接传递系数或者说网页跳转的可能性,常用的值是 0.85。

可以把这个公式的计算基础描述成一张图,网页就是节点 PR(Vi),边就是跟 PR(Vi) 有关系的 PR(Vj) 链接集合。

初始化的时候,各个 PR(Vi) 的分值是不确定的,只有边的链接描述,因此需要迭代计算,比如都给各个 PR(Vi) 初始化为 1,通过公式多轮不断的迭代计算,当各个 PR(Vi) 分值稳定的时候,就是各个网页的 rank 分值。

Sentence simularity

如果把上面的 PR(Vi) 当成句子,我们就可以套用 PageRank 公式计算出句子的 rank 值,并提取重要程度高的句子作为文章摘要描述。

但是如何确定不同的句子有边的联系呢,算法提供了计算句子间相似程度这个标准,使用下面的公式:

img

其中 wk 是句子 Si 及 Sj 都有的公共词组,分母是词组的数量。当然,也可以用句子的余弦相似度来计算,但是词组本身就得包含向量值了,这些词组,可以称为 word vector。

Word Vector

词组在中文里涉及到分词,有不同的工具可以用来分词表来构建语料的词向量表,比如有的用 word2vec,有的用 GloVe。话说,除了上面的模型、算法之外,语料可是相当重要的基础资源呀。

这里当然还涉及到使用哪些范畴的语料来构建这个 word vector,这里不详细叙述了,因为网上相关资源就更多了。

最后

TextRank 算法应该就是上面这些了吧,虽然为了搞清楚查了很久,最后推一把自己堆的 text_rank,基于 LuaJIT 和 THULAC,随便跑起来,内存就占用了 1 个 G,搞不起搞不起。

20年6月6日 周六 19:29

Lua 的优点

接着上一篇 Lua 的缺点,作为平衡,这里补充一下。

作为一个普普通通,用过 ObjC、C/C++、Java、Swift、Emacs Lisp 的开发者,也是可以把 Lua 的一些好用的方面吹一下的。由于没用过 Python、Ruby、JavaScript,下面的观点未必就是 Lua 对比其他脚本语言鲜明的优点。

其实呢,我是将 Lua 跟上面所列的编译型、静态类型的语言做对比的,:)

Lua 是简单的

Lua 是命令式的语言,感觉以 C/C++、Java 起步的同学,学习 Lua 完全没有难度,Lua 语言没有几个关键字,控制结构甚至没有 continue。

而容器结构,只有一个 table,融合了 Array 以及 HashMap,当然,table 的作用不止于此,后面有更进一步的描述。

Lua 很小易于移植

Lua 语言只有核心部分,VM 代码只有几万行,是古老的 C89 语法,而且运行期的 VM 内存占用也不多,大概几百 kb 这样。

这使得 Lua 的编译安装是毫无难度的,支持 C89 的 C 编译器、硬件遍地都是。较少的资源消耗,意味着,在如今的操作系统上,可以大大方方的将几十、几百个 Lua VM 跑起来。

Lua 的核心还可以配置,将 Number 配置为 32bit 的 Integer,在低端没有浮点数的平台上,也能使用。好早之前,我就在 Rockchip 的的平台上应用上了 Lua,没有浮点数,Number 设置为了 32bit 的 Integer,用得好好的。

所以,不用担心写的纯 Lua 代码是不是在某些平台跑不起来,不存在的。

Lua 很稳定很快

Lua 生于 1993 年 7 月 28 日,语言核心早就稳定下来了,工业界早已采用多年。

LuaJIT 很快很快,可以看一下 LuaJIT-2.0 对比 Lua-5.1.5 版本的效率对比 Performance: x86/x64。如今 Redis、OpenResty 标配 LuaJIT 作为内建的脚本支持。

Lua 是动态类型的

写应用程序的同学都了解,声明一个变量再去声明类型是有多重复,所以最新的 C++、Swift 对于类型都是可以自动推断的了。

我是觉得对于模块化设计来说,类型只在模块输入、输出的时候才有作用,比如对于输入的数据,我要知道变量的大小和范围,这也是模块对于这个输入参数声明的支持范围。

但如果真的需要程序关心内存布局的时候,每一个变量需要多大的内存空间,才值得去斟酌,而类型,其实就是内存空间占用的映射。模块内部,既然都是可信的环境,用足够大的内存区域去持有这个变量就行了,这个不影响,反而少了类似 C 这样因为类型转换而截断,导致期望的判断没有成功,引起模块内部错误,不得不抛出异常或者出错,其实毫无必要。

从另外一方面说,如果有了静态类型,可以控制任何一段程序在变量传递、比较时候的范围,但是当我们需要更高程度的抽象的时候,就又涉及到了如何抽象类型,这又涉及到了模版、范型。感觉又复杂了,也许这是所有静态类型的语言,都绕不过去的一个弯吧。

Lua 支持多种编程模式

Lua 中可以加载一段 String、一个文件并运行,简单的语法,使得数据描述编程、数据驱动编程是完全可行的。比如我在 Lua 脚本中加载自己,在运行前修改其流程,再运行,是完全可行的。

Lua 的函数是一等公民,可以实现 lambada 算子,函数式编程妥妥的没问题。

Lua 可以实现面向对象编程,上面有提到 table,当在 Lua 里面实现面向对象的时候,对象实例其实就是一个 table,对象的属性只不过是 table 里面的一个 key,函数跟 Number、String 一样可以作为 key 的 value。

当这样调用对象方法时,table:func(value),func 默认第一个参数会传递 self,就是对象自己,一个 table,第二个参数才是 value。

理解 Lua 的面向对象编程,需要了解 Lua 内建的细节了,比如 table 的 __index key 是指找值的时候应该去哪里找,__newindex 则是创建新值的时候应该怎么做。多说一句,如果想 table 是 readonly 的,修改 table 的 __newindex 就对了。

下面是 Lua 的面向对象编程类定义的一个例子,a = Object.newObject(1), b = Object.newObject(2), a:isEqual(b) 将返回 false。

local Object = {
    value = 0
}
Object.__index = Object

function Object.newObject(value)
    local obj = setmetatable({}, Object)
    obj.value = value
    return obj
end

function Object:isEqual(obj)
    return self.value == obj.value
end

function Object:isGreater(obj)
    return self.value > obj.value
end

return Object

更进一步,Lua 的面向对象可以定制 __index 来实现单继承,甚至多继承,实例变量、类变量等,面向对象用这个库就对了 kikito/middleclass

Lua 元表

话说 table 在 Lua 中占据了中心位置,既是 Array 又是 HashMap,面向对象的时候又是对象实例本身,定义的时候用到了,实例运行期间也用到了。

table 有这么多的身份,定义不同身份时候的行为,成了关键。在 Lua 里面,table 的 key 怎么寻找,怎么设置新值,两个 table 之间怎么相加、相减等等,是通过定义 table 的 metatable (元表)来实现的。

面向对象的例子,就用了 Lua 的内建函数 setmetatable,定义了 Object.__index 的行为,限制 key 值应该在哪里寻找。

这里有一篇 Lua 元表 的教程。

多说两句吧,结合面向对象 Object 的例子,我们定义一下两个 Object 相加的行为:

local Object = {}
Object.__index = Object
Object.__add = function(oobj, nobj)
    oobj.value = oobj.value + nobj.value
    return oobj
end

这样,如果 a = Object.newObject(1), b = Object.newObject(2), a = a + b 后,a.value 等于 3。

话说连 java 都没能实现的运算符重载,Lua 通过 table 的 metatable 实现了。

Lua 跟 C 的交互

官方 Lua 跟 C 的交互,需要用到 Lua 的 C API 定义 Lua 可以使用的 C 库,在这一层 wrapper 中再调用其他编译、链接进来的其他库,可以看下这篇 Lua C API 研究 —— 基础篇,英文的 Exposing C functions to Lua

如果用的是 LuaJIT,对于已有 C 库的使用,就方便多了,用到了内建的 ffi 库来声明二进制库中声明的函数接口、用到的结构等,官方教程及例子 FFI Tutorial,这里不单独列举了。

--

Lua 作为一种简单、稳定、快速的命令式语言,提供高度的抽象,又可以很方便地使用已有的 C 库资源,对于我这种从 C/C++ 起步的程序员来说,相当友好。

酒醒了,吹一波不为过,:)

20年6月5日 周五 23:56

Lua 的缺点

在官网的 关于 Lua 页面,是这么介绍 Lua 的:

Lua 是一种强大、高效、轻量,可嵌入的脚本语言。支持过程编程,面向对象编程,函数式编程,数据驱动编程,以及数据描述编程。

虽然 Lua 官网将自己介绍为脚本语言,但业界对于 Lua 的定位及使用早已超出普通脚本的范围。比如,魔兽争霸 3,以及 Adobe 的 Lightmoom 都大量使用了 Lua 来构建桌面程序;在后端组件中大名鼎鼎的 Redis 以及 OpenResty,则将 Lua 作为了内嵌的业务处理语言;而在 github 上 star 数量为 9k 的 skynet,则更进一步地将 Lua 定位为了后端的业务逻辑语言。

虽然 Lua 运行很快,业界的效率标杆 LuaJIT 是所有其他脚本语言用于比对的塔顶,要不然 Redis、OpenResty 怎会将其作为内嵌的扩展方案呢。

但是 Lua 并没有流行开来,对于一个创建于 1993 年 7 月 28 日的语言来说,缺的应该不是机遇,而是其他的一些东西。

我也用了不少时间的 Lua,作为一名普通的应用程序开发者,就吐槽一下吧。

Lua 是分裂的

Lua 是分裂的,不说别的,单就官方版本的 Lua 5.3.5 以及 LuaJIT,其实是两种不同的语言,LuaJIT 定在了 Lua 5.1.5 版本,且大量应用在了 Redis 以及 OpenResty 中。

而且因为 Lua 的核心很小,大量的功能都用 C 或者 C++ 构建,通过 C API 提供给 Lua 虚拟机调用,但是不同 的 Lua 版本,其实 C API 差异很大,几乎就是不同的语言。

很多将 Lua 作为嵌入脚本语言的的桌面程序,将其使用的 Lua 版本固定下来了,其 C API 构建的 Lua 库也都固定了,其他版本的 Lua 可不一定能使用上这个库,而这个提供给 Lua 使用的 C 库,也不是向前向后兼容的。

Lua 是动态类型的

这是一个双刃剑,这里只说不好的方面吧。如果一个变量是从 dofile() 函数中加载的,由于事先不知道类型,我无法知道这个变量的结构里面有哪些东西,在智能补全的 IDE 里面,将导致无法补全内容,也会将错误放到运行时才暴露。

Lua 几乎没有官方的功能包

由于定为为可嵌入的脚本语言,核心很小,基础的东西缺少太多了,比如

仅有的语言核心,只有基本的输入输出,double 精度的数学操作而已。

Lua 没有官方的包管理器

Lua 没有官方的包管理器,这就导致了社区中好的库,应用实践,无法通过权威的渠道沉淀,并传递开来。随处可见普通的 Lua 用户将长时间将 Lua 作为普通的脚本语言,无法应用上顺手的包,解决眼前的问题。而对于高级一点的用户,也没有权威的渠道,来散播其创意和经验。

现有的官方的 Lua Users Wiki,真的弱爆了。推一下 LuaRocks 吧,还不错的。

Lua 没有官方的 IDE

IDE 是大大降低使用门槛的工具,也是大大提高开发效率的工具,结构化开发,断点调试,这些其他语言 IDE 中都有的东西,在 Lua 官方网站上,你是看不到的。

我自己倒是使用了 vs-code 配合 sumneko 的 lua-language-server 插件,之前也看了一下 ZeroBrane IDE,但没有用过。

Lua 不支持多线程

Lua 核心很小,C89 语法写成,没有规定运行平台,也就没有多线程支持这一说法了。

--

话说,喝了不少酒,吐了一下,舒服多了,:)