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

2008/12/15Lesson25ExtendBBS12008/12/15Lesson25ExtendBBSReportsandrelatedtopicsOtherbbsReportsThepreprocessorHomeworkDec-112ReportsandrelatedtopicsOtheSoftwaredevelopmentRequestAnalysisFormalizeDesignCodingTest&resultanalyze3SoftwaredevelopmentRequestARequest:希望能自动从所有回贴中找到三种最具代表性的帖子：A、最能代表当前所有回贴内容的帖子。B、内容与其他所有回贴最不同的帖子。C、与某预设（自设）的敏感话题最相关的回帖。4Request:希望能自动从所有回贴中找到三种最具代表性的帖ProblemAnalysis——

最能代表当前所有回贴内容的帖子‘代表’到底是什么意思？所有回帖？5ProblemAnalysis——

最具代表性的帖子

—高戈，秦毅成在帖子中随机抽取2个帖子进行DP最长公共子串匹配。进行8n（n为帖子总数）次，这样在20%-30%以上帖子中都出现的关键词（关键词长度要大于等于4，小于等于10）我们都基本能记录下来。然后用其中出现次数较多的20个关键词（必须满足出现次数大于等于3）对每个帖子进行匹配，并根据匹配情况算出它的权值，其中匹配权值最高的那个帖子即为最具代表性的帖子。优点：不必分词，领域无关，自适应。算法复杂度较低。缺点：？6最具代表性的帖子—高戈，秦毅成6测试数据1：关于研究生应聘卖猪肉岗位的新闻的回帖运行结果:1最具代表性的帖子这是中国资源的浪费，读完研究生要耗去多少人力和财力，国家和家庭要付出多少，卖猪肉小学毕业就绰绰有余了，难道非要研究生吗？一个人从小学毕业开始卖猪肉，一年赚一万，又比在校学生少花费一万来计算，从初中到研究生毕业就是28万余元啊！说不定你研究生毕业人家就成养猪专业户或企业家了，你们研究生就是给人家打工的，年薪10万算什么？如果一个国家投资那么多钱就是为了培养卖猪肉的，真是太可悲了呀！相似度为1500左右，多次测试结果稳定2最不同的帖子可能性较多，有三至四种相似度为0到2之间，多次测试结果不稳定7测试数据1：关于研究生应聘卖猪肉岗位的新闻的回帖运行结果:7测试数据2：

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

对台检方周末加班写起诉书陈水扁可能被求处重刑展望：现在我们生成词典采用的是随机算法，对于较大规模的数据依旧是束手无策。因此，我们考虑将来可以进一步采用遗传算法进行优化，筛选出最具代表性的关键字词典。利用遗传算法可以更加有效地解决空间时间的紧张问题。另外，对于匹配算法上来讲，我们采用的是最基础的动态规划，应该可以改进成串的最大匹配算法，这样空间和时间的复杂度都可以远远小于O（mn），大幅度地提高我们的效率。9展望：现在我们生成词典采用的是随机算法，对于较大规模的数据依FormalizeMaxcommonsubstringKeywordsset+frequencyVector+class10FormalizeMaxcommonsubstring1建模：（张磊、刘邦）对汉字的编码和其他字符的编码统一化处理。对所有帖子组成的集合Z中所用的字Ci统计重复次数Ti。对第i个帖子，统计其中字的Ti之和，除以第i个帖子中字的个数N，相当于求一个平均频数，以此作为第i个帖子的代表全体意思程度的指数。建立停用字库，对原帖用字进行过滤。11建模：（张磊、刘邦）对汉字的编码和其他字符的编码统一化处理。陈健张海峰叶树雄：找关键词：在规定贴子数目以上的帖子出现过的连续字符（已编码）把每个贴子向量化内积运算12陈健张海峰叶树雄：找关键词：在规定贴子数目以上的帖子出现华连盛、蔡斯任：计算了每条回帖被回复的次数，特别加入了对于“顶”、“赞”、“支持”之类的回复的查找，普通回复每条算10分，包含上述字眼的每条算20分；考虑最有代表性的回帖必须和主题贴有一定的关联，又不能完全没有自己的观点，所以设计了一个相似度的评分，如果一条帖与主题贴的相似度为30%则定义为30分，相似度为0或100%的定义为0分，其余部分呈线性。最后将这两方面的评分相加得到最后的得分，找出得分最多的回帖即为最有代表性的。进行过前面的处理后，考虑可以去掉一些评分较低的帖子，对剩余的帖子统计每个汉字出现的频率，找出出现频率最高的几个汉字作为关键字（去除停用字词），再对这些帖子进行一遍关键字的检索，在进行一轮评分，这样结果可能会更加准确，

