Algoritmus hledání duplicitních textů

[PrograMig]

Dobrý den, rád bych se poradil či zeptal kde hledat informace o efektivním postupu řešení úlohy filtrování duplicitních slovních spojení, celých vět atp. ze vstup. textu. Nejsem v této oblasti příliš zběhlý a napoprvé mě napadlo "jen", že by to mohlo vést na nějaký kompresní algoritmus jako např. LZW (Lempel-Ziv-Welch), ale nejsem si jistý. Také mne napadlo, že bych mohl napřed ke všem slovům nechat spočítat nějaký hash kód, ale ani zde nevím, jaký postup zvolit, aby byly všechny hash kódy pokud možno unikátní (aby dvě či více různých slov neměla stejnou hash hodnotu). Díky hash kódům by pak mohlo být hledání shodných slov rychlejší. Předem díky za pomoc.

[Reklama]

[TTTTTTT]

Kompresní algoritmus se mi moc nezdá. Jednoduchý algoritmus je procházet slova na vstupu a vkládat je do nějaké datové struktury, která pozná, že v ní daný prvek už je a dle toho ho vypsat nebo ne. Datová struktura může být hash tabulka nebo třeba trie. Shodné hashe nemusí být nutně na škodu, jen je potřeba do hash tabulky ukládat i slova, která odpovídají hashům a v případě kolize ověřit, že jsou opravdu stejná.

[Croul]

Dobrý den, rád bych se poradil či zeptal kde hledat informace o efektivním postupu řešení úlohy filtrování duplicitních slovních spojení, celých vět atp. ze vstup. textu. Nejsem v této oblasti příliš zběhlý a napoprvé mě napadlo "jen", že by to mohlo vést na nějaký kompresní algoritmus jako např. LZW (Lempel-Ziv-Welch), ale nejsem si jistý. Také mne napadlo, že bych mohl napřed ke všem slovům nechat spočítat nějaký hash kód, ale ani zde nevím, jaký postup zvolit, aby byly všechny hash kódy pokud možno unikátní (aby dvě či více různých slov neměla stejnou hash hodnotu). Díky hash kódům by pak mohlo být hledání shodných slov rychlejší. Předem díky za pomoc.

To, co říkáš, je úplně z cesty. Proč bys texty, ve kterých chceš hledat duplicity, komprimoval? Když zahashuješ slova, budeš místo duplicity původních slov hledat duplicitu hashů. Ani tím se výsledku nepřiblížíš

Není to zas tak jednoduchá věda. Za mě doporučuju neobjevovat znovu kolo a něco si o tom přečíst. Je to celkem profláknuté akademické téma, ke kterému najdeš spoustu diplomek a vědeckých publikací.

[iwtu]

Vasa myslienka je podobna myslienke http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm plus si k hashom spravit zoznam pozic. Takou klasikou je este Aho-Corasick ale teno robi strom, co moze byt pamatovo celkom drahe. Ale ako, pokial toho textu nie su fakt haldy a slova sa tam neopakuju tisice krat ale ide o par vyskutov tak da sa vystacit aj so shellom sort a uniq -c. Ide o to, co Vas presne zaujima. uniq -c zistite slova a pocet ich vyskytov potom mozne dat kazde slovo do grepu napr..  Strigologia je fakt veda ale pokial sa naozaj nepotrebujete prehladavat kvantami textu tak mi sort, uniq a grep pride vcelku efektivny pokial potrebujete zistit iba nieco konkretne.

[davkol]

Jak si to má poradit s úmyslným opakováním, pokud jde o smysluplný text psaný člověkem pro lidi?

[Reklama]

[neruda]

Dobrý den, rád bych se poradil či zeptal kde hledat informace o efektivním postupu řešení úlohy filtrování duplicitních slovních spojení, celých vět atp. ze vstup. textu. Nejsem v této oblasti příliš zběhlý a napoprvé mě napadlo "jen", že by to mohlo vést na nějaký kompresní algoritmus jako např. LZW (Lempel-Ziv-Welch), ale nejsem si jistý. Také mne napadlo, že bych mohl napřed ke všem slovům nechat spočítat nějaký hash kód, ale ani zde nevím, jaký postup zvolit, aby byly všechny hash kódy pokud možno unikátní (aby dvě či více různých slov neměla stejnou hash hodnotu). Díky hash kódům by pak mohlo být hledání shodných slov rychlejší. Předem díky za pomoc.

To, co říkáš, je úplně z cesty. Proč bys texty, ve kterých chceš hledat duplicity, komprimoval? Když zahashuješ slova, budeš místo duplicity původních slov hledat duplicitu hashů. Ani tím se výsledku nepřiblížíš

Není to zas tak jednoduchá věda. Za mě doporučuju neobjevovat znovu kolo a něco si o tom přečíst. Je to celkem profláknuté akademické téma, ke kterému najdeš spoustu diplomek a vědeckých publikací.

Ne, z cesty mluvis ty.
On nechce komprimovat slova, on chce pouzit podobny algoritmus na vyhledavani duplicit jako LZW.

[omg]

rzip umi dobre smrsknout texty s duplicity. ma vhodnejsi nastaveni hodnot a delsi bloky na prohledavani jinak dal komprimuje stejne jako tusim bzip, ale porad to neni rozsahovy/presahovy, ale blokovy algoritmus a nepracuje az tak uplne s duplicitou slov, ale s entropii informace.