Spell Distance

This is G o o g l e's cache of http://home.earthlink.net/~neilbawd/spdist.html.
G o o g l e's cache is the snapshot that we took of the page as we crawled the web.
The page may have changed since that time. Click here for the current page without highlighting.
To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:2IlVt5un02AC:home.earthlink.net/~neilbawd/spdist.html+&hl=en&ie=UTF-8

Google is not affiliated with the authors of this page nor responsible for its content.

Spell Distance

Neil Bawd 2000-07-21

Kernighan and Pike, The Unix Programming Environment, (1984) pp 208--214, give a name-correcting file lookup. It uses a function like the following SPELL-DISTANCE. The K&P definition uses C-style strings, so SPELL-DISTANCE had to be written from scratch.

This is helpful with "word unknown" error. It catches the most common typing goofs.

TEXT

Needed from Tool Belt

THIRD 3DUP 3DROP

Test Requires Pattern Expansion

SPELL-DISTANCE ( str1 len1 str2 len2 -- {0...3} ): Returns distance between two names.

Very rough spelling metric.

0 if the strings are identical.
1 if two characters are transposed.
2 if one character different, added, or deleted.
3 otherwise.

Program Text 1 : Letter-Match ( str1 len str2 -- str' len' str2' ) >R BEGIN DUP WHILE OVER C@ R@ C@ = WHILE 1 /STRING R> 1+ >R REPEAT THEN R> ; : Letter-Switch ( str1 len str2 -- flag ) THIRD C@ OVER 1+ C@ = NOT IF 3DROP FALSE EXIT THEN THIRD 1+ C@ OVER C@ = NOT IF 3DROP FALSE EXIT THEN >R 2 /STRING R> 2 + OVER COMPARE 0= ; : Spell-Distance ( str1 len1 str2 len2 -- {0...3} ) ROT SWAP ( str1 str2 len1 len2) \ Save difference in lengths for later. 2DUP - >R ( R: diff) \ Is difference in lengths > 1? R@ ABS 1 > IF R@ DROP 2DROP 2DROP ( ) 3 EXIT THEN MIN SWAP ( str1 len str2) Letter-Match \ Are words equal or a letter inserted/deleted? OVER 0= IF 3DROP R> DUP IF DROP 2 THEN EXIT THEN \ Do the words have the same length? R> DUP 0= IF DROP \ Is the rest of the two words the same? 3DUP >R 1 /STRING R> 1+ OVER COMPARE 0= IF 3DROP 2 EXIT THEN \ Is a letter switched with the next letter? Letter-Switch IF 1 ELSE 3 THEN EXIT THEN \ Is a letter deleted? 0< IF 1+ OVER COMPARE 0= IF 2 ELSE 3 THEN EXIT THEN \ Is a letter inserted? 2>R 1+ 2R> OVER COMPARE 0= IF 2 ELSE 3 THEN ; ($ | CR ." $+0 " S" $1" PAD PLACE PAD COUNT S" $2" SPELL-DISTANCE . | HELLO HELLO HELLO EHLLO HELLO HLELO HELLO HELOL HELLO JELLO HELLO HALLO HELLO HEELO HELLO HELPO HELLO HELLS HELLO ELLO HELLO HLLO HELLO HELO HELLO HELL ELLO HELLO HLLO HELLO HELO HELLO HELL HELLO HELLO HELPS $) ..

Go back to Neil Bawd's home page.