Regex pattern kitalálóka

Algoritmusok

Párszor már beleakadtam ebbe a problémába, de most nagyon jó lenne 1 ilyen tool: Van 1 csomó string-em, amire meg kéne találni azt a regex pattern-t ami a lehető legszigorúbb és minden megadott stringre illeszkedik. Van erre kész megoldás, illetve hogy kéne nekiállni?

Igazából az a feladat, hogy:

  • a lista 1 része meccsel regex1-re,
  • a lista másik része meccsel regex2-re,
  • Kéne egy 3-ik regex, amire a maradék meccsel,
  • illetve a maradékból menyi az, amire regex3 mégsem meccsel.

Mondjuk úgy, hogy a nem well-formed stringeket kéne megtalálni és ez tényleg az a 2 legyen a nagyonsokból, amit biztosan javítani kell kézzel.

Ötlet, tipp, bármi?

  • 558 megtekintés

( gabrielakos v | 2021. 03. 23., k – 07:23 )

Ennek a meghatározásnak így nincs értelme mert bármi két regexet vagy-al összekapcsolsz, az is regex.

Például: (a|b)

Definiáld mi az ami well-formed, arra tudsz kapni egy regexet.

Az, hogy "mennyire nem well-formed" a többi, az első körben érdektelen.

Pont az az érdekes, ami nem well-formed, azok a problémásak. És a kiveszem az összesből a jókat és a maradék az hiba, az se jó megközelítés, mert nem a problémára válaszol. Pl.
 

van 1 csomó regex-em, amivel inputot validálok,
rendszeresen átcsúsznak invalid tételek, amik később problémát okoznak,
jó lenne egyszerűen bővíteni az input filtereket.

( K3cs1 | 2021. 03. 23., k – 07:38 )

Kész megoldást nem tudok, de Javaban ez nem tűnik túl komplikáltnak.

Kell egy List<String> amin végigiterálsz és hívogatod a Stringeken a metódust ami végigpróbálja mindhárom Matcher -el, hogy matches() -e. Ha egyikre sem machel a String, akkor azt gyüjtöd egy másik listába.

Bővebben.

Feltéve, ha jól értettem meg azt, amit szeretnél.

Vagy bedobni az összes stringet egy szövegfájlba, aztán

sort fájl | uniq | grep -v regexp1 | grep -v regexp2 | grep -v regexp3 > javítandók

disclaimer: ha valamit beidéztem és alá írtam valamit, akkor a válaszom a beidézett szövegre vonatkozik és nem mindenféle más, random dolgokra.

( peterson v | 2021. 03. 23., k – 07:57 )

Nem értem. A 3. regex, ami meccsel mindenre amire első kettő nem, az a teljes halmaz, kivéve az első kettő feltételeit. Ebben minden benne lesz, ami nem meccsel az első kettőre egyikére sem. Elméletileg nem lesz olyan, ami nem meccsel egyikre sem a háromból.

Vagy félreértek valamit...

"A megoldásra kell koncentrálni nem a problémára."

( bucko | 2021. 03. 23., k – 08:17 )

Van ilyen tool!

Úgy hívják awk és program, amit meg kell írni.

A problémád tipikus addattisztítási feladat:

  • kell egy minta, amire illeszkednek az 1. típusú rekordok
  • kell egy minta, amire illeszkednek az 2. típusú rekordok/a maradék
  • kell egy minta, amire illeszkednek az 3. típusú rekordok/a maradék
  • megnézzük mi maradt
    • utána esetleg újabb minta, vagy
    • javító algoritmus
  • loop, amíg el nem fogynak a rekordok vagy a hiba mennysége kellő mértékben csökken

Egyes esetekben lehet javító szótárat építeni. Pl.:

"well-formed"=Budapest ->szótárba (persze ilyen már van)

A megtalált hibák alapján kialakulhat egy szótár sor: Budapest,budappest,BudiPest,budoPest

Itt az első trükk a nagybetűsítés!!

A szótár sorokból készül egy regexp szótár (tömb). Ha az Input nagybetűsített elem megegyezik a szótár bármely elemével, akkor találat. Ilyenkor az erdeti inputot cseréljük a szótár sor fő elemére. Ha változott, akkor hiba++.

A maradék nincs a szótárban - pl. Csepel. ;) Szemrevételezés után csaphatjuk a javító szótárhoz: BUDAPEST=Budapest,budappest,BudiPest,budoPest,Csepel

Aztán loop.

Az élet nem oneliner. ;)

Van olyan program, ami kitalálja még a gondolatodat is. Csak most nem jut eszembe. ;)

A szemrevételezés nem az, hogy a maradék 10M rekordot megnézem. Elég néhány darabot, amiből újabb szabályt lehet lérehozni.

A való világ tud létrehozni érdekes eseteket is. Íme egy cím: Budapest Miskolc Wien, Kossuth utca 3. Erre mit lépne a MI?

A fent leírt módszerrel közel 100% pontossággal lehet javítani, bár nem tudom miben mesterkedsz.

Erre idézem magam

loop, amíg el nem fogynak a rekordok vagy a hiba mennysége kellő mértékben csökken

Ha tényleg adattisztításról van szó, akkor bizony van egy határ, amikor már elfogynak a javítási lehetőségek. A megmaradt eseteket vissza kell dobni az adatforrásnak javításra. (adatpontosítás) Fel lehet mérni azt is, hogy a részlegesen javított adatok felhasználhatók-e.

További lehetőség az esetlegesen ellentmondó vagy hiányos adatok más algoritmussal végzett kiegészítése vagy kijavítása. De ehhez már tényleg tudni kellene mit csinálsz. A regexp is algoritmus, de tudni kell mit csinálsz.

Adott esetben az adatok keletkezésének folyamatát és forrását is érdemes ismerni. Persze néha előfordulhat az "adatbányászás a semmiből" konstelláció is. Ha ezeket fel lehet mérni, akkor akár vissza is dobható a feladat, mint reális költséggel megvalósíthatatlan. Ilyen munkát is láttam már...

( mraron | 2021. 03. 23., k – 11:45 )

Esetleg építeni egy Aho-Corasickot építeni valamilyen random módon kiválasztott mintára majd azt redukálni regexppé.

( Zahy v | 2021. 03. 23., k – 12:49 )

Ezzel most nem nagyon fogsz tudni mit kezdeni, de van ilyen eszköz, kb az elmúlt fél évben jött szembe a neten. Már csak annyi kiegészítésként, hogy sem a szoftver nevére, sem az oldal címére nem emlékszem, de ha valahol elmentettem vagy beugrik, még jelentkezem. Valami regex teszter vagy hasonló, és pont az volt a leírás lényege, hogy legenerálja neked azt a mintát, ami pontosan a megadott elemekre fog meccselni.

Eddig ez lett:

https://regex-generator.olafneumann.org/

https://www.regexmagic.com/

tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?