取石子游戏说的是有两堆任意数量的小石子，游戏由两个人轮流取石子，对于取法，游戏规定有两种，一种是可以在任意的一堆中，取走任意多的石子；一种是在两堆中同时取走相同数量的石子。游戏规定，最后把石子全部取完的为胜者。现在假设初始时两堆石子的数目为a和b, a <= b，假设双方都采取最好的策略，问先取的人是胜者还是败者。
对于这题，可以得到在以下情况下，先取的人必败，其它情况下，先取的人必胜。
1 2
3 5
4 7
6 10
8 13
9 16
…
可以看出，这两个数字之间一定有规律，而说到规律，很容易想到的是黄金分割比。记得那时还很粗心的将其中的数字写错了，于是任晓祎同学就过来纠正了。时光飞逝啊，已经过去三年了。
最短编辑距离说的是两个字符串A和B，求用最少的字符操作将字符串A转化为字符串B。这里所说的字符操作包括
1.删除一个字符
2.插入一个字符
3.将一个字符改为另一个字符
分析：
先比较A和B的第一个字符，分两种情况
1.两个字符相等
此时只需要计算A和B剩下字符的编辑距离
2.两个字符不相等
此时有三种选择，
（1）删除A的第一个字符，之后求A剩下的字符与B的编辑距离
（2）在A中插入B的第一个字符，之后求A与B剩下字符的编辑距离
（3）将A的第一个字符变成B的第一个字符，之后求A剩下的字符与B剩下的字符的编辑距离
之后返回这三种情况的最小值，再加上1，即是A转化为B的最短编辑距离
依照上述方法，很容易写出一个递归方法1
2
3
4
5
6
7
8
9
10
11
12def edit_distance(a, b):
if a == '':
return len(b)
if b == '':
return len(a)
if a[0] == b[0]:
return edit_distance(a[1:], b[1:])
else:
return min(edit_distance(a[1:], b), edit_distance(a, b[1:]), edit_distance(a[1:], b[1:])) + 1
A="fxpimu"
B="xwrs"
print edit_distance(A, B)
唯一的缺点是，这种方法太慢了，于是想到用动态规划，此时最好还是从后面考虑，也就是考虑A和B最后一个字符的相等情况，再根据上面的分析计算。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def edit_distance(a, b):
la = len(a)
lb = len(b)
dp = [[0 for i in xrange(lb + 1)] for j in xrange(la + 1)]
for i in xrange(1, la + 1):
dp[i][0] = i
for j in xrange(1, lb + 1):
dp[0][j] = j
for i in xrange(la):
for j in xrange(lb):
if a[i] == b[j]:
dp[i + 1][j + 1] = dp[i][j]
else:
dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
return dp[la][lb]
A="fxpimu"
B="xwrs"
print edit_distance(A, B)
两年前面试4399时，和面试官说起用Python来做欧拉工程，于是面试官很感兴趣地说，有没有写一些小模块来求解，当时只是摇头，想想写写算法题还可以，写模块就太大了。现在想来，模块也无非是一些函数的集合，在接欧拉工程的过程中，就会经常遇到一些问题，需要用类似的方法解决，如果把这些共同的部分写在一起，不也是一个模块了？
质因子分解是经常需要用到的，这里给一个解决的办法。例如要求120的质因子分解，先用2去除，一直到不能整除为止，记得到2^3,以及剩下的15，之后用3去除，得到3以及剩下的5，之后用5去除，得到5以及0，分解过程结束。写成程序如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from collections import defaultdict
def get_divisors(n):
divisors = defaultdict(int)
if n % 2 == 0:
while n % 2 == 0:
divisors[2] += 1
n /= 2
i = 3
while i * i <= n:
if n % i == 0:
while n % i == 0:
divisors[i] += 1
n /= i
i += 2
if n > 1:
divisors[n] += 1
return divisors
有了这个方法就可以用来求一些数的最小公倍数，例如求，2 3 5 8 的最小公倍数1
2
3
4
5
6
7
8
9
10L = [2, 3, 5, 8]
factors = defaultdict(int)
for i in L:
divisors = get_divisors(i)
for d in divisors.iterkeys():
factors[d] = max(factors[d], divisors[d])
res = 1
for d in factors.iterkeys():
res *= d ** factors[d]
print res
^([1-9]?[0-9]{1}|1[0-9]{2}|2[0-4][0-9]|25[0-5])(.([1-9]?[0-9]{1}|1[0-9]{2}|2[0-4][0-9]|25[0-5])){3}$r'^(?!\.)(?![\w.]*?\.\.)[\w.]{1,64}@(?=[-a-zA-Z0-9.]{0,255}(?![-a-zA-Z0-9.]))((?!-)[-a-zA-Z0-9]{1,63}\.)*(?!-)[-a-zA-Z0-9]{1,63}$'
在Sphinx中，如果你调用的是C的api，并使用更新属性的功能，而此时，你想将更新后的索引冲刷到硬盘，你就会发现C的api中没有提供这个功能。而在Java,PHP,Python中，都提供了FlushAttributes这个接口来完成这个功能，于是你不得不另外在写一个程序来调用这个接口。
仔细想想，Sphinx都是用C++写的，而C的API中竟然没有提供这个接口，反倒是其它语言有提供，真是匪夷所思。所幸，代码都是开源的，想要自己有这个接口，自己动手写一个就好了，也许这就是开源的好处。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32int sphinx_flush_attributes(sphinx_client * client) {
char *buf, *req, *p;
int req_len = 0;
if (!client) {
printf("not valid client\n");
return -1;
}
buf = malloc ( 12 + req_len ); // request body length plus 12 header bytes
if ( !buf ) {
set_error ( client, "malloc() failed (bytes=%d)", req_len );
return -1;
}
req = buf;
send_word ( &req, SEARCHD_COMMAND_FLUSHATTRS );
send_word ( &req, VER_COMMAND_FLUSHATTRS );
send_int ( &req, req_len );
// send query, get response
if ( !net_simple_query ( client, buf, req_len ) )
return -1;
// parse response
if ( client->response_len < 4 ) {
set_error ( client, "incomplete reply" );
return -1;
}
p = client->response_start;
return unpack_int ( &p );
}
之后还要添加
SEARCHD_COMMAND_FLUSHATTRS = 7，
VER_COMMAND_FLUSHATTRS = 0x100，
以及在头文件中添加int sphinx_flush_attributes(sphinx_client * client)；即可。
很早之前就知道MMSEG分词算法，网上也有各种语言的实现。最近了解Sphinx-for-Chinese的分词后，才知道它也是使用的MMSEG，并且CoreSeek也是使用的MMSEG。也许MMSEG是互联网上使用知名度最高的分词算法了吧，因为它简单并且高效。
更进一步了解后，知道MMSEG是台湾人蔡志浩提出来的。蔡志浩是一位心理学教师，在美国伊利诺伊读博士期间，选修了语言学，在这个过程中，随手写了MMSEG。看蔡志浩网站，总是很舒心，因为蔡老师的文笔很好，总会用通俗的语言把问题讲清楚，而且蔡老师的博客涉及范围极广，设计，心理，写作，社会观察，旅游等等。也正是因为他的博客，我才用实名建立自己的博客。以下回归正题。
MMSEG总的说来就是四个规则。
1.最长匹配原则
2.最大平均长度
3.最小长度方差
4.最大单字单词的语素自由度
算法步骤：
1.选定一个分词个数，得到可行的分词情形
2.利用4条原则得到最优分词可能
3.得到最优分词的第一个词，回到步骤1继续分词
举个例子最好理解。下面是要对“研究生命起源的原因主要是因为它的重要性”进行分词。
1.首先选定分词个数为3，则可以得到可行的分词情形如下：
研 究 生
研 究 生命
研究 生命 起
研究 生命 起源
研究生 命 起
研究生 命 起源
2.利用4条原则得到最优分词可能
运用第1条原则后，可以得到最优分词可能为一下两条
研究 生命 起源
研究生 命 起源
运用第2条原则，这两个结果相同
运用第3条原则，可以得到最优的结果为
研究 生命 起源
3.从最优结果中得到第一个词，也就是“研究”，之后对“生命起源的原因主要是因为它的重要性”运用相同的步骤进行分词
有必要对原则4进行解释，这条原则说的是单字的成为语素的自由度。当分到”主要是因为“就会用到。对于”主要是因为“
第1步骤中得到：
主 要 是
主 要是 因为
主要 是 因
主要 是 因为
第2步骤中，由前三条原则，只剩下一下两个
主要 是 因为
主 要是 因为
之后再运用第4条原则，这里单字”是“为独立语素的可能比”主“要大，所以最优结果为
主要 是 因为
见过的MMSEG算法实现中，素心如何天上月的http://yongsun.me/2013/06/simple-implementation-of-mmseg-with-python/无疑是最简明清晰的。Python确实不错，短短100行就把算法的精髓展示出来，并且几乎可以不用写注释了。模仿他的实现，写了一遍。
1 | #coding:utf-8 |
在Sphinx-for-Chinese的分词细粒度问题中说过，为了解决分词的粒度问题，我们对Sphinx-for-Chinese的代码进行了一些修改，而针对精确匹配我们也写了一些额外的代码，虽然这一部分的代码并不是很好看，但毕竟解决了问题，所以也想对这一部分进行说明，因为相信其他人也会遇到类似的问题，这里可以提供一个参考的解决方案。
所谓精确匹配，也就是搜索的词语搜索的字段完全相同。例如假设有三个标题,中大，中大酒店，中大假日酒店，则搜索中大时，与中大完全匹配。一般情况下，我们都希望精确匹配的内容排在前面，此时还需要设置排序方法为SPH_RANK_SPH04。
依然以sphinx-for-chinese-2.2.1-dev-r4311为例，在sphinxsearch.cpp中6282行附近，找到RankerState_ProximityBM25Exact_fn，这里就是sph04的实现。看到数据成员m_uExactHit，知道这个与精确匹配有关，在这段代码里看到HITMAN::IsEnd，于是猜测在某个地方有SetEnd,在sphinx.cpp中27144行附近找到CSphSource_Document::BuildRegularHits方法，在这里找到了，
CSphWordHit pHit = const_cast < CSphWordHit > ( m_tHits.Last() );
HITMAN::SetEndMarker ( &pHit->m_iWordPos );
于是我们想，在进行细粒度分词时，中大将被分成，中大、中、大三个词。只要有某种办法，将中大这个词也使用SetEndMarker就可以达到所要的目的，于是增加了一些代码。
这之后，搜索中大时，中大这个标题确实排在了前面，可是问题又出现了，在搜索中大酒店时，中大酒店这个标题并没有排在前面，中大酒店与中大假日酒店的权重是相同的。分析了原因，搜索中大酒店时，将被分成中大+酒店，而中大假日酒店中，正好也包含中大和酒店，并且酒店也是排在末尾，于是这两个的权重是一样的。于是我们只好再看看m_uExactHit的计算，发现IsEnd并不是唯一的条件，于是相信为细分以前，索引中大酒店时，分词的词是中大、酒店，而细分后变成了中大、中、大、大酒店、酒店、酒、店，于是我们猜测，如果将分词按照原先的方法分一次，之后再一起返回细粒度的分词，可能可以达到目的。这样的结果就是分词返回的是中大、酒店、中、大、大酒店、酒、店。于是按照这个想法，又增加了一些代码。果然这次搜索中大酒店时，中大酒店排在了前面，并且权重比中大假日酒店高。
假如使用Sphinx来做搜索引擎，就一定会遇到分词问题。对于中文，有两个选择，选择1是使用Sphinx自带的一元分词，选择2是使用CoreSeek或者Sphinx-for-Chinese，这两个都使用了mmseg来进行分词。据我了解,CoreSeek在支持细粒度的分词，而Sphinx-for-Chinese不支持。而公司使用的是Sphinx-for-Chinese,所以就遇到了分词的粒度问题。
根据产品人员的反馈，有许多这样的例子。例如搜索西海或者海岸时，搜不到大华西海岸酒店，搜索兵马俑时，搜不到秦始皇兵马俑博物馆,搜索肯尼亚时搜不到肯尼亚山。这都是因为Sphinx-for-Chinese使用mmseg得到最优结果后，就不在进行细分的结果。拿大华西海岸酒店这个例子来说，词典里有大华，西海岸，酒店，华西，西海，海岸这些词，根据mmseg得到的最优分词结果，分成大华+西海岸+酒店，这个分词的结果也是正确的，可是搜索西海，海岸就搜不到它的。问过Sphinx-for-Chinese的开发人员后，要想支持更细粒度的分词，只有修改源码。
在组长划出一条线，需要在哪一部分代码后，一个最简单的想法是，对于mmseg中每一步得到的最优结果，都进行更细粒度的划分。例如上面的例子，对于西海岸进行更细粒度划分后，就可以得到西海和海岸，这样搜索西海和海岸时，就可以搜索到。于是立马动手写，折腾一个上午后，果然可以搜到了，这样就达到了同城旅游中酒店搜索的效果了。可是搜索华西还是搜不到，而携程则可以搜到，在携程里，搜索西也可以搜到它。仔细考虑后，在原来的代码里只需要很少的修改就可以做到搜索华西是也可以搜到它，搜索效果已经超过了同程旅游。在增加单字索引后，搜索效果和携程相当接近。
相信许多使用Sphinx-for-Chinese都会遇到类似的问题，也都将用各自的办法解决这个问题。这里将这一部分代码开源，也算是对开源事业的一点点贡献。事实上，需要修改的地方并不是很多。这里我使用的是sphinx-for-chinese-2.2.1-dev-r4311版本,相信其它版本也可以进行类似的修改。需要修改的文件只有一个，那就是sphinx.cpp。
在2244行附近，class CSphTokenizer_UTF8Chinese : public CSphTokenizer_UTF8_Base这个类中,增加以下数据成员1
2
3
4
5
6
7int m_totalParsedWordsNum; //总共得到的分词结果
int m_processedParsedWordsNum; //已经处理的分词个数
int m_isIndexer; //标示是否是indexer程序
bool m_needMoreParser; //标示是否需要更细粒度分词
const char * m_pTempCur; //标示在m_BestWord中的位置
char m_BestWord[3 * SPH_MAX_WORD_LEN + 3]; //记录使用mmseg得到的最优分词结果
int m_iBestWordLength; //最优分词结果的长度
在6404行附近CSphTokenizer_UTF8Chinese1
2
3
4
5
6
7char *penv = getenv("IS_INDEXER");
if (penv != NULL) {
m_isIndexer = 1;
} else {
m_isIndexer = 0;
}
m_needMoreParser = false;
在6706行附近BYTE * CSphTokenizer_UTF8Chinese1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33if(m_isIndexer && m_needMoreParser) { //对最优结果进行进一步细分
while (m_pTempCur < m_BestWord + m_iBestWordLength) {
if(m_processedParsedWordsNum == m_totalParsedWordsNum) {
size_t minWordLength = m_pResultPair[0].length;
for(int i = 1; i < m_totalParsedWordsNum; i++) {
if(m_pResultPair[i].length < minWordLength) {
minWordLength = m_pResultPair[i].length;
}
}
m_pTempCur += minWordLength;
m_pText=(Darts::DoubleArray::key_type *)(m_pCur + (m_pTempCur - m_BestWord));
iNum = m_tDa.commonPrefixSearch(m_pText, m_pResultPair, 256, m_pBufferMax-(m_pCur+(m_pTempCur-m_Best
Word)));
m_totalParsedWordsNum = iNum;
m_processedParsedWordsNum = 0;
} else {
iWordLength = m_pResultPair[m_processedParsedWordsNum].length;
m_processedParsedWordsNum++;
if (m_pTempCur == m_BestWord && iWordLength == m_iBestWordLength) { //是最优分词结果,跳过
continue;
}
memcpy(m_sAccum, m_pText, iWordLength);
m_sAccum[iWordLength]='\0';
m_pTokenStart = m_pCur + (m_pTempCur - m_BestWord);
m_pTokenEnd = m_pCur + (m_pTempCur - m_BestWord) + iWordLength;
return m_sAccum;
}
}
m_pCur += m_iBestWordLength;
m_needMoreParser = false;
iWordLength = 0;
}
在 iNum = m_tDa.commonPrefixSearch(m_pText, m_pResultPair, 256, m_pBufferMax-m_pCur);语句后面，增加如下语句1
2
3
4
5
6
7
8
9
10
11
12
13
14
15if(m_isIndexer && iNum > 1) {
m_iBestWordLength=getBestWordLength(m_pText, m_pBufferMax-m_pCur); //使用mmseg得到最优分词结果
memcpy(m_sAccum, m_pText, m_iBestWordLength);
m_sAccum[m_iBestWordLength]='\0';
m_pTokenStart = m_pCur;
m_pTokenEnd = m_pCur + m_iBestWordLength;
m_totalParsedWordsNum = iNum;
m_needMoreParser = true;
m_processedParsedWordsNum = 0;
memcpy(m_BestWord, m_pText, m_iBestWordLength);
m_BestWord[m_iBestWordLength]='\0';
m_pTempCur = m_BestWord;
return m_sAccum;
}
需要修改的地方就这么多。重新编译，生成后indexer后,设置环境变量,export IS_INDEXER=1，重建索引即可。这里需要注意的一点是，必须使用修改代码之前的searchd，这样才会符合我们的需求，如果使用修改代码之后的searchd,搜索西海时，会分成西海，西，海，然后去搜索，这就不是我们想要的。
对于代码，有几个关键的地方需要分明的。
1.GetToken函数
这个行数每次返回一个词，也就是分词的结果，返回前，需要设置m_pTokenStart和m_pTokenEnd,标示这个词在内容中的开始位置和结束位置。当返回值为NULL时，标示分词结束
2.m_pCur
这个用来标示当前的指针在内容的偏移位置，前面说到的设置m_pTokenStart和m_pTokenEnd就需要用到这个值
3.commonPrefixSearch函数
调用这个函数会返回所有共同前缀的词，结果保存在m_pResultPair中。例如m_pText当前位置是西，则会返回西，西海，西海岸这三个有共同前缀的词。
4.getBestWordLength函数
这个函数使用mmseg算法，得到下次分词最优结果的长度。例如m_pText当前位置是西，最优分词结果是西海岸，而在utf-8中，一个字为三个字节，所以函数返回8。
因为代码简单，所以就不细说了。这个修改，唯一不足的是，无法做到精确匹配。也是说，假设两个地点，一个是北京，一个是北京大学，搜索北京时，无法保证北京是排在第一个，即使它和搜索词精确匹配。这是因为在对北京进行更细粒度分词时，将北京分成北京,北,京这个三个词，这样破坏了Sphinx用来判断精确匹配的一些设置。为了纠正这个错误，组长和我又写了一些代码，这部分新增的代码就没有上面那部分好理解了，同时写的也有一些别扭。
在论坛和网上找了一下，发现django-pagedown可以满足需求，搜索之后，按照https://pypi.python.org/pypi/django-pagedown/0.1.0 进行添加。
首先是安装
pip install django-pagedownpagedown to your INSTALLED_APPSpython manage.py collectstatic --noinput1.首先pip install django-pagedown下载
2.之后添加pagedown到项目的’INSTALLED_APPS’中，
3.执行命令python manage.py collectstatic –noinput，收集js,css等django-pagedown用到的静态文件。
之后开始添加，我的博客是在blog目录下,在目录里创建forms.py,添加如下内容
1 | from pagedown.widgets import AdminPagedownWidget |
这里是将content字段设置为markdown编辑，之后在admin.py中添加如下内容：1
2
3
4
5
6from django.contrib import admin
from blog.models import Post
from blog.forms import PostForm
class PostAdmin(admin.ModelAdmin):
form = PostForm
admin.site.register(Post, PostAdmin)
搞定。这样之后，在编辑content时，在它的下方就会有一个markdown的解析成HTML的结果。这里，我在数据库中只保存了markdown的原始内容，显示时还需要将它解析成HTML，这个另外再说。
在开发环境中，使用Django自带的server,css这些静态资源都能够找到，可是用了gunicorn后,就找不到css等静态资源了，不知道如何是好，只记得之前看到在什么地方提到开发环境和生产环境是存在一些差异的。问过志容，志容说是要配置Nginx，可是我用gunicorn,根本都没有通过nginx。
今天正好看文档，正好看到，于是记下来。在https://docs.djangoproject.com/en/dev/howto/static-files/ 这个页面里有说到如何设置。
Set the STATIC_ROOT setting to the directory from which you’d like to serve these files, for example:
1 | STATIC_ROOT = "/var/www/example.com/static/" |
Run the collectstatic management command:
1 | $ python manage.py collectstatic |
为了避免硬编码，将STATIC_ROOT设置为os.path.join(BASE_DIR, ‘static’)后，
运行python manage.py collectstatic即可
