Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: Peterson 24. 01. 2011, 16:13:21

Název: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Peterson 24. 01. 2011, 16:13:21
Dobry den,

rad bych zvyraznil hledany vyraz v textu tak, aby preg_replace() nebral v potaz diakritiku v $subject, ale nevim si s tim rady...

Napr.:
Uzivatel zadal jako vyraz pro hledani "pocitac".
Pomoci MySQL LIKE '%pocitac%' dostanu text, kde se vyskytuje slovo "počítač".
Nyni bych rad v tomto textu zvyraznil ono slovo "počítač", ovsem uzivatel pro hledani nepouzil diakritiku.

Opacny pripad mi problemy nedela (tzn. zvyraznit v textu "pocitac", pokud uzivatel hleda "počítač").

Resil uz toto nekdo? Poradite?

Dekuji
--
P.
Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: Logik 24. 01. 2011, 16:29:52
No jedna možnost je pocčítač přepsat na něco typu
po[cč][ií]ta[cč]
písmen s diakritikou není tolik, takže výslednej regexp nebude tak dlouhej.

Druhá možnost je převést text na text bez diakritiky, vyhledat tam pocitac
a zvýrazňovat pak v orioginálním textu pomocí indexu.
Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: ghost 24. 01. 2011, 16:45:33
krkolomne reseni,
1. udelat si duplikat retezce bez diakritiky - jak vzor tak vysledek - treba iconvem z utf8 -> ascii
2. pouzit strpos na zjisteni pozice, kde retezec je
3. delku hledaneho vis
4. nahradit od indexu do indexu + delky retezce
Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: smartin_xx 24. 01. 2011, 17:58:05
Dobry den,

rad bych zvyraznil hledany vyraz v textu tak, aby preg_replace() nebral v potaz diakritiku v $subject, ale nevim si s tim rady...

Napr.:
Uzivatel zadal jako vyraz pro hledani "pocitac".
Pomoci MySQL LIKE '%pocitac%' dostanu text, kde se vyskytuje slovo "počítač".
Nyni bych rad v tomto textu zvyraznil ono slovo "počítač", ovsem uzivatel pro hledani nepouzil diakritiku.

Opacny pripad mi problemy nedela (tzn. zvyraznit v textu "pocitac", pokud uzivatel hleda "počítač").

Resil uz toto nekdo? Poradite?

Dekuji
--
P.

zkus: php.net/manual/en/book.mbstring.php
Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: Peterson 25. 01. 2011, 08:56:03
Napad s pocitanim pozice a pote nahrazeni od indexu do delky slova zvyraznenim byl sice funkcni, ale opravdu dosti krkolomny.

Nakonec jsem se na celou vec podival z druhe strany a to se mi zda ponekud jednodussi jak na psani, tak i na vykon...

Ve vysledku tedy rozdelim jednotliva slova z vyhledaneho textu do pole. Kazde takoveto slovo potom prevadim do ASCII//TRANSLIT a porovnavam vuci hledanemu vyrazu (take ASCII//TRANSLIT). Pokud se vyraz shoduje, doplnim ho o zvyraznovaci kod.
Vyhoda tohoto reseni spociva v tom, ze lze zvyraznit vsechny nalezene shody a zaroven cele slovo kde ke shode doslo.

Snad se nekomu bude hodit, prip. uvitam diskuzi vedouci ke zlepseni:

Kód: [Vybrat]
// Nutne nastavit locale jinak se iconv chova divne
setlocale(LC_ALL, 'cs_CZ.UTF8');

