希望能自动从所有回贴中找到三种最具代表性的帖子课件.ppt

1、2008/12/151Reports and related topicsnOther bbs ReportsnThe preprocessornHomework Dec-112Software development nRequest AnalysisnFormalizenDesignnCodingnTest&result analyze 3Request:n希望能自动从所有回贴中找到三种最具代表性的帖子：A、最能代表当前所有回贴内容的帖子。B、内容与其他所有回贴最不同的帖子。C、与某预设（自设）的敏感话题最相关的回帖。4Problem Analysis 最能代表当前所有回贴内容的帖子n代表

2、 到底是什么意思？n所有回帖？5最具代表性的帖子 高戈，秦毅成n在帖子中随机抽取2个帖子进行DP最长公共子串匹配。n进行8n（n为帖子总数）次，这样在20%-30%以上帖子中都出现的关键词（关键词长度要大于等于4，小于等于10）我们都基本能记录下来。然后用其中出现次数较多的20个关键词（必须满足出现次数大于等于3）对每个帖子进行匹配，并根据匹配情况算出它的权值，其中匹配权值最高的那个帖子即为最具代表性的帖子。n优点：不必分词，领域无关，自适应。算法复杂度较低。n缺点：？6测试数据1：关于研究生应聘卖猪肉岗位的新闻的回帖n运行结果:1 最具代表性的帖子 这是中国资源的浪费，读完研究生要耗去多少人

3、力和财力，国家和家庭要付出多少，卖猪肉小学毕业就绰绰有余了，难道非要研究生吗？一个人从小学毕业开始卖猪 肉，一年赚一万，又比在校学生少花费一万来计算，从初中到研究生毕业就是28万余元啊！说不定你研究生毕业人家就成养猪专业户或企业家了，你们研究生就是 给人家打工的，年薪10万算什么？如果一个国家投资那么多钱就是为了培养卖猪肉的，真是太可悲了呀！相似度为1500左右，多次测试结果稳定2 最不同的帖子 可能性较多，有三至四种 相似度为0到2之间，多次测试结果不稳定7测试数据2：对台检方周末加班写起诉书 陈水扁可能被求处重刑的评论。1 最具代表性的帖子 贪污这么多钱在国际上也是前无先例啊！不判死刑能给

4、世人交代吗？应该让陈水扁象萨达姆那样被台湾人民绞死！现在还在挺扁的绿营人士及民进党都是神经病患者，根本就没有是非观念，真是台湾的不幸啊！其他出现结果 很不理解台湾的极少数支持陈水扁的人，陈水扁贪污这么多，在祖国大陆这样的贪污犯是要处死刑的；难道支持陈水扁的少数人是接受了陈水扁的好处？是共犯？相似度为1200到1300，多次测试结果较为稳定2 最不同的帖子 可能出现的结果：n特赦，为什么啊？难道法律面前，人人不平等啊。n不是可能被处以重刑，而是必须判重刑！天理难容啊！n报应啊，哈哈哈哈哈哈哈哈哈哈哈哈哈n曾经人上人，如今阶下囚。谈人生为何如此丑恶？n等等n相似度为1或0，多次测试结果非常不稳定8

5、展望：n现在我们生成词典采用的是随机算法，对于较大规模的数据依旧是束手无策。因此，我们考虑将来可以进一步采用遗传算法进行优化，筛选出最具代表性的关键字词典。利用遗传算法可以更加有效地解决空间时间的紧张问题。n另外，对于匹配算法上来讲，我们采用的是最基础的动态规划，应该可以改进成串的最大匹配算法，这样空间和时间的复杂度都可以远远小于O（mn），大幅度地提高我们的效率。9FormalizenMax common substringnKeywords set+frequencynVectorn+class10建模：（张磊、刘邦）n对汉字的编码和其他字符的编码统一化处理。n对所有帖子组成的集合Z中所用

6、的字Ci统计重复次数Ti。对第i个帖子，统计其中字的Ti之和，除以第i个帖子中字的个数N，相当于求一个平均频数，以此作为第i个帖子的代表全体意思程度的指数。n建立停用字库，对原帖用字进行过滤。11陈健 张海峰 叶树雄：n找关键词：在规定贴子数目以上的帖子出现过的连续字符（已编码）n把每个贴子向量化n内积运算12华连盛、蔡斯任：n计算了每条回帖被回复的次数，特别加入了对于“顶”、“赞”、“支持”之类的回复的查找，普通回复每条算10分，包含上述字眼的每条算20分；n考虑最有代表性的回帖必须和主题贴有一定的关联，又不能完全没有自己的观点，所以设计了一个相似度的评分，如果一条帖与主题贴的相似度为30%

