Problem (za Stratosa?)

Najhitrejši algoritem, ki iz stringa S potegne tak substring T, da je L(T)*O(S,T) maksimalen.

L(T) - je dolžina Tja.

O(S,T) - število pojavljanj Tja v Sju.

O(S,T) mora biti več kot 1.

Ja no, če ne razumeš prvega posta, potem sem naredu napako v naslovu te teme.

Zelo dobro vprašanje JerKoJ.

NE sme se prekrivat.

Kakor ti najbolj ljubo.

Oki, problem sploh ni tako težak.
Navaden brute bi bil takšen :

Najhitrejši algoritem, ki iz stringa S potegne tak substring T, da je L(T)*O(S,T) maksimalen.

L(T) - je dolžina Tja.
O(S,T) - število pojavljanj Tja v Sju.
O(S,T) mora biti več kot 1.

če se odločimo da gremo samo na textualno razliko, moramo vedeti sledeče logične zaključke :

Dolžina T-ja oz sam iskani string, ta je znana
Gremo pač od začetne črke v S-ju in iščemo prvo ponavljanje T-ja, ker isti T ne more biti v S-ju med iskanim indexom in iskani index+dolžina (T) povečamo start point iskanja T-ja v S-ju za dolžino T-ja ...
ponavljamo dokler ne pridemo do konca.

Če najdemo več T-jev v S-ju je O(S,T) > 0, sama logika ti pove da bo hitrost iskanja večja čim večjo dolžino bo T imel relativno na S, kar ti pove tudi tvoja formula.

Procesorsko hitreje v določenih primerih prideš do zaključka, če upoštevaš le prvo črko T -ja in iščeš to v S-u, vse pa je odvisno od dolžine T in S a ter število ponavljanj prve črke T -ja v S-u.
Torej iščeš prvo črto T-ja v S u in ko to najdeš preveriš na tem mestu še ponavljanje celotnega T-ja v s-u, če ne pa nadaljuješ z iskanjem na index-u + dolžina T in zopet iščeš naslednja ponavljanja črk.

Jaz sem ti dal le dva načina, jih je pa več odvisno kakšen je svoj S in T string oziroma kakršna koli povezava.

Zgornji brute se pa najbolj obnesejo !

Sej sem ti v zgornjih postih povedal od česa je hitrost iskanja odvisna.
Še enkrat od velikosti stringov ( originalnega in iskalnega )
in od entropije stringov.

---

Jaz sem ti dal le dva načina, jih je pa več odvisno kakšen je svoj S in T string oziroma kakršna koli povezava

---

Kar si ti začel sem v bistu že jaz načel, vendar pa kakor si ti povedal HITROST v tvoji smeri predvsem odvisna od entropije in seguence S in T-ja.
Hitrostni algoritem za izračun le tega je torej odvisen od tega, in tudi pristop k problemu je odvisen od tega.

Če hočeš ti lahko dam enih 5 različnih primerov za reševanje, algoritem pa je seveda odvisen od samih stringov in zgoraj navedenih parametrov, zaporedij in entropij ter velikosti.

Govorimo o hitrosti in ne o algoritmu !
Hitrost algoritma oz. procesorsko gledano hitrost izvajanja algoritma in izračun končnega rezultata pa je spet drugo poglavje.

Kot sem ti že povedal moreš problem konkretizirati, jaz sem se že v večini primerov že dosti ubadal z procesorsko gledano hitrostjo obdelave stringov in sem našel 5 različnih tipov k pristopu.

Kot sem ti lepo napisal ti lahko povem v čem je fora, testiral sem predvsem v VB, ki je zaradi vmesnega člena ( runtime dll ) pri takšnih operacijah izreeedno počasen.

Tudi tista tvoja matematičen izraz ni preveč točen in velja splošno. Res pa je da je to entropijska velikostna funkcija obeh stringov.

Lahko ti povem kako gre funkcija Instr() v VB deluje.
Deluje totalno brute, mislim pa da vsaka funkcija ki išče določen string v drugem stringu deluje tako, zakaj torej uporabiti ukazni iskalec celotnega stringa v stringu.
To je dobro le pri krajših dolžinah stringov.

Če imaš velik string ( predvidevam, ker se ti gre za hitrost ) je seveda sam algoritem odvisen od entropije in velikosti stringov.

Algoritem je dober če je programer dober, in če veš kaj več o tvojem iskalnem stringu oz stringu v katerem iščeš.
To je tvoje izhodiššče, dokler sistem točno določiš - konkretiziraš.

Primer :
Vedno bomo iskali string "ABC"
string="00000000000000000000ABC"
1.
zdaj pa premisli : brute force bi iskal string "A" po 20 loopih bi ga našel, pregledati bi moral ali je še sledeči string "B" in "C", da bi spoznal da je, torej 3 korake več če bi iskal string "ABC" bi ga našel v 21 poskusu.

