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

Question

[Дима Прядкин]

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

Например, вот слова (их гораздо больше): BSNREORG, BSNWA010,
На выходе хочу что-то вроде этого: BSN (встречается в 100% случаев), REORG (50%), WA010 (50%).

Comments

[Сергей Горностаев]

Что вы подразумеваете под "части"?

[Дима Прядкин]

Например, вот слова (их гораздо больше): BSNREORG, BSNWA010,
На выходе хочу что-то вроде этого: BSN (встречается в 100% случаев), REORG (50%), WA010 (50%).

Answer 1

[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))

Comments

[Дима Прядкин]

Спасибо что уделили время. Действительно я плохо поставил задачу, не нужно было вообще писать про "максимальную длину".

Я родил вот такой велосипед:

%matplotlib inline

import matplotlib
import numpy as np
import matplotlib.pyplot as plt
    
def getBigrams(word):
    bigram = ""
    bigrams= []
    for i in range ( len ( word ) ):
        bigram += word[i]
        if (len(bigram) == 2):
            bigrams.append(bigram)
            bigram = word[i]
    return bigrams

def buildBigramHistogram(words):
    bigramOccurence = {}
    for word in words:
        for bigram in getBigrams(word):
            if bigram not in bigramOccurence:
                bigramOccurence[bigram] = 0
            bigramOccurence[bigram] = bigramOccurence[bigram]+1

    for bigram in bigramOccurence:
        bigramOccurence[bigram] = bigramOccurence[bigram] / len(bigramOccurence)
    return bigramOccurence

def accumulateAverageBigramOccurenceCurve(bigramOccurence,word):
    y = []
    x = []
    k = 0
    bigrams = getBigrams(word)
    for bigram in bigrams:
        if k == 0: 
            accumulatedOccurence = bigramOccurence[bigram]
        else:
            accumulatedOccurence = (k-1)/k*accumulatedOccurence + bigramOccurence[bigram]/k;
        x.append(k)
        y.append(accumulatedOccurence)
        k = k + 1
    return { "x":x, "y":y, "bigrams":bigrams }

def findCurveSteps(y, threshold=0.001):
    ret = []
    yi = y[0]
    lastPeak = None
    length = len(y)
    for i in range(length):
        if (abs( y[i] -  yi ) > yi*threshold):
            ret.append(i) 
        yi = y[i]

    return ret


def splitWordByCurve(word, curve, threshold=0.001):
    prevStep = 0
    steps = findCurveSteps(curve["y"], threshold)
    steps.append( len(curve["y"])-1 )
    
    segments = []
    for step in steps:
        if (prevStep != step):
            segments.append([prevStep, step, ""])
            prevStep = step
    
    segments.sort(key=lambda seg: min(curve["y"][seg[0]], curve["y"][seg[1]]), reverse=True)
    
    token = []
    for i in range(len(word)):
        token.append('')
        
    for seg in segments:
        start = seg[0]
        stop = seg[1]
        
        if (stop == len(curve["y"])-1):
            stop = stop + 1
        if (token[start]):
            start = start + 1
        if (token[stop]):
            stop = stop - 1
        
        seg[2] = word[start:stop+1]
        
        for i in range(start,stop+1):
            token[i] = seg[2][i-start]
    
    segments.sort(key=lambda seg: seg[0])
    return list(map(lambda seg: seg[2], segments))


#
# Start
#

words = ["BSNREORG", "BSNWA010","ABSN"]

bigramOccurence = buildBigramHistogram(words)
    
plt.bar(list(bigramOccurence.keys()), bigramOccurence.values(), color='g')
plt.show()

# examine accumulated average character occurence rates in each word
for word in words:
    curve = accumulateAverageBigramOccurenceCurve(bigramOccurence,word)
    tokens = splitWordByCurve(word,curve,threshold=0.1)
    
    print("Word: ",word, tokens)
    plt.bar(curve["x"], curve["y"], color='b')
    plt.xticks(curve["x"], curve["bigrams"])
    plt.show()

Он возвращает такие разбиения:

BSNREORG ['BSN', 'R', 'EORG']
BSNWA010 ['BSN', 'W', 'A010']
ABSN ['A', 'BSN']

Смотрел ещё nltk.FreqDist, но там приходится жёстко задавать длину находимых последовательностей.

Answer 2

[Владимир]

думаю нужно для этого использовать библиотеку которая этого предназначена - NLTK
тут есть кучка примеров, посмотрите и подберите что Вам больше подходит

Comments

[Дима Прядкин]

Спасибо, смотрел - мощная штука. До этого не знал что есть термин n-grams. Уже успел написать велосипед - в комментарии к первому ответу.

Answer 3

[Дима Прядкин]

Без перебора не обойтись, но его можно при необходимости ускорить.

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

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

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

Comments

[longclaps]

см апдейт ответа