这几天写了一个成分句法分析器，有写一下的感觉。就写一下吧
成分句法分析和依存句法分析算法类似，只不过实现上有比较大的区别，其主要在于成分句法的复杂度与类别的立方成正比比较多，而一阶依存句法和类别的个数成正比。
比如
VP -> VP + NP
这里共有3个类别，因此要穷举这种文法，需要类别的立方复杂度。
而在实际使用时，为了使用bottom up的解码算法，要对成分句法进行二分化：比如 VP-> VP + PP + NP需要转成 VP -> VP + PP_NP, PP_NP-> PP + NP，因此这样一来，类别的标记会非常多。可能会达到几千个（有些论文会对类别扩展，比如VP会扩展成VP3）。所以精确的解法是不现实的。Beam search或是其他一些减枝算法必须要使用。在此次的实现中，对A-> B + C中的B,C进行了减枝。Beam size由用户指定，默认为20
数据结构需要仔细设计才能满足这样的需求。
此次实现用到了如下的结构
首先，特征x部分由模板生成，其A-> B+C从训练语料中搜集得到。比如

S("it" VP(VP("is") ADJP("fine"))

采用模板%lw[0]%rw[0]
lw=left word
mw=middle word
rw=right word
生成 x:  is/fine
y为 VP-> VP + ADJP

一个x可能产生多个语法规则，比如
x:  is/fine
y为 VP-> VP + NP

要找到该x所产生的第i条语法规则(y)，需如下寻址：
ys[      feature_infos[     x2id[x]   ].base + i    ]
其对应的特征权重为
lambda[      feature_infos[     x2id[x]   ].base + i    ]



map<string,int> x2id将x映射到索引上，该索引给一个数组提供下标。
struct feature_info{
}
vector<feature_info> feature_infos


struct result_unit{
}
vector<result_unit> ys;




用这样的结构是周折试探了好久的。

最重要的是，一个x产生的y是稀疏的，远小于类别的立方，因此如果采用
lambda[   x2id[x][y1][y2][y3]  ]
来定位特征权重将产生严重的空间浪费。以类别=1000来算，一个x将消耗1000^3个double，不现实。因此采用稠密的存储。将x所产生的y放在一起
为什么不用  ys[  x2id[x] + i  ] 来寻址第i个y呢？因为这样没法存放x所对应的y的个数，这在遍历y时需要用到。
一种做法是，ys[  x2id[x] + 0  ] 作为y的个数，但如此一来，ys[  x2id[x] + i  ]所对应的lambda将不是lambda[  x2id[x] + i  ]，当然，可以插入无效参数lambda[  x2id[x] + 0 ]来使得lambda与ys对齐，但是这样一来，数据结构会十分混乱。ys[  x2id[x] + 0  ] 的数据结构是result_unit，但存的是int。
这里要提到的是，为什么不用int y=bottom_y*ysz*ysz+left_y*ysz+right来代替result_unit这个结构，ysz为类别的总数。主要是考虑到int的表示范围。ysz=2000就已经超过unsigned int 的范围了（以4字节计算），如果采用int64，将使得空间占用扩大一倍。而result_unit占用6字节，却可以表达ysz=65535的范围。

这样一来，就是用feature_info这个结构存放x对应的y的个数（其.ysz成员），而base成员存放的是首个y的地址。即base+0 ... base+ysz-1都是x对应的y。其相应的参数为lambda[base +i ]


采用beam search (size=20)
352句的中文语料，产生133个类别，特征10万个，迭代一次的时间大约为50秒

使用了urlrewrite.jar，发现中文无法处理，因此自己实现一个urlrewrite

首先贴一下MyURLRewriter.java源代码

//==========================code start====================
package mur;
import java.io.IOException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import javax.servlet.Filter;
import javax.servlet.FilterChain;
import javax.servlet.FilterConfig;
import javax.servlet.ServletException;
import javax.servlet.ServletRequest;
import javax.servlet.ServletResponse;
import javax.servlet.http.*;


public final class MyURLRewriter implements Filter {
    private FilterConfig _config;
    public void init(FilterConfig fConfig) throws ServletException {
        _config=fConfig;
    }
    public void destroy() {
        _config=null;
    }
    //一下代码将/HelloServlet/name/xxx.html转发到/HelloServlet?name=xxx
    public void doFilter(ServletRequest request, ServletResponse response,FilterChain chain) throws IOException, ServletException {
        String url=((HttpServletRequest)request).getRequestURI();
        _config.getServletContext().log(url);
        Pattern p=Pattern.compile("^/HelloServlet/name/(.+).html$");
        Matcher m=p.matcher(url);
        String newUrl=url;
        if(m.find()){
            newUrl="/HelloServlet?name="+m.group(1);
            _config.getServletContext().log("redirect: "+newUrl);
            ((HttpServletRequest)request).getRequestDispatcher(newUrl).forward(request, response);
        }else{
            _config.getServletContext().log("process");
            chain.doFilter(request, response);
        }
    }
}
//==========================code end===============================






步骤：
1、编译该代码
产生MyURLRewriter.class，将它放到WEB-INF/classes/mur/下
2、修改WEB-INF/web.xml
添加：
<filter>
    <filter-name>MyURLRewriter</filter-name>
    <filter-class>mur.MyURLRewriter</filter-class>
    <init-param>
        <param-name>logLevel</param-name>
        <param-value>WARN</param-value>
    </init-param>
</filter>
<filter-mapping>
    <filter-name>MyURLRewriter</filter-name>
    <url-pattern>/*</url-pattern>
</filter-mapping>
3、重启tomcat
4、输入网址：
http://localhost:8080/HelloServlet/name/%B8%A3%CC%D8.html
5、检查一下是否转成功
查看tomcat/logs/localhost.20XX-XX-XX.log，如果有
redirect: /HelloServlet?name=%B8%A3%CC%D8
则表示成功了



如果失败，请检查tomcat/logs/localhost.20XX-XX-XX.log，是否初始化成功，没有成功会出现MyURLRewriter的相关信息

今天晚上看了一下minimal perfect hashing的一篇paper：
A Faster Algorithm for Constructing Minimal Perfect Hash Functions
SIGIR 1992
minimal perfect hashing的基本思想如下

假设将n个元素hash到T个连续整数上, T>=n
minimal perfect hashing：
1、采用一个hash函数，将n个元素hash到b个bucket中。b通常=2n / log_2 n，这个hash最好是不均匀的，但同时要求每个bucket的元素不能太多。也就是说有的bucket会获得很多元素，但仍旧<<n，而有的bucket只有很少元素。
2、将bucket按照元素个数从多到少排序。
3、对于每个bucket，有一个hash函数h和一个偏移g。h的目的是将一个bucket中的元素无冲突地hash到1-T上，由于每个bucket元素不太多，因此这样的hash很快可以搜索到。g的作用是解决不同bucket经过hash后的冲突。比如第一个bucket hash到1,2,5，第二个bucket hash到2,3，则第二个bucket的偏移量g=1，这样第二个bucket就映射到3,4，与第一个bucket没有冲突了

相比以前，作业起来更累。

曾经少年多遐想
如今已是过眼云
只求了结一件事
从此做个平凡人

用于中文缩写。设x_1...x_n 缩写为x_i...x_j。则没有保留的字标为0，保留的字标为1。当然也可以扩展下，比如
首都儿童研究所 ->儿研所
ＯＯＢＯＣＯＯ
B表示当前字保留，且后面一个字舍弃，C表示当前字保留，后面两个字舍弃。用一个二阶CRF就行

//mind_freq_substring.h
#ifndef MIND_FREQ_SUBSTRING_H
#define MIND_FREQ_SUBSTRING_H
void mind_freq_substring(unsigned int freq, const char *input_file_name, const char *output_file_name, size_t (*get_c)(const char *));
//从input_file挖掘频率>f=req的子串，输出到output_file，get_c为读取一个字符函数，返回字符长度，比如读取一个GBK汉字，返回2
#endif


//mind_freq_substring.cpp
#include <fstream>
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
namespace {
    void string2characters(const string &s, vector<string> &chs, size_t (*get_c)(const char *)){
        chs.clear();
        const char *p=s.c_str();
        size_t c_len=0;
        size_t s_len=s.length();
        for(size_t l=0;l<s_len;l+=c_len){
            c_len=get_c(p+l);
            chs.push_back(s.substr(l,c_len));
        }
    }
}
void mind_freq_substring(unsigned int freq, const char *input_file_name, const char *output_file_name, size_t (*get_c)(const char *)){
    ifstream fin;
    ofstream fout;
    string s;
    fin.open(input_file_name);
    string fn1=input_file_name;
    
    string fn2=fn1+"2";
    fn1+="1";
    fout.open(fn1.c_str());
    while(fin>>s)
        fout<<s<<endl;
    fout.close();
    fout.clear();
    fin.close();
    fin.clear();
    
    map<string,unsigned int> substring_count;

    for(size_t len=1;;len++){
        substring_count.clear();
        if(len%2)
            fin.open(fn1.c_str());
        else
            fin.open(fn2.c_str());
        
        while(fin>>s){
            if(s.length()==0)
                break;
            //s into chs
            vector<string> chs;
            string2characters(s,chs,get_c);
            //get substring of length len
            if(chs.size()<len)
                continue;
            for(size_t i=0;i+len<=chs.size();i++){
                string word;
                for(size_t j=i;j<i+len;j++)
                    word+=chs[j];
                substring_count[word]++;
            }
        }
        fin.close();
        fin.clear();
        if(len%2){
            fin.open(fn1.c_str());
            fout.open(fn2.c_str());
        }else{
            fin.open(fn2.c_str());
            fout.open(fn1.c_str());
        }
        //split strings
        while(fin>>s){
            if(s.length()==0)
                break;
            //s into chs
            vector<string> chs;
            string2characters(s,chs,get_c);
            //get substring of length len
            if(chs.size()<len)
                continue;
            size_t start=0;
            for(size_t i=0;i+len<=chs.size();i++){
                string word;
                for(size_t j=i;j<i+len;j++)
                    word+=chs[j];
                if(substring_count[word]<freq){
                    if(i+len-1-start>=len+1){
                        for(size_t j=start;j<i+len-1;j++)
                            fout<<chs[j];
                        fout<<endl;
                    }
                    start=i+1;
                }
                
            }
            if(start+len+1<=chs.size()){
                for(size_t j=start;j<chs.size();j++)
                    fout<<chs[j];
                fout<<endl;
            }
        }

        fin.close();
        fin.clear();
        fout.close();
        fout.clear();
        bool new_word_found=false;
        fout.open(output_file_name,ios::app);
        for(map<string,unsigned int>::iterator it=substring_count.begin();it!=substring_count.end();it++)
            if(it->second>=freq){
                fout<<it->first<<"\t"<<it->second<<endl;
                new_word_found=true;
            }

        fout.close();
        fout.clear();
        if(!new_word_found)
            break;
    }
}


//main.cpp
#include "mind_freq_substring.h"
size_t get_gbk_char(const char *s){
    if(!s||!(*s))
        return 0;
    return s[0]<0?2:1;
}
int main(){
    mind_freq_substring(200,"tmp.txt","grap.txt",get_gbk_char);//tmp.txt格式为一句一行
    return 0;
}

对于一棵有向树(branch)，构造其距离矩阵D：

D(i,j)=从i出发到j所经过的边数（如果i是可以到达j的）
否则D(i,j)=\inf

第一个问题是，这样的矩阵和原来的树是不是一一对应的？
第二个问题是，如果是一一对应的，如何从一个矩阵D求最优对应树。矩阵D可能是不合法的，比如D可能是任意实矩阵，求一个矩阵X: X是一个合法的树距离矩阵，且tr(XM)最大， M(i,j)=1/D(i,j)。为了方便计算目标函数可以自己挑选一个合适的。

linux下的，见
http://www.hackchina.com/cont/108408



以下这段代码获取www.baidu.com的html源码
从http://hereson.javaeye.com/blog/198790改写
VS2005下正确运行


#include <winsock2.h>
#include <fstream>
#pragma comment(lib,"ws2_32.lib")
using namespace std;
void main()
{
    ///初始化Socket函数库
    WSADATA wsaData;
    if( WSAStartup(MAKEWORD(2,0), &wsaData)
        || LOBYTE(wsaData.wVersion) != 2 )
        return;

    struct protoent *ppe;
    ppe=getprotobyname("tcp");

    ///创建SOCKET对象
    SOCKET sock = socket(PF_INET, SOCK_STREAM, ppe->p_proto);
    if(sock == INVALID_SOCKET)
        return;

    ///根据主机名获得IP地址
    hostent* pHostEnt=gethostbyname("www.baidu.com");
    if(pHostEnt==NULL)
        return;

    int nTime = 10000;
    setsockopt(sock, SOL_SOCKET, SO_SNDTIMEO, (char*)&nTime, sizeof(nTime));
    setsockopt(sock, SOL_SOCKET, SO_RCVTIMEO, (char*)&nTime, sizeof(nTime));

    ///连接
    struct in_addr ip_addr;
    memcpy(&ip_addr, pHostEnt->h_addr_list[0], 4);///h_addr_list[0]里4个字节,每个字节8位

    struct sockaddr_in destaddr;
    memset((void *)&destaddr, 0, sizeof(destaddr));
    destaddr.sin_family = AF_INET;
    destaddr.sin_port = htons(80);
    destaddr.sin_addr = ip_addr;

    if( 0 != connect(sock, (struct sockaddr*)&destaddr, sizeof(destaddr)) )
        return;

    ///格式化请求
    char request[] =
        "GET / HTTP/1.1\r\n"
        "Host:www.baidu.com\r\n"
        "Accept:*/*\r\n"
        "User-Agent:Mozilla/4.0 (compatible; MSIE 5.00; Windows 98)\r\n"
        "Pragma: no-cache\r\n"
        "Cache-Control: no-cache\r\n"
        "Connection:Close\r\n\r\n";
    ///发送请求
    if( SOCKET_ERROR == send(sock, request, strlen(request), 0) )
        return;
    //---------Response----------
    // HTTP/1.1 200 OK
    // Date: Wed, 02 Feb 2005 08:42:09 GMT
    // Server: Apache
    // Last-Modified: Mon, 24 Jan 2005 13:17:07 GMT
    // ETag: "37a9ef-7635b-459bac0"
    // Accept-Ranges: bytes
    // Content-Length: 484187
    // Connection: close
    // Content-Type: application/zip

    // Transfer-Encoding: chunked - 当有该行存在时，content会是分块传送，每块有一个头，格式："[16进制块大小，string]\r\n"
    int rcv_bytes = 0;
    char buf[2049] = {0,};
    ofstream ofs("c:.html", ios::binary|ios::out|ios::trunc);
    while(1)
    {
        rcv_bytes = recv(sock, buf, 2048, 0);
        if( rcv_bytes <= 0 )
            break;
        ofs.write(buf, rcv_bytes);
    }
    ofs.close();
    closesocket(sock);
    WSACleanup();
}

