4
\$\begingroup\$

I wrote the following piece of Python as a part of a larger system. Profiling reveals that a large amount of time is spent in DocumentFeature.from_string. So far I've tried compiling the unmodified code with Cython and got a 33% improvement in running time. Any suggestions as to how this code can be improved further are greatly appreciated.

Here's the code and the unit tests I've been using.

import logging
from operator import itemgetter
from functools import total_ordering
from unittest import TestCase
import nose

class DocumentFeature(object):
    def __init__(self, type, tokens):
        self.type = type
        self.tokens = tokens

    @classmethod
    def from_string(cls, string):
        """
        Takes a string representing a DocumentFeature and creates and object out of it. String format is
        "word/POS" or "word1/PoS1 word2/PoS2",... The type of the feature will be inferred from the length and
        PoS tags of the input string. 

        :type string: str
        """
        try:
            token_count = string.count('_') + 1
            pos_count = string.count('/')
            if token_count != pos_count:
                return DocumentFeature('EMPTY', tuple())

            tokens = string.strip().split('_')
            if len(tokens) > 3:
                raise ValueError('Document feature %s is too long' % string)
            bits = [x.split('/') for x in tokens]
            if not all(map(itemgetter(0), bits)):
                # ignore tokens with no text
                return DocumentFeature('EMPTY', tuple())
            tokens = tuple(Token(word, pos) for (word, pos) in bits)

            if len(tokens) == 1:
                t = '1-GRAM'
            elif ''.join([t.pos for t in tokens]) == 'NVN':
                t = 'SVO'
            elif ''.join([t.pos for t in tokens]) == 'JN':
                t = 'AN'
            elif ''.join([t.pos for t in tokens]) == 'VN':
                t = 'VO'
            elif ''.join([t.pos for t in tokens]) == 'NN':
                t = 'NN'
            elif len(tokens) == 2:
                t = '2-GRAM'
            elif len(tokens) == 3:
                t = '3-GRAM'
            else:
                t = 'EMPTY'
        except:
            logging.error('Cannot create token out of string %s', string)
            raise

        return DocumentFeature(t, tokens)

    def __eq__(self, other):
        return (isinstance(other, self.__class__)
                and self.__dict__ == other.__dict__)
    # other irrelevant methods removed

@total_ordering
class Token(object):
    def __init__(self, text, pos, index=0):
        self.text = text
        self.pos = pos
        self.index = index

    def __str__(self):
        return '{}/{}'.format(self.text, self.pos) if self.pos else self.text

    def __repr__(self):
        return self.__str__()

    def __eq__(self, other):
        return (not self < other) and (not other < self)

    def __lt__(self, other):
        return (self.text, self.pos) < (other.text, other.pos)

    def __hash__(self):
        return hash((self.text, self.pos))

class Test_tokenizer(TestCase):
    def test_document_feature_from_string(self):
        x = DocumentFeature.from_string('big/J_cat/N')
        y = DocumentFeature('AN', (Token('big', 'J'), Token('cat', 'N')))
        self.assertEqual(y, x)

        self.assertEqual(
            DocumentFeature('1-GRAM', (Token('cat', 'N'), )),
            DocumentFeature.from_string(' cat/N ')
        )

        self.assertEqual(
            DocumentFeature('VO', (Token('chase', 'V'), Token('cat', 'N'))),
            DocumentFeature.from_string('chase/V_cat/N')
        )

        self.assertEqual(
            DocumentFeature('NN', (Token('dog', 'N'), Token('cat', 'N'))),
            DocumentFeature.from_string('dog/N_cat/N')
        )

        self.assertEqual(
            DocumentFeature('3-GRAM', (Token('dog', 'V'), Token('chase', 'V'), Token('cat', 'V'))),
            DocumentFeature.from_string('dog/V_chase/V_cat/V')
        )

        self.assertEqual(
            DocumentFeature('2-GRAM', (Token('chase', 'V'), Token('cat', 'V'))),
            DocumentFeature.from_string('chase/V_cat/V')
        )

        self.assertEqual(
            DocumentFeature('SVO', (Token('dog', 'N'), Token('chase', 'V'), Token('cat', 'N'))),
            DocumentFeature.from_string('dog/N_chase/V_cat/N')
        )

        for invalid_string in ['a\/s/N', 'l\/h/N_clinton\/south/N', 'l\/h//N_clinton\/south/N',
                               'l//fasdlj/fasd/dfs/sdf', 'l//fasdlj/fasd/dfs\_/sdf', 'dfs\_/sdf',
                               'dfs\_/fadslk_/sdf', '/_dfs\_/sdf', '_/_/', '_///f_/', 'drop_bomb',
                               'drop/V_bomb', '/V_/N', 'cat']:
            self.assertEqual(
                DocumentFeature('EMPTY', tuple()),
                DocumentFeature.from_string(invalid_string)
            )

