2008/12/15Lesson25ExtendBBS12008/12/15Lesson25ExtendBBSReportsandrelatedtopicsOtherbbsReportsThepreprocessorHomeworkDec-112ReportsandrelatedtopicsOtheSoftwaredevelopmentRequestAnalysisFormalizeDesignCodingTest&resultanalyze3SoftwaredevelopmentRequestARequest:希望能自動(dòng)從所有回貼中找到三種最具代表性的帖子：A、最能代表當(dāng)前所有回貼內(nèi)容的帖子。B、內(nèi)容與其他所有回貼最不同的帖子。C、與某預(yù)設(shè)（自設(shè)）的敏感話題最相關(guān)的回帖。4Request:希望能自動(dòng)從所有回貼中找到三種最具代表性的帖ProblemAnalysis——

最能代表當(dāng)前所有回貼內(nèi)容的帖子‘代表’到底是什么意思？所有回帖？5ProblemAnalysis——

最具代表性的帖子

—高戈，秦毅成在帖子中隨機(jī)抽取2個(gè)帖子進(jìn)行DP最長(zhǎng)公共子串匹配。進(jìn)行8n（n為帖子總數(shù)）次，這樣在20%-30%以上帖子中都出現(xiàn)的關(guān)鍵詞（關(guān)鍵詞長(zhǎng)度要大于等于4，小于等于10）我們都基本能記錄下來(lái)。然后用其中出現(xiàn)次數(shù)較多的20個(gè)關(guān)鍵詞（必須滿足出現(xiàn)次數(shù)大于等于3）對(duì)每個(gè)帖子進(jìn)行匹配，并根據(jù)匹配情況算出它的權(quán)值，其中匹配權(quán)值最高的那個(gè)帖子即為最具代表性的帖子。優(yōu)點(diǎn)：不必分詞，領(lǐng)域無(wú)關(guān)，自適應(yīng)。算法復(fù)雜度較低。缺點(diǎn)：？6最具代表性的帖子—高戈，秦毅成6測(cè)試數(shù)據(jù)1：關(guān)于研究生應(yīng)聘賣(mài)豬肉崗位的新聞的回帖運(yùn)行結(jié)果:1最具代表性的帖子這是中國(guó)資源的浪費(fèi)，讀完研究生要耗去多少人力和財(cái)力，國(guó)家和家庭要付出多少，賣(mài)豬肉小學(xué)畢業(yè)就綽綽有余了，難道非要研究生嗎？一個(gè)人從小學(xué)畢業(yè)開(kāi)始賣(mài)豬肉，一年賺一萬(wàn)，又比在校學(xué)生少花費(fèi)一萬(wàn)來(lái)計(jì)算，從初中到研究生畢業(yè)就是28萬(wàn)余元??！說(shuō)不定你研究生畢業(yè)人家就成養(yǎng)豬專(zhuān)業(yè)戶或企業(yè)家了，你們研究生就是給人家打工的，年薪10萬(wàn)算什么？如果一個(gè)國(guó)家投資那么多錢(qián)就是為了培養(yǎng)賣(mài)豬肉的，真是太可悲了呀！相似度為1500左右，多次測(cè)試結(jié)果穩(wěn)定2最不同的帖子可能性較多，有三至四種相似度為0到2之間，多次測(cè)試結(jié)果不穩(wěn)定7測(cè)試數(shù)據(jù)1：關(guān)于研究生應(yīng)聘賣(mài)豬肉崗位的新聞的回帖運(yùn)行結(jié)果:7測(cè)試數(shù)據(jù)2：

對(duì)臺(tái)檢方周末加班寫(xiě)起訴書(shū)陳水扁可能被求處重刑的評(píng)論。1最具代表性的帖子貪污這么多錢(qián)在國(guó)際上也是前無(wú)先例??！不判死刑能給世人交代嗎？應(yīng)該讓陳水扁象薩達(dá)姆那樣被臺(tái)灣人民絞死！現(xiàn)在還在挺扁的綠營(yíng)人士及民進(jìn)黨都是神經(jīng)病患者，根本就沒(méi)有是非觀念，真是臺(tái)灣的不幸啊！其他出現(xiàn)結(jié)果很不理解臺(tái)灣的極少數(shù)支持陳水扁的人，陳水扁貪污這么多，在祖國(guó)大陸這樣的貪污犯是要處死刑的；難道支持陳水扁的少數(shù)人是接受了陳水扁的好處？是共犯？相似度為1200到1300，多次測(cè)試結(jié)果較為穩(wěn)定2最不同的帖子可能出現(xiàn)的結(jié)果：特赦，為什么??？難道法律面前，人人不平等啊。不是可能被處以重刑，而是必須判重刑！天理難容啊！報(bào)應(yīng)啊，哈哈哈哈哈哈哈哈哈哈哈哈哈曾經(jīng)人上人，如今階下囚。談人生為何如此丑惡？等等相似度為1或0，多次測(cè)試結(jié)果非常不穩(wěn)定8測(cè)試數(shù)據(jù)2：

