Frekvenční analýza výskytu řetězce?

Frekvenční analýza výskytu řetězce?
« kdy: 12. 01. 2022, 14:41:41 »
co je nejlepsi nastroj pro zjisteni cetnosti patternu?

napriklad mam tabulku a   potrebuju zjistit 100 nejcasteji se vyskytujicich alfanumerickych stringu o 10 znacich (a pocet tech vyskytu).

moznost SQL query jsou hodne omezene ( a midleware to zabije na 3 dny), ale mam moznost vyexpertovat jeden log jako text
co je na tohle nejlepsi nastroj, vzit splunk? R?

BTW tohle je mimo moje knowhow, ale potrebuju to a mnoha hlavy indicky tym zasadne nic nedoda. uz jsem to zkousel escalovat, ale to by musel management pripustit, ze platit asi 50 "levnych" indu zbytecne, takze to je nepruchozi.


« Poslední změna: 12. 01. 2022, 17:25:39 od Petr Krčmář »


Re:Frekvenční analýza výskytu řetězce?
« Odpověď #1 kdy: 12. 01. 2022, 17:40:16 »
něco takovýho? https://cran.r-project.org/web/packages/bpa/vignettes/introduction.html
pro r je dobrý si nainstalovat rstudio
Gréta je nejlepší.

Re:Frekvenční analýza výskytu řetězce?
« Odpověď #2 kdy: 12. 01. 2022, 19:10:32 »
a kolik dat v db tabulce je?
nebo jak je velky vyexportovany textovy log?

mate k dispozici vice stroju, ze by slo praci rozsekat ukol na n samostatnych pocitacu.
podobne by to slo udelat jako viceprocesove, vicevlaknove zpracovani.

1) nejprve bych log prohnal filtrem na 10 znakove slova.
2) pak bych zacal plnit vhodnou strukturu kde by slo rychle vyhledat zda slovo uz existuje pripadne slovo vlozit (mapa, strom, apod.)
3) v datove strukture (2) bych vyhledal slovo a zvysil counter pokud uz tam slovo je nebo ho vlozil, pokud se slovo objevilo poprve.

_Jenda

  • *****
  • 1 064
    • Zobrazit profil
    • https://jenda.hrach.eu/
    • E-mail
Re:Frekvenční analýza výskytu řetězce?
« Odpověď #3 kdy: 13. 01. 2022, 00:57:38 »
mate k dispozici vice stroju, ze by slo praci rozsekat ukol na n samostatnych pocitacu.
Jak se tohle paralelizuje? Podle mě bude bottleneck velikost paměti, protože těch možných stringů je… hodně (64**10, resp. 10*velikost_vstupních_dat). Pokud jsou statisticky hodně nerovnoměrně rozdělené (což v „lidském textu“ jsou), tak by to možná šlo nejdřív předfiltrovat třeba počítáním 32bit hashů těch substringů (nějaké zkolidují) a v druhé fázi počítat jenom ty co se zahashovaly do bucketů kde toho je nejvíc.

Re:Frekvenční analýza výskytu řetězce?
« Odpověď #4 kdy: 13. 01. 2022, 07:51:35 »
nejdriv bych zkusil trivialne

Kód: [Vybrat]
from collections import Counter

def chunks(s, n=10):
    for i in range(len(s)):
        yield s[i:i + n]

c = Counter()

for s in zdrojdat():
     c.update(chunks(s))

print(c.most_common(3))

zalezi, jestli to potrebujes jen jednou, nebo chces vysledky drzet v databazi

Pokud je tech dat opravdu hodne, typicka uloha pro mapreduce
« Poslední změna: 13. 01. 2022, 07:57:13 od A.P.Hacker »


Re:Frekvenční analýza výskytu řetězce?
« Odpověď #5 kdy: 13. 01. 2022, 08:42:46 »
mate k dispozici vice stroju, ze by slo praci rozsekat ukol na n samostatnych pocitacu.
Jak se tohle paralelizuje? Podle mě bude bottleneck velikost paměti, protože těch možných stringů je… hodně (64**10, resp. 10*velikost_vstupních_dat). Pokud jsou statisticky hodně nerovnoměrně rozdělené (což v „lidském textu“ jsou), tak by to možná šlo nejdřív předfiltrovat třeba počítáním 32bit hashů těch substringů (nějaké zkolidují) a v druhé fázi počítat jenom ty co se zahashovaly do bucketů kde toho je nejvíc.

ano, přesně takhle se to paralelizuje, spočítaj se postupně kolidující stringy (buď využití hashe nebo v případě stejné délky řětězců jdeš postupně po písmenech) a přiděluješ jednotlivé prefixy nějakému výpočetnímu procesu. Frekvenční analýza je aditivní výpočet, lze tedy počítat postupně a připočítávat mezivýsledky, dobře se to paralelizuje.