13华连盛、蔡斯任：计算了每条回帖被回复的次数，特别加入了对于codingWorkgroupProgrammingenvironmentIDEWritingingoodstyle14codingWorkgroup14//by周先达15//by周先达151616施维加、袁洋、仝艺对每一个帖子进行加权处理，称为代表性权值。A的代表性权值为A与其余所有帖子的相似度之和：W_represent(A)=similar(A,X1)+similar(A,X2)+….similar(A,Xn)similar(A,B)=limit(g(lcs(A,B),kmp(A,B)))lcs函数返回A和B的最长公共子序列的长度；kmp函数返回A和B的最长公共子串；g函数为一个2元函数，具体的表示形式为：g=ax2+by2+cxy+dx+ey+f(x,y可以有更高次项)其中x,y分别为lcs和kmp返回参数，而a,b,c,d,e,f分别为6个待定系数17施维加、袁洋、仝艺对每一个帖子进行加权处理，称为代表性权值。工程在结构上做了改进：统一了搜索机制，重写了搜索引擎，给出了一个更一般的搜索方案(locateRep)，实现将搜索输出和删除统一的回馈机制（使用一个数组作为标记）。改进了命令语法，增加了逻辑运算功能，使之变得更加合理、有效。将大部分数组实现了动态化，使得能够更好的支持较早的编译器，并且使程序变得更稳定。本程序将工程各部分分离，为每一位参与者提供了数据标准，统一了函数接口。在代码实现上，使用了函数指针作为参数加入到搜索过程中，简化了重复的代码，并使得维护性得到提高。使用了函数指针数组来执行驱动，这样使得命令的可扩展性得到保障，使得今后添加命令将变得比较方便。18工程在结构上做了改进：统一了搜索机制，重写了搜索引擎，给出了Thepreprocessoroverviewmacrosfileinclusionconditionalcompilation19Thepreprocessoroverview19PreprocessorOverviewperforms:macrosubstitutionconditionalcompilationinclusionofnamedfilesthepreprocessormayactuallybeaseparateprogram,eventhoughitisinvokedbytheCcompilerpreprocessordirectivesbeginwitha#signpreprocessordirectivesarenotpartoftheClanguageproperCcompilerinvokesthepreprocessorfirstbeforedoingitscompilationprocessing(hencethetermpre-processor)20PreprocessorOverviewperforms:Macrosmakesprogramsmorereadable,modifiableandportable(butdon’toverdoit!)#define

-defineamacrosimplemacromacrowithparameters#undef

-removeamacrodefinitionparametermodifiers:#-stringsubstitution21MacrosmakesprogramsmorereadSimpleMacroDefinition#define

identifier

token-sequenceExamples:#define

TRUE1#define

TWO_PI2.0*3.141592654theidentifierisreplacedbythetoken-sequenceidentifiersarecapitalizedbyconvention22SimpleMacroDefinition#defineMacrowithParametersDefinition#define

identifier(identifier-list)

token-seqExample:#define

MAX(a,b)(((a)>(b))?(a):(b))theidentifierisreplacedbythetoken-sequenceeachparameterspecifiedintheidentifier-listissubstitutedinthetoken-seqbecarefulwithspacesandgrouping23MacrowithParametersDefiniti24242525MacroUsage#defineTRUE1#defineMAX(a,b)(((a)>(b))?(a):(b))voidsomefunction(intx,inty){intmaxvalue;while(TRUE){//someCcodemaxvalue=MAX(x,y);//somemoreCcode}}macroisknownfromdefinitiontoendoffile26MacroUsage#defineTRUE1macroRemovingaMacroDefinition#undefidentifierExamples:#undefDEBUG#undefMAXusefulfor:conditionalcompilationclearingoutamacrowiththesamenameasafunction27RemovingaMacroDefinition#unParameterModifiers#-stringsubstitution#definestr(x)#xstr(testing)“testing”somewhatusefulinprintf()statements28ParameterModifiers#-string2929The##operatorJointotokentogetheri##nin30The##operatorJointotokent3131FileInclusionincludefiles(.h)usefulinorganizing:preprocessordefinitionsstructuredefinitionsprototypedeclarationsglobalvariabledeclarationsplacedattopofCsourcefile(.c),willbeincludedaspartofthatfile,canbenested32FileInclusionincludefiles(.FileInclusionMethods#include<filename.h>searchesforfileonlyinthestandardsystemdirectories#include“filename.h”searchesforfileinthecurrentdirectoryandinthestandardsystemdirectories33FileInclusionMethods#includeConditionalCompilationcanconditionallyincludeorexcludechunksofcodefromasourcefile“if–else–end”sequenceusefulfor:maintainingmultipleversionsdebugging34ConditionalCompilationcancon#ifndef_ADD_H#define_ADD_H…#endif35#ifndef_ADD_H35#if…#eif,#else…#endif#ifdefined(POJ)#defineprintInt(var)printf(#var"=%d\n",var)#defineprintx(n)printInt(i##n)#else….#endif

