Algoritmus šindele (z anglického shingles - scales) je algoritmus určený k nalezení kopií a duplikátů příslušného textu ve webovém dokumentu. Nástroj pro odhalování plagiátorství .
Udi Manber v roce 1994 jako první na světě vyjádřil myšlenku hledání duplikátů a v roce 1997 Andrey Broderoptimalizoval a dovedl jej k logickému závěru a dal tomuto systému jméno – „algoritmus šindelů“.
Fáze, kterými text prochází, byly porovnány:
Kanonizace textu přináší původní text do jednotné normální formy. Text je vyčištěn od předložek, spojek, interpunkčních znamének, HTML tagů a dalších nepotřebných „odpadků“, které by neměly být zahrnuty do srovnání. Ve většině případů se také navrhuje odstranit z textu přídavná jména, protože nenesou sémantickou zátěž.
Ve fázi kanonizace textu mohou být podstatná jména také redukována na nominativní pád, jednotné číslo nebo z nich mohou být ponechány pouze kořeny.
Pásový opar jsou podsekvence slov extrahovaných z článku. Z porovnávaných textů je třeba vybrat podposloupnosti slov, které na sebe navazují po 10 kusech (délka šindele). Výběr se překrývá, nikoli od konce ke konci. Rozdělením textu na podsekvence tedy získáme sadu šindelů rovnající se počtu slov mínus délka šindelu plus jedna.
Principem algoritmu šindelů je porovnání náhodného vzorku kontrolních součtů šindelů (podsekvencí) dvou textů mezi sebou.
Problémem algoritmu je počet porovnání, protože to přímo ovlivňuje výkon. Nárůst počtu šindelů pro srovnání je charakterizován exponenciálním nárůstem operací, což kriticky ovlivní výkon.
| zpracování přirozeného jazyka | |
|---|---|
| Obecné definice | |
| Analýza textu |
|
| Odkazování |
|
| Strojový překlad |
|
| Identifikace a sběr dat | |
| Tematický model | |
| Peer review |
|
| Rozhraní přirozeného jazyka | |