I've recently been working on a fuzzy search and have achived it with a keywords table like this
create table keywords(
unique_id int(11) not null auto_increment primary key,
keyword varchar(255) not null,
a int(2) not null default 0,
b int(2) not null default 0,
c int(2) not null default 0,
d int(2) not null default 0,
e int(2) not null default 0,
f int(2) not null default 0,
...
etc
...
z int(2) not null default 0,
0 int(2) not null default 0,
1 int(2) not null default 0,
...
etc
...
9 int(2) not null default 0);
and then when I insert into the table I also insert the number of occurences for each character (no special characters allowed).
Then in searching I can also search on the presence of letters pull out the results and then score each result on the presence of letters, the order of the letters from the start of the word and from the end of the word. There are also some phonetic functions such as metaphone and soundex that my search uses.
HTH
Rob