文档相似度:高效地比较两个文档

Question

我有一个计算两个文档之间相似度的循环。它收集文档中的所有标记及其分数，并将它们放入字典中。然后对字典进行比较

这就是我到目前为止所做的，它是有效的，但是非常慢：

# Doc A
cursor1.execute("SELECT token, tfidf_norm FROM index WHERE doc_id = %s", (docid[i][0]))
doca = cursor1.fetchall()
#convert tuple to a dictionary
doca_dic = dict((row[0], row[1]) for row in doca)

#Doc B
cursor2.execute("SELECT token, tfidf_norm FROM index WHERE doc_id = %s", (docid[j][0]))
docb = cursor2.fetchall()
#convert tuple to a dictionary
docb_dic = dict((row[0], row[1]) for row in docb)

# loop through each token in doca and see if one matches in docb
for x in doca_dic:
    if docb_dic.has_key(x):
        #calculate the similarity by summing the products of the tf-idf_norm 
        similarity += doca_dic[x] * docb_dic[x]
print "similarity"
print similarity

我对Python还很陌生，所以才会遇到这样的麻烦。我需要加快速度，任何帮助都将不胜感激。谢谢。

Answer 1

一个Python点：adict.has_key(k)在Python2.x中已经过时，在Python3.x中消失了。k in adict作为一个表达式从Python2.2开始就可以使用了；请使用它。它会更快(没有方法调用)。

任何语言的实用要点:遍历较短的字典。

合并后的结果：

if len(doca_dic) < len(docb_dict):
    short_dict, long_dict = doca_dic, docb_dic
else:
    short_dict, long_dict = docb_dic, doca_dic
similarity = 0
for x in short_dict:
    if x in long_dict:
        #calculate the similarity by summing the products of the tf-idf_norm 
        similarity += short_dict[x] * long_dict[x]

如果您不需要这两个字典来做任何其他事情，您可以只创建A字典，并在B (key，value)元组从B查询中弹出时遍历它们。在docb = cursor2.fetchall()之后，将以下所有代码替换为：

similarity = 0
for b_token, b_value in docb:
    if b_token in doca_dic:
        similarity += doca_dic[b_token] * b_value

替代上面的代码:这做了更多的工作，但它在C中做了更多的迭代，而不是Python，而且可能更快。

similarity = sum(
    doca_dic[k] * docb_dic[k]
    for k in set(doca_dic) & set(docb_dic)
    )

Python代码的最终版本

# Doc A
cursor1.execute("SELECT token, tfidf_norm FROM index WHERE doc_id = %s", (docid[i][0]))
doca = cursor1.fetchall()
# Doc B
cursor2.execute("SELECT token, tfidf_norm FROM index WHERE doc_id = %s", (docid[j][0]))
docb = cursor2.fetchall()
if len(doca) < len(docb):
    short_doc, long_doc = doca, docb
else:
    short_doc, long_doc = docb, doca
long_dict = dict(long_doc) # yes, it should be that simple
similarity = 0
for key, value in short_doc:
    if key in long_dict:
        similarity += long_dict[key] * value

另一个实际问题是:你还没有说它的哪一部分是慢的……做字典还是做选择？在脚本中添加一些time.time()调用。

考虑将所有工作都推到数据库中。下面的示例使用了硬连接的SQLite查询，但原理是相同的。

C:\junk\so>sqlite3
SQLite version 3.6.14
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table atable(docid text, token text, score float,
    primary key (docid, token));
sqlite> insert into atable values('a', 'apple', 12.2);
sqlite> insert into atable values('a', 'word', 29.67);
sqlite> insert into atable values('a', 'zulu', 78.56);
sqlite> insert into atable values('b', 'apple', 11.0);
sqlite> insert into atable values('b', 'word', 33.21);
sqlite> insert into atable values('b', 'zealot', 11.56);
sqlite> select sum(A.score * B.score) from atable A, atable B
    where A.token = B.token and A.docid = 'a' and B.docid = 'b';
1119.5407
sqlite>

有必要检查数据库表是否有适当的索引(例如，token上的表本身)……没有可用的索引是使SQL查询运行非常慢的好方法。

说明:在token上建立索引可能会使您现有的查询或“在数据库中完成所有工作”查询或两者都运行得更快，这取决于数据库软件中查询优化器的突发奇想和月相。如果您没有可用的索引，DB将读取表中的所有行--这是不好的。

创建索引：create index atable_token_idx on atable(token);

删除索引：drop index atable_token_idx;

(但一定要参考您的数据库的文档)

Answer 2

把一些工作推到数据库上怎么样？

使用join可以得到一个基本上是

    Token    A.tfidf_norm B.tfidf_norm
-----------------------------------------
    Apple      12.2          11.00
       ...
    Word       29.87         33.21
    Zealot      0.00         11.56
    Zulu       78.56          0.00

您只需扫描光标并执行操作。

如果您不需要知道一个单词是否在一个文档中，而在另一个文档中缺少，那么就不需要外连接，列表将是两个集合的交集。我上面包含的示例自动为两个文档之一中缺少的单词分配"0“。看看你的“匹配”函数需要什么。

Answer 3

一个sql查询就可以完成这项工作：

SELECT sum(index1.tfidf_norm*index2.tfidf_norm) FROM index index1, index index2 WHERE index1.token=index2.token AND index1.doc_id=? AND index2.doc_id=?

只需替换“？”分别具有2个文档id。