| 784 | return v |
| 785 | |
| 786 | def _match(self, sequence, sentence, start=0, i=0, w0=None, map=None, d=0): |
| 787 | # Backtracking tree search. |
| 788 | # Finds the first match in the sentence of the given sequence of constraints. |
| 789 | # start : the current word index. |
| 790 | # i : the current constraint index. |
| 791 | # w0 : the first word that matches a constraint. |
| 792 | # map : a dictionary of (Word index, Constraint) items. |
| 793 | # d : recursion depth. |
| 794 | |
| 795 | # XXX - We can probably rewrite all of this using (faster) regular expressions. |
| 796 | |
| 797 | if map is None: |
| 798 | map = {} |
| 799 | |
| 800 | # MATCH |
| 801 | if i == len(sequence): |
| 802 | if w0 is not None: |
| 803 | w1 = sentence.words[start-1] |
| 804 | # Greedy algorithm: |
| 805 | # - "cat" matches "the big cat" if "cat" is head of the chunk. |
| 806 | # - "Tom" matches "Tom the cat" if "Tom" is head of the chunk. |
| 807 | # - This behavior is ignored with POS-tag constraints: |
| 808 | # "Tom|NN" can only match single words, not chunks. |
| 809 | # - This is also True for negated POS-tags (e.g., !NN). |
| 810 | w01 = [w0, w1] |
| 811 | for j in (0, -1): |
| 812 | constraint, w = sequence[j], w01[j] |
| 813 | if self.strict is False and w.chunk is not None: |
| 814 | if len(constraint.tags) == 0: |
| 815 | if constraint.exclude is None or len(constraint.exclude.tags) == 0: |
| 816 | if constraint.match(w.chunk.head): |
| 817 | w01[j] = w.chunk.words[j] |
| 818 | if constraint.exclude and constraint.exclude.match(w.chunk.head): |
| 819 | return None |
| 820 | if self.greedy(w.chunk, constraint) is False: # User-defined. |
| 821 | return None |
| 822 | w0, w1 = w01 |
| 823 | # Update map for optional chunk words (see below). |
| 824 | words = sentence.words[w0.index:w1.index+1] |
| 825 | for w in words: |
| 826 | if w.index not in map and w.chunk: |
| 827 | wx = find(lambda w: w.index in map, reversed(w.chunk.words)) |
| 828 | if wx: |
| 829 | map[w.index] = map[wx.index] |
| 830 | # Return matched word range, we'll need the map to build Match.constituents(). |
| 831 | return Match(self, words, map) |
| 832 | return None |
| 833 | |
| 834 | # RECURSION |
| 835 | constraint = sequence[i] |
| 836 | for w in sentence.words[start:]: |
| 837 | #print " "*d, "match?", w, sequence[i].string # DEBUG |
| 838 | if i < len(sequence) and constraint.match(w): |
| 839 | #print " "*d, "match!", w, sequence[i].string # DEBUG |
| 840 | map[w.index] = constraint |
| 841 | if constraint.multiple: |
| 842 | # Next word vs. same constraint if Constraint.multiple=True. |
| 843 | m = self._match(sequence, sentence, w.index+1, i, w0 or w, map, d+1) |