regulární výrazy

Odpovědět
daton
Příspěvky: 664
Registrován: 16 bře 2013, 16:12

regulární výrazy

Příspěvek od daton »

Zdravím všechny
měl bych dotaz ohledně možností ESP 8266 nebo 32.
Bylo by čistě hypoteticky možné naprogramovat esp tak aby fungoval jako filtr pro procházejicí kod? Něco jako třeba náhrada procházejících výrazu (obdobu regulárních výrazů ve win či linuxu). Bylo by obtížné naprogramovat to tak aby text (kód) který je nutno v procházejícím kodu nahradit byl jednoduše přístupný a nemusel se vkládat do hlavní funkce??
Rychlost procházejícího kodu by měla být kolem 500kb.
Jak náročné na programování by to bylo?
Dík za odpověd.
Uživatelský avatar
gilhad
Příspěvky: 262
Registrován: 29 kvě 2015, 00:36
Kontaktovat uživatele:

Re: regulární výrazy

Příspěvek od gilhad »

čistě hypoteticky by to jako filtr naprogramovat samozřejmě šlo
obdoba regulárních výrazů - pro hrubou představu v pythonu má knihovna pro regulární výrazy asi 2.5 tisíce řádků a kdoví co ještě všechno dalšího používá - ale je otázka, jestli potřebuješ "regulární výrazy v plné palbě", nebo ti stačí "něco jako" a co všechno by to "něco jako" mělo umět. Vzhledem k dalšímu stejně to budeš chtít jako knihovnu, která bude mít kód ve FLASH (stejně jako zbytek programu), ale za běhu bude potřebovat používat RAM
jednoduše přístupný - můžeš ho za běhu ukládat do RAM nějakým příkazem (nebo signálem na pinu, nebo ...) a pak používat na ten procházející kód (jenže ti to sežere další RAM, takže jde o to, kolik těch filtrů budeš potřebovat a jak dlouhé)
Rychlost procházejícího kodu pro jednoduché záměny by to asi šlo rozumně, otázka je, jak složité (a kolik) těch pravidel bude. A každý ten filtr, dokud nebude jasné, že se nedá aplikovat, bude potřebovat, abys někde v RAM držel to, co zrovna testuje (takže pravidlo "s/A.*B/XX/" (A cokoli jakkoli dlouhé B nahraď za XX) klidně může u blbého souboru, co začne A a nebude v něm B potřebovat držet celý ten soubor, aby nakonec zjistilo, že se neuplatní. Přičemž pokud budeš filtrovat obecný vstup, tak ti tam klidně můžou téct (a tedy se kumulovat) třeba Terabyty a to nedáš. Naopak "s/A.{3,5}B/XX/" (A 3-5 něčeho B nahraď za XX) bude potřebovat držet asi tak 7 bytů, než se rozhodne jestli ano nebo ne.)
Což ti tu rychlost taky ovlivní, protože dokud bude nějaké pravidlo "v akci", tak nemůžeš vysílat, protože nevíš, jestli se uplatní, nebo ne a jestli teda budeš vysílat nový nebo původní obsah. Až se to rozhodne, tak to můžeš vyslat plnou rychlostí, ale při víc a častěji používaných pravidlech to bude trpět hroznou škytavkou, kdy na jedné straně budeš číst jak rychle vysílač vysílá, pak to budeš sušit u sebe a pak to budeš posílat jak rychle to přijímač přijímá. (a buď bude ten přijímač výrazně rychlejší a pak bude dostávat HRCDATA pauza HRCDATA, nebo ten vysílač bude muset čekat, než to přešrotíš a přijímač ti uvolní výstupní frontu - a nebo to bude tak malé a jednoduché, že to pokryješ bufferem a zpracuješ za plného chodu, zatímco se ti bude plnit vstupní buffer a vyprazdňovat výstupní )
Jak náročné na programování by to bylo? No, záleží na tom, co si od toho slibuješ a co ne, může to být celkem jednoduché až celkem neřečitelné a cokoli mezi tím - čistě hypoteticky - jak už to u čistě hypotetických otázek bez nějakých podkladů bývá

Navíc pokud bys něco věděl předem o struktuře těch dat a těch záměn, tak se možná dá udělat řada zjednodušujících triků a vtipně si navrhnout to "něco jako" aby to nebylo zbytečně obecné a víc ti to hrálo na ruku

prakticky nějaké věci by šly snadno, nějaké ne, ale na to jsi nedodal dost údajů
daton
Příspěvky: 664
Registrován: 16 bře 2013, 16:12

Re: regulární výrazy

Příspěvek od daton »

Moc díky za zajímavé náměty. Tak že asi bych měl být trochu konkrétnější aby bylo možné trochu více o tom diskutovat. Jednalo by se asi o Dvacet znaků co jdou po sobě v konkrétní sestavě. Tato sekvence by mohla být rozpoznána už v prvních pěti znacích. Těch dvacet znaků se bude opakovat. Problém je že ta komunikace je obustranná tedy něco jako dotaz od jednoho zařízení což by mělo téci přes filtr bez úprav a odpověd což by měl právě filtr zachytit a zaměnit tu sekveci. Tento proces by se měl opakovat asi 10x. sekvence bude vždy stejná a měla by být spolehlivě nahrazena.
Je to již konkrétnější natolik aby bylo možné více odhadnout složitost a moznost vytvoření kodu? Děkuji
Uživatelský avatar
gilhad
Příspěvky: 262
Registrován: 29 kvě 2015, 00:36
Kontaktovat uživatele:

