存档在 ‘编程’ 分类

单文档与多文档新闻摘要

2013年6月3日

1、自动文摘技术

文档自动摘要技术的研究比较成熟,在年前Yahoo 已经收购了自动新闻摘要应用Summly,又使得自动摘要重新火了一把。在当前市场的比较热门的摘要有Summly、Clipped等国外使用较为广泛的app,最近国内的今日头条在新闻客户端上也加上了摘要内容。即刻新闻移动客户端在新的版本计划中也加上了摘要的内容,这里对新闻的单文档和多文档摘要进行了调研分析。主要概述的论文:http://www.cs.cmu.edu/~nasmith/LS2/das-martins.07.pdf

一般来讲,文档自动摘要分为Extractive和Abstractive两种方法,任务可以分为单文档与多文档摘要两种。

目前大多数的自动摘要都是以Extractive进行的,只是抽取的方法有所改进。有通过原文的句子进行抽取分析、语料库进行机器学习、建立语义网模型等抽取方法。

    基于Abstractive的方法也有很多人进行研究,基本思路是预先设计好一个模板,以及需要填充的字段。比如某新闻的发生时间、人物、地点等,利用计算机自动的在原文本中定位有关的信息片段,最后将这些片段填充到对应的模板的位置上。该方法能够产生较高质量的摘要,但是应用领域较为狭窄,模板不能统一。

2、单文档摘要技术

   一个较为简单的Extractive的单文档摘要生成方法如下所示:
  1. 对输入的文档进行分词处理,将一些停用词等与无关的词进行过滤
  2. 提取每一个句子里面的实词(专有名词、动词等),对于所有的实词进行计算相似度和同义词分析
  3. 对词义不同的词,计算其TF/IDF信息
  4. 计算每个句子在整篇文章中的权重、句子在段落中的权重、段落与段落直接的相似度
  5. 最后计算出每个句子在文档中的重要度,得到粗略的文摘
  6. 对句子与句子直接进行重复检查
  7. 最后得到整篇文摘的摘要

3、多文档摘要技术

    多文档摘要的抽取一般有如下几类:
  • 与单文档类似的方法
    • 通过计算词频、句子位置、主题词等抽取文档的重要内容,在通过多文档之间的相关性进行内容选择和过滤。
  • 采用Abstractive的方法
    • 从多个文档中提取信息填充到预先定制好的模板系统中。
  • 多文档集合判断的方法
    • 通过计算多文档的主题,作为该多文档的质心。判断文档中的句子与文档质心的距离,从而判断哪些句子比较重要。然后通过对句子安装相似程度进行聚类,最后从不同的类别中选取摘要句,从而减少摘要的冗余。

4、Summly的实现(猜测)

123
通过多次使用Summly,发现其是采用聚类分析后的新闻文档,然后选取与该topic中概括性(与topic的主题词、文档标题进行相似度计算)最大的段落作为摘要。
     缺陷:     很多时候选取的摘要部分是第一短内容。有的时候会出现与原文毫无关系的一段话,尤其是在体育新闻中。

5、Clipped的实现

2
   关于Clipped的自然语言处理原理,坦登告诉我们,Clipped能根据语法分析文本,并能识别哪种句子结构包含了最重要的信息。该算法通过分词标注器来分析一个句子,并能确定某一区块的信息与其他部分信息的依赖关系。通过统计和关键字的组合分析,Clipped能够对信息块的重要度进行排名,并选出那些关联系数最高的句子。然后Clipped根据分析结果生成内容摘要,最后还会重新读取它自动生成的摘要进行分析,以确保选定的信息内容是合理的。然后,该算法才会将最终结果呈现给用户阅读。
    Clipped的主要思路还是单文档的Extractive来选取最为重要的三句话返回给用户。
    缺陷:对于某些专业论文计算的比较好,但是普通的新闻有的时候很不连贯,无法概括全部的含义。

