× Kötetlen, játékon kívüli témák

normal Segítségkérés játékon kívül

Több
7 éve 5 hónapja #5493

Szövegre kell? Vagy DNS szekvenciákhoz?


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5497

Dögrovás írta: Szövegre kell? Vagy DNS szekvenciákhoz?

Nyers szövegre..csináltam már belőle szekvenciát igazából


Up the Irons!
Utolsó szerkesztés: 7 éve 5 hónapja Írta: Ragingfist.

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5499

Na valahogy így néz ki:

Feldarabolod a 2 szöveget szavakra.
str1, str2
A mátrixod count(str1) x count(str2) -es lesz, a mátrix 0. sora és oszlopa 0-val van feltöltve.
A mátrix további elemei az alábbiak szerint töltődnek (bal fentről kezdve kell kitölteni):

Az [X,Y] hely értékének kiszámításához kell az [X-1, Y-1] értéke, ez módosúl a következők szerint:
Ha str1[X] == str2[Y] akkor növeled az [X-1, Y-1] értékét 2-vel, ha nem, akkor csökkented 1-el.
Ezen felül veszed az [X-1,Y] és az [X,Y-1] mezők értékét is, mindkettőt csökkented 1-1el. Az így kapott három érték közűl a legmagasabb lesz az [X,Y] helyen.

Az így feltöltött mátrix feldolgozása a következőképpen zajlik:
Mindíg a mátrix legmagasabb értékű pontjáról indul feldolgozás, minden esetben a [X-1,Y-1], [X-1,Y], [X,Y-1] mezők közül arra megy a feldolgozás tovább amelyiknek a legmagasabb az értéke. A bejárt mezőknek megfelelő szót (str1[X]) mindíg elrakja, ebből fog összeállni a két szöveg közti leghosszabb eggyezező rész (mindíg előre kell befüzni az eredmény stringbe).

Ez volt a kérdés? Vagy a matekjára vagy kiváncsi?


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5502

Ezzel amit te írtál negatív értékek lehetnek a mátrixban, de elvileg pont az lenne a lényeg, hogy ne legyenek, nem? Az elméletét szeretném megérteni leginkább, kérdésedre válaszolva.


Up the Irons!

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5503

Tudtommal lehet benne negatív, és a fentiekből látszik a lényege:
összehasonlítja a 2 szöveg szavait mindet mindegyikkel, Mivel mindíg az előző összehasonlítás eredményét növeli csökkenti, így a leghosszabb egyezés végén lesz a legnagyobb érték. Innen szépen visszalépked, és összerakja a sztringet. Addig megy visszafelé, amíg 0-t nem talál, vagy el nem fogynak a szavak.


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5504

The main difference to the Needleman-Wunsch algorithm is that negative scoring matrix cells are set to zero, which renders the (thus positively scoring) local alignments visible.


Ezt írták wikin, tehát akkor ami negatív simán 0-zni kéne, nem? Meg nekem vannak itt valami insert/delete súlyfüggvények is, ez lenne a +- 1?

+Bonus kérdés: mindig H[n+][m+1] lesz a legnagyobb értékű mező?


Up the Irons!
Utolsó szerkesztés: 7 éve 5 hónapja Írta: Ragingfist.

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5510

Igen feltöltéskor ebben az esetben ha <0 akkor 0-zni kell.
Az insert delete a következőt jelenti:
Ha nem átlóban halad a legnagyobb értéket követve a feldolgozás, az azt jelenti, hogy szó beszúrás, vagy szóhiány van az egyik str1-en. (ugye ha csak egyik irányba megy a feldolgozó nem átlósan -1,-1 irányba, akkor az egyik tengelyen azonos szón marad a következő vizsgálatkor is)
Ezért a feltöltéskor a [X-1,Y] mező értékét a Deletion, az [X,Y-1] mező értéket Insertion büntetéssel veszik figyelembe tehát így néz ki:

[X,Y] = max( ([X-1,Y] + Deletion), ([X,Y-1] + Insertion), [X-1,Y-1] + Match/Mismatch)

(én fentebb az Insertion, és Deletion büntetés értékét mindkettőt 1-re vettem):
4 fajta súlyozás van:
Match (ez az én példámban 2 volt)
Mismatch (ez -1)
Insert (ez -1)
Delete (ez is -1)

Mátrix

          EZ EGY PRÓBA SZÖVEG
      0    0  0    0     0
VAN-E 0   -1 -1   -1    -1
BENNE 0   -1 -2   -2    -2
EGY   0   -1  1    0    -1
PRÓBA 0   -1  0    3     2
0-zva:
          EZ EGY PRÓBA SZÖVEG
      0    0  0    0     0