function highlight($haystack,$needle) {

// Hledany vyraz prevest na transliterovany ASCII
$ASCII_needle=iconv("UTF-8","ASCII//TRANSLIT",$needle);

// Rozdelit slova z $haystack do pole; Odstranit duplicity z pole
$words=preg_split("/[\s,\.]+/",$haystack); array_unique($words);

// Prochazet pole slov
foreach($words as $word) {

// Slovo prevest na transliterovany ASCII
$ASCII_word=iconv("UTF-8","ASCII//TRANSLIT",$word);

// Porovnat shodu (pokud chci zvyraznit cele slovo kde je shoda, jinak pouzit /^$ASCII_needle$/ pro absolutni shodu)
if(preg_match("/".$ASCII_needle."/ui",$ASCII_word)) {

// Zvyrazneni hledaneho slova
$haystack=str_replace("$word","<span class=\"highlight\">$word</span>",$haystack);

}
}
return $haystack;
}
Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: Logik 25. 01. 2011, 09:25:07
ehm.... jednodušší? výkonější? To tvoje řešení je kulantně řečeno jedno z nejhorších. Jedinou devizu má, že je vcelku krátký, i když hromada lepších řešení by nebylo o moc delších.

O co je výkonější rozdělit text do pole a zkonvertovat každej prvek pole, než zkonvertovat celej text najednou? (A už vůbec nemluvim o tom, že text v ASCII si lze
připravit jednou a načítat z databáze už zkonvertovanej....) Už jen to zbytešný rozdělování do pole...
O co je výkonější provnávat každej prvek pole, než vyhledávat najednou v celym řetězci? Nemluvě o x-násobný kompilaci regulárního řetězce.

A každý nalezený slovo v řetězci navíc v každé podobě (s diakritikou nebo bez) hledáš v řetězci znovu. Takže pokud se ti tam vyskytuje Počítač, počítač, pocitac a Pocitac, tak místo jednoho převedení textu na lowercase ascii a vyhledání pomocí jednoduchého strpos (značně levnější než preg_match) to vyhledáváš 5x... To je výkonnost :-)

PS: Jako detail už je, že když už používáš str_replace, tak bys moh to aspoň nahradit vše najednou, viz argument typu pole u str_replace, nebudeš tak x-krát sestavovat dlouhej řetězec.

PPS: Kdyby každej programátor povinně rok psal v C/C++,. to by byl svět krásnej :-)

Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: Peterson 25. 01. 2011, 09:39:21
Logik:

uznavam, ze to moje reseni neni uplne koser, ale na druhou stranu ma velkou vyhodu v tom, ze muzu zvyraznit cele slovo kde je vyskyt hledaneho vyrazu a zaroven vsechny vyskyty v celem textu.
Ano, index je jiste nejjednodussi orientace v retezci. Ne, ze by se mi ho nechtelo pouzit, ale pomoci indexu jsem neprisel na zpusob jak docilit toho co mam za lubem...
Název: Re: PHP: zvyrazneni vyrazu, preg_replace vs. diakritika
Přispěvatel: ghost 25. 01. 2011, 11:01:00
Kód: [Vybrat]
setlocale(LC_ALL, 'cs_CZ.UTF8');
function highlight($search, $string) {
$_search = strtolower(iconv("UTF-8","ASCII//TRANSLIT", $search));
$_string = strtolower(iconv("UTF-8","ASCII//TRANSLIT", $string));
$result = "";
$end = "";

while(($lastIndex = strpos($_string, $_search)) !== false) {
// zacatek vyrazu
$start = mb_substr($string, 0, $lastIndex, "UTF-8");
// hledany vyraz
$middle = "<b>".mb_substr($string, $lastIndex, strlen($_search), "UTF-8")."</b>";
// novy zbytek vyrazu
$end = mb_substr($string, $lastIndex + strlen($_search), strlen($_string), "UTF-8");

// pripojime do vysledku
$result .= $start.$middle;

// hledame jen dopredu
$string = $end;
$_string = substr($_string, $lastIndex + strlen($_search), strlen($_string));
}

$result .= $end;

return mb_strlen($result, "UTF-8") ? $result : $string;
}

Zvyrazní všechno v textu, ignoruje diakritiku a velikost pismen. Ale nebere prekryvy - muzes si to ale upravit :).
Kód: [Vybrat]
echo highlight("poc", "Pocitace počitace počítač tralala");
<b>Poc</b>itace <b>poč</b>itace <b>poč</b>ítač tralala;

