nodes: 0, module; 1, function_definition; 2, function_name:search; 3, parameters; 4, block; 5, identifier:self; 6, identifier:query; 7, default_parameter; 8, expression_statement; 9, expression_statement; 10, expression_statement; 11, comment:# Identify possible results; 12, for_statement; 13, comment:# Sort results by decreasing similarity; 14, expression_statement; 15, return_statement; 16, identifier:threshold; 17, None; 18, comment:"""Search the index for items whose key exceeds threshold
          similarity to the query string.
  
          :param query: returned items will have at least `threshold` \
          similarity to the query string.
  
          :return: list of pairs of (item, similarity) by decreasing similarity.
  
          >>> from ngram import NGram
          >>> n = NGram([(0, "SPAM"), (1, "SPAN"), (2, "EG")], key=lambda x:x[1])
          >>> sorted(n.search("SPA"))
          [((0, 'SPAM'), 0.375), ((1, 'SPAN'), 0.375)]
          >>> n.search("M")
          [((0, 'SPAM'), 0.125)]
          >>> n.search("EG")
          [((2, 'EG'), 1.0)]
          """; 19, assignment; 20, assignment; 21, pattern_list; 22, call; 23, block; 24, call; 25, identifier:results; 26, identifier:threshold; 27, conditional_expression:threshold if threshold is not None else self.threshold; 28, identifier:results; 29, list; 30, identifier:match; 31, identifier:samegrams; 32, attribute; 33, argument_list; 34, expression_statement; 35, expression_statement; 36, if_statement; 37, attribute; 38, argument_list; 39, identifier:threshold; 40, comparison_operator:threshold is not None; 41, attribute; 42, call; 43, identifier:items; 44, assignment; 45, assignment; 46, comparison_operator:similarity >= threshold; 47, block; 48, identifier:results; 49, identifier:sort; 50, keyword_argument; 51, keyword_argument; 52, identifier:threshold; 53, None; 54, identifier:self; 55, identifier:threshold; 56, attribute; 57, argument_list; 58, identifier:allgrams; 59, parenthesized_expression; 60, identifier:similarity; 61, call; 62, identifier:similarity; 63, identifier:threshold; 64, expression_statement; 65, identifier:key; 66, lambda; 67, identifier:reverse; 68, True; 69, identifier:self; 70, identifier:items_sharing_ngrams; 71, identifier:query; 72, binary_operator:len(self.pad(query))
                          + self.length[match] - (2 * self.N) - samegrams + 2; 73, attribute; 74, argument_list; 75, call; 76, lambda_parameters; 77, subscript; 78, binary_operator:len(self.pad(query))
                          + self.length[match] - (2 * self.N) - samegrams; 79, integer:2; 80, identifier:self; 81, identifier:ngram_similarity; 82, identifier:samegrams; 83, identifier:allgrams; 84, attribute; 85, attribute; 86, argument_list; 87, identifier:x; 88, identifier:x; 89, integer:1; 90, binary_operator:len(self.pad(query))
                          + self.length[match] - (2 * self.N); 91, identifier:samegrams; 92, identifier:self; 93, identifier:warp; 94, identifier:results; 95, identifier:append; 96, tuple; 97, binary_operator:len(self.pad(query))
                          + self.length[match]; 98, parenthesized_expression; 99, identifier:match; 100, identifier:similarity; 101, call; 102, subscript; 103, binary_operator:2 * self.N; 104, identifier:len; 105, argument_list; 106, attribute; 107, identifier:match; 108, integer:2; 109, attribute; 110, call; 111, identifier:self; 112, identifier:length; 113, identifier:self; 114, identifier:N; 115, attribute; 116, argument_list; 117, identifier:self; 118, identifier:pad; 119, identifier:query
code: def search(self, query, threshold=None):
          """Search the index for items whose key exceeds threshold
          similarity to the query string.
  
          :param query: returned items will have at least `threshold` \
          similarity to the query string.
  
          :return: list of pairs of (item, similarity) by decreasing similarity.
  
          >>> from ngram import NGram
          >>> n = NGram([(0, "SPAM"), (1, "SPAN"), (2, "EG")], key=lambda x:x[1])
          >>> sorted(n.search("SPA"))
          [((0, 'SPAM'), 0.375), ((1, 'SPAN'), 0.375)]
          >>> n.search("M")
          [((0, 'SPAM'), 0.125)]
          >>> n.search("EG")
          [((2, 'EG'), 1.0)]
          """
          threshold = threshold if threshold is not None else self.threshold
          results = []
          # Identify possible results
          for match, samegrams in self.items_sharing_ngrams(query).items():
              allgrams = (len(self.pad(query))
                          + self.length[match] - (2 * self.N) - samegrams + 2)
              similarity = self.ngram_similarity(samegrams, allgrams, self.warp)
              if similarity >= threshold:
                  results.append((match, similarity))
          # Sort results by decreasing similarity
          results.sort(key=lambda x: x[1], reverse=True)
          return results