Illeszkedő minták megtalálása

Algoritmusok

Sziasztok!

Biztos van sok megoldás a problémámra a neten, de én sajnos nem találtam. Az lenne a feladat, hogy megtaláljam sok minta közül azokat, amelyek az adott tételre illenek. A minták olyan reguláris kifejezések, ahol csak a '.'-ot lehet használni (tehát karakterenként megadható, hogy bármi vagy egy adott érték lehet).
Kb. 300 minta lesz, és 10 karakter. Van annál gyorsabb módszer, hogy végignézem mind a 300-at egyesével?

Köszi,
Gábor

  • 6079 megtekintés

( zamboriz v | 2012. 09. 03., h – 11:52 )

Rengeteg lehetőség van. A részletek ismerete nélkül felelőtlenség módszert ajánlani.

( joco01 v | 2012. 09. 03., h – 12:24 )

Szerintem pár millió tételig a 300 minta * 10 karakter ellenőrzése villámgyors minden további nélkül.

Egyébként tudni kellene, hogy mi alapján lehet leginkább szórni. Mivel erről semmit nem írtál, kb. semmit nem tudunk segíteni. Pl. építhetsz a minták karaktereiből döntési fát információtartalom alapján, de lehet, hogy a mintáid alapján ez átlagban ugyanannyi vagy több lépés lesz, mint trükközés nélkül.

Illetve egy-egy minta vizsgálatát lehet gyorsítani: http://en.wikipedia.org/wiki/String_searching_algorithm

--
joco voltam szevasz

Naponta egyszer fog futni a program és kb. 1 millió tételt kell végignéznie. Én is erre jutottam, hogy az a leggyorsabb, ha simán végiggyalogolok.
Nem akartam bonyolítani a kérdést, de lesz a mintáknak prioritása, és a legnagyobb prioritású illeszkedést kell megtalálnom, tehát berendezem a szerint és az első találatnál le is állhatok a kereséssel.
A döntési fát még meggondolom.

( lx | 2012. 09. 03., h – 12:12 )

Ahogy a többiek írták, kevés az info.
Hogy mégis konkrétumot sugalljak: ha a mintáid első/utolsó 1-2 karaktere stabil (karakter vagy tartomány és nem .), ÉS azonosítható pozíción kéne szerepelniük (sor vagy mező eleje/vége), akkor valószínűleg (nem mindig) érdemes előbb ezt a részmintát keresni, és az illeszkedő sorokban finomítani, a nem illeszkedőket meg el lehet dobni, és nem kell rájuk erőltetni párszáz felesleges próbát.

Depends...

A minták még nincsenek meg. Olyasmire gondoltam, hogy csinálok egy 300x10-es mátrixot és bepipálgatom a találatokat karakterenként, aztán kiválasztom azokat a mintákat ahol csupa pipa van, de ennél gyorsabb simán végiggyalogolni. A pipálgatós módszer sem lenne rossz, ha mondjuk be lenne rendezve a 300 minta 10 példányban, minden karakterre külön-külön, így csak a végén kellene végiggyalogolnom a tömbön hogy megkeressem a 10 pipás mintát. Vagy ha egy külön tömbben nyilvántartanám az első karakter után még ki játszik, és így szűkíteném a kört karakterenként...

Ez ugyanaz az algoritmus: http://en.wikipedia.org/wiki/Bitap_algorithm?
Az a baj, hogy ha a 300x10-es mátrixban kell keresnem egy fix értéket és abban nincs semmilyen rendezés, minimum egyszer végig kell mennem rajta ('preprocessing phase' tételenként le kell hogy fusson).
Egyébként köszönöm, a bit-tömb jó ötlet.

( Beanie | 2012. 09. 03., h – 15:07 )

Feltételezem, hogy sor alapú illesztésre van szükség, tehát a pont nem jelölhet \n karaktert. Veszed mintánként a leghosszabb fix részt, tehát amiben nincs pont. Ezekre alkalmazod a Wu-Manber algoritmust, ha találsz egy illeszkedést, akkor az adott sort elkülöníted és erre hívod meg a saját összehasonlító függvényedet, ami kezeli a pontot (azért ezt, mert ez gyorsabb, mint egy regex matching). Ez persze akkor alkalmazható, ha a leghosszabb fix részek elég hosszúak. Legalább 3-4 kellene, hogy legyen ahhoz, hogy érdemes legyen így leimplementálni. Ennek a megoldásnak az előnye, hogy nem kell karakterenként olvasni, mivel a Wu-Manber többet is ugorhat egyszerre és a sorokkal sem kell törődni addig, amíg nincs egy potenciális illeszkedés. Legegszerűbb, ha a fájlt mmap()-pal nyitod meg és nem kell sorokra bontani, csak arra kell figyelni, hogy ne olvass túl.

Köszönöm, megnéztem ezt a Wu-Manber algoritmust. Ha jól értem ennek az a lényege, hogy folyó szövegben keres párhuzamosan több minta szerint. Nekem erre nincs szükségem, mert fix karakterszámmal dolgozom. A feldolgozandó tétel és a minták is a memóriában lesznek. Az eljárás ciklusban hívódik, ahol a tétel változik, a szabályok pedig végig állandóak.
A gyalogos módszer elég gyorsnak tűnik, egyelőre marad az.

Ja, ertem, az nem volt nekem vilagos, hogy an input is fix hosszu, nemcsak a mintak. Esetleg az, hogy elso karakter szerint indexeled a mintakat, es azokat, amik az elso karakternel illeszkednek (egyezo karakter vagy pont a mintaban) beteszed valamilyen halmaz strukturaba, majd minden lepesben nezed a kovetkezo karaktert ugy, hogy vegigiteralsz a tombon, es ha nem egyezik a karakter, vagy nem pont, akkor kidobod. Ha valaha kiurul a tombod, akkor nincs egyezes. Az elejen az indexeles akkor hatasos, ha ezzel sok mintat kidobsz, pl. ha sok kezdobetu lehet es ezek kozel egyenletesen oszlanak el. De tenyleg jo lenne tudni a mintak statisztikai eloszlasat, mert azzal lehet jobban spekulalni, hogy hogyan erdemes.

( horvatha | 2012. 09. 03., h – 16:05 )

Egy amatőr ötlet, amit gyorsan lehetne implementálni, és ha a minták közt van hasonlóság, gyorsítana:

1) A mintákból egyetlen regexpet kreálni, mely 10 karakteres és mindegyik pozíción felsorolja az összes karaktert, ami valamelyik mintában előfordult, vagy a "."-ot, ha valahol abban a pozícióban "." volt.

2) A nagy adattömböt ezzel az egy regexppel megszűrni.

3) Az előző szűrés eredményére ráengedni az összes mintát.

No, ez persze sokszor csak felesleges munka, pl. ha mindegyik pozíció olyan, hogy valamely mintában van ott ".". De ha a mintákban van valami szabályosság, akkor a 2. pont egy sokkal kisebb fájlt eredményez, amiben aztán gyorsan lehet egyesével keresni.

De nem gondoltam át, lehet, hogy ez az előszűrés az esetek többségében csak felesleges munka, mert alig szűr ki valamit.