對(duì)臺(tái)檢方周末加班寫(xiě)起訴書(shū)陳水扁可能被求處重刑展望：現(xiàn)在我們生成詞典采用的是隨機(jī)算法，對(duì)于較大規(guī)模的數(shù)據(jù)依舊是束手無(wú)策。因此，我們考慮將來(lái)可以進(jìn)一步采用遺傳算法進(jìn)行優(yōu)化，篩選出最具代表性的關(guān)鍵字詞典。利用遺傳算法可以更加有效地解決空間時(shí)間的緊張問(wèn)題。另外，對(duì)于匹配算法上來(lái)講，我們采用的是最基礎(chǔ)的動(dòng)態(tài)規(guī)劃，應(yīng)該可以改進(jìn)成串的最大匹配算法，這樣空間和時(shí)間的復(fù)雜度都可以遠(yuǎn)遠(yuǎn)小于O（mn），大幅度地提高我們的效率。9展望：現(xiàn)在我們生成詞典采用的是隨機(jī)算法，對(duì)于較大規(guī)模的數(shù)據(jù)依FormalizeMaxcommonsubstringKeywordsset+frequencyVector+class10FormalizeMaxcommonsubstring1建模：（張磊、劉邦）對(duì)漢字的編碼和其他字符的編碼統(tǒng)一化處理。對(duì)所有帖子組成的集合Z中所用的字Ci統(tǒng)計(jì)重復(fù)次數(shù)Ti。對(duì)第i個(gè)帖子，統(tǒng)計(jì)其中字的Ti之和，除以第i個(gè)帖子中字的個(gè)數(shù)N，相當(dāng)于求一個(gè)平均頻數(shù)，以此作為第i個(gè)帖子的代表全體意思程度的指數(shù)。建立停用字庫(kù)，對(duì)原帖用字進(jìn)行過(guò)濾。11建模：（張磊、劉邦）對(duì)漢字的編碼和其他字符的編碼統(tǒng)一化處理。陳健張海峰葉樹(shù)雄：找關(guān)鍵詞：在規(guī)定貼子數(shù)目以上的帖子出現(xiàn)過(guò)的連續(xù)字符（已編碼）把每個(gè)貼子向量化內(nèi)積運(yùn)算12陳健張海峰葉樹(shù)雄：找關(guān)鍵詞：在規(guī)定貼子數(shù)目以上的帖子出現(xiàn)華連盛、蔡斯任：計(jì)算了每條回帖被回復(fù)的次數(shù)，特別加入了對(duì)于“頂”、“贊”、“支持”之類(lèi)的回復(fù)的查找，普通回復(fù)每條算10分，包含上述字眼的每條算20分；考慮最有代表性的回帖必須和主題貼有一定的關(guān)聯(lián)，又不能完全沒(méi)有自己的觀點(diǎn)，所以設(shè)計(jì)了一個(gè)相似度的評(píng)分，如果一條帖與主題貼的相似度為30%則定義為30分，相似度為0或100%的定義為0分，其余部分呈線性。最后將這兩方面的評(píng)分相加得到最后的得分，找出得分最多的回帖即為最有代表性的。進(jìn)行過(guò)前面的處理后，考慮可以去掉一些評(píng)分較低的帖子，對(duì)剩余的帖子統(tǒng)計(jì)每個(gè)漢字出現(xiàn)的頻率，找出出現(xiàn)頻率最高的幾個(gè)漢字作為關(guān)鍵字（去除停用字詞），再對(duì)這些帖子進(jìn)行一遍關(guān)鍵字的檢索，在進(jìn)行一輪評(píng)分，這樣結(jié)果可能會(huì)更加準(zhǔn)確，

13華連盛、蔡斯任：計(jì)算了每條回帖被回復(fù)的次數(shù)，特別加入了對(duì)于codingWorkgroupProgrammingenvironmentIDEWritingingoodstyle14codingWorkgroup14//by周先達(dá)15//by周先達(dá)151616施維加、袁洋、仝藝對(duì)每一個(gè)帖子進(jìn)行加權(quán)處理，稱為代表性權(quán)值。A的代表性權(quán)值為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函數(shù)返回A和B的最長(zhǎng)公共子序列的長(zhǎng)度；kmp函數(shù)返回A和B的最長(zhǎng)公共子串；g函數(shù)為一個(gè)2元函數(shù)，具體的表示形式為：g=ax2+by2+cxy+dx+ey+f(x,y可以有更高次項(xiàng))其中x,y分別為lcs和kmp返回參數(shù)，而a,b,c,d,e,f分別為6個(gè)待定系數(shù)17施維加、袁洋、仝藝對(duì)每一個(gè)帖子進(jìn)行加權(quán)處理，稱為代表性權(quán)值。工程在結(jié)構(gòu)上做了改進(jìn)：統(tǒng)一了搜索機(jī)制，重寫(xiě)了搜索引擎，給出了一個(gè)更一般的搜索方案(locateRep)，實(shí)現(xiàn)將搜索輸出和刪除統(tǒng)一的回饋機(jī)制（使用一個(gè)數(shù)組作為標(biāo)記）。改進(jìn)了命令語(yǔ)法，增加了邏輯運(yùn)算功能，使之變得更加合理、有效。將大部分?jǐn)?shù)組實(shí)現(xiàn)了動(dòng)態(tài)化，使得能夠更好的支持較早的編譯器，并且使程序變得更穩(wěn)定。本程序?qū)⒐こ谈鞑糠址蛛x，為每一位參與者提供了數(shù)據(jù)標(biāo)準(zhǔn)，統(tǒng)一了函數(shù)接口。在代碼實(shí)現(xiàn)上，使用了函數(shù)指針作為參數(shù)加入到搜索過(guò)程中，簡(jiǎn)化了重復(fù)的代碼，并使得維護(hù)性得到提高。使用了函數(shù)指針數(shù)組來(lái)執(zhí)行驅(qū)動(dòng)，這樣使得命令的可擴(kuò)展性得到保障，使得今后添加命令將變得比較方便。18工程在結(jié)構(gòu)上做了改進(jìn)：統(tǒng)一了搜索機(jī)制，重寫(xiě)了搜索引擎，給出了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