2.
string="AAAAAAAAAAAAAAAAAAAAABC"
če bi tu iskal "A" bi uporabil vsaj eno korak več pri vsakem koraku ( pregled ali je sledeči string "B" ).

3.
string="ABABABABABABABABABABABC"
če bi tu iskal "A" bi uporabil min 2 koraka več pri vsakem koraku, če bi iskal "AB" bi uporabil enako št. korakov kot pri 1.), prav tako kot če bi iskal "ABC".

Če sedaj gledamo relativno hitrost kot št. korakov in ne procesorsko hitrost, ki po možnosti tebe zanima ( še zdaj nisi specificiral kaj misliš kot hitrost ) vidimo da je funkcija ki nam bo to opisala odvisna seveda od velikosti stringa in našega iskanega stringa v njem in število kombinacij iskanega stringa v našem stringu in vseh njegovih ( iskanih ) podstringov, kar pa ni enako entropiji ( to je le stanje neurejenosti sistema ), entropija sistema je v tem mišljena na ponavljanje našega iskanega stringa v stringu.
Od tebe je potem odvisno ali boš iskal prvo črko iskanega stringa v stringu, prve dve ozirama kakšen koli substring ali del iskanega stringa.
Če te zanima le število ponaljanj iskanega stringa v stringu je rezultat vedno isti, ne glede na pot iskanja in sequenco iskanja iskalnega stringa v stringu, ki si jo izbral, le število korakov pri tem se lahko zelko razlikuje.
Če hočeš statistično res dobiti minimum korakov moraš sistem prej kombinacijsko/entropijsko obdelati.
Kakšen del stringa v iskanem stringu boš iskal in kako ga boš iskal ti da ta funkcija.
Iščeš kombinacije vseh stringov in podstringov iskanega stringa v stringu za dan primer, ko najdeš pri kerem substringu iskanega stringa ja najmanj možnih kombinacij izbereš za iskanje le tega.

Da ne bom pametoval ...
tule je naprimer izsek stringa "...ABABERTFFJTZJABECEF#$%RTNGN$%&ABRZJCVXVBMKKHL.."
iščeš string "ABECEDA" v zgornjem (delnem) stringu.
Z frekvenčno analizo si ugotovil, da se string ABEC najmanjkrat pojavlja v celotnem izbranem stringu stringa.
Torej iščeš "ABEC" v celotnem stringu in ko ga najdeš skušaš še najti celoten iskani string stringa.
Tudi sequenca ponavljanja je matematično zanimiva, lahko bi izmed teh delov odkril da se izmed "ABEC" pri nam še relativno manj ponavlja "A??E?D"
toda se pri programskemu delu to precej pozna, kajti pri vsakem koraku imaš za dani korak še 3 dodatne korake ( da preveriš ).

To je le računalniško najboljši sistem za najkrajše število korakov.
Če te še kaj bolj zanima si pa lahko prebereš kakšno bukvo o kombinatoriki, neurejenosti in podobnem pa mi potem mal bolj zabluzi z nekim primerom.
Torej če sistem ti točno določiš ima samo eno najkrajšo pot kar se tiče programskih minimalnih korakov pri tem ( dobiti pa število ponaljanj stringa v stringu).

Za vsak razlićen primer imamo le vedno en postopek/algoritem s katerim bomo prišli do konca, število korakov in algoritem sam se pa od primera do primera razlikuje. Odvisen je le od začetnih pogojev, entropije in ostalih parametrov.

Po moje se dobro izvijam - direktno (in pošteno) rečeno, ker sam nisi nič konkretiziral.
Dej dejanski primer in povej kaj za vraga smatraš kot hitrost ...


Upam da sem bil dovolj konkreten in sem hkrati rešil tvoj problem, za najkrajše število programskih korakov pa lahko za velik sistem razpišeš nagrado !!

Statistika, totalni brute, potem pa izbezat kaj se da za določen sistem ...

Povej kakšen problem imaš, jaz mam kar podobnega, no ne gre se za minimum korakov ampak minimum poti itd ...

Znak, ki se največkrat pojavi v nizu...

algoritem, ki vedno deluje....
znak po znak.. pa stejemo

Zahtevnost: k*n (linearna), kar ni tako slabo.. ampak v bistvu je slabo.

Moj genetski optimizator se pa še sesuva (in daje čudne rezultata.. pri različnih random nizih BISTVENO različne rezultate - sicer je res, da se s tem nisem ukvarjal več ko 1h ... pa vendar) tako da... ga trenutno še ne morem uporabiti za kaj pametnega.