echo highlight("pop", "popop");
<b>pop</b>op
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: ghost 25. 01. 2011, 11:14:32
prosim nekritizovat za opakovane pouziti strlen, zejmena pak strlen($_search). Samozrejme spocitat jednou na zacatku ... psal jsem rychle ...
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Logik 25. 01. 2011, 12:40:31
Peterson: viz např. ghostovo řešení. Zvýrazňovat celý slovo - to je takovej problém získanej index (respektive interval indexů) "rozšířit" o všechny nebílý znaky na obě strany?

Ghost: ten strlen by tak nevadil, v php je dýlka stringu uložená, takže se nemusí projít celej string. Horší je, že v každym kroku cyklu vytváříš novej $_string, místo toho, co bys nechal původní a hledal od určitýho indexu. No a pak ještě to jde taky dělat "inplace", stačí si pamatovat délku vloženejch segmentů. U hodně dlouhýho řetězce (řádově stovky kilobajt) to může udělat znatelnej rozdíl, nejen ve spotřebě paměti, ale taky potažmo rychlosti díky procesorový cache.

Ale možná úplně nejlepší řešení je ne budovat ten string inkrementálně, ale jeho vytvářený kousky házet do pole a pak výslednej řetězec vytvořit pomocí implode. Odpadne vytváření spousty pracovních pomocnejch řetězců a v implode se vše naalokuje a zkopíruje najednou.
Dokonce některý knihovny by to tak zvládly bez jakýhokoli kopírování částí řetězců - někde je substr implementovaný tak, že nevytváří novej buffer, ale používá buffer
původního řetězce, takže by se opravdu řetězec kopíroval pouze jednou. To ale bohužel není případ php.
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: ghost 25. 01. 2011, 13:01:26
Ghost: ten strlen by tak nevadil, v php je dýlka stringu uložená, takže se nemusí projít celej string. Horší je, že v každym kroku cyklu vytváříš novej $_string, místo toho, co bys nechal původní a hledal od určitýho indexu. No a pak ještě to jde taky dělat "inplace", stačí si pamatovat délku vloženejch segmentů. U hodně dlouhýho řetězce (řádově stovky kilobajt) to může udělat znatelnej rozdíl, nejen ve spotřebě paměti, ale taky potažmo rychlosti díky procesorový cache.

Ale možná úplně nejlepší řešení je ne budovat ten string inkrementálně, ale jeho vytvářený kousky házet do pole a pak výslednej řetězec vytvořit pomocí implode. Odpadne vytváření spousty pracovních pomocnejch řetězců a v implode se vše naalokuje a zkopíruje najednou.
Dokonce některý knihovny by to tak zvládly bez jakýhokoli kopírování částí řetězců - někde je substr implementovaný tak, že nevytváří novej buffer, ale používá buffer
původního řetězce, takže by se opravdu řetězec kopíroval pouze jednou. To ale bohužel není případ php.

strlen - jasny, vim jak je to s delkou stringu, ale neni moc pekne volat stejnou funkci se stejnym parametrem vicekrat :)

spojovani - rozmyslel jsem, zda pouzit implode a chvili jsem jej tam i mel, ale nakonec jsem pouzil spojeni retezcu prislo mi to v dany okamzik nazornejsi :)

hledani az od indexu - samozrejme by to bylo vhodnejsi, ale psal jsem jen po pameti a pouzival tak fce, ktere znam.
Ted jsem se podival a zjistil, ze strpos ma i treti parametr offset :) - tim by se to krasne vyresilo a odpadlo by znovu vytvareni $_string