It is pitiful that some people has no coding skill for right implementation, it is more pitiful that many people think coding skill is important

转载：

http://mat.gsia.cmu.edu/orclass/integer/node13.html#SECTION00042000000000000000

用分支定界法求解布尔线性规划问题

布尔线性规划问题：(P1)
max_x    a'x
s.t.    b'x<=c
    x_i is bool

性质1.假设求的松弛问题(P2)
max_x    a'x
s.t.    b'x<=c
    for some i, x_i is bool
的最优解x^*,z^*，则P1的最优解必定<=z^*。
进一步，如果此时所有的x^*_i恰好为布尔值，则求解结束。

例子：求解如下问题：
max    8x1+11x2+6x3+4x4
s.t.    5x1+7x2+4x3+3x4<=14
    x_i is bool

(1)去掉布尔约束，求的最优解
x1=1,x2=1,x3=0.5,x4=0,z=22
此时x3不是布尔值，对x3分支x3=0, or x3=1


解得两个最优值：
x3=0时，x1=1,x2=1,x3=0,x4=0.667, z=21.65
x3=1时，x1=1,x2=0.714,x3=1,x4=0, z=21.85
此时我们知道原问题的最优解<=21
因为21.85>21.65，对x3=1先分支，此时x2=0 or 1


x3=1,x2=0时 x1=1,x2=0,x3=1,x4=1,z=18
x3=1,x2=1时 x1=0.6,x2=1,x3=1,x4=0,z=21.8
取x3=1,x2=1,对x1分支

有，
x3=1,x2=1,x1=0时，x1=0,x2=1,x3=1,x4=1,z=21
此时已经达到最优值，结束。