wiki:cs/KontrolaDuplicit

Version 1 (modified by xkocinc, 10 years ago) (diff)

--

Kontrola duplicit


Tento článek popisuje hledání a odstranění duplicitních dokumentů v korpusech.

Úvod

Co jsou to duplicitní dokumenty - vysvětlení termínů

  • Korpus je složen z jednoho nebo více vertikálů.
  • 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ů.
  • Dokument je část vertikálu mezi značkami <doc id="identifikátor"> a <doc/>.
  • Identifikátor dokumentu je hodnota atributu id značky doc a je jednoznačný v celém korpusu.
  • 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.

Příčiny duplicit jsou:

  • Některé zdroje byly omylem zařazeny do korpusu vícekrát.
  • 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).
  • Některé články jsou si velmi podobné (kurzovní lístky, předpovědi počasí).

Našim cílem je vyřešit tento problém. Což znamená:

  • Smazat ty dokumenty, které byly omylem zařazeny vícekrát.
  • Označit fakt, že některé dokumenty jsou si velmi podobné, a že pro další zpracování chceme použít jen jeden z nich.

Hledání duplicitních dokumentů

Zkoumá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í.

Ilustrující sada duplicitních dokumentů

Tyto dokumenty jsou intuitivně duplicitní:

Dokument 1:

<doc id="1">
<head>
Špidla
</head>
<p>
Ministr
práce
a
sociálních
věcí
</p>
</doc>

Dokument 2:

<doc id="2">
<head>
Špidla
</head>
<p>
Ministr
práce
a
sociálních
věcí
</p>
</doc>

Dokument 3:

<doc id="3">
<p>
Špidla
Ministr
práce
a
sociálních
věcí
</p>
</doc>

Dokument 4:

<doc id="4">
<p>
Špidla
-
ministr
práce
a
sociálních
věcí
</p>
</doc>

Považujme dokument 1 za základní. BRDokument 2 je s ním zcela identický až na to, že se liší v identifikátoru. BRDokument 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ý. BRDokument 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.

Signaturní funkce

Výš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.

Základní signaturní funkce jsou:

  • Identita až na jméno dokumentu: realizována filtrem
    grep -v '^<doc'
  • Nezávislost na značkování: realizována filtrem
    grep -v '^<.*>$'
  • Signatura dokumentu: realizována filtrem
    grep -v '^<.*>$'|cstocs il2 ascii|tr "A-Z" "a-z" | tr -cd "a-z"| hashovaci_funkce 
    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:
T_Sub: 1A35C6DC

Pro 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:
cut -f1 | grep -v '^<doc'

Rozklad na třídy ekvivalence vzhledem k relaci rovnosti signaturních funkcí

Zvolme 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ů.

Odstranění a označení duplicitních dokumentů

Návaznost vytvořených nástrojů, vytvoření korpusu ALL.

Dejme 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.

Jak budeme postupovat?

Nejdří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):

$ traverse_dir meta attrib_insert_meta

Potom si vybudujeme seznam všech dokumentů:

$ traverse_dir meta make_doc_list > vertikal.list

Pak 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:

$ cat vertikal.list | sort -t: -k1,1 | repeated_lines --delimiter=: --output=uniq --field=1 | cut -d: -f4-6 | sort -t: -k3,3 | list2vert | encode

To je nejjednodušší způsob, jak se vypořádat s duplicitama.