Adamantine Blog post
#utility#programování

Nativeextractor - nástroj pro nestrukturovaná data

Pavel Procházka
12/10/2021

NativeExtractor - otevřený nástroj pro zpracování textu

Dlouhodobě se zabýváme zpracováním nestrukturovaných dat. Jedním z důležitých kroků při zpracování takových dat je extrakce pojmenovaných entit. Například tel. čísla, emailové adresy, rodná čísla, vlastní jména apod. V minulosti jsme používali kombinaci regulárních výrazů, globů NERů pro extrakci entit, ale výsledky mívaly velmi kolísavou úroveň, rychlost a spolehlivost. Rozhodli jsme se tedy vytvořit nový nástroj, který tyto nedostatky odstraní. Takovým nástrojem je NativeExtraktor licencovaný pod GNU LGPL licencí.

Projekt je hostován na GitHubu - NativeExtractor.

Doprovodné bindingy pro vysokoúrovňové jazyky jsou na těchto odkazech:

Návody pro instalaci a zprovoznění jsou součástí dokumentace.

Hlavní cíle NativeExtractoru

Kýžené vlastnosti:

Provozní cíle:

Zvolené prostředky:

Extractor

Extraktor je třída, která zajišťuje procházení předaného textu znak po znaku (utf-8) zleva doprava a pro každý procházený znak spouští minery, které jsou na extractor navázány. Během procesu procházení shromažďuje informace o nalezených entitách - tzv. occurrences.

Minery

Miner je de-facto ručně optimalizovaný krátký programový kód, který je schopen rozpoznat jeden typ entity (například emailovou adresu, telefonní číslo, ...) v libovolném místě textu. Entrypoint mineru se spouští pro všechny utf-8 znaky postupně zleva doprava a je schopen pracovat s celým kontextem - v okolí znaku se lze neomezeně pohybovat doprava i doleva a pracovat s veškerými prostředky procesu. Pro ilustraci se podívejme na primitivní miner, který umí rozpoznat entitu "hello":

// Hlavičkové soubory
#include <nativeextractor/miner.h>
#include <nativeextractor/unicode.h>

/* Hledá řetězec "hello". Proměnná m reprezentuje stav mineru. */
static occurrence_t* match_hello_impl(miner_c* m) {
  // Zaznamenáme začátek řetězce
  if (!m->mark_start(m)) return NULL;
  // Pokusíme se nalézt od aktuálního místa dále ve směru zleva doprava text hello, pokud se to nepovede, vrátíme výskyt NULL.
  if (!m->match_string(m, "hello", Right)) return NULL;
  // Zaznamenáme konec řetězce hello.
  if (!m->mark_end(m)) return NULL;
  // Vytvoříme výskyt s pravděpodobností 1.0 a vrátíme.
  return m->make_occurrence(m, 1.0);
}

/* Registrace mineru. */
miner_c* match_hello() {
  return miner_c_create("Hello", NULL, match_hello_impl);
}

/**
 * Metainformace pro sdílenou knihovnu
 * Formát je: [ "funkce1", "entita1", "funkce2", "entita2", ..., NULL ]
 */
const char* meta[] = {
  "match_hello", "HELLO",
  NULL
};

Miner může pohybovat svou čtecí hlavou doprava i doleva podle potřeby. Všimněme si metody mark_start(), která zaznamenává aktuální polohu čtecí hlavy v textu jako začátek entity a metody mark_end(), která zaznamená aktuální polohu hlavy jako konec výskytu entity.

Minery jsou v praxi samozřejmě typicky složitější než match_hello(), lze je využít například k hledání:

Výrazy typu Glob alias wildcard matching

V našich produktech potřebujeme často vyhledávat klíčová slova ve formě Glob výrazů. Pro tento účel jsme vyvinuli miner, který tuto sémantiku nabízí. V praxi to funguje tak, že se připraví pro každý glob jeden miner, který je parametrizován právě glob výrazem. Můžeme si uvést krátký příklad použití.

// Instanciace extractor_c
miner_c ** miners = calloc(1, sizeof(miner_c*));
extractor_c * e = extractor_c_new(1, miners);