7、则定义为30分，相似度为0或100%的定义为0分，其余部分呈线性。n最后将这两方面的评分相加得到最后的得分，找出得分最多的回帖即为最有代表性的。n进行过前面的处理后，考虑可以去掉一些评分较低的帖子，对剩余的帖子统计每个汉字出现的频率，找出出现频率最高的几个汉字作为关键字（去除停用字词），再对这些帖子进行一遍关键字的检索，在进行一轮评分，这样结果可能会更加准确，13codingnWorkgroupnProgramming environmentnIDEnWriting in good style 14/by 周先达1516施维加、袁洋、仝艺n对每一个帖子进行加权处理，称为代表性权值。nA的代表性

8、权值为A与其余所有帖子的相似度之和：nW_represent(A)=similar(A,X1)+similar(A,X2)+.similar(A,Xn)nsimilar(A,B)=limit(g(lcs(A,B),kmp(A,B)nlcs函数返回A和B的最长公共子序列的长度；kmp函数返回A和B的最长公共子串；ng函数为一个2元函数，具体的表示形式为：g=ax2+by2+cxy+dx+ey+f (x,y可以有更高次项)其中x,y分别为lcs和kmp返回参数，而a,b,c,d,e,f分别为6个待定系数 17工程在结构上做了改进：n统一了搜索机制，重写了搜索引擎，给出了一个更一般的搜索方案(loc

9、ateRep)，实现将搜索输出和删除统一的回馈机制（使用一个数组作为标记）。n改进了命令语法，增加了逻辑运算功能，使之变得更加合理、有效。n将大部分数组实现了动态化，使得能够更好的支持较早的编译器，并且使程序变得更稳定。n本程序将工程各部分分离，为每一位参与者提供了数据标准，统一了函数接口。n在代码实现上，使用了函数指针作为参数加入到搜索过程中，简化了重复的代码，并使得维护性得到提高。使用了函数指针数组来执行驱动，这样使得命令的可扩展性得到保障，使得今后添加命令将变得比较方便。18The preprocessornoverviewnmacrosnfile inclusionncondition

10、al compilation19Preprocessor Overviewnperforms:macro substitutionconditional compilationinclusion of named filesnthe preprocessor may actually be a separate program,even though it is invoked by the C compilernpreprocessor directives begin with a#signnpreprocessor directives are not part of the C lan

11、guage propernC compiler invokes the preprocessor first before doing its compilation processing(hence the term pre-processor)20Macrosnmakes programs more readable,modifiable and portable(but dont over do it!)n#define -define a macrosimple macromacro with parametersn#undef -remove a macro definitionnp

12、arameter modifiers:#-string substitution21Simple Macro Definitionn#define identifier token-sequencenExamples:#define TRUE 1#define TWO_PI 2.0*3.141592654nthe identifier is replaced by the token-sequencenidentifiers are capitalized by convention22Macro with Parameters Definitionn#define identifier(id

13、entifier-list)token-seqnExample:#define MAX(a,b)(a)(b)?(a):(b)nthe identifier is replaced by the token-sequenceneach parameter specified in the identifier-list is substituted in the token-seqnbe careful with spaces and grouping232425Macro Usage#define TRUE 1#define MAX(a,b)(a)(b)?(a):(b)voidsomefunc

14、tion(int x,int y)int maxvalue;while(TRUE)/some C code maxvalue=MAX(x,y);/some more C code macro isknown fromdefinitionto end of file26Removing a Macro Definitionn#undef identifiernExamples:#undef DEBUG#undef MAXnuseful for:conditional compilationclearing out a macro with the same name as a function2

15、7Parameter Modifiersn#-string substitution#define str(x)#xstr(testing)“testing”nsomewhat useful in printf()statements2829The#operatornJoin to token togetherni#n in3031File Inclusionninclude files(.h)useful in organizing:preprocessor definitionsstructure definitionsprototype declarationsglobal variab

16、le declarationsnplaced at top of C source file(.c),will be included as part of that file,can be nested32File Inclusion Methodsn#include searches for file only in the standard system directoriesn#include“filename.h”searches for file in the current directory and in the standard system directories33Con

17、ditional Compilationncan conditionally include or exclude chunks of code from a source filen“if else end”sequencenuseful for:maintaining multiple versionsdebugging34#ifndef _ADD_H#define _ADD_H#endif35#if#eif,#else#endifn#if defined(POJ)#define printInt(var)printf(#var =%dn,var)#define printx(n)prin

18、tInt(i#n)#else .#endif 36Conditional Compilation Example#ifndef DEBUG somefunction();#else printf(“calling somefunction()”);#endifthe real codedebug code37Indefinite number of arguments nfunctions may take a variable number of arguments and are declared with an ellipsis in place of the last paramete

19、r.such as:int printf(const char*_Format,.);n is a header in the C standard library of the C programming language that allows functions to accept an indefinite number of arguments.38394041Variable Number of arguments to MacrosnThree dots at the end of argument listnSpecial identifier:_VA_ARGS_#define

20、 debugPrintf()printf(“DEBUG”_VA_ARGS_)debugPrintf(“hello world”);debugPrintf(“%d%f”,i,f);42Binary files operation(Review)ntext filea named collection of characters saved in secondary storageninput(output)streamcontinuous stream of character codes representing textual input(or output)datan(FILE*)stdi

21、nsystem file pointer for keyboards input streamn(FILE*)stdout,stderrsystem file pointers for screens output stream43File Open Mode44Binary FilesnFormatted Text files contain variable length recordsmust be accessed sequentially,processing all records from the start of file to access a particular reco

22、rdnBinary Files(random access file)a file containing binary numbers that are the computers internal representation of each file componentcontain fixed length recordscan be accessed directly,directly accessing the record that is requirednsizeofoperator that finds the number of bytes used for storage

23、of a data type45The Data HierarchynBit-smallest data itemValue of 0 or 1nByte 8 bits Used to store a characterDecimal digits,letters,and special symbolsnField-group of characters conveying meaning Example:your namenRecord group of related fieldsRepresented a struct or a classExample:In a payroll sys

24、tem,a record for a particular employee that contained his/her identification number,name,address,etc.nFile group of related recordsExample:payroll filenDatabase group of related files4647In a Random Access File nDataData unformatted(stored as raw bytes)in random access filesAll data of the same type

25、(ints,for example)use the same memoryAll records of the same type have a fixed lengthData not human readable48Random AccessnAccess individual records without searching through other recordsnInstant access to records in a filenData can be inserted without destroying other datanData previously stored

26、can be updated or deleted without overwriting.nImplemented using fixed length recordsSequential files do not have fixed length records0200300400500byte offsets100100bytes100bytes100bytes100bytes100bytes100bytes49Random Access a File-fread()nfread-Transfer bytes from a file to a location in memorynFu

27、nction fread requires four argumentsret=fread(buffer,size,num,myptr);the number of objects readbuffer:Address of first memory cell to fillsize:Size of one valuenum:Maximum number of elements to copy from the file into memorymyptr:File pointer to a binary file opened in mode“rb”using function fopen50

28、Random Access a File fwrite()nfwrite-Transfer bytes from a location in memory to a filenfwrite(&number,sizeof(int),1,myPtr);&number-Location to transfer bytes fromsizeof(int)-Number of bytes to transfer1-For arrays,number of elements to transferIn this case,one element of an array is being transferr

29、edmyPtr file pointer51Random Access a File fwrite()(cont.)nWriting structsfwrite(&myObject,sizeof(struct myStruct),1,myPtr);sizeof-Returns size in bytes of object in parenthesesnTo write several array elementsPointer to array as first argumentNumber of elements to write as third argument52Creating a

30、 Binary File of Integers53Access Data in a Random Access FilenfseekSets file position pointer to a specific positionfseek(myPtr,offset,symbolic_constant);myPtr-pointer to fileoffset-file position pointer(0 is first location)symbolic_constant-specifies where in file we are reading fromSEEK_SET-seek s

31、tarts at beginning of fileSEEK_CUR-seek starts at current location in fileSEEK_END-seek starts at end of filenftellReturn the current position in a streamftell(myptr)myPtr-pointer to file54SEEK_SETSEEK_CURSEEK_ENDorigin:当前存取位置移动后offsetfile55Read file5657Homeworkn1 hr contestn20pm 21pm today?nftp：/第14次作业-12-15/58