7
\$\begingroup\$

I decided to try out Python (3.x) two or so weeks ago, and this is my first real script using it. The program I've written below is slow, clunky, inefficient, inaccurate, and probably poorly coded! But it produces what I want most of the time, and it was really just a project to become accustomed to different Python techniques.

What it should do is, recieve a string, one that looks like a tag from a social media site (#socialmedia, #20000leaguesunder, etc.), and then based on a dictionary, split the string into logical words.

So "#volunteeringtoday" becomes "volunteering today" and so on.

I understand my algorithm is poor, so any help with the actual Python and formatting would be preferred.

import re

class Splitter():

    input = ''
    clean = ''
    words = []


    def __init__(self, string):
        '''
        Set the input string
        '''
        self.input = string

    def split(self):
        '''
        Split the input string. Get the clean version then start the separation loop.
        '''
        self.clean = self.cleanString(self.input)
        return self.separateString(self.clean)

    def separateString(self, inp):
        '''
        Separate the string input. Break apart and look for matches in a dictionary.
        '''
        # Index each character in the input string
        for ind in range(len(inp)):
        # Build a segment
        built = self.partition(inp, ind)
        #print('"'+built+'"') # Add for details
        # If only one letter remains, steal a letter from the previous match
        if len(built) == 1:
            built = self.words[-1][-1] + self.lastLarge
            self.words[-1] = self.words[-1][0:-1]
            return self.separateString(built)
        # Check if segment ends with a digit. Separate it if it does.
        if re.match('\d+$', built):
            built = re.sub("([^\d])\d", "", built)
            self.words.append(built)
            return self.separateString(inp.replace(built, '', 1))
        # It does not end with a digit
        else:
            # Iterate over each line in the dictionary
            for word in open('word.txt', 'r'):
                if self.cleanString(word) == built:
                    self.words.append(built)
                    # Check if list of separations joined together is equal to original
                    if ''.join(self.words) == self.clean:
                        return ' '.join(self.words)
                    else:
                        # Loop back through to separate more
                        self.lastLarge = inp.replace(built, '', 1)
                        return self.separateString(inp.replace(built, '', 1))

    def partition(self, value, index):
        '''
        Break apart string. Length from right
        '''
        return value[0:len(value) - index]

    def cleanString(self, string):
        '''
        Remove all non-alphabetic and non-digit characters.
        '''
        return re.sub("[^\d[a-z]]*", "", string.lower().strip())

And then you can sample it with something such as:

splitter = Splitter(input('Hashtag: '))
print('\nFinal:',splitter.split())

word.txt is a text file with roughly 60k words. One on each line. The list can be found here.

Any tips on making it more professional?

\$\endgroup\$
6
\$\begingroup\$

Bugs

Try some simple test cases to find bugs:

def test_split(s):
    splitter = Splitter(s)
    print(s, "⇒", splitter.split(s))

test_split('[')        #no word, just punctuation
test_split('cat')
test_split('cattree')
test_split('cathode')  #one word, not cat-hode
test_split('muscat')   #one word, not mus-cat
test_split('onetwothree')
test_split('one1two2') #multiple numbers
test_split('2014')     #multi-digit number
test_split('xyzzy')    #unknown word
test_split('cathodemuscat') #cathode-muscat, not cathodemus-cat or cat-hodemuscat

These reveal some bugs:

  1. Only the first call to split works (even on separate instances). This is because Splitter.words is shared between instances but is modified by separateWords, and words remain in it after each call.

  2. Unknown words are omitted. What should separateString return when it doesn't recognize a word? The whole input?

  3. Words containing numbers are not handled in any reasonable way. Perhaps any sequence of digits should be parsed as a word?

  4. Brackets are treated as letters. The regex in cleanString should be "[^\da-z]*", not "[^\d[a-z]]*", unless you want to keep square brackets.

When modifying separateString, be careful with the case where the whole input as one word — it's easy to break this or have it only work by accident.

The last test case ('cathodemuscat') is particularly hard. Hint: split the string, recurse on both halves, and check that both halves succeed.

Architecture and simplification

The Splitter class does nothing useful. Its methods should be top-level functions instead. (This contributes to the Splitter.words bug.)

It's not a good idea for separateString to communicate with its recursive call by modifying input and words. This is bug-prone (it contributes to the Splitter.words bug) and hard to read. Instead, separateString should pass the appropriate substring as an argument to the recursive call, and append its word to the result. It may look something like this:

return separateString(inp[:-ind]) + [word]

Callers probably want a list of words, rather than a space-separated string, so separateString should return the list without joining.

It would be clearer (and faster) to load the dictionary once, as a set, rather than reading it repeatedly:

dictionary = set([cleanString(w) for w in open('word.txt')])

partition is unnecessary. Just write inp[len(inp)-ind:], or even inp[-ind:] if ind is never 0. (Negative indexes count from the end.)

\$\endgroup\$
  • \$\begingroup\$ Good stuff, I appreciate it. I think i started to confuse myself by jumping into a project like this, and that led to some bad practices like you pointed out! \$\endgroup\$ – Alex L May 19 '14 at 3:00
0
\$\begingroup\$

You know what you're effectively building is one large regular expression containing all the possible words you want to consider. You might want to either try to explicitly build one such regular expression, then see what you find, remove the part you found from the beginning, and repeat with the rest (it would still be interesting because you'd have to keep track of different splits, some of which may become a dead end, e.g. "hereiam" might first be split into "he" and then "reiam" which doesn't make sense so you'd have to back track to use "here"). Even though that might actually be expressible in RegEx as well. Or take a more low-level approach, read up on "finite state automata for regular expressions" and build something specialized yourself.

Concerning your code, I wouldn't read word.txt in separateString, but only once and then save it with the object. You might to extract that part so that only when you first call separateString the file gets read, but on the second time, you use a reference to the read data.

\$\endgroup\$
  • \$\begingroup\$ I'm not sure I understand what you mean by "explicitly build one such regular expression" that contains "all the possible words you want to consider"? Do you know any code which relates to this to show what you mean? \$\endgroup\$ – Alex L May 18 '14 at 22:00
  • \$\begingroup\$ something like /^(apple|banana)/ with many more words \$\endgroup\$ – Nicolas78 May 18 '14 at 22:20
  • \$\begingroup\$ What kind of performance issues would I face by cycling through a regex with a thousands words hundreds of times? I'm still not sure what you're thinking with this, but I'll go research a little on large regexs in this context. \$\endgroup\$ – Alex L May 18 '14 at 22:28
  • \$\begingroup\$ Regular expressions are a highly researched topic and can be matched very efficiently. It's going to be way faster than any approach that involves matching the first keyword, then the next, ... because the code for matching the expression will go through your input only once (if that sounds like magic, do check out the finite state stuff I mentioned above). Be sure to compile and save your giant expression though since constructing it may take a while indeed (but only once) \$\endgroup\$ – Nicolas78 May 18 '14 at 23:05
  • \$\begingroup\$ PS You're absolutely right not to take my word for it. Create that giant string, turn it into a regex, and compare runtimes, particularly how they grow in relation to the number of dictionary items :) \$\endgroup\$ – Nicolas78 May 18 '14 at 23:07

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.