21. září bude sraz! Od 18.00 v restauraci Tradice v Praze u Anděla
Autor Zpráva
regvac
Profil *
Ahoj,
nedokázal by mi někdo poradit kde najít nebo jak udělat skript, který by sloučil stringy, pokud se částečně překrývají svým obsahem?

příklad:
var list = new Array('padat','Data','notepad');
->
var list_prunik = new Array(
'text',
'padat',
'Data',
'notepad',
'padatext', //vzniklo sloučením padat a text
'padata', //vzniklo sloučením padat a Data
'notepadat', //vzniklo sloučením notepad a padat
'notepadata', //vzniklo sloučením notepad a data nebo notepad, padat a data
);

Díky
WanTo
Profil
Na efektivní řešení tak, aby se ta slova sloučila v nějakém rozumném čase, budeš pravděpodobně potřebovat pro každé slovo postavit suffix tree. Pro dvě různá slova pak najdeš nejdelší společný podřetězec, pro který platí, že je suffixem jednoho slova a prefixem slova druhého. Na Wikipedii je popis řešení hodně podobného problému - Longest common substring problem. A rovnou říkám, že naprogramovat tohle není žádná sranda.

Další možností je to, že pro všechny suffixy jednoho slova určíš, zda náhodou nejsou prefixem jiného slova, případně jiných slov, podle čehož pak slova sloučíš. Poběží to přibližně tolikrát pomaleji, kolik je průměrná délka jednoho slova, ale naprogramovat to nebude zdaleka tak složité.
WanTo
Profil
Ale slib mi, že se pokusíš porozumět tomu, jak to funguje :o)

/**
 * Pokud slovo A končí nějakým suffixem, který je prefixem slova B,
 * obě slova sloučí tak, že suffix resp. prefix se ve výsledném slově
 * objeví pouze jednou.
 *
 * Nebere v úvahu velikost znaků, výsledek je vždy lower-case.
 */
function mergeWords(a, b) {
    var a = a.toLowerCase();
    var b = b.toLowerCase();
    
    // projdeme všechny suffixy slova A (od nejdelšího po nekratší)
    suffixLoop: for (var start = 0; start < a.length; start++) {
        // projdeme slovo A od pozice start až do konce
        // pokud se bude pořád shodovat se znaky ve slově B,
        // našli jsme společnou část obou slov a slova můžeme spojit
        for (var i = 0; i < a.length - start; i++) {
            // 1) pokud jsme se prošli celé slovo B (bylo kratší než suffix),
            // pokračujeme dalším suffixem
            if (i == b.length) continue suffixLoop;
            
            // 2) pokud se znaky v suffixu slova A a slově B neshodují,
            // také pokračujeme dalším suffixem
            if (a[start+i] != b[i]) continue suffixLoop;
        }
        
        // pokud jsme se dostali až sem, suffix slova A se shoduje s prefixem
        // slova B, můžeme tedy slova sloučit - protože procházíme suffixy
        // od nejdelšího po nejkratší, žádný delší společný řetězec už nemůžeme
        // najít, můžeme tedy rovnou vrátit nové slovo
        var mergedWord = a.substring(0, start) + b;
        return mergedWord;
    }
    
    // pokud jsme neúspěšně prošli všechny suffixy a dostali jsme se až sem,
    // slova A a B nelze sloučit...
    return null;
}

/**
 * Každé dvě slova ze zadaného pole se pokusí sloučit,
 * sloučená slova vrátí v novém poli.
 */
function mergeWordsInArray(array) {
    var newArray = new Array();
    for (i = 0; i < array.length; i++) {
        for (j = i + 1; j < array.length; j++) {
            var merge1 = mergeWords(array[i], array[j]);
            var merge2 = mergeWords(array[j], array[i]);
            
            if (merge1) newArray.push(merge1);
            if (merge2) newArray.push(merge2);
        }
    }
    return newArray;
}


Časová složitost přibližně O(N^2 * M^2), kde N je počet slov a M průměrná délka slova. Pokud nevíš, o čem mluvím, tak při poli se 100 slovy to funguje rychle a bez problémů, ale na slovník s 50.000 hesly bych to nepouštěl :)
_es
Profil
WanTo:
Až na to, že použitie operátor poľa [] na textový reťazec funguje len v niektorých prehliadačoch.
WanTo
Profil
_es:
Hmm, sakra. Tak to se omlouvám, v tom případě se místo operátoru [] bude muset použít řetězec.charAt(index). To by snad mohlo fungovat všude.
regvac
Profil *
Super, moc díky,je to úžasný.

Ještě jsem si tam před spuštění této funkce přidal funkci pro eliminaci duplicitních slov ve vstupní array a podmínku pro spuštění funkce mergeWordsInArray(array) jen pokud je array.length>1.

Ještě jeden dotaz, daly by se jednoduše hodnoty array seřadit podle délky řetězce (počtu znaků) od nejdelšího po nejkratší.

např.
var list = new Array('123','2345','a','1111');
->
var list_dle_poctu_znaku = new Array(
'2345', //4 znaky
'1111', //4 znaky
'123', //3 znaky
'a', //1 znak
);
_es
Profil
WanTo:
Ten tvoj skript bude pre JavaScript časovo neefektívny.
Malo by sa využiť to, že JavaScript umožňuje porovnávať celé reťazce.
Teda porovnávať priamo viaznakové podreťazce z tých dvoch reťazcov a nie to porovnávať po jednotlivých znakoch.
WanTo
Profil
_es:
Nemám přehled o tom, jak jsou v JavaScriptu implementované řetězce, ale pokud je metoda substring() založená na zkopírování řetězce a alokaci nové paměti, tak porovnávat celé řetězce (které by bylo nejdřív potřeba nějak získat) by rozhodně efektivnější nebylo.

