searchparser.py 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292
  1. """Search query parser
  2. version 2006-03-09
  3. This search query parser uses the excellent Pyparsing module
  4. (http://pyparsing.sourceforge.net/) to parse search queries by users.
  5. It handles:
  6. * 'and', 'or' and implicit 'and' operators;
  7. * parentheses;
  8. * quoted strings;
  9. * wildcards at the end of a search term (help*);
  10. Requirements:
  11. * Python
  12. * Pyparsing
  13. If you run this script, it will perform a number of tests. To use is as a
  14. module, you should use inheritance on the SearchQueryParser class and overwrite
  15. the Get... methods. The ParserTest class gives a very simple example of how this
  16. could work.
  17. -------------------------------------------------------------------------------
  18. Copyright (c) 2006, Estrate, the Netherlands
  19. All rights reserved.
  20. Redistribution and use in source and binary forms, with or without modification,
  21. are permitted provided that the following conditions are met:
  22. * Redistributions of source code must retain the above copyright notice, this
  23. list of conditions and the following disclaimer.
  24. * Redistributions in binary form must reproduce the above copyright notice,
  25. this list of conditions and the following disclaimer in the documentation
  26. and/or other materials provided with the distribution.
  27. * Neither the name of Estrate nor the names of its contributors may be used
  28. to endorse or promote products derived from this software without specific
  29. prior written permission.
  30. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  31. ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  32. WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  33. DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
  34. ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  35. (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  36. LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
  37. ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38. (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  39. SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40. CONTRIBUTORS:
  41. - Steven Mooij
  42. - Rudolph Froger
  43. - Paul McGuire
  44. TODO:
  45. - add more docs
  46. - ask someone to check my English texts
  47. - add more kinds of wildcards ('*' at the beginning and '*' inside a word)?
  48. """
  49. from pyparsing import Word, alphanums, Keyword, Group, Combine, Forward, Suppress, OneOrMore, oneOf
  50. class SearchQueryParser:
  51. def __init__(self):
  52. self._methods = {
  53. 'and': self.evaluateAnd,
  54. 'or': self.evaluateOr,
  55. 'not': self.evaluateNot,
  56. 'parenthesis': self.evaluateParenthesis,
  57. 'quotes': self.evaluateQuotes,
  58. 'word': self.evaluateWord,
  59. 'wordwildcard': self.evaluateWordWildcard,
  60. }
  61. self._parser = self.parser()
  62. def parser(self):
  63. """
  64. This function returns a parser.
  65. The grammar should be like most full text search engines (Google, Tsearch, Lucene).
  66. Grammar:
  67. - a query consists of alphanumeric words, with an optional '*' wildcard
  68. at the end of a word
  69. - a sequence of words between quotes is a literal string
  70. - words can be used together by using operators ('and' or 'or')
  71. - words with operators can be grouped with parenthesis
  72. - a word or group of words can be preceded by a 'not' operator
  73. - the 'and' operator precedes an 'or' operator
  74. - if an operator is missing, use an 'and' operator
  75. """
  76. operatorOr = Forward()
  77. operatorWord = Group(Combine(Word(alphanums) + Suppress('*'))).setResultsName('wordwildcard') | \
  78. Group(Word(alphanums)).setResultsName('word')
  79. operatorQuotesContent = Forward()
  80. operatorQuotesContent << (
  81. (operatorWord + operatorQuotesContent) | operatorWord
  82. )
  83. operatorQuotes = Group(
  84. Suppress('"') + operatorQuotesContent + Suppress('"')
  85. ).setResultsName("quotes") | operatorWord
  86. operatorParenthesis = Group(
  87. (Suppress("(") + operatorOr + Suppress(")"))
  88. ).setResultsName("parenthesis") | operatorQuotes
  89. operatorNot = Forward()
  90. operatorNot << (Group(
  91. Suppress(Keyword("not", caseless=True)) + operatorNot
  92. ).setResultsName("not") | operatorParenthesis)
  93. operatorAnd = Forward()
  94. operatorAnd << (Group(
  95. operatorNot + Suppress(Keyword("and", caseless=True)) + operatorAnd
  96. ).setResultsName("and") | Group(
  97. operatorNot + OneOrMore(~oneOf("and or") + operatorAnd)
  98. ).setResultsName("and") | operatorNot)
  99. operatorOr << (Group(
  100. operatorAnd + Suppress(Keyword("or", caseless=True)) + operatorOr
  101. ).setResultsName("or") | operatorAnd)
  102. return operatorOr.parseString
  103. def evaluateAnd(self, argument):
  104. return self.evaluate(argument[0]).intersection(self.evaluate(argument[1]))
  105. def evaluateOr(self, argument):
  106. return self.evaluate(argument[0]).union(self.evaluate(argument[1]))
  107. def evaluateNot(self, argument):
  108. return self.GetNot(self.evaluate(argument[0]))
  109. def evaluateParenthesis(self, argument):
  110. return self.evaluate(argument[0])
  111. def evaluateQuotes(self, argument):
  112. """Evaluate quoted strings
  113. First is does an 'and' on the indidual search terms, then it asks the
  114. function GetQuoted to only return the subset of ID's that contain the
  115. literal string.
  116. """
  117. r = set()
  118. search_terms = []
  119. for item in argument:
  120. search_terms.append(item[0])
  121. if len(r) == 0:
  122. r = self.evaluate(item)
  123. else:
  124. r = r.intersection(self.evaluate(item))
  125. return self.GetQuotes(' '.join(search_terms), r)
  126. def evaluateWord(self, argument):
  127. return self.GetWord(argument[0])
  128. def evaluateWordWildcard(self, argument):
  129. return self.GetWordWildcard(argument[0])
  130. def evaluate(self, argument):
  131. return self._methods[argument.getName()](argument)
  132. def Parse(self, query):
  133. #print self._parser(query)[0]
  134. return self.evaluate(self._parser(query)[0])
  135. def GetWord(self, word):
  136. return set()
  137. def GetWordWildcard(self, word):
  138. return set()
  139. def GetQuotes(self, search_string, tmp_result):
  140. return set()
  141. def GetNot(self, not_set):
  142. return set().difference(not_set)
  143. class ParserTest(SearchQueryParser):
  144. """Tests the parser with some search queries
  145. tests containts a dictionary with tests and expected results.
  146. """
  147. tests = {
  148. 'help': {1, 2, 4, 5},
  149. 'help or hulp': {1, 2, 3, 4, 5},
  150. 'help and hulp': {2},
  151. 'help hulp': {2},
  152. 'help and hulp or hilp': {2, 3, 4},
  153. 'help or hulp and hilp': {1, 2, 3, 4, 5},
  154. 'help or hulp or hilp or halp': {1, 2, 3, 4, 5, 6},
  155. '(help or hulp) and (hilp or halp)': {3, 4, 5},
  156. 'help and (hilp or halp)': {4, 5},
  157. '(help and (hilp or halp)) or hulp': {2, 3, 4, 5},
  158. 'not help': {3, 6, 7, 8},
  159. 'not hulp and halp': {5, 6},
  160. 'not (help and halp)': {1, 2, 3, 4, 6, 7, 8},
  161. '"help me please"': {2},
  162. '"help me please" or hulp': {2, 3},
  163. '"help me please" or (hulp and halp)': {2},
  164. 'help*': {1, 2, 4, 5, 8},
  165. 'help or hulp*': {1, 2, 3, 4, 5},
  166. 'help* and hulp': {2},
  167. 'help and hulp* or hilp': {2, 3, 4},
  168. 'help* or hulp or hilp or halp': {1, 2, 3, 4, 5, 6, 8},
  169. '(help or hulp*) and (hilp* or halp)': {3, 4, 5},
  170. 'help* and (hilp* or halp*)': {4, 5},
  171. '(help and (hilp* or halp)) or hulp*': {2, 3, 4, 5},
  172. 'not help* and halp': {6},
  173. 'not (help* and helpe*)': {1, 2, 3, 4, 5, 6, 7},
  174. '"help* me please"': {2},
  175. '"help* me* please" or hulp*': {2, 3},
  176. '"help me please*" or (hulp and halp)': {2},
  177. '"help me please" not (hulp and halp)': {2},
  178. '"help me please" hulp': {2},
  179. 'help and hilp and not holp': {4},
  180. 'help hilp not holp': {4},
  181. 'help hilp and not holp': {4},
  182. }
  183. docs = {
  184. 1: 'help',
  185. 2: 'help me please hulp',
  186. 3: 'hulp hilp',
  187. 4: 'help hilp',
  188. 5: 'halp thinks he needs help',
  189. 6: 'he needs halp',
  190. 7: 'nothing',
  191. 8: 'helper',
  192. }
  193. index = {
  194. 'help': {1, 2, 4, 5},
  195. 'me': {2},
  196. 'please': {2},
  197. 'hulp': {2, 3},
  198. 'hilp': {3, 4},
  199. 'halp': {5, 6},
  200. 'thinks': {5},
  201. 'he': {5, 6},
  202. 'needs': {5, 6},
  203. 'nothing': {7},
  204. 'helper': {8},
  205. }
  206. def GetWord(self, word):
  207. if (word in self.index):
  208. return self.index[word]
  209. else:
  210. return set()
  211. def GetWordWildcard(self, word):
  212. result = set()
  213. for item in list(self.index.keys()):
  214. if word == item[0:len(word)]:
  215. result = result.union(self.index[item])
  216. return result
  217. def GetQuotes(self, search_string, tmp_result):
  218. result = set()
  219. for item in tmp_result:
  220. if self.docs[item].count(search_string):
  221. result.add(item)
  222. return result
  223. def GetNot(self, not_set):
  224. all = set(list(self.docs.keys()))
  225. return all.difference(not_set)
  226. def Test(self):
  227. all_ok = True
  228. for item in list(self.tests.keys()):
  229. print(item)
  230. r = self.Parse(item)
  231. e = self.tests[item]
  232. print('Result: %s' % r)
  233. print('Expect: %s' % e)
  234. if e == r:
  235. print('Test OK')
  236. else:
  237. all_ok = False
  238. print('>>>>>>>>>>>>>>>>>>>>>>Test ERROR<<<<<<<<<<<<<<<<<<<<<')
  239. print('')
  240. return all_ok
  241. if __name__=='__main__':
  242. if ParserTest().Test():
  243. print('All tests OK')
  244. else:
  245. print('One or more tests FAILED')