Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

How do I separate words in a string?

In the following I have a random sample of words in a string extracted from text file with over a million words.

Here's the string: "intervene Pockets Jerusalemand tissues powerful days gadgets rate invention heated Stewartis find communal working lots internal They caused noise offer goand big jumps lose galaxies All Mall birth child world spin killed produced great center Dont pretend Africa solution times cursor good night professional problem refugees talk"

As you can see, the third word is "Jerusalemand." My goal is to separate "Jerusalem" and "and", and do the same thing for any other words that are stuck together.

Only thing that I could think of as of now is to compare every word in the string to a dictionary (SCOWL perhaps?), and if a segment of the word matches a word in the dictionary, I'll have to split the words to make them independent.

As an example, for "Jerusalemand" I'll loop through every character until a match is found in the dictionary for "Jerusalem," then I can separate that from "and," in turn completing the separation.

Shouldn't there be a better way to do this?

share|improve this question
    
Yes Google has solved this problem, as have many people before them :-) –  Jarrod Roberson Jul 12 '12 at 5:25
2  
Did you check any online information on how to solve this problem before asking? Like for example en.wikipedia.org/wiki/Word_segmentation? –  James Youngman Jul 12 '12 at 6:58
    
I see, great link :) I can see that this problem falls under the topic of natural language processing. The page describes general approaches to this problem, one is to analyze the collected large corpus of text manually and the other is to use machine learning. Certainly the latter sounds less time consuming given that the text contains about 2.1 million words. I shall look into these, thank you! –  ji. Jul 15 '12 at 18:04

3 Answers 3

Solutions to this problem are often ambiguous, and it's sometimes difficult to decide an optimum solution, even for a human.

If you need only a single solution where all words exist in a dictionary, then a naive approach will fail as soon as you encounter a word which prefix is also a valid dictionary entry.

For example, if your input string was:

tryingtomessitup

Unless you backtrack, your algorithm would probably come up with:

try in gtomessitup

instead of

trying to mess it up

Correct solution to this problem needs to be done using dynamic programming, or even a brute force recursive algorithm which can decide if a prefix indeed leads to the optimal solution.

A DP example is mentioned in this StackOverflow thread. This answer explains it even more thoroughly (and leads to this article: Splitting words joined into a single string (compound-splitter)).

share|improve this answer

I can't think of any sensible alternatives to the general approach you describe. You're probably going to want to focus your attention on exactly what steps you're going to use to (try to) transform a potential word into one or more verified words.

One thing you could definitely do to speed things up is to check the whole word first, and only check substrings if that lookup fails. This assumes that most potential words are valid words, as appears to be the case in your example.

Some things to consider, in no particular order:

  1. Will there ever be more than 2 words jammed together?
  2. Make sure your dictionary lookup is fast!
  3. A capital letter in the middle of the word could be a good indication of where to start trying to split a word.
  4. Is a split only valid if both the parts are valid words?
  5. What do you want to do if there's a potential word which you can't split into 2 (or more) valid words?
  6. If you really care about efficiency, you may find it's faster to try splitting potential words in half first, rather than starting with the first character and going from there. Valid splits are going to tend to be near the middle of potential words, rather than at the beginning or end. This would make the code responsible for trying all the potential splits a bit more complex though.
share|improve this answer
    
#6a:look for common words jammed onto less common words:a, an, and, the, is... Also what about misspelled words (dont) in the example. –  mhoran_psprep Jul 12 '12 at 11:13

Bootheel.

This a solved problem in the sense that it's not hard to find a dictionary, and iterating over all the words in your list, checking to see if it is in the dictionary, and if not splitting the word into pieces and seeing if the pieces make up words isn't difficult.

But that's it, most people don't have cause to check a million words to see if a couple if them have been combined.

share|improve this answer
3  
And to add to that, how do you expect to deal with words like "Sunderland"? Sunder is a word, land is a word, so is sunderland. –  Ian Jul 12 '12 at 4:40
    
@Ian, In order to solve this problem with less errors like one you said, one must develop some AI to understand the meaning of the sentence. As you said it is hard to work with natural language, even people sometimes misunderstand words. –  Mert Jul 12 '12 at 7:14
    
@Ian - good point. Grammer helps, but as natural language has been the first frontier of AI since before AI was a TLA, and is still not fully solved, I doubt the OP will achive it any time soon. –  mattnz Jul 12 '12 at 8:45
2  
AI to understand the meaning would never work with the example given. –  mhoran_psprep Jul 12 '12 at 11:14
    
AI on the given example would reply with a message stating it's OK to come down now the fleshies have gotten their machines good enough to run the place. –  Stijn Sanders Jul 12 '12 at 19:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.