6、今日头条的实现(猜测)

    今日头条的新闻很多都来源于微博,猜测是思路是根据新闻聚类将微博内容和新闻同时进行聚类(粒度较小),这样所有相关的微博和新闻都会到一个topic中,然后在选取摘要的时候,选取相似的微博内容作为摘要。当微博摘要不存在的时候,往往选取的是第一段内容。
     缺陷:依赖新浪微博,时效性、领域性要求很强,即便是新浪微博的内容,质量也并不太高。

Level DB中的BloomFliter及Murmur Hash算法

2013年3月6日

1、LevleDb bloomfilter存储格式

在LevelDb 1.4版本中,加入了bloomfilter的支持,这样在DB::Get()方法的调用过程中,可以直接读取到bloom filter的block部分,从而减少了不存在key的大量的sstable文件随机读的操作。
在levelDb中的filter block是存储在Meta Block部分,目前的版本Meta BLock只有现在的bloom filter,后续版本还可能会加入新的内容。如下图所示。

3

对于Meta block中的bloom filter的存储方式,如下图所示。

[filter 0]
[filter 1]
[filter 2]

[filter N-1]

[offset of filter 0] : 4 bytes
[offset of filter 1] : 4 bytes
[offset of filter 2] : 4 bytes

[offset of filter N-1] : 4 bytes

[offset of beginning of offset array] : 4 bytes
lg(base) : 1 byte
首先有一个base,大小是以lg的方式进行存储的,默认为2Kb,则在数据存储区的[i*base,(i+1)*base)这一部分的数据就映射到了filter i上面,可以直接计算出i的值,然后获取到offset of beginning of offset array,就可以得到filter i和filter i+1的offset,这两段中间的内容即是该部分的bloom filter的存储内容。Table::InternalGet会首先利用filter进行判断该key是否match,如果不match就直接返回,无需读取相应的block,代码在/table/table.cc中。

2、bloomfilter构造算法

具体的bloom fliter的构造算法在https://github.com/google/leveldb/blob/master/util/bloom.cc
从该bloom.cc创建的代码可以看出,bloom fliter所占有的内存由n(key的个数)和bits_per_key_这两个参数来决定的。 而在整个leveldb中bloom fliter所占有的内存,应该是所有打开的sstable中的内存和,打开的sstable文件个数为max_open_files 进行指定,默认为1000。因此整个leveldb中bloom fliter占有的内存有所有打开的key的个数和keyt指定的bits_per_key_来决定的。a million keys and you use the suggested 10 bits per key as the argument to NewBloomFilterPolicy, the memory usage will be approximately 10 million bits =~ 1.25 MB。

3、bloomfilter Hash算法

bloom的Hash采用k_个hash函数的值,k_在1~30之间,由bits_per_key_*ln(2)计算所得。这些hash函数式通过BloomHash计算所得后,再进行相互移位所得。 具体的BloomHash的计算方法与MurMurHash类似。

4、MurmurHash 算法

MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。由Austin Appleby在2008年发明 MurmurHash2能产生32-bit或64-bit哈希值。 murmurhash在多个开源项目中得到应用,包括libstdc、libmemcached、nginx、hadoop等。代码可见 https://github.com/lightkeeper/murmurhash/blob/master/MurmurHash1.cpp

5、参考资料

http://leveldb.googlecode.com/svn/trunk/doc/table_format.txt
https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash2.cpp
http://duanple.blog.163.com/blog/static/7097176720123227403134/
http://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C
https://code.google.com/p/leveldb/source/detail?r=85584d497e7b354853b72f450683d59fcf6b9c5c

mmap to mm 思维导图文件

2012年9月13日
  • windows下的思维导图Mind Manager产生的.mmap文件,在Ubuntu下没有替代的软件
  • 二者的核心文件还是Document.xml中少了一个头部部分
  • 代码如下,详见:https://gist.github.com/xddaijun/3264921
  • 需要依赖 python, python-libxml2, python-libxslt1
  • 使用方法:python mm2fm.py *.mmap

源码:https://gist.github.com/xddaijun/3264921

Python 一句话抓取百度搜狗的热词

2012年6月19日
  • 需要依赖 python, pyquery

[gist]https://gist.github.com/xddaijun/3115077[/gist]

