2008年暑期
为培养软件学院高年级本科生和研究生的科研创新能力和编程能力，海量计算研究所特别选择几个项目供有意加入和已经加入该所的同学练习与培训。为达到锻炼与培训的目的，项目选择遵循以下原则：
1、难度适中：项目应选择难度适合初步学习过编程或有0-2年编程经验的同学完成，不应太难或太简单。
2、实用性强：项目应是非常有针对性的科学问题，是从科研工作中提取出的必须要解决的工程问题。项目不应抽象得太过于数学化，应保留问题本身的物理特性，让学生可以了解到问题和现实世界的联系。项目也不应涉及太多细节，否则学生难以从纷繁复杂的应用背景中找到解决问题的关键。
3、工作量适当：项目工作量应适中，以有0-2年编程经验的同学可在1-3个月内完成为标准，大致相当于500-1000行源代码的工作量。如果项目确实需要较大的工作量，则应设置可在1-3个月内完成的阶段性目标。周期太长的工作不利于学生建立信心，也不利于项目进度控制。
4、独立性强：项目应相对独立，有自己的数据输入和输出，一般不应直接和其它项目交换数据。独立的项目可避免刚入门的同学被相关信息干扰，保证同学可集中精力解决项目本身的问题。
项目由海量计算研究所教师提出并公布，向软件学院所有尚未加入实验室的本科学生和海量计算研究所的研究生开放。有意完成某个项目的同学可向海量计算研究所教师提出申请。有意申请的同学需填写《海量计算研究所学生培训项目申请书》并提交给海量计算研究所的教师。海量计算研究所将根据申请的实际情况分配项目。每个项目限一名同学参加。如有多名同学申请同一个项目，海量计算研究所将择优选定参加同学。
要正式参与海量所的项目，除填写《海量计算研究所学生培训项目申请书》外，还需要针对申请的项目写项目申请书。只有项目申请书完成情况好的同学才可正式参与项目。撰写项目申请书的一些说明可见这个幻灯片的介绍。
项目分配后，获得项目的同学将可进入海量计算研究所学生实验室工作。海量计算研究所将提供学生帐号和计算机。同时，海量计算研究所的教师将提供全方位的指导，包括但不限于：问题的理解和定义、算法和数据结构的设计、编程技巧、数据处理和分析技巧等。
海量所科研项目中随时都可能有新项目可供参与，有兴趣的同学可随时与海量所老师联系。
对被选中承担项目的同学，必须合理安排工作时间，在规定的期限内实现教师指定的功能。如确实遇到无法解决的技术问题，应尽早向教师提供数据证明。承担项目的同学应每周向教师汇报工作进展。如遇到的困难，可随时向教师请教。如果承担项目的同学在连续三个星期内没有取得实质性进展，或者合计五个星期没有取得实质性进展，将被取消继续执行项目的资格。项目结束后，承担项目的同学必须提交以下材料：
1、实现指定功能的源代码，包括核心代码和测试代码。
2、实现指定功能的可执行文件。可以是测试程序的可执行文件。
3、测试所使用的全部数据，包括全部的输入和输出数据。
4、实验报告，详细记录实验中的各种情况，以及对实验数据的分析。
另外，所提交的源代码必须满足以下要求：
1、无特殊说明的项目使用纯C++完成。特殊说明的项目可使用项目指定的开发工具。开发中可使用生成C/C++源代码的工具如re2c和DataDraw等，但必须保证在linux和windows两种平台上均可转换成合适的C/C++文件。
2、程序可以调用标准C库函数，但不能调用任何标准C++库函数，如string和各种数据结构、cin/cout、i/o/fstream等。海量计算研究所将提供一些数据结构和IO的库。
3、核心算法不得进行任何IO操作，也不得有任何人机界面。如有程序必须进行数据交换，则IO部分必须和核心算法严格分离。核心算法不得调用printf、getch、exit等函数。
4、测试程序必须全面细致，测试用例必须保证发现程序的大多数错误。测试所用数据必须达到足够数量。
5、代码书写必须规范、严谨。包括分割行、空行、缩进级、头文件和cpp设置、头文件基本结构等必须严格统一并满足基本要求。测试代码也必须满足书写要求。
海量计算研究所除提供机房和指导教师外，还将根据工作难度和完成情况向承担项目的同学提供500-2500元的补助。如承担项目的同学完成了额外的工作，补助额将更高。如承担项目的同学完成项目后愿意参加更深入的工作，海量计算研究所将提供按月发放的助学金。如果承担项目的同学在中途被取消项目执行资格，或自动申请退出项目，可根据已经完成的工作及其完成质量获得部分补助。
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、新闻网页配图和标题提取
很多网页，特别是新闻网页，经常配有图片、视频等多媒体内容。但是，网页配图并不一定与其内容相关。大多数配图是网页的结构元素而非语义元素，如列表前的圆点、转角、分割线等。还有另一些是广告或以广告目的放置的。真正与网页内容相关的图片等多媒体内容只占很小一部分。如何通过分析网页把这些与内容相关的配图及其标题提取出来是一个大问题。本项目拟解决这个问题。项目分以下几个阶段实现最终目标：
（1）提取网页的图片信息：输入一个HTML文件及其URL，输出所有的<img>标记和其关联信息，如位置、大小、图像URL、链接、替代文字、附加属性等。
（2）通过分析来自同一网站的多个页面的所有<img>标记，识别出重复的结构元素，去除重复的结构<img>标记。该算法要求实现训练和分类两个程序。训练程序通过分析多个页面<img>标记的统计特性获得一个模型，分类程序用这个模型将结构<img>标记去除。
（3）对阶段（2）剩下的标记，通过SVM算法进行分类。要求手工标注不少于3000个<img>标记用于训练SVM模型。要求自己编写辅助手工标记的程序。
（4）对分类为新闻配图的<img>标记，在原HTML文件中检测其标题文字。
4、论坛博客下载工具
论坛和博客在中文WEB中是非常重要的一块。由于论坛和博客的帖子往往包含来自多个用户的内容，单纯以页面为单位的检索方式难以很好地检索这些信息。为此，就必须对论坛和博客页面进行更细致的分析，提取出更多的内容。部分论坛和博客支持RSS，可以极大地方便下载分析过程。但另一些论坛和博客不支持这个功能，就必须用较智能的工具进行分析。本项目拟解决这个问题。项目分以下几个阶段实现最终目标：
（1）XML/HTML简化分析器：利用re2c、flex、bison、AnaGram等工具结合C++开发一个简化的XML/HTML读取/分析器，目标是使用方便、分析效率高、便于维护。该分析器的主要用处其一是作为RSS文件的解析器，其二是作为解析HTML的前期语法解析器。
（2）开发RSS下载、分析和整理平台：连续下载几个论坛的RSS文件，并分析、整理出其中的记录，保存帖子列表、发帖用户、发帖时间、帖子题目、帖子间关联等信息供后续分析和处理使用。要求间隔一定时间产生一个新帖子列表。
（3）论坛/博客页面下载和分析：根据RSS下载、分析和整理平台输出的新帖子列表下载论坛和博客的帖子，提取帖子文字内容和相关信息并存储为易于处理的格式。
（4）开发通过网页获得新帖子列表的系统，实现类似RSS的功能，用以下载不支持RSS的论坛和博客。
5、图/树数据可视化工具
Treebolic是一个非常不错的图/树数据可视化工具。但是，这个工具所使用的算法有专利问题。另外，该工具的实现稍显复杂，代码不易维护。本项目拟开发一个图/树数据的可视化工具，实现Treebolic类似的功能，但不使用专利技术。项目分以下几个阶段实现最终目标：
（1）实现图/树数据在二维平面上的排布算法。该阶段不涉及到可视化，仅仅根据数据计算出各节点在二维平面的坐标。
（2）显示排布好的图/树数据，实现简单的拖动、点击等操作。
（3）实现Treebolic中利用双曲几何的类似鱼眼效果的效果。这里的实现要避免使用双曲几何，因为该技术是专利技术，另外，为充分利用显示面积，应当把数据投影到二维矩形中，而不是二维圆盘。
（4）改进界面的易用性，最终实现可稳定运行的可视化工具。
该项目由于特殊需要，将全部使用Java开发，并要求最终实现可在浏览器内运行的JavaApplet。特别需要注意的是，该项目对数学功底要求较高。另外，该项目完全实现的难度较大，所以在3个月内不要求实现所有功能。
6、基于Trie结构的词典分词算法
分词是汉语处理的第一步。分词的性能和效率对后续的汉语处理过程有巨大的影响。实现分词功能最基本的算法是基于词典的分词算法。而Trie结构非常适合用于分词中保存词典信息。所以，用Trie结构实现词典分词就是非常好的选择（关于Trie结构和分词的更多信息可参见课程《多媒体搜索引擎》的相关内容）。本项目拟使用Trie结构实现词典分词算法。本项目分以下几个阶段实现最终目标：
（1）实现Trie结构及基于Trie结构的正向最大匹配分词。
（2）实现反向最大匹配和双向最大匹配算法。
（3）实现至少一种解决歧义的高级算法。算法将从下载的论文中来。
（4）实现至少一种未登录名识别算法。算法将从下载的论文中来。
7、XML数据流处理工具集（c++版本与java版本）
XML作为一种灵活的数据表示、数据交换标准在很多系统中都有应用。现有XML处理工具大都针对静态XML文件，不能适应灵活的XML数据交换在功能上和性能上的需要。本项目旨在开发一套灵活的XML数据交换工具，要求采用流式处理（参见XML的SAX解析方法：http://www.saxproject.org/），以获得需要的性能。实现针对XPath和关键词的XML文档的过滤（单查询）、分发（多查询）功能。本项目可分成四个阶段：
(1) 基于XPath的的XML文档过滤
(2) XPath+关键词的XML文档过滤
(3) XPath+关键词的XML文档分发
(4) XML文档过滤队列实现
8、Hadoop上的数据索引实现
Hadoop(http://hadoop.apache.org/core/)是一个基于java的分布式数据处理平台。在hadoop平台上，HBase（http://hadoop.apache.org/hbase/）是一个数据管理系统。目前，HBase不支持有效的索引功能。本项目旨在开发HBase中的索引。本项目可分成以下三个部分：
(1) HBase中的关键词索引实现
(2) HBase中的正则表达式匹配实现
(3) HBase中的数值索引实现
9、图像分割
图像分割是图像、视频处理的重要技术。目前的开源工具中，分割做得较好的是使用Mean-Shift算法的分割方法（源码下载）。不过，Mean-Shift计算量大，对纹理区域的处理也不太好。这篇论文提出了一个新的纹理和颜色特征，可以较好地描述纹理。这里可以下载一个用该特征进行纹理分割的演示程序，但没有提供源码。本项目实现这个图像分割算法。
10、Condor-SVM
SVM是相当好的分类算法。但是，要获得好的效果，SVM训练算法必须尝试大量的参数组合。由于在不同参数组合下的SVM训练和测试是完全独立的，利用集群对SVM训练进行并行处理将极大地提高训练速度。本项目结合SVM-Light或LibSVM和Condor来实现在大规模集群上SVM的并行训练。
X、文本编辑器
Notepad++曾经是一个不错的文本编辑器。但是最近却出现了这个情况。这是难以接受的。我们不愿意泛政治化，但这显然不以我们的意志为转移。何况，一个文本编辑器有什么了不起。本项目旨在开发一个文本编辑器，一个可以全面超越Notepad++的文本编辑器。当然，仅仅以一时之怒行事是不可取的。本项目的设立是因为Notepad++本身并不完美，存在诸多缺陷。我们在设计过程中将解决这些问题。并且，文本编辑器既可以从非常简单的程序和算法开始，又可以有足够的发展空间，是编程练习非常好的课题。
当然，要实现一个实用的，并且是非常实用的文本编辑器还是非常困难的。为此，本项目将要分解成2-3个子项目，由2-3名同学合作完成。具体如何划分暂时无法确定。请有兴趣的同学在申请书中大致阐述你的意见。