我正在为范围连接语法编写 CKY 解析器。我想使用树库作为语法,所以语法会很大。我已经用 Python 编写了一个原型(prototype) 1,当我模拟几十个句子的树库时,它似乎工作得很好,但内存使用是 Not Acceptable 。我尝试用 C++ 编写它,但到目前为止,这非常令人沮丧,因为我以前从未使用过 C++。这是一些数据(n 是语法所基于的句子数):
n mem
9 173M
18 486M
36 836M
考虑到最佳优先算法,这种增长模式是可以预期的,但开销的数量是我关注的问题。根据 heapy 的内存使用量比这些数字小十倍,valgrind 报告了类似的情况。是什么导致了这种差异,我可以在 Python(或 Cython)中做些什么?也许是因为碎片化?或者可能是python词典的开销?
一些背景:两个重要的数据结构是将边映射到概率的议程和图表,这是一个将非终结符和位置映射到边的字典。该议程是通过一个 heapdict(内部使用一个 dict 和一个 heapq 列表)来实现的,该图表带有一个将非终结符和位置映射到边的字典。议程经常被插入和删除,图表只能插入和查找。我用这样的元组表示边:
(("S", 111), ("NP", 010), ("VP", 100, 001))
字符串是语法中的非终结符标签,位置被编码为位掩码。当成分不连续时,可以有多个头寸。所以这条边可以代表对“is Mary happy”的分析,其中“is”和happy都属于VP。图表字典由这条边的第一个元素(“S”,111)索引案例。在新版本中,我尝试转置此表示,希望由于重用而节省内存:
(("S", "NP", "VP), (111, 100, 011))
我认为如果第一部分与不同位置组合出现,Python 只会存储一次,尽管我实际上不确定这是真的。在任何一种情况下,它似乎都没有任何区别。
所以基本上我想知道是否值得进一步追求我的 Python 实现,包括使用 Cython 和不同的数据结构做事情,或者用 C++ 从头开始编写它是唯一可行的选择。
更新 :经过一些改进后,我不再遇到内存使用问题。我正在开发优化的 Cython 版本。我将奖励最有用的建议,以提高代码的效率。 http://student.science.uva.nl/~acranenb/plcfrs_cython.html 有一个带注释的版本
1 https://github.com/andreasvc/disco-dop/
-- 运行 test.py 来解析一些句子。需要 python 2.6、nltk 和 heapdict
最佳答案
不必要:
>>> ("S", "NP", "VP") is ("S", "NP", "VP")
False
您可能想要
intern
引用非终端的所有字符串,因为您似乎在 rcgrules.py
中创建了很多这些。如果你想 intern
一个元组,那么先把它变成一个字符串:>>> intern("S NP VP") is intern(' '.join('S', 'NP', 'VP'))
True
否则,您将不得不“复制”元组而不是重新构建它们。
(如果您是 C++ 的新手,那么在其中重写这样的算法不太可能提供很大的内存优势。您必须首先评估各种哈希表实现并了解其容器中的复制行为。我已经发现
boost::unordered_map
有很多小哈希表非常浪费。)关于python - 概率解析器的内存使用,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/5379531/