NONE = str(None) def prune_punc(a_toks):
    """Remove tokens representing punctuation from set.

    Args:
      a_toks (iterable): original tokens

    Returns:
      frozenset: tokens without punctuation marks

    """
    return frozenset([tok for tok in a_toks if not _ispunct(tok[-1])]) def score_substitute(a_c1, a_c2):
    """Score substitution of two characters.

    Args:
      a_c1 (str): first word to compare
      a_c2 (str): second word to compare

    Returns:
      int: 2 if the last characters of both words are equal, -3 otherwise

    """
    return 2 if a_c1[-1] == a_c2[-1] else -3 def translate_toks(a_toks, a_translation):
    """Translate tokens and return translated set.

    Args:
      a_toks (iterable): tokens to be translated
      a_translation (dict): - translation dictionary for tokens

    Returns:
      frozenset: translated tokens

    """
    if a_translation is None:
        return a_toks
    ret = set()
    for tok in a_toks:
        for t_tok in a_translation[tok]:
            ret.add(t_tok)
    return frozenset(ret) HEAD = "head"
ADDRESS = "address"
LEMMA = "lemma"
CTAG = "ctag"
FEATS = "feats"
STANDARD_FIELDS = [HEAD, DEPS, WORD, REL, TAG, ADDRESS, LEMMA, CTAG, FEATS]
TOP_TAG_LABEL = 'TOP'
TOP_RELATION_LABEL = 'ROOT'
class DependencyGraph(NLTKDependencyGraph):
    def words(self):
    def subgraphs(self, exclude_root=False):
    def get_dependencies_simple(self, address):
    def address_span(self, start_address):
    def token_span(self, start_address=0):
    def is_valid_parse_tree(self):
    def length(self):
    def annotate(self, iterable, field_name):
    def deannotate(self, field_name):
