соответствие сохраненных ключевых слов / фраз в тексте

Question

У меня есть таблица базы данных, содержащая около 1000 ключевых слов / фраз (длиной от одного до четырех слов). Эта таблица изменяется редко, поэтому я могу извлечь данные в нечто более полезное (например, регулярное выражение?) / угадывание ключевых слов на основе обработки естественного языка ..

Затем у меня есть пользователь, который вводит некоторый текст в форму, которую я хотел бы сопоставить с моими ключевыми словами и фразами.

Затем программа будет хранить ссылку на каждую фразу, которая соответствует тексту.

Таким образом, если бы мы запустили алгоритм в этом тексте вопроса по нескольким фразам, которые здесь есть, мы получили бы такой результат:

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

Какие у меня варианты?

1. Скомпилируйте регулярное выражение
2. Какой-то SQL-запрос
3. Третий путь?

Имея в виду, что есть 1000 возможных фраз ..

Я использую Django / Python с MySQL.

edit: я сейчас делаю это:

>>> 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

Если у вас есть 1000 фраз, и вы ищете строку ввода, чтобы найти, какие из этих фраз являются подстроками, вы, вероятно, не будете удовлетворены производительностью, которую вы получите, используя большое регулярное выражение. trie - это немного больше работы для реализации, но он гораздо эффективнее: регулярное выражение a|b|c|d|e выполняет пять тестов для каждого символа в данной входной строке, в то время как три выполняет только один. Вы также можете использовать лексер, такой как Plex , который производит DFA.

Edit:

Я, кажется, откладываю это утро. Попробуйте это:

    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, очень удобный для использования - он содержит около 240 000 слов):

>>> 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 в словах.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

Answer 3

После того, как вы сформировали свой шаблон, например (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 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

Просто на голову ... вас может заинтересовать поддержка django регулярных выражений в запросах

Пример из связанных документов django:

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

Answer 6

Если я правильно вас понимаю, у вас есть уникальный набор строк, с которым вы хотите сравнить входные строки. В этом случае вы можете использовать set для хранения результатов обработки и значений в дБ. Сравнение тогда можно сделать следующим образом:

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

Дальнейшее преобразование в словарь тривиально.