接着上次4道比较简单的题的解题报告写。这次是Detect the Virus IIAn Unusual Problem的解题报告,主要涉及如何在C, C++, Java, Perl, Python中使用正则表达式与及无损压缩算法

ZOJ3440. Detect the Virus II

[regex, topSort]

题目简单来讲就是通过上下文无关语法(context-free grammar, CFG)描述了virus。问一个字符串是否存在virus形式的子串。题目保证描述不会有环/递归。

这题用正则表达式(Regular expressions, regex)来做是再自然不过了,比如sample就等价于下面这段perl代码:

# subparta:=fg|g
$subparta = qr(fg|g);
# parta:=a|b|c
$parta = qr{a|b|c};
# partb:=d|e[subparta]h
$partb = qr{d|e($subparta)h};
# virus:=[parta][partb][partb]
$virus = qr{($parta)($partb)($partb)};

printf 'abcdefghijklm' =~ $virus ? "YES\n" : "NO\n";
printf 'nopqrstuvwxyz' =~ $virus ? "YES\n" : "NO\n";

当然,因为代码是顺序执行的,所以我们调整了几个record的顺序。顺插一句,如果是函数式编程语言的话,那顺序就完全无关紧要了。于是问题就是给定的字符串能否匹配题目所描述的正则表达式,不过因为输入的顺序不确定,所以要麻烦一点,不过即然没有环,一个拓扑排序就搞定了(ZOJ3440watashi2.pl)。

quark用python写了标程(ZOJ3440quark.py),他的写法是记忆话搜索,这样比我的拓扑排序简洁美观得多。于是我也照着改了一个记忆化搜索(ZOJ3440watashi.pl),代码是最短的。Python的re模块提供的正则有一个缺陷,就是他的分组不能超过100个,否则会抛出

AssertionError: sorry, but this version only supports 100 named groups

最好的解决办法使用非捕获型分组(/(?:…)/)代替捕获型分组(/(…)/),这样效率也更高。不过quark的程序用了一个更evil的做法:去掉不必要的分组来减小分数数,这样也能通过所有数据,而且更快。

Java也提供了正则表达式的支持,事实上java里的String.split和String.replceAll就使用了正则,所以AC此题也同样不成问题(ZOJ3440watashi5.java)。不过java有着和python类似的不能有过多括号的问题,而且即使改成非捕获型括号也无济于事。提交后会RuntimeError,打出来的调用堆栈是

Exception in thread "main" java.lang.StackOverflowError
	at java.util.regex.Pattern$Node.study(Pattern.java:3026)
	at java.util.regex.Pattern$CharProperty.study(Pattern.java:3372)
	at java.util.regex.Pattern$Node.study(Pattern.java:3027)
	...
	at java.util.regex.Pattern$Node.study(Pattern.java:3027)
	at java.util.regex.Pattern$CharProperty.study(Pattern.java:3372)
	at java.util.regex.Pattern$Node.study(Pattern.java:3027)
	at java.util.regex.Pattern$Node.study(Pattern.java:3027)

可见是递归深度过深,于是可以用quark那种只在必要的时候加分组的办法避免这个问题。说实话,这种数据太xe了,不知道可能有这种问题的话更本想不到死在哪里,还好perl的正则很强大。

C/C++也绝非与此题无缘,除了可以自己写算法搜索匹配字符串外,其实C/C++也有很多可选的正则工具。首先想到的是boost,boost这么强大的库怎么少得了正则呢,我也写了一个boost::regex版本的程序(ZOJ3440watashi4.cpp)。不过说实话,boost的regex不是太好用,regex_replace也不支持e开关,或调用一个函数,这个程序在编码效率、编译效率和执行效率都排在了最后。而且boost大多不能在OJ得到支持,ZOJ也只短期提供过boost头文件,而且boost::regex编译时需要-lboost_regex。另一个选择是std::regex,是的,regex是传说中的c++0x的一部分,可惜的是g++在编译的时候会要求加上-std=c++0x的参数,更悲剧的是c++0x离我们还很远,事实上stdlibc++还没有实现完整其std::regex,所以会得到一个链接错误:

/tmp/ccqI94VD.o: In function `std::basic_regex<char, std::regex_traits<char> >::
basic_regex(char const*, unsigned int)':
ZOJ3440watashi5_.cpp:(.text._ZNSt11basic_regexIcSt12regex_traitsIcEEC1EPKcj[std:
:basic_regex<char, std::regex_traits<char> >::basic_regex(char const*, unsigned
int)]+0x61): undefined reference to `std::basic_regex<char, std::regex_traits<ch
ar> >::_M_compile()'
collect2: ld returned 1 exit status

不过好消息是,我们还有C POSIX library提供的正则表示式,虽然不及C standard library般标准,但regex.h是POSIX的26个必须的头文件之一,这意味着在POSIX的机器上,这就是标配,你可以通过include “regex.h”在Linux和跑在Linux上的OJ来使用它。虽然它看起来不那么强大:

#include <sys/types.h>
#include <regex.h>

int regcomp(regex_t *preg, const char *regex, int cflags);

int regexec(const regex_t *preg, const char *string, size_t nmatch,
            regmatch_t pmatch[], int eflags);

size_t regerror(int errcode, const regex_t *preg, char *errbuf,
                size_t errbuf_size);

void regfree(regex_t *preg);

但是应付此题是绰绰有余了。于是我写了一个能在ZOJ AC的版本(ZOJ3440watashi3.cpp)。

ZOJ3444. An Unusual Problem

[compress, Huffman encoding, zip, gzip, bzip2]

对于输入的每一个ZOJ题号code,输出对应的题目标题title。如果题目不存在,则输出”No such problem”。

