用Python写一个小小的爬虫程序 (Python Spider)

Python有一个urllib的库，可以很方便的从给定的url抓取网页，以下这段程序实现了抓取一个url并存到指定文件的功能：爬虫工作的基本原理就是，给定一个初始的url，下载这个url的网页，然后找出网页上所有满足下载要求的链接，然后把这些链接对应的url下载下来，然后再找下载下来的这些网页的url，我们可以用广度优先搜索实现这个算法，不过，首先得有一个函数找出网页上所有的满足要求的url，下面这个例子用正则表达式找出url.

最后就是广度优先搜索了，这个实现起来也很简单：
作者用上面的算法，感觉速度还行，1小时可以抓10000多网页，可以满足小型系统的要求。

N-最短路径分词算法

NSP分词算法是句子粗分的基本算法，在中科院计算所的文章中有详细描述。但是看了不甚明白，今天实现了这个算法，主要用的还是图论的基本算法Dijkstra算法。

将分词转化为图的最短路径问题
假设要切分一下句子 ：主席出现在这里。可将其转化为以下的图：

从而，找出这个句子的最短切分的问题就可以转化为找出上图的0-->7最短路径的问题。这里所有边的权值都是1。

Dijkstra最短路径算法
关于这个算法的描述，网上很多，诸多教科书中也有描述，这里就不详述了。我们现在任务是根据Dijkstra算法计算出的源点0到所有点的最短路径值distace[]来找出所有的最短路径。
比如上图就有2条最短路径，对应两种切分方法：

1. 0->2->4->5->7 主席/出现/在/这里
2. 0->2->3->5->7 主席/出/现在/这里

可以用广度优先搜索来找出所有的路径。算法如下：
Input : 源点S，汇点T，distance[]

1. Queue VQ，用来作为广度优先搜索的队列, VQ.append(T)
2. while(!VQ.empty())
3. Vertex V = VQ.pop()
4. if V == S :
5. 回溯出一条路径
   
6. for vn in vertexlist :
7. if distace[vn] == distacnce[V]-1 and w(vn,V) == 1 :
8. VQ.append(vn)

这以算法的复杂度主要取决于Dijkstra算法，而后面的回溯过程是和最短路径数成正比的。
Dijkstra算法的复杂度取决于图的数据结构，在最好的情况下可以达到VlogV的复杂度。

Emacs 网上资源

1. Emacs的日常生活
2. 在Emacs下用C/C++编程

Emacs 语法提示 --> Semantic

今天搞了一下Emacs的语法提示，参考了王垠的主页关于Semantic的介绍，试用了一下发现不错。

senator可以在已经分析的文件里提取匹配前缀的符号进行补全。有两种补全方式：

1. senator-complete-symbol : 补全当前的部分变量名，函数名或类型名。我将它绑定在C-l上。
2. senator-completion-menu-popup : 弹出一个补全菜单。我将它绑定在C-q上。