// Přidání globu *.exe
if(!e->add_miner_so(e, "./build/debug/lib/glob_entities.so", "match_glob", (void*)"*.exe") {
  printf("Error adding miner %s\n", e->get_last_error(e));
  return EXIT_FAILURE;
}

Při následném procházení streamu se budou na výstupu objevovat entity, které končí řetězcem .exe.

Nativní regulární výrazy

Součástí NativeExtractoru je také unikátní překladač regulárních výrazů do nativního procesorového kódu. Principielně funguje tak, že regulární výraz přeloží do jazyka C a vyrobí tak miner, který lze dále používat jako každý jiný miner. Překladač se aktuálně zaměřuje na podporu regulárních výrazů bez nekonzervativních rozšíření - plná podpora základních regulárních výrazů s podporou utf-8.

Pro demonstrační účely jsme vyvinuli jednoduchý nástroj ngrep podobný široce používanému nástroji GNU grep.

Princip překladu

Překlad regulárních výrazů probíhá interně v těchto krocích:

V krátkosti zmíníme příklad překladu, povšimněte si, že jsem taky dbali na čitelnost Cčkového mezi-kódu. Následující vzorek kódu odpovídá výrazu .*@.*.

#include <nativeextractor/miner.h>
#include <nativeextractor/extractor.h>
#include <nativeextractor/unicode.h>

static inline bool state_regex_0(miner_c *e);
static inline bool state_regex_1(miner_c *e);
static inline bool state_regex_2(miner_c *e);
static inline bool state_regex_3(miner_c *e);

/* inline funkce reprezentující uzel 0, při přechodu do jiného uzlu zkonzumujeme znak pomocí pohybu Right - vpravo */
static inline bool state_regex_0(miner_c *e) {
  if (false
    || e->match(e, "@", Right)) { /* pokud je na pásce @ přechod do stavu 2 */
    return state_regex_2(e);
  }
  if (false /* pokud je na pásce zalomení řádku, přechod do stavu 1 */
    || e->match_fn(e, unicode_not_islinebreak, Right)) {
    return state_regex_1(e);
  }
  /* přechod do zamítacího stavu */
  return false;
}

static inline bool state_regex_1(miner_c *e) {
  if (false
    || e->match(e, "@", Right)) {
    return state_regex_2(e);
  }
  if (false
    || e->match_fn(e, unicode_not_islinebreak, Right)) {
    return state_regex_1(e);
  }
  return false;
}

static inline bool state_regex_2(miner_c *e) {
  if (false
    || e->match_fn(e, unicode_not_islinebreak, Right)) {
    return state_regex_3(e);
  }
  return true;
}

static inline bool state_regex_3(miner_c *e) {
  if (false
    || e->match_fn(e, unicode_not_islinebreak, Right)) {
    return state_regex_3(e);
  }
  return true;
}

static occurrence_t *match_regex_regex_impl(miner_c *e) {
  mark_t mark;
  e->mark_pos(e, &mark);
  e->mark_start(e);
  e->reset_pos(e, &mark);
  if (state_regex_0(e)) {
    e->mark_end(e);
    return e->make_occurrence(e, 1.0);
  }

  e->reset_pos(e, &mark);
  return NULL;
}

miner_c* regex() {
  return miner_c_create(".*@.*", NULL, match_regex_regex_impl);
}


const char *meta[] = {
  "regex", ".*@.*",
  NULL
};

Reálné nasazení nativních regulárních výrazů v nativeextractoru

Vzhledem ke skutečnosti, že například ve vysokoúrovňových jazycích obecně nelze průhledně pracovat s mapovanou pamětí tak, aby se na ni dalo dívat jako například na pole v daném jazyce, nelze na ni použít klasické vestavěné implementace regulárních výrazů. Navíc naše implementace vnáší možnost efektivně zpracovávat více regulárních výrazů paralelně nad stejnou pamětí a taky velmi rychle - díky nativnímu překladu regulárních výrazů do podoby minerů.

Vlastní implementace Radix tree pro rychlý match

Častou operací při implementaci entit je přístup do slovníku - například validace národních předvoleb u telefonních čísel. Aby tato operaci byla co nejefektivnější, přistoupili jsme k implementaci Radixového stromu, který jsme nazvali Patty trie a přisoudili jsme mu tyto vlastnosti:

Kde získat minery?

Součástí NativeExtractoru je miner glob v adresáři src/miners a dále v src/examples se nachází naive_email_parser.c, který slouží jako naivní implementace parseru emailů pro edukativní účely. Další minery lze implementovat vlastními silami. Případně se můžete obrátit na tým SpongeData.cz, který vyvinul sadu minerů MinersNonFree pod nesvobodnou licencí.

Shrnutí a budoucnost projektu

NativeExtractor je základní nástroj pro efektivní těžbu pojmenovaných entit z velkých i malých souborů, který lze používat z vyšších programovacích jazyků jako je Python a Node.js, případně s malou mírou úsilí i v dalších jazycích. Vyznačuje se zejména vysokým výkonem, technickou vybaveností pro tento úkol a rozumným návrhem pro další rozšiřování.

Do budoucna bychom chtěli implementovat těžery pro extrakci entit jako jsou vlastní jména, názvy společností, úřadů, geografické informace apod. Máme na mysli také kompilaci neuronových sítí a genetických algoritmů do formy minerů, a využít tak slibných výsledků z oblasti DeepLearningu.

Antivirová kontrola nové generace

Produkt Adamantine zvyšuje ochranu před únikem citlivých údajů Vašich zákazníků.

Kontaktujte nás