概率检索模型BM25系列-文档相关性检索的利器

发表于 2016-01-26

给定一个用户需求(query),如果搜索系统展示的搜索结果是根据文档和query的相关性由高向低排序的，那么这个搜索引擎是最优的。在文档集合的基础上计算其相关性估计是其核心~

概率排序原理

以往的向量空间模型是将query和文档使用向量表示然后计算其内容相似性来进行相关性估计的，而概率检索模型是一种直接对用户需求进行相关性的建模方法,一个query进来，将所有的文档分为两类—-相关文档、不相关文档,这样就转为了一个相关性的分类问题,赞!

对于某个文档$D$来说，$P(R|D)$表示该文档数据相关文档的概率，则$P(NR|D)$表示该文档属于不相关文档的概率，如果query属于相关文档的概率大于不相关文档$P(R|D)>P(RN|D)$，则认为这个文档是与用户查询相关相关的.

用笨方法解决Shell中按行读取文件之后Tab键不见的问题

By Kubi Code

发表于 2016-01-03

Shell强大灵活，但是今天在使用Shell处理按行读取文件时发现读取到的行设定的tab分割符不见了

先看一下演示的待处理文件:

需要做的需求就是将里面的数据使用shell将第一列读取出来做一些其他处理(当然如果仅仅是完成读取首列这个功能，使用awk是最快的，这里只是演示)

盛最多水的容器

By Kubi Code

发表于 2015-12-28

来源：https://leetcode-cn.com/problems/container-with-most-water

题目

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解

指针移动规则与证明：初始化头和尾两个指针，每次选定围成水槽两板高度 h[i]h[i],h[j]h[j] 中的短板，向中间收窄 11 格

int maxArea(vector<int>& height) {
    int ret = 0;
    int i=0,j=height.size()-1;
    while(i<j){
    	if(height[i]<height[j]){
    		ret = max(ret,(j-i)*height[i]);
    		i++;
    	}else{
    		ret = max(ret,(j-i)*height[j]);
    		j--;
    	}
    }

    return ret;
}

参考

https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/

接雨水

By Kubi Code

发表于 2015-12-27

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

解法

双指针法：
如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
我们必须在遍历时维护 $\text{leftMax}$ 和 $\text{rightMax}$，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。

#include<iostream>
#include<vector>
using namespace std;

int trap(vector<int>& height) {
    if(height.size()<=2){
        return 0;
    }

    int left_max = height[0];
    int right_max = height[height.size()-1];
    int i = 0,j = height.size()-1;
    int sum = 0;

    while(i<=j){
        cout << "i:"<<i << " j:"<<j<<endl;
        if(left_max <= right_max){
            if(height[i]>=left_max){
                left_max = height[i];
            }else{

                cout << "left: " << left_max << ":" << height[i] << endl;
                sum += left_max-height[i];
            }
            ++i;
        }else{
            if(height[j] >= right_max){
                right_max = height[j];
            }else{
                cout << "right: " << right_max << ":" << height[j] << endl;
                sum += right_max - height[j];
            }
            --j;
        }
    }

    return sum;
}



int main(){
    //int num1[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int num1[] = {5,5,1,7,1,1,5,2,7,6};
    vector<int> vec1(num1,num1+10);


    cout << trap(vec1) << endl;
	
	return 0;
}

参考

最大乘积的子序列

By Kubi Code

发表于 2015-12-27

题目

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

思路

标签：动态规划
遍历数组时计算当前最大值，不断更新

令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
当负数出现时则imax与imin进行交换再进行下一步计算
时间复杂度：O(n)

int maxProduct(vector<int>& nums) {
        if(nums.size()<=0){
            return 0;
        }

        int ret = nums[0];
        int imax = 1,imin = 1;
        for(int i=0;i<nums.size();++i){
            if(nums[i]<0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }

            imax = max(imax*nums[i],nums[i]);
            imin = min(imin*nums[i],nums[i]);

            ret = max(ret,imax);
        }

        return ret;
    }

参考

https://leetcode-cn.com/problems/maximum-product-subarray/solution/hua-jie-suan-fa-152-cheng-ji-zui-da-zi-xu-lie-by-g/

求最小编辑距离

By Kubi Code

发表于 2015-12-26

问题链接：https://leetcode-cn.com/problems/edit-distance

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

则需要维护一个二维的最小编辑距离表：

则右下角则为最小的编辑距离，核心代码为:

int minDistance(string word1, string word2) {
        int M = word1.length();
        int N = word2.length();
        int A[M+1][N+1];

        for(int i=0;i<=M;++i){
            for(int j=0;j<=N;++j){
                if(i==0){
                    A[i][j] = j;
                }else if(j==0){
                    A[i][j] = i;
                }else{
                    A[i][j] = 0;
                }
            }
        }


        for(int i=1;i<=M;++i){
            for(int j=1;j<=N;++j){
                if(word1[i-1] == word2[j-1]){
                    A[i][j] = A[i-1][j-1];
                }else{
                    A[i][j] = min(A[i-1][j-1],min(A[i-1][j],A[i][j-1]))+1;
                }
            }
        }

        return A[M][N];
    }

找两个数组中第K个大的数字

By Kubi Code

发表于 2015-12-26

题目

在两个有序数组中，找到第k大的数字，要求复杂度为O(log(m+n))

解析

因为题目是要求复杂度O(log(m+n))，则无法直接使用遍历，重排的方式了，基本一下子就能想到类似二分查找的方法

假设这两个数组分别为A和B