Kazdopadne jsem chtel jen lehce nastinit jak to udelat pomoci zakladnich funkci pro praci se stringem a vyhnout se regexpum ...
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Efficient 25. 01. 2011, 13:18:03
Tady jsou sami PHP heroes jak tak vidim... Zkuste trochu algoritmicky myslet drive nez neco zprasite v PHP...
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: ghost 25. 01. 2011, 13:27:26
Tady jsou sami PHP heroes jak tak vidim... Zkuste trochu algoritmicky myslet drive nez neco zprasite v PHP...
Tak nam navrhni vlastni reseni a hlavne u toho algoritmicky mysli ... navic tazatel to chtel v PHP ... to mu to mame napsat v Cecku?
Nebo jsme mu meli napsat algoritmus na vyhledávaní v textu - treba Rabin–Karp?
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Peterson 25. 01. 2011, 18:02:40
Jeste jsem si s tim nejakou dobu hral a zkousel ...

Priklad od Ghosta funguje perfektne. Trochu jsem ho upravil na zaklade navrhu Logika, ale bud jsem to neudelal dobre nebo je chyba jinde (je rozhodne pomalejsi).
Mozna nakonec to, ze Ghost "$_string" ukusuje, je pro vykon lepsi nez prochazeni celeho textu pomoci indexu a offsetu.
Sazeni vysledku do pole a nasledny implode (namisto rozsirovani stavajiciho stringu) nemelo temer zadny vliv na pamet i vykon (nebo opravdu velmi zanedbatelny).

Nakonec jsem otestoval celkem 4 reseni na textu dlouhem 1.5MB (1.564.135 slov, 172.109 slov), testovaci podminky byly shodne a pred kazdym testem jsem restartoval apache.
Vysledky jsou nasledujici:

# Ghostovo originalni reseni
highlight    MEM: 1707,292 kB, Time: 13,8758 s

# Uprava Ghostova reseni
highlight2  MEM: 1707,360 kB, Time: 17,7329 s

Kód: [Vybrat]
function highlight2($search, $string) {
$_search = strtolower(iconv("UTF-8","ASCII//TRANSLIT", $search));
$_string = strtolower(iconv("UTF-8","ASCII//TRANSLIT", $string));
$result = "";
$len=strlen($_search);

// Vychozi offset
$offset=0;

// Hledame pozici prvniho vyskytu hledaneho; bereme v potaz offset
while(($lastIndex = strpos($_string, $_search, $offset)) !== false) {

// zacatek vyrazu (zaciname na offsetu)
$start = mb_substr($string, $offset, ($lastIndex-$offset), "UTF-8");
// hledany vyraz
$middle = "<b>".mb_substr($string, $lastIndex, $len, "UTF-8")."</b>";

// pripojime do vysledku
$result .= $start.$middle;

// Nastavime novy offset
$offset=($lastIndex+$len);
}

// Pripojime konec textu (bereme v potaz offset)
$result.=mb_substr($string,$offset,mb_strlen($string,"UTF-8"),"UTF-8");

return mb_strlen($result, "UTF-8") ? $result : $string;
}

# Index pozic pomoci preg_match_all()
highlight3  MEM: 1794,860 kB, Time: 15,4054 s

Kód: [Vybrat]
function highlight3($needle,$haystack,$type="need") {

// Transliterace
$ASCII_haystack=strtolower(iconv("UTF-8","ASCII//TRANSLIT",$haystack));
$ASCII_needle=strtolower(iconv("UTF-8","ASCII//TRANSLIT",$needle));

// Delka hledaneho
$len=strlen($ASCII_needle);

// preg_match_all nam naplni pole pozicemi hledaneho vyrazu
preg_match_all("/$ASCII_needle/",$ASCII_haystack,$m,PREG_OFFSET_CAPTURE);

// Vychozi offset
$offset=0;

// Prochazeni pole s pozicemi kazdeho vyskytu
foreach($m[0] as $p) {

// Pozice vyskytu
$pos=$p[1];

// Zacatek vyrazu
$start=mb_substr($haystack,$offset,($pos-$offset),"UTF-8");

// Zvyrazneni
$word="<strong>".mb_substr($haystack,$pos,$len,"UTF-8")."</strong>";

// Pripojeni do vysledku
$out.=$start.$word;

// Novy offset
$offset=($pos+$len);
}

// Konec vyrazu do vysledku
$out.=mb_substr($haystack,$offset,mb_strlen($haystack,"UTF-8"),"UTF-8");

return $out;

}

