鬼の领地

前几天因为某些原因，我把饭否上所有的好友和关注者全部清空了。当然，如果没有程序的帮忙，估计还不等我删完我也就后悔了。

我没有那么狠心的把饭否的消息给清空，因为消息是不可恢复的（而且也太多了），但好友和关注者是可以的。做事情都给自己留后路显然是我一贯的风格，不然的话，我大概早从我家阳台跳下去了……
Read the rest of this entry »

上一篇日志里面我做了一个从 VeryCD 为 Rhythmbox 提取专辑封面的程序，后来想到豆瓣其实也有这个东西，于是又做了一个豆瓣的。然后想，既然这样我干脆把原来的封面艺人插件 fork 出来，自己开一个新项目，专门做封面艺人插件的 China Mod~

现在已经开好了，就在 Google Code 上：http://code.google.com/p/rhythmbox-artdisplay-cn/

其实说 Mod 也不算，就是加了几个扩展进去……主要是考虑到如果不 fork 似乎很单独安装，所以就 fork 出来了……那个插件看过去也很长时间没有更新了呢？

第一个版本0.1可以点击这里下载：rhythmbox-artdisplay-cn-0.1.tar.bz2，暂时还没有做任何安装包，deb 包和 arch 的包应该会随后奉上~

安装很简单，常规的 make 和 make install 就可以了~

如果各位有什么改进意见，欢迎提出~

我们知道 Rhythmbox 里面有一个插件叫做“封面艺人”，可以通过互联网下载对应专辑的封面图片。可是，那个插件使用的似乎是美国的 Amazon，中文歌曲基本找不到对应封面，怎么办呢……

想到我的很多专辑都是从 VeryCD 上下载的，那些下载页面通常都会有专辑封面图片，于是我就写了个封面艺人的扩展，让其可以从 VeryCD 上搜索专辑，并下载相应专辑封面。这个扩展可以在这里下载：verycd-cover.tar.bz2 (5KB)

下载解压后，运行其中的 compile.py，然后把除了 compile.py 以外的四个文件拷贝到 Rhythmbox 的封面艺人插件的目录就可以了，在 Ubuntu 下，那个目录是 /usr/lib/rhythmbox/plugins/artdisplay。
Read the rest of this entry »

继上一篇文章之后，我又下大力气对这个程序做了许多修改，在精确度和速度方面似乎都有些许提高。在此推出第二季~

使用真正的12px宋体

在上一次的程序中使用的 PIL 似乎是因为不支持宋体 ttc 文件中对于小字体下优化的点阵形式，才在选择小于 19px 的字号时不能正确渲染汉字。考虑到这一点，我就想到把 ttc 文件里面 12px 的点阵字体单独提取出来使用，毕竟贴吧上面显示 ID 都是用这个字号显示的。

使用 FontForge 提取出来了 simsun-12.bdf 文件，就是宋体 12px 下的点阵。参考 PIL 的手册，发现 PIL 不能直接使用 .bdf 文件，需要使用一个叫做 pilfont 的脚本转换成专有的 .pil 文件才行。我想转换就转换呗。simsun-12.bdf 一个 2.4MB 的文件，转换完就剩不到 100KB，我就觉得肯定有问题，用 PIL 导入，发现还是不能渲染中文。后来知道，这个 .pil 文件根本不支持非拉丁字母的字符，它的储存空间限定了 256 个字符……

无奈了，这意味着 PIL 完全无法支持中文点阵了……

当然，办法总归是有的，那就是——抛弃 PIL！为什么我能有这样的想法呢，因为看到 .bdf 文件是 UNIX 标准的。UNIX 标准意味着什么呢？记不记得 UNIX 有一个非常好的传统叫做，尽量使用纯文本。是的，这虽然让有些文件会变得太大，不过同时也让这些东西更容易被其他程序读取，而 .bdf 恰好即使这么一种文件。

这样读取 .bdf 点阵字体文件的程序自己写不就好了，什么额外的库都不需要……当然，纠错性极弱就是了~

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

line_count = 0
 
def read_split(f):
    global line_count
    line_count += 1
    line = f.readline()
    if not line:
        return False
    return line[:-1].split()
 
with open('simsun-12.bdf', 'r') as f:
    chars = {}
    line = ['']
    try:
        # 获得字符总数
        while line[0] != 'CHARS':
            line = read_split(f)
        # 读取所有字符
        for i in range(int(line[1])):
            assert read_split(f)[0] == 'STARTCHAR'
            line = read_split(f)
            # 编码
            assert line[0] == 'ENCODING'
            char = unichr(int(line[1]))
            line = read_split(f)
            # 绘制参数
            assert line[0] == 'BBX'
            width, height, x1, y1 = [int(x) for x in line[1:]]
            x0, y0 = (1 + x1, 12 - y1 - height)
            # 准备绘制文字
            base_image = [[0 for x in range(14)] for y in range(14)]
            # 读取并绘制文字
            line = read_split(f)
            assert line[0] == 'BITMAP'
            for y in range(y0, y0 + height):
                line = read_split(f)[0]
                bits = int(line, 16)
                bits >>= len(line) * 4 - width
                for x in range(x0 + width - 1, x0 - 1, -1):
                    base_image[y][x] = bits & 1
                    bits >>= 1
            chars[char] = base_image
            # 结束这个文字
            line = read_split(f)
            assert line[0] == 'ENDCHAR'
        line = read_split(f)
        assert line[0] == 'ENDFONT'
    except AssertionError:
        print 'line', line_count
        raise