36#if…#eif,#else…#endif#ifConditionalCompilationExample#ifndefDEBUGsomefunction();#elseprintf(“callingsomefunction()”);#endiftherealcodedebugcode37ConditionalCompilationExamplIndefinitenumberofarguments

functionsmaytakeavariablenumberofargumentsandaredeclaredwithanellipsisinplaceofthelastparameter.suchas:intprintf(constchar*_Format,...);<stdarg.h>isaheaderintheCstandardlibraryoftheCprogramminglanguagethatallowsfunctionstoacceptanindefinitenumberofarguments.38Indefinitenumberofarguments393940404141VariableNumberofargumentstoMacrosThreedotsattheendofargumentlistSpecialidentifier:__VA_ARGS__#definedebugPrintf(…)printf(“DEBUG”__VA_ARGS__)debugPrintf(“helloworld”);debugPrintf(“%d%f”,i,f);42VariableNumberofargumentstBinaryfilesoperation(Review)textfileanamedcollectionofcharacterssavedinsecondarystorageinput(output)streamcontinuousstreamofcharactercodesrepresentingtextualinput(oroutput)data(FILE*)stdinsystemfilepointerforkeyboard’sinputstream(FILE*)stdout,stderrsystemfilepointersforscreen’soutputstream43Binaryfilesoperation(ReviewFileOpenMode44FileOpenMode44BinaryFilesFormattedTextfilescontainvariablelengthrecordsmustbeaccessedsequentially,processingallrecordsfromthestartoffiletoaccessaparticularrecordBinaryFiles(randomaccessfile)afilecontainingbinarynumbersthatarethecomputer’sinternalrepresentationofeachfilecomponentcontainfixedlengthrecordscanbeaccesseddirectly,directlyaccessingtherecordthatisrequiredsizeofoperatorthatfindsthenumberofbytesusedforstorageofadatatype45BinaryFilesFormattedTextfilTheDataHierarchyBit-smallestdataitemValueof0or1Byte–8bitsUsedtostoreacharacterDecimaldigits,letters,andspecialsymbolsField-groupofcharactersconveyingmeaning

Example:yournameRecord–groupofrelatedfieldsRepresenteda

structoraclassExample:Inapayrollsystem,arecordforaparticularemployeethatcontainedhis/heridentificationnumber,name,address,etc.File–groupofrelatedrecordsExample:payrollfileDatabase–groupofrelatedfiles46TheDataHierarchyBit-smalle4747InaRandomAccessFile…DataDataunformatted(storedas"rawbytes")inrandomaccessfilesAlldataofthesametype(ints,forexample)usethesamememoryAllrecordsofthesametypehaveafixedlengthDatanothumanreadable48InaRandomAccessFile…Data4RandomAccessAccessindividualrecordswithoutsearchingthroughotherrecordsInstantaccesstorecordsinafileDatacanbeinsertedwithoutdestroyingotherdataDatapreviouslystoredcanbeupdatedordeletedwithoutoverwriting.ImplementedusingfixedlengthrecordsSequentialfilesdonothavefixedlengthrecords49RandomAccessAccessindividualRandomAccessaFile--fread()fread--TransferbytesfromafiletoalocationinmemoryFunctionfreadrequiresfourargumentsret=fread(buffer,size,num,myptr);thenumberofobjectsreadbuffer:Addressoffirstmemorycelltofillsize:Sizeofonevaluenum:Maximumnumberofelementstocopyfromthefileintomemorymyptr:Filepointertoabinaryfileopenedinmode“rb”usingfunctionfopen50RandomAccessaFile--freadRandomAccessaFile

—fwrite()fwrite-Transferbytesfromalocationinmemorytoafilefwrite(&number,sizeof(int),1,myPtr);

&number-Locationtotransferbytesfromsizeof(int)-Numberofbytestotransfer1-Forarrays,numberofelementstotransferInthiscase,"oneelement"ofanarrayisbeingtransferredmyPtr–filepointer51RandomAccessaFile

RandomAcce