首先的对题号的标题的对应表可以比较轻松的人肉得到,这个就不用上机器人了,反而更没效率。然后注意题目的输入是一个string,所以对于不是1001到3436的题号要输出”No such problem”,而且你会发现题号2867和3000也是空缺的 :D 不过这些都不是主要问题,真正的问题是,人肉得到的列表(zojlist)有38k,超过了提交限制32k,这个表是交不上去的。似乎有人尝试删掉其中一些题目的题号,这是不靠谱的,因为测试数据包含了所有题号 :D 正确的方法是对这些题号做无损压缩。有关压缩算法,附上《数据压缩算法简介》,文章时间虽然很老了,内容还是满新的。

我想,没有人不知道哈夫曼编码(Huffman coding)吧。好的,活学活用,这里只要把zojlist通过huffman编码一下,大小就只有23.1kb。不过可惜的是我们无法在代码中直接引用二进制数据,即使像Perl那样可以用__DATA__读取二进制数据,提交到ZOJ也会失败。解决的办法就是再用可见字符来表示这段二进制数据,最简单的办法是用4个可见字符来表示3个字节,这就是著名的base64。经过base64编码后,一下子增大了1/3,变成了30.7k。不过剩下来1.3k的空间已经足够用来实现base64和huffman的解码和main函数了。不过也是刚好低空飘过,hhanger的代码有31.9kb(ZOJ3444hhanger.cpp)。

提到无损压缩,我想,更没有人不知道.gz, .zip, .7z这些压缩包。插入一句,打包(Archive)和压缩(Compress)还是有区别的,还有,.rar去死。那么直接用这些基于字典编码的压缩算法,我们可以得到更高的压缩率,而很多语言中都对此提供有支持。比如hsys用了gzip的python代码只有23.5kb(ZOJ3444hsys.py),核心部分只有两行

import base64, zlib, sys
x = zlib.decompress(base64.b64decode(x)).split('\n')

而我的perl版代码只有21.0kb(ZOJ3444watashi.pl),用了bzip2,也很简单

use Compress::Bzip2;
use MIME::Base64;

chomp($_ = <DATA>);
$_ = decode_base64($_);
$_ = decompress($_);
@_ = split(/\n/, $_);

不熟悉脚本语言的朋友也不用担心,因为java对此同样有着支持,事实上.jar格式的压缩包就是基于.zip的。我们可以通过java.util.zip.*实现无损的压缩和解压缩。下面的代码可以从zojlist中生成zip压缩并base64编码后的字符串。

import java.io.*;
import java.util.zip.Deflater;
import sun.misc.BASE64Encoder;

public class Gao {

	public static void main(String[] args) throws IOException {
		InputStream in = new FileInputStream("zojlist.txt");
		byte[] data = new byte[65536];
		int size = in.read(data);
		in.close();

		Deflater zip = new Deflater(Deflater.BEST_COMPRESSION);
		zip.setInput(data, 0, size);
		zip.finish();
		size = zip.deflate(data);

		OutputStream out = new FileOutputStream("zojlist.tmp");
		BASE64Encoder base64 = new BASE64Encoder();
		base64.encode(new ByteArrayInputStream(data, 0, size), out);
		out.close();
	}
}

利用生成的字符串就能够写出在ZOJ上AC的代码了,需要注意的是,在ZOJ上用sun.misc.BASE64Decoder会RE,所以我自己实现了一个很暴力的Base64.decode,我的代码有25.1kb(ZOJ3444watashi3.java)。

最后提一下C语言使用zlib,事实上前面的python和python用的就是zlib,perl也有zlib的接口,不过可能有文件之类的非法调用,在ZOJ上会Non-zero Exit Code。虽然zlib.h基本在所有Linux机器上都有,可是链接时需要参数-lz,我想虽然几乎所有OJ都有-lm,但几乎没有OJ提供有-lz吧,所以在OJ上是没法用了。不过我还是写了压缩代码

#include <zlib.h>
#include <unistd.h>

int main() {
	Bytef dest[65536], source[65536];
	uLongf destLen, sourceLen;

	sourceLen = read(0, source, sizeof(source));
	destLen = sizeof(dest);
	compress2(dest, &destLen, source, sourceLen, Z_BEST_COMPRESSION);
	write(1, dest, destLen);

	return 0;
}

和25.7kb的解压缩代码(ZOJ3444watashi2.c)。偷懒没有写C语言版的base64,直接用了命令行工具。

最后还剩我出的三道题,下次补完……

15 Responses to “[题解](续)Let’s Celebrate the 100th Contest on ZOJ!”
  1. VegetableB says:

    为啥这么讨厌.rar的?-.-

    • watashi says:

      .gz和.zip都支持随机访问,这样要读写一个.zip非常轻松,gvim可以直接打开他们,而winMount也可以把他们mount成一个分区。打开zip格式的漫画可以很顺畅的阅览。rar行么,你打开.rar的漫画试试看,你用winMount挂载一个.rar试试看卡不卡死。
      .rar优于.zip的不过是一点压缩率,但是这个优势就很可怜了。我们需要这点压缩率么,用十倍的时间(cpu)换不到十分之一的大小(bandwidth/disk),值得么。如果真的要压缩率,能和.7z比么,发现对于某些压缩潜力很大的东西,.7z还是很给力的,不过压缩潜力不大的用.7z就是蛋疼,虽然.7z比.rar还要慢。
      最后一点是最根本的原因,.rar是算法并非原创,却申请了专利,整了个收费的玩意。引以为耻。

  2. quark says:

    记忆话搜索 -.-

  3. Navi says:

    果断momo那个搞D搞了26次的人… 最后都查到了哪句话抛了哪个异常了却不知道怎么搞定

  4. Navi says:

    sfを続けよう

  5.  
Leave a Reply