这样所有的字符就被读入，并变成一个单色像素二位数组了。

当然，这个性能很低，在我的机器上转换读取文件的2W+字符大概需要 18s，这可能也是为什么 PIL 要选择进行转换。事实上，使用纯文本储存一直以来都给 UNIX 风格的这一类软件带来一定性能缺陷。不过其实，这很值得，因为方便。

不过这个时间确实是太长了，更何况我们到目前为止还什么都没处理。怎么办呢？两个想法：一、优化代码；二、保存处理的数据。

第一种，基本上是没什么希望了，而且即使能优化，估计效果也不会太好，可能省个几秒封顶了。第二个显然不是个坏想法。

Python 在数据的持续化方面还是有很多现成的东西的，比如 pickle 什么的。不过那个速度太慢，而且是纯文本！好吧，偶尔我也会不喜欢纯文本，因为在这里意义不大……因此选择了 marshal。marshal 也是一个用于数据持续化的库，不过仅能对 Python 的内部类型进行。我会看中它最重要的原因就是它的应用范围极其有限，只能持续化内部类型。如果一个 Python 标准库，它有很明显的限制，却没有标明不推荐或在新版中被剔除，说明它必然有一个其他库不可及的优势。对于 marshal，我猜它的优势就是效率。

使用 marshal 就很简单了……

62
63

import marshal
marshal.dump(chars, open('base_image', 'wb'))

这样后面的处理不需要不断重复这个低效的步骤了~

处理文字图像

原来是用 PIL 处理文字图像，现在抛弃 PIL 了，就得自己写了……不过这样也很好，自由发挥的空间很大了~

我猜用的是 Matrix67 大牛的那种在附近留阴影的方法，不过似乎我写的不够好就是了，怎么测试效果都不大理想。除此之外，纯 Python 实现的算法效率和 PIL 这种包装还是没得比，很简单的算法却慢的不得了……

下面是目前的处理代码：

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

#!/usr/bin/python
# - * - coding: utf8 - * -
 
import marshal
import copy
 
base_chars = marshal.load(open('base_image', 'rb'))
chars = {}
for char, image in base_chars.iteritems():
    new_image = []
    for y in range(14):
        new_row = []
        for x in range(14):
            if image[y][x]:
                value = 81
            else:
                value = 0
            if y > 0 and image[y-1][x]:
                value += 4
            if y < 13 and image[y+1][x]:
                value += 4
            if x > 0 and image[y][x-1]:
                value += 4
            if x < 13 and image[y][x+1]:
                value += 4
            new_image.append(value)
    chars[char] = new_image
 
marshal.dump(chars, open('advanced_data', 'wb'))

处理效果不是很理想就是了，耗时大概也是 30s+。

寻找相似字符

其实这个部分就是一样的了……直接贴代码好了……

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

#!/usr/bin/python
# - * - coding: utf8 - * -
 
import marshal
 
chars = marshal.load(open('advanced_data', 'rb'))
 
def image_diff(image1, image2):
    ret = 0
    for v1, v2 in zip(image1, image2):
        ret += (v1 - v2) ** 2
    return ret
 
remember_number = 5
try:
    searched = marshal.load(open('searched_chars', 'rb'))
except IOError:
    searched = {}
while True:
    input_string = unicode(raw_input('ID: '), 'utf8')
    if not input_string:
        break
    for char in input_string:
        if char not in chars:
            continue
        if char not in searched:
            diff_data = []
            image = chars[char]
            for c, v in chars.iteritems():
                if c == char:
                    continue
                diff_data.append((image_diff(v, image), c))
            diff_data.sort()
            searched[char] = diff_data[:remember_number]
        print char,
        for item in searched[char]:
            print u'({0}, {1})'.format(*item),
        print
    print
 
marshal.dump(searched, open('searched_chars', 'wb'))

和上次不同的是查找过的字会被保存下来，效率可以高一些……

继续改进

现在的主要问题就是如何提高相似度的识别精度了……目前的想法是通过逐像素比对测试两个字的相似度，最多加一些模糊化什么的处理。doggy 提出一个想法是计算连通区域面积的比例，我个人认为不大可行……我的想法是识别文字的笔画，把文字的骨架弄出来，然后对比什么的，可能效果更好吧？

不知道各位还有没有其他什么想法？

下载

最后是完整版的目前的程序以及已经生成的数据，各位有兴趣可以直接拿来试用了……find-similar-character.tar.bz2 (1.7MB)

参考资料

• 我想把simsun.ttf里的12号点阵字体单独提取出来做成一个ttf – 北大中文论坛
• Glyph Bitmap Distribution Format – Wikipedia
• Glyph Bitmap Distribution Format (BDF) Specification – Adobe Developer Support
• marshal — Internal Python object serialization – Python documentation