拼音处理资料

2011年10月5日

ibus-sogoupycc

  • 非官方的搜狗云拼音客户端, for Linux/ibus,调用搜狗云端输入法来实现本地拼音客户端。

ibus-cloud-pinyin

  • 为 Linux / ibus 设计的一个支持在线云拼音服务的拼音输入法

pinyin4j

  • convert 中文 to zhongwen.pinyin4j是一个支持将中文转换到拼音的Java开源类库。 支持简体中文和繁体中文字符; 支持转换到汉语拼音,通用拼音,威妥玛拼音(威玛拼法),注音符号。

imewlconverter

  • IME Words Library Converter/深蓝词库转换实现了各种输入法的用户词库、网络词库(细胞词库)之间的相互转换。
    支持的输入法
    目前支持的输入法有: PC端: 搜狗拼音 QQ拼音 QQ五笔(纯汉字) 谷歌拼音 搜狗五笔 紫光拼音 拼音加加 新浪拼音 极点郑码 自定义格式 手机端: QQ手机拼音 百度手机拼音 触宝手机输入法(Android)

中文自然语言处理开放平台

  • 中科院计算机自然语言处理的词库、论文等资料。

利用Python来解析Pcap包

2011年3月23日

Tcpdump可以将网络中传送的数据包的“头”完全截获下来提供分析。它支持针对网络层、协议、主机、网络或端口的过滤,并提供and、or、not等逻辑语句来帮助你去掉无用的信息。

3

这个我在截取的一段Tcpdump的数据包。通常可以采用wireshark来对Tcpdump数据包进行分析。

1

3

从图中大概可以看出每一个tcpdump的数据里面有很多的包,每一个包都有包的head部分和Data部分。其中head部分包括网卡的地址,ip的地址,端口地址,发送时间等等很多信息。在我的工作中需要将包的发送时间、它的目的IP以及发送的数据保存起来。这就需要对tcpdump数据进行分析,提取出有用的信息。

在网上有一个C#版本做的解析Pcap数据包的资料,很有参考价值。读写 cap 文件的 C# 代码(兼容 tcpdump 及 Wireshark)

它的关键代码

#region Constructors
      /// <summary>
      /// 构造一个 Pcap 包捕获读取器。
      /// </summary>
      /// <param name="baseStream">要读取的基础流</param>
      public PacketCaptureReader(Stream baseStream)
      {
          if (baseStream == null)
throw new ArgumentNullException("baseStream");
          if (!baseStream.CanRead)
throw new ArgumentException("传入的流必须为可读。", "baseStream");
          _BaseStream = baseStream;
          m_Reader = new BinaryReader(_BaseStream);
          if (m_Reader.ReadUInt32() != MAGIC)
              throw new FormatException("无效的 PCAP 格式。");
          short versionMajor = m_Reader.ReadInt16();
          short versionMinjor = m_Reader.ReadInt16();
          if (versionMajor != 2 || VersionMinjor != 4)
          {
              throw new FormatException(
string.Format("无法处理的 PCAP 版本 {0}.{1}", versionMajor, versionMinjor));
          }
          _TimeZone = m_Reader.ReadInt32();
          _CaptureTimestamp = m_Reader.ReadInt32();
          _MaxPacketLength = m_Reader.ReadInt32();
          _LinkLayerType = (LinkLayerType)m_Reader.ReadInt32();
      }

      #endregion

      /// <summary>
      /// 读取下一个捕获包
      /// </summary>
      /// <returns>读取的捕获包,如果已经到达尾端,返回 null</returns>
      public PacketCapture Read()
      {
          if (_BaseStream.Position == _BaseStream.Length) return null;
          UnixTime timestamp = new UnixTime(m_Reader.ReadInt32());
          int millseconds = m_Reader.ReadInt32();
          if (millseconds > 1000000)
              throw new InvalidDataException("读取到无效的数据格式。");
          int len = m_Reader.ReadInt32();
          int rawLen = m_Reader.ReadInt32();
          if (len > rawLen)
              throw new InvalidDataException("读取到无效的数据格式。");
          byte[] buff = m_Reader.ReadBytes(len);
          return new PacketCapture(buff, rawLen, timestamp, millseconds);
      }

