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?

  • Yes Google has solved this problem, as have many people before them :-) – user7519 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 Park Jul 15 '12 at 18:04

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:


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)).


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.
  • #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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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