ææä¸ä¸ªæ¢¦æ³:让ä¸æè¾å ¥å¾æ´å¿«
æ±æ¯ 2002.2
å¨è¥¿æ¹ç¤¾ä¼åäºå å¹´, 对西æå¨è®¡ç®æºä¸è¾å ¥ä¹ä¾¿å©çæ¯å¤ªææ触äº. æ 论æ¯å¨åå ¬å®¤
è¿æ¯å¨å®¶ä¸,æ 论æ¯åEMAILè¿æ¯å产å设计æ件,æ 论æ¯æå¡ååæ åºä½å®¿ç»è®°è¿æ¯å¥³å¿åä¸å¦ç
家åºä½ä¸,ä½è§é£é®çä¸åæ轻弹,èªç¶æµç ,è±è¯æå¥å°±å¦è¡äºæµæ°´è¬å¨å±å¹ä¸å¥æ¶èåº.
æ¶é´åæ¨åä¸ä¹ä¹å å¹´æ¥å¤©.å½æ¶ææ³å¦ä¸æè¾å ¥, å´åç°ä¸ä» æ¾ç¸å ³ç软件ä¸å®¹æ,å°±æ¯æ¾å°
äºä¹çé¾ä½¿ç¨ãè¿æ ·ï¼ä¸ç§æ³å©ç¨èªå·±ææ¡ç计ç®æºç¥è¯ä»å®ç¨çè§åº¦ç 究åæ¹è¿ä¸æè¾å ¥çæ³æ³
便ä»å¿éæ²¹ç¶èçï¼å¹¶å°æ¤ä»è¯¸äºè¡å¨.
ç°å¨,积å å¹´ä¹å¿è¡, ç»äºå¯ä»¥æ¿åºæ¥ä¸ä¸ªèªè®¤ä¸ºè¿åç¹æ ·çä¸è¥¿ç»å¤§å®¶çäº.è¿å°±æ¯ææè¿åå
å®çä¸æç¼è¾è¾å ¥ç¨åº,å«ãæ±çç®ãä¸æ书åå¹³å°.æå¨å ¶ä¸å®ç°äºä¸¤ä¸ªå ·åæ°ææ³çä¸æè¾å ¥æ¹æ³:
ã秦çè¡¡æ¼é³ãåã秦çè¡¡å½¢ç ã.
以ä¸åå«å¯¹æç主è¦æè·¯ååºæè¿°(å¦æä½ ä¸è½½äºãæ±çç®ãç¨åº,å¯è¿è¡"帮å©"èåä¸ç
ã秦çè¡¡è¾å ¥æ³ãæ¼ç¤ºå¹»ç¯ç.é£æ ·æ´å 形象)ã
ã秦çè¡¡æ¼é³ãã
è¯ç»æ¼é³æ¯äººä»¬æ常ç¨çè¾å ¥æ¹æ³ãæ对æ¼é³æ¹æ³ä½äºå¦ä¸æ¹è¿ï¼
ï¼1ï¼æ¼é³æ¹æ³çæ大弱ç¹,è«è¿äºéç è¾å¤ãæ解å³çåæ³æ¯ï¼å¨è¾ååæ¶,å¦ææè§éç 太å¤ï¼
å¯ç¨é®çæ左边ä¸åé®æ åºè¯¥å声è°ï¼å¦æ¯è¾è¯ç»ï¼åæ åºè¯å°¾åç声è°ï¼.è¿æ ·è½æåéè¯åé¤
æ约ååä¹ä¸ï¼å声åä¸å£°ï¼ãç±äºæ¼é³è¾å ¥æ¶èæµ·ä¸åºç°çæ¬æ¥å°±æ¯åè¯çåé³ï¼æ ç¨å£°è°å
éå®è¾ä¸ºèªç¶ã注æï¼æç设计ä¸æ¯é常æä¹ä¸ç带è°æ¼é³ãå 为å¨æçæ¹æ¡ä¸å声å¯å å¯ä¸å ï¼
å°±æ¯å ä¹åªå¯¹è¯çæåä¸åå ã
ï¼2ï¼æ¼é³ç第äºå¤§é®é¢ï¼æ¯æ²é®å«å¤ï¼åæ¼é¤å¤ï¼ãæç设计å 许å°æ¼é³ä¸çângâç®è¾ä¸º
âgâï¼å¦ fang è¾ä¸º fag ï¼liang 为 liagãè¿ä¸æ¥æ²çé®å¯å°±çäºä¸å°ãï¼æ¢ç¶ä¼ ç»ä¸å½¢ç
ç设计å 许åçç¥ï¼æ¼é³ç¼ç å½ç¶ä¹åºè¯¥å 许åçç¥ï¼ã
ï¼3ï¼å¯¹å声ä¸åç人ï¼ä¸ºç²¾ç¡®éåè¯(ç¹å«æ¯åå), å¯ç¨é®çå³è¾¹äºä¸ªç¹å®é®æ åºåå(æè¯å°¾å)
ç第ä¸,äºåæ«ç¬åï¼ä¸ç¨å ¨æ ï¼ï¼ä»¥å¤§å¤§åå°éç çãï¼åï¼1ï¼ä¸æ ·ï¼ç¬åé®ä¸æ¯éå ä¸å¯ï¼ã
è¿ç¹å«éç¨äºâçæâçæ å½¢ã
ï¼4ï¼è¯ç»æ¹æ³å¤§å¤§å å¿«äºè¾å ¥é度ãä½æ们ç»å¸¸ä¼éå°æ¾ä¸å°è¯çæ¶åï¼è¯æ³ä¸ä¸,å¦ææ²
äºä¸å é®å´åç°æ¾ä¸å°è¯åªå¥½å æéæ¥ä¼æ¯ä»ä¹æè§? ï¼ãå æ¤ï¼å¯¹äºä¸ä¸ªè¾å ¥æ³ï¼ä¸ä¸ªæºè½å
çï¼æç¨çâæ¾è¯æ¹æ³âæ¯é常éè¦ç. æ设计çæ¾è¯æ¹æ³ä¼å©ç¨å·²æ²çé®åºå,å°å ¶ä¸åé¨å
对åºçè¯æåï¼ä¼å 大è¯ï¼æ¾åºæ¥, 使æ¨è½»æ¾çç»ææ³è¦çè¯ï¼æ°è¯èªå¨å å ¥è¯åºï¼ãå ·ä½åæ³
æ¯ï¼å¦æä½ è¾å ¥æ¶åç°æ¾ä¸å°è¯ï¼å¯æ²ãå车ã便å å ¥æ¾è¯è¿ç¨ã
ï¼5ï¼æ±åè¾å ¥çè¿ç¨å®é ä¸æ¯ä¸ä¸ªå¯¹å符串è¿è¡å¹é çè¿ç¨ãéç¨è®¡ç®âç¼è¾è·ç¦»â
ï¼Edit-Distance,Dynamic Programming)çæ¹æ³ï¼ä¸åç¼å¹é æ¹æ³ç¸ç»åï¼ä¾¿å¯å®ç°å¯¹è¾å ¥å符
串ç模ç³å¹é ãè¿æ ·å¤§å¤§å 强äºè¾å ¥ç容éè½åï¼æ±ç¼è¾è·ç¦»çæ¹æ³è½è¾å¥½å°å¤çå°æ²ï¼å¤æ²ï¼
éæ²ï¼ä¸¤é®æ¬¡åºåçæ å½¢ï¼ãå¨æ±åè¾å ¥é¢åï¼æè¿æ²¡æè§å°è¿å ¶ä»äººä½¿ç¨è¿ç§æ¹æ³ã
ã秦çè¡¡å½¢ç ãã
æ¼é³æ¹æ³è½ç®åæå¦ï¼ä½éç å¤ï¼ä¸åºæ¬ä¸æ¯ä¸ç§åºäºéåçæ¹æ³ï¼æçä¸é«ã
并ä¸ï¼ç±äºéåé æ注æåçç»å¸¸è½¬ç§»ï¼å¯¹åä½æç»´é æå¹²æ°ãè¿ä¹æ¯ä¸ºä»ä¹çè¡·äº
æ±åè¾å ¥ç人æç»è¦å»å¦å½¢ç ã
å½¢ç ä¸è¬éç 大大å°äºé³ç ï¼ä½æ®éé¾å¦ãé¾å¦åå ä¹ä¸ï¼æ¯åæ ¹å¤ï¼é¾è®°ã
è¿æ¯å½¢ç ä¸å¯å æçé®é¢ãå½¢ç å¿ ç¶æ¯æ¼é³æ¹æ³é¾å¦ã
说å°å½¢ç ï¼âä¸ç å¥è ¾âçå±é¢ä¸ï¼æå¤çå°±æ¯å½¢ç ãæ对æè§è¿çå½¢ç çå°è±¡æ¯ï¼
å®ä»¬çåæ ¹åç»å¸¸å¸¸å´ç»çåæ ¹çæ¸æºãåä¹çæ½è±¡çä¸è¥¿æ¥åç»ãè¿æ ·é æçç»ææ¯ï¼
åå¨ä¸é®ä¸çåæ ¹äºç¸å¾ä¸è±¡ãæè§å¾è¿æ¯è´å½ç缺ç¹ãå 为ä¸è¬å¹³å¤´ç¾å§å¹¶ä¸ç¥éæ
ä¸å»å ³å¿åæ ¹çåä¹ææ¥é¾å»èï¼æ好çåæ ¹åç»åºçº¯ç²¹æç §âå½¢ç¸ä¼¼âçååå»åã
å¦å¤ï¼æäºè¾å ¥æ³åªå°åæ ¹åé å¨26个è±æåæ¯é®ä¸ï¼è¿é æèéå¨ä¸é®ä¸çåæ ¹è¿å¤
(æçè¾å ¥æ³è¾¾å°ä¸é®30个åæ ¹),ä¸ä¸é®å¯¹åºå¤ç»äºä¸ç¸è±¡çåæ ¹ãè¿ä¹é æä¸ä¸ªçèµ·æ¥
å°å®é ä¸é常éè¦çåæï¼æ æ³ç»åºä¸ä¸ªæ°å½çé®çåæ ¹åå¸å¾ãèè¿ä¸ªå¾å¯¹äººä»¬çè®°å¿
é常ææãå 为记å¿åæ ¹åå¸ï¼å®é ä¸å°±æ¯è®°å¿ç±åæ ¹å°é®ä½çäºç»´ä½ç½®çæ å°ï¼èé®ç
åæ ¹åå¸å¾åæ¯æ¤æ å°çç´æ¥è¡¨ç¤ºãè¿ç§åªç¨26个åæ¯é®çå½¢ç ï¼åºç¨å°ææ°å ¬å¸çæ±å
大å符éï¼å®ä¼éæ°é¢å¯¹éç çé®é¢ã
è¿æï¼æäºè¾å ¥æ³çè§åä¸èªç¶ãæ¯å¦è§å®ä¸åæ²é®å次ï¼å¯¹äºåæ ¹æ°å°äºåçï¼
è¦è¡¥ååè¯å«ç ï¼å¦æ«ç¬ç¬ç»çç¬ç»é®ï¼ï¼å¤äºåçï¼åå æ²åä¸åæ ¹ï¼ç¶åæ²å°¾åæ ¹ã
è¿ä½¿å¾å¨æåæ¶é¡»å¯¹æ¯åç¥å åæãæ¤äºçä¼¼ä¸å¤§ï¼å ¶å®å¤§å¤§å éäºè¾å ¥è çå¿çè´æ ã
æé对è¿äºé®é¢è®¾è®¡äºç§¦çè¡¡å½¢ç ãå®æå¦ä¸ç¹ç¹ï¼
1ãåæ ¹å¨é®çä¸çæåè¾åçãéç¨äºå¤§é®ççææ³ï¼å°åæ¯é®ï¼æ°åé®ï¼æ ç¹
符å·é®ï¼çåå 以使ç¨ãè¿æ ·ï¼å¨ä¸é®ä¸çåæ ¹è¾è±¡ï¼æ¯é®ä¸åæ ¹ä¹ä¸å¤ªå¤ãä¹å 为å¦æ¤ï¼
æ¬è¾å ¥æ³å¯ä»¥æä¾å¯ç¨çé®çåæ ¹åå¸å¾ï¼ä»¥å©è®°å¿ã
å½ç¶ï¼ä¸ºé¿å è¿å¤éç ï¼ä»æä¸è§åçæ å½¢ãä½æ¯è¾è§è¿çå ¶å®å½¢ç ï¼ç¸ä¿¡è¦å°çå¤ã
2.è¾å ¥è§åèªç¶ã人们ååæ¶å¤§èä¸åççäºï¼é¦å æ¯ç±åæ å°ä¸ºä»¥ç¬é¡ºä¸ºåºçåæ ¹
åºåï¼è¿ä¸ªæ å°ææ¶å¹¶ä¸ä¸ä¸å®æï¼èæ¯åé¢çåæ ¹æéäºåé¢çåæ ¹ï¼ï¼ç¶åéåæ ¹å
ä¸ãå æ¤æèªç¶çè¾å ¥è§åï¼æ£æ¯éåæ ¹ä¸ä¸è¾å ¥ã秦çè¡¡å½¢ç æ£æ¯è¿æ ·ä¸ç§âå ¨åæ ¹â
è¾å ¥æ³ãç±äºç§¦çè¡¡å½¢ç éåçåæ ¹è¾å¤§**ï¼å¯¹äºç®ä½åèè¨ï¼å¤§å¤æ°å¸¸ç¨åçç é¿ä¸å¤§ï¼
äºãä¸ãåé®å¯è¾ä¸åã对äºåæ ¹åºåè¾é¿çåï¼åæãä»»æå¹é é®ã帮å©ï¼ä¹é®é¢ä¸å¤§ã
ç±äºç¸ä¼¼åæ ¹åå¤ä¸é®ï¼èä¸å°åæ ¹èªæä¸åï¼æåæ ¹ï¼ï¼å¿ ç¶å°é æä¸é®åæ¶ç´æ¥
代表å¤åçæ å½¢ãé¤äºæå®ä¸åï¼é®åï¼ç¨ãç©ºæ ¼ãè¾å ¥å¤ï¼å ¶å®æåæ ¹ç¨è¿æ²å ¶æ¼é³é¦
åæ¯äºæ¬¡çæ¹æ³éåºè¾å ¥ï¼äº¦å¯ç¨F1ï¼F2çé®éåï¼ãå½ç¶å¨è®¾è®¡ä¸éä¿è¯è¿ç§éåçä¸
é®åºåä¸ä¼æ为任ä½å ¶å®åç¼ç çåç¼ï¼ä¸ç¶å ¶å®åå°±æ æ³è¾å ¥äºã
è¿ç§è¿æ²æ¼é³é¦åæ¯äºæ¬¡çéåæ¹æ³ï¼ç±äºéå¨å¤§èä¸åæ åºè¯¥åçé³ï¼ä¼ä¸ä¼å é
è¾å ¥è çå¿çè´æ å¢ï¼å®è·µè¡¨æï¼é®é¢ä¸å¤§ãçç±ä¸ºï¼ä¸ï¼å¯¹è±¡ä¸ºæåæ ¹ï¼ä¸éæåï¼æ
ç±å½¢å°é®ç第ä¸æ¥æ å°è´æ å°ï¼äºï¼åªéå¨å¤§èä¸åæ åºè¯¥åçæ¼é³é¦åæ¯ï¼ä¸æ¯æ´ä¸ªæ¼
é³åºåã
3.ç±äºåæ ¹å¨å¤§é®çä¸åæ£å¼æ¥ï¼ä¸æåä¸ä¸äºå夫ï¼æ éç å°ï¼ä¸éç»å¸¸éåã
4.é®ä½å¸å±åºæ¬åä¹ææ³è¦æ±ï¼å³é®å ¥æ±åæ¶æåºèªç¶ï¼ä¸å«æã
5.è¾å ¥æ ç¹ç¬¦å·åè±æåæ¯æ¶æ éåæ¢ç¶æã
6. å½å¯¹æè¾åæï¼äºï¼åæ ¹ä¸è®°å¾æ¶ï¼è¿æ¯å¸¸åççäºï¼ï¼å¯é®å ¥ãä»»æå¹é é®ã以代ä¹ã
æ»ä¹ï¼ç§¦çè¡¡å½¢ç è¾å ¥æ³çåºæ¬è®¾è®¡æ¨ç为ï¼
ï¼1ï¼ä¸ºå®ç°éåæ ¹ä¸ä¸è¾å ¥æ±åçç®åè¾å ¥è§åï¼éåæ ¹æ¶ï¼åªæé大åæ ¹**ï¼æè½
ç¡®ä¿æçï¼åªæç®ä½åè½ä½å°è¿ç¹ï¼ã
ï¼2ï¼é大åæ ¹ï¼å¿ ç¶éåºäºç¾å¤å°ä¸ç¾å¤ä¸ªåæ ¹ï¼ä¸å¯è½ä» ç±26个åæ¯é®ä½é®æï¼ä¸
å®è¦ç¨å°å æ¬æ ç¹ç¬¦å·é®ï¼æ°åé®å¨å çå ¶å®åé®ããSHIFTãï¼ãCAPS LOCKãçé®å
åªå¯¹è¾è±æææä¹ï¼ä½ç½®ä¹ä¸éï¼å³ãSHIFTãé¤å¤ï¼ï¼åºå¯ç¨ä½æ£å¸¸é®æã
ï¼3ï¼ç±åæ ¹å°é®çåé ï¼éµå¾ªåä¸é®ä¸åæ ¹å½¢ç¶ç¸ä¼¼çååï¼ä¸ºé¿å éæ ¹è¿å¤ï¼äº¦æ
ä¾å¤æ å½¢ãç±åæ ¹å°é®çèç³»ï¼å¤æ°æå½¢ç¸ä¼¼ï¼é£æå¾æ¨¡ç³ï¼ï¼ææ¶ææ¼é³ã p>
ï¼4ï¼åä¸é®ä¸ä¼æå¤ä¸ªæåæ ¹ï¼é¡»æåæ³éåºå®ä»¬ãç¨è¿æ²ä¸¤ä¸æ¼é³é¦åæ¯çåæ³è¾
èªç¶ï¼å辨çæ¯ç¨æ«ç¬ç¬ç»ç è¦é«ã
ï¼5ï¼ä½¿ç¨ãSHIFTãåå·¦
ï¼6ï¼è®¾å·¦ãALTãé®ä¸ºç¹å«é®âç¥âé®ï¼ç¨æ¥æ¿ä»£éæäºçä¸ä¸ªæå¤ä¸ªåæ ¹ã以å©äº
å¦ä¹ åå®é è¾å ¥ã
æç设计åºæ¬ä¸æâå½¢ç¸ä¼¼âçååå®æåæ ¹ï¼æ åæ ¹ä¹çå¤ï¼å®é çä»·åæ ¹å¹¶ä¸å¤ï¼
åªæäºå个ï¼äºå个é®ï¼ãåæ ¹è¡¨çèµ·æ¥å人ï¼å¯ç¨ä¸ç¹å·¥å¤«ï¼è¿æ±åè¾å ¥å¯å°±åç¹ä¸ºç®äºï¼
以ä¸æè¿°ä¸è½ä»¥å½¢ç ç¯å¹ 为å¤ï¼ä½ä»ææã秦çè¡¡è¾å ¥æ³ãæ¾å°ç½ä¸åææ¶å°çåé¦
ä¿¡æ¯çï¼ä»¥ã秦çè¡¡æ¼é³ãæ´å欢è¿ãè¿æ¾ç¤ºåºä½¿ç¨æ¼é³ç人è¿æ¯ä½¿ç¨å½¢ç ç为å¤ã
ä¸åæå,ç»ä¸½å¤é.ä¸åè¯è¨,å大精深.å¦å°çå¨æçä¹å¹´,è½ä¸ºå¼æ¬ä¸åè¯æå°½
å¾®èä¹å,ä¹å°±ä¸ææ¤ç.
ï¼jiangyi@hanwj.comï¼
åèæç®[1]âä¸æåçæºæ¢°åâï¼å¢¨æµ·ï¼ä¹ä¸å¹´ä¸æ第ä¸ä¸âæï¼ãåå¤ææãã
[2]âæ±æ¯ åç«ã秦çè¡¡è¾å ¥æ³ãâ, äºï¼¯ï¼¯ä¸å¹´äºæåæ¥,é西æ¥æ¥ã
[3] Introduction to Algorithms, a creative approach, pp. 155-158,
Manber, U., Addison-Wesley, 1989.
åèç½é¡µ[1] http://www.hanwj.com