在文本中匹配存储的关键字/短语

Question

我有一个包含大约1000个关键字/短语（长度为1到4个字）的数据库表 - 此表很少改变，所以我可以将数据提取到更有用的东西（如正则表达式？ ） - 所以这不是根据基于自然语言处理的关键字找到/猜测。

然后我有一个用户输入一些文本到我想匹配我的关键字和短语的表单。

然后，程序将存储指向文本旁边匹配的每个短语的链接。

因此，如果我们跑了针对在这里几句这个问题文本的算法，我们会得到像这样的结果：

{"inputting some text" : 1, 
"extract the data" : 1, 
"a phrase not here" : 0} 

我有哪些选择？

1. 编译正则表达式
2. 某种SQL查询
3. 第三种方法吗？

铭记，有一个1000个可能的短语..

我正在Django的/ Python的使用MySQL。

编辑：目前，我正在做这个：

>>> text_input = "This is something with first phrase in and third phrase" 
>>> regex = "first phrase|second phrase|third phrase" 
>>> p = re.compile(regex, re.I) 
>>> p.findall(text_input) 
['first phrase','third phrase'] 

Answer 1

此作业的算法是Aho-Corasick ......看到界河指向C的扩展为Python底部的链接。

Answer 2

如果我理解正确的话，你有一组唯一的字符串，要对比较输入字符串。在这种情况下，您可以使用set来存储处理结果和db​​值。然后可以进行比较，如下所示：

>>> db = {'abc', 'def', 'jhi', 'asdf'} 
>>> inpt = {'abc', 'tmp'} 
>>> db & inpt 
{'abc'} 

进一步转换为字典是微不足道的。

Answer 3

刚抬起头......你可能会从链接的Django文档感兴趣django's support for regex in queries

例子：

Entry.objects.get(title__regex=r'^(An?|The) +') 

Answer 4

这里是SilentGhost的答案稍有不同。您逐行加载关键字。将它们存储在一个集合中。对于您在用户输入中找到的每个关键字，都会增加结果中的相应条目。

keyword_file = StringIO("""inputting some text 
    extract the data 
    a phrase not here""") 

keywords = set(line.strip() for line in keyword_file) 

results = defaultdict(int) 
for phrase in keywords: 
    if userinput.find(phrase) != -1: 
     results[phrase] += 1 

print results 

希望这点能指出您的方向是正确的。不完全确定这是你所问的，但这是我最好的猜测。

你关心速度吗？你为什么不喜欢现在使用的方法？你的方法工作吗？

Answer 5

一旦你形成你的模式，如(first phrase)|(the second)|(and another)（与括号表明我），并将其编译成一个正则表达式对象r，一个好办法，在比赛环路，并确定其符合它是：

class GroupCounter(object): 
    def __init__(self, phrases): 
    self.phrases = phrases 
    self.counts = [0] * len(phrases) 
    def __call__(self, mo): 
    self.counts[mo.lastindex - 1] += 1 
    return '' 
    def asdict(self): 
    return dict(zip(self.phrases, self.counts)) 

g = GroupCounter(['first phrase', 'the second', 'and another']) 
r.sub(g, thetext) 
print g.asdict() 

让GroupCounter实例也构建正则表达式对象也是合理的，因为它确实需要与正则表达式本身出现的顺序相同的短语列表。

Answer 6

如果您有1000个短语，并且您在搜索输入字符串以查找其中哪些短语是子字符串，那么您可能不会对使用大正则表达式获得的性能感到满意。一个trie是一个更多的工作要实现，但它更有效率：正则表达式a|b|c|d|e对给定输入字符串中的每个字符执行五个测试，而一个只有一个字符串。您也可以使用产生DFA的词法分析器，如Plex。

编辑：

我出现在这个早上被拖延。试试这个：

class Trie(object): 
     def __init__(self): 
      self.children = {} 
      self.item = None 
     def add(self, item, remainder=None): 
      """Add an item to the trie.""" 
      if remainder == None: 
       remainder = item 
      if remainder == "": 
       self.item = item 
      else: 
       ch = remainder[0] 
       if not self.children.has_key(ch): 
        self.children[ch] = Trie() 
       self.children[ch].add(item, remainder[1:]) 
     def find(self, word): 
      """Return True if word is an item in the trie.""" 
      if not word: 
       return True 
      ch = word[0] 
      if not self.children.has_key(ch): 
       return False 
      return self.children[ch].find(word[1:]) 
     def find_words(self, word, results=None): 
      """Find all items in the trie that word begins with.""" 
      if results == None: 
       results = [] 
      if self.item: 
       results.append(self.item) 
      if not word: 
       return results 
      ch = word[0] 
      if not self.children.has_key(ch): 
       return results 
      return self.children[ch].find_words(word[1:], results) 

快速测试（words.txt是BSD字的文件，一个非常方便的事情有大约 - 它包含了约24个字）：

>>> t = Trie() 
>>> with open(r'c:\temp\words.txt', 'r') as f: 
     for word in f: 
      t.add(word.strip()) 

这需要在15秒左右我机。然而，这几乎是瞬间：

>>> s = "I played video games in a drunken haze." 
>>> r = [] 
>>> for i in range(len(s)): 
     r.extend(t.find_words(s[i:])) 
>>> r 
['I', 'p', 'play', 'l', 'la', 'lay', 'a', 'ay', 'aye', 'y', 'ye', 'yed', 'e', 'd', 'v', 'video', 'i', 'id', 'ide', 'd', 'de', 'e', 'o', 'g', 'ga', 'gam', 'game', 'a', 'am', 'ame', 'm', 'me', 'e', 'es', 's', 'i', 'in', 'n', 'a', 'd', 'drunk', 'drunken', 'r', 'run', 'u', 'un', 'unken', 'n', 'k', 'ken', 'e', 'en', 'n', 'h', 'ha', 'haze', 'a', 'z', 'e'] 

是，unken是words.txt。我不知道为什么。

哦，我也尝试用正则表达式来比较：

>>> import re 
>>> with open(r'c:\temp\words.txt', 'r') as f: 
     p = "|".join([l.strip() for l in f]) 

>>> p = re.compile(p) 

Traceback (most recent call last): 
    File "<pyshell#250>", line 1, in <module> 
    p = re.compile(p) 
    File "C:\Python26\lib\re.py", line 188, in compile 
    return _compile(pattern, flags) 
    File "C:\Python26\lib\re.py", line 241, in _compile 
    p = sre_compile.compile(pattern, flags) 
    File "C:\Python26\lib\sre_compile.py", line 529, in compile 
    groupindex, indexgroup 
OverflowError: regular expression code size limit exceeded