VAN-E 0    0  0    0     0
BENNE 0    0  0    0     0
EGY   0    0  2    1     0
PRÓBA 0    0  1    4     3

Nem mindíg az utolsó mező a leganyobb értékű, lásd a fenti példát. A leghoszabb egyezés VÉGÉN lesz a legnagyobb érték, ez egyáltalán nem biztos, hogy a szövegek végére esik.


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…
Utolsó szerkesztés: 7 éve 5 hónapja Írta: Dögrovás.

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5513

Értem, ezek alapján megcsináltam a mátrixot, most fogok majd hozzá a tracebackhez. A súlyfüggvényeket viszont finomítanám, nem szimpatikus hogy mindegyik -1. Azt nem tudom, hogy hasraütés szerűen történik-e a változtatgatás, vagy ennek is van valami metodikája?


Up the Irons!

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5514

Attól függ milyen eredményt szeretnél kapni. Minél nagyobb a „büntetés” az adott függvényen, annál kevésbé fogja tolerálni az adott eltérést. Ha nagyokat vonsz le insert, delete-re, akkor rövidebb de teljesen azonos szövegek is bekerülhetnek. Ha nem túl nagy levonás van insert, delete-re, akkor egy két szó eltérés még bele fog férni, ha egyébként a szöveg egyezik.


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5515

Köszönöm, tiszta minden. Már csak a Java isten kegyére lesz szükségem :)


Up the Irons!

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 5 hónapja #5634

Nincs valakinek scribd acca véletlenül?Találtam pár könyvet, ami fenn van, és szívesen elolvasnám, de legalábbis problémás a dolog.

Kösz előre is!

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 4 hónapja #6012

Hátha valaki tud segíteni.
A kérdés az, hogy hogyan dönthető el GYORSAN két téglalapról, hogy van-e közös pontjuk. Mindkét téglalap élei 0 és 90 fokot zárnak be az X tengellyel. Adott a bal felső, és a jobb alsó sarkuk koordinátája. Fontos szempont a gyorsaság, tizedmásodpercenként többszáz összehasonlítást kell végezni. Csak olyan megoldás jöhet szóba, ami koordinátákkal dolgozik (tehát raszteren kitöltjük feketével az egyiket, ill másikat kékkel, és lesz-e közös rész nem játszik)


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 4 hónapja #6014

Dögrovás írta: Hátha valaki tud segíteni.
A kérdés az, hogy hogyan dönthető el GYORSAN két téglalapról, hogy van-e közös pontjuk. Mindkét téglalap élei 0 és 90 fokot zárnak be az X tengellyel. Adott a bal felső, és a jobb alsó sarkuk koordinátája. Fontos szempont a gyorsaság, tizedmásodpercenként többszáz összehasonlítást kell végezni. Csak olyan megoldás jöhet szóba, ami koordinátákkal dolgozik (tehát raszteren kitöltjük feketével az egyiket, ill másikat kékkel, és lesz-e közös rész nem játszik)

Legyenek az egyik téglalap (ezután A) bal felső sarkának a koordinátái (a_2, b_2) és a jobb alsónak (a_1, b_1), a másik téglalapnak (ezután X) pedig (x_2, y_2) illetve (x_1, y_1). Ezek alapján a_2<a_1, b_2>b_1, x_2<x_1 és y_2>y_1.