Pokud substring() interně jenom šachuje s nějakými pointery a nekopíruje paměť, tak budiž, ale kdo chce časovou efektivitu, ať si postaví suffix tree. Na 100 slovech rozdíl nepoznáš, na databázi tě při téhle asymptotické časové složitosti ani interní porovnávání JavaScriptu nezachrání.
_es
Profil
WanTo:
JavaScript nemá dátový typ "znak".
Dokáže porovnávať len reťazce, teda v tvojom skripte sú porovnávané jednoznakové reťazce.
Nechcelo sa mi zisťovať, ako presne tvoj skript pracuje, no myslím, že namiesto toho, aby porovnal dva reťazce na rovnosť a využil na to optimalizované vnútorné algoritmy, tak sa snaží túto, už zabudovanú, funkčnosť nahradiť tým, že tie reťazce začne porovnávať po jednotlivých znakoch.
_es
Profil
Neviem, ako je to myslené s veľkými a malými písmenami, ak má mať prednosť veľkosť písmen z prvého reťazca tak by som použil:
function spoj(a, b){
  var x = a.toLowerCase();
  var y = b.toLowerCase();
  var i = Math.max(0, x.length - y.length);
  var j = Math.min(x.length, y.length);
  while(x.substring(i) !== y.substring(0, j)) i++, j--;
  return a + b.substring(j);
}
WanTo
Profil
_es:
Jak ten skript pracuje, tam máš poměrně obšírně vysvětlené. Tak jako tak, pokud ani jeden z nás neví (nebo já to přinejmenším nevím, tys to třeba jenom nenapsal), jak interně pracuje substring() a jak nákladné je jeho volání, nemá cenu se o tom bavit dál, to bychom akorát kázali bludy. Asymptotická časová složitost je nicméně mnohem důležitější a tím, že využiješ interní porovnávání stringů, se jinak nezmění.
_es
Profil
WanTo:
jak interně pracuje substring() a jak nákladné je jeho volání, nemá cenu se o tom bavit dál, to bychom akorát kázali bludy
Tvoj skript bude určite pomalší, lebo si z toho, čo dokáže JavaScript vyriešiť jedným príkazom, spravil zložitý cyklus.
Ten jeden príkaz síce interne tiež musí robiť nejaké cykly, no určite oveľa efektívnejšie.
Tvoj kód vyzerá ako prerobený kód z C, no pre C je to vhodný algoritmus.
regvac
Profil *
_es
Ve tvém kódu chybka, resp. nedělá to samé co kód od WanTo. Mělo by tam být jen return b.substring(j); bez a +

Nevim, co je rychlejší, ale šlape to. Dík
_es
Profil
regvac:
Ve tvém kódu chybka, resp. nedělá to samé co kód od WanTo.

Neviem, ako bolo to spájanie myslené s veľkými písmenami, moja funkcia zachová veľkosť písmen v prvom reťazci a pripojí k tomu časť druhého reťazca so zachovaním jeho veľkosti písmen.
Myslel som, že to tak má byť.
spoj("jablko","Kolín") vráti reťazec "jablkolín".
regvac
Profil *
_es
spoj("jablko","Kolín") vráti reťazec "jablkolín".
Mě to vrátí jablkolín,Kolínjablko,jablko,Kolín -> Kolínjablko je tu navíc - nemají průnik. Je chyba tedy asi někde jinde v kódu.
_es
Profil
regvac:
Mě to vrátí...
Ja som dal len funkciu na to špeciálne spojenie reťazcov.
Ľahko si ju upravíš, aby vracala prienik reťazcov, alebo vracala nejakú hodnotu, len ak prienik existuje - vtedy bude j rovné 0.
Možno chceš túto funkciu:
function spoj2(a, b){
  var x = a.toLowerCase();
  var y = b.toLowerCase();
  var i = Math.max(0, x.length - y.length);
  var j = Math.min(x.length, y.length);
  while(x.substring(i) !== y.substring(0, j)) i++, j--;
  if(j) return a + b.substring(j);
}
regvac
Profil *
Nedokázali by jste mi ještě poradit se zbytkem. Váše sktipty jsem použil jako součást mé vyhledávací funkce. Viz. Odkaz

Stránka je sestavena tak, aby obsahoval co nejvíce prvků, ze kterých se HTML stránka skládá.

Skript String.prototype.highlight bych potřeboval upravit tak,aby:
- nedělal problémy s HTML entitami na stránce
- ignoroval vše mezi tagy <script></script>,<style></style>,<option></option>,<textarea></textarea> ,....
atd...
Tento skript není můj a vůbec mu nerozumim, ale dělá zatím ze všech co jsem na netu hledal nejméně chyb.

Hledal jsem na netu něco podobného, ale vždy to dělá při označování textu nějakou chybu.

Stránku vyzkoušejte například na text "a" nebo tak podobně.

Díky

Vaše odpověď

Mohlo by se hodit

Neumíte-li správně určit příčinu chyby, vkládejte odkazy na živé ukázky.
Užíváte-li nějakou cizí knihovnu, ukažte odpovídajícím, kde jste ji vzali.

Užitečné odkazy:

Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0