# Diakritika / alternativy pomoci preg_replace()
Nejvice naroku na pamet i cas. Zase na druhou stranu to je jednoduche a diky regexpum se to da velice dobre rozsirovat.
highlight4  MEM: 3261,516 kB, Time: 17,8068 s

Kód: [Vybrat]
function highlight4($needle,$haystack,$type="need") {

// Priprava na slozeni regexpu (obsazeni temer vsech moznych akcentu)
$map1[]="/[aãǎâăåąàȧáä]/iu";
$map1[]="/[bḃ]/iu";
$map1[]="/[cčĉċćç]/iu";
$map1[]="/[dďḋḑ]/iu";
$map1[]="/[eěêĕęèéëȩ]/iu";
$map1[]="/[fḟ]/iu";
$map1[]="/[gǧĝġǵģ]/iu";
$map1[]="/[hȟĥḣḧḩ]/iu";
$map1[]="/[iĩǐîĭįìıíï]/iu";
$map1[]="/[jǰĵ]/iu";
$map1[]="/[kǩḱķ]/iu";
$map1[]="/[lľĺļ]/iu";
$map1[]="/[mṁḿ]/iu";
$map1[]="/[nñňǹṅńņ]/iu";
$map1[]="/[oõǒôŏǫòȯóőö]/iu";
$map1[]="/[pṗṕþ]/iu";
$map1[]="/[rřṙŕŗ]/iu";
$map1[]="/[sšŝṡśş]/iu";
$map1[]="/[tťṫẗţ]/iu";
$map1[]="/[uũǔûŭůųùúűü]/iu";
$map1[]="/[vṽ]/iu";
$map1[]="/[wŵẘẁẇẃẅ]/iu";
$map1[]="/[xẋ]/iu";
$map1[]="/[yỹŷẙỳẏýÿ]/iu";
$map1[]="/[zžẑżź]/iu";

// Slozeni regexpu
$map2[]="[aãǎâăåąàȧáä]";
$map2[]="[bḃ]";
$map2[]="[cčĉċćç]";
$map2[]="[dďḋḑ]";
$map2[]="[eěêĕęèéëȩ]";
$map2[]="[fḟ]";
$map2[]="[gǧĝġǵģ]";
$map2[]="[hȟĥḣḧḩ]";
$map2[]="[iĩǐîĭįìıíï]";
$map2[]="[jǰĵ]";
$map2[]="[kǩḱķ]";
$map2[]="[lľĺļ]";
$map2[]="[mṁḿ]";
$map2[]="[nñňǹṅńņ]";
$map2[]="[oõǒôŏǫòȯóőö]";
$map2[]="[pṗṕþ]";
$map2[]="[rřṙŕŗ]";
$map2[]="[sšŝṡśş]";
$map2[]="[tťṫẗţ]";
$map2[]="[uũǔûŭůųùúűü]";
$map2[]="[vṽ]";
$map2[]="[wŵẘẁẇẃẅ]";
$map2[]="[xẋ]";
$map2[]="[yỹŷẙỳẏýÿ]";
$map2[]="[zžẑżź]";

// Nahrazeni hledaneho vyrazu regexpem
// "pocitac" se bude hledat jako: [pṗṕþ][oõǒôŏǫòȯóőö][cčĉċćç][iĩǐîĭįìıíï][tťṫẗţ][aãǎâăåąàȧáä][cčĉċćç]
$needle=preg_replace($map1,$map2,$needle);

// Finalni nahrazeni hledaneho vyrazu v textu
$haystack=preg_replace("/[^\s]*${needle}[^\s\.]*/iu","<strong>\$0</strong>",$haystack);

return $haystack;
}
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: ghost 25. 01. 2011, 19:19:31
Pekne srovnani.
Jen mala poznamka k highlight3:
mel bys jeste v $ASCII_needle backslashovat vsechny specialni znaky, ktere jsou ridici pro regularni vyraz - teda pokud to nedelas o uroven vys nebo s tim zamerne nepocitac ...
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Kit 25. 01. 2011, 20:10:04
Napadlo mě jiné řešení: Co kdyby se místo serveru zatížila klientská stanice? Prostě by k vygenerované stránce byl přidán kousek Javascriptu s hledanými slovy a ten by se postaral o zvýraznění. Nevím sice z hlavy, jestli disponuje vhodným arzenálem, ale určitě by to bylo i pro server přijatelnější.

