Эффективный способ подсчета частоты непрерывных слов?

Question

У меня есть такая строка:

inputString = "this is the first sentence in this book the first sentence is really the most interesting the first sentence is always first"

и словарь, подобный этому:

{   
   'always first': 0,
    'book the': 0,
    'first': 0,
    'first sentence': 0,
    'in this': 0,
    'interesting the': 0,
    'is always': 0,
    'is really': 0,
    'is the': 0,
    'most interesting': 0,
    'really the': 0,
    'sentence in': 0,
    'sentence is': 0,
    'the first': 0,
    'the first sentence': 0,
    'the first sentence is': 0,
    'the most': 0,
    'this': 0,
    'this book': 0,
    'this is': 0
}

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

Answer 1

Проверьте алгоритм Aho-Corasick .

Answer 2

Aho – Corasick определенно подходит, но если бы мне понадобилась простая реализация Python, я бы написал:

import collections

def consecutive_groups(seq, n):
    return (seq[i:i+n] for i in range(len(seq)-n))

def get_snippet_ocurrences(snippets):
    split_snippets = [s.split() for s in snippets]
    max_snippet_length = max(len(sp) for sp in split_snippets)
    for group in consecutive_groups(inputString.split(), max_snippet_length):
        for lst in split_snippets:
            if group[:len(lst)] == lst:
                yield " ".join(lst)

print collections.Counter(get_snippet_ocurrences(snippets))
# Counter({'the first sentence': 3, 'first sentence': 3, 'the first': 3, 'first': 3, 'the first sentence is': 2, 'this': 2, 'this book': 1, 'in this': 1, 'book the': 1, 'most interesting': 1, 'really the': 1, 'sentence in': 1, 'is really': 1, 'sentence is': 1, 'is the': 1, 'interesting the': 1, 'this is': 1, 'the most': 1})

Answer 3

Когда я сталкиваюсь с этой проблемой, я думаю: «Я знаю, я буду использовать регулярные выражения».

Начните с составления списка всех паттернов, отсортированных по убыванию длины:

patterns = sorted(counts.keys(), key=len, reverse=True)

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

allPatterns = re.compile("|".join(patterns))

Теперь запустите этот шаблон над входной строкой и подсчитайте количество совпадений для каждого шаблона по ходу:

pos = 0
while (True):
    match = allPatterns.search(inputString, pos)
    if (match is None): break
    pos = match.start() + 1
    counts[match.group()] = counts[match.group()] + 1

В итоге вы получите количество каждой строки.

(Кроме того: я полагаю, что большинство хороших библиотек регулярных выражений скомпилируют большое чередование по фиксированным строкам, подобным этому, используя алгоритм Aho-Corasick, о котором упоминал e.dan. Использование библиотеки регулярных выражений, вероятно, самый простой способ применения этого алгоритма .)

С одной проблемой: где шаблон является префиксом другого шаблона (например, «первое» и «первое предложение»), только более длинный шаблон будет иметь счет против него. Это по замыслу: для этого и была сортировка по длине в начале.

Мы можем рассматривать это как этап постобработки; Пройдите подсчет, и всякий раз, когда один шаблон является префиксом другого, добавьте счет более длинного шаблона к более короткому шаблону. Будьте осторожны, чтобы не добавить дважды. Это просто сделано как вложенный цикл:

correctedCounts = {}
for donor in counts:
    for recipient in counts:
        if (donor.startswith(recipient)):
            correctedCounts[recipient] = correctedCounts.get(recipient, 0) + counts[donor]

Этот словарь теперь содержит фактические значения.

Answer 4

Просто пройдите строку и используйте словарь, как обычно, чтобы увеличить любое вхождение.Это O (n), так как поиск по словарю часто O (1).Я делаю это регулярно, даже для больших сборников слов.

Answer 5

Попробуйте использовать Дерево суффиксов или Три для хранения слов вместо символов.