[futurebasic] Re: [FB] Metaphone

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : September 2001 : Group Archive : Group : All Groups

From: Ken Shmidheiser <k.shmidheiser@...>
Date: Tue, 4 Sep 2001 09:31:49 -0400
jonathan, having through our time tour been enlightened to the wisdom
of the ages (well, at least having once read a Mad Magazine) sounds
forth in understanding:

>  > Running the Levensthein distance.
>
>let me guess... this must be a way of calculating how far [quintupled]
>metaphoned 'words' are from each other, in order to say that 'sugar' if
>closer to 'Shmidheiser' than 'gnome', no?

Yes, my prismatic-domed son, there is hope for you.

Our excursion has borne fruitage in your glint of Levenstheinein insight.

I fondly remember how, in group conversation, one know-it-all
bombastically asserted:

"Did you know that 'sugar' is the only word in the English language
where the 'su' is pronounced as 'sh.'"

A shy little girl intently watching the proceedings smiled and quitely asked:

"Are you sure?"

But I digress.

>thanks for the explanations - waiting for the next episode.
>
>:-j

Here, then, my pyramid-tonsorialized leprechaun,  is the promised,
and may I humbly add, long-awaited (at least for 17 minutes) Episode
II...

(Fanfare)

Running the Levensthein distance!

(Which Alain will take and shorten to two lines within 37 minutes)

'-----SHMIDHEISERIZED LEVENSTHEIN DISTANCE IN FB^3 -----

BEGIN GLOBALS
DIM DYNAMIC d(_maxInt, _maxInt) AS INT
DIM gQuit AS BOOLEAN
END GLOBALS

LOCAL FN buildMenus
APPLE MENU "(Demo..."
MENU 1,0,_enable, "File"
MENU 1,1,_disable, "-"
MENU 1,2,_enable, "Quit/Q"
EDIT MENU 2
END FN

LOCAL FN buildWindow
WINDOW-1,"Levenshtein Distance",(0,0)-(300,220),5'_docNoGrow
EDIT = 3
EDIT FIELD -1,"",(20,  35)-(170,  50),_framedNoCr,_leftJust
EDIT FIELD -2,"",(20,  75)-(170,  90),_framedNoCr,_leftJust
EDIT FIELD -3,"",(20, 105)-(280, 155),_statFramed,_leftJust
LONG COLOR 56797,56797,56797,_false
EDIT FIELD -4, "Enter first word:",(20, 20)-(150, 32),_statNoFramed,_leftJust
EDIT FIELD -5,"Enter second word:",(20, 60)-(380, 72),_statNoFramed,_leftJust
BUTTON 1,1,"Compute Levenshtein Distance",(50,180)-(280,203),_push
EDIT FIELD 1
WINDOW 1
END FN

// Get minimum of three values
LOCAL FN Minimum( a AS INT, b AS INT, c AS INT)
DIM mi AS INT
mi = a
IF b < mi THEN mi = b
IF c < mi THEN mi = c
END FN = mi

// Compute Levenshtein Distance
LOCAL FN LD( s AS STR255, t AS STR255 )
DIM LD   AS INT ' result
DIM m    AS INT ' length of t
DIM n    AS INT ' length of s
DIM i    AS INT ' iterates through s
DIM j    AS INT ' iterates through t
DIM s_i  AS STR255 ' ith character of s
DIM t_j  AS STR255 ' jth character of t
DIM cost AS INT ' cost

// Step 1
n = LEN(s)
m = LEN(t)
IF n = 0 THEN LD = m : EXIT FN
IF m = 0 THEN LD = n : EXIT FN

// Step 2
FOR i = 0 TO n
d(i, 0) = i
NEXT i

FOR j = 0 TO m
d(0, j) = j
NEXT j

// Step 3
FOR i = 1 TO n
s_i = MID$( s, i, 1 )
// Step 4
FOR j = 1 TO m
t_j = MID$(t, j, 1)
// Step 5
IF s_i = t_j THEN cost = 0 ELSE cost = 1
// Step 6
d(i, j) = FN Minimum(d(i - 1, j) + 1, d(i, j - 1) ¬
+ 1, d(i - 1, j - 1) + cost)
NEXT j
NEXT i

// Step 7
LD = d( n, m )
KILL DYNAMIC d

END FN = LD

LOCAl FN doLevenshtein
DIM ldSteps  AS INTEGER
DIM test1Str AS STR255
DIM test2Str AS STR255
test1Str = EDIT$(1)
test2Str = EDIT$(2)
  ldSteps = FN LD( test1Str, test2Str )
EDIT$(3) = "It takes a minimum of" + STR$( ldSteps )¬
+ " steps to transform """ + test1Str + """ into """ + test2Str + """
eDIT FIELD 1
END FN

LOCAL FN doDialog
DIM AS INTEGER evnt,id
evnt = DIALOG(0)
id = DIALOG(evnt)
SELECT CASE( evnt )
CASE _wndClose
SELECT( id )
CASE 1 : END
END SELECT
CASE _efTab
SELECT( id )
CASE 1 : EDIT FIELD 2
CASE 2 : EDIT FIELD 1
END SELECT
CASE _btnClick
SELECT( id )
CASE 1 : FN doLevenshtein
END SELECT
END SELECT
END FN

LOCAL FN doMenu
DIM AS INTEGER menuID,itemID
menuID = MENU(_menuID)
itemID = MENU(_itemID)
SELECT CASE( menuID )
CASE _applemenu
SELECT( itemID )
CASE 1
END SELECT
CASE 1
SELECT( itemID )
CASE 2 : END
END SELECT
END SELECT
MENU
END FN

ON DIALOG FN doDialog
ON MENU   FN doMenu

FN buildMenus
FN buildWindow

DO
HANDLEEVENTS
UNTIL gQuit
END

'---------- END OF TOUR ---------