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?
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)).
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:
- Will there ever be more than 2 words jammed together?
- Make sure your dictionary lookup is fast!
- A capital letter in the middle of the word could be a good indication of where to start trying to split a word.
- Is a split only valid if both the parts are valid words?
- What do you want to do if there’s a potential word which you can’t split into 2 (or more) valid words?
- 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.
1