从中可以看出 每一个tcpdump数据里面都有一个数据格式的head信息,通过读取该部分判断这个数据包的格式。剩下的部分就是我需要的数据包内容了。

我的python代码如下

   1: #!/usr/bin/python2.5

   2: # -*- coding: utf-8 -*-#

   3: import struct

   4: import os

   5: import re

   6: import sys

   7: import time

   8: import socket

   9: def Pcap_check(infile):

  10:     c = infile.read(24)

  11:     if not c:

  12:         return c

  13:     (a,b,cx,d,e,f,g)=struct.unpack('<Ihhiiii',c)

  14:     if a!= 0xA1B2C3D4:

  15:         return False

  16:     print "versionMajor:",b

  17:     print "VersionMinjor:",cx

  18:     print "_TimeZone:",d

  19:     print "_CaptureTimestamp",e

  20:     print "_MaxPacketLength:",f

  21:     print "_LinkLayerType:",g

  22:     return True

  23: def Pcap_read(infile):

  24:     c = infile.read(16)

  25:     if not c:

  26:         return ('',0,c)

  27:     (timestamp,millseconds,len,rawlen)=struct.unpack('<IIII',c)

  28:     timeStruct=time.gmtime(timestamp)

  29:     currentTime=(timeStruct.tm_hour*3600+timeStruct.tm_min*60+

  30:                 timeStruct.tm_sec)*1000+millseconds/1000

  31:     c=infile.read(34)

  32:     source,dest=struct.unpack('<26xII',c)

  33:     source=socket.inet_ntoa(c[26:30])

  34:     dest=socket.inet_ntoa(c[30:])

  35:     infile.read(8)

  36:     c=infile.read(len-8-34)

  37:     return (dest,currentTime,c)

参考资料:读写 cap 文件的 C# 代码(兼容 tcpdump 及 Wireshark)http://www.cnblogs.com/zealic/archive/2008/05/04/1182420.html

tcpdump+python编写的流量监控的脚本 http://blog.csdn.net/kobeyan/archive/2009/07/13/4344192.aspx

dpkt下载地址:http://code.google.com/p/dpkt/downloads/list

pcap下载地址:http://code.google.com/p/pypcap/

很好的几个Cheat Sheet

2010年10月19日

一个很偶然的机会,发现还有人制作好的python的快速手册,相当精美。

6

看上图,这里还有很多 python、Regular Expressions 等等。

网址是http://www.addedbytes.com/cheat-sheets/,他主要侧重于web开发

在搜索后还发现了一个,主要侧重于网络的。http://packetlife.net/library/cheat-sheets/

此外还有几个哲思软件社区做的几个学习笔记,也可以参考一下。

Learning Mysql
Learning Git
Learning Apache

from http://amosk.info/program.html

 

 

Learning gcc (in Chinese)
Learning gdb (in Chinese)
Learning iptables (in Chinese)

from http://wangcong.org/articles/index.html

使用Physics Helper 做SilverLight小游戏

2010年4月22日

最近在做一个Silverlight的游戏,由于人物上面的关节需要进行活动,类似于在flash用骨骼工具,在SilverLight中没有类似的控件,找了很多东西都感觉实现得很不理想。后来发现了 codeproject上面的一个Physics Helper的开源项目,它封装了Farseer的功能,并且它的使用方法非常简单,直接在Blend中就可以实现很好的动画效果,支持鼠标,重力等。下面是他的描述。

Project Description

The Physics Helper for Blend, Silverlight and WPF contains several Behaviors and controls which allow you to draw objects in Expression Blend 3, and have those objects translated directly into Physics objects using the Farseer Physics Engine. This can be a great timesaver for creating games, as it is traditionally difficult to line up underlying physics bodies and geometries with your Blend artwork.

demo演示地址    http://www.andybeaulieu.com/silverlight/3.0/physicshelper3/index.htm.

Demo Behaviors 2