V primeru res dolgega niza.. in če ne potrebujemo števila znakov, bi se mogoče izplačala statistična metoda... Na "random" ali kakorkoli že (samo neodvisno od vsebine niza) izberemo en odstotek znakov (kaj statistično pomembnega - 15% - 50%) in potem preverimo na tem vzorcu. V večini primerov (veliki nizi) bi dobili DOKAJ merodajen rezultat, lahko pa tudi POPOLNOMA sfalimo.

Zahtevnost: k*n (pri čemer je k približno pol zgornjega), kar je bolje vendar ne bistveno. Lahko pa sfalimo (zgoraj ne moremo).

Če je string res dolg... pa je znakov, ki jih je največ dejansko VIDNO več... lahko naprimer rečemo da je aritmetična sredina njihovih ascii kod... nekje blizu tega znaka... kar ne pobere veliko časa, ker čez zanko vlačimo samo 2 spremenljivki (seštevek in število). Drugače pa ... ali uporabljamo ta podatek v kakšnem večjem algoritmu, ali tukaj govorimo o tem podatku kot podatku samem zase?

Tako je - pod linearno odvisnost pridemo, da določimo najverjetnejši znak, ki se največkrat pojavlja v stringu.

Ampak mene zanima, če nam ta podatek kaj koristi tudi, ko iščemo dejansko najverjetnejši znak.

Sej. Ampak recimo, da veš, da je A najverjetneje najpogostejši znak.

Ti ta vednost lahko kaj pomaga pri dejanskem štetju? In kako?

Naprimer če kaže, da je najpogostejšega znaka več od polovice, potem se splača it štet samo tisti znak in nobenega drugega.

Če je končen rezultat res več od polovice - smo že nekoliko optimizirali.

Ampak to je šele začetek problema. Zdaj moramo pa preveriti še najpogostejši substring.

Ja seveda, če pa se ti (StratOS) brezveze izvijaš :-)

as i told u : No pain no gain.

Analiza pa boš mel minimalno/najgitrejšo rešitev.

Ja... samo vprašanje je, če se splača. Če bomo to potem ponovili še za tretji znak itd... moramo na koncu še vedno spobat vsaj nekaj vzorcev z bruteforce... in tako se lahko celo zgodi, da imamo na koncu bolj zahteven algoritem od debilnega brute forcea.

Ok, danes sem si prvic vzel cas in slucajno prebral tale topic, moj odgovor sledi.

Thomas: Kaj ti si nor in se po moznosti gres boga, oziroma mislis da je StratOS bog, se ti sploh zavedas kaksen problem si predstavil!? ;)

Resevanje tega problema je popoln nesmisel (no ja ;) ?), berite naslednje:
Pri tem programu je edina moznost, da testiras vse kombinacije stringov takole:
1, 1+2, 1+2+3, 1+2+3+...+n; 2, 2+3, 2+3+4, 2+3+4+...+n; ..+n; n; (stevilke pomenijo zaporedne stevilke znakov)

zdej pa podrobnosti:
-najbolje je, da v buffer shranjujes moznosti, ki si jih sprobal(torej ob tem vse prve kombinacije; s tem, da je pri prvi kombinaciji za vse ostale string z +n nesmiseln, stalno je string zadnje

...+n kombinacije nesmiseln za naslednjo y iteracijo kar bi lahko pomenilo, da je +(n-1) povsem nesmiseln za naslednjo kombinacijo ampak ni res, torej je tukaj ze paradox, ki je neresljiv v realnem

koncnem prostoru, resljiv je le kompleksnem neskoncnem prostoru, kar je za racunalnik nemogoce, ampak ker prizkusamo vse kombinacije tega problema na sreco ni) in ob njih napises stevilo

ponavljanj, iz njega potem preverjas ce je kter string se tak v drugih y iteracijah in vecas stevec v bufferju pri stringu, ki se ponovi.
Kje je problem, problem je v tistem ker na sreco preizkusamo vse kombinacije?! potem pa moramo se cel buffer preracunat, da dobimo maximalno vrednost racuna, ki si ga predlozil.
To kar si ti nacel je podobno problemu trgovskega potnika, ki ni resljiv v realnem casu.

Ampak si postavil zelo dober problem, ki se ga ne da resiti na klasicen nacin, zato je potrebno risati preko okvirja slike in biti utvarjalen, mislim, da imam resitev!?
Namig: bifurkacije, vreme, kaos.
Amapak bos ob ze napisanem moral se sam biti zeloooo ustvarjalen.(kot da ze sama napisana teorija ne bi bila dovolj tezka ;) )

Kaj mislis zakaj ni nobene reference na netu!?

Nisem pa ziher.


Dovolj. :)