今天大学军训完了，不想做什么正经事，就想到前一段时间想做的寻找相似汉字的程序，用以寻找更高仿的贴吧 ID。用程序来寻找相似汉字，从另一个角度，也是从 Matrix67 大牛的一篇日志里得到的启发。不过 Matrix67 大牛使用的是 Mathematica 来寻找，我不大会 Mathematica，就想用我熟悉的 Python 来解决，毕竟 Python 是一个很强大的东西~
Read the rest of this entry »

貌似很久没发文章了，无聊冒出来发一个……

这次发的东西是很无聊的，大家知道最近世界杯在踢。不过呢，作为一个对体育几乎毫不关心的人，这事基本上也跟我没什么关系……不过我要说的呢，是关于世界杯竞猜的“赌博”游戏，貌似不止百度再做，还有网易、校内什么的都在搞。不过鉴于百度这个，比较经常上，我就也来参加了~

当然，发在这里的东西总归要有一些技术性……这次也不例外的……

我看到网易的竞猜不仅有各种形式，而且最重要的是有赔率！而百度只显示投注金额，显然不够专业，于是我就拿 Greasemonkey 插件，可以在百度投注金额的下面显示当前赔率~就像下面这样：

安装了 Firefox 的 Greasemonkey 插件的，可以点击这里安装这个脚本：tieba_guess.user.js

哦，有人大概会注意到我在前面那张图里面下注给了韩国。倒不是我多喜欢棒子，只是因为我几乎完全不懂足球，所以就根据赔率压冷门……话说压冷门有的时候其实很划算的，比如昨晚我压瑞士，赔率40！赚翻了~强大吧~

前几天在找 Android 应用的时候，又见到了 QR code。说到 QR code，记得2006年，我还在维基活跃的时候，有一个人在维基的 QQ 群上发了这个的东西，然后大家就觉得很好玩。很早的事情了。寒假回福州的时候，在乌山公园，不少地方也有这个二维码，是移动设置的“物联网试验区”。

二维码着实是一个很有趣的东西。据我去过日本的同学讲，这个东西在日本已经十分普及了。在维基上查了一下，QR code 是开放的，有专利但没有被行使。而且识别算法似乎已经十分稳定成熟了。Android 手机里面安装一个 Barcode Scanner 就可以利用摄像头扫描二维码了，非常方便~

二维码可以干嘛呢？它可以储存网址、储存电话、储存名片信息，扫描一下就可以读取出来，将人从人工的复制方式中解脱出来~

于是我便也做了一个 CGI 的 QR code 生成器。
Read the rest of this entry »

因为以后可能要用到，于是今天用 Erlang 写了一个 0-1 背包算法，这算是我第一次用 Erlang 写算法，也是我第二次写 Erlang 程序……

以前都使用正常语言写，各种算法自然不会难写。所谓正常的语言，呃……也就是我们平时用的最多的语言了，像 C++、Python 什么的在我看来都还算正常的语言。那么 Erlang 到底哪里不正常了呢？

其实 Erlang 只要两个不正常的地方就足够囧死人了……那就是：

1. 没有循环，必须用递归代替
2. 数组不能随机访问，只能从头部读写

其实说数组不能随机访问吧，应该也是能的，只不过时间恐怕就不是 O(1) 了罢了。
Read the rest of this entry »

昨晚花了几个小时写了个计算人人网（其实我还是更喜欢叫他校内）当中，任意两个用户的好友之间交集的在线小工具，可以到我的实验室里看看这个小工具：人人网好友交集。

话说能写出这样的工具，主要有赖于我的空间提供商将系统换为 FreeBSD 后可以解析 Python 了，而且也没有限制 CGI，所以就成功了~
Read the rest of this entry »

昨天的那篇日志跨编译器的 C 语言 NaN 支持当中讲到了如何在 Linux 下用 wine 执行 VC6 编译器编译程序，不过总觉得还是有那么些麻烦，要把待编译的文件复制到 VC6 的安装目录，还要写那么长一串东西。要是能像调用 GCC 那么方便就好了~

于是就有了下面这个小脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#!/bin/bash
# - * - coding: UTF-8 - * -
 
VC6_DIR="这里写上VC6的安装地址"
 
BIN="$VC6_DIR/VC98/Bin"
export INCLUDE="$VC6_DIR/VC98/Include"
export LIB="$VC6_DIR/VC98/Lib" 
 
ARGS=
 
while getopts "o:c" optname
do
  case "$optname" in
  "o")
    ARGS="$ARGS /o$OPTARG"
    ;;
  "c")
    ARGS="$ARGS /c"
    ;;
  esac
done
 
wine "$BIN/CL.EXE" $ARGS ${@:$OPTIND}

然后把他放在 PATH 里面的某个目录下 (我放在了用户级的 /home/upsuper/bin 里，这个似乎要自己添加就是了)，然后给这个文件加上可执行属性，最后只要在需要的地方执行：

1

vc6 xxx.cpp

就解决了~
Read the rest of this entry »