Berte to jako pohled na problém z jiného úhlu.
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: ghost 25. 01. 2011, 20:26:53
Napadlo mě jiné řešení: Co kdyby se místo serveru zatížila klientská stanice? Prostě by k vygenerované stránce byl přidán kousek Javascriptu s hledanými slovy a ten by se postaral o zvýraznění. Nevím sice z hlavy, jestli disponuje vhodným arzenálem, ale určitě by to bylo i pro server přijatelnější.

Berte to jako pohled na problém z jiného úhlu.
jde to udelat temer stejnym zpusobem, az na jednu vec - musis se vyporadat s mene elegantnim prevodem z utf8 na ascii - kdyz se podivas po netu, tak se vsude resi pres regexp
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Peterson 25. 01. 2011, 21:59:36
Kit:
Rozhodne to stoji za uvahu a urcite si to alespon vyzkousim. Skvely tip!
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: Logik 25. 01. 2011, 22:43:42
To moje řešení trvá tak dlouho díky použitýmu kódování. UTF-8 nemá pevnou délku znaku a tam nejde skákat rozumně doprostřed řetězce indexem. A na to jsem zapoměl.

Řešením je počítat v mb_string s nějakym kódováním s pevnym znakem, např. UCS-2. Pak je to najednou rychlejší, dle mejch testů cca 2x rychlejší:
2,5s ku 4,7s.
Problém je, že vstupní texty budou pravděodobně v UTF-8 a pak teda je nutné dělat dvojí konverzi (na vstupu a výstupu fce), takže se rychlost smrskne na
3,9s ku 4,7s
a tady je už asi rychlejší použít ten substring. I když todle řešení je robustnější, tamto bude při velkym počtu vyhledanejch řetězců (popř. vyhledávanejch řetězců, kde zas stačí jeden UTF/UCS převod) zpomalovat víc, tam se projeví rychlost kódování UCS-2 (zkoušel jsem jen svůj algoritmus, při vyhledání 'a' byl najednou rozdíl
mezi UCS a UTF-8 1 ku 5,9s (menší počet iterací).

Ideální by bylo, kdyby (mb_)substr řetěazce nekopíroval, ale to bychom chtěli od php příliš....

Jo, ještě v těch řešeních je nadužívání mb_strlen - vzhledem k tomu, že u mb se musí projít celej řetězec, tak tam to vadí, i když jsem předtim tvrdil, že ne... :-(

Ad na klientu: Šlo by to i zkombinovat: na serveru převést utf8 na ascii a na klientu to zvýraznit :-)

PS: Jo a UCS-2 nemá všechny znaky, takže přijdeš o starou čínštinu apod... UCS-4 to řeší, ale to by bylo zas pomalejší, přecijenom cca 3x větší paměťový nároky se poznaj....
Název: Re: PHP: zvýraznění výrazu a diakritika
Přispěvatel: ghost 25. 01. 2011, 22:56:50
jo tak s tema znakama jsem potom taky pekne na omylu - az se stydim.
kazdopadne na php.net je zajimavy benchmark - vysledek je asi jasny, strlen nejspis taky pocita po jednom, akorat je pevna delka, takze je rychlejsi ...
# test runs: 1000000
# benchmarking strlen vs. mb_strlen
# normal strlen: 3.6795361042023 ms, average: 3.6795361042023E-6 ms
# mb_strlen: 5.5934538841248 ms, average: 5.5934538841248E-6 ms
ok 1 - mb_strlen is slower than strlen