Určení fráze společné všem prvkům pole

puhy.cz

(5 hodnocení)

28. 8. 2019 22:25:44

Zdravím a potřeboval bych poradit s menším zádrhelem:

Mám pole, které obsahuje podobné texty. Např.

atd ...

Nebo:

atd ....

a chtěl bych z toho dostat frázi, která je společná všem prvkům. V tomto případě by to byla fráze " tlaková hadice" a "elektrolitycký kondenzátor nippon" tuto frázi ale předem neznám. A nevím ani jak bude dlouhá. Jak by jste na to šli?

Díky za nakopnutí.

28. 8. 2019 22:25:44

https://webtrh.cz/diskuse/urceni-fraze-spolecne-vsem-prvkum-pole/#reply1413466

kolousek

28. 8. 2019 23:03:42

Každou větu rozdělit na slova podle mezer, slova vložit do pole a udělat si ještě na každém slovu příznak "obsahuje". Projet všechny věty navzájem a nastavit příznak (non case sensitive porovnání). Ze slov s příznakem "obsahuje" udělat frázi.

28. 8. 2019 23:03:42

https://webtrh.cz/diskuse/urceni-fraze-spolecne-vsem-prvkum-pole/#reply1413465

node

(5 hodnocení)

28. 8. 2019 23:59:59

prebehni si vsetky retazce cez transliteraciu do asci, idealne bez interpunkcie.

sprav foreach pre kazdy zaznam, splitni to na medzerach a ziskaj pre kazde slovo zaciatocnu a konecnu poziciu v stirngu. cize ak mas "abcd efgh jklmn" tak pre abcd to bude 0,3, pre efgh to bude 5,8 a td. potom si sprav zase slucku pre kazdy zaznam a ignoruj ten akitvny, samozrejme.

nasledne pre kazde slovo ktore mas zacni kontorlovat ci retazec obsahuje to slovo, ak ano tak zacni pridavat k tym poziciam -1 a +1, podla toho vytiahni susedny znak z originalneho retazca a znovu porovnaj az kym sa nezaseknes na oboch stranach alebo nenarazis na zaciatok alebo koniec aktivneho stringu. niekam si zapis zhodny retazec, jeho dlzku a deltu/index zaznamu ktory ho obsahoval.

na koniec si usporiadaj najdene zhody podla dlzky a podla poctu zhod, to uz je na tebe ktore prioritizujes.

ak nie je jasne co pisem tak nevadi lebo je pol noc a nechce sa mi to inak rozpisovat.

28. 8. 2019 23:59:59

https://webtrh.cz/diskuse/urceni-fraze-spolecne-vsem-prvkum-pole/#reply1413464

TomasX

(4 hodnocení)

29. 8. 2019 07:47:58

řada běžných algoritmů pro texty je popsaná na http://www.512.cz/index.php?title=Algoritmy_zpracován%C3%AD_textů_–_operace_s_řetězci,_porovnán%C3%AD_se_vzorem_(KMP,_Boyer-Moore_algoritmus),_nejdelš%C3%AD_společný_podřetězec_(LCS_algoritmus),_vzdálenost_mezi_řetězci,_datová_struktura_Trie_a_použit%C3%AD

Pro tebe je asi nejjednodušší si dát řetězce do pole, seřadit je podle abecedy, vzít první a poslední rětězec, poslední projít po písmenech a zastavit se až písmena přestanou být shodná s těmi na stejné pozici u prvního řetězce v seřazeném poli.

Porovnávat musíš bez ohledu na velikosti písmen. Pokud chceš sadu rětězců sdružit podle jejich společných prefixů, algoritmus by byl složitější, musel bys si pamatovat nejdelší prefix, posunout se na další slovo a poté sdružit slova. Už by se jednalo o NP-problém a složitost by šla exponenciálně nahoru.

29. 8. 2019 07:47:58

https://webtrh.cz/diskuse/urceni-fraze-spolecne-vsem-prvkum-pole/#reply1413463

puhy.cz

(5 hodnocení)

29. 8. 2019 15:15:44

Takže díky všem, snad vyřešeno, koho by to zajímalo tak asi takto:

použil jsem nakonec sphinx + sphinx api pro php, ten mi tam už běžel (index aby se nepřetěžovala db, něco jako elasticsearch) a pak nad výsledkem funkci similar_text https://www.php.net/manual/en/function.similar-text.php

pak pár foreachů a ještě dynamické nastavení po kolika slovech to probublává podle velikosti výsledku.

Překvapivě to je docela rychlé, teď ještě testuji omezení různých znaků a nastavení vah....

29. 8. 2019 15:15:44

https://webtrh.cz/diskuse/urceni-fraze-spolecne-vsem-prvkum-pole/#reply1413462

Pro odpověď se přihlašte.

Přihlásit