повторяющиеся фразы в тексте Python - PullRequest
Новая
       25

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

2 голосов
/ 24 декабря 2010

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

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

Ответы [ 4 ]

7 голосов
/ 25 декабря 2010

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

Первый - эффективный способ нормализации ввода.Вы говорите, что хотите найти все фразы из трех слов во входных данных, но из чего состоит фраза?Например, 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')]

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

* 1017Примечательно, что объединение генераторов в цепочку происходит только один раз, и оно не создает больших временных структур данных в памяти.Вы можете использовать результат для построения defaultdict, набираемого по фразе: 
>>> import collections
>>> counts = collections.defaultdict(int)
>>> for phrase in phrases(words(text)):
        counts[phrase] += 1

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

2 голосов
/ 24 декабря 2010

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

d = КоллекцияНо, конечно, вы должны начать

1 голос
/ 24 декабря 2010

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

0 голосов
/ 24 декабря 2010

Вот примерное решение 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]
>>> []
...