@Bangybug
tinker

Есть ли в python готовый алгоритм для нахождения часто встречающихся последовательностей?

Ищу алгоритм в около-Python, который по набору слов выделит наиболее часто встречающиеся части максимальной длины, либо наперёд заданной длины.

Например, вот слова (их гораздо больше): BSNREORG, BSNWA010,
На выходе хочу что-то вроде этого: BSN (встречается в 100% случаев), REORG (50%), WA010 (50%).
  • Вопрос задан
  • 167 просмотров
Решения вопроса 1
longclaps
@longclaps
Слово длины n содержит (n+1)*n/2 непустых подстрок, на тексте из m слов верхняя оценка - m*(n+1)*n/2 разных подстрок.
Задача PN-полная (ну то что ты написал - вообще черте-что, а не задача - что за хрень "наиболее часто встречающиеся" и как оно соотносится с "максимальной длины"?), так вот, задача решается полным перебором.
Морда не треснет?
ps вот грязненький код, который ищет максималные подстроки, встречающеся хоь в паре слов. Ужас-ужас.
from collections import defaultdict
from pprint import pprint

data = [w.strip() for w in "BSNREORG, BSNWA010".split(',')]
alphabet = set(c for w in data for c in w)

nxt = {}
for c in alphabet:
    tmp = [w for w in data if c in w]
    if len(tmp) > 1:
        nxt[c] = tmp
pprint(nxt)
while nxt:
    cur, nxt = nxt, defaultdict(set)
    for k, v in cur.items():
        for c in alphabet:
            for pattern in {k + c, c + k}:
                nxt[pattern].update(w for w in v if pattern in w)
    nxt = {k: v for k, v in nxt.items() if len(v) > 1}
pprint(dict(cur))
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
думаю нужно для этого использовать библиотеку которая этого предназначена - NLTK
тут есть кучка примеров, посмотрите и подберите что Вам больше подходит
Ответ написан
@Bangybug
tinker
Без перебора не обойтись, но его можно при необходимости ускорить.

Ваши оценки не совсем верны (к первой еще 1 добавить надо), но это не важно.

Мне казалось, всё-таки есть алгоритм разбиения последовательностей символов на части. Мне не обязательно чёткий алгоритм, поэтому я писал слово "вроде".

Посмотрю что удастся получить от гистограммы для последовательностей из двух букв на всём тексте.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы