how can i separate words stuck together ?

Question

I have a lot of files which are named poorly

videoofmegoingtoschool.avi

is there a library or some algorithm out there that will separate it properly ?

video of me going to school.avi

Answer 1

I suspect not. It's even an interesting problem to solve, because you must determine the most 'likely' way to split, and splitting at certain points will affect future splits. A fun project for someone in their spare time, but in the real world, you'll need to do it manually :)

Answer 2

I don't think there's anything out there. I could envision a program that uses a dictionary of words and selects the shortest word that matches left to right and then if it cannot find a second word it fails back to search for the next largest word and so on. (backtracking if necessary) However this could come up with false positives and negatives. Sounds like a fun problem to tackle!

Answer 3

assuming you have a dictionary, and t(str) means that str is a valid word or group of words,
t(str) = sum_over_i(t(str[0,i]) && t(str[i+1, length])
that is, to check if a groupofwords forms a valid group-of-words, add a space after the first letter and see if you can still form words with both halves; if that doesn't work, try after the second letter, then the third...

with dynamic programming, this can be done in O(n^2) time!

[Edit] People don't like my answer. Perhaps some pseudo-code.

function IsValidString(x)
    if(x is one letter, not 'a' or 'i')
        return false
    if(x is a dictionary word)
        return true
    for i from 0 to x.length-2
        if( IsValidString(x[0,i]) and IsValidString(x[i+1, x.length-1]) )
            return true
    return false

Here, IsValidString returns true if there is a way to break up the string into individual, valid words, and false otherwise. It is not hard to see how you could keep track of which values of i (space placement) made the string valid.

Answer 4

This has been discussed several times before here on SO, unfortunately I can only find one link now.

EDIT - More Links:

• How to sort all possible words out of a string?
• How can I split multiple joined words? (this one is a fun read)

Answer 5

In Linux you may have: /usr/share/dict/american-english

---

You can try creating a word 1 letter at a time (from the left), then seeing if it exists as a whole in that dict file. Then save that token as a separate word.