Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

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


Comment on Re: Help Needed for Spellcheck
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://544002]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (17)
As of 2015-07-01 15:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (6 votes), past polls