@Bangybug
tinker

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

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

Например, вот слова (их гораздо больше): BSNREORG, BSNWA010,
На выходе хочу что-то вроде этого: BSN (встречается в 100% случаев), REORG (50%), WA010 (50%).
  • Вопрос задан
  • 149 просмотров
Решения вопроса 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
Ваш ответ на вопрос

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

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