Re: Sorting Algorythms

["Bill Buckels" <bbuckels@mts.net>]

"Bill Buckels" <bbuckels@mts.net> wrote:

> http://www.filegate.net/pdn/pdncee/Metasim.zip

> Lawrence Philips' Metaphone Algorithm (used by MetaSim) is an algorithm 
> which returns the rough approximation of how an English word sounds.

Unfortunately I never "dabbled in" and programmed a sorting "algorythm" 
while "playing" on my Apple II computer. I am only 60 years old so sorting 
algorithms were already well understood and available by the time I wrote my 
first Apple II computer program, which was for money in those days... it 
would have been pretty hard to find anyone who would have paid me much to 
write sorting algorithms or much of anything trivial anyway.

This thing I did with Metaphone happened a little later on, when I really 
programmed and could hold 5,000 to 15,000 lines of code in my head at 
once... I sure couldn't do that today. This one I wrote for fun... but like 
everything else I am sure it was already well-understood by the time I got 
to it...

About The Soundex Algorithm
---------------------------

Soundex is an algorithm developed and patented by Margaret Odell and Robert 
Russell in the early part of this century (U.S. Patent 1,261,167 (1918) and 
1,435,663 (1922)). Don't worry about the patents, they've long since 
expired.

Many articles have been written about it, but one of the best descriptions 
is by Donald Knuth in The Art of Computer Programming, Vol. 3.

Soundex converts a word or name to a code comprised of a letter followed by 
three digits. Some redundancy is taken out of the word (such as stripping 
vowels, consonant doubles, etc.). The first letter is preserved and the code 
is generated from what remains.

About the Extended Soundex Algorithm
------------------------------------

This is a minor change to the basic Soundex algorithm. In this algorithm, 
the first letter is treated like all the rest of the letters (i.e., if it's 
a vowel, it's stripped, if it's part of a consonant double, the second is 
stripped (as in LLAMA), etc.).

This code is purely numeric. This can result in faster database scans to 
pick out like-sounding words or names.

About the Metaphone Algorithm
-----------------------------

Lawrence Philips' Metaphone Algorithm is an algorithm which returns the 
rough approximation of how an English word sounds.

Metaphone originated from Lawrence Philips, an artificial intelligence 
specialist at NAC Reinsurance. There is a write-up on Metaphone in the 
December 1990 issue of Computer Language.

Metaphone does a better job than Soundex and Extended Soundex when it comes 
to representing like-sounding names. Its drawback is that Metaphone is 
comprised purely of letters. In other words, it takes up more storage and, 
in a large database, this can be costly.

Metaphone algorithm as described in Computer Language, volume 7, number
12, December 1990, pp 39-43

The Metaphone Rules
-------------------

Metaphone reduces the alphabet to 16 consonant sounds:

B X S K J T F H L M N P R 0 W Y

That isn't an O but a zero - representing the 'th' sound.

Transformations

Metaphone uses the following transformation rules:

Doubled letters except "c" -> drop 2nd letter. Vowels are only kept
when they are the first letter.

  B -> B   unless at the end of a word after "m" as in "dumb"
  C -> X    (sh) if -cia- or -ch-
       S   if -ci-, -ce- or -cy-
    K   otherwise, including -sch-
  D -> J   if in -dge-, -dgy- or -dgi-
       T   otherwise
  F -> F
  G ->     silent if in -gh- and not at end or before a vowel
           in -gn- or -gned- (also see dge etc. above)
    J   if before i or e or y if not double gg
    K   otherwise
  H ->     silent if after vowel and no vowel follows
       H   otherwise
  J -> J
  K ->     silent if after "c"
       K   otherwise
  L -> L
  M -> M
  N -> N
  P -> F   if before "h"
       P   otherwise
  Q -> K
  R -> R
  S -> X   (sh) if before "h" or in -sio- or -sia-
       S   otherwise
  T -> X   (sh) if -tia- or -tio-
       0   (th) if before "h"
        silent if in -tch-
    T   otherwise
  V -> F
  W ->     silent if not followed by a vowel
       W   if followed by a vowel
  X -> KS
  Y ->     silent if not followed by a vowel
       Y   if followed by a vowel
  Z -> S

  Initial Letter Exceptions

  Initial  kn-, gn- pn, ae- or wr-      -> drop first letter
  Initial  x-                           -> change to "s"
  Initial  wh-                          -> change to "w"