if __name__ == '__main__':
    nose.core.runmodule()
\$\endgroup\$
4
+100
\$\begingroup\$

By parsing the string using a regular expression, I get a 20% performance increase over your original code.

from itertools import izip_longest
import re

class DocumentFeature(object):
    def __init__(self, type, tokens):
        self.type = type
        self.tokens = tokens

    _TYPES = dict([
        ('NVN', 'SVO'), ('JN', 'AN'), ('VN', 'VO'), ('NN', 'NN')
    ])
    _TOKEN_RE = re.compile(r'([^/_]+)/([NVJ])(?:_|$)')

    @classmethod
    def from_string(cls, string):
        try:
            match = cls._TOKEN_RE.split(string, 3)
            type = ''.join(match[2::3])
            match = iter(match)
            tokens = []
            for (junk, word, pos) in izip_longest(match, match, match):
                if junk:        # Either too many tokens, or invalid token
                    raise ValueError(junk)
                if not word:
                    break
                tokens.append(Token(word, pos))
            type = cls._TYPES.get(type,
                ('EMPTY', '1-GRAM', '2-GRAM', '3-GRAM')[len(tokens)])
            return DocumentFeature(type, tuple(tokens))
        except:
            raise
\$\endgroup\$
  • \$\begingroup\$ This is indeed faster, thank you. One minor point though: the regex is assuming the thing following the forward slash can only have three values [NVJ], whereas my original code doesn't. You couldn't have known that as I didn't make it explicit and the unit tests I provided do not cover any other cases. \$\endgroup\$ – mbatchkarov Jan 7 '14 at 16:17
  • \$\begingroup\$ Your observation is correct. ([^/_]+)/([^/_]+)(?:_|$) would be closer in spirit to the original, but I chose something more strict since the original was excessively permissive. Feel free to tweak the regex to suit your needs. \$\endgroup\$ – 200_success Jan 7 '14 at 17:15
4
\$\begingroup\$

I find your error handling is a bit counterintuitive: if the input string is invalid, you return an "empty" DocumentFeature, but if there are too many tokens, it raises an exception. I would raise exceptions in both cases, and let the caller decide what to do.

I think that you're being too pessimistic in validating your inputs: the validation repeats some of the real work that would be done anyway. Furthermore, counting slashes and underscores is insufficient validation — for example, "word1_word2//" passes the initial validation, only to fail at tuple(Token(word, pos) for (word, pos) in bits). Instead, I would suggest validating as you perform the transformations.

_TYPES = dict([
    ('NVN', 'SVO'), ('JN', 'AN'), ('VN', 'VO'), ('NN', 'NN')
])

@classmethod
def from_string(cls, string):
    """
    Takes a string representing a DocumentFeature and creates and object out of it. String format is
    "word/PoS" or "word1/PoS1_word2/PoS2",... The type of the feature will be inferred from the length and
    PoS tags of the input string. 

    :type string: str
    """
    try:
        tokens = string.strip().split('_')
        if len(tokens) > 3:
            raise ValueError('Document feature %s is too long' % string)

        tokens = [token.split('/') for token in tokens]

        # Check for too many slashes, too few slashes, or empty words
        if not all(map(lambda token: len(token) == 2 and token[0], tokens)):
            raise ValueError('Invalid document feature %s' % string)

        tokens = tuple(Token(word, pos) for (word, pos) in tokens)

        type = cls._TYPES.get(''.join([t.pos for t in tokens]),
            ('EMPTY', '1-GRAM', '2-GRAM', '3-GRAM')[len(tokens)])
    except:
        logging.error('Cannot create token out of string %s', string)
        raise

    return DocumentFeature(type, tokens)
\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback, especially for spotting the problem with counting underscores and slashes. You corrected implementation is also ~5% faster on my machine. Regarding your first point, invalid input strings are due to data formatting. Since I'm dealing with natural language, there will inevitably be a small number of such tokens. There's nothing that can be done about that and I don't consider this to be exceptional. However, having more than 3 tokens violates a hard constraint and indicates a problem with my own code. \$\endgroup\$ – mbatchkarov Jan 3 '14 at 12:01

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.