алгоритм согласования последовательностей в python

Question

У меня есть список предложений, таких как это:

errList = [ 'Ragu ate lunch but didnt have Water for drinks',
            'Rams ate lunch but didnt have Gatorade for drinks',
            'Saya ate lunch but didnt have :water for drinks',
            'Raghu ate lunch but didnt have water for drinks',
            'Hanu ate lunch but didnt have -water for drinks',
            'Wayu ate lunch but didnt have water for drinks',
            'Viru ate lunch but didnt have .water 4or drinks',

            'kk ate lunch & icecream but did have Water for drinks',
            'M ate lunch &and icecream but did have Gatorade for drinks',
            'Parker ate lunch icecream but didnt have :water for drinks',
            'Sassy ate lunch and icecream but didnt have water for drinks',
            'John ate lunch and icecream but didnt have -water for drinks',
            'Pokey ate lunch and icecream but didnt have Water for drinks',
            'Laila ate lunch and icecream but did have water 4or drinks',
        ]

Я хочу узнать количество самых длинных фраз / части (фраза должна быть более 2 слов) предложений в каждом элементе списка?В следующем примере выходные данные будут выглядеть ближе к этому (самая длинная фраза в качестве ключа и значение в качестве значения):

{ 'ate lunch but didnt have': 7,
  'water for drinks': 7,
  'ate lunch and icecream': 4,
  'didnt have water': 3,
  'didnt have Water': 2    # case sensitives
}

Использование модуля re не подлежит сомнению, поскольку проблема близка к сопоставлению последовательности или, возможно, с использованием nltk или, возможно,учить-учиться?Я немного знаком с NLP и scikit, но не достаточно, чтобы решить эту проблему?Если я решу это, я опубликую это здесь.

Answer 1

Использование инструментов из сторонней библиотеки more_itertools:

Дано

import itertools as it
import collections as ct

import more_itertools as mit


data = [ 
    "Ragu ate lunch but didnt have Water for drinks",
    "Rams ate lunch but didnt have Gatorade for drinks",
    "Saya ate lunch but didnt have :water for drinks",
    "Raghu ate lunch but didnt have water for drinks",
    "Hanu ate lunch but didnt have -water for drinks",
    "Wayu ate lunch but didnt have water for drinks",
    "Viru ate lunch but didnt have .water 4or drinks",
    "kk ate lunch & icecream but did have Water for drinks",
    "M ate lunch &and icecream but did have Gatorade for drinks",
    "Parker ate lunch icecream but didnt have :water for drinks",
    "Sassy ate lunch and icecream but didnt have water for drinks",
    "John ate lunch and icecream but didnt have -water for drinks",
    "Pokey ate lunch and icecream but didnt have Water for drinks",
    "Laila ate lunch and icecream but did have water 4or drinks",
]

Код

ngrams = []
for sentence in data:
    words = sentence.split()
    for n in range(3, len(words)+1): 
        ngrams.extend((list(mit.windowed(words, n))))

counts = ct.Counter(ngrams)
dict(counts.most_common(5))

Выход

{('but', 'didnt', 'have'): 11,
 ('ate', 'lunch', 'but'): 7,
 ('lunch', 'but', 'didnt'): 7,
 ('ate', 'lunch', 'but', 'didnt'): 7,
 ('lunch', 'but', 'didnt', 'have'): 7}

В качестве альтернативы

sentences = [sentence.split() for sentence in data]
ngrams = mit.flatten(list(mit.windowed(w, n)) for n in range(3, len(sentences)+1) for w in sentences)
counts = ct.Counter(ngrams)
dict(counts.most_common(5))

Answer 2

Это не слишком больно с scikit-learn с небольшим количеством numpy foo.Однако, предупреждающее слово, здесь у меня есть только настройки по умолчанию для предварительной обработки, если вы заинтересованы в пунктуации в вашем наборе данных, вам нужно настроить это.

from sklearn.feature_extraction.text import CountVectorizer

# Find all the phrases >2 up to the max length 
cv = CountVectorizer(ngram_range=(3, max([len(x.split(' ')) for x in errList])))
# Get the counts of the phrases
err_counts = cv.fit_transform(errList)
# Get the sum of each of the phrases
err_counts = err_counts.sum(axis=0)
# Mess about with the types, sparsity is annoying
err_counts = np.squeeze(np.asarray(err_counts))
# Retrieve the actual phrases that we're working with
feat_names = np.array(cv.get_feature_names())

# We don't have to sort here, but it's nice to if you want to print anything
err_counts_sorted = err_counts.argsort()[::-1]
feat_names = feat_names[err_counts_sorted]
err_counts = err_counts[err_counts_sorted]

# This is the dictionary that you were after
err_dict = dict(zip(feat_names, err_counts))

Вот вывод для верхнегонесколько

11 but didnt have
10 have water for drinks
10 have water for
10 water for drinks
10 but didnt have water
10 didnt have water
9 but didnt have water for drinks
9 but didnt have water for
9 didnt have water for drinks
9 didnt have water for

Answer 3

Если вы не хотите возиться с внешними библиотеками, вы можете сделать это только с помощью stdlib (хотя это может быть медленнее, чем некоторые альтернативы):

import collections
import itertools

def gen_ngrams(sentence):
    words = sentence.split() # or re.findall('\b\w+\b'), or whatever
    n_words = len(words)
    for i in range(n_words - 2):
        for j in range(i + 3, n_words):
            yield ' '.join(words[i: j]) # Assume normalization of spaces


def count_ngrams(sentences):
    return collections.Counter(
        itertools.chain.from_iterable(
            gen_ngrams(sentence) for sentence in sentences
        )
    )

counts = count_ngrams(errList)
dict(counts.most_common(10))

, что дает вам:

{'but didnt have': 11,
 'ate lunch but': 7,
 'ate lunch but didnt': 7,
 'ate lunch but didnt have': 7,
 'lunch but didnt': 7,
 'lunch but didnt have': 7,
 'icecream but didnt': 4,
 'icecream but didnt have': 4,
 'ate lunch and': 4,
 'ate lunch and icecream': 4}

Answer 4

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

from nltk import ngrams, word_tokenize
from collections import defaultdict
min_ngram_length = 1
max_ngram_length = max([len(x) for x in errList])
d = defaultdict(int)
for item in errList:
    for i in range(min_ngram_length, max_ngram_length):
        for ngram in ngrams(word_tokenize(item), i):
            d[ngram] += 1
for pair in sorted(d.items(), key = lambda x: x[1], reverse=True):
    print(pair)