DIRECTORYRope USING [ROPE, Size, Fetch, FromRefText],SpellingCorrection;SpellingCorrectionImpl: CEDAR MONITORIMPORTS RopeEXPORTSSpellingCorrection =BEGINROPE: TYPE = Rope.ROPE;BruteForceCorrection: PUBLIC PROC [word: ROPE, f: PROC [REF TEXT] RETURNS [BOOL], buffer: REF TEXT] RETURNS [corrections: LIST OF ROPE _ NIL, newBuffer: REF TEXT] = {s: CARDINAL _ word.Size[];w: REF TEXT;c, t: CHAR;Test: PROC [w: REF TEXT] = INLINE {IF f[w] THENcorrections _ CONS[Rope.FromRefText[w], corrections];};IF buffer.maxLength < s+1 THENbuffer _ NEW[TEXT[s+1]];w _ buffer;w.length _ s;FOR i: CARDINAL IN [0..s) DOw[i] _ Rope.Fetch[word, i];ENDLOOP;FOR i: CARDINAL IN [0..s-1) DOt _ w[i];  w[i] _ w[i+1]; w[i+1] _ t;Test[w];w[i+1] _ w[i];  w[i] _ t;ENDLOOP;c _ w[s-1];w.length _ s - 1;FOR i: CARDINAL DECREASING IN [0..s-1) DOTest[w];t _ c;  c _ w[i];  w[i] _ t;ENDLOOP;Test[w];w.length _ s;FOR i: CARDINAL DECREASING IN [0..s-1) DOw[i+1] _ w[i];ENDLOOP;w[0] _ c;w.length _ s + 1;FOR i: CARDINAL DECREASING IN [0..s] DOIF i < s THEN w[i+1] _ w[i];IF i = s THEN c _ w[s-1] ELSE c _ w[i];IF c IN ['A..'Z] THENFOR x: CHAR IN ['A..'Z] DOw[i] _ x;Test[w];ENDLOOPELSE FOR x: CHAR IN ['a..'z] DOw[i] _ x;Test[w];ENDLOOP;ENDLOOP;FOR i: CARDINAL IN [0..s) DOw[i] _ w[i+1];ENDLOOP;w.length _ s;FOR i: CARDINAL IN [0..s) DO c _ w[i];IF c IN ['A..'Z] THENFOR x: CHAR IN ['A..'Z] DOIF x # c THEN {w[i] _ x;Test[w];};ENDLOOPELSEFOR x: CHAR IN ['a..'z] DOIF x # c THEN {w[i] _ x;Test[w];};ENDLOOP;w[i] _ c;ENDLOOP;newBuffer _ buffer;};END.CHANGE LOGCreated by Nix on October 7, 1983 2:22 pm   ┤  File: SpellingCorrectionImpl.mesaLast Edited by: Nix, October 8, 1983 5:03 pmGenerates all words close to "word" and returns a list of those for which f returns TRUE.  The generation of close words proceeds in the usual brute-force manner: transpositions of adjacent letters in the word are considered first, then deletions of single letters, then insertions of single letters from 'a to 'z, and finally replacement of single letters by one of the other twenty five letters between 'a and 'z.  The corrections proposed try to mimic the same capitalization style of  the root word.Tests to see if a correction is in the word list and adds it to the correction list if it is.Try transpositions.  Transpose each of the adjacent characters in the word and see if any of those are in the word list.Try deletions.  Delete each of the characters in the word and see if the resulting word is in the word list.Try insertions.  Insert a character between 'a and 'z in each of the s+1 possible locations in the word and see if the resulting word is in the dictionary.Try replacements.  Replace each of the letters in the word with one of the other 25 letters and see if that word is in the dictionary.Э╩  Ш Ц"Cedar" styleЪЬ!Щ!JЩ,ЧunitЪ╧k	Ш	IcodeЪЬЭЬЭЬШ,LШЧKЪ╧bЬЭЬЭШ%ЪЭЬШLЪЬШЧЪЭШLЪЬШЧLЪЭШLЪЭЬЭЬЭЬШJШ ЪЮЬШJЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШNJЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШBJЩўJЪЬЭЬШJЪЬЭЬЭЬШJЪЬЭЬШJШ Ъ
╧nЬЭЬЭЬЭЬЭЬШ#JЪЬ]Щ]ЪЭЬЭШJЪЬЭЬ#Ш5ЧJШJШ ЧЪЭЬЭШJЪЬ	ЭЬЭЬШЧJШJШЪЭЬЭЬЭЬЭШJШJЪЭЬШЧШ JЪЬxЩxЧЪЭЬЭЬЭЬ
ЭШJШ%JЪЬШJШJЪЭЬШJШ JЪЬlЩlЧJЪЬШJШЪ	ЭЬЭЬЭ
ЬЭЬ
ЭШ)JЪЬШJШJЪЭЬШЧJЪЬШJШЪ	ЭЬЭЬЭ
ЬЭЬ
ЭШ)JШJЪЭЬШЧJШ	Ш JЪЬЫЩЫЧJШЪ	ЭЬЭЬЭ
ЬЭЬЭШ'JЪЭЬЭЬШJЪЭЬЭЬЭЬ
Ш'ЪЭЬЭЬ
ЭШЪЭЬЭЬЭЬ
ЭШJШ	JЪЬШJЪЭШЧЧЪЭЬШЪЭЬЭЬЭЬ
ЭШJШ	JЪЬШJЪЭЬШЧЧJЪЭЬШЧЪЭЬЭЬЭЬЭШJШJЪЭЬШЧJШШ JЪЬЖЩЖЧЪЭЬЭЬЭЬЭЬШJШ	ЪЭЬЭЬ
ЭШЪЭЬЭЬЭЬ
ЭШЪЭЬЭЬШJШ	JЪЬШJШЧJЪЭШЧЧЪЭШЪЭЬЭЬЭЬ
ЭШЪЭЬЭЬШJШ	JЪЬШJШЧJЪЭЬШЧЧJШ	JЪЭЬШЧJШJШJШ ЧЪЭЬШKЪЭЬЭШ
KЪЬ)Ш)ЧЧ ЕЧ    x  .  