Indexování termínů - Term indexing

v počítačová věda, a termínový index je datová struktura umožňující rychlé vyhledávání termínů a doložky v logický program,^[1] deduktivní databáze nebo automatizovaný testovací teorém.

Přehled

Mnoho operací v automatických ověřovacích teorémech vyžaduje hledání v obrovských sbírkách výrazů a klauzí. Takové operace obvykle spadají do následujícího schématu. Byla dána sbírka ${ displaystyle S}$ pojmů (doložek) a dotazovaných výrazů (doložek) ${ displaystyle q}$ , nalézt v ${ displaystyle S}$ některé / všechny termíny ${ displaystyle t}$ související s ${ displaystyle q}$ podle určité podmínky načítání. Nejzajímavější podmínky načítání jsou formulovány jako existence substituce, která zvláštním způsobem souvisí s dotazem a obnovenými objekty ${ displaystyle t}$ . Zde je seznam podmínek načítání, které se často používají v testovacích zařízeních:

období ${ displaystyle q}$ je unifiable s termínem ${ displaystyle t}$ tj. existuje substituce ${ displaystyle theta}$ , takový, že ${ displaystyle q theta}$ = ${ displaystyle t theta}$
období ${ displaystyle t}$ je instancí ${ displaystyle q}$ tj. existuje substituce ${ displaystyle theta}$ , takový, že ${ displaystyle q theta}$ = ${ displaystyle t}$
období ${ displaystyle t}$ je zobecněním ${ displaystyle q}$ tj. existuje substituce ${ displaystyle theta}$ , takový, že ${ displaystyle q}$ = ${ displaystyle t theta}$
doložka ${ displaystyle q}$ klauzule subsumes ${ displaystyle t}$ tj. existuje substituce ${ displaystyle theta}$ , takový, že ${ displaystyle q theta}$ je podmnožina / podmnožina ${ displaystyle t}$
doložka ${ displaystyle q}$ je zahrnut do ${ displaystyle t}$ tj. existuje substituce ${ displaystyle theta}$ , takový, že ${ displaystyle t theta}$ je podmnožina / podmnožina ${ displaystyle q}$

Častěji než ne, ve skutečnosti nás zajímá explicitní nalezení vhodných substitucí společně s vyhledanými termíny ${ displaystyle t}$ , spíše než jen při zjišťování existence takových substitucí.

Velice často jsou sady termínů, které se mají prohledávat, velké, volání načítání jsou častá a podmínka načítání je poměrně složitá. V takových situacích lineární vyhledávání v ${ displaystyle S}$ , když je podmínka načítání testována na každém termínu od ${ displaystyle S}$ , se stává neúměrně nákladným. K překonání tohoto problému, speciální datové struktury, tzv indexy, jsou navrženy tak, aby podporovaly rychlé vyhledávání. Takové datové struktury, spolu s doprovodnými algoritmy pro údržbu indexu a vyhledávání, se nazývají techniky indexování termínů.

Klasické techniky indexování

Substituční stromy překonávají indexování cest, indexování diskriminačních stromů a abstrakční stromy.^[2]

Index pojmu diskriminační strom ukládá své informace do a trie datová struktura.^[3]

Moderní techniky indexování

Reference

^ Colomb, Robert M. (1991). "Vylepšení sjednocení v PROLOGU prostřednictvím indexování klauzule". The Journal of Logic Programming. 10: 23–44. doi:10.1016/0743-1066(91)90004-9.
^ Peter Graf."Substitution Tree Indexing".1994.
^ John W. Wheeler; Guarionex Jordan.„Empirická studie indexování termínů při Darwinově implementaci kalkulu evoluce modelu“.2004.p. 5.

Další čtení

P. Graf, Term Indexing, Lecture Notes in Computer Science 1053, 1996 (mírně zastaralý přehled)
R. Sekar a I.V. Ramakrishnan a A. Voronkov, Term Indexing, A. Robinson a A. Voronkov, redaktoři, Příručka automatizovaného uvažování, svazek 2, 2001 (nedávný přehled)
W. W. McCune, Experimenty s indexováním diskriminačních stromů a indexováním cest pro vyhledávání termínů, Journal of Automated Reasoning, 9 (2), 1992
P. Graf, Substitution Tree Indexing, Proc. RTA, Lecture Notes in Computer Science 914, 1995
M. Stickel, The Path Indexing Method for Indexing Terms, Tech. Rep. 473, Centrum umělé inteligence, SRI International, 1989
S. Schulz, jednoduchý a efektivní odběr klauzulí s funkcí indexování vektorů funkcí, Proc. semináře IJCAR-2004 ESFOR, 2004
A. Riazanov a A. Voronkov, Částečně adaptivní kódové stromy, Proc. JELIA, Lecture Notes in Artificial Intelligence 1919, 2000
H. Ganzinger a R. Nieuwenhuis a P. Nivela, Fast Term Indexing with Coded Context Trees, Journal of Automated Reasoning, 32 (2), 2004
A. Riazanov a A. Voronkov, Efficient Instance Retrieval with Standard and Relational Path Indexing, Information and Computation, 199 (1–2), 2005

[1] Colomb, Robert M. (1991). "Vylepšení sjednocení v PROLOGU prostřednictvím indexování klauzule". The Journal of Logic Programming. 10: 23–44. doi:10.1016/0743-1066(91)90004-9.

[2] Peter Graf."Substitution Tree Indexing".1994.

[3] John W. Wheeler; Guarionex Jordan.„Empirická studie indexování termínů při Darwinově implementaci kalkulu evoluce modelu“.2004.p. 5.

[1]

[2]

[3]