def transform_line(line):
def number_tokens(dgraph):
def tree2tok(a_tree, a_tree_idx, a_root_idx, a_tk_start=0):
def read_tok_trees(a_lines):
def read_trees(a_lines): def generate_subtrees_from_forest(forest):
    """yields all subtress of a forest of trees"""
    for tree in forest:
        for subtree in tree.subtrees():
            yield subtree DEFAULT_SEGMENT = "HS" DEPENDENCY = 1 class DiscourseSegment(object):
    """Class representing discourse segment.

    Attributes:
      name (str): name of this segment
      leaves (list): words or other segments inside of this unit

    """

    def __init__(self, a_name="", a_leaves=[]):
        """Class constructor.

        Args:
          a_name (str): name of discourse segment
          a_leaves (list): segment's child nodes (either words or other
            segments)

        """
        self.name = a_name
        self.leaves = a_leaves
        self.leaves.sort(key=lambda el: el[0] if el else -1)

    def get_end(self):
        """Obtain position of the last token in the list of leaves.

        Returns:
          int: position of the last token in the list of leaves

        """
        if not self.leaves:
            return -1
        else:
            last_leaf = self.leaves[-1]
            if isinstance(last_leaf[-1], DiscourseSegment):
                return last_leaf[-1].get_end()
            else:
                return last_leaf[0]

    def insort(self, a_leaf):
        """Insert leaf in the list of leaves according to its position.

        Args:
          a_leaf (dict): leaf to be inserted

        Returns:
          void:

        """
        ipos = bisect_right(self.leaves, a_leaf)
        inserted = False
        prev_pos = ipos - 1
        if prev_pos >= 0:
            prev_leaf = self.leaves[prev_pos]
            if isinstance(prev_leaf[-1], DiscourseSegment) and \
                    prev_leaf[-1].get_end() > a_leaf[0]:
                prev_leaf[-1].insort(a_leaf)
                inserted = True
        if not inserted:
            self.leaves.insert(ipos, a_leaf)

    def __len__(self):
        """Return number of elements in given segment.

        Returns:
          int:number of elements in segment

        """
        return len(self.leaves)

    def __nonzero__(self):
        """Return True if the given segment is not empty.

        Returns:
          bool: True if segment is not empty

        """
        return bool(self.leaves)

    def __unicode__(self):
        """Return unicode representation of given segment.

        Returns:
          unicode: unicode string representing this object

        """
        ret = u"(" + unicode(self.name)
        for t in self.leaves:
            ret += u' ' + unicode(t[-1])
        ret += u" )"
        return ret

    def __str__(self):
        """Return utf-8 string representation of given segment.

        Returns:
          str: utf-8 string representing this object

        """
        return self.__unicode__().encode(ENCODING)

    def __repr__(self):
        """Return internal representation of given segment.

        Returns:
          str: internal representation of this segment

        """
        ret = '<' + self.__class__.__name__ + " at " + str(hex(id(self)))
        ret += u" name=" + repr(self.name)
        ret += u" leaves=" + repr(self.leaves) + ">"
        return ret class TreeSegmenter(object):
    """Class for converting parse trees to discourse segments.

    Attributes:
      decfunc: decision function
      segment: public function for doing segmentation
      type: type of trees to be processed

    """

    def __init__(self, a_decfunc=None, a_type=DEPENDENCY):
        """
        Class constructor.
        """
        # set default decision function, if none was specified
        self.decfunc = a_decfunc

        # set default segmentation function, if none was specified
        if a_type == DEPENDENCY:
            self.segment = self._dg_segment
            if self.decfunc is None:
                self.decfunc = self._dg_decfunc
        elif a_type == CONSTITUENCY:
            self.segment = self._cnst_segment
            if self.decfunc is None:
                self.decfunc = self._cnst_decfunc
        else:
            raise RuntimeError("Invalid tree type specified for tree"
                               " segmenter: '{:s}'".format(a_type))

    def _dg_segment(self, a_tree, a_predict=None,
                    a_root_idx=0, a_children=[],
                    a_word_access=lambda x: x, a_strategy=GREEDY):
        """Extract discourse segments from dependency parse trees.

        Args:
          a_tree (nltk.parse.dependencygraph): parse tree which should be
            processed
          a_predict (lambda): prediction function
          a_root_idx (int): index of the root node in the list of tree nodes
          a_children (list[int]): index of the child nodes
          a_word_access (lambda): a function for accessing the token string for
                         more complex, structured tokens
          a_strategy (int): flag for handling missing and non-projective edges
            (GREEDY means that only adjacent descendants of the root node will
            be put into a segment, if the root initiates one; GENEROUS means
            that all words between the root and its right- and left-most
            dependencies will be put into one segment disregarding the actual
            structure of the dependency tree)

        Returns:
          list: discourse segments

        """
        a_ret = []
        dec = None             # decision
        if a_predict is None:
            a_predict = self.decfunc
        if a_children:
            children = a_children
        elif a_root_idx is None:
            children = []
        else:
            children = [a_root_idx]

        while children:
            ipos = children.pop(0)
            inode = a_tree.nodes[ipos]
            word = a_word_access(inode[WORD]) if WORD in inode else ""
            deps = a_tree.get_dependencies_simple(ipos)
            dec = a_predict(inode, a_tree)
            if dec is None or dec == NO_MATCH_STRING:
                # if the node did not start any new segment on its own, then we
                # add it to the top-most segment in the list
                if word is not None:
                    a_ret.append((ipos, word))
                children[:0] = deps
            else:
                # recurse
                leaves = self.segment(
                    a_tree, a_predict=a_predict, a_root_idx=None,
                    a_children=deps, a_word_access=a_word_access,
                    a_strategy=a_strategy)
                dseg = DiscourseSegment(a_name=dec, a_leaves=leaves)

                if word is not None:
                    dseg.insort((ipos, word))
                # if strategy is GREEDY, only leave nodes which are adjacent to
                # the root
                if a_strategy == GREEDY:
                    outleaves = self._extract_nonadjacent(dseg, ipos)
                    a_ret += outleaves
                a_ret.append((dseg.leaves[0][0] if dseg.leaves else -1, dseg))
        # for GENEROUS strategy, do some post-processing
        a_ret.sort(key=lambda el: el[0])
        if a_strategy == GENEROUS:
            a_ret[:] = self._unite_nonadjacent(a_ret)
        return a_ret

    def _dg_decfunc(self, a_node, a_tree):
        """Make a prediction whether given node initiates a segment.

        Args:
          a_node (dict): parse node to be analyzed
          a_tree (nltk.parse.dependencygraph): tree of analyzed node

        Returns:
          str or None: name of discourse segment or None

        """
        chnode = None
        chtag = ""
        irel = a_node.get(REL, "UNK")
        ideps = a_node.get(DEPS, [])
        if irel == "TOP":
            return "HS"
        else:
            for chpos in ideps:
                chnode = a_tree.nodelist[chpos]
                chtag = chnode.get(TAG, "UNK")
                if chtag == "KOUS":
                    return "SUB"
                elif chtag == "PRELS":
                    return "ARR"
            return None

    def _cnst_segment(self, a_tree, a_ret, a_predict=None, a_start=0):
        """Extract discourse segments from constitutency parse trees.

        Args:
          a_tree (nltk.parse.dependencygraph): parse tree which should
            be processed
          a_ret (list): target list which should be populated with segments
          a_predict (lambda): prediction function
          a_start (int): starting index of tokens

        Returns:
          list: discourse segments

        """
        if a_predict is None:   # find appropriate decision function
            a_predict = self.decfunc

        if isinstance(a_tree, basestring):
            a_ret.append((a_start, a_tree))
            a_start += 1
        else:
            dec = a_predict(a_tree)  # make decision about the tree
            if dec is None:
                for ch in a_tree:
                    a_start = self.segment(ch, a_ret, a_predict, a_start)
            else:
                # create a new segment
                dseg = DiscourseSegment(a_name=dec, a_leaves=[])
                # add tree leaves to the segment
                for ch in a_tree:
                    a_start = self.segment(ch, dseg.leaves, a_predict, a_start)
                # append the new segment to the tree
                if dseg.leaves and len(dseg.leaves[0]):
                    a_ret.append((dseg.leaves[0][0], dseg))
        return a_start

    def _cnst_decfunc(self, a_tree):
        """Make a prediction whether given parse tree initiates a segment.

        Args:
         a_tree (nltk.parse.dependencygraph):- tree of analyzed node

        Returns:
          str or None: name of discourse segment or None

        """
        if a_tree.label() == "TOP":
            return "HS"
        else:
            return None

    def _extract_nonadjacent(self, a_seg, a_root_pos):
        """Remove from segment nodes which are not adjacent to root.

        Args:
          a_seg (list): terminals to be modified
          a_root_idx (int): index of the root node

        Return:
          list: non-adjacent words (discourse segment will also be
            modified)

        """
        temp = []
        adjacent = []
        non_adjacent = []
        prev_pos = -2
        root_seen = False
        for cur_pos, cur_node in a_seg.leaves:
            if prev_pos != -2 and prev_pos != cur_pos - 1:
                if root_seen:
                    adjacent += temp
                    root_seen = False
                else:
                    non_adjacent += temp
                del temp[:]
            if cur_pos == a_root_pos or a_root_pos == 0:
                root_seen = True
            if isinstance(cur_node, DiscourseSegment) and cur_node.leaves:
                prev_pos = cur_node.get_end()
            else:
                prev_pos = cur_pos
            temp.append((cur_pos, cur_node))
        if root_seen:
            adjacent += temp
        else:
            non_adjacent += temp
        a_seg.leaves = adjacent
        return non_adjacent

    def _unite_nonadjacent(self, a_word_seg):
        """Add nodes between the discourse segment and its non-projective edges

        Args:
          a_word_seg (list): terminals and segments to be modified

        Returns:
          list: modified word/segment list

        """
        word_seg = []
        right_leaves = []
        cur_node = None
        prev_wseg = nxt_wseg = None
        cur_start = cur_end = wseg_end = -1
        i = 0
        max_i = len(a_word_seg)
        while i < max_i:
            cur_start, cur_node = a_word_seg[i]
            i += 1
            if isinstance(cur_node, DiscourseSegment):
                while word_seg:
                    prev_wseg = word_seg[-1]
                    if isinstance(prev_wseg, DiscourseSegment):
                        wseg_end = word_seg[-1].get_end()
                    else:
                        wseg_end = word_seg[-1][0]
                    if wseg_end > cur_start:
                        cur_node.insort(word_seg.pop())
                    else:
                        break
                cur_end = cur_node.get_end()
                while i < max_i and a_word_seg[i][0] < cur_end:
                    nxt_wseg = a_word_seg[i]
                    if isinstance(nxt_wseg[1], DiscourseSegment):
                        cur_end = max(cur_end, nxt_wseg[1].get_end())
                    right_leaves.append(nxt_wseg)
                    i += 1
                if right_leaves:
                    # right_leaves = self._unite_nonadjacent(right_leaves)
                    # for rl in right_leaves:
                    #     cur_node.insort(rl)
                    cur_node.leaves += right_leaves
                    del right_leaves[:]
                    cur_node.leaves.sort(key=lambda el: el[0])
                    cur_node.leaves[:] = \
                        self._unite_nonadjacent(cur_node.leaves)
            word_seg.append((cur_start, cur_node))
        return word_seg NO_MATCH_STRING = "NONE" GREEDY = 0 def nw_align(s1, s2, insert=lambda c: -2,
             delete=lambda c: -2,
             substitute=lambda c1, c2: 2 if c1 == c2 else -1,
             offset=0, keep_deleted=False):
    """Align two iterables using Needleman-Wunsch algorithm.

    Complexity: :math:`O(nm)` time; :math:`O(nm)` space

    Args:
      s1 (iterable): iterable for alignment
      s2 (iterable): iterable which should be aligned
      insert (lambda): penalty for insertion (default -2)
      delete (lambda): penalty for deletion (default -2)
      substitute (lambda): penalty for substitution (default -1)
      offset (int): add ``offset`` to each aligned index of second iterable
                   (this option is only needed for recursive alignmnet of
                   substrings or sublists)
      keep_deleted (bool): return indices of deleted words too

    Returns:
      list: indices of s2 corresponding to given positions in s1

    """
    # create optimal matching matrix
    mtx = _make_matrix_(s1, s2, insert, delete, substitute)
    # decode best alignment using this matrix
    return _decode_matrix_(mtx, offset, keep_deleted)
