2008年
1、文字编码检测和语种识别、分割
大规模检索中遇到的一个问题是输入文件可能是不同的语种，如中文、英文、日文等等。有时候单个文件中还有多个语种混合，如中英对照翻译的文件同时有中文和英文。另外，输入文件的代码页可能是多种多样的，如GBK、BIG5、UTF-8、ISO-8859-x、Windows-xxx等。有时候这些代码页可以从文件的某些信息获得，如xml和html等有说明代码页的域。但有些时候这些信息无法获得，或者编码到文件中的信息是错误的。这种情况下就会出现乱码。于是，如何检测出现了乱码（从而可以矫正对输入文件的代码页的认定）、如何分割文件的各语种部分并识别各部分的语种就是一个需要解决的问题。本项目拟解决这个问题。项目分四个阶段实现最终目标：
（1）单语种文件的语种识别：输入一个UTF-16LE编码的纯文本文件，输出其语种。要求输出的类别至少包括：简体中文、繁体中文、英文、日文、拉丁系非英文语种、乱码。要求在输入文件超过100字时识别准确率不低于95%。测试数据集不少于1000文件/类别。
（2）多语种文件检测：输入一个UTF-16LE编码的纯文本文件，输出其是否包含多个语种的文字。要求在输入文件超过200字时识别准确率不低于95%。测试数据集不少于1000文件/类别。
（3）多语种文件分割：对检测到是多语种的文本文件，把各个语种部分分割开。要求在某个语种的连续文字串超过100字时分割准确率不低于95%。测试数据集不少于1000个多语种混合文件。
（4）乱码矫正：对检测到是乱码的文件，通过更深入的分析其原始数据（不是输入的UTF-16LE纯文本数据），发现其真实的编码。要求在输入原始数据超过200字节大小时矫正准确率不低于90%。测试数据集不少于1000个文件。
本项目的工作除编写相应程序外，收集各种测试数据也是工作之一。收集数据的工作可以通过编写程序自动从网上抓取。教师将对实现这些功能给与必要的指导和帮助，并提供一些实用工具。
2、基于海量数据统计的新词识别
分词是涉及汉语的检索和分析系统必须要实现的功能。然而，汉语词汇经常变化，经常有新词被创造出来。如果使用固定的词典或数据库，则难以快速适应新创造的词汇，难以检测新流行词。对检索系统来说，词分得较细问题不大，仍然可以通过各种索引结构把被分解成多个部分的词拼合，最终效果仅仅是计算量有所增加。但对于语义分析和提取的应用，大词被分解成小词将造成语义的变化，从而极大地影响了分析结果。例如，“芙蓉姐姐”目前是一个有特殊含义的专有词，但现有分词软件均不能把这个词分为一个独立的词。而一旦这个词被分解，其特殊含义将完全消失。所以，准确地检测和识别新词就是非常重要的问题。本项目拟通过对大量数据进行统计分析的方法，结合半监督机器学习算法进行新词识别。项目分以下几个阶段实现最终目标：
（1）海量文字数据的n-gram统计及n-gram建模：实现对文本文件进行n-gram统计的程序，并对教师给定的数据进行统计，获得海量数据的n-gram统计模型。数据格式和数据由教师指定。数据总量不小于1GB纯文字材料。
（2）结合n-gram统计模型和相邻词关联模型实现候选新词打分：根据教师给定的算法，从n-gram统计模型和相邻词关联模型计算出各种字的组合的新词可能性打分。相邻词关联模型由教师给定。
（3）评价对候选新词的打分，实验教师指定的几种不同的打分策略，找到最佳打分方案，实现新词检测。
（4）结合新词检测和已有分词程序实现具有新词检测功能的汉语分词查询。
本项目难度较大，所以暂时不对新词检测的准确率进行要求。只要有一定效果即算完成。如完成得好，本项目可以考虑写一篇论文。
3、论坛博客下载工具
论坛和博客在中文WEB中是非常重要的一块。由于论坛和博客的帖子往往包含来自多个用户的内容，单纯以页面为单位的检索方式难以很好地检索这些信息。为此，就必须对论坛和博客页面进行更细致的分析，提取出更多的内容。部分论坛和博客支持RSS，可以极大地方便下载分析过程。但另一些论坛和博客不支持这个功能，就必须用较智能的工具进行分析。本项目拟解决这个问题。项目分以下几个阶段实现最终目标：
（1）XML/HTML简化分析器：利用re2c、flex、bison、AnaGram等工具结合C++开发一个简化的XML/HTML读取/分析器，目标是使用方便、分析效率高、便于维护。该分析器的主要用处其一是作为RSS文件的解析器，其二是作为解析HTML的前期语法解析器。
（2）开发RSS下载、分析和整理平台：连续下载几个论坛的RSS文件，并分析、整理出其中的记录，保存帖子列表、发帖用户、发帖时间、帖子题目、帖子间关联等信息供后续分析和处理使用。要求间隔一定时间产生一个新帖子列表。
（3）论坛/博客页面下载和分析：根据RSS下载、分析和整理平台输出的新帖子列表下载论坛和博客的帖子，提取帖子文字内容和相关信息并存储为易于处理的格式。
（4）开发通过网页获得新帖子列表的系统，实现类似RSS的功能，用以下载不支持RSS的论坛和博客。
4、图/树数据可视化工具
Treebolic是一个非常不错的图/树数据可视化工具。但是，这个工具所使用的算法有专利问题。另外，该工具的实现稍显复杂，代码不易维护。本项目拟开发一个图/树数据的可视化工具，实现Treebolic类似的功能，但不使用专利技术。项目分以下几个阶段实现最终目标：
（1）实现图/树数据在二维平面上的排布算法。该阶段不涉及到可视化，仅仅根据数据计算出各节点在二维平面的坐标。
（2）显示排布好的图/树数据，实现简单的拖动、点击等操作。
（3）实现Treebolic中利用双曲几何的类似鱼眼效果的效果。这里的实现要避免使用双曲几何，因为该技术是专利技术，另外，为充分利用显示面积，应当把数据投影到二维矩形中，而不是二维圆盘。
（4）改进界面的易用性，最终实现可稳定运行的可视化工具。
该项目由于特殊需要，将全部使用Java开发，并要求最终实现可在浏览器内运行的JavaApplet。特别需要注意的是，该项目对数学功底要求较高。另外，该项目完全实现的难度较大，所以在3个月内不要求实现所有功能。
5、基于Trie结构的词典分词算法
分词是汉语处理的第一步。分词的性能和效率对后续的汉语处理过程有巨大的影响。实现分词功能最基本的算法是基于词典的分词算法。而Trie结构非常适合用于分词中保存词典信息。所以，用Trie结构实现词典分词就是非常好的选择（关于Trie结构和分词的更多信息可参见课程《多媒体搜索引擎》的相关内容）。本项目拟使用Trie结构实现词典分词算法。本项目分以下几个阶段实现最终目标：
（1）实现Trie结构及基于Trie结构的正向最大匹配分词。
（2）实现反向最大匹配和双向最大匹配算法。
（3）实现至少一种解决歧义的高级算法。算法将从下载的论文中来。
（4）实现至少一种未登录名识别算法。算法将从下载的论文中来。
6、图像分割
图像分割是图像、视频处理的重要技术。目前的开源工具中，分割做得较好的是使用Mean-Shift算法的分割方法（源码下载）。不过，Mean-Shift计算量大，对纹理区域的处理也不太好。这篇论文提出了一个新的纹理和颜色特征，可以较好地描述纹理。这里可以下载一个用该特征进行纹理分割的演示程序，但没有提供源码。本项目实现这个图像分割算法。
7、Condor-SVM
SVM是相当好的分类算法。但是，要获得好的效果，SVM训练算法必须尝试大量的参数组合。由于在不同参数组合下的SVM训练和测试是完全独立的，利用集群对SVM训练进行并行处理将极大地提高训练速度。本项目结合SVM-Light或LibSVM和Condor来实现在大规模集群上SVM的并行训练。
X、文本编辑器
Notepad++曾经是一个不错的文本编辑器。但是最近却出现了这个情况。这是难以接受的。我们不愿意泛政治化，但这显然不以我们的意志为转移。何况，一个文本编辑器有什么了不起。本项目旨在开发一个文本编辑器，一个可以全面超越Notepad++的文本编辑器。当然，仅仅以一时之怒行事是不可取的。本项目的设立是因为Notepad++本身并不完美，存在诸多缺陷。我们在设计过程中将解决这些问题。并且，文本编辑器既可以从非常简单的程序和算法开始，又可以有足够的发展空间，是编程练习非常好的课题。
当然，要实现一个实用的，并且是非常实用的文本编辑器还是非常困难的。为此，本项目将要分解成2-3个子项目，由2-3名同学合作完成。具体如何划分暂时无法确定。请有兴趣的同学在申请书中大致阐述你的意见。