Re: regulární výrazy

Příspěvek od gilhad »

To vypadá, že by mělo jít celkem snadno (teda podle toho, co s tou sekvencí hodláš dělat, pokud ji jen zaměnit za nějakou konstantní, nebo oblozit necim, tak je to snadne, kryptograficky ji lamat je nesnadne) :D

Da se to jeste ruzne optimalizovat, podle toho jakeho zpusobu budou ty zameny, rekneme ze hledana sekvence je "NAZEV:nejaka hodnota;" a pozna se to, ze to zacina NAZEV a konci strednik

tak menit to na "NAZEV: BRAMBORA;" je jednoduche a zcela bez zdrzeni (az na rozdil delky nejake hodnoty a BRAMBORY)
"POPIS:nejaka hodnota NECO DALSIHO" je uz trochu slozitejsi a zadrhne se to na bufferovani toho NAZEV
"POPIS: dvojnasobek nejake hodnoty JESTE NECO" je jeste slozitejsi a zadrhne se to na cely ten hledany vyraz

ale s tou delkou 20 to je vsechno v principu jednoduche a melo by to jit napsat nejak neprilis slozite a dost rychle na to, aby to pricetna zarizeni uspokojilo
(taky zalezi na tom, jak je to protizarizeni citlive na plynulost vysilani, ale i s tim se daji delat triky)
daton
Příspěvky: 664
Registrován: 16 bře 2013, 16:12

Re: regulární výrazy

Příspěvek od daton »

Ještě jsem se chtěl zeptat jak správně a co nejrychleji porovnávat znaky přemýšlel jsem ze bych po jednom znaku přidával a zároveň ubiral z pěti znaku a ty jako skupinu porovnávat s se skupinou kontrolní. Jen jsem se chtěl zeptat jak korektně porovnávat skupiny znaku kde jsou písmena i čísla (alespoň v nahrazovánem kodu) a můžou tam byt i ostatní znaky z kodu.
Diky
Uživatelský avatar
fulda
Příspěvky: 1359
Registrován: 04 led 2016, 17:18

Re: regulární výrazy

Příspěvek od fulda »

daton píše: 16 zář 2021, 19:00Ještě jsem se chtěl zeptat jak správně a co nejrychleji porovnávat znaky.
{cut}
ne že bych úplně přesně rozuměl tvému návrhu algoritmu. Ale jak správně hledat podřetězec v řetězci (textu) jako náhodou vím.
Tedy bezpečně ovládám dva algoritmy (a s tím jsem si většinou vystačil)

První algoritmus vypracoval František Brute a Jiří Force. Na jejich památku se označuje jako Brute-Force search. Prostě vezmeš znak z textu a podíváš se, jestli je stejný jako první hledaný znak. Pokud je, podíváš se, jestli i následující znak je stejný jako druhý hledaný znak... a tak dále, až ověříš všechny znaky.

Na druhém algoritmu pracovali společně Robert Boyer a J Strother More a tak se na jejich počest označuje jako Boyer-More search. Tady potřebuješ nějaký čas na přípravu a víc paměti, ale zase dostaneš dramaticky rychlejší hledání. Proto se používá při prohledávání opravdu dlouhých textů. Potřebuješ tabulku všech znaků (většinou pole 256 integerů; v unicode je to trochu víc) celé pole si vyplníš hodnotou délky "podřetězce". Teď vezmeš "podřetězec" od konce a díváš se na jednotlivé znaky. na pozici v poli, která odpovídá tvému znaku, vložíš obrácenou hodnotu počtu znaků od začátku. Takže pátý znak od začátku dostane hodnotu -4, znak na samém začátku dostane hodnotu 0 a tak dále. Pokud j znak v podřetězci několikrát, počítá se pozice blíž k začátku. Když máš pole vyplněné, můžeš začít prohledávat. Prostě vezmeš první znak z dlouhého textu a podíváš se do tvého pole, jakou u něj máš hodnotu. Pokud je nenulová, prostě přičteš hodnotu k aktuální pozici a o tolik poskočíš. Pokud je hodnota nula, tak máš první znak z podřetězce, čili se podíváš na prostou schodu následujícího a dalšího znaku. Pokud se neschodují, posuneš se o jednu a pokračuješ.

... a víc se mi psát nechce, když je to na wiki.
... a stejně nakonec použiješ "substr"
Za pravopisné chyby v této zprávě může moje učitelka češtiny.
DavidO
Příspěvky: 1133
Registrován: 01 kvě 2013, 21:27

Re: regulární výrazy

Příspěvek od DavidO »

Akorát teda Franta s Jirkou musejí jít pomalu, protože když se jim to někde začne neshodovat, musejí jít ne odsud, ale posunout se na vstupu jen o jeden znak od původního začátku. Jinak by třeba v řetězci AAAB podřetězec AAB nenašli, protože u třetího áčka na vstupu se to shodovat přestane (má tam být B), ale kdyby jen pokračovali od aktuálního (3.písmeno) nebo dokonce nedejbože dokonce příštího znaku (4.písmeno), tak to taky nenajdou. Musejí jít znovu od 2. písmene.
Nikoho plánovaně neurážím. Jestli se Vám nelíbí co píšu, tak to nečtěte. A ostatně, třeba za to nemůžu - Researchers believe that dark humor can be a significant symptom of dementia.
Odpovědět