from dsegmenter.common import NONE, prune_punc, score_substitute, \
    translate_toks
from dsegmenter.mateseg.dependency_graph import HEAD, WORD, REL, TAG, ADDRESS
from dsegmenter.mateseg.segmentation_tree import generate_subtrees_from_forest
from dsegmenter.treeseg import (TreeSegmenter, DiscourseSegment, DEPENDENCY,
                                DEFAULT_SEGMENT)
from dsegmenter.treeseg.treesegmenter import NO_MATCH_STRING
from dsegmenter.treeseg.constants import GREEDY
from dsegmenter.bparseg.align import nw_align
from sklearn.pipeline import Pipeline
from sklearn.feature_extraction import DictVectorizer
from sklearn.feature_selection import VarianceThreshold
from sklearn.svm import LinearSVC
from sklearn.metrics import precision_recall_fscore_support
from sklearn.externals import joblib
import os
import sys
    for tree_toks in tree_tok_keys:
        pruned_toks = prune_punc(tree_toks)
        if pruned_toks not in a_toks2trees:
            a_toks2trees[pruned_toks] = a_toks2trees[tree_toks]
    # establish a mapping between tree tokens and segment tokens
    tree_toks = list(set([t
                          for t_set in a_toks2trees.iterkeys()
                          for t in t_set]))
    tree_toks.sort(key=lambda el: el[0])
    seg_toks = list(set([t
                         for t_set in a_toks2segs.iterkeys()
                         for t in t_set]))
    seg_toks.sort(key=lambda el: el[0])
    # align tokens if necessary
    seg_t2tree_t = None
    if tree_toks != seg_toks:
        seg_t2tree_t = dict()
        alignment = nw_align(seg_toks, tree_toks,
                             substitute=score_substitute,
                             keep_deleted=True)
        for i, tt in enumerate(alignment):
            seg_t2tree_t[seg_toks[i]] = [tree_toks[j] for j in tt]
        # for each segment look if its corresponding token set is matched by
        # any other subtree
        translated_toks = None
    for toks, segs in a_toks2segs.iteritems():
        translated_toks = translate_toks(toks, seg_t2tree_t)
        key = None
        if translated_toks in a_toks2trees:
            key = translated_toks
        else:
            translated_toks = prune_punc(translated_toks)
            if translated_toks in a_toks2trees:
                key = translated_toks
        if key:
            for tree in a_toks2trees[key]:
                # if tree2seg[tree] is not None:
                #     continue
                assert tree2seg[tree] is None, \
                    "Multiple segments found for tree" + repr(tree) + ": " + \
                    repr(segs[-1]) + "; " + repr(tree2seg[tree])
                tree2seg[tree] = segs[-1]
    return tree2seg


