Wikipedia Path Finder

 

无聊的产物:

http://jisatsu.org/WikiAnalyze/

由于这货太占后台内存，反正也没人访问，就不再提供服务了

 

使用说明：

输入任意两个wikipedia的节点，会返回它们之间通过内部链接所形成的最短路。。。

你可以输入条目的名称，也可以输入完整的url

为了提升可玩性，我们提供了三个选项，

禁止经过国家有关的条目（数据主要来源自国家人口列表），

禁止经过日期有关的条目（主要是xxxx年，前xxx年，xxxx年代，o月x日这四种格式）

禁止经过字母有关的条目（包括所有拉丁字母和希腊字母）

并且我们又提供了一个列表，你可以在这里自由输入条目，我们将不会经过这里说出现的条目，应用这个功能，

你可以寻找两个条目之间多条路径，或许不乏一些有趣的路径~~

（可以看下条目的定义，我们支持的页面是所有主名称空间下的页面）

update:增加了随机条目功能

 

背后的故事1:

想法最初源于今年的寒假，2月份寒假时，每天待在家里，啥都不想干，就每天就度无聊地在刷vip版，

然后那段时间里vip上流行一个游戏，就是安价选两个wikipedia（当然是日文版）条目

一个做起点，一个做终点，大家一起在找如何只通过内部链接从起点到终点，

vip上一般路径要尽可能短(<=6)，速度要尽可能快，而且不能走与日期时间，地名相关的条目，不能走“xx列表”之类的条目

比如

原帖：http://hayabusa.2ch.net/news4vip/kako/1360/13608/1360812960.html

（logsoku：http://www.logsoku.com/r/news4vip/1360812960/）

原帖：http://hayabusa.2ch.net/news4vip/kako/1361/13616/1361617131.html

（logsoku：http://www.logsoku.com/r/news4vip/1361617131/）

 

和他们玩了几盘，我觉得这个游戏还是很有意思的。。。

因为

1.wikipedia链接所形成的网络的连通性超乎想象，基本你只要保证终点是有入度，起点是有出度，就一定能找到路径。。。（对于大部分情况，这个都是正确的，而事实上日文wikipedia的图的完整性比中文wikipedia要好很多，中文wikipedia上出现没有两点之间没有路的情况可能会更普遍些，这个下面我会说）

2.玩这个游戏需要思考+运气+直觉～～有机会你自己试试就知道了

3.通常，两点之间都存在的很多你完全意想不到的路，而走一些意想不到的路可能会更短，并且更有趣

举两个例子：

比如

69 名前：以下、名無しにかわりましてVIPがお送りします[] 投稿日：2013/02/14(木) 12:54:26.91 ID:NxavRf+j0 [2/2]
ファミコン3Dシステム→任天堂→ポケットモンスター→男性器→女性器→まんこ

 

从FC 3D系统到ま○こ

FC 3D系统 > 任天堂 > pokemon > 男性器 > 女性器 > ま○こ

444 名前：以下、名無しにかわりましてVIPがお送りします[] 投稿日：2013/02/14(木) 15:43:30.46 ID:OE2bGtQo0 [10/27]
プラナリア
肛門
アナルセックス
イスラーム世界の少年愛
イスラーム文化
吟遊詩人

从涡虫到吟游诗人

涡虫 > 肛门 > 肛X > 伊斯兰世界的少年爱 > 伊斯兰文化 > 吟游诗人

（好吧，当时我实时在玩的时候完全没想到往肛X的方向走。。。）

 

其实当时有日本人做了一个网站http://wikitter.info/

功能就是输入两个日文wikipedia条目，寻找其间的最短路

 

背后的故事2:

大概是今年四月份，上预科时，某次在与zjk聊天时，我无意说道了这个问题

记得当时我有些好奇，说不定wikipedia中给一个有出度的点做起点，一个有入度的点做起点，它们之间可能还真是可达的。。。我就随口说下次写个程序验证一下

然后六月中旬时，zjk跟我说他闲着无聊，就写了程序在那抓从一个点出发开始bfs抓页面

他是在自己机器上开goagent跑的（原因你懂的），他说他的程序现在连续跑了好几天，遍历了大概15w个页面

他还跟我说了些他抓页面时碰到的困难，我印象比较深的就是，他为了确定页面中的正文部分，遍历网页时判了<div>标签的个数，结果他的程序在某个页面爆了，原因是那个页面是关于html的……

我就说要和他一起搞。。。并且我提供vps跑程序

因为他的抓页面程序是C#写的，而我vps是centos，原来我还想用ruby重写下，不过zjk试了下用mono就能在linux下完美运行C#

记得那时候那程序抓页面时还有不少bug，我们折腾了好长时间，才终于修复了大部分的bug，并增加了些功能

（我不会C#，基本都是他搞的…我只是找了找bug）

zjk:终于搞完了，你说我们是从哪个条目开始抓啊？

我:当然是Hentai啦ｗｗｗ

zjk:我看看啊～～居然还真有这个条目ｗｗｗ就这个啦

我:还是中文wikipedia的高质量特色条目呢～

…半小时以后…