假如两个数组分别取k/2位置的值，如果A[k/2-1]等于B[k/2-1]，则这个值就是第k大的数
但是如果A[k/2-1]大于B[k/2-1]，则B[0:k/2-1]范围内的值都将会小于第k大，这里的值可以直接过滤，从B[k/2]再开始查找
如果A[k/2-1]小于B[k/2-1]同理2的方式
因此可以根据k/2部分值大的大小比较进行递归

同时在递归时会预见某个子数组会0长度或者k到1的边界，此时直接取值返回即可，因此对应的代码为:

#include<iostream>
using namespace std;

int binary_find_k(int* A,int len1,int* B,int len2,int k){
	if(len1>len2)
		// 需要保证A数组比B短
		return binary_find_k(B,len2,A,len1,k);
	if(len1 == 0)
		return B[k-1];
	if(k==1)
		return min(A[0],B[0]);

	int k1 = min(k/2,len1);
	int k2 = k-k1;

	cout << k1 << " , " << k2 << ":" <<  A[k1-1] << " , "<<B[k2-1] <<endl;
	if(A[k1-1] > B[k2-1]){
		// 说明B[0:k2-1]部分都会比   第k大 数字要小，这部分抛弃，继续递归
		cout << "keep k1" << endl;
		return binary_find_k(A,len1,B+k2,len2-k2,k1);
	}else if(A[k1-1] < B[k2-1]){
		cout << "keep k2" << endl;
		return binary_find_k(A+k1,len1-k1,B,len2,k2);
	}else{
		// 这个就是k大
		return B[k2-1];
	}
}

int main(){
	int A[] = {2,3,4,7,8,12};
	int B[] = {1,5,6,8,10,11};
	int len1 = 6;
	int len2 = 7;
	int k = 5;
	cout << binary_find_k(A,len1,B,len2,k)<<endl;

	
	return 0;
}

这里正好也输出为5

轻量的结构化文本处理工具-awk

By Kubi Code

发表于 2015-12-24

与其说awk是一个强大的文本处理工具，我更加喜欢称之为轻量级的C语言版脚本，有了它，你就能非常自由，轻松的操作文本文件了。ps:比Excel更加方便哦,一句话：awk可以带你装b带你飞~

初体验：九九乘法表

#! /bin/awk -f

BEGIN{
    print "lets begins"
}

{
    for(i=1;i<=NR;i++)
        printf("%sx%s=%s\t",NR,i,NR*i)
    printf("\n")
}

END{
    print "ends"
}

在先看awk程序之前，咱先来看一下由他实现的一个九九乘法表

yans-MacBook-Pro:Downloads yanyl$ seq 9 | awk -f chengfa.awk
lets begins
1x1=1
2x1=2    2x2=4
3x1=3    3x2=6    3x3=9
4x1=4    4x2=8    4x3=12    4x4=16
5x1=5    5x2=10    5x3=15    5x4=20    5x5=25
6x1=6    6x2=12    6x3=18    6x4=24    6x5=30    6x6=36
7x1=7    7x2=14    7x3=21    7x4=28    7x5=35    7x6=42    7x7=49
8x1=8    8x2=16    8x3=24    8x4=32    8x5=40    8x6=48    8x7=56    8x8=64
9x1=9    9x2=18    9x3=27    9x4=36    9x5=45    9x6=54    9x7=63    9x8=72    9x9=81
ends
yans-MacBook-Pro:Downloads yanyl$

Hadoop Streaming 实践以及Debug

By Kubi Code

发表于 2015-11-08

Hadoop Streaming是一个便于变成Map Reduce程序的工具包，这个工具包可以支持各种可执行/脚本语言来创建Mapper和Reducer，利用Hadoop的优势进行大数据的处理，这些语言仅仅只需要支持*unix的表示输出输入即可(python,c,c++,perl,akw etc.)

Streaming实践

先直接来看一个由python写的Streaming程序，还有那个经典的word count,我们的数据集是一篇英语作文,
看来看他的mapper文件

#!/usr/bin/env python
#-*- coding=utf8 -*-

import sys,re

re_english = re.compile(u'[^a-zA-Z0-9\-]+')

for line in sys.stdin: #这里你可以看做是map类中的line输入
    words = re_english.sub(' ',line.strip()) #这里只提取英文数字
    for word in words.split():
        print '%s\t%s' % (word, 1)  #这儿就是标准的输出，用tab隔开  默认第一个值为key

在Mac的OSX系统中配置VIM

By Kubi Code

发表于 2015-11-07

本文主要参考[译]如何在Mac OS X中开启VIM语法高亮,他是真的work啊^_^

使用vim来敲代码很带感，设置vim是一大要事，但是在Mac的vim默认是黑白的，而且并不能像Linux设置~/.vimrc来进行配置，但是毕竟还有其他的方法，先下面一步一步走就可以了

首先进入终端之后输入如下代码

1
2
3

cd /usr/share/vim

sudo vim vimrc

Kubi Code'Blog

The palest ink is better than the best memory.

概率检索模型BM25系列-文档相关性检索的利器

概率排序原理

用笨方法解决Shell中按行读取文件之后Tab键不见的问题

盛最多水的容器

题目

解

参考

接雨水

题目

解法

参考

最大乘积的子序列

题目

思路

参考

求最小编辑距离

找两个数组中第K个大的数字

题目

解析

轻量的结构化文本处理工具-awk

初体验：九九乘法表

Hadoop Streaming 实践以及Debug

Streaming实践

在Mac的OSX系统中配置VIM