binaries/src/globplot/biopython-1.50/Bio/triefind.py

   1 """
   2 Given a trie, find all occurrences of a word in the trie in a string.
   3
   4 Like searching a string for a substring, except that the substring is
   5 any word in a trie.
   6
   7 Functions:
   8 match         Find longest key in a trie matching the beginning of the string.
   9 match_all     Find all keys in a trie matching the beginning of the string.
  10 find          Find keys in a trie matching anywhere in a string.
  11 find_words    Find keys in a trie matching whole words in a string.
  12
  13 """
  14 import string
  15 import re
  16
  17 def match(string, trie):
  18     """match(string, trie) -> longest key or None
  19
  20     Find the longest key in the trie that matches the beginning of the
  21     string.
  22
  23     """
  24     longest = None
  25     for i in range(len(string)):
  26         substr = string[:i+1]
  27         if not trie.has_prefix(substr):
  28             break
  29         if trie.has_key(substr):
  30             longest = substr
  31     return longest
  32
  33 def match_all(string, trie):
  34     """match_all(string, trie) -> list of keys
  35
  36     Find all the keys in the trie that matches the beginning of the
  37     string.
  38
  39     """
  40     matches = []
  41     for i in range(len(string)):
  42         substr = string[:i+1]
  43         if not trie.has_prefix(substr):
  44             break
  45         if trie.has_key(substr):
  46             matches.append(substr)
  47     return matches
  48
  49 def find(string, trie):
  50     """find(string, trie) -> list of tuples (key, start, end)
  51
  52     Find all the keys in the trie that match anywhere in the string.
  53
  54     """
  55     results = []
  56     start = 0     # index to start the search
  57     while start < len(string):
  58         # Look for a match.
  59         keys = match_all(string[start:], trie)
  60         for key in keys:
  61             results.append((key, start, start+len(key)))
  62         start += 1
  63     return results
  64
  65 DEFAULT_BOUNDARY_CHARS = string.punctuation + string.whitespace
  66
  67 def find_words(string, trie):
  68     """find_words(string, trie) -> list of tuples (key, start, end)
  69
  70     Find all the keys in the trie that match full words in the string.
  71     Word boundaries are defined as any punctuation or whitespace.
  72
  73     """
  74     _boundary_re = re.compile(r"[%s]+" % re.escape(DEFAULT_BOUNDARY_CHARS))
  75
  76     results = []
  77     start = 0     # index of word boundary
  78     while start < len(string):
  79         # Look for a match.
  80         keys = match_all(string[start:], trie)
  81         for key in keys:
  82             l = len(key)
  83             # Make sure it ends at a boundary.
  84             if start+l == len(string) or \
  85                _boundary_re.match(string[start+l]):
  86                 results.append((key, start, start+l))
  87         # Move forward to the next boundary.
  88         m = _boundary_re.search(string, start)
  89         if m is None:
  90             break
  91         start = m.end()
  92     return results