Повторяющиеся фразы в тексте Python

Question

У меня есть проблема, и я не знаю, как ее решить. Пожалуйста, дайте совет.

У меня есть текст. Большой, большой текст. Задача состоит в том, чтобы найти в тексте все повторяющиеся фразы, длина которых равна 3(содержит три слова).

Answer 1

У вас, как мне кажется, две проблемы.

Первый - это эффективный способ нормализации ввода. Вы говорите, что хотите найти все фразы из трех слов во входных данных, но из чего состоит фраза? Например, являются the black dog а также The black, dog? та же фраза?

Способ сделать это, как предполагает Marcog, - использовать что-то вроде re.findall, Но это довольно неэффективно: он обходит весь ваш ввод и копирует слова в список, а затем вам нужно обработать этот список. Если ваш вводимый текст очень длинный, это будет расточительно как во времени, так и в пространстве.

Лучшим подходом было бы рассматривать входные данные как поток и создать генератор, который выводит по одному слову за раз. Вот пример, который использует пробелы в качестве разделителя между словами, затем удаляет из слов не-буквенные символы и преобразует их в нижний регистр:

>>> def words(text):
       pattern = re.compile(r"[^\s]+")
       non_alpha = re.compile(r"[^a-z]", re.IGNORECASE)
       for match in pattern.finditer(text):
           nxt = non_alpha.sub("", match.group()).lower()
           if nxt:  # skip blank, non-alpha words
               yield nxt


>>> text
"O'er the bright blue sea, for Sir Joseph Porter K.C.B."
>>> list(words(text))
['oer', 'the', 'bright', 'blue', 'sea', 'for', 'sir', 'joseph', 'porter', 'kcb']

Вторая проблема - группировка нормализованных слов в трехсловные фразы. Опять же, вот место, где генератор будет работать эффективно:

>>> def phrases(words):
        phrase = []
        for word in words:
            phrase.append(word)
            if len(phrase) > 3:
                phrase.remove(phrase[0])
            if len(phrase) == 3:
                yield tuple(phrase)

>>> list(phrases(words(text)))
[('oer', 'the', 'bright'), ('the', 'bright', 'blue'), ('bright', 'blue', 'sea'), ('blue', 'sea', 'for'), ('sea', 'for', 'sir'), ('for', 'sir', 'joseph'), ('sir', 'joseph', 'porter'), ('joseph', 'porter', 'kcb')]

Почти наверняка возможна более простая версия этой функции, но она эффективна, и ее нетрудно понять.

Важно отметить, что объединение генераторов в цепочку происходит только один раз, и оно не создает больших временных структур данных в памяти. Вы можете использовать результат, чтобы построить defaultdict ключевая фраза:

>>> import collections
>>> counts = collections.defaultdict(int)
>>> for phrase in phrases(words(text)):
        counts[phrase] += 1

Это делает один проход text как он считает фразы. Когда это будет сделано, найдите в словаре каждую запись, значение которой больше единицы.

Answer 2

Самый грубый способ - читать текст в виде строки. Сделайте string.split() и получите отдельные слова в списке. Затем вы можете нарезать список на три слова и использовать collection.defaultdict(int) для сохранения количества.

d = collection.defaultdict(int)

д [фраза]+=1

как я уже сказал, это очень грубо. Но, конечно, вы должны начать

Answer 3

Я бы посоветовал взглянуть на инструментарий NLTK. Это открытый исходный код и предназначен для обучения естественному языку. Наряду с высокоуровневыми функциями НЛП, он имеет много типов функций и коллекций.

Answer 4

Вот примерное решение O(n), которое должно работать с довольно большими входными текстами. Если он слишком медленный, вы, вероятно, захотите использовать Perl, который был разработан для обработки текста, или C++ для чистой производительности.

>>> s = 'The quick brown fox jumps over the lazy dog'
>>> words = string.lower(s).split()
>>> phrases = collections.defaultdict(int)
>>> for a, b, c in zip(words[:-3], words[1:-2], words[2:]):
...     phrases[(a, b, c)] += 1
... 
>>> phrases
defaultdict(<type 'int'>, {('over', 'the', 'lazy'): 1, ('quick', 'brown', 'fox'): 1, ('the', '
quick', 'brown'): 1, ('jumps', 'over', 'the'): 1, ('brown', 'fox', 'jumps'): 1, ('fox', 'jumps
', 'over'): 1})
>>> [phrase for phrase, count in phrases.iteritems() if count > 1]
>>> []