在.emacs文件中加入2行：
(global-set-key "\C-q" 'senator-completion-menu-popup)
(global-set-key "\C-l" 'senator-complete-symbol)

以下是我的屏幕截图：

Emacs C && C++ (转载)

http://www.emacs.cn/Doc/CProgram

Emacs对于编辑程序有很多方便的功能，下面是在编辑C程序时常用到的一些功能。

下面是一个示例的.emacs文件:

(add-hook 'c-mode-hook 'linux-c-mode)
(add-hook 'c++-mode-hook 'linux-cpp-mode)
;; 设置imenu的排序方式为按名称排序
(setq imenu-sort-function 'imenu--sort-by-name)
(defun linux-c-mode()
;; 将回车代替C-j的功能，换行的同时对齐
(define-key c-mode-map [return] 'newline-and-indent)
(interactive)
;; 设置C程序的对齐风格
(c-set-style "K&R")
;; 自动模式，在此种模式下当你键入{时，会自动根据你设置的对齐风格对齐
(c-toggle-auto-state)
;; 此模式下，当按Backspace时会删除最多的空格
(c-toggle-hungry-state)
;; TAB键的宽度设置为8
(setq c-basic-offset 8)
;; 在菜单中加入当前Buffer的函数索引
(imenu-add-menubar-index)
;; 在状态条上显示当前光标在哪个函数体内部
(which-function-mode)
)
(defun linux-cpp-mode()
(define-key c++-mode-map [return] 'newline-and-indent)
(define-key c++-mode-map [(control c) (c)] 'compile)
(interactive)
(c-set-style "K&R")
(c-toggle-auto-state)
(c-toggle-hungry-state)
(setq c-basic-offset 8)
(imenu-add-menubar-index)
(which-function-mode)
)

一此有用的快捷键：

• C-c C-c 注释区域，此命令等同于M-x comment-region，但C-c C-c仅适用于C程序，而M-x comment-region适用于任何程序。
• C-u C-c C-c :: 在c-mode下C-c C-c comment-region，C-u C-c C-c是uncomment-region.
• C-M-\ 对齐一个区域，用些命令要先保证区域已经被选中，则用系统默认的对齐方式进行对齐。
• C-c C-q 自动对齐一个函数。将光标停在一个函数体内，然后按这个键，可以自动将函数的内容按默认的对齐方式对齐。
• TAB 重新缩进当前行
• C-c . 设置缩进风格（按TAB键可列出可用的风格，缺省的为gnu，其缩进为2个字符；linux为8个；k&r为5个…）
• M-/ 自动补齐（缓冲区中能找得到的串）
• M-; 行尾加入注释
• C-c C-e 扩展宏，察看当前宏的值
• C-c C-\ 通过'\'连接多行代码

子模式

auto-state 当你输入时自动缩进，自动换行

hungry-state 当你Backspace时，自动删除尽可能多的空白和空行

• C-c C-t 同时转换(开/关)auto-state和hungry-state子模式
• C-c C-a 转换 auto-state 子模式
• C-c C-d 转换 hungry-state 子模式

编译与调试

• M-x compile 可以输入命令对程序文件进行编译，编译器的输出在一个另外一个子窗口中显示，将光标移到*compilation* 中的一行错误提示上击回车（或直接鼠标中键）即可在程序中定位错误。
• M-x gdb RET 调试
• C-x ` （出错信息中）下一个错误，一个窗口显示错误信息，另一个显示源码的出错位置
• C-c C-c 转到出错位置

启动gdb调试器后，光标在源码文件缓冲区中时：

• C-x SPC 在当前行设置断点
• C-x C-a C-s step
• C-x C-a C-n next
• C-x C-a C-t tbreak
• C-x C-a C-r continue

中国姓氏:单姓和复姓

中国目前的复姓有以下80个 :
欧阳、太史、端木、 上官、司马、东方、独孤、南宫、万俟、闻人、夏侯、诸葛、尉迟、公羊、赫连、澹台、皇甫、宗政、濮阳、公冶、太叔、申屠、公孙、慕容、仲孙、钟离、长孙、 宇文、司徒、鲜于、司空、闾丘、子车、亓官、司寇、巫马、公西、颛孙、壤驷、公良、漆雕、乐正、宰父、谷梁、拓跋、夹谷、轩辕、令狐、段干、百里、呼延、 东郭、南门、羊舌、微生、公户、公玉、公仪、梁丘、公仲、公上、公门、公山、公坚、左丘、公伯、西门、公祖、第五、公乘、贯丘、公皙、南荣、东里、东宫、 仲长、子书、子桑、即墨、达奚、褚师

中国排名前300名的姓氏 :
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程 32曹 33袁 34邓 35许 36傅 37沈 38曾 39彭 40吕
41苏 42卢 43蒋 44蔡 45贾 46丁 47魏 48薛 49叶 50阎
51余 52潘 53杜 54戴 55夏 56钟 57汪 58田 59任 60姜
61范 62方 63石 64姚 65谭 66廖 67邹 68熊 69金 70陆
71郝 72孔 73白 74崔 75康 76毛 77邱 78秦 79江 80史
81顾 82侯 83邵 84孟 85龙 86万 87段 88曹 89钱 90汤
91尹 92黎 93易 94常 95武 96乔 97贺 98赖 99龚 100文


101庞102樊103兰104殷105施106陶107洪108翟109安110颜
111倪112严113牛114温115芦116季117俞118章119鲁120葛
121伍122韦123申124尤125毕126聂127丛128焦129向130柳
131邢132路133岳134齐135沿136梅137莫138庄139辛140管
141祝142左143涂144谷145祁146时147舒148耿149牟150卜
151路152詹153关154苗155凌156费157纪158靳159盛160童
161欧162甄163项164曲165成166游167阳168裴169席170卫
171查172屈173鲍174位175覃176霍177翁178隋179植180甘
181景182薄183单184包185司186柏187宁188柯189阮190桂
191闵192欧阳193解194强195柴196华197车198冉199房200边

201辜201吉203饶204刁205瞿206戚207丘208古209米210池
211滕212晋213苑214邬215臧216畅217宫218来219嵺220苟
221全222褚223廉224简225娄226盖227符228奚229木230穆
231党232燕233郎234邸235冀236谈237姬238屠239连240郜
241晏242栾243郁244商245蒙246计247喻248揭249窦250迟
251宇252敖253糜254鄢255冷256卓257花258仇259艾260蓝
261都262巩263稽264井265练266仲267乐268虞269卞270封
271竺272冼273原274官275衣276楚277佟278栗279匡280宗
281应282台283巫284鞠285僧286桑287荆288谌289银290扬
291明292沙293薄294伏295岑296习297胥298保299和300蔺

Emacs ECB 的安装（转载）

ECB 是Emacs中浏览代码的一个工具，今天刚装了，感觉不错 。下面分享一下安装的方法，嘿嘿。由于是参考了别人的安装方法，所以原文转载：

一、下载
ECB是CEDET工具包中的一项，可以从以下地址下载：
http://sourceforge.net/projects/ecb/
他还需要其她几个软件包
speedbar
eieio
semantic
下载地址：
http://sourceforge.net/projects/cedet/

将这几个软件包解压到emacs的目录下，我的emacs配置目录为
/usr/local/share/emacs/21.1/
site-lisp/
ecb
speedbar
eieio
semantic

然后进行配置，顺序为：speedbar eieio semantic ecb

二、配置
1.speedbar配置
在site-lisp/subdirs.el中加入
(add-to-list 'load-path "/path/speedbar")
我的为:
(add-to-list 'load-path "/usr/local/share/emacs/speedbar")
然后加入:
(autoload 'speedbar-frame-mode "speedbar" "Popup a speedbar frame" t)
(autoload 'speedbar-get-focus "speedbar" "Jump to speedbar frame" t)
(global-set-key [(f4)] 'speedbar-get-focus)


如果你用Emacs,加入:
(define-key-after (lookup-key global-map [menu-bar tools])
[speedbar] '("Speedbar" . speedbar-frame-mode) [calendar])

如果你用XEmacs,加入：
(add-menu-button '("Tools")
["Speedbar" speedbar-frame-mode
:style toggle
:selected (and (boundp 'speedbar-frame)
(frame-live-p speedbar-frame)
(frame-visible-p speedbar-frame))]
"--")

;; Texinfo fancy chapter tags
(add-hook 'texinfo-mode-hook (lambda () (require 'sb-texinfo)))

;; HTML fancy chapter tags
(add-hook 'html-mode-hook (lambda () (require 'sb-html)))
(autoload 'rpm "sb-rpm" "Rpm package listing in speedbar.")
;; w3 link listings
(autoload 'w3-speedbar-buttons "sb-w3" "s3 specific speedbar button generator.")

XEmacs Emacs 20.2版本以前的加入:
;; chapter listings
(autoload 'Info-speedbar-buttons "sb-info" "Info specific speedbar button generator.")
;; folder listings
(autoload 'rmail-speedbar-buttons "sb-rmail" "Rmail specific speedbar button generator.")
;; current stack display
(autoload 'gud-speedbar-buttons "sb-gud" "GUD specific speedbar button generator.")
以后的加入
(eval-after-load "info" '(require 'sb-info))


2.eieio 配置
在site-lisp/subdirs.el中加入
(add-to-list 'load-path "/path/eieio")
我的为:
(add-to-list 'load-path "/usr/local/share/emacs/eieio")


3.semantic 配置
在site-lisp/subdirs.el中加入
(add-to-list 'load-path "/path/to/semantic")
(setq semantic-load-turn-everything-on t)
我的为:
(add-to-list 'load-path "/usr/local/share/emacs/semantic")
(setq semantic-load-turn-everything-on t)

4.ecb 配置

在site-lisp/subdirs.el中加入
(add-to-list 'load-path "/path/ecb")
我的为:
(add-to-list 'load-path "/usr/local/share/emacs/ecb")

在~/.emacs中加入
(require 'ecb)

三、使用

M-x ecb-activate 激活ECB
M-x ecb-show-help 查看帮助


四、其它

如果你想加速这些程序的执行，那么就要将EL文件编译成ELC文件。
查看相应程序的Makefile文件，修改LOADPATH变量，然后make即可

Emacs 的一些技巧

1. 注释一段代码：选中要注释的区域，按 C-c C-c就可以注释这一区域，如果要取消注释，用鼠标选择这一区域，按C-u C-c C-c。


2. 改变编辑器的字体，M-x set-default-font 然后按tab键，就会出现所有的font，或者也可以修改.emacs配置文件，我的配置文件是：
   
   (set-default-font "-adobe-courier-medium-r-normal--14-100-100-100-m-90-iso10646-1")
   


3. 改变缩进方式，C-c .，然后按Tab键，可以选择缩进方式，我用的是linux.
   

Windows和Solaris上Boost安装和编译

文章转自 http://www.stlchina.org/twiki/bin/view.pl/Main/BoostInstall

0 前言

大卫注：这是当初研究boost时的笔记，最近看到论坛上有人问，所以就贴出来共享一下。其实个人认为，boost目前还不适于进行应用开发，毕竟 boost库太大了（当然，你可以只用一部分，但程序的可维护性始终是个问题），除非你想一探C++研究前沿的Meta Programming这个Generic Programming的神奇世界。强烈建议boost的研究者在研究boost之前研究一下一个小得多的模板库loki，boost中的很多让你无法理 解的技术在loki库中被大量运用，并且这个库的作者专门写了Modern C++ Design来解说该库的实现。此外，如果你要研究boost，开始时不要编译所有的库，如Python，thread，test等，因为等你花几个小时 编译完了，你可能发现，你根本就用不到这些库，或者对它根本就不感兴趣，等到你研究完比较小的几个库，对boost有了充分了解的时候再来编译也不迟。

注：

1. 开始前请确认你的OS中已经安装了适当的编译器，以下Windows环境中以Windows 2000 + VC6为例，Unix环境中以Solaris 9 + GCC 3.4.2为例；
2. 以下以$BOOSTDIR表示boost的存放目录，请自行根据实际情况进行修改。

1 下载 Boost + 解包（略）

---

2 编译jam

---

2.1Windows

到$BOOSTDIR\tools\build\jam_src 下执行build.bat对jam进行编译，编译结果将存放在$BOOSTDIR\ tools\build\jam_src\bin.ntx86下。如果你在执行该批处理程序过程中遇到问题，如报告无法找到编译器相关程序，请执行 X:\Program Files\Microsoft Visual Studio\VC98\Bin\VCVARS32.bat 以建立VC的基本环境变量。

2.2 Solaris 9

到$BOOSTDIR\tools\build\jam_src下执行./build.sh对jam进行编译，编译结果将存放在$BOOSTDIR\tools\build\jam_src\bin.solarisx86下。

3 设置环境变量

---

（注：这一步其实可以省略，直接在（三）中通过-s输入到命令行即可，但设置可以让命令行更清晰、简单一点。）

3.1 Windows

我的电脑点右键->属性->高级->环境变量->user variable或system variable中：
PATH最后添加bjam存放目录，如：
$BOOSTDIR\tools\build\jam_src\bin.ntx86
新建环境变量MSVCDIR，并在变量值一栏中填入VC安装目录，如：
X:\Program Files\Microsoft Visual Studio\VC98
新建环境变量：
PYTHON_ROOT=X:\Program Files\Python2.3.4
PYTHON_VERSION=2.3

3.2 Solaris 9

在.profile中PATH后添加编译后的jam的存放目录。
并增加
PYTHON_VERSION=2.3
export PYTHON_VERSION
注意，无需设置PYTHON_ROOT，Solaris下jam会自动处理。

4 编译Boost

---

4.1 Windows

命令：

jam -sBOOST_ROOT=. -sTOOLS=msvc "-sBUILD=debug release static/dynamic"

以上命令解释如下：

-s 即set，设置环境变量；

BOOST_ROOT boost的存放目录

TOOLS 你选择的toolset，如gcc、msvc（即vc6）、vc7.1，此外还有gcc-stlport、msvc-stlport、vc7.1- stlport，表示同时使用stlport。具体支持何种toolset，大家可以自行到$BOOSTDIR\tools\build\v1看个究竟。 BUILD 编译类型，上述选项表示编译出支持static和dynamic链接的debug和release版本（4个版本）。

编译后的lib、dll将被copy到$BOOSTDIR\bin\boost\libs目录下，但是这些lib、dll分散在不同的目 录下，为了便于使用，可以在上述目录下分别查找*.lib和*.dll找出这些文件，然后将他们分别全部copy到VC的lib目录和Windows的 System32目录，也可以自己建立一个专门用于存放boost的lib文件的目录，然后 依次选择Tools->Options->Directories->Library files，将上述目录路径添加到VC的环境设置中。

4.2 Solaris 9

到$BOOSTDIR下执行以下命令：

jam -sBOOST_ROOT=. -sTOOLS=gcc "-sBUILD=debug release static/dynamic"

但建议用如下命令：

jam -sBOOST_ROOT=. -sTOOLS=gcc "-sBUILD=release dynamic speed"

这样可以极大加快编译的速度，同时，个人认为像boost这样大的库，最好还是采用动态链接以减小目标程序的size，就像libstdc++，还没有见过有人去静态链接libstdc++.a，虽然系统中提供了这个静态库。