Hlavním cílem projektu je vytvoření konečného automatu (KA) z knowledge base (KB), který bude možné použít v kombinaci s programem figa (FIt GAzetter) pro hledání entit a jejich fragmentů v textu.
V rámci tohoto projektu existuje také program autocomplete (vyhledávání uložených názvů entit), který lze použít pro KA figy.
Všechny programy a skripty lze nálezt v git repozitáři na serveru knot09:
git clone ssh://user@knot09.fit.vutbr.cz/var/decipher/secapi/
Files:
secapi/NER/figav08 // složka s nástroji figa ve verzi 08
secapi/NER/figav08/make_automat/ // složka s nástroji pro vytvoření KA
secapi/NER/autocomplete // složka s nástrojem autocomplete pro KA
Vyhledávač figa je přizpůsoben pro hledání v konečném automatu, který mimo samotného názvu entity obsahuje i informaci o umístění entity v KB (číslo řádku). Tato informace se posléze použije k nalezení entit v souboru s Knowledge Base (KB.all) ze kterého byl konečný automat vytvořen. Výstup je ukládán do objektu typu string (pro účely python bindingu). Pro výpis nalezených dat na stdout je nutné použít přepínač -p (viz. paramtery).
Spuštění:
figav08 -d <automata> [-f <input_file>|-p|-h]
Parametry:
-d - povinný parametr; definuje název souboru s KA (standardně automata.fsa)-f - nepovinný parametr; definuje vstup ze souboru-p - nepovinný parametr; výstup vyhledávače bude vypsán na stdout-h - nepovinný parametr; výpis nápovědy, následuje konec programuPříklad spuštění programu figav08:
./figav08 -d automata.fsa -p < soubor (vstup ze stdin | výstup do stdout)
./figav08 -d automata.fsa -f soubor (vstup ze souboru | výstup pouze do stringu)
./figav08 -d automata.fsa <<< "A Bird" (vstup ze stdin | výstup pouze do stringu)
Příklad výstupu:
čísla řádků v KB poč. offsety konc. offset název entity
36739 1 6 A Bird
Konečný automat (automata.fsa) se vytváří pomocí nástrojů fsa p. Daciuka (fsa_build nebo fsa_ubild). Pro tento proces byl vytvořen skript create_fsa_v05.sh , který využívá těchto nástrojů a dokáže vytvořit KA pro vyhledávač figa. Je však nutné dodržet formát vstupních dat (viz. dále).
Formát dat vložených do končeného automatu:
název_entity|číslo_řádku_v_KB[;další_číslo;...]
(např. A Bird|36739)
Formát výstupních dat. Pokud daný term odpovídá více entitám (řádkům) v KB, jsou tyto hodnoty odděleny znakem ;:
číslo_řádku[;číslo_řádku;...] \t offset_začátku_slova \t offset_konce_slova \t název_entity
Vytvoření KA
Automat se vytváří pomocí skriptu create_fsa_v05.sh. Jako parametr je nutné uvést soubor s Knowledge Base (KB.all) a také soubory names a activities.
Použití:
secapi/NER/figa/make_automat/create_fsa_v05.sh ../../KB.all names activities
Poté je vytvořen soubor automata.fsa o adresář výše.
Po každé změně souboru KB.all je nutné vytvořit konečný automat znovu. V opačném případě je vysoce pravděpodobné, že záznamy nebudou odpovídat hledanému řetězci.
Figa dokáže rozpoznat, zda je v textu obsažen fragment některé z entit, které se nacházejí v KB.all. Výpis nalezeného fragmentu se liší oproti celé entitě v údaji na pozici 1 (row_number_in_KB). Pro tyto případy je hodnota implicitně nastavena na "0".
Příklad výstupu:
čísla řádků v KB poč. offsety konc. offset název entity
0 1 5 James
Tato vlastnost umožňuje vyhledávači vracet se ke slovu, které následuje okamžitě za aktuálním počátkem vyhledávání. Figa vyhledává implicitně entity s nejdelším možným názvem.
Více informací o implementaci lze najít v komentářích souboru figa.cc (funkce lookup, lookup_file nebo lookup_string).
Příklad:
"Já a James Blain jsme navštívili divadlo. A A Bird šel s námi."
1. vyhledaná entita -> James Blain (počátek řetězce "^James Blain jsme ....$")
2. -> Blain (počátek řetězce "^Blain jsme ....$")
3. -> A A (počátek řetězce "^A A Bird šel ....$")
4. -> A Bird (počátek řetězce "^A Bird šel ....$")
Tato vlastnost zajišťuje pravděpodobnější nalezení entity v textu.
Všechny nástroje pro práci s KA (vytváření + figa) jsou přizpůsobeny pro zpracování vstupního řetězce/souboru obsahující UTF-8 znaky. Funkci převodu u figy lze najít v souboru figa.cc (utf2symbols aa dec2hex). Převod pro proces vytváření KA lze najít v souboru utf2symbols.cc. Více informací o implementaci lze najít v komentářích zdrojového kódu.
Nástroje využívají algoritmu pro převod UTF-8 znaků na jejich ASCII reprezentaci ("š" -> "š").
Pro vyhledávání entit ve fulltextu jsou vytvořena pravidla pro přeskakování znaků. Před začátkem vyhledávání se tyto znaky ve vstupních řetězci/souboru jednoduše přeskočí a neberou se v potaz.
Toto však platí jen pro začátky slov, nikoliv v průběhu vyhledávání nebo na konci slov.
Znaky k přeskakování lze také jednoduše doplňovat do zdrojového kódu figy (figa.cc).
Postup pro přidání:
Ve funkci bool marker::to_skip(char) stačí přidat další větev -> case 'požadovaný_znak':.
Knowledge base (KB.all) obsahuje několik typů entit. Data jsou na každém řádku záznamu oddělována tabulátorem. Více informací k souboru KB.all je možné nalézt zde.
Testovací data obsahují názvy entit (tzn. 1 název = 1 řádek) v rozmezí 10.000 - 10.000.000.
Testovací data lze najít v git repozitáři:
secapi/NER/data/performance/
These stats are were measured on 22.11.2013 on server athena1:
time ./figav08 -d automata.fsa -p < data10.test > /dev/null
real 0.197 user 0.140 sys 0.054
time ./figav08 -d automata.fsa -p < data100.test > /dev/null
real 1.969 user 1.886 sys 0.058
time ./figav08 -d automata.fsa -p < data1000.test > /dev/null
real 15.420 user 15.282 sys 0.119
time ./figav08 -d automata.fsa -p < data10000.test > /dev/null
real 145.513 user 144.369 sys 0.728
Tyto údaje jsou pouze orientační a byly naměřeny dne 22.11.2013 na serveru athena1.
Autocomplete je program vytvořený pro KA figy. Pro posloupnost znaků vrací nástroj entity z KA, jejichž prefix se shoduje s danou posloupností. Jedná se o upravený nástroj figy.
Pro vstupní řetězec vypíše nástroj implicitně 5 názvů entit, které mají stejný prefix a jsou obsaženy v konečném automatu.
Entity jsou řazeny podle tohoto prioritního seznamu:
" ',-.:aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ&0123456789#;|"
Program je ve stavu funkční prototyp a lze ho najít v git repozitáři na tomto umístění:
secapi/NER/figa
Pro autocomplete existuje několik typů KA. Jsou charakterizovány podle prefixu (více info na KB).
Popis ve zkratce:
VISUAL ARTIST (prefix: p)
LOCATION (prefix: l)
ARTWORK (prefix: w)
MUSEUM ( prefix: c)
EVENT (prefix: e)
ART FORM (prefix: f)
ART MEDIUM (prefix: d)
ART PERIOD MOVEMENT (prefix: m)
ART GENRE (prefix: g)
NATIONALITY (prefix: n)
ALL (prefix: x)
Použití:
secapi/NER/autocomplete/figa_autocomplete_v01 [-d -f -p -h -m]
Parametry:
-d - povinný parametr; definuje název souboru s KA (standardně [plwcefdmgnx]_automata.fsa)-f - nepovinný parametr; definuje vstup ze souboru-p - nepovinný parametr; výstup vyhledávače bude vypsán na stdout-h - nepovinný parametr; výstup vyhledávače bude vypsán na stdou-m - nepovinný parametr; počet entit, které se mají dohledat (implicitně 5)Příklad spuštění programu figa_autocomplete:
./figav08 -a -d l_automata.fsa -p < soubor (vstup ze stdin | výstup na stdout)
./figav08 -a -d w_automata.fsa -f soubor (vstup ze souboru | výstup pouze do stringu)
./figav08 -a -d p_automata.fsa -m 2 <<< "Paris" (vstup ze stdin | výstup pouze do stringu | 2 záznamy)
Příklad výstupu pro vstup "Paris":
Paris
2604662;2640630;2682383;2686449;2703450;2709352;2711956;2714570;2741670;2747387;2801217;2833100;2837 451;2861981;2875907;2901014;2904894;2954273;2956455;2975011;3116612;3135687;3179239;3184675;3238521;3306306;3400867;3401125;3425723;3464984;3515932
Paris - Charles de Gaulle Airport 3181703
Paris - Le Bourget Airport 3400405
Paris - Orly Air Base 3462031
Paris - Orly Airport 3147659
Paris Appeal Court 3239613
Tento nástroj slúži na prevedenie čísel riadkov v súbore namelist.ASCII z textovej podoby na binárny zápis (kvôli šetreniu miestom). Je začlenený do scriptu pre tvorbu KA create_fsa_v05.sh. Nástroj kvôli problémom s tvorbou automatu pri takomto zápise čísel používa jednoduché kódovanie (viď nižšie). Pri nájdení fragmentu (fragment_name|N), nástroj prepíše daný záznam na výstup bez zmeny.
Zdrojový kód spolu s programom sa nachádza v priečinku:
secapi/NER/figa/make_automat/
V komentároch v zdrojovom kóde je algoritmus podrobne popísaný.
Formát vstupných dát:
Názov entity tvorí ľubovoľná postupnosť znakov okrem '|', ktorý oddeľuje názov od čísel riadkov. Čísla sú vo formáte string - pri väčšom počte čísel sú oddelené znakom ';'. Riadok (záznam) je ukončený znakom '\n'.
názov_entity|číslo_riadku_v_KB[;ďalšie_číslo;...]
Formát výstupných dát:
Názov entity tvorí ľubovoľná postupnosť znakov okrem '|', ktorý oddeľuje názov od čísel riadkov. Čísla sú v binárnom formáte (4 bajty na jedno číslo) - pri väčšom počte čísel sú čísla priamo za sebou bez oddeľovacích znakov. Riadok (záznam) je ukončený znakom '\n'.
názov_entity|číslo_riadku[ďalšie_číslo][ďalšie_číslo]...
Ušetrené miesto vo vstupnom súbore namelist.ASCII(.bin) je približne 12% (pri aktuálnej verzii KB.all je to 35 629 774 B).
Ušetrené miesto v konečnom automate je približne 5% (pri aktuálnej verzii KB.all 9 616 084 B).
Kódovanie čísel:
Čísla sú načítavané (spolu s ostatným textom) zo štandardného vstupu a prevádzané do binárnej podoby. Ukladané sú do premennej typu unsigned int. Následne sa z 32 bitov odrežú vrchné 4 bity a zvyšných 28 bitov sa rozdelí na 4 časti (po 7 bitov), z ktorej každá sa zapíše do jedného bajtu (char). V každom vytvorenom bajte sa zapísané bity posunú (bitovým posuvom) o jeden bit doľava, a následne sa bit s indexom [0] v každom bajte nastaví fixne na hodnotu 1. Takto upravené bajty sa odošlú na štandardný výstup - prvé idú hodnotovo významnejšie bajty.
Toto kódovanie čísel bolo zvolené kvôli chybe pri vytváraní konečného automatu pri klasickom binárnom zápise čísla, kedy sa stávalo, že niektoré bajty týchto čísel odpovedali '\0' alebo '\n' čo sú v automate oddeľovacie znaky (minimálne jeden z týchto dvoch). Nevýhodou tohto kódovania je zmenšenie maximálneho možného čísla, ktoré takto môžme zapísať na (2^28 - 1) = 268 435 455.
Formát zápisu čísla v binárnej podobe (dokopy 32 bitov):
[7_bits] + [1] + [7_bits] + [1] + [7_bits] + [1] + [7_bits] + [1]
Automaty sa vytvárajú zvlášť pre každý nástroj. Scripty pre vytvorenie automatov sa nachádzajú v priečinku:
secapi/NER/figa/make_automat/create_fsa.sh
secapi/NER/figa/make_automat/create_fsa_autocomplete.sh
Príklady spustenia (parametre v zdrojových súboroch):
./create_fsa.sh [-l] [-s] --knowledge-base=../../KBstatsMetrics.all --names=names
Parametry:
-l - vytvorenie lowercase verzie automatu-s - vytvorenie automatu pre spellchecking ./create_fsa_autocomplete.sh ../../KBstatsMetrics.all # tvorba automatov pre autocomplete
Figa aj autocomplete sú zlúčené do jedného programu. Pre autocomplete sa ale používa script autocomplete.py (viď. Autocomplete).
Príkaz "make" v priečinku secapi/NER/figa/sources/ vytvorí binárny program s názvom figav08 v priečinku secapi/NER/figa/.
Parametre spustenia:
-d FILE - povinný parameter; definuje názov súboru s KA (*.fsa)-a - zapína funkcionalitu autocomplete-b - aktivuje vracanie offsetu v bytoch (offset sa defaultne vracia v znakoch) [ONLY FIGA]-f FILE - vstupný súbor-h - nápoveda-m NUMBER - maximálny počet entít, ktoré budú vrátené, ak je zapnutá funkcionalita autocomplete (default: 5) [ONLY AUTOCOMPLETE]-o - figa bude vracať aj prekrývajúce sa entity [ONLY FIGA]-p - výstup bude vypisovaný na stdout-q - text v úvodzovkach/apostrofoch bude braný ako celok, figa nebude vraciať jeho časti ako entity [ONLY FIGA]-s FILE - zapína spellchecking, definuje názov automatu pre spellchecking [ONLY FIGA]-x - vráti všetky entity s prefixom, ktorý bol zadaný na vstupe [ONLY AUTOCOMPLETE]Popis výstupu:
[čísla riadkov do KB oddelené znakom ;] \tab [počiatočný offset] \tab [koncový offset] \tab [entita/fragment] \tab [FLAG F/S]
Figa - oddeľovacie znaky
Oddeľovacie znaky slúžia vo fige na viaceré účely (viď nižšie). Funkcia marker::to_skip()používa okrem iného aj znaky z reťazca static const char *delimiters (v súbore figa.h) - tie je možné pridávať/odoberať podľa potreby.
Účely oddeľovacích znakov:
marker::to_skip() vráti true pri znaku ., čo aj vráti ak sa znak nachádza v reťazci *delimitersmarker::to_skip() popr. z reťazca *delimitersPríklad spustenia nástroja figa:
Vrátený fragment:
./figav08 -d automata.fsa -p <<< "Putin"
0 1 5 Putin F
Vrátená entita:
./figav08 -d automata.fsa -p <<< "London"
2936223;3019186;3032807;3043156;3055700;3098156;3120755;3187307;3233389;3366587;3408764 1 6 London F
Offset v znakoch:
./figav08 -d automata.fsa -p <<< "Trenčín"
2860691;3110343;3179887;3183231 1 7 Tren쒍쎭n F # zlá interpretácia znakov
Offset v bytoch:
./figav08 -d automata.fsa -p -b <<< "Trenčín"
2860691;3110343;3179887;3183231 1 9 Tren쒍쎭n F # zlá interpretácia znakov
Pre účely autocomplete sa používa script autocomplete.py. Autocomplete podporuje všetky znaky vypísané v abecede uvedenej vyššie (prioritný zoznam znakov) vrátane utf-8 znakov, tzn. vracia také entity, ktoré obsahujú iba znaky z tejto abecedy a ich základ je zhodný so vstupným textom.
UTF-8 znaky sú v automate uložené vo podobe "�" kde 0000 predstavuje hexadecimálny znak [0-9A-F].
Usage:
./autocomplete_py [opts]
Parametre:
-a --return-all - vrátí všechny možné entity-d dictionary - soubor s automatem (je možno zadat více souborů)-f FILE - vstupní soubor-h --help - nápověda-l --lowercase - převést vstup do lowercase-m NUMBER - počet vrácených entit (default 5)-r --remove-accent - odstranit znaky pro výslovnostPríklad spustenia autocomplete:
./autocomplete.py -d a_automata.fsa <<< "Ir" # ./figav08 -a -d a_automata.fsa -p <<< "Ir"
Ir Herbowo 2334250
Ira Bach J 2454591
Ira Belmont 2270971
Ira Block 2334212
Ira C Goodell 2382662
Vrátená entita s utf-8 znakmi:
./autocomplete.py -d a_automata.fsa -m 7 <<< "Ire" #./figav08 -a -d p_automata.fsa -p -m 7 <<<
"Ire"
Ire 1182597;1863634
Ire Wardlaw 1542701
Ire, Yuba 1024623
Irec쎪 Valad쎣o 1097357 # zlá interpretácia znakov
Ireen Kirsch 446907
Ireen Ntonyo 269368
Ireen Sheer 668236
Figa implicitne vracia entity s najdlhším možným názvom. Každé slovo zo vstupu sa nachádza maximálne v jednej entite na výstupe. Pri zapnutí prepínača -o sa toto zmení a figa vracia všetky nájdené entity. Backtracking používa záchytné znaky z premennej static const char *delimiters (v súbore figa.h), na ktoré sa vracia ak bolo vyhľadávanie neúspešné alebo ak bol zadaný prepínač -o. Znaky v tomto reťazci je možné pridávať/odoberať podľa potreby.
Príklad spustenia bez prepínača -o:
./figav08 -d automata.fsa -p <<< "Paris Hilton"
1347157;3339718 1 12 Paris Hilton F
Príklad spustenia s prepínačom -o:
./figav08 -d automata.fsa -p -o <<< "Paris Hilton"
3409299;3417530 1 5 Paris F
1347157;3339718 1 12 Paris Hilton F
3230791;3418233 7 12 Hilton F
Spellchecking bol zavedený do nástroja figa pre účely rozpoznávania entít, v ktorých je preklep. Spúšťa sa pomocou parametru -s FILE kde FILE reprezentuje názov automatu určeného pre spellchecking. Tento automat musí byť vytvorený z rovnakej KB ako základný automat.
Princíp:
Pri rozpoznávaní entít vo vstupnom texte sa ukladajú indexy začiatočných veľkých písmen a ak sa v slove, ktoré začína veľkým písmenom nerozpozná žiadna entita/fragment, spustí sa spellchecking, ktorý sa pokúsi dané slovo opraviť. Skontroluje sa, či sa v automate nachádzajú záznamy, ktoré sú podobné danému slovu (líšiace sa v jednom znaku, popr. také kde treba jeden znak pridať alebo ubrať). Ak sa nenachádza žiaden takýto záznam (entity) v spellchecking automate, pokračuje sa ďalej v prehľadávaní vstupného textu figou. Ak sa nájde jedna podobná entita, vráti sa pôvodné slovo zo vstupu + offsety tohto slova a čísla riadkov danej podobnej entity. Ak sa takýchto podobných entít nájde viac, vrátia sa čísla riadkov všetkých týchto entít spolu s pôvodným slovom, ktoré je "opravované".
Príklady vstupov / výstupov:
./figav08 -d automata.fsa -p -s automata-spell.fsa <<< "Nathaniel"
1755311;1992639 1 9 Nathaniel F
./figav08 -d automata.fsa -p -s automata-spell.fsa <<< "Nsthaniel"
1755311;1992639 1 9 Nsthaniel S
Script je určený na kontrolu niekoľkých chýb, ktoré by sa nemali vyskytovať v namelistoch. Použitie viz. prepínač --help. Príklady chýb, ktoré script dokáže detekovať - viz. nižšie.
Po skontrolovaní script vypíše kontrolné/štatistické údaje o nameliste (možnosť jednoduchého doplnenia scriptu o zber a výpis ďalších údajov podľa potreby).
V scripte je použité obmedzenie na počet chýb - tj. script po určitom počte chýb usúdi, že ďalšie chyby už nie je potreba hľadať a prejde na ďalší namelist, popr. skončí. (nastaviteľné prepínačom -n, viď --help).
Script dokáže kontrolovať aj namelisty, kde sú čísla riadkov do KB binárne kódované (prepínač -b ... viď. --help).
Chyby, ktoré script dokáže detekovať:
Entity on line with missing pipe 2547
Missing number after semicolon|1542;
|1545
Missing number|
N is not at the end|N;5500
utf_char-šč|55554
Umiestnenie:
secapi/NER/figa/make_automat/check_namelist.py
Príklady spustenia:
./check_namelist.py random_namelist.ASCII
===== random_namelist.ASCII =====
max. lenght of line: 158
number of lines: 11713837
-----------------------------------
O.K.
./check_namelist.py -b namelist.bin
===== namelist.bin =====
max. lenght of line: 147
number of lines: 11713837
-----------------------------------
O.K.
Príklady niekoľkých chybných riadkov v nameliste:
./check_namelist.py small_namelist.ASCII
===== small_namelist.ASCII =====
max. lenght of line: 55
number of lines: 50
-----------------------------------
14: Alder River, Canada| # Zly format.
21: Alder Rock|3408516; # Zly format.
23: Alder Sherwood|N;1477681 # Zly format.
32: |1371382 # Zly format.
33: Ačlder burn|3821588 # Unicode character v nameliste.