### Re: Help Needed for Spellcheck

by davidj (Priest)
 on Apr 18, 2006 at 05:48 UTC ( #544002=note: print w/replies, xml ) Need Help??

in reply to Help Needed for Spellcheck

srik4u,
the solution I was given in a recent post of mine, find all paths of length n in a graph, might offer a good place to start. Using the idea of a trie, you could recursively build the phrases as you go along. I am not good at writing recursive functions, but the idea is basically this: recursively iterate over the string and pop off substrings that match whole words. The phrase fails when you have a substring that is not a partial word. You have a valid phrase when you have reached the end of the string without failing on a substring. A function might look something like this:
```sub check_string(\$word) {
foreach \$chr (split //, \$word) {
\$check .= \$chr;
if whole_word(\$check) {
push @phrase, \$check;
\$rem = substr(\$word, length(\$check), length(\$word) - lengt
+h(\$check));
check_string(\$remainder);
} elsif not_valid(\$check) {
@phrase = ();
return;
}
}

print "@phrase\n";
@phrase = ();
}
as I say I am not good at recursive functions, so the above is merely a starting place. (getting the recursive element to work always befuddles me). More visually, this is what would happen with the string "mycarrot"

```m    valid partial string, so continue
my   found a whole word, so push and recurse
@phrase = ("my")

c    valid partial string, so continue
ca   valid partial string, so continue
car  found a whole word, so push and recurse
@phrase = ("my", "car")

r    valid partial string, so continue
ro   valid partial string, so continue
rot  found a whole word, so push
at end of string, so print valid phrase
@phrase = ("my", "car", "rot")

(backup to last iteration and continue)
@phrase = ("my")

carr   valid partial string, so continue
carro  valid partial string, so continue
carrot found a whole so push
at end of string, so print valid phrase
("my", "carrot")

back to last iteration and continue)
@phrase = ()

myc   invalid partial string, so quit
@phrase = ()
In the scary place I call my mind, this makes sense. I hope it makes sense to you. Maybe if someone else understands what I am trying to explain, they might be able to clarify it better than I.

davidj

Create A New User
Node Status?
node history
Node Type: note [id://544002]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2017-08-22 07:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (331 votes). Check out past polls.

Notices?