zjk:我x，这个Hentai出发抓出的前几百条都不能直视啊！！！

我:。。。我也发现了。。。

zjk:万一这个结果我们还要给别人看怎么办！换一个正常点的吧…

我:好吧，那就中国共产党吧～

zjk:好吧…

我:我们来找一下从Hentai到中国共产党的路吧!

zjk:好。。。

3分钟以后

我:找到了！Hentai > 萝莉控 > 宋庆龄 > gcd

zjk:我x。。。怎么发现的。。。

后来我又和zjk玩了几盘，我和他同时说一个条目，分别作为起点和终点，印象比较深的就是美少女游戏到相对论

我找到最短的一条路是

美少女游戏 > 萌 > 科学家 > 伪科学  > 相对论

（为什么萌能到科学家。。。因为有一种萌属性叫科学家。。。）

（不同寻常的科学家道相对论的最短路径就是从伪科学走，走其他物理学家什么的都不能直达相对论）

。。。。。。

不过这次从共产党开始的抓取不小心被我取消了

zjk建议我从一个离Hentai不要太近也不要太远的条目开始抓取，最好能在1k条以后才密集出现的那些有些不堪入目条目…

想了想我就从魔法少女这个开始抓取了

结果后来我发现那程序还有个bug

.net的url转换函数会把魔法少女会被转换成%e9%ad%94%e6%b3%95%e5%b0%91%e5%a5%b3

而wikipedia里则是%E9%AD%94%E6%B3%95%E5%B0%91%E5%A5%B3

这就导致魔法少女这个页面重复访问…

我发现以后，不等zjk修复，就决定从一个名称纯英文条目出发，避免这个问题，正好听到kotoko的歌就从改从KOTOKO开始遍历了

我们程序在vps上大概跑了9～10天终于结束了KOTOKO开始的bfs，抓到了81W个页面，约430M的边表

 

背后的故事3:

或许Wikipedia最令我们头疼的问题就是重定向页面的问题

这个问题是我们从KOTOKO出发抓取了30W左右个页面时，对不完整的数据进行分析时才发现

wikipedia存在一种重定向，这个重定向并不同与http的重定向，他们返回的是不同的url，但是正文是完全一样的

比如Prc，PRC，共產中國，北京政权 ，中華人民共和國均为中华人民共和国的重定向页

并且由于繁体字问题，此重定向在中文维基百科中大量出现

如果要从抓取页面的程序层次进行重定向页识别，要进行大量的修改

如果简单的看两个的出边，如果边表完全一样就认为这的是重定向的话，又会遇到这么两个问题

1.对于一些讲述类似内容却并且出度很少的条目，他们的边表有可能相同

2.对于一些条目，它和它的重定向页不是在同一时期抓获，由于我们抓取前后花了9天，他的边表可能已经被修改而发生了变化

我们就还是决定先无视重定向搞一回

数据抓完后，我立刻用c++写了个找最短路简单的程序（数据量很大。。。为了效率，只能用c++）

zjk建议我们做一个web版，但是那时候我的程序内存占用要600多M，而VPS的内存就只有1G

我折腾了半天，做了各种优化，才把终于把内存占用降到了400M左右

我和zjk都没接触过web，zjk会些.net，他稍微看了下aspx，用mono做了个aspx的简易接口。。。就得到了我们的第一个版本

同时我们对我们抓取的数据稍微进行了一些分析，

81W个页面了大概有28W个疑似重定向页…（通过边表相同来判断的）

我对图做了一次tarjan scc，得到了1700多个强联通分支，不过看一下因为不明原因我们抓的数据时，有几个条目出了些问题，边表没打出来…（又有问题…），并且有重定向页面的干扰，这个结果也没什么意义

 

背后的故事4:

可笑的是，我无意间发现了一个页面Wikipedia:数据库下载…

于是我们的所有问题都解决了。。。之前就是在那白折腾了。。。

于是。。。就有了现在这个版本了。。。。

 

FAQ：

Q：为什么是asp，你们程序跑在windows上吗？

A：因为我什么都不会。。。zjk会些.net，就让他用asp去写了，不过奇葩的是我们是跑在linux上的。。。

Q：为什么网页前端这么简陋？

A：还是因为我不会css/js。。。而且我对网站前端暂时也没什么兴趣去学。。。

Q：为什么是jisatsu.org(自杀.org)

A：我也不知道为啥就买了的闲置域名…

Q：为什么我输入菲律宾和马来西亚结果却是

菲律宾->馬來西亞  而不是 菲律宾->马来西亚

A：马来西亚是馬來西亞的一个重定向页，菲律宾中的链接是通向馬來西亞，假设起点终点发别为s，t，我们的bfs在找到t以及t的某个重定向页是就会停止返回结果…不然的话路就会更长了

Q：为什么有些页面你的程序返回无法找到

A：

1.保证这个页面是在主名称空间下

2.如果输条目英文条目注意大小写，注意包括空格在内的特殊符号的话，如果输入条目名（url）查找失败的话则请输入url（条目名）

3.我们缓存的是6月25号左右的数据，这个页面是这个时间点以后新建的。

4.有问题请汇报bug

……

…

.