Autor | Zpráva | ||
---|---|---|---|
regvac Profil * |
#1 · Zasláno: 28. 2. 2010, 16:28:06
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 |
#2 · Zasláno: 28. 2. 2010, 17:33:05
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 |
#3 · Zasláno: 28. 2. 2010, 18:35:20
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 |
#4 · Zasláno: 28. 2. 2010, 19:12:08
WanTo:
Až na to, že použitie operátor poľa [] na textový reťazec funguje len v niektorých prehliadačoch. |
||
WanTo Profil |
#5 · Zasláno: 28. 2. 2010, 19:24:56
_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 * |
#6 · Zasláno: 28. 2. 2010, 20:50:04
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 |
#7 · Zasláno: 28. 2. 2010, 21:17:30
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 |
#8 · Zasláno: 28. 2. 2010, 21:37:10
_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 |
#9 · Zasláno: 1. 3. 2010, 07:27:16
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 |
#10 · Zasláno: 1. 3. 2010, 09:53:11 · Upravil/a: _es
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 |
#11 · Zasláno: 1. 3. 2010, 13:46:36
_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 |
#12 · Zasláno: 1. 3. 2010, 14:13:16 · Upravil/a: _es
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 * |
#13 · Zasláno: 1. 3. 2010, 23:46:08
_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 |
#14 · Zasláno: 2. 3. 2010, 00:20:09
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 * |
#15 · Zasláno: 2. 3. 2010, 00:34:40
_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 |
#16 · Zasláno: 2. 3. 2010, 01:32:47
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 * |
#17 · Zasláno: 2. 3. 2010, 16:33:49
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 |
||
Časová prodleva: 14 let
|
0