Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
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 romping around the Monastery: (18)
As of 2014-07-14 13:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (259 votes), past polls