def gen_features_for_segment(dep_graph, trg_adr):
    """ ugly feature extraction code  ;) """

    nodes = list(dep_graph.subgraphs(exclude_root=False))
    nl = {node[ADDRESS]: node for node in nodes}
    assert len(nodes) == len(nl)

    if trg_adr >= len(nl):
        return {}
    seg_adr_span = dep_graph.address_span(trg_adr)

    # get relation, this word and pos
    rel = nl[trg_adr][REL] if REL in nl[trg_adr] else feature_not_found
    this_word = nl[trg_adr][WORD][1] if WORD in nl[trg_adr] and \
        nl[trg_adr][WORD] is not None else feature_not_found
    this_pos = nl[trg_adr][TAG] if TAG in nl[trg_adr] else feature_not_found

    # get head word and pos
    head_adr = nl[trg_adr][HEAD] if HEAD in nl[trg_adr] else None
    if head_adr is not None:
        head_word = nl[head_adr][WORD][1] if WORD in nl[head_adr] and \
            nl[head_adr][WORD] is not None else feature_not_found
        head_pos = nl[head_adr][TAG] if TAG in nl[head_adr] else \
            feature_not_found
    else:
        head_word = head_pos = feature_not_found

    # get first and last word from segment
    first_adr = seg_adr_span[0]
    first_word = nl[first_adr][WORD][1] if nl[first_adr][WORD] is not None \
        else feature_not_found
    last_adr = seg_adr_span[-1]
    last_word = nl[last_adr][WORD][1] if nl[last_adr][WORD] is not None \
        else feature_not_found

    # get words left and right from segment
    left_adr = seg_adr_span[0] - 1
    left_word = nl[left_adr][WORD][1] if len(nl) > left_adr > 0 and \
        WORD in nl[left_adr] and nl[left_adr][WORD] is not None else \
        feature_not_found
    right_adr = seg_adr_span[-1] + 1
    right_word = nl[right_adr][WORD][1] if len(nl) > right_adr > 0 and \
        WORD in nl[right_adr] and nl[right_adr][WORD] is not None else \
        feature_not_found

    # get segment length
    length_abs = len(seg_adr_span)

    # get number of punctuation in segment
    punct_count = sum([1 if adr in nl and TAG in nl[adr] and
                       nl[adr][TAG] in punct_tags else 0 for adr in
                       seg_adr_span])

    # resulting feature dictionary
    r = {
        'rel': rel,
        'head_word': head_word,
        'head_pos': head_pos,
        'this_word': this_word,
        'this_pos': this_pos,
        'rel+head_pos+this_pos': '+'.join([rel, head_pos, this_pos]),
        'rel+head_pos': '+'.join([rel, head_pos]),
        'rel+this_pos': '+'.join([rel, this_pos]),
        'head_pos+this_pos': '+'.join([head_pos, this_pos]),
        'first_word': first_word,
        'last_word': last_word,
        'left_word': left_word,
        'right_word': right_word,
        'length_abs': length_abs,
        'punct_count': punct_count,
    }

    # simply add all words for this segment
    for adr in seg_adr_span:
        if nl[adr][WORD] is not None:

            word = nl[adr][WORD][1]