Rag Doll

用LINQ来对文章列表进行操作

2010年4月4日

最近正在做的一个软件,就是对某个网站的所有文章列表里添加一个监听器,判断是否有指定的关键字。对文章列表里面的抓取都已经做好了,就需要对一前一后的两个列表进行更新。本来可以用循环列表一个一个的进行判别的,一想在VS2008里面不是有个LINQ啊,一直只是听说过,从来没用过。今天试看看怎么用。就上网搜了会,照着别人的写了个。感觉效率不好,应该可以写成一个语句了,我去写成了三个,也不知道怎么改好。

 

 public bool getState(ref List<Post> ls)
      {
          second = getData();
          var list2 = from s in first
                      where s.Title.IndexOf( key ) >= 0
                      select s.getPostUid();
          first[4].getPostUid();
          var list3 = second.Where(s => s.Title.IndexOf( key) >= 0);
          var l =from s in list3
              where !list2.Contains(s.getPostUid())
               select s;
          first = second;
          if (l.Count() >= 1)
          {
              ls = l.ToList();
              return true;
          }
          else
              return false;
      }

复试上机题

2009年3月15日
Problems A.请写一个程序,判断给定整数序列能否构成等差数列
输入说明:多组数据,每组输入数据由两行构成,第一行只有一个整数n(<1000),表示序列长度(即序列中整数的个数,0表示输入结束),第二行为n个整数,每个整数的取值区间都为[-32768—-32767],整数之间以空格或挑格间隔。
输出说明:对于每一组数据,输出一个yes或no,表示该序列能否构成等差数列。
输入样本:
6
23 15 4 18 35 11
3
3 1 2
0
输出样本:
yes
noProblem B.判断给定正整数是不是“水仙花数”。“水仙花数”是指一个三位数,其各位数字的立方和等于该数,例如153=13+53+33。
输入说明:有多组数据,每组数据为一个正整数n(0<n<65536,占一行),为0时表示输入结束。
输出说明:对于每一组数据,输出一个yes或no(表示该数是否为“水仙花数”)。
输入样本:
153
111
370
422
0
输出样本:
yes
no
yes
noProblem C. Arnold变换是一种常用的图像置乱技术,Arnold变换的定义如下:
对任意N*N矩阵(所有元素都相同的矩阵除外),设i,j为矩阵元素原始下标,经过Arnold变换后新下标为i’,j’,且满足下式:
i’=(i+j)mod N
j’=(i+2j)mod N
i,j:0,1,………N-1
Arnold变换具有周期性,即经过若干次变换后,矩阵回到最初状态,且周期T与N的大小有关。对于任意N>2,TN<=N2/2,请编写程序输出给定的N(2<N<=10)对应的周期TN。
输入说明:有多组数据,每组数据只有一个整数N(2<N<=10,占一行),为0时表示输入结束。
输出说明:对输入的每一N,给出N*N矩阵的Arnold变换的周期T。
输入样本:
3
8
0
输出样本:
4
6

Problem D.对于一个正整数n,如果它的各位之和等于它的所有质因数的各位之和,则该数被称为Smith数。例如,31257=3*3*23*151,31257的各位数字之和为3+1+2+5+7=18,它的所有质因数的各位数字之和为3+3+2+3+1+5+1=18,因此,31257是一个Smith数。编写一个程序判断输入的正整数是不是Smith数。
输入说明:有多组数据,每组数据只有一个整数n(<100000,占一行),为0时表示输入结束。
输出说明:对于每一组数据,输出一个yes或no(表示该数是否为Smith数)。
输入样本:
31257
123
0
输出样本:
yes
no

Problem E. 请写一个程序,计算Rn精确结果(0.0<R<99.999,n是整数且0<n<=25)。
输入说明:有多组数据,每组数据占一行,用一对数据表示,第一个数据是R(含小数点共6位),第二个数据是n,两个数之间有一个空格。
输出说明:对每个输入输出其结果(占一行)
输入样本:
95.123   12
0.4321   20
6.7592   9
98.999   10
1.0100   12
输出样本:
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201