Vetítsd le a téglalapok oldalait a koordinátarendszer tengelyeire, és először dolgozzunk mondjuk csak az OY tengellyel.
Az A téglalap vetülete az OY tengelyre a i]b_1, b_2[/i zárt intervallum lesz, míg a B téglalapé az i]y_1, y_2[/i zárt intervallum. A két téglalapnak csak akkor lehet nem üres metszete, ha ez a két inervallum metszi egymást. Viszont ez pontosan akkor következhet be, ha egyszerre teljesülnek a b_2>y_1 és y_2>b_1 feltételek.

Ugyanígy, most nézzük az OX tengelyt, amelyen az i]a_2, a_1[/i és i]x_2, x_1[/i zárt intervallumokat kapjuk. A fenti gondolatmenet alapján annak feltétele, hogy a két téglalap metssze egymást az, hogy a_1>x_2 és x_1>a_2 egyszerre teljesüljön.

Nyilvánvaló, hogy a két téglalap akkor és csak akkor metszi egymást, ha a fent jelzett négy egyenlőtlenség egyszerre teljesül, vagyis

(b_2>y_1) és (y_2>b_1) és (a_1>x_2) és (x_1>a_2)

Megjegyzés: a feltételeid alapján érinthetik is egymást a téglalapok, vagyis fentebb > helyett >= kell mindenhova.

Utolsó szerkesztés: 4 éve 3 hete Írta: Dögrovás.

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 4 hónapja #6015

PFF automatikusan formázódtak a szögletes zárójeleim, amikkel az intervallumokat jelöltem. Érthető így?

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 4 hónapja #6016

Köszi, közben hasonlóra jutottam, bár kicsit olcsóbb (most fejeztem be az implementálást):
A két téglalapnak akkor és csak akkor van metszete, ha a mindkét téglalapot befoglaló legkisebb téglalap (fentiek szerint a min(a_2,x_2), min(b_2,y_2) és max(a_1,x_1), max(b_1,y_1) koordinátákkal leírt) megfelelő élhosszai rövidebbek mint a két vizsgálandó téglalap élhosszainak összege.

Azaz

( max(a_1,x_1)-min(a_2,x_2) < ( ( a_1 - a_2 ) + ( x_1 - x_2 ) ) ) ÉS ( max(b_1,y_1)-min(b_2,y_2) < ( ( b_1 - y_2 ) + ( b_1 - y_2 ) ) )


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 4 hónapja #6017

Frappáns megoldás, tetszik! :)
De nem lesz drágább implementálás szempontjából (bár csak két egyenlőtlenséget kell ellenőrizni, de számolsz néhány max. és min-t, meg több alapműveletet végzel)?

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 4 hónapja #6020

Szerintem nagyságrendilag azonos költsége van a két megoldásnak, min, max tulajdonképpen behelyetesíthető egy-egy egyenlőtlenséggel.
De lehet hogy az (((a_2+a_1)/2) - ((x_2+x_1)/2)) < ((a_2-a_1) + (x_2-x_1)) / 2 ) ÉS ((b_2+b_1)/2) - ((y_2+y_1)/2)) < ((b_2-b_1) + (y_2-y_1)) / 2 )) olcsóbb ezeknél, főleg, hogy a 2vel osztás elhagyható mindenhol. (Ez ugye azt mondja, hogy összeérnek, ha a két téglalap középontjainak X illletve Y koordinátában mért eltérése kisebb mint az adott irányú élhosszak átlaga)


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…
Utolsó szerkesztés: 7 éve 4 hónapja Írta: Dögrovás.

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 2 hónapja #8111

Az iránt szeretnék érdeklődni, hogy van-e itt bárki, aki - ha nem is érzi magát profinak - valamilyen szinten jártas a birkózás terén? Az angol szakkifejezések magyarításai érdekelnek, mivel a legtöbb magyar nyelvű oldalon csakis angol eredetiben találom meg őket, nekem viszont egy gyerekműsorhoz magyarul kellenének, mégsem akarok nagy hülyeségeket írni. Előre is köszi!

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 2 hónapja #8292

Háelló! Na, már két hete itt vagyok a messzi távolban, és mivel esténként nem tudok mit kezdeni magammal, valamilyen módon vissza akarok jönni hozzátok. A következőre gondoltam:
Egy ilyenen dolgozom jelenleg:
http://www.dell-shop.hu/134607_adatlap_dell_nb_latitude_e5520_156_hd_int.html

És vennék hozzá egy ilyet:
http://www.saturn.de/mcs/catentry/3-5-2000-GB-USB-3.0-Spaceloop,48352,252084,201495.html
Vagy egy ugyanilyet usb 2-vel. A kérdés az lenne, hogy egyrészt a laptop integrált VGA-ja elbírná-e a wowot (nem feltétlenül full hdban), mert valahol azt olvastam igen. A másik pedig az, hogy a külső winchesterről való bootolás mekkora teljesítményromlást okoz, játszható lenne-e. A fő probléma az, hogy a céges gépre nem tudok telepíteni semmi okosságot, max egy virtuális gépet, de ahhoz nincs elég háttértára, macerás, etc.

Na, a lényeg hogy jönnék márciusban sárkányt ölni, de kellenek a releváns vélemények.
Ragi


Up the Irons!

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Több
7 éve 2 hónapja #8293

végre egy jó híííííír! :o)


*inner peace*

Kérjük, hogy Bejelentkezés vagy vagy Fiók létrehozása, hogy csatlakozhass a beszélgetéshez!

Oldalmegjelenítési idő: 0.181 másodperc
Az oldal motorja a Kunena fórum