I will write some articles talking about lucene.
Let's begin~~~
Jarkarta Lucene (http://jakarta.apache.org/lucene/) is a high-performance, full-featured, java, open-source, text search engine API written by Doug Cutting.
Note that Lucene is specifically an API, not an application. This means that all the hard parts have been done, but the easy programming has been left to you. The payoff for you is that, unlike normal search engine applications, you spend less time wading through tons of options and build a search application that is specifically suited to what you're doing. You can easily develop a custom search application, perfectly suited to your needs. Lucene is startlingly easy to develop with and use.
I'm going to assume that you're a basically competent programmer and that you are basically competent in java.
2007年6月12日星期二
2007年6月4日星期一
from my senior school classmate
From xiaonei
Published by Zhichao Shan
已经酝酿很长时间的本文终于出场了。
写本文的主要目的：1 很多人看了我前面大量的历史日志后，对我的数学水平产生了怀疑；2 有高中的校友师妹咨询关于大学数学学习的问题；3 概率论是数学中一个重要而美的分支，可惜多数同学尚没有机会看到其冰山一角。
本文的读者适用范围：最低标准是学过工科专业的高等数学和概率论，最高标准不清楚（也许水平比我高的人就不屑于读了）
当我跟皇上提到要写这篇文章的想法时，我提到：试图用比较短的篇幅让只要有初等概率论基础的人，也能看懂，从而对较深的概率论的研究对象和有趣的结论有一个初步的了解，激发其进一步深入学习概率论的兴趣。皇上说：那可不容易，相当于一个毕业设计了。我觉得，确实如此，本文是基本失败还是基本成功，还要看读者的评价。
要想引入本文的内容，首先从数学美的定义说起。关于数学美，我比较欣赏的有两种观点，一是Birkhoff的观点，数学美=逻辑的复杂程度/表述的复杂程度；（注：那个/是除号的意思，就是说表述简单，但证明复杂，理论背景深刻的数学是好的数学，例如我下面给出的例子）二是Von Neumann的观点，数学的活力依赖于与它有联系的科学分支的多寡与分支的活力。也许做应用的人更喜欢后者，但我是比较喜欢前者的。因此，我下面的主要内容就是介绍一些概率论中的基本例子，这些例子的表述是相当简单的，但得到这些例子的手段却比较复杂。我将试图把每个例子表述清楚，让只要有初等概率论基础的读者就知道在说什么，但对得到这些结果的证明过程则一律省略，只简要提出涉及的基本工具，但其中有些比较简单的细节会给大家留为习题。这些例子一律来自伟大的Durrett的著作：Probability theory and examples——我认为最优秀的概率论教材。
例1 Coupon collector问题：X1,X2,…是独立同分布，均匀的取自集合{1，…，n}的随机变量序列。大家把集合{1，…，n}想象为若干张扑克牌，每次我们等概率的取一张扑克牌，取完放回。t(n,k)=inf{m: /{X1,…,Xm}/=k}，意思就是手中取过k种不同的扑克牌所需的次数。T(n)=t(n,n)表示取过所有扑克牌所需的次数。X(n,k)=t (n,k)-t(n,k-1)，则X(n,k)服从参数是1-(k-1)/n的几何分布（思考题！），它的期望和方差可求，且容易发现X(n,1),…, X(n,n)相互独立，从而可以求出ET(n),Var T(n)（习题！)。且去证明（T(n)-ET(n)）/nlogn 依概率趋近于0.（数学基础稍微深一些的同学都知道，L2收敛蕴含依概率收敛）最终得到一个漂亮的结论：
T(n) / nlogn 依概率收敛于1.
数学基础比较少的同学可以直接看这一行，我把这一行的实际意义说清楚：就是假设我们要收集的邮票有n张，而每次别人给我们提供的邮票恰恰是等概率的，那么要想把n张收集全，需要的时间依概率趋近于 nlogn。所以大家就可以发现，为什么我们想集邮时，初期集的比较快，但到快集齐时总是很难找到仅差的那几张，这就是因为上面的nlogn的阶大于线性函数。
作为更为深层次的读者，我要说的是，在随机变量收敛性问题的研究中，独立性和矩总是常见的关注对象。为什么我们非常喜欢方差这个概念呢？我想一个重要的性质就是：对于独立的随机变量，方差对和有分配律。于是二阶中心矩才会成为最重要的矩。通过对矩的估计把随机变量的收敛性问题，转化为实数序列的收敛性问题，最后完全是数学分析的东西，这种手段是屡屡使用的。
例2 非对称的简单随机游动问题：X1,X2,…独立同分布，P(X1=1)=p, P(X1=-1)=1-p=q,Sn=X1+…+Xn.
对于数学基础不太好的同学，我简单介绍一下这个问题的背景，其实很好理解。设有一个点在0时刻位于实轴的原点0处，它在每个时刻以概率p向右跳跃一个单位长度，以概率q向左跳跃一个单位长度，且跳跃的方向与以前每次跳跃的情况是独立的。Sn表示的是：n时刻这个点所在的位置。
我们有如下非常精彩的结论：
1 Tx=inf{n:Sn=x} Tx的直观意思就是，这个点首次跳到x的位置的时刻。那么对于任意的a< 0< b，P(Ta < Tb)=[ f(b)-f(0) ] / [ f(b)-f(a) ] 这里函数f(x)=[(1-p)/p]的x次幂。
上面的这个等式的直观意义：a是负半轴上一点，b是正半轴上一点，点没到b之前先到a的概率被计算了出来。
得到这个结论最快的方法就是用鞅论。鞅实在是一个漂亮的东西，而它的漂亮之处就在于它与停时结合在一起后的巨大威力。用N表示Ta和Tb中的较小值，则N是停时。首先要说明的是N小于无穷大。要得到这个结论，我掌握的有三种方法：
（1） 通过EN小于无穷大，得到这个结论，这事实上是通过一个强的多的结论说明的，具体见Durrett书181页。
（2） 通过鞅收敛定理，见Durrett书275页。其中用了一个重要结论：一致有界的鞅序列必然一致可积（应该是很显然的吧，呵呵）。
（3） 通过马氏链的性质：对于一个有可列状态，不可约的马氏链，用F表示状态空间的一个有限子集，设初始状态属于F,用T表示链首次离开F的时间，则一定有T小于无穷大。（可以作为本科生三年级应用随机过程的习题，证之！）
2 ETb=b/(2p-1) 即首次到达b点的平均时间是b/(2p-1)。
处理方法还是用鞅论，这里不再多说。
关于用鞅论解决马氏链问题的例子，我还推荐数学基础比较高的同学阅读Durrett书上的（1）M/G/1排队（282页，298页，309页） （2）生灭过程（295页，301页）
本来我认为这两个例子是更加漂亮的，但考虑到数学基础一般的同学的阅读水平，就不写了。
例3 遍历定理的一个应用（Benford定律）
首先提一个问题：随机选取一个正整数，它的第一位数字是1 的概率是多少？
很多同学会武断的回答：1/9.
可是你忘记了问我一个问题：你是如何随机选取的？
也许你会说：这还用问？就是等概率的选取呗。
可是不要忘记，对于可列状态的状态空间，不存在一个概率测度，使得它在任意两个单点集上的概率相同！（思考题！）
其实一个直观的想法是：我们考虑前n个正整数中（均匀分布是可能的），首位数字是1的概率记为f(n),然后把f(n)的极限作为我上面所提问题的答案。
可是随后会不幸的发现，极限是不存在的！
于是作为习题，设前ｎ个正整数中，首位数字是１的概率记为f1(n),则f1(n)的上极限是5/9,下极限是1/9，且对于任意属于区间 [1/9,5/9]的实数a，都存在f1（n）的子序列，它的极限就是a。类似的，记前n个正整数中，首位数字是2的概率是f2(n),其上极限是 10/27,下极限是1/18.（作为数学分析的习题！）
但是，当我们转而思考这样的等比序列，1，2，4，8，16，…记这个序列的前n项中首位数字是1的概率为f1(n),则f1（n）是有极限的，且极限是 lg 2.一般地，对于任意一个非10的整数次幂的正整数q，考虑以1为首项，以q为公比的等比数列，它的前n项中首位数字是k的概率为f k（n）,则fk(n) 的极限是lg(k+1)-lgk. （证明不可能在这里给出了，大家只管从结论中去欣赏概率论之美吧！）
这个结论是非常漂亮的！叙述是非常简单的，意义是非常直观的，但并不是容易猜到的，证明所需的背景——遍历定理又是极其深刻的。读来畅快淋漓！
今年春天，陈大岳教授对我说，在现代概率论的研究中，遍历定理显现的越发重要。当看到上面这个结论后，我初步认识到遍历定理内涵的深刻和丰富。
以上仅选取三个概率论的基本例子，它们的结论的直观易懂与其所需理论背景的复杂程度形成了鲜明的对比，体现了概率论作为一个数学分支的美妙。管中窥豹，可见一斑，希望能以此激发大家深入学习概率论的兴趣，使不同数学基础的同学都能有所收获。
Published by Zhichao Shan
已经酝酿很长时间的本文终于出场了。
写本文的主要目的：1 很多人看了我前面大量的历史日志后，对我的数学水平产生了怀疑；2 有高中的校友师妹咨询关于大学数学学习的问题；3 概率论是数学中一个重要而美的分支，可惜多数同学尚没有机会看到其冰山一角。
本文的读者适用范围：最低标准是学过工科专业的高等数学和概率论，最高标准不清楚（也许水平比我高的人就不屑于读了）
当我跟皇上提到要写这篇文章的想法时，我提到：试图用比较短的篇幅让只要有初等概率论基础的人，也能看懂，从而对较深的概率论的研究对象和有趣的结论有一个初步的了解，激发其进一步深入学习概率论的兴趣。皇上说：那可不容易，相当于一个毕业设计了。我觉得，确实如此，本文是基本失败还是基本成功，还要看读者的评价。
要想引入本文的内容，首先从数学美的定义说起。关于数学美，我比较欣赏的有两种观点，一是Birkhoff的观点，数学美=逻辑的复杂程度/表述的复杂程度；（注：那个/是除号的意思，就是说表述简单，但证明复杂，理论背景深刻的数学是好的数学，例如我下面给出的例子）二是Von Neumann的观点，数学的活力依赖于与它有联系的科学分支的多寡与分支的活力。也许做应用的人更喜欢后者，但我是比较喜欢前者的。因此，我下面的主要内容就是介绍一些概率论中的基本例子，这些例子的表述是相当简单的，但得到这些例子的手段却比较复杂。我将试图把每个例子表述清楚，让只要有初等概率论基础的读者就知道在说什么，但对得到这些结果的证明过程则一律省略，只简要提出涉及的基本工具，但其中有些比较简单的细节会给大家留为习题。这些例子一律来自伟大的Durrett的著作：Probability theory and examples——我认为最优秀的概率论教材。
例1 Coupon collector问题：X1,X2,…是独立同分布，均匀的取自集合{1，…，n}的随机变量序列。大家把集合{1，…，n}想象为若干张扑克牌，每次我们等概率的取一张扑克牌，取完放回。t(n,k)=inf{m: /{X1,…,Xm}/=k}，意思就是手中取过k种不同的扑克牌所需的次数。T(n)=t(n,n)表示取过所有扑克牌所需的次数。X(n,k)=t (n,k)-t(n,k-1)，则X(n,k)服从参数是1-(k-1)/n的几何分布（思考题！），它的期望和方差可求，且容易发现X(n,1),…, X(n,n)相互独立，从而可以求出ET(n),Var T(n)（习题！)。且去证明（T(n)-ET(n)）/nlogn 依概率趋近于0.（数学基础稍微深一些的同学都知道，L2收敛蕴含依概率收敛）最终得到一个漂亮的结论：
T(n) / nlogn 依概率收敛于1.
数学基础比较少的同学可以直接看这一行，我把这一行的实际意义说清楚：就是假设我们要收集的邮票有n张，而每次别人给我们提供的邮票恰恰是等概率的，那么要想把n张收集全，需要的时间依概率趋近于 nlogn。所以大家就可以发现，为什么我们想集邮时，初期集的比较快，但到快集齐时总是很难找到仅差的那几张，这就是因为上面的nlogn的阶大于线性函数。
作为更为深层次的读者，我要说的是，在随机变量收敛性问题的研究中，独立性和矩总是常见的关注对象。为什么我们非常喜欢方差这个概念呢？我想一个重要的性质就是：对于独立的随机变量，方差对和有分配律。于是二阶中心矩才会成为最重要的矩。通过对矩的估计把随机变量的收敛性问题，转化为实数序列的收敛性问题，最后完全是数学分析的东西，这种手段是屡屡使用的。
例2 非对称的简单随机游动问题：X1,X2,…独立同分布，P(X1=1)=p, P(X1=-1)=1-p=q,Sn=X1+…+Xn.
对于数学基础不太好的同学，我简单介绍一下这个问题的背景，其实很好理解。设有一个点在0时刻位于实轴的原点0处，它在每个时刻以概率p向右跳跃一个单位长度，以概率q向左跳跃一个单位长度，且跳跃的方向与以前每次跳跃的情况是独立的。Sn表示的是：n时刻这个点所在的位置。
我们有如下非常精彩的结论：
1 Tx=inf{n:Sn=x} Tx的直观意思就是，这个点首次跳到x的位置的时刻。那么对于任意的a< 0< b，P(Ta < Tb)=[ f(b)-f(0) ] / [ f(b)-f(a) ] 这里函数f(x)=[(1-p)/p]的x次幂。
上面的这个等式的直观意义：a是负半轴上一点，b是正半轴上一点，点没到b之前先到a的概率被计算了出来。
得到这个结论最快的方法就是用鞅论。鞅实在是一个漂亮的东西，而它的漂亮之处就在于它与停时结合在一起后的巨大威力。用N表示Ta和Tb中的较小值，则N是停时。首先要说明的是N小于无穷大。要得到这个结论，我掌握的有三种方法：
（1） 通过EN小于无穷大，得到这个结论，这事实上是通过一个强的多的结论说明的，具体见Durrett书181页。
（2） 通过鞅收敛定理，见Durrett书275页。其中用了一个重要结论：一致有界的鞅序列必然一致可积（应该是很显然的吧，呵呵）。
（3） 通过马氏链的性质：对于一个有可列状态，不可约的马氏链，用F表示状态空间的一个有限子集，设初始状态属于F,用T表示链首次离开F的时间，则一定有T小于无穷大。（可以作为本科生三年级应用随机过程的习题，证之！）
2 ETb=b/(2p-1) 即首次到达b点的平均时间是b/(2p-1)。
处理方法还是用鞅论，这里不再多说。
关于用鞅论解决马氏链问题的例子，我还推荐数学基础比较高的同学阅读Durrett书上的（1）M/G/1排队（282页，298页，309页） （2）生灭过程（295页，301页）
本来我认为这两个例子是更加漂亮的，但考虑到数学基础一般的同学的阅读水平，就不写了。
例3 遍历定理的一个应用（Benford定律）
首先提一个问题：随机选取一个正整数，它的第一位数字是1 的概率是多少？
很多同学会武断的回答：1/9.
可是你忘记了问我一个问题：你是如何随机选取的？
也许你会说：这还用问？就是等概率的选取呗。
可是不要忘记，对于可列状态的状态空间，不存在一个概率测度，使得它在任意两个单点集上的概率相同！（思考题！）
其实一个直观的想法是：我们考虑前n个正整数中（均匀分布是可能的），首位数字是1的概率记为f(n),然后把f(n)的极限作为我上面所提问题的答案。
可是随后会不幸的发现，极限是不存在的！
于是作为习题，设前ｎ个正整数中，首位数字是１的概率记为f1(n),则f1(n)的上极限是5/9,下极限是1/9，且对于任意属于区间 [1/9,5/9]的实数a，都存在f1（n）的子序列，它的极限就是a。类似的，记前n个正整数中，首位数字是2的概率是f2(n),其上极限是 10/27,下极限是1/18.（作为数学分析的习题！）
但是，当我们转而思考这样的等比序列，1，2，4，8，16，…记这个序列的前n项中首位数字是1的概率为f1(n),则f1（n）是有极限的，且极限是 lg 2.一般地，对于任意一个非10的整数次幂的正整数q，考虑以1为首项，以q为公比的等比数列，它的前n项中首位数字是k的概率为f k（n）,则fk(n) 的极限是lg(k+1)-lgk. （证明不可能在这里给出了，大家只管从结论中去欣赏概率论之美吧！）
这个结论是非常漂亮的！叙述是非常简单的，意义是非常直观的，但并不是容易猜到的，证明所需的背景——遍历定理又是极其深刻的。读来畅快淋漓！
今年春天，陈大岳教授对我说，在现代概率论的研究中，遍历定理显现的越发重要。当看到上面这个结论后，我初步认识到遍历定理内涵的深刻和丰富。
以上仅选取三个概率论的基本例子，它们的结论的直观易懂与其所需理论背景的复杂程度形成了鲜明的对比，体现了概率论作为一个数学分支的美妙。管中窥豹，可见一斑，希望能以此激发大家深入学习概率论的兴趣，使不同数学基础的同学都能有所收获。
订阅：
博文 (Atom)