Changes between Initial Version and Version 1 of cs/KontrolaDuplicit


Ignore:
Timestamp:
Feb 28, 2014, 1:36:57 PM (10 years ago)
Author:
xkocinc
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • cs/KontrolaDuplicit

    v1 v1  
     1= Kontrola duplicit = #Kontrola_duplicit-1
     2[[BR]]        Tento článek popisuje hledání a odstranění duplicitních dokumentů v korpusech.   
     3
     4= Úvod = #A.2BANo-vod
     5== Co jsou to duplicitní dokumenty - vysvětlení termínů == #Co_jsou_to_duplicitn.2BAO0_dokumenty_-_vysv.2BARs-tlen.2BAO0_term.2BAO0-n.2BAW8-
     6
     7 * ''Korpus'' je složen z jednoho nebo více vertikálů.   
     8
     9
     10 * ''Vertikál'' je textový soubor ve formátu XML, navíc členěný na řádky.  Každý vertikál obsahuje jeden nebo více dokumentů.   
     11
     12
     13 * ''Dokument'' je část vertikálu mezi značkami <doc id="identifikátor"> a <doc/>.   
     14
     15
     16 * ''Identifikátor'' dokumentu je hodnota atributu id značky doc a je jednoznačný v celém korpusu.   
     17
     18
     19 * ''Duplicitní dokumenty'' jsou dva nebo více různých dokumentů (s různými identifikátory) mající stejný nebo téměř stejný obsah.   
     20
     21
     22
     23Příčiny duplicit jsou:   
     24
     25 * Některé zdroje byly omylem zařazeny do korpusu vícekrát.   
     26 * Některé články jsou zvěřejněny vícekrát v různých zdrojích (zprávy ČTK v různých denících).   
     27 * Některé články jsou si velmi podobné (kurzovní lístky, předpovědi počasí).   
     28
     29Našim cílem je vyřešit tento problém. Což znamená:   
     30
     31 * Smazat ty dokumenty, které byly omylem zařazeny vícekrát.   
     32 * Označit fakt, že některé dokumenty jsou si velmi podobné, a že pro další  zpracování chceme použít jen jeden z nich.   
     33
     34= Hledání duplicitních dokumentů = #Hled.2BAOE-n.2BAO0_duplicitn.2BAO0-ch_dokument.2BAW8-
     35Zkoumáme-li  zda dva dokumenty jsou duplicitní můžeme použít různě  přísná kritéria.  Nejjednodušší řešení je prosté porovnání: dokumenty uložíme do souborů a  použijeme příkaz `cmp`. Je ale nutné abychom nebrali v úvahu řádek se značkou `<doc id="identifikátor">`, protože různé dokumenty mají vždy různé identifikátory.  Toto můžeme vyřešit pomocí příkazu `grep -v '^<doc '`, který tento problém odstraní.   
     36
     37== Ilustrující sada duplicitních dokumentů == #Ilustruj.2BAO0-c.2BAO0_sada_duplicitn.2BAO0-ch_dokument.2BAW8-
     38Tyto dokumenty jsou intuitivně duplicitní: 
     39
     40Dokument 1:
     41
     42{{{
     43<doc id="1">
     44<head>
     45Špidla
     46</head>
     47<p>
     48Ministr
     49práce
     50a
     51sociálních
     52věcí
     53</p>
     54</doc>
     55}}}
     56Dokument 2:
     57
     58{{{
     59<doc id="2">
     60<head>
     61Špidla
     62</head>
     63<p>
     64Ministr
     65práce
     66a
     67sociálních
     68věcí
     69</p>
     70</doc>
     71}}}
     72Dokument 3:
     73
     74{{{
     75<doc id="3">
     76<p>
     77Špidla
     78Ministr
     79práce
     80a
     81sociálních
     82věcí
     83</p>
     84</doc>
     85}}}
     86Dokument 4:
     87
     88{{{
     89<doc id="4">
     90<p>
     91Špidla
     92-
     93ministr
     94práce
     95a
     96sociálních
     97věcí
     98</p>
     99</doc>
     100}}}
     101Považujme dokument 1 za základní.  [http://nlp.fi.muni.cz/cs/BR BR]Dokument 2 je s ním zcela identický až na to, že se liší  v identifikátoru. [http://nlp.fi.muni.cz/cs/BR BR]Dokument  3 se od dokumentu 1 liší v použitých  značkách - tento rozdíl vzniká  typicky pokud převod provádějí rozliční autoři - autor dokumentu 3 byl  při převodu evidentně méně pečlivý. [http://nlp.fi.muni.cz/cs/BR BR]Dokument  4 se od dokumentu 1 liší v použitých  značkách, ale i v pozicích -  obsahuje navíc pomlčku a slovo ministr má malé počáteční písmeno. 
     102
     103== Signaturní funkce == #Signaturn.2BAO0_funkce
     104Výše  zmíněný způsob hledání duplicit odhalí jako duplicitní jen dokumenty 1 a  2. Metoda pro odhalování duplicitních dokumentů je taková, že pomocí  nějakého filtru - signaturní funkce aplikovaného na zkoumané dokumenty  si vyrobíme otisky (signatura, fingerprint) a testujeme, zda jsou tyto  otisky identické. Pokud ano, říkáme, že tyto dokumenty jsou duplicitní  vzhledem k dané signaturní funkci. 
     105
     106Základní signaturní funkce jsou:   
     107
     108 * ''Identita až na jméno dokumentu:'' realizována filtrem [[BR]] `grep -v '^<doc'`   
     109
     110
     111 * ''Nezávislost na značkování:'' realizována filtrem[[BR]]  `grep -v '^<.*>$'`   
     112
     113
     114 * ''Signatura dokumentu:'' realizována filtrem [[BR]] `grep -v '^<.*>$'|cstocs il2 ascii|tr "A-Z" "a-z" | tr -cd "a-z"| hashovaci_funkce ` [[BR]]  Tedy tato funkce je realizována kolonou, která odstraňuje značkování  dokumentu, potom písmena české abecedy převede na ASCII, potom velká  písmena převede na malá, potom odstraní vše kromě malých písmen z  množiny [a-z] a tento výsledek zkrátí pomocí pro tento účel vytvořené  hashovací funkce na maximálně osmimístné hexadecimální číslo. Toto číslo  se nazývá signatura dokumentu a je uloženo v metainformacích v atributu  T_Signat. Například:
     115
     116
     117{{{
     118T_Sub: 1A35C6DC
     119}}}
     120   
     121
     122Pro morfologicky značené korpusy (DESAM) je vhodné na začátek kolony přidat příkaz `cut -f1`,  který odstraní morfologické značky, které  jsou oddělěny tabulátorem.  Takže pro morfologicky značený korpus získáme například tuto signaturní  funkci: [[BR]] `cut -f1 | grep -v '^<doc'`
     123
     124== Rozklad na třídy ekvivalence vzhledem k relaci rovnosti signaturních funkcí == #Rozklad_na_t.2BAVkA7Q-dy_ekvivalence_vzhledem_k_relaci_rovnosti_signaturn.2BAO0-ch_funkc.2BAO0-
     125Zvolme  pevně některou signaturní funkci. Ke každému dokumentu tak máme jeho  signaturu. Pokud jsou signatury dvou dokumentů rovny jsou tyto dokumenty  podobné. Tato rovnost je pochopitelně relací ekvivalence a vytváří  rozklad na množině všech dokumentů.   
     126
     127= Odstranění a označení duplicitních dokumentů = #Odstran.2BARs-n.2BAO0_a_ozna.2BAQ0-en.2BAO0_duplicitn.2BAO0-ch_dokument.2BAW8-
     128== Návaznost vytvořených nástrojů, vytvoření korpusu ALL. ==
     129Dejme  tomu, že máme v adresáři /nlp/corpora/vertical všechna korpusová data  (vertikály a metainformace). Chceme vybudovat korpus, který bude  obsahovat jen neduplicitní dokumenty. 
     130
     131Jak budeme postupovat? 
     132
     133Nejdřív  se ujistíme, že v metainforamcích máme uloženu signaturu dokumentu.  Pokud si nejsem zcela jisti, můžeme ji vložit znovu (jedná se ale o  časově náročnou operaci):
     134
     135{{{
     136$ traverse_dir meta attrib_insert_meta
     137}}}
     138Potom si vybudujeme seznam všech dokumentů:
     139
     140{{{
     141$ traverse_dir meta make_doc_list > vertikal.list
     142}}}
     143Pak  tento seznam setřídíme podle signatury, tím se stejné signatury seřadí  za sebe a obdobou programu uniq ponecháme jen jeden z duplicitních  dokumentů a nakonec vybereme 4. až 6. sloupec pro list2vert, který ze  slušnosti setřídíme podle souboru a můžeme spustit encode:
     144
     145{{{
     146$ cat vertikal.list | sort -t: -k1,1 | repeated_lines --delimiter=: --output=uniq --field=1 | cut -d: -f4-6 | sort -t: -k3,3 | list2vert | encode
     147}}}
     148To je nejjednodušší způsob, jak se vypořádat s duplicitama.